Rating: 0
# Runes - 70 points - 234 solves
## Paillier cryptosytem
We are given numbers `n, g, c` and the hint *Paillier*. Googling for it, we discover the Paillier cryptosystem, which is based on the hardness of [decisional composite residuosity assumption](https://en.wikipedia.org/wiki/Decisional_composite_residuosity_assumption), which is weaker than integer factorization. This is good news since the parameter `n` is easily factored.
It is then a matter of copy-pasting the algorithm on Wikipedia to get the flag:
```python
from math import gcd
from Crypto.Util.number import inverse
from binascii import unhexlify
n= 99157116611790833573985267443453374677300242114595736901854871276546481648883
g= 99157116611790833573985267443453374677300242114595736901854871276546481648884
c= 2433283484328067719826123652791700922735828879195114568755579061061723786565164234075183183699826399799223318790711772573290060335232568738641793425546869
p = 310013024566643256138761337388255591613
q = 319848228152346890121384041219876391791
assert n == p*q
def L(x):
return (x-1)//n
lamb = (p-1)*(q-1)//gcd(p-1,q-1)
mu = inverse(L(pow(g,lamb,n**2)),n)
m = L(pow(c,lamb,n**2))*mu%n
print(unhexlify(hex(m)[2:]))
```
which ouptuts the flag `actf{crypto_lives}`.
