密码学 | 5.5.2 通过Pollard’s ρ Method离散对数

密码学 1个月前 admin
98 0 0

5.5.2 Discrete Logarithms via Pollard’s ρ Method

在这一节中,我们将讨论如何使用 Pollard’s ρ Method 解决如下离散对数问题,其中  是  下的一个原根。

想法是找到  和  的碰撞,然后我们就有 ,有这样的关系离解决这个离散对数问题就不远了。
问题在于扰乱函数  的选取,其需要能够很好地将  中的元素扰乱,但是又比较简单,这样方便追踪其轨道。 Pollard 在 《Monte Carlo methods for index computation (mod p)》给出建议
密码学 | 5.5.2 通过Pollard’s ρ Method离散对数
需要注意的是在使用式  时需要将  取余  到区间  中,

注 5.51 其实并没有人能够证明式  是足够随机的以确保定理  能够适用,但是在实践中  表现效果还是不错的。不过, Teske 在《Speeding up Pollard’s rho method for computing discrete logarithms, in Algorithmic Number Theory》 和 《 Square-root algorithms for the discrete logarithm problem (a survey), in Public-Key Cryptography and Computational Number Theory》 表明  并没有很好的随机性以给出最佳效果,并且她还给出了一些更复杂的函数例子,称在这些函数中 Pollard’s ρ Method 工作的很好。

考虑我们从  开始不断地对其进行  映射会发生什么。在每一步中,  将乘以  或者 ,或者计算其二次方,于是最终我们得到一个  的幂次乘以  的幂次。即  步后我们得到

我们并不能预测  的值,但是我们可以在每一步计算中对其进行以下方式地记录,显然 
密码学 | 5.5.2 通过Pollard’s ρ Method离散对数
因为 ,所以  的计算是在模  中的,否则的话它们的值在后面会变得非常的大。
然后就是跟之前一样,计算  ,然后  ,其中  的记录规则同  一致,就是每次计算要记录两次,当然,第一次记录规则根据 ,第二次记录规则根据 
我们不断地进行映射,直到找到  和  的碰撞,即有

我们设 ,即有 ,等价

(5.42)vlogg(h)u(modp1)

果满足 ,那么我们在式 5.42 两边同乘一个  的逆元就可以得到 ,从而也就解决这个离散对数问题了。
更一般的,如果 ,那么我们先使用拓展欧几里得算法找到  满足 ,然后式 5.42 两边同乘 ,得

(5.43)dlogg(h)w(modp1)

中 ,并且我们知道除了  外的所有值。事实上,由于  整除 ,这会使得其肯定也整除 ,因此  就是式  的一个解,但并不是唯一解,其完整的解集是从  开始不断地加 ,即

在实践中  通常比较小,因此我们可以检查每一个 ,直到找到正确的 

例 5.52

我们通过以下的例子来说明如何使用 Pollard’s ρ Method 解决离散对数问题

第一步计算序列  直到找到它们的碰撞 ,同时也要记录序列 ,表 5.11 给出了该过程的初始阶段和发现碰撞前的最后几个步骤。
密码学 | 5.5.2 通过Pollard’s ρ Method离散对数
从表中我们得到 ,相应的指数为

所以我们有

(在继续之前,我们可以再次检查这个等式,以确保之前的程序中没有出现错误)式子整理一下得

(5.44)1913470=2471726510F48611

后我们发现 ,并且 
将式 5.44 两边同时升 970 的幂次得到

因此我们有

这给出

也就是所有可能的解,就是不断地对  加上 4861 的倍数,所以   的解在以下集合中

为了解决问题,我们使用集合中的每一个元素对19 计算相应幂次,直到找到等于 24717 的。
密码学 | 5.5.2 通过Pollard’s ρ Method离散对数
因此最终  的解为 37869。
       

原文始发于微信公众号(山石网科安全技术研究院):密码学 | 5.5.2 通过Pollard’s ρ Method离散对数

版权声明:admin 发表于 2023年2月8日 上午10:51。
转载请注明:密码学 | 5.5.2 通过Pollard’s ρ Method离散对数 | CTF导航

相关文章

暂无评论

暂无评论...