ISAttack.sagews

Initial Segment Attack

Description. The main idea of this attack is to compute the value $x=(R-(R \mod 10^j))/10^j$ for j=1, 2, ... k where k is the number of tdigits of the modulus R and each step to find gcd(x, R). The attack works if R is a product of two primes such that one of the primes has many consecutive zeros and the otheprime is relatively small.

####################################################################################################################################
# The ISAttack uses only one input - the modulus R. If successful, the function provides only one of the primes.                   #
####################################################################################################################################

def ISAttack (R):
    R = ZZ(R)
    n = R.ndigits()
    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("no factor found")

############################################
#                    EXAMPLE               #
############################################

R=580096039015263184152637189359470000000019641046990280564502805826096423
p=ISAttack(R)
print('p=',p)
print('q=',R/p)

p= 456768534657687546576879676661 q= 1270000000000000000000000000000000000000043

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 %d\n", x - st + 1)
            return(x + y)
    print("No factors found in %d \n", rounds)
n = 1380329510951197510100010724038844435804781490991185453524669
def ISAttack (R):
    R = ZZ(R)
    n = R.ndigits()
    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("no factor found")

#FermatAttack(n, 100000)

n
factor(n)
#ISAttack(n)

1380329510951197510100010724038844435804781490991185453524669 678313966378204911693968634971 * 2034941899134614735081905904839