44 lines
1.2 KiB
Plaintext
44 lines
1.2 KiB
Plaintext
import math
|
|
from decimal import *
|
|
def isPrime(n):#判断是否为素数
|
|
if n <= 1:
|
|
return False
|
|
for i in range(2, int(math.sqrt(n) + 1)):
|
|
if n % i == 0:
|
|
return False
|
|
return True
|
|
def crack(n):#质因素分解
|
|
for p in range(2, n):
|
|
for q in range(p+1, n):
|
|
if p*q == n and isPrime(p) and isPrime(q):
|
|
return (p, q)
|
|
def extGcd(a, b):#扩展欧几里得可以求出最大公约数
|
|
if a < b:
|
|
return extGcd(b, a)
|
|
if b == 0:
|
|
return a, 1, 0
|
|
gcd, x, y = extGcd(b, a%b)
|
|
return gcd, y, x-a/b*y
|
|
def getD(n, e): #求解私钥d
|
|
p, q = crack(n)
|
|
fai = (p-1)*(q-1)
|
|
gcd, x, y = extGcd(fai, e)
|
|
while y < 0:
|
|
y += fai
|
|
return y
|
|
def decrypt(n, e, ciphertext):
|
|
plaintext = []
|
|
d = getD(n, e)
|
|
for num in ciphertext:
|
|
num = num**d % n
|
|
plaintext.append(chr(num))
|
|
return "".join(plaintext)
|
|
if __name__ == "__main__":
|
|
print(getD(2449,7))
|
|
n = 2449
|
|
e = 7
|
|
ciphertext = [971,922,605,1446,1704,889,2090,605,1899,
|
|
1915,2088,1988,1235,1032,65,922,958,1988,
|
|
2144,591,1988,2270,2088,1032,65,958,2233]
|
|
plaintext = decrypt(n, e, ciphertext)
|
|
print (plaintext) |