Contact
CoCalc Logo Icon
StoreFeaturesDocsShareSupport News AboutSign UpSign In
| Download
Views: 499
Visibility: Unlisted (only visible to those who know the link)
Image: ubuntu2004

ELLIPTIC CURVE BABY STEP GIANT STEP

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 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 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 if kronecker(j ** 3 + a * j + b, p) == 1: x = (j ** 3 + a * j + b) % p var('z') L=TonSh(x,p) y = L 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] 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]]) EPoint = E(Point[0],Point[1]) cgret = scalar*EPoint if(cgret[0]==0 and cgret[1]==1 and cgret[2]==0): return ECIdentity return([cgret[0],cgret[1]]) import math
def GroupOrder(Group): E = EllipticCurve(GF(Group[2]),[Group[0],Group[1]]) return E.order() def ptorder (pt, Group, factoredGpOrder): ECIdentiy = EllipticCurve(GF(7),[0,2])(0,1,0) x = factoredGpOrder k = len(factoredGpOrder) result = listproduct(factoredGpOrder) for i in range(1, k + 1): p = x[i][0] #op(1, op(i, x)) a = x[i][1] #op(2, op(i, x)) for j in range(0, a): result = result / p test = ECTimes(pt, result, Group) if test != ECIdentity: result = result * p return(result) def listproduct (primelist): x = primelist k = len(primelist) result = 1 for i in range(0, k): result = result * x[i][0] ^ x[i][1] #op(1, op(i, x)) ** op(2, op(i, x)) return(result) def listptorder (pt, Group, factoredGpOrder): ECIdentity = [] x = factoredGpOrder k = len(factoredGpOrder) orderlist = set([]) result = listproduct(factoredGpOrder) for i in range(0, k ): p = x[i][0] #op(1, op(i, x)) a = x[i][1] #op(2, op(i, x)) ord = 0 for j in range(0, a ): try: result = ZZ(result / p) test = ECTimes(pt, result, Group) if test != ECIdentity: result = result * p ord = ord + 1 except: pass if 0 < ord: orderlist = orderlist | set([[p,ord]]) return(convert(orderlist, list))

Baby Step Giant Step Algorithm

Data Have group G and points P and Q. We must find any x such that Q = x*P
Step 1 Choose > squrt(grouporder)
Step 2 Baby steps: Computer list T_i = i*P for i =1,...,m
Step 3 Giant steps: Take m*P from last baby step and computer list R_j = Q-j*(m*P) for j = 1,...,m-1
Step 4 Compare 2 lists for coincidences T_i=R_j reveals a solution to Q = x*P as follows x = i+j*m mod grouporder
def BSGS (pt, Qt, gp): E = EllipticCurve(GF(gp[2]),[gp[0],gp[1]]) N = E.order() m = sqrt(N).round() + 1 BSL = [0]*(m+1) GSL = [0]*(m+1) BSL[0] = pt for j in range(1, m+1): BSL[j] = ECTimes(pt, j, gp) pt2 = BSL[m] GSL[0] = pt2 for j in range(1, m+1): GSL[j] = ECAdd(Qt, ECInverse(ECTimes(pt2, j, gp), gp), gp) for i in range(1, m+1 ): for j in range(1, m+1): if BSL[i] == GSL[j]: DL = (i + j * m) % N print ("Discrete log is {0}".format(DL)) return DL
p=next_prime(12111) A=0 B=4 G=[A,B,p] G ############################# Elliptic Curve Group n=GroupOrder(G) ############### The order of the elliptic curve group G P=[5, 7766] ################### Point on the elliptic curve group G Q=[10991, 10509] ############## Point on the elliptic curve group G BSGS(P,Q,G)
[0, 4, 12113] Discrete log is 25 25
ECTimes(P,25,G) ############# We test that the solution x=25 is correct i.e. xP = Q
[10991, 10509]