I lost my modulus. Can you find it for me?
The server implement paillier cryptosystem. It gives us a encrypted flag at start.
There are two operations, A and B, Operation A return the ciphertext of our input. Operation B gives us the last byte of plaintext. We can run atmost 2048 operations.
Unfortunately, we know nothing about .
- Leak 8 ~ 1024 bits of n bit-by-bit (1008 OPs).
- Last byte is
- Leak 16 bytes of flag (16 OPs).
- Repeat with a new connection.
We can calculate by encrypting it and then decrypting, If , we get the last byte of $m$. However, if , we get the last byte of . We can leak bit-by-bit by selecting as . Moreover, the return value is if , which means we have 16 operations left for leaking 16 bytes of flag.
For example, Let
To decrypt the flag, we can use the homomorphic property of paillier: Decrypt it with following recursive equation: