一个改进的离散对数问题攻击算法

1、一个改良的离散对数问题攻击算法很多密码技术的平安性都建立在离散对数问题的困难性上 ,如 Diffie Hellman 密钥协议 1 , EIGamal 密码体制及其签名 方案， 以及它们的变种等。 Diffie Hellman 问题2 ，模合数 n 乘群 Z*n 中的离散对数问题， 以及 n 的因子分解问题， 在密码学上存 在 一定的关联，它们的困难性存在着内在的等价性 1 。针对离散对数问题有许多攻击方法，目前的有穷举攻击， Pohlig Hellman 攻击 3 ，指数积分攻击 3 ， Pollard 概 率 攻击 3 ，小步大步攻击 2 ， 4 ，袋鼠攻击 5 和生日攻击 6 等。 这些

2、攻击方法往往在某些特定场合尤其有效， 如当 p-1 为形 如 2 的 幂次方 6 ， p-1 的因数都较小 3 或 p 的位数较短时。小 步大步 攻击算法那么适合于包括椭圆曲线 2， 3在内的所有离散 对数问题，是 本文进行研究并加以改良的对象。对于小步大步攻击算法， 在忽略对数因子的情况下， 其时 间 复杂度为 0(n) ，已接近于离散对数问题的任何通用算法的复杂性下界6 ，但仍留有值得优化的余地。另一方面，空间复杂 度较大一直是小 步大步算法的缺乏之处。1 离散对数问题 离散对数的求解虽是困难的， 但其逆运算即指数运算， 可以 应用平方乘的方法有效地计算。 假设将指数用有符号的二进制数表

3、示，使 之具有较小的海明权重 7 ，那么可以进一步减少其中乘法 的次数，从 而提高运算速度。2 小步大步攻击算法及分析小步一大步(Baby Step Gia nt Step)攻击算法有时也称 为 Shanks 算法4, 具体实现如下面的算法 1 所示。其中参数 n, a， B 的 意义与定义 1 中的定义相同。3 改良算法先给出改良后的算法描述 ,其中参数与算法 1 完全相同。4 改良算法的性能分析同样以群乘法为根本运算单位， 分析改良算法的时间和空间 复 杂性。与算法 1 一样，在第 1)步，要先预计算 a m 并缓存。虽时 间复杂 度仍为 O(logm) ，但在(1.2)步中将指数 m 采

4、取具有较小 海明权重 7 的 表示方式， 可以显著减少其中乘法的次数， 从而 可以平均提高大致 11% 的运算速度 2 。由于平方运算最快可以 比两个不同整数的乘法运算 快两倍 1 ，所以这项措施的好处是 非常明显的； 同时在 (1.3) 步中 采用多精度平方乘算法 1 ，可进 一步提高运算速度。5 两算法的比照 由上面的分析，可归纳出两个算法的主要不同之 处在于：1) 存贮表的数目。 算法 1 需要两个表， 而算法 2 那么只需 1 个 , 从而存贮器开销不同2)表元素的比拟时机。 算法 1 是两组数据 (两张表 )都计算完 成 后再进行比拟， 而算法 2 那么是只需在第一张表完成的根底上即

5、 可开 展比拟工作。5) 表排序与查表时间。 算法 1 需对两张表都排序， 且查表时 间 与表的规模直接相关 (为 0(m) ) 。而算法 2 由于引入抗冲突 的哈希函数， 无须排序操作，且查表时间也降为O(1) 。6 进一步的改良措施 改良后的小步大步攻击算法较原算法而言 进行了算法实 现上的多项优化， 但这仅是针对算法本身的优化， 两 种算法所面 对的问题规模仍然是相同的。 可以尝试通过降低问题的规 模来进 一步缩短攻击算法的计算过程。 这一点对于比特位较长的素数 p 意义更加明显。7 结语 本文将改良后的小步大步攻击算法与原算法的性能进行 了比照分析， 说明上述改良措施均是正确而行之有效的。 如何减 少 存贮开销， 尽量防止或减少求逆元运算， 如何有效应用多精度 算法， 以及通过变换指数表现形式来加速幂运算速度等， 都值得 在日益广泛 应用的密码系统和签名方案的实现过程中加以充分 考虑和探讨。努力提高攻击算法的运算效率只是一个方面的工作， 延伸到 如 何降低算法的输入规模将是一件非常有意义的工作。 本文仅讨