RSA

发表于 更新于 分类于 ，

开始RSA的学习

RSA加密过程

1
2
3
4
5
6
p = ;q = ;（两个质数）
n = p * q
φ(n) = (p-1)*(q-1)
e = 公钥指数(与φ(n)互质)
m = 明文
c ≡ m^e (mod n)

(d * e) mod φ(n) = 1

公钥: (e, n)

私钥: (d, n)

解密过程

1
m ≡ c^d (mod n)

例题1

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
from Crypto.Util.number import getPrime, bytes_to_long
from random import randint
from sympy import totient
from secret import flag

def power_tower_mod(a, k, m):  # a↑↑k mod m
    if k == 1:
        return a % m
    exp = power_tower_mod(a, k - 1, totient(m))
    return pow(a, int(exp), int(m))


p = getPrime(512)
q = getPrime(512)
r = 123456
n = p * q
e = 65537
n_phi= p+q-1
x=power_tower_mod(n_phi + 1, r, pow(n_phi, 3))
m = bytes_to_long(flag)
c = pow(m, e, n)

print(f"n = {n}")
print(f"e = {e}")
print(f"c = {c}")
print(f"x = {x}")

'''
n = 128523866891628647198256249821889078729612915602126813095353326058434117743331117354307769466834709121615383318360553158180793808091715290853250784591576293353438657705902690576369228616974691526529115840225288717188674903706286837772359866451871219784305209267680502055721789166823585304852101129034033822731
e = 65537
c = 125986017030189249606833383146319528808010980928552142070952791820726011301355101112751401734059277025967527782109331573869703458333443026446504541008332002497683482554529670817491746530944661661838872530737844860894779846008432862757182462997411607513582892540745324152395112372620247143278397038318619295886
x = 522964948416919148730075013940176144502085141572251634384238148239059418865743755566045480035498265634350869368780682933647857349700575757065055513839460630399915983325017019073643523849095374946914449481491243177810902947558024707988938268598599450358141276922628627391081922608389234345668009502520912713141
'''
1
2
3
4
5
x = 1 + n_phi + n_phi^2
n_phi = (-1 + sqrt(4*x - 3)) // 2
n_phi = p + q - 1
φ(n) = (p-1)*(q-1) = n + n_phi
d = pow(e, -1, φ(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
from math import isqrt
from Crypto.Util.number import long_to_bytes

n = 128523866891628647198256249821889078729612915602126813095353326058434117743331117354307769466834709121615383318360553158180793808091715290853250784591576293353438657705902690576369228616974691526529115840225288717188674903706286837772359866451871219784305209267680502055721789166823585304852101129034033822731
e = 65537
c = 125986017030189249606833383146319528808010980928552142070952791820726011301355101112751401734059277025967527782109331573869703458333443026446504541008332002497683482554529670817491746530944661661838872530737844860894779846008432862757182462997411607513582892540745324152395112372620247143278397038318619295886
x = 522964948416919148730075013940176144502085141572251634384238148239059418865743755566045480035498265634350869368780682933647857349700575757065055513839460630399915983325017019073643523849095374946914449481491243177810902947558024707988938268598599450358141276922628627391081922608389234345668009502520912713141

# Calculate n_phi from x
temp = 4 * x - 3
root = isqrt(temp)
n_phi = (root - 1) // 2

# Calculate φ(n)
phi_n = n - n_phi

# Calculate private exponent d
d = pow(e, -1, phi_n)

# Decrypt c
m = pow(c, d, n)

# Convert to bytes
flag = long_to_bytes(m)
print(flag)