部分CTF-RSA解题思路及脚本

RSA攻击方法总结

暴力破解

用于已知e,c,m,不是很大的n(小于等于1024)

常用分解方法:

linux下命令行: factor n(本地计算,n较小时推荐)
factordb n(需要安装对应的py模块，pip install factordb-pycli)
在线分解: http://factordb.com/

#!/usr/bin/python  
#coding:utf-8  
 
import libnum  
from Crypto.Util.number import long_to_bytes 
 
q = int(input("please input q:\n"))
p = int(input("please input p:\n"))
c = eval(input("please input c:\n"))
e = int(input("please input e:\n"))
 
d = libnum.invmod(e, (p - 1) *(q - 1))
n = q * p
phi = (p-1)*(q-1)  
d = libnum.invmod(e,phi) 
m = pow(c, d, n)
 
print("16进制数为:     %d"%m)
print(end="字符串为:    ")
print (long_to_bytes(m))

共模攻击

攻击条件:

使用了相同的n加密同一组明文
e1和e2互素

#!/usr/bin/python
import gmpy2
e1 = int(input("input e1"))
e2 = int(input("input e2"))
 
g,x,y=gmpy2.gcdext(e1,e2)

低加密指数小明文加密

如果m很小,e也比较小,导致c小于n,于是可对c直接开e次方得到m
例如:

#/usr/bin/python
n = 123456782
e = 3
m = 233
print(pow(m,e))

可以观察到pow(m,e)依然小于n,也就是说取模运算根本没有发生

于是直接对c开e次方即可

低解密指数攻击

详见Michael J.Wiener于1989发表的Cryptanalysis of Short RSA Secret Exponents

import ContinuedFractions, Arithmetic, RSAvulnerableKeyGenerator
 
def hack_RSA(e,n):
    '''
    Finds d knowing (e,n)
    applying the Wiener continued fraction attack
    '''
    frac = ContinuedFractions.rational_to_contfrac(e, n)
    convergents = ContinuedFractions.convergents_from_contfrac(frac)
 
    for (k,d) in convergents:
 
        #check if d is actually the key
        if k!=0 and (e*d-1)%k == 0:
            phi = (e*d-1)//k
            s = n - phi + 1
            # check if the equation x^2 - s*x + n = 0
            # has integer roots
            discr = s*s - 4*n
            if(discr>=0):
                t = Arithmetic.is_perfect_square(discr)
                if t!=-1 and (s+t)%2==0:
                    print("Hacked!")
                    return d
 
# TEST functions
 
def test_hack_RSA():
    print("Testing Wiener Attack")
    times = 5
 
    while(times>0):
        e,n,d = RSAvulnerableKeyGenerator.generateKeys(1024)
        print("(e,n) is (", e, ", ", n, ")")
        print("d = ", d)
 
        hacked_d = hack_RSA(e, n)
 
        if d == hacked_d:
            print("Hack WORKED!")
        else:
            print("Hack FAILED")
 
        print("d = ", d, ", hacked_d = ", hacked_d)
        print("-------------------------")
        times -= 1
 
if __name__ == "__main__":
    #test_is_perfect_square()
    #print("-------------------------")
    test_hack_RSA()

广播攻击

对于相同的明文,相同的指数e,不同的n加密得到多组数据可以考虑广播攻击

原理:中国剩余定理(孙子定理)

def GCRT(mi, ai):
   # mi,ai分别表示模数和取模后的值,都为列表结构
assert (isinstance(mi, list) and isinstance(ai, list))
   curm, cura = mi[0], ai[0]
for (m, a) in zip(mi[1:], ai[1:]):
       d = gmpy2.gcd(curm, m)
       c = a - cura
assert (c % d == 0) #不成立则不存在解
       K = c / d * gmpy2.invert(curm / d, m / d)
       cura += curm * K
       curm = curm * m / d
       cura %= curm
return (cura % curm, curm) #(解,最小公倍数)