Contact
CoCalc Logo Icon
StoreFeaturesDocsShareSupport News AboutSign UpSign In
| Download
Views: 253
%latex FERMAT FAC 5d8d6164-f431-42ea-9aed-fa9dad2595dcs︠ import numpy import itertools def ASCIIPad(Message,p): K = (map(ord,reversed(Message))); #print(K); le= len(K); #print(le); x = [100+K[i] for i in range(le)]; x = ZZ(x,1000); return([x]); def ASCIIDepad(Number): N = ""; Number = ZZ(Number[0]) n = Number.ndigits() % 3; if (n > 0): print("This is not a padded ASCII string\n"); else: L = [((Number - (Number % (1000^i)))/1000^i)%1000 - 100 for i in range(Number.ndigits()/3)]; for i in range(Number.ndigits()/3): N = chr(L[i]) + N; return(N); def ECRAdd(Point1,Point2,Group): a = Group[0] b = Group[1] p = Group[2] #print Point2 if Point1!=[]: x1 = Point1[0] y1 = Point1[1] if Point2!=[]: x2 = Point2[0] y2 = Point2[1] if ZZ(mod(4*a^3 + 27*b^2, p)) == 0: print "This is not an ellitpic curve" elif Point1!=[] and ZZ(mod(y1^2, p)) != ZZ(mod(x1^3 + a*x1 + b,p)): print "Point 1 is not on the elliptic curve." elif Point2!=[] and ZZ(mod(y2^2, p)) != ZZ(mod(x2^3 + a*x2 + b,p)): print "Point 2 is not on the elliptic curve." else: if Point1==[]: R=Point2 elif Point2=={}: R=Point1 else: if x1==x2 and 0==ZZ(mod(y1+y2,p)): R=[] elif x1==x2 and y1==y2: R=ECRDouble(Point1,Group) if R==True: return(True) else: g=gcd(x1-x2,p) if (g>1): print "factor is {0}".format(g) return(True) s=ZZ(mod((y1-y2)/(x1-x2),p)) x=ZZ(mod(s^2-(x1+x2),p)) y=ZZ(mod(s*(x1-x)-y1,p)) R=[x,y] return R
def ECRDouble(Point,Group): a = Group[0] b = Group[1] p = Group[2] if Point!=[]: x1 = Point[0] y1 = Point[1] if ZZ(mod(4*a^3 + 27*b^2, p)) == 0: print "This is not an ellptic curve" elif Point!= [] and ZZ(mod(y1^2,p))!= ZZ(mod(x1^3+a*x1+b,p)): print "point to double not on elliptic curve" elif y1==0: R=[] else: g = gcd(y1,p) if g>1: print "Factor is {0}".format(g) return True s = ZZ(mod((3*x1^2+a)/(2*y1),p)) x = ZZ(mod(s^2-(x1+x1),p)) y = ZZ(mod(s*(x1-x)-y1,p)) R = [x,y] else: R=[] return R
def ECRTimes(Point,scalar,Group): ECIDENTITY = [] if Point==ECIDENTITY or scalar ==0: return ECIDENTITY else: m = scalar pt = Point x = ECIDENTITY #for j in xrange(1,scalar+1): j=1 while j<(scalar +1): if m%2==0: m = m/2 else: m=(m-1)/2 x=ECRAdd(x,pt,Group) if x==True: return true if m==0: return x pt = ECRDouble(pt,Group) if pt==True: return true j+=1 def isqrt(n): return int(floor(sqrt(n))) def usqrt (n): ur = isqrt(n) if ur ** 2 < n: ur = ur + 1 return(ur) def FermatAttack (n, rounds): st = usqrt(n) for x in range(st, st + rounds + 1): sq = x ** 2 - n y = isqrt(sq) if y ** 2 == sq: print "Factor found in round {0}".format(x - st +1) return ZZ(x+y) print "No factor found in {0} rounds".format(rounds) def ISAttack (R): R = ZZ(R) n = R.ndigits() #n = len(R) for j in range(1, n + 1): x=(R-(R % 10^j))/10^j p = gcd(x, R) if ((1 < p)and (p<R)): return(p) print "none found"
FermatAttack(17*43,89)
Factor found in round 3 43
p = next_prime(398793824793827498330928302913021803284598743957843985738927598759843759843750001) p p.ndigits() q = next_prime(p+100) q q.ndigits()
398793824793827498330928302913021803284598743957843985738927598759843759843750179 81 398793824793827498330928302913021803284598743957843985738927598759843759843750491 81
R=p*q R FermatAttack(R,1000)
159036514693689983941651127883368586201655747927706116369962006335777320438442666570787646792828597134996921334192059514888059653595070079977594119733157812587889 Factor found in round 1 398793824793827498330928302913021803284598743957843985738927598759843759843750491
#Alice R1=848061823138803033956535537084928083694225574017227239202042915523318741451772313173490442338601595465454540997822653451 n1=709 #Bob ############ p=8032675150754975402362507257235803770180658067882476519228035175990199 R2=37885653684248267190426624311372117301484717973748532033600889660841894907640421540658926740364534314366072725823598644840289412835528887169677 n2=next_prime(456) #Charlene ########### p=8032675150754975402362507257235803770180658067882476519228035175990199 R3=2224123957689421255759858997418551440089355215540010333196853340059721875420737855562885580039905848944140463948466814256698260955991 n3=719 #Daryl Factor found in round 616 ########## p=309742867231360502542308382200288243484059808679848559789801707 R4=95940643800704219789558456337945182311302224923094312522638008322538251917593808188643649492422122515432514556759166706562323 n4=727 #Elena ############ p=7129751218963441260363864753127960488586058483691117069949 R5=3675845370677380684776022610559668088370019789885420589924951014740511233928486180364454306991800313968665218025373476769753 n5=733 #Francis Factor found in round 255 ########## p=749340807728335795394301261630714438439971018875237969485940753 R6=561511646126954714905978212034679745347598508166104333032020503455906363658719694396251647443630223158626762164262057674226523 n6=739 #Gina R7=313081420184512798869781203931181362634178747735658266438007633482746731351580434146412286114362239508674326489068271151203 n7=743
mess1="Public-Key Schemes" mess2="Elliptic Curves!" mess3="Quantum Attacks" mess4="Security Analysis" mess5="Homomorphic Encryption" m3=ASCIIPad(mess1,R3) m6=ASCIIPad(mess2,R6) m5=ASCIIPad(mess3,R5) m2=ASCIIPad(mess4,R2) m4=ASCIIPad(mess5,R4) g3=[m3[0],1] b3=(1-m3[0]^3) % R3 G3=[0,b3,R3] c3=ECRTimes(g3,n3,G3) c3
[903751773819117092776133148846534798908228375708877333461110601109316847730497868328317534538935446906432884060813920793266175819022, 1610878290002749032825519637062887147827238164237317445567306841894365762413353448106958520494103725199437234970214053816262122599737]
g6=[m6[0],1] b6=(1-m6[0]^3) % R6 G6=[0,b6,R6] c6=ECRTimes(g6,n6,G6) c6
[203169609070781589091548230947637948443856772199857387229742687552770006654774545907210478119329523874134735545324155181857196, 217867352448565786731834655580531870159795701507641854494832096647950398294184079606169853980988873917310444721531802796360725]
g5=[m5[0],1] b5=(1-m5[0]^3) % R5 G5=[0,b5,R5] c5=ECRTimes(g5,n5,G5) c5
[1658343880752580269608441259639895348925093364626787618057372216175762429185576818264069652362099639487798352756776958858586, 2507780195529465690341053392414250212557056716596864009384576903864915253478720474510383147361895193719355015810430457281133]
g2=[m2[0],1] b2=(1-m2[0]^3) % R2 G2=[0,b2,R2] c2=ECRTimes(g2,n2,G2) c2
[13164160182828613275165894041640152771198051533917555532934255903546160955170555011540766782955066837153541926543022305770526456933552863223922, 24822757663801944716829792903969006156022515226631401151713552016115624518081558819626697581528286117888582908325012474813497169595210967261974]
g4=[m4[0],1] b4=(1-m4[0]^3) % R4 G4=[0,b4,R4] c4=ECRTimes(g4,n4,G4) c4
[50101932502269002569116180311341789312626993850274203520998558665416932522571247912833873398509823939843105723466693847516154, 15096386482371661862720119225138478240197419947566728389837905694416937739753713428978280757196946739343231830457983316672789]