密码学系列| 2.7 A Collision Algorithm for the DLP

密码学 2年前 (2022) admin
832 0 0


Chapter 2 

Discrete Logarithms and Diffie–Hellman

2.7 A Collision Algorithm for the DLP


在本节中,我们将介绍 Shanks 提出的一种离散对数算法,是一种碰撞或中间相遇算法。这类算法将在第 5.4, 5.5 节中进行更详细的讨论。5.4和5.5。该算法适用于任何群体,而不仅仅是  。对于任意群来说,证明该算法的正确有效性也并不困难,所以我们证明它的一般形式。

我们首先回顾求解DLP的普通蛮力算法的运行时间。

命题 2.19 (DLP 的平凡界)假设我们有群 ,  为  中一个具有阶  的元素(即不存在比  小的正整数  满足  。那么离散对数问题

通过占用  的内存,在   步内将被解决。其中,每一步包含了一次  的乘法运算。

证明:在普通蛮力算法中,我们只需要不断地计算  所有的值都是连续的,每一个值都可以由前一个值生成,所以我们一次只需要存储两个值。如果  存在,那么  将在  次运算内出现。

注 2.20 如果我们在  内进行运算,那么每次计算  将需要  次计算机运算,其中常数  和隐含在  内的常数取决于计算机和用于模乘的算法。那么对于计算机来说,该算法的running time 为  。

接下来介绍的碰撞算法背后的思想其实就是构造两个列表,找到其中在两个表都出现过的元素。对于命题 2.19 中的离散对数问题,碰撞算法的 running time 大约为 ,当  很大的时候,对比  , 将节省很大的运算开支。

命题 2.21 (Shanks’s Babystep-Giantstep Algorithm,BSGS) 假设我们有群 ,  为  中一个具有阶 的元素。下述算法将使用  内存,在  运行步骤内解决 DLP。

  1. 设 
  2. 构造两个列表(List 1 中不断地乘以  被称作 “baby step”,List2 中不断地乘以  ,被称作 “giant step”。)

  1. 在两个列表中找到相同的值,设 
  2. 那么  即为  的解。

证明:首先,我们看到 List2,我们先计算 ,然后计算  完成 List2 的构造。所以两个 List 的构造大约需要  次乘法运算。然后,假设碰撞存在,那么我们用标准的排序和搜索算法可以在大约  的一个小倍数的步骤内找到这个碰撞。所以步骤 3 需要  步,所以算法的总running time 是 

最后,在步骤 2 中一个列表的长度是 ,所以算法需要  的内存用于列表的存储。

为了证明这个算法是有效的,我们需要证明碰撞总是存在的。为此,我们假设  为  的解,我们将 写为

我们知道 ,所以

所以我们可以将  表示为

显然 ,所以 List1 和 List2 肯定会有相同的元素。

例 2.22 我们将使用下述例子来具体描述 BSGS 的算法流程。

其中  的阶为 ,根据算法,我们设 ,并且计算 ,表 2.4 列出了  的一些值

密码学系列| 2.7 A Collision Algorithm for the DLP

在表中我们可以找到

因为 ,代入上式

即  为  的解。

密码学系列| 2.7 A Collision Algorithm for the DLP

原文始发于微信公众号(山石网科安全技术研究院):密码学系列| 2.7 A Collision Algorithm for the DLP

版权声明:admin 发表于 2022年4月14日 上午10:30。
转载请注明:密码学系列| 2.7 A Collision Algorithm for the DLP | CTF导航

相关文章

暂无评论

您必须登录才能参与评论!
立即登录
暂无评论...