The challenge has the most code in it so far, but should not take too long to realize the task we had to do. This follows the same idea as the prequel challenge Let’s Decrypt - that is to find an appropriate N, e such that the pow(sig, e, N) is equal to the value of the PKCS1 padded messages. However, in this challenge, we had a twist - we can only use one non-prime modulus N but has to generate three es such that pow(sig, e_n, N) = m_n with e_n being the public exponent correlated to the nth message m_n.

First, the modulus is big (2048 bits) and the public exponent e is small (3), hence we may use a small number and the arithmetic operation under the modulo N is the same as in $\mathcal Z$ Pedro is not exactly careful with the padding, indeed: vote = int(your_input['vote'], 16) verified_vote = long_to_bytes(pow(vote, ALICE_E, ALICE_N)) # remove padding vote = verified_vote.split(b'\00')[-1] if vote == b'VOTE FOR PEDRO': return {"flag": FLAG} Anything in the verified_vote variable before the null byte is discarded, hence a message of the form <SOME RANDOM STUFF>\x00VOTE FOR PEDRO is still valid.

RSA signing with malleability, we can sign anything but the admin token to retrieve the flag. My approach is to get the signature of the hex string b'\x02', in numeric value is $2^d$, with $d$ being the private key. Then we request for the message that is twice the value of the admin token, then we get the value of $(2m)^d$. Then retrieving the value of $m^d$ should be trivial.

This is a example of Franklin-Reiter attack on RSA. We can obtain two ciphertexts that correspond to the same plaintext encrypted with the same modulus, but padded differently. Denote the plaintext as $m$, the modulus $N$, the public exponent $e$, the ciphertexts $c_1$ and $c_2$, and the padding variables be $a_1, a_2, b_1, b_2$. We thus have the two polynomials with the common root of $m$: $$ p_1(x) = (a_1 x + b_1) ^ e - c_1 \mod N $$

The flag is padded with \x00 at the end to make the length of the flag overall becomes 100 bytes long. For each null byte appended, the value of the flag is multiplied by 256. Hence, we can retrieve the flag using Coppersmith, however there is a twist. Even if the polynomial theoretically should output some result, none is returned by the small_roots function. The solution that works seems to reduce the x that is calculated to be the smallest x possible such that the result makes sense.