Fermat Attack.sagews

Fermat Attack

Description. This attack takes advantage of the difference of squares theorem. If the two primes used for RSA (or KMOV) 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. The second input "rounds" is a positive number that the user chooses  #
###############################################################################################
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", (x-st+1))
            return(x + y)
    print ("No factor found in rounds", (rounds))

Example. This is an example where Fermat Attack factors

n=392978654845729289907021754452182325881346071758898433529538362675031664460938682805318112640661164293937049338385443383663702038544055748284664168992544981428408893033338462355487676707091259638157494641830935147650581928069288556483290429263378443463703

in one round.

n = 392978654845729289907021754452182325881346071758898433529538362675031664460938682805318112640661164293937049338385443383663702038544055748284664168992544981428408893033338462355487676707091259638157494641830935147650581928069288556483290429263378443463703
print("The modulus is " ,n)
p=FermatAttack(n,10)

print("One of the prime factors is", p)
q=n/p
print("The other prime factor is ", q)

The modulus is 392978654845729289907021754452182325881346071758898433529538362675031664460938682805318112640661164293937049338385443383663702038544055748284664168992544981428408893033338462355487676707091259638157494641830935147650581928069288556483290429263378443463703 Factor found in round 1 One of the prime factors is 19823689233987938247938274983309283029130218032845987439578439857389275997598441027803118841872484057442928728490226128152255489 The other prime factor is 19823689233987938247938274983309283029130218032845987439578439857389275987598437592345678984375000100012345678909876543216789527

Example. This is an example where Fermat Attack factors n=5502178753279631187249744419074900728448775696662176319670240394119468798083499 in over 5000 rounds.

n=5502178753279631187249744419074900728448775696662176319670240394119468798083499
p=FermatAttack(n,100000)
p

Factor found in round 5329 2345672345678234577823456782345678345893