RSA解题方法

发表于 更新于 分类于
RSA的各种题型和解题方法

基本公式

n = p*q

φ(n) = (p-1)*(q-1)

dp = d mod (p-1)

dq = d mod (q-1)

m = c^d mod n

c = m^e mod n

e*d mod φ(n) = 1

e*d = 1 mod φ(n)

已知e,n的情况

先在 http://www.factordb.com/ 将n分解为两个质数,分别为p和q,知道了p和q后,算出φ(n)

用gmpy2库的invert(e,phin)函数算出d,再用rsa库的PrivateKey(n,e,d,p,q)函数算出私钥即可

1
2
3
4
5
6
7
8
9
10
import rsa
import gmpy2
e = ...
n = ...
p = ...
q = ...
phin = (p-1)*(q-1)
d = gmpy2.invert(e, phin)
key = rsa.PrivateKey(n, e, d, p, q)
print(key)

也可以用维纳攻击

1
2
3
4
5
6
7
8
9
import  RSAwienerHacker
import hashlib
n = ...
e = ...
d =  RSAwienerHacker.hack_RSA(e,n)
if d:
    print(d)
flag = hashlib.md5(hex(d)).hexdigest()
print flag

RSAwienerHacker的地址: https://github.com/pablocelayes/rsa-wiener-attack

例题:BUUCTF RSA

—–BEGIN PUBLIC KEY—–
MDwwDQYJKoZIhvcNAQEBBQADKwAwKAIhAMAzLFxkrkcYL2wch21CM2kQVFpY9+7+
/AvKr1rzQczdAgMBAAE=
—–END PUBLIC KEY—–

加密的文件:flag.enc

先把公钥放在RSA公钥分解网站里解析 http://tool.chacuo.net/cryptrsakeyparse ,解析后得到e,n,将n转换为10进制数,套用上面的方法即可得到私钥,再用rsa库的decrypt函数即可解密文件,上代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
import rsa
import gmpy2
e = 65537
n = 86934482296048119190666062003494800588905656017203025617216654058378322103517
p = 285960468890451637935629440372639283459
q = 304008741604601924494328155975272418463
phin = (p-1)*(q-1)
d = gmpy2.invert(e,phin)
key = rsa.PrivateKey(n, e, d, p, q)
with open("./flag.enc", "rb+") as file:
    text = file.read()
message = rsa.decrypt(text, key)
print(message)

已知p,q,dp,dq,c的情况

直接套代码吧……

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
import gmpy2 as gp
p = ...
q = ...
dp = ...
dq = ...
c = ...
n = p*q
phin = (p-1)*(q-1)
dd = gp.gcd(p-1, q-1)
d = (dp-dq)//dd * gp.invert((q-1)//dd, (p-1)//dd) * (q-1) + dq
print("d=", d)
m = pow(c, d, n)
print("m=", m)
print(hex(m))
print(bytes.fromhex(hex(m)[2:]))
#如果解出来的m或者m转成16进制后提交还是错误,可以把m转换成ascii在提交

已知e,n,dp,c的情况

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
import gmpy2 as gp

e = ...
n = ...
dp = ...
c = ...
for x in range(1, e):
    if(e*dp % x == 1):
        p = (e*dp-1)//x+1
        if(n % p != 0):
            continue
        q = n//p
        phin = (p-1)*(q-1)
        d = gp.invert(e, phin)
        m = gp.powmod(c, d, n)
        if(len(hex(m)[2:]) % 2 == 1):
            continue
        print(m)
        print(hex(m)[2:])
        # print(bytes.fromhex(hex(m)[2:]))

已知c1,c2,e1,e2,n的情况(共模攻击)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
from libnum import n2s, s2n
from gmpy2 import invert

def egcd(a, b):
    if a == 0:
        return (b, 0, 1)
    else:
        g, y, x = egcd(b % a, a)
        return (g, x - (b // a) * y, y)
    
def main():
    n = ...
    c1 = ...
    c2 = ...
    e1 = ...
    e2 = ...
    s = egcd(e1, e2)
    s1 = s[1]
    s2 = s[2]
    if s1 < 0:
        s1 = - s1
        c1 = invert(c1, n)
    elif s2 < 0:
        s2 = - s2
        c2 = invert(c2, n)
    m = pow(c1, s1, n)*pow(c2, s2, n) % n
    print(hex(m)[2:])

if __name__ == '__main__':
    main()

已知p,q,e,c的情况

带入公式

n=p*q

φ(n)=(p-1)*(q-1)

e*d mod φ(n)=1

m=c^d mod n

1
2
3
4
5
6
7
8
9
10
import gmpy2
p = ...
q = ...
e = ...
c = ...
n = p*q
phin = (p-1)*(q-1)
d=gmpy2.invert(e,phin)
m = pow(c, d, n)
print(m)