RSA（三）之小公钥指数攻击

crypto python

字数统计: 211阅读时长: 1 min

 2016/10/03   Share

下边来看一个场景：

(e, n) = (3, 28891)c = 13153

c≡m^3 modn

m^3 = c + k * n

m = ³√c+k*n

我通过试k的值，当m为整数的时候，就可以求出m了。我这里使用了最差的情况，让step初始为2，步进为1.

python实现

python实现要使用gmpy2库，利用gmpy.iroot(a,b),理解为a开b次方，这个函数的返回值为一个(x,y)元组，其中x为结果值，y为一个bool型变量，如果x为整数，y=True,否则y=False。

import gmpy2
import binascii
 
(e,d,n)=(3,19035,28891)
m = int(binascii.b2a_hex("4F"),16)
c = pow(m,e)%n
step = 2
print c
(t1, t2) = gmpy2.iroot(step, 2)
while not t2:
    step = step + 1
    (t1,t2) = gmpy2.iroot(c+step*n, e)
print t1

亲自拿秒表测这个就跑了1分15秒，看来还需要多线程，可以把N分段，然后分段跑。。。

Next Post

RSA（二）之共模攻击
Previous Post

socket RSA加密通信

CATALOG

1. python实现

