Description
Oops! I have a typo in my first message so I sent it again! I used RSA twice so this is secure right? Download: chall.py and output.txt .
Setup
Download chall.py and output.txt.
Read chall.py to understand the RSA setup and how the two messages are related.
cat chall.py
cat output.txt
Solution
- Step 1Identify the Franklin-Reiter attackThe same RSA public key (n, e) is used to encrypt two related messages m1 and m2 where m2 = m1 + k for some small known constant k (a typo correction). With e=3 and a linear relation between the plaintexts, Franklin-Reiter's related-message attack can recover both messages.
- Step 2Extract the values from output.txtParse output.txt to get n, e, c1 (ciphertext of m1), and c2 (ciphertext of m2), and the relationship constant k.cat output.txt
- Step 3Apply the Franklin-Reiter attackCompute the GCD of two polynomials over Z/nZ to recover the plaintext. The standard implementation uses Sage or a custom polynomial GCD.# In SageMath: sage << 'EOF' n = YOUR_N e = 3 c1 = YOUR_C1 c2 = YOUR_C2 k = YOUR_K # m2 = m1 + k R.<x> = Zmod(n)[] f1 = x^e - c1 f2 = (x + k)^e - c2 def gcd_poly(a, b): while b: a, b = b, a % b return a.monic() m1 = -gcd_poly(f1, f2)[0] print(bytes.fromhex(hex(int(m1))[2:])) EOF
Flag
picoCTF{fr4nkl1n_r31t3r_...}
The flag is recovered using the Franklin-Reiter related-message attack on RSA with e=3.