Contact
CoCalc Logo Icon
StoreFeaturesDocsShareSupport News AboutSign UpSign In
| Download
Views: 129
import itertools 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 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 ECTimes(Point, scalar, Group): ECIdentity = [] if Point == ECIdentity or scalar == 0: return ECIdentity else: m = scalar pt = Point x = ECIdentity for j in itertools.count(0): if m==0: return x if m%2==0: m = m/2 else: m = (m-1)/2 x = ECAdd(x,pt,Group) pt = ECDouble(pt,Group)
import itertools def ECWiener(R,n): M=10101 b = (1^2-M^3)%R #ElCurve = EllipticCurve(GF(R),[0,b]) gp = [0,b,R] pt = [M,1] E = ECTimes(pt,n,gp) r = R+2*((sqrt(R)).round())+1 cf = continued_fraction(r/n) #print r #print n #print cf m = len(cf) for i in itertools.count(0): if i == m-1: return "Private key not found" t = cf.numerator(i) #print t d = ECTimes(E,t,gp) #print d if (d==pt): print "k = {0}".format(cf.denominator(i)) print "psi(R) = {0}".format((n*t-1)/cf.denominator(i)) return t
R=15639961278698218473530392300582786774108917982448006736774837569008287550230304206305840443056254615691224908372717706929499950940639004252733723 n=10556735581291623648875456039593886265875583839137300899929464171237397429797041290698083323563146300426021808634769915501312781888366432317464461 ECWiener(R,n)
k = 15643751481774109137150683750085 psi(R) = 15639961278698218473530392300582786774108917982448006736774837569008287782615271423955021482167689793355435470544281318039195098203104930067920088 23176451237645728113645123785821
(13/17).continued_fraction_list() len(continued_fraction(13/17))
[0, 1, 3, 4] 4