We do not do parties, we do multi-parties! One of the most important ingredients for these is (next to mate) oblivious transfers.
Solved 1 hour after the ctf end :(
The server use paillier cryptosystem, we can provide generator and publickey , then the server computes a encrypted flag using following formula. and returns ciphertext to us.
- Generate a safe prime
- Use as public key
- Send as
In paillier, multiplication in ciphertext is addition in plaintext, and power in ciphertext is multiplication in plaintext. So the decryption result will be:
To solve this task, I use a safe prime as and private key, formally: After decryption, we'll have: To get , simply calculate the remainder over :
is more complicated. Recall that , we can derive following formulas:
Now xor those two integer to get the flag.
Here's the solution from admin. It is stronger than my solution which doesn't need the assumption of safe prime on private key. Here's a proof about how it works:
Using extended gcd to get X, Y, such that:
Using the equation above, we have following equation about multiplicative inverse:
Select , where
However the script calculate using: which is also true.
We can calculate from in the similar way: