CTF Crypto RSA

已知质数p,q,公钥(指数)e,求私钥d。
利用欧拉定理解私钥d,利用扩展欧几里得求逆元。
python代码:

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
31
32
33
34
35
36
37
38
39
40
41
42
43
def CPPDiv(a,b):
    return int(a/b)

def CPPMod(a,b):
    quotient = CPPDiv(a,b)
    return a-b*quotient

def ExGCD(a,b,x,y): # Return GCD,x,y
    if b==0: return a, 1, 0
    d, y, x = ExGCD(b, CPPMod(a,b), y ,x)
    y -= CPPDiv(a,b)*x
    return d, x, y

def ExGCD_Cal(a,b):
    return ExGCD(abs(a),abs(b),0,0)[1:]

def QuickPow(a,b,MOD):
    if b==0: return 1
    result = QuickPow(a,b//2,MOD) % MOD
    result *= result
    if b&1==1: result *= a
    result %= MOD
    return result

def solveRSAd(n,phi,e):
    u, v = ExGCD_Cal(e, phi)
    if v>0:
        u += phi
        v = e-v
    return u

def Main():
    p = int(input("Prime p:"))
    q = int(input("Prime q:"))
    phi = (p-1)*(q-1)
    n = p * q
    print("Mod N: %d" % n)
    e = int(input("Public Key e:"))
    d = solveRSAd(n, phi, e)
    print("Private Key d: %s" % d)

if __name__ == '__main__':
    Main()

已知质数p,q,公钥(指数)e,和密文c,解出私钥d和明文m。

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
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
def CPPDiv(a,b):
    return int(a/b)

def CPPMod(a,b):
    quotient = CPPDiv(a,b)
    return a-b*quotient

def ExGCD(a,b,x,y): # Return GCD,x,y
    if b==0: return a, 1, 0
    d, y, x = ExGCD(b, CPPMod(a,b), y ,x)
    y -= CPPDiv(a,b)*x
    return d, x, y

def ExGCD_Cal(a,b):
    return ExGCD(abs(a),abs(b),0,0)[1:]

def QuickPow(a,b,MOD):
    if b==0: return 1
    result = QuickPow(a,b//2,MOD) % MOD
    result *= result
    if b&1==1: result *= a
    result %= MOD
    return result

def solveRSAd(n,phi,e):
    u, v = ExGCD_Cal(e, phi)
    if v>0:
        u += phi
        v = e-v
    return u

def Main():
    p = int(input("Prime p:"))
    q = int(input("Prime q:"))
    phi = (p-1)*(q-1)
    n = p * q
    print("Mod N: %d" % n)
    e = int(input("Public Key e:"))
    d = solveRSAd(n, phi, e)
    print("Private Key d: %s" % d)
    c = int(input("Cipher c:"))
    m = pow(c,d,n)
    print("Plain m: %s" % str(hex(m)))
   

if __name__ == '__main__':
    Main()

参考链接:

数论代码总结

洛谷 同余方程


https://www.freebuf.com/sectool/163781.html
还有一本数论概论:)

发表评论

电子邮件地址不会被公开。 必填项已用*标注