离散对数密码系统安全性分析与安全实现技术研究

论文摘要

离散对数问题因其计算复杂、结构灵活多变为密码体制的设计提供了良好的安全性基础。用目前已知的最好的算法求解n阶乘法群中的离散对数仍然需要O(（n）1/2)次群运算,它比分解因子问题要更难一些。因此被广泛用于密码体制的设计,如美国的数字签名标准DSS、欧洲的TESS等。目前,离散对数问题已经成为密码学研究中的一类重要原语。本文以基于离散对数的密码系统为研究对象,系统研究其从安全设计到安全实现过程中的一系列问题,以帮助设计者更好地利用离散对数设计并实现密码应用系统。本文系统分析了现有求解离散对数问题的算法的特点、性能以及适用范围,根据算法的计算复杂性给出了密码体制安全参数选择的依据。论文介绍了一些著名的基于离散对数的密码体制,重点研究了作为密码体制的基本构件-承诺体制和知识证明协议的设计与应用,用离散对数构造了一个在CR2（Concurrent-Reset-2）下安全的陷门承诺体制,分析了传统基于离散对数承诺体制的可延伸性,首次将Diffie-Hellman密钥协商方案用于随机挑战的生成以阻止知识证明的可延伸性,设计出了一种新的基于Diffie-Hellman密钥协商的不可延伸的承诺体制。论文也系统研究了密码体制的安全性证明方法学,研究了在随机ORACLE模型、一般群模型以及证据独立性模型下理想系统的安全性证明方法,重点分析了理想系统的可证明安全性并不能蕴涵其应用系统的安全性的原因,提出了离散对数密码体制安全性的一般证明方法,并以数字签名体制为例,对证明过程的有效性与公平性问题进行了探讨。本文还注意到密码体制的安全性证明与数学上的证明不同,其结论只在一定的概率界内成立,绝对的安全是不存在的。论文对离散对数密码系统的安全性进行了全面的分析。从离散对数问题所依赖的群的数学结构与系统实现环节两个方面研究了攻击的可能性和技术途径。通过对素数模乘法群、合数模乘法群以及素数阶子群中离散对数问题的安全性分析,分别给出了这些群的安全结构形式,以阻止攻击者使用具有光滑阶的生成元或使用特殊结构的合数模进行攻击。大量事实表明,基于系统实现中的低级错误和系统执行环境中的漏洞的攻击因其具有实现简单、成本较低等特点,已经对密码系统的安全性形成更大的威胁。由于现实系统中不具有理想系统的随机性与独立性保证,系统实现过程中很容易人为地植入错误,所以理想系统的安全性并不能保证应用系统的安全,这使得系统安全实现问题成为一个新的研究方向。为此,本文重点研究了系统的安全实现技术,采用安全协议工程的思想,提出了密码系统安全实现的基本原则、任务与目标,设计了系统安全实现平台的基本构架,针对离散对数密码系统的特点,研究并设计了参数验证、消息鉴别、密钥独立性与协议执行独立性机制,以防止攻击者利用参数弱化、消息重定向、消息重放及已知密钥等实施攻击。将容侵思想应用密码系统的安全实现,利用失败-停止协议（Fail-stop protocol）的技术原理,设计了基于消息链验证和基于等待时间的容侵机制,使得任何主动攻击都不会造成秘密数据的进一步泄露,为系统提供最后一道安全防线,即使受到攻击也能将危害降到最低。同时,使用基于失败-停止原理的容侵机制可以简化系统的安全实现工作,使设计者将更多的精力放到预防被动攻击和内部攻击上,只要建立合适的主动攻击行为检测机制,则只要系统在被动攻击下是安全的,那么在主动攻击下也是安全的。此外,本文还对目前尚处于发展之中的协议形式化描述语言（如CAPSL等）以及编译器的功能与体系结构进行了介绍与探讨。

论文目录

• 摘要
• ABSTRACT
• 1 绪论
• 1.1 离散对数在密码学中的地位与作用
• 1.2 基于离散对数密码系统的安全性问题
• 1.3 安全性与可实现性的关系
• 1.4 安全实现的任务、目标与技术
• 1.4.1 安全实现的必要性
• 1.4.2 安全实现的任务与目标
• 1.4.3 安全实现技术
• 1.5 论文的主要目标与研究工作
• 2 离散对数问题及其算法
• 2.1 预备知识
• 2.2 离散对数问题及其变体
• 2.2.1 一般离散对数问题描述
• 2.2.2 离散对数问题的变体形式
• 2.3 离散对数的一些重要结论与特征
• 2.4 离散对数计算技术
• 2.4.1 Shank 算法
• 2.4.2 Pollard Rho 算法
• 2.4.3 Pollards Lambda（λ） 算法
• 2.4.4 Pohling-Hellman 算法
• 2.4.5 基本指数积分法
• 2.4.6 线性筛选算法
• 2.4.7 三次筛选方法
• 2.5 关于离散对数算法的评述
• 2.5.1 指数算法的分析
• 2.5.2 指数积分算法的分析
• 2.6 本章小结
• 3 基于离散对数的密码体制
• 3.1 Diffie-Hellman 密钥协商协议
• 3.1.1 Diffie-Hellman 密钥协商基本方案
• 3.1.2 固定指数的Diffie-Hellman 密钥协商协议
• 3.1.3 单向认证的ElGamal 密钥协商协议
• 3.1.4 MTI/A0 密钥协商协议
• 3.1.5 端对端相互认证的密钥协议STS
• 3.1.6 隐式证明公钥
• 3.2 基于离散对数的知识证明
• p^* 中的离散对数的协议'>3.2.1 证明知道素数模Z_p^*中的离散对数的协议
• n^* 中离散对数的协议'>3.2.2 证明知道模合数模Z_n^*中离散对数的协议
• + 协议'>3.2.3 在未知阶子群中证明知道离散对数的∑⁺协议
• 3.3 基于离散对数的承诺体制
• 3.3.1 Pedersen 承诺体制
• 3.3.2 基于离散对数的陷门承诺体制设计
• 3.3.3 基于离散对数的不可延展的承诺体制设计
• 3.4 身份认证体制
• 3.4.1 Schnorr 身份认证协议
• 3.4.2 CR2 安全的身份认证协议设计
• 3.5 基于离散对数的数字签名体制
• 3.5.1 数字签名体制及其安全性概念
• 3.5.2 El Gamal 数字签名体制
• 3.5.3 Schnorr 签名体制
• 3.5.4 DSA 签名算法
• 3.5.5 KCDSA 签名体制
• 3.5.6 带消息恢复的Neber-Rueppel 签名体制
• 3.5.7 盲签名体制（Okamoto-Schnorr 盲签名体制）
• 3.6 本章小结
• 4 离散对数密码体制的安全性证明方法
• 4.1 随机ORACLE 模型及其有效性分析
• 4.1.1 随机ORACLE 模型
• 4.1.2 理想系统的实现
• 4.1.3 随机ORACLE 方法的无效性
• 4.1.4 随机ORACLE 模型的真正作用
• 4.2 一般群模型及其有效性
• 4.2.1 一般算法及其计算复杂性
• 4.2.2 一般群模型的有效性讨论
• 4.3 安全性证明的一般方法
• 4.4 数字签名体制的证明方法
• 4.4.1 基本思想
• 4.4.2 无消息攻击下的伪造定理及其应用
• 4.4.3 自适应选择消息攻击下的伪造定理及其应用
• 4.4.4 关于签名体制安全性证明中的一些思考
• 4.5 证据不可区分性证明
• 4.5.1 证据不可区分性的概念
• 4.5.2 证据不可区分性的应用
• 4.6 本章小结
• 5 离散对数密码体制的结构安全性与实现安全性分析
• 5.1 基于数论的攻击
• p^* 中离散对数问题安全性分析'>5.1.1 Z_p^*中离散对数问题安全性分析
• p^* 的素数阶子群中的离散对数问题安全性分析'>5.1.2 Z_p^*的素数阶子群中的离散对数问题安全性分析
• n^* 中离散对数的安全性分析'>5.1.3 Z_n^*中离散对数的安全性分析
• 5.1.4 Diffie-Hellman 问题及其变体的安全性分析
• 5.2 基于验证机制的攻击
• 5.2.1 基于体制参数验证的攻击
• 5.2.2 基于消息验证的攻击
• 5.3 基于实现中的漏洞的攻击
• 5.4 结构安全性与效率的平衡问题
• 5.4.1 安全结构参数的估计与生成
• 5.4.2 系统参数的选择与系统的效率
• 5.5 本章小结
• 6 安全实现技术
• 6.1 系统安全实现的主要任务与目标
• 6.2 密码应用系统的组成与结构
• 6.3 验证机制的设计
• 6.3.1 系统参数验证机制的实现
• 6.3.2 消息验证机制的设计
• 6.4 密钥共享与密钥管理
• 6.5 容侵机制的设计
• 6.5.1 失败-停止协议及其在容侵实现中的作用
• 6.5.2 基于消息链鉴别的攻击检测方法
• 6.5.3 基于等待时间的攻击检测机制
• 6.5.4 容侵签名体制
• 6.6 密码系统安全实现平台的基本架构
• 6.6.1 协议模型设计
• 6.6.2 安全性分析
• 6.6.3 性能分析
• 6.6.4 系统模拟运行与攻击实验
• 6.6.5 辅助代码生成
• 6.6.6 标准构件库
• 6.7 形式化描述语言—CAPSL
• 6.7.1 CAPSL 的基本概念
• 6.7.2 CIL
• 6.8 编译器的构造
• 6.8.1 构造编译器面临的问题
• 6.8.2 编译器的体系结构
• 6.9 本章小结
• 7 结论与展望
• 7.1 本文的主要贡献和创新点
• 7.2 今后需要进一步做的工作
• 致谢
• 参考文献
• 附录
• A. 本人在攻读博士学位期间发表的学术论文
• B. 在攻读博士学位期间从事的科研项目