Factoring with Elliptic Curve Method
[Primes Home][Home]
Hendrik W. Lenstra Jr. became a Professor at the University of Amsterdam in 1979, and then, in 1987, he was appointed to the University of California, Berkeley. One of his most famous PhD students is Daniel J. Bernstein, who is famous for producing standards such as Curve 25119, ChaCha20 and Poly1305. In the year he was appointed to Berkley, he outlined a method to factorize integers using elliptic curve methods [1]. Several methods, such as RSA, can be cracked by factorizing integers. One method of factorizing values uses elliptic curve methods (ECMs) [article].
|
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]:
import random import hashlib import math 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 ] import sys from libnum import ecc mytype="P256" val=455832 if (len(sys.argv)>1): val=str(sys.argv[1]) if (len(sys.argv)>2): mytype=(sys.argv[2]) if (mytype=="secp256k1"): print ("secp256k1") a=0 b=7 G=(55066263022277343669578718895168534326250603453777594175500187360389116729240, 32670510020758816978083085130507043184471273380659243275938904335757337482424) p=115792089237316195423570985008687907853269984665640564039457584007908834671663 n=115792089237316195423570985008687907852837564279074904382605163141518161494337 elif (mytype=="Curve25519"): print ("Curve 25519 - Weierstrass") a=19298681539552699237261830834781317975544997444273427339909597334573241639236 b=55751746669818908907645289078257140818241103727901012315294400837956729358436 G=(19298681539552699237261830834781317975544997444273427339909597334652188435546, 14781619447589544791020593568409986887264606134616475288964881837755586237401) p=pow(2,255)-19 n=7237005577332262213973186563042994240857116359379907606001950938285454250989 elif (mytype=="P192"): print ("P192") a=-3 b=18958286285566608000408668544493926415504680968679321075787234672564 G=(19277929113566293071110308034699488026831934219452440156649784352033, 19926808758034470970197974370888749184205991990603949537637343198772) p=26959946667150639794667015087019630673557916260026308143510066298881 n=6277101735386680763835789423176059013767194773182842284081 elif (mytype=="P512"): print ("P512") a=-3 b=1093849038073734274511112390766805569936207598951683748994586394495953116150735016013708737573759623248592132296706313309438452531591012912142327488478985984 G=(2661740802050217063228768716723360960729859168756973147706671368418802944996427808491545080627771902352094241225065558662157113545570916814161637315895999846, 3757180025770020463545507224491183603594455134769762486694567779615544477440556316691234405012945539562144444537289428522585666729196580810124344277578376784) p=6864797660130609714981900799081393217269435300143305409394463459185543183397656052122559640661454554977296311391480858037121987999716643812574028291115057151 n=0x000001fffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffa51868783bf2f966b7fcc0148f709a5d03bb5c9b8899c47aebb6fb71e91386409 elif (mytype=="P256"): print ("P256") a=-3 b=41058363725152142129326129780047268409114441015993725554835256314039467401291 G=(48439561293906451759052585252797914202762949526041747995844080717082404635286, 36134250956749795798585127919587881956611106672985015071877198253568414405109) p=115792089210356248762697446949407573530086143415290314195533631308867097853951 n=115792089210356248762697446949407573529996955224135760342422259061068512044369 elif (mytype=="P224"): print ("P224") a=-3 b=18958286285566608000408668544493926415504680968679321075787234672564 G=(19277929113566293071110308034699488026831934219452440156649784352033, 19926808758034470970197974370888749184205991990603949537637343198772) p=26959946667150639794667015087019630673557916260026308143510066298881 n=26959946667150639794667015087019625940457807714424391721682722368061 elif (mytype=="P384"): print ("P384") a=-3 b=27580193559959705877849011840389048093056905856361568521428707301988689241309860865136260764883745107765439761230575 G=(26247035095799689268623156744566981891852923491109213387815615900925518854738050089022388053975719786650872476732087, 8325710961489029985546751289520108179287853048861315594709205902480503199884419224438643760392947333078086511627871) p=39402006196394479212279040100143613805079739270465446667948293404245721771496870329047266088258938001861606973112319 n=0xffffffffffffffffffffffffffffffffffffffffffffffffc7634d81f4372ddf581a0db248b0a77aecec196accc52973 elif (mytype=="secp160r2"): print ("secp160r2") a=1461501637330902918203684832716283019651637554288 b=1032640608390511495214075079957864673410201913530 G=(0x52dcb034293a117e1f4ff11b30f7199d3144ce6d , 0xfeaffef2e331f296e071fa0df9982cfea7d43f2e) p=1461501637330902918203684832716283019651637554291 n=1461501637330902918203685083571792140653176136043 elif (mytype=="brainpoolP160r1"): print ("brainpoolP160r1") a=0x340E7BE2A280EB74E2BE61BADA745D97E8F7C300 b=0x1E589A8595423412134FAA2DBDEC95C8D8675E58 G=(0xBED5AF16EA3F6A4F62938C4631EB5AF7BDBCDBC3, 0x1667CB477A1A8EC338F94741669C976316DA6321) p=0xE95E4A5F737059DC60DFC7AD95B3D8139515620F n=0xE95E4A5F737059DC60DF5991D45029409E60FC09 elif (mytype=="brainpoolP192r1"): print ("brainpoolP192r1") a=0x6A91174076B1E0E19C39C031FE8685C1CAE040E5C69A28EF b=0x469A28EF7C28CCA3DC721D044F4496BCCA7EF4146FBF25C9 G=(0xC0A0647EAAB6A48753B033C56CB0F0900A2F5C4853375FD6, 0x14B690866ABD5BB88B5F4828C1490002E6773FA2FA299B8F) p=0xC302F41D932A36CDA7A3463093D18DB78FCE476DE1A86297 n=0xC302F41D932A36CDA7A3462F9E9E916B5BE8F1029AC4ACC1 elif (mytype=="brainpoolP224r1"): print ("brainpoolP224r1") a=0x68A5E62CA9CE6C1C299803A6C1530B514E182AD8B0042A59CAD29F43 b=0x2580F63CCFE44138870713B1A92369E33E2135D266DBB372386C400B G=(0x0D9029AD2C7E5CF4340823B2A87DC68C9E4CE3174C1E6EFDEE12C07D,0x58AA56F772C0726F24C6B89E4ECDAC24354B9E99CAA3F6D3761402CD) p=0xD7C134AA264366862A18302575D1D787B09F075797DA89F57EC8C0FF n=0xD7C134AA264366862A18302575D0FB98D116BC4B6DDEBCA3A5A7939F elif (mytype=="brainpoolP256r1"): print ("brainpoolP256r1") a=0x7D5A0975FC2C3057EEF67530417AFFE7FB8055C126DC5C6CE94A4B44F330B5D9 b=0x26DC5C6CE94A4B44F330B5D9BBD77CBF958416295CF7E1CE6BCCDC18FF8C07B6 G=(0x8BD2AEB9CB7E57CB2C4B482FFC81B7AFB9DE27E1E3BD23C23A4453BD9ACE3262,0x547EF835C3DAC4FD97F8461A14611DC9C27745132DED8E545C1D54C72F046997) p=0xA9FB57DBA1EEA9BC3E660A909D838D726E3BF623D52620282013481D1F6E5377 n=0xA9FB57DBA1EEA9BC3E660A909D838D718C397AA3B561A6F7901E0E82974856A7 elif (mytype=="BN(2,254)"): print ("BN(2,254)") a=0 b=2 G=(1,2) p=0xfffffffffffcf0cd46e5f25eee71a49f0cdc65fb12980a82d3292ddbaed33013 n=0xfffffffffffcf0cd46e5f25eee71a49e0cdc65fb1299921af62d536cd10b500d else: print("Not supported") def extended_gcd(a,b): x,y,lastx,lasty=0,1,1,0 while b!=0:a 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) 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] 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)] 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 curve = ecc.Curve(a,b,p,G,order=n) print(f"N={val}=",end='') for p in prime: while val%p==0: if (first==True): print(p, end=' ') first=False else: print('x',p, end=' ') val//=p m=int(math.factorial(2000)) while val!=1: k=int(ellipticFactor(val,m)) val=int(val//k) if (first==True): print(k, end=' ') first=False else: print('x',k, end=' ')
A sample run:
P256 N=455832=2 x 2 x 2 x 3 x 3 x 13 x 487
[1] Lenstra Jr, H. W. (1987). Factoring integers with elliptic curves. Annals of mathematics, 649–673 [paper].