Factoring with Elliptic Curve Methods
[Primes Home][Home]
Several methods, such as RSA, can be cracked by factorizing integers. One method of factorizing values uses elliptic curve methods (ECMs).
|
We basically compute \(kP \pmod N\), and where \(k\) is a product of many small numbers, such as \(Z!\), and where we calculate one factor at a time. We could thus start with \(2P\), then use \(3(2P)\), and then \(4 (3!)P\), and then \(5 (4!)P\), and so on. The value of \(Z\) is selected, so that the calculations are efficient on the curve.
If we move from a point \(P\) to \(2P\), we find the tangent to the point \(P\) and use this to find \(2P\). This tangent will be defined with a slope (\(s\)) and with a gradient in the form of \(\frac{a}{b}\). For this we must find the modular inverse of \(b\). If we cannot find the modular inverse of \(b\), a factor of \(N\) is \(gcd(N,b)\).
If our curve is \(y^2 = x^3 + ax + b\), the slope (\(s\)) will be:
\(s = \frac{3x^2+a}{2y}\)
This is defined with differentiation.
In detail, we first pick a random point \(P=(x_0,y_0)\) on an elliptic curve of:
\(y^2 = x^3 + Ax + B\)
We also select a random value of \(A\) and then calculate:
\(B = y_0^2 - x_0^3 - Ax \pmod{N} \)
For two points on the curve: \(P = (P_x, P_y)\) and \(Q = (Q_x, Q_y)\), the slope of the line between them will be:
\(s = \frac{(P_y - Q_y)}{(P_x - Q_x)}\)
With this we have \(s\) in the form of \(\frac{a}{b} \pmod N\).
Next we define:
\(R = P + Q = (R_x, - R_y)\)
and using:
\(s=\frac{(P_x-Q_x)}{(P_y-Q_y)} \pmod N\)
\(R_x=s^2-P_x-Q_x \pmod N\)
\(R_y=P_y+s(R_x-P_x) \pmod N\)
If \(P_x = Q_x\) and \(P_y = -Q_y\), we define as 0 [Identity], else we calculate \(R = P + P = 2P = (R_x, -R_y)\):
\(s=\frac{3P_x^2+A}{2P_y} \pmod N\)
\(R_x=s^2-2P_x \pmod N\)
\(R_y=P+s(R_x-P_x) \pmod N\)
An outline of the code used is [code]:
#!/usr/local/bin/python # -*- coding: utf-8 -*- import math import random import sys #y^2=x^3+ax+b mod n prime=[2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 103, 107, 109, 113, 127, 131, 137, 139, 149, 151, 157, 163, 167, 173, 179, 181, 191, 193, 197, 199, 211, 223, 227, 229, 233, 239, 241, 251, 257, 263, 269, 271 ] # ax+by=gcd(a,b). This function returns [gcd(a,b),x,y]. Source Wikipedia def extended_gcd(a,b): x,y,lastx,lasty=0,1,1,0 while b!=0: q=a//b a,b=b,a%b x,lastx=(lastx-q*x,x) y,lasty=(lasty-q*y,y) if a<0: return (-a,-lastx,-lasty) else: return (a,lastx,lasty) # pick first a point P=(u,v) with random non-zero coordinates u,v (mod N), then pick a random non-zero A (mod N), # then take B = u^2 - v^3 - Ax (mod N). # http://en.wikipedia.org/wiki/Lenstra_elliptic_curve_factorization def randomCurve(N): A,u,v=random.randrange(N),random.randrange(N),random.randrange(N) B=(v*v-u*u*u-A*u) % N return [(A,B,N),(u,v)] # Given the curve y^2 = x^3 + ax + b over the field K (whose characteristic we assume to be neither 2 nor 3), and points # P = (xP, yP) and Q = (xQ, yQ) on the curve, assume first that xP != xQ. Let the slope of the line s = (yP - yQ)/(xP - xQ); since K # is a field, s is well-defined. Then we can define R = P + Q = (xR, - yR) by # s=(xP-xQ)/(yP-yQ) Mod N # xR=s^2-xP-xQ Mod N # yR=yP+s(xR-xP) Mod N # If xP = xQ, then there are two options: if yP = -yQ, including the case where yP = yQ = 0, then the sum is defined as 0[Identity]. # thus, the inverse of each point on the curve is found by reflecting it across the x-axis. If yP = yQ != 0, then R = P + P = 2P = # (xR, -yR) is given by # s=3xP^2+a/(2yP) Mod N # xR=s^2-2xP Mod N # yR=yP+s(xR-xP) Mod N # http://en.wikipedia.org/wiki/Elliptic_curve#The_group_law''') def addPoint(E,p_1,p_2): if p_1=="Identity": return [p_2,1] if p_2=="Identity": return [p_1,1] a,b,n=E (x_1,y_1)=p_1 (x_2,y_2)=p_2 x_1%=n y_1%=n x_2%=n y_2%=n if x_1 != x_2 : d,u,v=extended_gcd(x_1-x_2,n) s=((y_1-y_2)*u)%n x_3=(s*s-x_1-x_2)%n y_3=(-y_1-s*(x_3-x_1))%n else: if (y_1+y_2)%n==0:return ["Identity",1] else: d,u,v=extended_gcd(2*y_1,n) s=((3*x_1*x_1+a)*u)%n x_3=(s*s-2*x_1)%n y_3=(-y_1-s*(x_3-x_1))%n return [(x_3,y_3),d] # http://en.wikipedia.org/wiki/Elliptic_curve_point_multiplication # Q=0 [Identity element] # while m: # if (m is odd) Q+=P # P+=P # m/=2 # return Q') def mulPoint(E,P,m): Ret="Identity" d=1 while m!=0: if m%2!=0: Ret,d=addPoint(E,Ret,P) if d!=1 : return [Ret,d] # as soon as i got anything otherthan 1 return P,d=addPoint(E,P,P) if d!=1 : return [Ret,d] m>>=1 return [Ret,d] def ellipticFactor(N,m,times=5): for i in range(times): E,P=randomCurve(N); Q,d=mulPoint(E,P,m) if d!=1 : return d return N first=True n=455832 if (len(sys.argv)>1): n=int(sys.argv[1]) print(n,'=', end=' ') for p in prime: while n%p==0: if (first==True): print(p, end=' ') first=False else: print('x',p, end=' ') n/=p m=int(math.factorial(2000)) while n!=1: k=int(ellipticFactor(n,m)) n=int(n//k) if (first==True): print(k, end=' ') first=False else: print('x',k, end=' ')