Bespoke Padding

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 $$ $$ p_2(x) = (a_2 x + b_2) ^ e - c_2 \mod N $$ Hence, if both polynomials have the root $m$, then they are both divisible by $(x - m)$....

December 15, 2022 · 2 min · qvinhprolol