Contact
CoCalc Logo Icon
StoreFeaturesDocsShareSupport News AboutSign UpSign In
| Download
Views: 1859
%html <h1><center>Fermat Attack</center></h1>

Fermat Attack

Description. This attack takes advantage of the difference of squares theorem. If the two primes used for RSA are close together it will be able to produce one of the primes as an output. This algorithm is deterministic meaning it will find a solution but is efficent only if the difference of the primes is small

############################################################################################## # isqurt takes in an integer as input and produces the floor of the square root of the number# ############################################################################################## def isqrt(n): return int(floor(sqrt(n))) ############################################################################################## # usqrt takes in a number and produces the celing of the square root of the number # ############################################################################################## def usqrt (n): ur = isqrt(n) if ur ** 2 < n: ur = ur + 1 return(ur) ############################################################################################### # Fremat Attack takes in input of a composite number and how many rounds the user wants to run# # Using difference of squares it will produce one of the primes or will excede the number of # # rounds and terminate # ############################################################################################### def FermatAttack (n, rounds): st = usqrt(n) for x in range(st, st + rounds + 1): #print (x-st) sq = x ** 2 - n y = isqrt(sq) if y ** 2 == sq: print "Factor found in round {0}".format(x-st+1) return(x + y) print "No factor found in {0} rounds".format(rounds)
%md <b>Example.</b> One case where the fermat attack should find the correct prime in one round

Example. One case where the fermat attack should find the correct prime in one round

n = 392978654845729289907021754452182325881346071758898433529538362675031664460938682805318112640661164293937049338385443383663702038544055748284664168992544981428408893033338462355487676707091259638157494641830935147650581928069288556483290429263378443463703 print "n is " ,n p=FermatAttack(n,10) print "one of the primes is", p q=n/p print "the other prime is ", q
n is 392978654845729289907021754452182325881346071758898433529538362675031664460938682805318112640661164293937049338385443383663702038544055748284664168992544981428408893033338462355487676707091259638157494641830935147650581928069288556483290429263378443463703 Factor found in round 1 one of the primes is 19823689233987938247938274983309283029130218032845987439578439857389275997598441027803118841872484057442928728490226128152255489 the other prime is 19823689233987938247938274983309283029130218032845987439578439857389275987598437592345678984375000100012345678909876543216789527

Example. One case where the fermat attack will find one of the primes after about 5000 rounds

p = next_prime(2345672345678234567823456782345678345678) q = next_prime(2345672345678234577823456782345678345678) n = p*q FermatAttack(n,100000)
Factor found in round 5329 2345672345678234577823456782345678345893L