Category: Crypto
Points: 70
Description: The year is 20XX. ångstromCTF only has pwn challenges, and the winner is solely determined by who can establish a socket connection first. In the data remnants of an ancient hard disk, we’ve recovered a string of letters and digits. The only clue is the etching on the disk’s surface: Paillier.

Cool so for this challenge we are given the following values:

n: 99157116611790833573985267443453374677300242114595736901854871276546481648883
g: 99157116611790833573985267443453374677300242114595736901854871276546481648884
c: 2433283484328067719826123652791700922735828879195114568755579061061723786565164234075183183699826399799223318790711772573290060335232568738641793425546869

And the hint of Paillier. Googling that came up with a crypto system which is super similar to RSA check out

So from there since n is very small I used factordb to get p and q out of it which then can be used to generate the private key. Then from there I was able to decrypt the cipher text c. See the code below which basically just follows the steps for key generation and the decryption.

def gcd(a,b): # helper function to calculate the greatest common denominator
    """Compute the greatest common divisor of a and b"""
    while b > 0:
        a, b = b, a % b
    return a
def lcm(a, b): #lowest common multiple
    """Compute the lowest common multiple of a and b"""
    return a * b / gcd(a, b)

def L_func(x, n): # L function which is defined in the wiki
    return (x - 1) / n

def egcd(a, b): # euler greatest common denominator
    if a == 0:
        return (b, 0, 1)
        g, y, x = egcd(b % a, a)
        return (g, x - (b // a) * y, y)

def modinv(a, m): #modular inverse
    g, x, y = egcd(a, m)
    if g != 1:
        raise Exception('modular inverse does not exist')
        return x % m
def int2Text(number, size): # able to convert the int output to a string we can read
    text = "".join([chr((number >> j) & 0xff)
                    for j in reversed(range(0, size << 3, 8))])
    return text.lstrip("\x00")

p = 310013024566643256138761337388255591613 #from factor db
q = 319848228152346890121384041219876391791

g= 99157116611790833573985267443453374677300242114595736901854871276546481648884 #from the challenge
c= 2433283484328067719826123652791700922735828879195114568755579061061723786565164234075183183699826399799223318790711772573290060335232568738641793425546869

n = p * q #calculate n again

lamb = lcm(p - 1, q -1) #calculate the lambda value from the wiki

l_value =  L_func(pow(g, lamb, n*n), n)  # calculate the output of the L function which is defined in the wiki
u = modinv(l_value, n) # calculate u

m = (L_func(pow(c, lamb, n*n), n) * u) % n  # decrypt the cipher text now knowing u
print(int2Text(m, 100)) # print to readable text

Running this function will give us the flag



Leave a Reply

Your email address will not be published. Required fields are marked *