-
Notifications
You must be signed in to change notification settings - Fork 0
/
RSA-CRT.py
99 lines (80 loc) · 1.75 KB
/
RSA-CRT.py
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
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
import random
import math
from egcd import egcd
def power(x, y, p):
res = 1
x = x % p
while (y > 0):
if (y & 1):
res = (res * x) % p
y = y>>1
x = (x * x) % p
return res;
def miillerTest(d, n):
a = 2 + random.randint(1, n - 4)
x = power(a, d, n)
if (x == 1 or x == n - 1):
return True
while (d != n - 1):
x = (x * x) % n
d *= 2
if (x == 1):
return False
if (x == n - 1):
return True
return False
def isPrime( n, k):
if (n <= 1 or n == 4):
return False
if (n <= 3):
return True
d = n - 1
while (d % 2 == 0):
d //= 2
for i in range(k):
if (miillerTest(d, n) == False):
return False
return True
def modinv(a, m):
g, x, y = egcd(a, m)
if g != 1:
raise Exception('No modular inverse')
return x%m
'''KEY GENERATION'''
p=0
q=0
k=4
for i in range(1000):
n=random.randint(1,pow(10, 5))
f=abs(pow(n, 2)+n-1354363)
if (isPrime(f, k)):
if (p==0):
p=f
continue
if (p!=f and q==0):
q=f
break
n=p*q
f=(p-1)*(q-1)
e=0
for i in range(2,f):
if math.gcd(i,f)==1:
e=i
break
d=modinv(e, f)
dP=(1/e)%(p-1)
dQ=(1/e)%(q-1)
qInv=(1/q)%p
'''ENCRYPTION'''
c=math.pow(m, e)%n
print(int(c))
'''DECRYPTION'''
# m = c^d mod n
#from the CRT => x=a mod pq IF AND ONLY IF x=a mod p AND x=a mod q
#m=c^d mod p and m=c^d mod q
#in the place of c we can use c%p/q
m1=math.pow(c, dP)%p
m2=math.pow(c, dQ)%q
h=qInv*(m1-m2)%p
m_original=m2+h*q
print(int(round(m_original)))