import numpy import itertools ############################################################################################################################ # For all these procedures we are working with elliptic curve (EC) groups over Z_p where p is a prime number larger than 3.# # An Elliptic Curve group will be represented by a triple [A,B,p] where # # (1) p is a prime number larger than 3 # # (2) A is the coefficient of x and # # (3) B is the constant term in y^2 = x^3 + A*x + B mod p. # # # # A point in the group will be represented as a pair [x,y] where # # (1) x is the x-coordinate of a solution # # (2) y is the y-coordinate of a solution # # (3) The identity will be represented by [] # ############################################################################################################################ def TonSh (a, Prime): if kronecker(a, Prime) == -1: pass print "{0} does not have a square root mod {1}".format(a, Prime) return None elif Prime % 4 == 3: x = power_mod(ZZ(a), ZZ((Prime+1)/4),ZZ(Prime)) return(x) else: ################################################################################# # Determine e so that Prime-1 = (2^e)*q for some odd number q # ################################################################################# e = ZZ(0) q = ZZ(Prime - 1) # for j in range(1, Prime): for j in itertools.count(1): if q % 2 == 0: e = ZZ(e + 1) q = ZZ(q / 2) else: break for i in range(1, 101): n = i if kronecker(n, Prime) == -1: break z = power_mod(ZZ(n),ZZ(q),ZZ(Prime)) y = ZZ(z) r = ZZ(e) x = power_mod(ZZ(a),ZZ( (q-1)/2),ZZ( Prime)) b = (a * x ** 2) % Prime x = (a * x) % Prime #for i in range(1, e + 1): for i in itertools.count(1): if b == 1: break else: for m in itertools.count(1): t = power_mod(ZZ(b), ZZ(2^m) , ZZ(Prime)) if t == 1: mm = m break t = power_mod(ZZ(y), ZZ(2^(r - mm - 1)),ZZ(Prime)) y = power_mod(ZZ(t), ZZ(2),ZZ(Prime)) r = mm x = (x * t) % Prime b = (b * y) % Prime return(x)
ECSearch is a procedure that searches for a point on a given elliptic curve with first coordinate between "lowerbound" and "upperbound". The lowerbound and the upperbound are positive random numbers.
import itertools def ECSearch (lowerbound, upperbound, Group): p = Group[2] a = Group[0] b = Group[1] if (4 * a ** 3 + 27 * b ** 2) % p == 0: print "This is not an elliptic curve. " else: for j in itertools.count(lowerbound): if j==lowerbound-1 or j>upperbound or j>upperbound: return "not found" j=j%p #print "test "+str(j) #print (kronecker(j ** 3 + a * j + b, p) ) if kronecker(j ** 3 + a * j + b, p) == 1: x = (j ** 3 + a * j + b) % p var('z') #print("stuck here") #print ("Modsqrt({0}, {1})".format(x,p)) #L = solve_mod(z ** 2 == x, p) L=TonSh(x,p) y = L #if y>p/2: # y=p/2-(y-p/2) #y = L[0][0] return([j,y])
import sympy.ntheory def FermatGreat (N): if sympy.ntheory.isprime(N): if N % 4 == 1: Z = two_squares(N) #print(Z) return(Z) else: print "{0} is prime, but {1} mod 4 = 3".format(N, N) else: print "{0} is not prime\n".format(N)
ECAdd is a procedure that computes the sum of two points on a given elliptic curve using the elliptic curve operation.
def ECAdd (Point1, Point2, Group): a = Group[0] b = Group[1] p = Group[2] ''' #This could be an optimization for code readability E = EllipticCurve(GF(p),[a,b]) p1 = E(Point1[0],Point1[1]) p2 = E(Point2[0],Point2[1]) toReturn = p1+p2 return [toReturn[0],toReturn[1]] ''' if(Point1!=[]): x1 = Point1[0] y1 = Point1[1] if(Point2!=[]): x2 = Point2[0] y2 = Point2[1] if (4 * a ** 3 + 27 * b ** 2) % p == 0: print "This is not an elliptic curve. " elif Point1 != [] and y1 ** 2 % p != (x1 ** 3 + a * x1 + b) % p: print "Point 1 is not on the elliptic curve. \n" elif Point2 != [] and y2 ^ 2 % p != (x2 ^ 3 + a * x2 + b) % p: print "Point 2 is not on the elliptic curve. \n" else: if Point1 == []: R = Point2 elif Point2 == []: R = Point1 else: if x1 == x2 and 0 == (y1 + y2) % p: R = [] elif x1 == x2 and y1 == y2: R = ECDouble(Point1, Group) else: s = ((y1 - y2) / (x1 - x2)) % p x = (s ** 2 - x1 - x2) % p y = (s * (x1 - x) - y1) % p R = [x,y] return(R)
def ECDouble (Point, Group): a = Group[0] b = Group[1] p = Group[2] if Point != []: x1 = Point[0] y1 = Point[1] if (4 * a ** 3 + 27 * b ** 2) % p == 0: print "This is not an elliptic curve. " elif Point != [] and y1 ** 2 % p != (x1 ** 3 + a * x1 + b) % p: print "The point to double is not on the elliptic curve. " elif y1 == 0: R = [] else: s = mod((3 * x1 ** 2 + a) / y1 / 2, p) x = (s ** 2 - 2 * x1) % p y = (s * (x1 - x) - y1) % p R = [x,y] else: R = [] return(R)
def ECInverse (Point, Group): if Point == []: return(Point) else: p = Group[2] x = Point[0] y = Point[1] return([x,(p - y) % p])
ECTimes is a procedure that adds a point k-times (scalar) to itself for a given elliptic curve using the elliptic curve operation.
def ECTimes (Point, scalar, Group): ECIdentity=[] if Point == ECIdentity or scalar == 0: return(ECIdentity) else: E=EllipticCurve(GF(Group[2]),[Group[0],Group[1]]) Eid = E(0,1,0) EPoint = E(Point[0],Point[1]) #print type(EPoint) cgret = scalar*EPoint if(cgret[0]==0 and cgret[1]==1 and cgret[2]==0): return ECIdentity #print cgret[0] return([ZZ(cgret[0]),ZZ(cgret[1])])
def findptOrder(point,group): E = EllipticCurve(GF(group[2]),[group[0],group[1]]) Ep = E(point[0],point[1]) return Ep.additive_order()
import math def ASCIIPad(Mess,Mod): K = [] for letter in Mess: K.append(ord(letter)) L = Mod.ndigits() l = len(K) y = ZZ(math.floor(L/3)) count = 0 padded = [] buffer = "" for numChar in K: numChar+=100 buffer+=str(numChar) count+=1 if count==y: padded.append(ZZ(buffer)) buffer = "" count = 0 if len(buffer)>0: padded.append(ZZ(buffer)) return padded def ASCIIDepad(Number): N = ""; #Number = ZZ(Number[0]) n = Number.ndigits() % 3; if (n > 0): print("This is not a padded ASCII string\n"); else: L = [((Number - (Number % (1000^i)))/1000^i)%1000 - 100 for i in range(Number.ndigits()/3)]; for i in range(Number.ndigits()/3): #print L[i] N = chr(L[i]) + N; return(N);
############################################################################################################################ # For all these procedures we are working with elliptic curve (EC) groups over Z_p where p is a prime number larger than 3.# # An Elliptic Curve group will be represented by a triple [A,B,p] where # # (1) p is a prime number larger than 3 # # (2) A is the coefficient of x and # # (3) B is the constant term in y^2 = x^3 + A*x + B mod p. # # # # The legendre attack procedure "KeyDiscover" assumes that the key is 160 bits and uses at least 16 signatures. # # # ############################################################################################################################ def NewLegendre(a,p): if is_prime(p): return (1+kronecker(a,p))/2 else: print "Second Parameter Must Be Prime" def BlockNumber(y,primelist): m=0 for j in xrange(4): m=2*m + NewLegendre(y,primelist[j+10]) return m+1 def BlockContents(y,primelist): k=0 for j in xrange(10): k=10*k+NewLegendre(y,primelist[j]) return k def KeyDiscover(ylist,primelist): c=10^10 k=0 for j in xrange(16): d = 16-BlockNumber(ylist[j],primelist) k = k+(BlockContents(ylist[j],primelist))*(c^d) return Integer("0b"+str(k))
P = 663387443711528942643635057898404027193421310082542021011656879155667905387 A = 21312312 B = 0 gp=[A,B,P] g=[492873375141017728843065648101283625090852213700867821647811199685629404285,89574915537919602031488396589957324227806408647943338161212529937502980733] bpt=[598336596907943085792954190531328937748185456383615216328831824083291776971, 311323267635439194031879743000297739927745849392795284445196597742592932909] E = EllipticCurve(GF(P),[A,B]) factor(E.order()) q=findptOrder(g,gp); q
2^2 * 3 * 7 * 7897469567994392174328988784504809847540729881935024059662581894710332207
7897469567994392174328988784504809847540729881935024059662581894710332207
y=[0]*16 s=[0]*16 y[0]=2775306968860011282841153081598756062285157697529883821387484144682208797 s[0]=26691106967260136602034787793019435523588534901980092703215093976156026455643277047 y[1]=6889460445512997835762154625661264720290054959876547939062735208796630377 s[1]=1223310020420919586416959311466154937571096043139426377037927229199751994495813724650420 y[2]=3156503332552767789653779952540247576075857415645820641462002285915536357 s[2]=671390469385743546754352736803526001406768264669746121444675093385829114184924415819 y[3]=3633476661228651948217610876388869293303326331579352110298732805934949460 s[3]=1020157344417942093095818703351548663490691237490448981545233270687752319929639366604836 y[4]=6051240609242928722748262684369501272184500111169118762170281555734588332 s[4]=1171257369875656975884255940135719733751156582289544307157905350245395605831103301 y[5]=505709848273131404381296663312273951887213395943981781025111773936144068 s[5]=556654225265105183725069782451005355240434513168018903853696789143783546988168922308 y[6]=1896573445566298490225138233993888441952888755899330347280807184145622430 s[6]=452739467677705033308145298024411210117328213244158824628276111194374828081945381956084774847648 y[7]=7562940396118444432059830785448255250373398604555442945304049438682968115 s[7]=806273119641449929303741720395536068992494280242226008969877697022700280384652594 y[8]=4877452590896244001254320541673743855593520471713794324609465306616380523 s[8]=1258240279925771097497572648746129701608651216817448001001363878471607652423066802 y[9]=5477271918370170896097395502480935482691591705300722748178938456583913429 s[9]=736117301080593613272171819786886304243454071873515608404910194033179556536881066389011065 y[10]=7654337266878349456232677995905874325374465160185144902005632771590300420 s[10]=891909961168740280836403522688031800577136090473974862864180020084578171708721060770001774 y[11]=4543752686876807772808322981524036743562657535980406525597278014281602499 s[11]=1290365422997096469628444395822772509501998217587189298862587321336440812307900600032119777 y[12]=5193135418981088589868798604460728008324379625696111565386240363451836204 s[12]=350827078389525218588424826910094734622153402432878132527810546561686922677909 y[13]=1303768824315450059990843126544916953043305343824195886067363048717332926 s[13]=402946629068361133119554058935320967949971946748597171835362363794159197252930395 y[14]=5945852717930063679258746612844748567811843700737417255721238229824328226 s[14]=1395794647445042238249949687850000728627602151933881347535900599363117314891494674 y[15]=2369287348264590865302627103771562350530663324115604403891496893112277167 s[15]=93383690378304347897519898080597675640162395239019937559720526714172709993028
p=[0]*14 p[0] = 1461501637330902918203684832716283019655932543267 p[1] = 1461501637330902918203684832716283019655932543333 p[2] = 1461501637330902918203684832716283019655932543397 p[3] = 1461501637330902918203684832716283019655932543447 p[4] = 1461501637330902918203684832716283019655932543477 p[5] = 1461501637330902918203684832716283019655932543619 p[6] = 1461501637330902918203684832716283019655932543661 p[7] = 1461501637330902918203684832716283019655932543837 p[8] = 1461501637330902918203684832716283019655932543897 p[9] = 1461501637330902918203684832716283019655932544107 p[10] = 1461501637330902918203684832716283019655932544627 p[11] = 1461501637330902918203684832716283019655932544677 p[12] = 1461501637330902918203684832716283019655932544737 p[13] = 1461501637330902918203684832716283019655932544863
mess=[0]*16 mess[0]="Wow!" mess[1]="WoW??" mess[2]="Yes." mess[3]="Yes??" mess[4]="No." mess[5]="Why?" mess[6]="Because." mess[7]="So?" mess[8]="So!" mess[9]="So-so." mess[10]="Oh-no." mess[11]="No-no." mess[12]="OK" mess[13]="Bye" mess[14]="Try" mess[15]="Hi" mess
['Wow!', 'WoW??', 'Yes.', 'Yes??', 'No.', 'Why?', 'Because.', 'So?', 'So!', 'So-so.', 'Oh-no.', 'No-no.', 'OK', 'Bye', 'Try', 'Hi']
print g print bpt print gp M=[0]*16 for j in xrange(16): M[j] = ASCIIPad(mess[j],q)[0] u=(M[j]/s[j]) % q v=(y[j]/s[j]) % q #print " u is "+str(u) #print " v is "+str(v) R=ECAdd(ECTimes(g,u,gp),ECInverse(ECTimes(bpt,v,gp),gp),gp) #print(R[0]) #print(q-y[j]) z = ZZ(mod(R[0], (q)))-y[j] #print mess[j] #print M[j] if z==0: print "signature {0} is valid".format(j) else: print "signature {0} is invalid".format(j)
[492873375141017728843065648101283625090852213700867821647811199685629404285, 89574915537919602031488396589957324227806408647943338161212529937502980733]
[598336596907943085792954190531328937748185456383615216328831824083291776971, 311323267635439194031879743000297739927745849392795284445196597742592932909]
[21312312, 0, 663387443711528942643635057898404027193421310082542021011656879155667905387]
signature 0 is valid
signature 1 is valid
signature 2 is valid
signature 3 is valid
signature 4 is valid
signature 5 is valid
signature 6 is valid
signature 7 is valid
signature 8 is valid
signature 9 is valid
signature 10 is valid
signature 11 is valid
signature 12 is valid
signature 13 is valid
signature 14 is valid
signature 15 is valid
X=KeyDiscover(y,p) X
514161840296455995546788761262864623039417126145
############################################################################################################################ # For all these procedures we are working with elliptic curve (EC) groups over Z_p where p is a prime number larger than 3.# # An Elliptic Curve group will be represented by a triple [A,B,p] where # # (1) p is a prime number larger than 3 # # (2) A is the coefficient of x and # # (3) B is the constant term in y^2 = x^3 + A*x + B mod p. # # # # The legendre attack procedure "KeyDiscoverNew" below assumes that the key is 40 bits and uses at least 8 signatures. # # # ############################################################################################################################ def NewLegendre(a,p): if is_prime(p): return (1+kronecker(a,p))/2 else: print "Second Parameter Must Be Prime" def BlockNumberNew(y,primelist): m=0 for j in xrange(3): m=2*m + NewLegendre(y,primelist[5+j]) return m+1 def BlockContentsNew(y,primelist): k=0 for j in xrange(5): k=10*k+NewLegendre(y,primelist[j]) return k def KeyDiscoverNew(ylist,primelist): c=10^5 k=0 for j in xrange(8): d = 8-BlockNumberNew(ylist[j],primelist) k = k+(BlockContentsNew(ylist[j],primelist))*(c^d) return Integer("0b"+str(k))