SharedFermat Attack.sagewsOpen in CoCalc
Authors: Liljana Babinkostova, Charles Burnell
Views : 23

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)

Example. One case where the fermat attack finds one of prime factors in one round

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

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

n=5502178753279631187249744419074900728448775696662176319670240394119468798083499 FermatAttack(n,100000)
Factor found in round 5329 2345672345678234577823456782345678345893L