| /Classwork/MATH4176 - Cryptography 2/ElGamal.py |
|---|
| 0,0 → 1,82 |
| # Encrypted Data |
| data_set = ((3781,14409),(31552,3930),(27214,15442),(5809,30274), |
| (5400,31486),(19936,721),(27765,29284),(29820,7710), |
| (31590,26470),(3781,14409),(15898,30844),(19048,12914), |
| (16160,3129),(301,17252),(24689,7776),(28856,15720), |
| (30555,24611),(20501,2922),(13659,5015),(5740,31233), |
| (1616,14170),(4294,2307),(2320,29174),(3036,20132), |
| (14130,22010),(25910,19663),(19557,10145),(18899,27609), |
| (26004,25056),(5400,31486),(9526,3019),(12962,15189), |
| (29538,5408),(3149,7400),(9396,3058),(27149,20535), |
| (1777,8737),(26117,14251),(7129,18195),(25302,10248), |
| (23258,3468),(26052,20545),(21958,5713),(346,31194), |
| (8836,25898),(8794,17358),(1777,8737),(25038,12483), |
| (10422,5552),(1777,8737),(3780,16360),(11685,133), |
| (25115,10840),(14130,22010),(16081,16414),(28580,20845), |
| (23418,22058),(24139,9580),(173,17075),(2016,18131), |
| (19886,22344),(21600,25505),(27119,19921),(23312,16906), |
| (21563,7891),(28250,21321),(28327,19237),(15313,28649), |
| (24271,8480),(26592,25457),(9660,7939),(10267,20623), |
| (30499,14423),(5839,24179),(12846,6598),(9284,27858), |
| (24875,17641),(1777,8737),(18825,19671),(31306,11929), |
| (3576,4630),(26664,27572),(27011,29164),(22763,8992), |
| (3149,7400),(8951,29435),(2059,3977),(16258,30341), |
| (21541,19004),(5865,29526),(10536,6941),(1777,8737), |
| (17561,11884),(2209,6107),(10422,5552),(19371,21005), |
| (26521,5803),(14884,14280),(4328,8635),(28250,21321), |
| (28327,19237),(15313,28649)) |
| 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 = 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 = a//b |
| r = a - q * b |
| # print("%d\t= %d * %d + %d" % (a, q, b, r)) |
| r = b |
| return (r, s, t) |
| 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__': |
| p = 31847 |
| a = 7899 |
| # For each encrypted data packet, decrypt it using the following function: |
| # d(y_1,y_2) = y_2(y_1^a)^-1 mod p |
| for i in data_set: |
| d = i[1] * Inverse(i[0]**a,p) % p |
| s = Decrypt(d) |
| print("%c%c%c" % (chr(s[0]+65), chr(s[1]+65), chr(s[2]+65)), end='') |
| print() |
| /Classwork/MATH4176 - Cryptography 2/EllipticCurve.py |
|---|
| 0,0 → 1,112 |
| 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''' |
| if (a < 0): |
| a = a + b |
| ret = Extended_Euclidian(a,b) |
| if (ret[1] < 0): |
| inv = ret[1] + b |
| else: |
| inv = ret[1] |
| return inv |
| def Elliptic_Curve_Add(p, a, b, point_1, point_2): |
| '''Adds two points on an Elliptical Curve and returns the result''' |
| # Adding a point at infinity results in the same point |
| if point_1[0] == 'x' and point_1[1] == 'x': |
| return point_2 |
| if point_2[0] == 'x' and point_2[1] == 'x': |
| return point_1 |
| # Test to make sure both points are on the curve |
| z = (point_1[0]**3 + a*point_1[0] + b) % p |
| if z**((p-1)//2)%p != 1: |
| print("Point", point_1, "is not on the elliptic curve!") |
| return |
| z = (point_2[0]**3 + a*point_2[0] + b) % p |
| if z**((p-1)//2)%p != 1: |
| print("Point", point_2, "is not on the elliptic curve!") |
| return |
| # If x_1 == x_2 and y_1 != y_2, return point at infinity |
| if point_1[0] == point_2[0] and point_1[1] != point_2[1]: |
| return ('x','x') |
| # If point_1 == point_2, slope = (3 x_1^2 + a)(2 y_1)^-1 |
| if point_1[0] == point_2[0] and point_1[1] == point_2[1]: |
| inv = Inverse(2*point_1[1], p) |
| slope = ((3 * point_1[0]**2 + a) * inv) % p |
| else: # Otherwise point_1 != point_2, slope = (y_2 - y_1)(x_2 - x_1)^-1 |
| inv = Inverse(point_2[0] - point_1[0], p) |
| slope = ((point_2[1] - point_1[1]) * inv) % p |
| # Calculate the third point given the slope |
| x_3 = (slope**2 - point_1[0] - point_2[0]) % p |
| y_3 = (slope * (point_1[0] - x_3) - point_1[1]) % p |
| return (x_3,y_3) |
| def Elliptic_Curve_Multiple(p, a, b, point, multiple): |
| '''Returns a multiple of a point on an Elliptical Curve''' |
| ret = point |
| for i in range(multiple-1): |
| ret = Elliptic_Curve_Add(p, a, b, ret, point) |
| print(i+2,":",ret) |
| return ret |
| if __name__ == '__main__': |
| # print("For the following tests, the curve y^2 = x^3 + x + 6 is used") |
| # print("\nResult when point is not on the curve (quadratic residue failed):") |
| # print(Elliptic_Curve_Add(11, 1, 6, (1,2), (2,7))) |
| # print("\nResult when one or both points being the point at infinity:") |
| # print(Elliptic_Curve_Add(11, 1, 6, ('x','x'), (2,7))) |
| # print(Elliptic_Curve_Add(11, 1, 6, (2,7), ('x','x'))) |
| # print(Elliptic_Curve_Add(11, 1, 6, ('x','x'), ('x','x'))) |
| # print("\nResult when adding two distinct points:") |
| # print(Elliptic_Curve_Add(11, 1, 6, (2,7), (7,9))) |
| # print("\nResult when adding a point to itself:") |
| # print(Elliptic_Curve_Add(11, 1, 6, (2,7), (2,7))) |
| # print("\nResult when computing multiples of a point:") |
| # Elliptic_Curve_Multiple(11, 1, 6, (2,7), 3) |
| # print("\nFor the following tests, the curve y^2 = x^3 + 5x + 4 is used") |
| # print("\nAttempting to add point (220,407) to itself:") |
| # print(Elliptic_Curve_Add(997, 5, 4, (220,407), (220,407))) |
| # print("\nResult of 267(220,407):") |
| # Elliptic_Curve_Multiple(997, 5, 4, (220,407), 267) |
| Elliptic_Curve_Multiple(71,1,28,(1,32),10) |
| /Classwork/MATH4176 - Cryptography 2/Factoring.py |
|---|
| 0,0 → 1,88 |
| def PollardPM1(N,B): |
| '''Implementation of the Pollard p-1 algorithm for factoring primes''' |
| a = 2; |
| for i in range(2,B): |
| a = a**i % N |
| d = GCD(a-1,N) |
| if 1 < d < N: |
| return d |
| else: |
| return -1; |
| def PollardRho(N,x_1): |
| '''Implementation of the Pollard Rho algorithm for factoring primes''' |
| x = x_1 |
| y = PollardRhoHelper(x) % N |
| g = GCD(abs(x-y),N) |
| iterations = 0; |
| while g == 1: |
| iterations += 1 |
| x = PollardRhoHelper(x) % N |
| y = PollardRhoHelper(y) % N |
| y = PollardRhoHelper(y) % N |
| g = GCD(abs(x-y),N) |
| print("Iterations: %d\n" % (iterations)) |
| if g == N: |
| return -1 |
| else: |
| return g |
| def PollardRhoHelper(x): |
| return x**2 + 1 |
| 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 |
| if __name__ == '__main__': |
| prime1 = 112426043 |
| prime2 = 262063 |
| prime3 = 9420457 |
| for i in range(100): |
| p = PollardPM1(prime1,i) |
| if p != -1: |
| print("Prime found with B = %d with value %d\n" % (i,p)) |
| break |
| p = PollardRho(prime2,1) |
| print("A prime factor of %d is %d\n" % (prime2,p)) |
| p = PollardRho(prime3,1) |
| print("A prime factor of %d is %d\n" % (prime3,p)) |
| /Classwork/MATH4176 - Cryptography 2/GCD.py |
|---|
| 0,0 → 1,31 |
| 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) |
| if __name__ == '__main__': |
| a = 99 |
| b = 101 |
| res = Extended_Euclidian(a, b) |
| print("%d = %d * %d + %d * %d" % (res[0], res[1], a, res[2], b)) |
| /Classwork/MATH4176 - Cryptography 2/Notes.pdf |
|---|
| Cannot display: file marked as a binary type. |
| svn:mime-type = application/octet-stream |
| /Classwork/MATH4176 - Cryptography 2/Notes.pdf |
|---|
| Property changes: |
| Added: svn:mime-type |
| +application/octet-stream |
| \ No newline at end of property |
| /Classwork/MATH4176 - Cryptography 2/PollardRhoLog.py |
|---|
| 0,0 → 1,71 |
| import math |
| 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 = 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 = a//b |
| r = a - q * b |
| # print("%d\t= %d * %d + %d" % (a, q, b, r)) |
| r = b |
| return (r, s, t) |
| 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 GCD(q,N): |
| '''Returns the GCD of a and b''' |
| ret = Extended_Euclidian(q,N) |
| return ret[0] |
| def PollardRhoLog(G,p,n,alpha,beta): |
| '''Implements the Pollard Rho discrete log factoring algorithm''' |
| def PollardRhoFunction(x,a,b): |
| '''Helper functions for defining sets''' |
| if x % 3 == 1: |
| return (beta*x%p,a,(b+1)%n) |
| elif x % 3 == 0: |
| return (x**2%p,2*a%n,2*b%n) |
| else: |
| return (alpha*x%p,(a+1)%n,b) |
| i = 1 |
| (x,a,b) = PollardRhoFunction(G[0],G[1],G[2]) |
| (x_,a_,b_) = PollardRhoFunction(x,a,b) |
| print("i =", i, ":", (x,a,b), "\t2i :", (x_,a_,b_)) |
| while x != x_: |
| i += 1 |
| (x,a,b) = PollardRhoFunction(x,a,b) |
| (x_,a_,b_) = PollardRhoFunction(x_,a_,b_) |
| (x_,a_,b_) = PollardRhoFunction(x_,a_,b_) |
| print("i =", i, ":", (x,a,b), "\t2i :", (x_,a_,b_)) |
| if GCD(b_-b,n) != 1: |
| return -1 |
| else: |
| return (a-a_)*Inverse((b_-b), n)%n |
| if __name__ == '__main__': |
| print(PollardRhoLog((1,0,0),526483,87747,13,59480)) |
| /Classwork/MATH4176 - Cryptography 2/RSA.py |
|---|
| 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() |
| /Classwork/MATH4176 - Cryptography 2/Shamir.py |
|---|
| 0,0 → 1,82 |
| from operator import mul |
| from random import randrange, sample |
| from functools import reduce |
| 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 = 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 = a//b |
| r = a - q * b |
| # print("%d\t= %d * %d + %d" % (a, q, b, r)) |
| r = b |
| return (r, s, t) |
| 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 prod(nums): |
| """Product of nums""" |
| return reduce(mul, nums, 1) |
| def horner_mod(coeffs, mod): |
| """Polynomial with coeffs of degree len(coeffs) via Horner's rule; uses |
| modular arithmetic. For example, if coeffs = [1,2,3] and mod = 5, this |
| returns the function x --> (x, y) where y = 1 + 2x + 3x^2 mod 5.""" |
| return lambda x: (x, |
| reduce(lambda a, b: a * x + b % mod, reversed(coeffs), 0) % mod) |
| def shamir_threshold(S, k, n, p): |
| """Shamir's simple (k, n) threshold scheme. Returns xy_pairs genrated by |
| secret polynomial mod p with constant term = S. Information is given to n |
| different people any k of which constitute enough to reconstruct the secret |
| data.""" |
| coeffs = [S] |
| # Independent but not necessarily unique; choose k - 1 coefficients from [1, p) |
| coeffs.extend(randrange(1, p) for _ in range(k - 1)) |
| # x values are unique |
| return map(horner_mod(coeffs, p), sample(range(1, p), n)) |
| def interp_const(xy_pairs, k, p): |
| """Use Lagrange Interpolation to find the constant term of the degree k |
| polynomial (mod p) that gave the xy-pairs; we get to use a shortcut since |
| we are only after the constant term for which x = 0.""" |
| assert len(xy_pairs) >= k, "Not enough points for interpolation" |
| x = lambda i: xy_pairs[i][0] |
| y = lambda i: xy_pairs[i][1] |
| return sum(y(i) * prod(x(j) * Inverse(x(j) - x(i), p) % p for j in range(k) if j != i) for i in range(k)) % p |
| if __name__ == "__main__": |
| k, n, p = 5, 9, 81342267667 |
| pairs = [(11,29952055635),(22,26786192733),(33,77756881208),(44,80139093118),(55,24225052606), |
| (66,74666503567),(77,1078845979),(88,72806030240),(99,1471177497)] |
| for i in range(9): |
| lst = [] |
| for j in range(9): |
| if i != j: |
| lst.append(pairs[j]) |
| print("Omitting Share", (i), ":", interp_const(lst,k,p)) |
| /Classwork/MATH4176 - Cryptography 2/Shanks-Tonelli.py |
|---|
| 0,0 → 1,53 |
| def modular_sqrt(a, p): |
| '''Finds the square root x^2 = a (mod p) and returns x''' |
| ''' See http://www.math.vt.edu/people/brown/class_homepages/shanks_tonelli.pdf''' |
| if Jacobi_Symbol(a, p) != 1: |
| return 0 |
| elif a == 0: |
| return 0 |
| elif p == 2: |
| return p |
| elif p % 4 == 3: |
| return (a**((p+1)/4)) % p |
| s = p - 1 |
| e = 0 |
| while s % 2 == 0: |
| s /= 2 |
| e += 1 |
| n = 2 |
| while Jacobi_Symbol(n, p) != -1: |
| n += 1 |
| x = (a**((s+1)/2)) % p |
| b = (a**s) % p |
| g = (n**s) % p |
| r = e |
| while True: |
| t = b |
| m = 0 |
| for m in range(r): |
| if t == 1: |
| break |
| t = (t**2) % p |
| if m == 0: |
| return x |
| gs = (g**(2 ** (r - m - 1))) % p |
| g = (gs * gs) % p |
| x = (x * gs) % p |
| b = (b * g) % p |
| r = m |
| def Jacobi_Symbol(a, p): |
| ls = (a**((p - 1) // 2)) % p |
| return -1 if ls == p - 1 else ls |
| if __name__ == '__main__': |
| print(modular_sqrt(2,113)) |
| print(modular_sqrt(19,4481)) |
| print(modular_sqrt(191,1009)) |
| /Classwork/MATH4176 - Cryptography 2/Shanks.py |
|---|
| 0,0 → 1,93 |
| import math |
| 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 = 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 = a//b |
| r = a - q * b |
| # print("%d\t= %d * %d + %d" % (a, q, b, r)) |
| r = b |
| return (r, s, t) |
| 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 Shanks(n,a,b): |
| ''' Implements the Shanks algorithm for solving the Discrete Logarithm Problem''' |
| m = math.ceil(math.sqrt(n)) |
| d = a**m % n |
| # Generate and sort list L1 |
| L1 = dict() |
| for i in range(m): |
| L1[i] = d**i % n |
| print('L1: (unsorted)') |
| for i in range(m): |
| print("%d\t:\t%d" % (i, L1[i])) |
| L1 = sorted(L1.items(), key=lambda x: x[1]) |
| # Generate and sort list L2 |
| L2 = dict() |
| for i in range(m): |
| L2[i] = b * Inverse(a**i, n) % n |
| print('L2: (unsorted)') |
| for i in range(m): |
| print("%d\t:\t%d" % (i, L2[i])) |
| L2 = sorted(L2.items(), key=lambda x: x[1]) |
| # Search for a pair with identical second coordinates |
| for e in L1: |
| for f in L2: |
| if e[1] == f[1]: |
| j = e[0] |
| k = f[0] |
| break; |
| return m * j + k % n |
| if __name__ == '__main__': |
| # a = 2 |
| # b = 767 |
| # n = 526483 |
| # d = Shanks(n, a, b) |
| # print(d) |
| # a = 2 |
| # b = 48 |
| # n = 101 |
| # d = Shanks(n, a, b) |
| # print(d) |
| # a = 2 |
| # b = (48**27)*(27**33) |
| # n = 101 |
| # d = Shanks(n, a, b) |
| # print(d) |
| a = 2 |
| b = 19 |
| n = 4481 |
| d = Shanks(n, a, b) |
| print(d) |