密码学｜5.4.3 一个针对离散对数问题的碰撞算法

admin
admin
admin
101138
文章
87
评论
2023年1月31日11:55:05评论15 views字数 1722阅读5分44秒阅读模式
碰撞算法在密码学中有许多应用，包括密钥、明文或密文的搜索恢复，或者是解决一个公钥密码系统基于的数学困难问题。在这一节中，我们将通过一个针对离散对数问题的具体算法来说明这一理论。对于有限域 下的离散对数问题，该算法大约需要运行  步。
读者可能会觉得命题 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.38），我们将  视为包含  个球的盒子，列表  视为将其中的  个球画上红色。
然后，我们选取元素  ，并计算

密码学｜5.4.3 一个针对离散对数问题的碰撞算法

以构造另一个集合。
假设问题  有解，即  是  的某次幂，那么就意味着某个  也在集合  中。那么集合  也可以视为在盒子中取  个球。于是我们想知道第二次至少取到一个红球的概率是多少，也就是两个集合中至少有一个元素相匹配的概率。根据碰撞定理 （5.38）

因此，如果我们设定  ，概率将高达 ，几乎可以看作至少存在一个匹配了。如果还不放行，设 ，那么存在匹配的概率将高于 。注意到，一旦我们找到两个列表中的匹配，即意味着有 ，也就能解得 。
那么找到这样一个匹配大概要耗时多久呢？两个列表均含有  个元素，那么构造这样两个列表大约需要 步，更准确的，每个列表中的每个元素都是 ，需要进行一次幂运算，根据1.3.2 一节介绍的幂次算法，大约需要进行  次群乘法运算。因此两个列表一共需要约  次群乘法运算。另外，还需要去检查第二个集合中的某个元素是否存在于第一个元素（例如，对第一个集合进行排序），所以又大约需要 步。因此，求一个和，大约需要

选取  可以获取  的成功概率，那么

例 5.45
我们用一个例子来说明上述过程，解以下离散对数问题

数字  具有阶 658，因此它是一个原根。于是，在这个例子中 。我们随机选取元素  并计算 ，直到我们找到一个匹配。（计算过程如表 5.9 所示

密码学｜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 一个针对离散对数问题的碰撞算法

  • 左青龙
  • 微信扫一扫
  • weinxin
  • 右白虎
  • 微信扫一扫
  • weinxin
admin
  • 本文由 发表于 2023年1月31日11:55:05
  • 转载请保留本文链接(CN-SEC中文网:感谢原作者辛苦付出)：
                   密码学｜5.4.3 一个针对离散对数问题的碰撞算法http://cn-sec.com/archives/1530707.html

发表评论

匿名网友 填写信息