论文部分内容阅读
Diffie-Hellman(DH)密钥协商协议是一种安全协议，它可以让双方在完全没有对方任何预先信息的条件下通过不安全信道创建公共密钥，该密钥可在后续通讯中作为对称密钥加密通讯内容。DH协议的安全性是基于有限域上的离散对数问题。本文主要研究了离散对数问题以及DH协议的相关问题。具体地，在如下两方面进行了研究并取得了一定进展。 1.离散对数问题通常，人们对于离散对数问题的求解主要是对PollardsKangaroos算法的改进，尝试通过减少跳跃次数来优化算法。目前解决这一问题的最优低存储算法是Van Oorschot和Wiener版本的Pollards Kangaroos算法，其平均情况下的时间代价是(2+O(1))√N次群运算。文中对解决这一问题的经典Pollards IKangaroos算法进行改进得到新的求解算法。新算法是通过利用多次小整数乘法代替一次完整的大整数乘法来减少kangaroos每次跳跃的时间代价实现算法效率的提高。进一步，通过增加kangaroos的数量使得算法在跳跃次数和每次跳跃的时间代价两方面都得到改进，从而得到区间上离散对数问题更有效的求解算法。 2.DH密钥的多项式信息泄露问题本部分研究主要针对2004年Sh-parlinski提出的探索性问题，即对给定的Oracle，其返回的错误值无法区分并且全部的输入均随机。本文证明，给定一个可返回DH密钥多项式信息的Oracle，即用gx和gy询问Oracle时，其可返回DH密钥的多项式信息F(gxy)，其中，F(X)是确定的m-稀疏多项式，存在多项式时间算法可恢复DH密钥。证明恢复DH密钥的多项式信息的困难性和恢复整个密钥的困难性相同。进一步，本文还研究了DH问题的几个相关变体，DHg(2，gy)，n-DH问题及MDH问题，并分别得到类似结果。 这两大类问题是许多密码系统和签名系统的安全性基础，对其进行研究，不但对算法的设计及密码系统的设计有很大帮助，而且对现代密码学的发展也有重要意义。