公式

公钥 KU

n:两素数pq的乘积(p和q必须保密)。

e:与(p-1)(q-1)互质的数。

pq可以使用工具yafu得出

私钥 KR

de^-1 mod (p-1)(q-1) 的结果
n:同上

密文 c = m^e mod n

明文 m = c^d mod n

脚本

已知 公钥(n, e) 和 密文 c  求 明文 m?

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
import gmpy2
import binascii
n = 4154220405062524632278989171077190153188438109
# p 和 q通过yafu得出
p = gmpy2.mpz(56898061770151570660943)
q = gmpy2.mpz(73011633012107403650963)
e = gmpy2.mpz(0x10001)
phi_n = (p-1)*(q-1)
d = gmpy2.invert(e, phi_n)
c = gmpy2.mpz(0x346644dfe4c826c07a0ee6e0b2e10862d41aa8)
m = pow(c, d, n)
print("10:\n%s"%m)
m_hex = hex(m)[2:]
print("16:\n%s"%(m_hex,))
print("ascii:\n%s"%(binascii.a2b_hex(m_hex).decode("utf8"),))