碰撞算法在密码学中有许多应用，包括密钥、明文或密文的搜索恢复，或者是解决一个公钥密码系统基于的数学困难问题。在这一节中，我们将通过一个针对离散对数问题的具体算法来说明这一理论。对于有限域 下的离散对数问题，该算法大约需要运行 步。
读者可能会觉得命题 5.44 介绍的具有 复杂度的碰撞算法没啥意义，因为在第 2.7 一节介绍的确定性算法：baby step–giant step (bsgs) 也是需要这样的时间复杂度。并且两个算法还都需要占用 的存储空间，当常数 是一个较大数字时，这将是一个严峻的问题。所以命题 5.44 介绍的算法可以看做是 Pollard‘s 算法的一个 ”warm-up” 版本。我们将在 5.5 一节介绍该算法，其仍具有 时间复杂度，但是仅占用 的存储空间。
或者又有读者疑惑为什么要使用这些 的碰撞算法，比如在 一节介绍的 index calculus 算法能够更快速的解决 下的离散对数问题。但是，在其他群结构中，比如椭圆曲线群，碰撞算法则是已知的最快的解决离散对数问题的方法。因此这也是为什么要在密码学中使用椭圆曲线这样的代数结构：至今为止，在同样的数量级下，解决椭圆曲线下的离散对数问题相较于解决 下的离散对数问题要更为困难。（我们将在第六章介绍椭圆曲线在密码学中的应用）
命题 5.44
设有群 ， 是群中具有阶 的一个元素，即 ，并且 不存在比 更小的幂次等于 。并且设下述离散对数问题存在解
那么我们可以在 步内找到解，其中每一步都会用到群 内的一个幂次元素。（注意到由于 ，通过1.3.2 一节介绍的幂次算法，我们可以使用少于 次群乘法计算 的任意幂次）
我们构造两个数据列表，分别存储 和 ，然后去找到两个列表中是否有相匹配的值。
![密码学｜5.4.3 一个针对离散对数问题的碰撞算法]( "密码学｜5.4.3 一个针对离散对数问题的碰撞算法")
注意到列表 中的值均在集合 中。所以 是集合 中的（大约） 元素。根据碰撞定理（定理5.38），我们将 视为包含 个球的盒子，列表 视为将其中的 个球画上红色。
![密码学｜5.4.3 一个针对离散对数问题的碰撞算法]( "密码学｜5.4.3 一个针对离散对数问题的碰撞算法")
假设问题 有解，即 是 的某次幂，那么就意味着某个 也在集合 中。那么集合 也可以视为在盒子中取 个球。于是我们想知道第二次至少取到一个红球的概率是多少，也就是两个集合中至少有一个元素相匹配的概率。根据碰撞定理 （5.38）
因此，如果我们设定 ，概率将高达 ，几乎可以看作至少存在一个匹配了。如果还不放行，设 ，那么存在匹配的概率将高于 。注意到，一旦我们找到两个列表中的匹配，即意味着有 ，也就能解得 。
那么找到这样一个匹配大概要耗时多久呢？两个列表均含有 个元素，那么构造这样两个列表大约需要 步，更准确的，每个列表中的每个元素都是 ，需要进行一次幂运算，根据1.3.2 一节介绍的幂次算法，大约需要进行 次群乘法运算。因此两个列表一共需要约 次群乘法运算。另外，还需要去检查第二个集合中的某个元素是否存在于第一个元素（例如，对第一个集合进行排序），所以又大约需要 步。因此，求一个和，大约需要
数字 具有阶 658，因此它是一个原根。于是，在这个例子中 。我们随机选取元素 并计算 ，直到我们找到一个匹配。（计算过程如表 5.9 所示
![密码学｜5.4.3 一个针对离散对数问题的碰撞算法]( "密码学｜5.4.3 一个针对离散对数问题的碰撞算法")
table 5.9
通过长度为 的集合，我们就找到了匹配，解决了这个离散对数问题（取长度为 ，我们有 的概率找到匹配，因此这一次算是比较幸运），解为
注 4.46
命题 2.21 和 5.44 均能够在 步内解决离散对数问题。有趣的是，在某种意义上，Victor Shoup 在论文《 Lower bounds for discrete logarithms and related problems》中表明，不可能存在一个通用算法来以少于 的步骤来求解任意有限群中的离散对数问题，其中 是群阶因子中的最大素数。
原文始发于微信公众号（山石网科安全技术研究院）：密码学｜5.4.3 一个针对离散对数问题的碰撞算法
免责声明:文章中涉及的程序(方法)可能带有攻击性，仅供安全研究与教学之用，读者将其信息做其他用途，由读者承担全部法律及连带责任，本站不承担任何法律及连带责任；如有问题可邮件联系(建议使用企业邮箱或有效邮箱,避免邮件被拦截，联系方式见首页)，望知悉。
点赞
http://cn-sec.com/archives/1530707.html
复制链接
复制链接
-
左青龙
- 微信扫一扫
-
-
右白虎
- 微信扫一扫
-
评论