Contact
CoCalc Logo Icon
StoreFeaturesDocsShareSupport News AboutSign UpSign In
| Download
Views: 245
import numpy import itertools import sympy.ntheory ############################################################################################################################ # 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 FermatGreat (N): if sympy.ntheory.isprime(N): if N % 4 == 1: Z = two_squares(N) return(Z) else: print("{0} is prime, but {1} mod 4 = 3").format(N, N) else: print("{0} is not prime\n").format(N) 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.
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])
EXAMPLE: Find a point on the elliptic curve y2=x3+2x+14  mod  1291y^2=x^3+2x+14\;mod\; 1291 such that the first coordinate of the point is between (234,789).
P=ECSearch(234,789,[2,14,1291]) P Q=ECSearch(345,891,[2,14,1291]) Q
[236, 1131] [346, 749]
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)
EXAMPLE: Find the sum of the points (236, 1131) and (346, 749) on the elliptic curve y2=x3+2x+14  mod  1291y^2=x^3+2x+14\;mod\; 1291.
ECAdd([236,1131],[346,749],[2,14,1291])
Error in lines 1-1 Traceback (most recent call last): File "/cocalc/lib/python3.10/site-packages/smc_sagews/sage_server.py", line 1244, in execute exec( File "", line 1, in <module> NameError: name 'ECAdd' is not defined
ECDouble is a procedure that computes the sum of a point to itself on a given elliptic curve using the elliptic curve operation.
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)
EXAMPLE: Find the sum of the point (6,9) to itself i.e. 2(6,9)2\cdot(6,9) on the curve y2=x3+x+2  mod  13y^2=x^3+x+2\;mod\; 13.
ECDouble([6,9],[1,2,13])
[2, 8]
ECInverse is a procedure that finds the inverse of a point on a given elliptic curve using the elliptic curve operation.
def ECInverse (Point, Group): if Point == []: return(Point) else: p = Group[2] x = Point[0] y = Point[1] return([x,(p - y) % p])
EXAMPLE: Find an inverse of the point (6,9) on the curve y2=x3+x+2  mod  13y^2=x^3+x+2\;mod\; 13.
ECInverse([6,9],[1,2,13])
Error in lines 1-1 Traceback (most recent call last): File "/cocalc/lib/python3.10/site-packages/smc_sagews/sage_server.py", line 1244, in execute exec( File "", line 1, in <module> NameError: name 'ECInverse' is not defined
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]])
EXAMPLE: Add the point (6,9) to itself 1234 times on the curve y2=x3+x+2  mod  13y^2=x^3+x+2\;mod\; 13.
ECTimes([6,9],1234, [1,2,13])
[2, 5]
The procedure findptOrder computes order of an elliptic curve point P. The command for computing order of an elliptic curve group E in SageMath is E.order( ) or E.cardinality( ).
def findptOrder(point,group): E = EllipticCurve(GF(group[2]),[group[0],group[1]]) Ep = E(point[0],point[1]) return Ep.additive_order()

Hellman - Pohlig - Silver Attack for Solving DLP in Elliptic Curves

def listproduct (primelist): x = primelist k = len(primelist) result = 1 for i in range(0, k): result = result * x[i][0] ^ x[i][1] return(result) def listptorder (pt, Group, factoredGpOrder): ECIdentity = [] x = factoredGpOrder k = len(factoredGpOrder) orderlist = [] result = listproduct(factoredGpOrder) for i in range(0, k ): p = x[i][0] a = x[i][1] 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.append([p,ord]) returnlist = [] return orderlist def primeHPSonEC (y,g,Group,p): newg = [] for j in itertools.count(0): if y == newg: break newg = ECAdd(newg, g, Group) return(j) def powerHPSonEC (y,g,og,p,a,Group): gp = ECTimes(g, ZZ(og / p), Group) newog = og newy = y c = 0 partx = 0 for i in range(0, a ): newy = ECAdd(y, ECInverse(ECTimes(g, partx, Group), Group), Group) newog = ZZ(newog / p) ypower = ECTimes(newy, newog, Group) c = primeHPSonEC(ypower, gp, Group, p) partx = partx + c * p ** i return(partx) def HPSonEC (y,g,Group,factoredGpOrder): X = 0 Ord = 1 K = listptorder(g, Group, factoredGpOrder) k = len(K) ordg = listproduct(K) for j in range(0, k): p = K[j][0] powerp = K[j][1] partx = powerHPSonEC(y, g, ordg, p, powerp, Group) if j == 0: X = partx Ord = p ** powerp else: X = crt([X,partx], [Ord,p ^ powerp]) Ord = Ord * (p ^ powerp) return(X)

Strategy For Generating a Key Resistant Against Hellman Pohlig Silver Attack

######################################################## # dconstruct43 generates a prime p with p mod 4 =3 # ######################################################## def dconstruct43(q): counter = 1 while True: p=4*counter*q-1 if is_prime(p): return p counter=counter+1 ######################################################## # dconstruct32 generates a prime p with p mod 3 =2 # ######################################################## def dconstruct32(q): counter = 1 while True: p=6*counter*q-1 if is_prime(p): return p counter=counter+1
STEP 1.

Use deconstruct43 or dconstruct32 to generate a prime number p with p mod 4= 3 or p mod 3=2.

q = next_prime(3874239847893574935648569238401298308092098409384893758746584597328048209893478584765843643092839) p = dconstruct43(q) print ("Prime number p=", p) D=factor(p+1) print("p + 1=",D)
Prime number p= 867829725928160785585279509401890821012630043702216201959234949801482799016139202987548976052812063 p + 1= 2^5 * 7 * 3874239847893574935648569238401298308092098409384893758746584597328048209893478584765843643092911
STEP 2.

Generate an elliptic curve over the field of prime order defined in STEP 1.

A = 387468734627 B = 0 Group=[A,B,p] print("The eliptic curve group is", Group) E = EllipticCurve(GF(p),[A,B]) Gord=factor(E.order()) print("The factorization of the elliptic curve order is\n",Gord)
The eliptic curve group is [387468734627, 0, 867829725928160785585279509401890821012630043702216201959234949801482799016139202987548976052812063] The factorization of the elliptic curve order is 2^5 * 7 * 3874239847893574935648569238401298308092098409384893758746584597328048209893478584765843643092911
STEP 3.

Generate a point on the elliptic curve group such that the factorization of the point order contains the largest prime factor of the elliptic group order generated in STEP 2.

counter = 1 while True: P1 = ECSearch(counter,8932748937487364873657643875,Group) ord = findptOrder(P1,Group) if mod(ord,3874239847893574935648569238401298308092098409384893758746584597328048209893478584765843643092911)==0: break counter = P1[0]+1 P=P1 print("The elliptic curve point is",P) ############################################################################################### # Note that the inputs in the function listptorder are specific to the curve chosen in Step 2 # ############################################################################################### PointOrd=findptOrder(P, Group) F=factor(PointOrd) print("The factorization of the point order is",F)
The elliptic curve point is [2, 135152431609326694924981469320792005678635933446762766073401432337425622094946893492512392099836798] The factorization of the point order is 2^4 * 3874239847893574935648569238401298308092098409384893758746584597328048209893478584765843643092911
STEP 3.

Use the Chinese Remainder Theorem (CRT) to generate the private key. The number of coefficients CiC_i chosen for the CRT is the same as the number of factors of the point order.

C1=0 ########################################################################################### # C0 is always chosen as the difference of the "largest factor of point order" and 1 # ########################################################################################### C0=3874239847893574935648569238401298308092098409384893758746584597328048209893478584765843643092911 - 1 x=crt([0,C0],[2^4, 3874239847893574935648569238401298308092098409384893758746584597328048209893478584765843643092911]) print("The private key x=", x)
The private key x= 58113597718403624034728538576019474621381476140773406381198768959920723148402178771487654646393664
REMARK.
Note that xx modulo the largest prime factor of point order is a large number. This implies that the private key xx generated in STEP 3 is resistant again Hellman Pohlig Silver attack.
mod(x, 2^4) mod(x, 3874239847893574935648569238401298308092098409384893758746584597328048209893478584765843643092911)
Error in lines 1-1 Traceback (most recent call last): File "sage/symbolic/expression.pyx", line 1513, in sage.symbolic.expression.Expression._integer_ n = self.pyobject() File "sage/symbolic/expression.pyx", line 774, in sage.symbolic.expression.Expression.pyobject raise TypeError("self must be a numeric expression") TypeError: self must be a numeric expression During handling of the above exception, another exception occurred: Traceback (most recent call last): File "sage/rings/finite_rings/integer_mod.pyx", line 380, in sage.rings.finite_rings.integer_mod.IntegerMod_abstract.__init__ z = integer_ring.Z(value) File "sage/structure/parent.pyx", line 897, in sage.structure.parent.Parent.__call__ return mor._call_(x) File "sage/structure/coerce_maps.pyx", line 287, in sage.structure.coerce_maps.NamedConvertMap._call_ cdef Element e = method(C) File "sage/symbolic/expression.pyx", line 1515, in sage.symbolic.expression.Expression._integer_ raise TypeError("unable to convert %r to an integer" % self) TypeError: unable to convert x to an integer During handling of the above exception, another exception occurred: Traceback (most recent call last): File "/cocalc/lib/python3.10/site-packages/smc_sagews/sage_server.py", line 1244, in execute exec( File "", line 1, in <module> File "sage/rings/finite_rings/integer_mod.pyx", line 156, in sage.rings.finite_rings.integer_mod.Mod return IntegerMod(parent, n) File "sage/rings/finite_rings/integer_mod.pyx", line 201, in sage.rings.finite_rings.integer_mod.IntegerMod return t(parent, value) File "sage/rings/finite_rings/integer_mod.pyx", line 384, in sage.rings.finite_rings.integer_mod.IntegerMod_abstract.__init__ value = value.pyobject() File "sage/symbolic/expression.pyx", line 715, in sage.symbolic.expression.Expression.pyobject cpdef object pyobject(self): File "sage/symbolic/expression.pyx", line 774, in sage.symbolic.expression.Expression.pyobject raise TypeError("self must be a numeric expression") TypeError: self must be a numeric expression