### Runes

**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 https://en.wikipedia.org/wiki/Paillier_cryptosystem

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)
else:
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')
else:
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

FLAG:

`actf{crypto_lives}`