| 0,0 → 1,116 |
|---|
| import random |
| |
| RSA_Text_1 = [12423,11524,7243,7459,14303,6127,10964,16399,9792,13629,14407,18817, |
| 18830,13556,3159,16647,5300,13951,81,8986,8007,13167,10022,17213,2264,961,17459, |
| 4101,2999,14569,17183,15827,12693,9553,18194,3830,2664,13998,12501,18873,12161, |
| 13071,16900,7233,8270,17086,9792,14266,13236,5300,13951,8850,12129,6091,18110, |
| 3332,15061,12347,7817,7946,11675,13924,13892,18031,2620,6276,8500,201,8850, |
| 11178,16477,10161,3533,13842,7537,12259,18110,44,2364,15570,3460,9886,8687,4481, |
| 1231,7547,11383,17910,12867,13203,5102,4742,5053,15407,2976,9330,12192,56,2471, |
| 15334,841,13995,17592,13297,2430,9741,11675,424,6686,738,13874,8168,7913,6246, |
| 14301,1144,9056,15967,7328,13203,796,195,9872,16979,15404,14130,9105,2001,9792, |
| 14251,1498,11296,1105,4502,16979,1105,56,4118,11302,5988,3363,15827,6928,4191, |
| 4277,10617,874,13211,11821,3090,18110,44,2364,15570,3460,9886,9988,3798,1158, |
| 9872,16979,15404,6127,9872,3652,14838,7437,2540,1367,2512,14407,5053,1521,297, |
| 10935,17137,2186,9433,13293,7555,13618,13000,6490,5310,18676,4782,11374,446, |
| 4165,11634,3846,14611,2364,6789,11634,4493,4063,4576,17955,7965,11748,14616, |
| 11453,17666,925,56,4188,18031,9522,14838,7437,3880,11476,8305,5102,2999,18628, |
| 14326,9175,9061,650,18110,8720,15404,2951,722,15334,841,15610,2443,11056,2186] |
| |
| RSA_Text_2 = [6340,8309,14010,8936,27358,25023,16481,25809,23614,7135,24996,30590, |
| 27570,26486,30388,9395,27584,14999,4517,12146,29421,26439,1606,17881,25774, |
| 7647,23901,7372,25774,18436,12056,13547,7908,8635,2149,1908,22076,7372,8686, |
| 1304,4082,11803,5314,107,7359,22470,7372,22827,15698,30317,4685,14696,30388, |
| 8671,29956,15705,1417,26905,25809,28347,26277,7897,20240,21519,12437,1108, |
| 27106,18743,24144,10685,25234,30155,23005,8267,9917,7994,9694,2149,10042,27705, |
| 15930,29749,8635,23646,11738,24591,20240,27212,27486,9741,2149,29329,2149,5501, |
| 14015,30155,18154,22319,27705,20321,23254,13624,3249,5443,2149,16975,16087, |
| 14600,27705,19386,7325,26277,19554,23614,7553,4734,8091,23973,14015,107,3183, |
| 17347,25234,4595,21498,6360,19837,8463,6000,31280,29413,2066,369,23204,8425, |
| 7792,25973,4477,30989] |
| |
| def RSA_Encrypt(x, b, n): |
| '''Encrypts a plaintext x using b and n''' |
| return (x**b)%n |
| |
| def RSA_Decrypt(y, a, n): |
| '''Decrypts a ciphertext y using a and n''' |
| return (y**a)%n |
| |
| def PollardRho(N): |
| '''Implementation of the Pollard Rho algorithm for factoring primes''' |
| if N%2==0: |
| return 2 |
| x = random.randint(1, N-1) |
| y = x |
| c = random.randint(1, N-1) |
| g = 1 |
| while g==1: |
| x = ((x*x)%N+c)%N |
| y = ((y*y)%N+c)%N |
| y = ((y*y)%N+c)%N |
| g = GCD(abs(x-y),N) |
| return g |
| |
| def Extended_Euclidian(a, b): |
| ''' Takes values a and b and returns a tuple (r,s,t) in the following format: |
| r = s * a + t * b where r is the GCD and s and t are the inverses of a and b''' |
| t_ = 0 |
| t = 1 |
| s_ = 1 |
| s = 0 |
| q = int(a/b) |
| r = a - q * b |
| # print("%d\t= %d * %d + %d" % (a, q, b, r)) |
| while r > 0: |
| temp = t_ - q * t |
| t_ = t |
| t = temp |
| temp = s_ - q * s |
| s_ = s |
| s = temp |
| a = b |
| b = r |
| q = int(a/b) |
| r = a - q * b |
| # print("%d\t= %d * %d + %d" % (a, q, b, r)) |
| r = b |
| return (r, s, t) |
| |
| def GCD(q,N): |
| '''Returns the multiplicative inverse of a and b''' |
| ret = Extended_Euclidian(q,N) |
| return ret[0] |
| |
| def Inverse(a, b): |
| '''Returns the multiplicative inverse of a mod b''' |
| ret = Extended_Euclidian(a,b) |
| if (ret[1] < 0): |
| inv = ret[1] + b |
| else: |
| inv = ret[1] |
| return inv |
| |
| def Decrypt(n): |
| '''Decodes an encoding where n = a * 26^2 + b * 26 + c''' |
| a = int(n / 676) |
| n = n - (a * 676) |
| b = int(n / 26) |
| n = n - (b * 26) |
| c = n |
| return (a, b, c) |
| |
| if __name__ == '__main__': |
| n = 31313 |
| b = 4913 |
| p = PollardRho(n) # Factor n to find a prime |
| q = int(n / p) # Find the other prime |
| phi = (q - 1) * (p - 1) # Calculate Phi(n) |
| a = Inverse(b, phi) # Calculate the decrypting exponent a |
| print("N = %d, p = %d, q = %d, phi = %d, a = %d, b = %d" % (n, p, q, phi, a, b)) |
| |
| # Decrypt the message |
| for entry in RSA_Text_2: |
| enc = Decrypt(RSA_Decrypt(entry, a, n)) |
| print("%c%c%c" % (chr(enc[0]+65), chr(enc[1]+65), chr(enc[2]+65)), end='') |
| print() |