# Here's how one defines a finite field as well as an elliptic curve over that field.
F = GF(599); print F
E = EllipticCurve(F, [0,0,0,0,1]); print E
# Here are a few points on the curve and their orders.
P = E([60,19]); print P
Q = E([277,239]); print Q
N = P.order(); print N
Finite Field of size 599 Elliptic Curve defined by y^2 = x^3 + 1 over Finite Field of size 599 (60 : 19 : 1) (277 : 239 : 1) 600 Finite Field of size 599 Elliptic Curve defined by y^2 = x^3 + 1 over Finite Field of size 599 (60 : 19 : 1) (277 : 239 : 1) 600 |
# Here is an implementation of Shanks's "Baby Step/Giant Step" Method
def BabyStepGiantStep(E, P, Q):
q = E.base_ring().cardinality()
m = ceil(sqrt(q) + 1)
R = m*P;
BabyStep = [ [k, k*P] for k in range(m) ]
print "Baby Step results:"; print BabyStep
GiantStep = [ [k, Q-k*R] for k in range(m) ]
print "Giant Step results:"; print GiantStep
k = min([ b[0]+g[0]*m for b in BabyStep for g in GiantStep if b[1]==g[1] ])
return k
# In this example, we show that the point Q = (30 : 40 : 1) is 23 times P = (0 : 1 : 1).
E = EllipticCurve( GF(41), [0,0,0,2,1] )
P = E( [ 0, 1] )
Q = E( [30,40] )
k = BabyStepGiantStep(E, P, Q); print k
k*P - Q
Baby Step results: [[0, (0 : 1 : 0)], [1, (0 : 1 : 1)], [2, (1 : 39 : 1)], [3, (8 : 23 : 1)], [4, (38 : 38 : 1)], [5, (23 : 23 : 1)], [6, (20 : 28 : 1)], [7, (26 : 9 : 1)]] Giant Step results: [[0, (30 : 40 : 1)], [1, (9 : 25 : 1)], [2, (26 : 9 : 1)], [3, (0 : 40 : 1)], [4, (22 : 22 : 1)], [5, (11 : 1 : 1)], [6, (12 : 21 : 1)], [7, (20 : 28 : 1)]] 23 (0 : 1 : 0) Baby Step results: [[0, (0 : 1 : 0)], [1, (0 : 1 : 1)], [2, (1 : 39 : 1)], [3, (8 : 23 : 1)], [4, (38 : 38 : 1)], [5, (23 : 23 : 1)], [6, (20 : 28 : 1)], [7, (26 : 9 : 1)]] Giant Step results: [[0, (30 : 40 : 1)], [1, (9 : 25 : 1)], [2, (26 : 9 : 1)], [3, (0 : 40 : 1)], [4, (22 : 22 : 1)], [5, (11 : 1 : 1)], [6, (12 : 21 : 1)], [7, (20 : 28 : 1)]] 23 (0 : 1 : 0) |
# Here is an implementation of Pollard's "Rho" Method for the Discrete Logarithm Problem.
def PollardRhoMethod(E, M, P, Q):
a = M[0,0]
b = M[0,1]
Data = [[ a, b, a*P+b*Q ]]
Bool = []
s = M.nrows() - 1
print "Beginning search for cycles:"
print Data[-1][0], "* P +", Data[-1][1], "* Q =", Data[-1][2]
while Bool == []:
u = Data[-1][0]
v = Data[-1][1]
R = Data[-1][2]
i = mod( R[0] - 1, s) + 1
a = M[i,0]
b = M[i,1]
New = [ u+a, v+b, R+a*P+b*Q ]
Bool = [ Old for Old in Data if Old[-1] == New[-1] ]
Data.append(New)
print Data[-1][0], "* P +", Data[-1][1], "* Q =", Data[-1][2]
u0 = Data[-1][0]
v0 = Data[-1][1]
u1 = Bool[-1][0]
v1 = Bool[-1][1]
N = P.order()
d = GCD( v0 - v1, N)
print "Cycle found:"
print (u0 - u1), "* P +", (v0 - v1), "* Q =", N, "* P = (0 : 1 : 0)"
print "Searching through", d, "candidate(s) for k"
k0 = mod( (u0 - u1)/(v1 - v0), numerator(N/d) )
kList = [ lift(mod(k0 + m*numerator(N/d), N )) for m in range(d) ]
k = min([k for k in kList if k*P == Q])
return k
# In this example, we show that Q = (413 : 959 : 1) is 499 times P = (0 : 1 : 1).
E = EllipticCurve( GF(1093), [0,0,0,1,1] )
P = E( [ 0, 1] )
Q = E( [413, 959] )
M = matrix(ZZ, [[3,5], [9,17], [19,6], [4,3]]); print M
k = PollardRhoMethod(E, M, P, Q); print k
k*P - Q
[ 3 5]
[ 9 17]
[19 6]
[ 4 3]
Beginning search for cycles:
3 * P + 5 * Q = (326 : 69 : 1)
22 * P + 11 * Q = (727 : 589 : 1)
31 * P + 28 * Q = (560 : 365 : 1)
50 * P + 34 * Q = (1070 : 260 : 1)
69 * P + 40 * Q = (473 : 903 : 1)
88 * P + 46 * Q = (1006 : 951 : 1)
97 * P + 63 * Q = (523 : 938 : 1)
106 * P + 80 * Q = (506 : 116 : 1)
125 * P + 86 * Q = (412 : 520 : 1)
134 * P + 103 * Q = (814 : 906 : 1)
143 * P + 120 * Q = (583 : 230 : 1)
152 * P + 137 * Q = (210 : 207 : 1)
155 * P + 142 * Q = (523 : 938 : 1)
Cycle found:
58 * P + 79 * Q = 1067 * P = (0 : 1 : 0)
Searching through 1 candidate(s) for k
499
\newcommand{\Bold}[1]{\mathbf{#1}}\left(0 : 1 : 0\right)
[ 3 5]
[ 9 17]
[19 6]
[ 4 3]
Beginning search for cycles:
3 * P + 5 * Q = (326 : 69 : 1)
22 * P + 11 * Q = (727 : 589 : 1)
31 * P + 28 * Q = (560 : 365 : 1)
50 * P + 34 * Q = (1070 : 260 : 1)
69 * P + 40 * Q = (473 : 903 : 1)
88 * P + 46 * Q = (1006 : 951 : 1)
97 * P + 63 * Q = (523 : 938 : 1)
106 * P + 80 * Q = (506 : 116 : 1)
125 * P + 86 * Q = (412 : 520 : 1)
134 * P + 103 * Q = (814 : 906 : 1)
143 * P + 120 * Q = (583 : 230 : 1)
152 * P + 137 * Q = (210 : 207 : 1)
155 * P + 142 * Q = (523 : 938 : 1)
Cycle found:
58 * P + 79 * Q = 1067 * P = (0 : 1 : 0)
Searching through 1 candidate(s) for k
499
\newcommand{\Bold}[1]{\mathbf{#1}}\left(0 : 1 : 0\right)
|
# Here is an implementation of the Pohlig-Hellman Method.
def PohligHellman(E, P, Q):
N = P.order()
B = matrix(list(factor(N)))
s = B.nrows()
nList = [ B[i,0]^B[i,1] for i in range(s) ]
i = 0; kList = []
while i < s:
p = B[i,0]
e = B[i,1]
T = [ numerator(j*N/p)*P for j in range(p) ]
j = 0; qList = [ [0,Q] ]
while j < e:
temp = T.index( numerator(N/p^(j+1))*qList[-1][1] )
qList.append([ temp*p^j, qList[-1][1] - temp*p^j*P ])
j = j+1
kList.append(sum([q[0] for q in qList]))
print "k =", kList[-1], "modulo", nList[i]
i = i+1
return crt(kList, nList)
# In this example, we show that Q = (277:239:1) is 266 times P = (60:19:1).
E = EllipticCurve(GF(599), [0,0,0,0,1])
P = E([ 60, 19])
Q = E([277,239])
k = PohligHellman(E, P, Q); print k
k*P - Q
k = 2 modulo 8
k = 2 modulo 3
k = 16 modulo 25
266
\newcommand{\Bold}[1]{\mathbf{#1}}\left(0 : 1 : 0\right)
k = 2 modulo 8
k = 2 modulo 3
k = 16 modulo 25
266
\newcommand{\Bold}[1]{\mathbf{#1}}\left(0 : 1 : 0\right)
|
# Here we use Unicode (actually, UTF-8) to write any string as an integer.
def StringToNumber(Str):
lst = unicode(Str,'utf-8')
n = len(lst)
b = 2^(16)
return sum( ord(lst[k])*b^k for k in range(n) )
def NumberToString(Nmbr):
m = Integer(Nmbr)
b = 2^(16)
lst = []
while m != 0:
lst.append( unichr(m % b).encode('utf-8') )
m //= b
return ''.join(lst)
# Here is a simple example.
print StringToNumber('hello to everyone in the class')
print NumberToString(5478005390604350828832014232884173246445564752857594674494869730649688013594911151241644679840477300600646181723293258839806442545835925635176)
547800539060435082883201423288417324644556475285759467449486973064968801\ 3594911151241644679840477300600646181723293258839806442545835925635176 hello to everyone in the class 5478005390604350828832014232884173246445564752857594674494869730649688013594911151241644679840477300600646181723293258839806442545835925635176 hello to everyone in the class |
# Here is an implementation of an affine cipher: the ciphertext is lambda * plaintext + nu.
def AffineCipher(Lambda, Nu, Str):
plaintext = unicode(Str,'utf-8')
n = len(plaintext)
b = 2^(16)
N = sum( ord(plaintext[k])*b^k for k in range(n) )
M = numerator(Lambda*N + Nu*(b^n - 1)/(b - 1))
ciphertext = []
while M != 0:
ciphertext.append(unichr(M % b).encode('utf-8'))
M //= b
return ''.join(ciphertext)
# The Caesar Cipher was a shift by 3 places.
print AffineCipher(1,3,'hello')
# Here is a fun example in Klingon! You must have fonts installed from http://www.kasper-online.de/en/docs/startrek/klingon.htm
print AffineCipher(1,63599,'hello')
khoor khoor |
# Here we perform a frequency analysis of a text imported from a web page.
def FrequencyAnalysis(Url):
import urllib
urltext = str(urllib.urlopen(Url).readlines())
plaintext = unicode(urltext,'utf-8')
n = len(plaintext)
b = 2^(16)
data = [ ord(plaintext[k]) for k in range(n) ]
print "Imported", len(data), "characters."
TimeSeries(data).plot_histogram(normalize = False, axes_labels=['Character','Frequency'], aspect_ratio = 'automatic').show()
# 'The Declaration of Independence of The United States of America' by Thomas Jefferson
FrequencyAnalysis('http://www.gutenberg.org/files/16780/16780.txt')
# 'On the Origin of Species' by Charles Darwin
FrequencyAnalysis('http://www.gutenberg.org/files/1228/1228.txt')
# 'Ulysses' by James Joyce
FrequencyAnalysis('http://www.gutenberg.org/files/4300/4300.txt')
# 'War and Peace' by Leo Tolstoy
FrequencyAnalysis('http://www.gutenberg.org/files/2600/2600.txt')
# 'Gadsby: a story of over 50,000 words without using the letter E' by Ernest Vincent Wright
FrequencyAnalysis('http://homepage.mac.com/ehgoins/ma598/gadsby.txt')
Imported 36824 characters. Imported 36824 characters. |
Imported 1068107 characters.
Imported 1771417 characters.
Imported 3683966 characters.
Imported 298459 characters.
# Neal Koblitz introduced a way to encode a message as a point on a given elliptic curve.
def KoblitzEncode(E, Str):
b = 2^(16)
p = E.base_field().cardinality()
plaintext = str(Str)
n = len(plaintext)
m = sum(ord(plaintext[k])*b^k for k in range(n))
d = min( floor(p/(m+1)), 100)
for k in range(d):
x = (d*m + k) % p
z = E.two_division_polynomial(x) % p
if z == power_mod(z, int((p+1)/2), p):
y = (-E.a1()*x - E.a3() + power_mod(z, int((p+1)/4), p))/2 % p
return E([x,y])
def KoblitzDecode(P):
b = 2^(16)
d = 100
m = floor( int(P[0]/P[2])/d )
lst = []
while m != 0:
lst.append(unichr(m % b).encode('utf-8'))
m //= b
return ''.join(lst)
def KoblitzBreak(E, Str):
b = 2^(16)
d = 100
p = E.base_field().cardinality()
max_length = floor(log(p/d, b))
plaintext = str(Str)
n = len(plaintext)
lst = []
counter = 0
while counter != ceil(n/max_length):
lst.append(plaintext[max_length*counter : min(max_length*(counter+1),n)])
counter = counter+1
print "Breaking up the message as follows:"; print lst
return [ KoblitzEncode(E, text) for text in lst]
# Here are a few examples.
p = next_prime(100*2^(16*8)); print p
E = EllipticCurve(GF(p), [0,0,0,0,1]); print E
plaintext = 'hello!'
P = KoblitzEncode(E, plaintext); print P
S = KoblitzDecode(P); print S
plaintext = 'Sometimes the message is too long for just one point, and we will need to break it up over several points.'
P = KoblitzBreak(E, plaintext); print P
34028236692093846346337460743176821145607 Elliptic Curve defined by y^2 = x^3 + 1 over Finite Field of size 34028236692093846346337460743176821145607 (3989659966627470587337124000 : 21867283570004036175290000298745787608002 : 1) hello! Breaking up the message as follows: ['Sometime', 's the me', 'ssage is', ' too lon', 'g for ju', 'st one p', 'oint, an', 'd we wil', 'l need t', 'o break ', 'it up ov', 'er sever', 'al point', 's.'] [(52443061870867099620465588000043835501 : 16213708275273584336986920292769476671670 : 1), (52443061862041913467247129959333899503 : 2915460992663385759115306515664097172786 : 1), (59712245772725666441426631745096920302 : 27659258559825318694849802990636380653215 : 1), (57116144889543470132526198833047145601 : 23034147086597770488143587378429819591300 : 1), (60750713067248907374558968316061296701 : 8733665863261135643409384861803290785898 : 1), (58153978357920468780838809683650161905 : 14487060683884360257914074834462770345396 : 1), (57116033960928136069616011653998193501 : 16934698858872332540212761725408866350256 : 1), (56077637982268814449512163991722403602 : 22165715548634591379996766439108381669612 : 1), (60230897101213490647938437482754878000 : 20772498776814565288784623926715368981380 : 1), (16616197700377117805295743460284836700 : 31181546981609099391792340364745598478847 : 1), (61269982367183643580400854900853975300 : 15793016338757989810377473039772290686587 : 1), (59192984406003940021862097651826698100 : 31043748296390283061008363236579337786813 : 1), (60231515081485583266632644396607088105 : 17238321360574074140191666050466244934729 : 1), (301477100 : 19590822968871651022502870759760179668589 : 1)] 34028236692093846346337460743176821145607 Elliptic Curve defined by y^2 = x^3 + 1 over Finite Field of size 34028236692093846346337460743176821145607 (3989659966627470587337124000 : 21867283570004036175290000298745787608002 : 1) hello! Breaking up the message as follows: ['Sometime', 's the me', 'ssage is', ' too lon', 'g for ju', 'st one p', 'oint, an', 'd we wil', 'l need t', 'o break ', 'it up ov', 'er sever', 'al point', 's.'] [(52443061870867099620465588000043835501 : 16213708275273584336986920292769476671670 : 1), (52443061862041913467247129959333899503 : 2915460992663385759115306515664097172786 : 1), (59712245772725666441426631745096920302 : 27659258559825318694849802990636380653215 : 1), (57116144889543470132526198833047145601 : 23034147086597770488143587378429819591300 : 1), (60750713067248907374558968316061296701 : 8733665863261135643409384861803290785898 : 1), (58153978357920468780838809683650161905 : 14487060683884360257914074834462770345396 : 1), (57116033960928136069616011653998193501 : 16934698858872332540212761725408866350256 : 1), (56077637982268814449512163991722403602 : 22165715548634591379996766439108381669612 : 1), (60230897101213490647938437482754878000 : 20772498776814565288784623926715368981380 : 1), (16616197700377117805295743460284836700 : 31181546981609099391792340364745598478847 : 1), (61269982367183643580400854900853975300 : 15793016338757989810377473039772290686587 : 1), (59192984406003940021862097651826698100 : 31043748296390283061008363236579337786813 : 1), (60231515081485583266632644396607088105 : 17238321360574074140191666050466244934729 : 1), (301477100 : 19590822968871651022502870759760179668589 : 1)] |
# We will use the elliptic curves suggested by NIST: http://csrc.nist.gov/publications/fips/fips186-3/fips_186-3.pdf
i = 0
p = [
6277101735386680763835789423207666416083908700390324961279,
115792089210356248762697446949407573530086143415290314195533631308867097853951,
39402006196394479212279040100143613805079739270465446667948293404245721771496870329047266088258938001861606973112319,
6864797660130609714981900799081393217269435300143305409394463459185543183397656052122559640661454554977296311391480858037121987999716643812574028291115057151
][i]
b = [
0x64210519e59c80e70fa7e9ab72243049feb8deecc146b9b1,
0x5ac635d8aa3a93e7b3ebbd55769886bc651d06b0cc53b0f63bce3c3e27d2604b,
0xb3312fa7e23ee7e4988e056be3f82d19181d9c6efe8141120314088f5013875ac656398d8a2ed19d2a85c8edd3ec2aef,
0x051953eb9618e1c9a1f929a21a0b68540eea2da725b99b315f3b8b489918ef109e156193951ec7e937b1652c0bd3bb1bf073573df883d2c34f1ef451fd46b503f00
][i]
N = [
6277101735386680763835789423176059013767194773182842284081,
115792089210356248762697446949407573529996955224135760342422259061068512044369,
39402006196394479212279040100143613805079739270465446667946905279627659399113263569398956308152294913554433653942643,
6864797660130609714981900799081393217269435300143305409394463459185543183397655394245057746333217197532963996371363321113864768612440380340372808892707005449
][i]
|
|
# Real-time example of Diffie-Hellman Key Exchange
E = EllipticCurve(GF(p), [0,0,0,-3,b]); print E
P0 = KoblitzBreak(E, 'this will be our initialization')[0]; print P0
# First we choose private keys then perform a key exchange.
AlicePrivateKey = [ 'alices key for lambda', 'alices key for nu' ]
AlicePublicKey = [ (StringToNumber(AlicePrivateKey[0]) % N)*P0, (StringToNumber(AlicePrivateKey[1]) % N)*P0 ]; print AlicePublicKey
BobPrivateKey = [ 'bobs key for lambda', 'bobs key for nu' ]
BobPublicKey = [ (StringToNumber(BobPrivateKey[0]) % N)*P0, (StringToNumber(BobPrivateKey[1]) % N)*P0 ]; print BobPublicKey
Lambda = StringToNumber(KoblitzDecode( StringToNumber(AlicePrivateKey[0])*BobPublicKey[0] )); print "Lambda =", Lambda
Nu = StringToNumber(KoblitzDecode( StringToNumber(AlicePrivateKey[1])*BobPublicKey[1] )); print "Nu =", Nu
# Next we encrypt a message using an affine cipher.
# This message has too many characters to be encoded as one point on the elliptic curve, so we break into several messages.
plaintext = 'here is our secret message!'
print KoblitzBreak(E, plaintext)
ciphertext = AffineCipher(Lambda, Nu, plaintext); print ciphertext
print KoblitzBreak(E, ciphertext)
Elliptic Curve defined by y^2 = x^3 + 6277101735386680763835789423207666416083908700390324961276*x + 2455155546008943817740293915197451784769108058161191238065 over Finite Field of size 6277101735386680763835789423207666416083908700390324961279 Breaking up the message as follows: ['this will b', 'e our initi', 'alization'] (14322787411902589536774281949136941733871001377189200 : 5303103525169985974489105056569940866329182287986373852161 : 1) [(2441268929662413824665313447403547599382607120572951193356 : 6222811382787892072564074296536211086430693908956788798531 : 1), (399841724491984216117685577907653958790377681764295904255 : 53988097076620983009411264512562328693284928497682243057 : 1)] [(1488897016211500260066170691110599481225656063502860607453 : 2934167938868827505048840616443318453197217583760618923858 : 1), (6239460153619465513738041726248613314535534498269024048135 : 4086778345555684233784035137519124751085613450535075089451 : 1)] Lambda = 5172823602760195049846425933984286430454376906389063638 Nu = 22260663599139745666010579746740261220533861424275423125 Breaking up the message as follows: ['here is our', ' secret mes', 'sage!'] [(16661379588068266964896263879455464109902320087869603 : 3923350887908929149608178453805303000436995853411973597965 : 1), (16807494070540983134343340545717543086014674259152002 : 5532884037072910546504162633848626183901112147461295898141 : 1), (60877098384745096817900 : 536253550486203974372289166933329874683742082244308490484 : 1)] 꺅畺﹑剚늚뷡綐蹯菂䭴瑕䠒ᘽ㺽椁꒚䛴뉍ꩱ僂ꝥ㓪쀣ꌫ蟡뀨⌧˧뤪ߞ Breaking up the message as follows: ['\xea\xba\x85\xed\xa7\xbe\xee\xb6\xa1\xe7\x95', '\xba\xef\xb9\x91\xe5\x89\x9a\xeb\x8a\x9a\xeb', '\xb7\xa1\xef\x9e\x8c\xe7\xb6\x90\xe8\xb9\xaf', '\xe8\x8f\x82\xe4\xad\xb4\xef\x9c\x99\xe7\x91', '\x95\xed\xb4\xae\xe4\xa0\x92\xe1\x98\xbd\xe3', '\xba\xbd\xe6\xa4\x81\xea\x92\x9a\xe4\x9b\xb4', '\xeb\x89\x8d\xed\xbd\xb7\xef\xa2\xac\xea\xa9', '\xb1\xe5\x83\x82\xea\x9d\xa5\xe3\x93\xaa\xec', '\x80\xa3\xee\xbd\xbe\xea\x8c\xab\xe8\x9f\xa1', '\xeb\x80\xa8\xe2\x8c\xa7\xcb\xa7\xeb\xa4\xaa', '\xdf\x9e'] [(21776889548923180147745061315926016814434530322045800 : 1023640696300569192408769985173717651415189641937728373109 : 1), (34345631913448294633088229848563723836018584656300201 : 1917316996888431127442771387021116753201599681397713730073 : 1), (25576691224971599568175118721395441476806495548229501 : 338232285862704222245480214583798700440162842590880673128 : 1), (21192288893718579586962926028853644353581924371684001 : 5054222412868100962235565872438496591803232204980030409021 : 1), (33176508656668157277035352921941877394907436502235702 : 5047387700227047294636118910025530427427219743922430696004 : 1), (26307375141265347680650798657647146748525600237177003 : 325457136695247830858267824065787106478966296247696371467 : 1), (24699899514182845762366610652272455195921662561508301 : 885430181668668070882395650257144437569803581467298962342 : 1), (34491817758679952550384135974866075648066560072107300 : 528135880325396931305696423181863482719701467565020697374 : 1), (23530530950770833321938552086969803655324777231168000 : 5371952940849608571451079423070968981741315842052212915685 : 1), (24845893574843327847290106653326196897109525712100300 : 1178660474404336838597085807884215015172653777371129687282 : 1), (1035491101 : 3293322091099630847735268092123527258113050780925664206547 : 1)] Elliptic Curve defined by y^2 = x^3 + 6277101735386680763835789423207666416083908700390324961276*x + 2455155546008943817740293915197451784769108058161191238065 over Finite Field of size 6277101735386680763835789423207666416083908700390324961279 Breaking up the message as follows: ['this will b', 'e our initi', 'alization'] (14322787411902589536774281949136941733871001377189200 : 5303103525169985974489105056569940866329182287986373852161 : 1) [(2441268929662413824665313447403547599382607120572951193356 : 6222811382787892072564074296536211086430693908956788798531 : 1), (399841724491984216117685577907653958790377681764295904255 : 53988097076620983009411264512562328693284928497682243057 : 1)] [(1488897016211500260066170691110599481225656063502860607453 : 2934167938868827505048840616443318453197217583760618923858 : 1), (6239460153619465513738041726248613314535534498269024048135 : 4086778345555684233784035137519124751085613450535075089451 : 1)] Lambda = 5172823602760195049846425933984286430454376906389063638 Nu = 22260663599139745666010579746740261220533861424275423125 Breaking up the message as follows: ['here is our', ' secret mes', 'sage!'] [(16661379588068266964896263879455464109902320087869603 : 3923350887908929149608178453805303000436995853411973597965 : 1), (16807494070540983134343340545717543086014674259152002 : 5532884037072910546504162633848626183901112147461295898141 : 1), (60877098384745096817900 : 536253550486203974372289166933329874683742082244308490484 : 1)] 꺅畺﹑剚늚뷡綐蹯菂䭴瑕䠒ᘽ㺽椁꒚䛴뉍ꩱ僂ꝥ㓪쀣ꌫ蟡뀨⌧˧뤪ߞ Breaking up the message as follows: ['\xea\xba\x85\xed\xa7\xbe\xee\xb6\xa1\xe7\x95', '\xba\xef\xb9\x91\xe5\x89\x9a\xeb\x8a\x9a\xeb', '\xb7\xa1\xef\x9e\x8c\xe7\xb6\x90\xe8\xb9\xaf', '\xe8\x8f\x82\xe4\xad\xb4\xef\x9c\x99\xe7\x91', '\x95\xed\xb4\xae\xe4\xa0\x92\xe1\x98\xbd\xe3', '\xba\xbd\xe6\xa4\x81\xea\x92\x9a\xe4\x9b\xb4', '\xeb\x89\x8d\xed\xbd\xb7\xef\xa2\xac\xea\xa9', '\xb1\xe5\x83\x82\xea\x9d\xa5\xe3\x93\xaa\xec', '\x80\xa3\xee\xbd\xbe\xea\x8c\xab\xe8\x9f\xa1', '\xeb\x80\xa8\xe2\x8c\xa7\xcb\xa7\xeb\xa4\xaa', '\xdf\x9e'] [(21776889548923180147745061315926016814434530322045800 : 1023640696300569192408769985173717651415189641937728373109 : 1), (34345631913448294633088229848563723836018584656300201 : 1917316996888431127442771387021116753201599681397713730073 : 1), (25576691224971599568175118721395441476806495548229501 : 338232285862704222245480214583798700440162842590880673128 : 1), (21192288893718579586962926028853644353581924371684001 : 5054222412868100962235565872438496591803232204980030409021 : 1), (33176508656668157277035352921941877394907436502235702 : 5047387700227047294636118910025530427427219743922430696004 : 1), (26307375141265347680650798657647146748525600237177003 : 325457136695247830858267824065787106478966296247696371467 : 1), (24699899514182845762366610652272455195921662561508301 : 885430181668668070882395650257144437569803581467298962342 : 1), (34491817758679952550384135974866075648066560072107300 : 528135880325396931305696423181863482719701467565020697374 : 1), (23530530950770833321938552086969803655324777231168000 : 5371952940849608571451079423070968981741315842052212915685 : 1), (24845893574843327847290106653326196897109525712100300 : 1178660474404336838597085807884215015172653777371129687282 : 1), (1035491101 : 3293322091099630847735268092123527258113050780925664206547 : 1)] |
# Here we work through a real-time example of RSA.
plaintext = 'dont forget your towel'
n = floor(len(plaintext)/2)
p = next_prime(2^(16*n)); print "p =", p
q = next_prime(2^(16*n + 1)); print "q =", q
N = p*q; print "N =", N
PhiN = (p-1)*(q-1)
P = StringToNumber(plaintext) % N
print "Working with plaintext '", NumberToString(P),"'."
# Alice and Bob choose their public keys.
AlicePublicKey = StringToNumber('dont panic') % PhiN
AlicePublicKey = int( AlicePublicKey / gcd( AlicePublicKey, PhiN )) % PhiN
print "Alice's Public Key:", AlicePublicKey
BobPublicKey = StringToNumber('what about bob') % PhiN
BobPublicKey = int( BobPublicKey / gcd( BobPublicKey, PhiN )) % PhiN
print "Bob's Public Key:", BobPublicKey
# Alice and Bob choose their private keys.
AlicePrivateKey = power_mod( AlicePublicKey, -1, PhiN )
print "Alice's Private Key:", AlicePrivateKey
BobPrivateKey = power_mod( BobPublicKey, -1, PhiN )
print "Bob's Private Key:", BobPrivateKey
# We pass the numbers back and forth three times.
Q1 = power_mod( P, AlicePublicKey, N ); print Q1
Q2 = power_mod( Q1, BobPublicKey, N ); print Q2
Q3 = power_mod( Q2, AlicePrivateKey, N ); print Q3
print "The plaintext was '", NumberToString(power_mod( Q3, BobPrivateKey, N)),"'!"
p = 95780971304118053647396689196894323976171195136475563 q = 191561942608236107294793378393788647952342390272950347 N = 183479889279205720928865671624166955263725199133463379704230522407672214\ 40232142379387122287921287277870361 Working with plaintext ' dont forget your towel '. Alice's Public Key: 551952376218554682314173742057592422689128473 Bob's Public Key: 40315558422048757912804420848262156232252433934157777887082053751 Alice's Private Key: 154373608039978510496908113061132339693654428467988857720199789111803625\ 00777386828184980120545695953516129 Bob's Private Key: 392628837256747576818420388070012996215819298345643865213051470901226418\ 0290846318657940602753989858862879 114953961980150272377324483035683719025281618689212184915373949945706533\ 01319100193472258717336106319175245 205160939627005707203314225637750700043978102031807417992540904202294685\ 5834353427883260173386033071491722 404593696514415988195837755932564946751528339310871896321701554090774697\ 0744622038899618967736877874559657 The plaintext was ' dont forget your towel '! p = 95780971304118053647396689196894323976171195136475563 q = 191561942608236107294793378393788647952342390272950347 N = 18347988927920572092886567162416695526372519913346337970423052240767221440232142379387122287921287277870361 Working with plaintext ' dont forget your towel '. Alice's Public Key: 551952376218554682314173742057592422689128473 Bob's Public Key: 40315558422048757912804420848262156232252433934157777887082053751 Alice's Private Key: 15437360803997851049690811306113233969365442846798885772019978911180362500777386828184980120545695953516129 Bob's Private Key: 3926288372567475768184203880700129962158192983456438652130514709012264180290846318657940602753989858862879 11495396198015027237732448303568371902528161868921218491537394994570653301319100193472258717336106319175245 2051609396270057072033142256377507000439781020318074179925409042022946855834353427883260173386033071491722 4045936965144159881958377559325649467515283393108718963217015540907746970744622038899618967736877874559657 The plaintext was ' dont forget your towel '! |
def factorial_mod(a, B, N):
b = 1
a1 = a
while b <= B:
a1 = power_mod(a1, b, N)
b = b+1
return a1
def Pollard(N):
B = 10^4
a = 2
while a < N:
d = gcd(a, N)
if d > 1:
print "a =", a, "d =", d
return d
a1 = factorial_mod( a, B, N )
d = gcd(a1 - 1, N)
if (d > 1) and (d < N):
print "a =", a, "d =", d
return d
a = a + 1
n = 6;
p = floor(10^(n/2) * random()).next_prime()
q = floor(10^(n/2) * random()).next_prime()
N = p * q; print N
Pollard(N)
361567
a = 547 d = 547
\newcommand{\Bold}[1]{\mathbf{#1}}547
361567
a = 547 d = 547
\newcommand{\Bold}[1]{\mathbf{#1}}547
|
|
|