redpwnCTF 2020 Crypto

primimity

This challenges gives us the n and e in a RSA encryption. And it tells us that n consists of 3 1024-bit primes. In this case, we probably can't factor n with Crypto tools and by checking factordb, there is no entry of n. So we need to start from the prime-generation python script.

The Script

def prime_gen():
    i = getRandomNBitInteger(1024)
    d = getRandomNBitInteger(8)
    for _ in range(d):
        i = find_next_prime(i)
    p = find_next_prime(i)
    d = getRandomNBitInteger(8)
    for _ in range(d):
        i = find_next_prime(i)
    q = find_next_prime(i)
    d = getRandomNBitInteger(8)
    for _ in range(d):
        i = find_next_prime(i)
    r = find_next_prime(i)
    return (p,q,r)

this is the prime generation function of the script and we can see how it works. First in generates a random 1024 bit integer to form the base of the random generation. Then for three primes, it generates an 8 bit integer and finds the next_integer after the 1024 base integer that many times.
What can we spot here? Like the name suggests, I kind of get of sense of "proximity". This is because all three primes are generated base off one 1024 bit random integer, and the only thing that's different between the three primes are how many times next_prime is called. An 8 bit integer can be 0-255 which is not that much. So the biggest gap between each prime is 255 primes away.

The Exploit

By knowing that these primes are close to each other, we could just write something that goes around the cube root of n and check each prime around the range of +-255 primes. This is tedious work so I wrote a script to handle that. We check each prime by n%found_prime == 0 and it's a factor of n, we found a factor of n. Notice we only need 2 out of 3 primes to find all of them. In my case, I was only able to get 2 primes, but that gives me the third one as well.We know that one is above the cube root and one is below, we could just find the third one by division.

curr = # Cube root of n, skiped to save space
for x in range(300):
    curr=find_prev_prime(curr)
    posible.append(curr)

curr = # Cube root of n, skiped to save space
for x in range(300):
    curr=find_next_prime(curr)
    posible.append(curr)

ans=[]
for x in posible:
    if(n%x==0):
        ans.append(x)

curr = # Cube root of n, skiped to save space
for x in range(curr,n):
    if(new*x==n):
        ans.append(x)
        break

curr = # Cube root of n, skiped to save space
for x in range(curr,n,-1):
    if(new*x==n):
        ans.append(x)
        break
print(ans)

I modified the find_next_prime function to find the previous prime so that we get a range of +-256. Then we just wait for the primes to get calculated.

The Flag

Finally, we get the three primes we could just do our regular RSA decryption by finding the totient and the modular inverse of e and phi

from Crypto.Util.number import inverse
p,q,r=139926822890670655977195962770726941986198973494425759476822219188316377933161673759394901805855617939978281385708941597117531007973713846772205166659227214187622925135931456526921198848312215276630974951050306344412865900075089120689559331322162952820292429725303619113876104177529039691490258588465409208581,139926822890670655977195962770726941986198973494425759476822219188316377933161673759394901805855617939978281385708941597117531007973713846772205166659227214187622925135931456526921198848312215276630974951050306344412865900075089120689559331322162952820292429725303619113876104177529039691490258588465409397803,139926822890670655977195962770726941986198973494425759476822219188316377933161673759394901805855617939978281385708941597117531007973713846772205166659227214187622925135931456526921198848312215276630974951050306344412865900075089120689559331322162952820292429725303619113876104177529039691490258588465409494847
n=# Deleted to Save Space
e=65537
c= # Deleted to Save Space
phi = (p-1)*(q-1)*(r-1)
d=inverse(e,phi)
m=pow(c,d,n)
print(hex(m))