| 219 |
Kevin |
1 |
import random
|
|
|
2 |
|
|
|
3 |
RSA_Text_1 = [12423,11524,7243,7459,14303,6127,10964,16399,9792,13629,14407,18817,
|
|
|
4 |
18830,13556,3159,16647,5300,13951,81,8986,8007,13167,10022,17213,2264,961,17459,
|
|
|
5 |
4101,2999,14569,17183,15827,12693,9553,18194,3830,2664,13998,12501,18873,12161,
|
|
|
6 |
13071,16900,7233,8270,17086,9792,14266,13236,5300,13951,8850,12129,6091,18110,
|
|
|
7 |
3332,15061,12347,7817,7946,11675,13924,13892,18031,2620,6276,8500,201,8850,
|
|
|
8 |
11178,16477,10161,3533,13842,7537,12259,18110,44,2364,15570,3460,9886,8687,4481,
|
|
|
9 |
1231,7547,11383,17910,12867,13203,5102,4742,5053,15407,2976,9330,12192,56,2471,
|
|
|
10 |
15334,841,13995,17592,13297,2430,9741,11675,424,6686,738,13874,8168,7913,6246,
|
|
|
11 |
14301,1144,9056,15967,7328,13203,796,195,9872,16979,15404,14130,9105,2001,9792,
|
|
|
12 |
14251,1498,11296,1105,4502,16979,1105,56,4118,11302,5988,3363,15827,6928,4191,
|
|
|
13 |
4277,10617,874,13211,11821,3090,18110,44,2364,15570,3460,9886,9988,3798,1158,
|
|
|
14 |
9872,16979,15404,6127,9872,3652,14838,7437,2540,1367,2512,14407,5053,1521,297,
|
|
|
15 |
10935,17137,2186,9433,13293,7555,13618,13000,6490,5310,18676,4782,11374,446,
|
|
|
16 |
4165,11634,3846,14611,2364,6789,11634,4493,4063,4576,17955,7965,11748,14616,
|
|
|
17 |
11453,17666,925,56,4188,18031,9522,14838,7437,3880,11476,8305,5102,2999,18628,
|
|
|
18 |
14326,9175,9061,650,18110,8720,15404,2951,722,15334,841,15610,2443,11056,2186]
|
|
|
19 |
|
|
|
20 |
RSA_Text_2 = [6340,8309,14010,8936,27358,25023,16481,25809,23614,7135,24996,30590,
|
|
|
21 |
27570,26486,30388,9395,27584,14999,4517,12146,29421,26439,1606,17881,25774,
|
|
|
22 |
7647,23901,7372,25774,18436,12056,13547,7908,8635,2149,1908,22076,7372,8686,
|
|
|
23 |
1304,4082,11803,5314,107,7359,22470,7372,22827,15698,30317,4685,14696,30388,
|
|
|
24 |
8671,29956,15705,1417,26905,25809,28347,26277,7897,20240,21519,12437,1108,
|
|
|
25 |
27106,18743,24144,10685,25234,30155,23005,8267,9917,7994,9694,2149,10042,27705,
|
|
|
26 |
15930,29749,8635,23646,11738,24591,20240,27212,27486,9741,2149,29329,2149,5501,
|
|
|
27 |
14015,30155,18154,22319,27705,20321,23254,13624,3249,5443,2149,16975,16087,
|
|
|
28 |
14600,27705,19386,7325,26277,19554,23614,7553,4734,8091,23973,14015,107,3183,
|
|
|
29 |
17347,25234,4595,21498,6360,19837,8463,6000,31280,29413,2066,369,23204,8425,
|
|
|
30 |
7792,25973,4477,30989]
|
|
|
31 |
|
|
|
32 |
def RSA_Encrypt(x, b, n):
|
|
|
33 |
'''Encrypts a plaintext x using b and n'''
|
|
|
34 |
return (x**b)%n
|
|
|
35 |
|
|
|
36 |
def RSA_Decrypt(y, a, n):
|
|
|
37 |
'''Decrypts a ciphertext y using a and n'''
|
|
|
38 |
return (y**a)%n
|
|
|
39 |
|
|
|
40 |
def PollardRho(N):
|
|
|
41 |
'''Implementation of the Pollard Rho algorithm for factoring primes'''
|
|
|
42 |
if N%2==0:
|
|
|
43 |
return 2
|
|
|
44 |
x = random.randint(1, N-1)
|
|
|
45 |
y = x
|
|
|
46 |
c = random.randint(1, N-1)
|
|
|
47 |
g = 1
|
|
|
48 |
while g==1:
|
|
|
49 |
x = ((x*x)%N+c)%N
|
|
|
50 |
y = ((y*y)%N+c)%N
|
|
|
51 |
y = ((y*y)%N+c)%N
|
|
|
52 |
g = GCD(abs(x-y),N)
|
|
|
53 |
return g
|
|
|
54 |
|
|
|
55 |
def Extended_Euclidian(a, b):
|
|
|
56 |
''' Takes values a and b and returns a tuple (r,s,t) in the following format:
|
|
|
57 |
r = s * a + t * b where r is the GCD and s and t are the inverses of a and b'''
|
|
|
58 |
t_ = 0
|
|
|
59 |
t = 1
|
|
|
60 |
s_ = 1
|
|
|
61 |
s = 0
|
|
|
62 |
q = int(a/b)
|
|
|
63 |
r = a - q * b
|
|
|
64 |
# print("%d\t= %d * %d + %d" % (a, q, b, r))
|
|
|
65 |
while r > 0:
|
|
|
66 |
temp = t_ - q * t
|
|
|
67 |
t_ = t
|
|
|
68 |
t = temp
|
|
|
69 |
temp = s_ - q * s
|
|
|
70 |
s_ = s
|
|
|
71 |
s = temp
|
|
|
72 |
a = b
|
|
|
73 |
b = r
|
|
|
74 |
q = int(a/b)
|
|
|
75 |
r = a - q * b
|
|
|
76 |
# print("%d\t= %d * %d + %d" % (a, q, b, r))
|
|
|
77 |
r = b
|
|
|
78 |
return (r, s, t)
|
|
|
79 |
|
|
|
80 |
def GCD(q,N):
|
|
|
81 |
'''Returns the multiplicative inverse of a and b'''
|
|
|
82 |
ret = Extended_Euclidian(q,N)
|
|
|
83 |
return ret[0]
|
|
|
84 |
|
|
|
85 |
def Inverse(a, b):
|
|
|
86 |
'''Returns the multiplicative inverse of a mod b'''
|
|
|
87 |
ret = Extended_Euclidian(a,b)
|
|
|
88 |
if (ret[1] < 0):
|
|
|
89 |
inv = ret[1] + b
|
|
|
90 |
else:
|
|
|
91 |
inv = ret[1]
|
|
|
92 |
return inv
|
|
|
93 |
|
|
|
94 |
def Decrypt(n):
|
|
|
95 |
'''Decodes an encoding where n = a * 26^2 + b * 26 + c'''
|
|
|
96 |
a = int(n / 676)
|
|
|
97 |
n = n - (a * 676)
|
|
|
98 |
b = int(n / 26)
|
|
|
99 |
n = n - (b * 26)
|
|
|
100 |
c = n
|
|
|
101 |
return (a, b, c)
|
|
|
102 |
|
|
|
103 |
if __name__ == '__main__':
|
|
|
104 |
n = 31313
|
|
|
105 |
b = 4913
|
|
|
106 |
p = PollardRho(n) # Factor n to find a prime
|
|
|
107 |
q = int(n / p) # Find the other prime
|
|
|
108 |
phi = (q - 1) * (p - 1) # Calculate Phi(n)
|
|
|
109 |
a = Inverse(b, phi) # Calculate the decrypting exponent a
|
|
|
110 |
print("N = %d, p = %d, q = %d, phi = %d, a = %d, b = %d" % (n, p, q, phi, a, b))
|
|
|
111 |
|
|
|
112 |
# Decrypt the message
|
|
|
113 |
for entry in RSA_Text_2:
|
|
|
114 |
enc = Decrypt(RSA_Decrypt(entry, a, n))
|
|
|
115 |
print("%c%c%c" % (chr(enc[0]+65), chr(enc[1]+65), chr(enc[2]+65)), end='')
|
|
|
116 |
print()
|