> For the complete documentation index, see [llms.txt](https://alham-rizvi.gitbook.io/alhamrizvi/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://alham-rizvi.gitbook.io/alhamrizvi/cryptography/rsa/11.-franklin-reiter-attack.md). # 11. Franklin-Reiter Attack ### 1. Overview This attack breaks RSA when **two messages are linearly related** and encrypted with the **same modulus `n` and same exponent `e`**. ``` M2 = a·M1 + b ``` and: ``` C1 = M1^e mod n C2 = M2^e mod n ``` Goal: ``` Recover M1 (and M2) ``` ### 2. Core Idea Define polynomials over modulo `n`: ``` f(x) = x^e − C1 g(x) = (a·x + b)^e − C2 ``` Since: ``` x = M1 is a root of both f and g ``` We compute: ``` gcd(f, g) ``` This reveals: ``` x − M1 ``` So: ``` M1 = root of gcd ``` ### 3. Why This Works RSA is deterministic (without padding): ``` Same structure → same algebraic relation preserved after encryption ``` So: ``` Relation in plaintext → relation in ciphertext polynomials ``` ### 4. Conditions Attack works when: ``` Same modulus n Same exponent e (usually small like 3) Messages linearly related No padding ``` ### 5. Attack Steps 1. Define: ``` f(x) = x^e − C1 g(x) = (a·x + b)^e − C2 ``` 2. Compute: ``` h(x) = gcd(f, g) ``` 3. Extract: ``` M1 from h(x) ``` ### 6. Python (SageMath) Implementation This attack requires polynomial GCD over modular arithmetic. ```python # Run in SageMath n = ... e = 3 C1 = ... C2 = ... a = ... b = ... R. = PolynomialRing(Zmod(n)) f = x^e - C1 g = (a*x + b)^e - C2 h = f.gcd(g) M1 = -h[0] # root from linear polynomial print("M1 =", M1) ``` ### 7. Important Detail After GCD: ``` h(x) = x − M1 ``` So: ``` M1 = −constant term ``` ### 8. Minimal Example ``` M2 = M1 + 1 a = 1, b = 1 ``` Then: ``` g(x) = (x + 1)^e − C2 ``` ### 9. When to Recognize Look for: ``` Two ciphertexts Same n and e Hint: messages related Patterns like: "second message is previous + 1" "messages differ by constant" ``` ### 10. Why It Breaks RSA Because: ``` RSA preserves algebraic structure ``` Without padding: ``` Encryption is predictable and reversible via algebra ``` ### 11. Limitations ``` Needs exact linear relation Fails if padding is used Requires polynomial GCD (Sage) ``` ### 12. Pure Python Note ``` Sympy is not reliable for modular polynomial gcd ``` Best tool: ``` Use SageMath ``` ### 13. Summary ``` M2 = a·M1 + b → build polynomials → gcd(f, g) → recover M1 ``` ### 14. Practice Problem ``` n = 18721 e = 3 M2 = M1 + 5 C1 = 10652 C2 = 16021 ``` ### Task ``` Recover M1 ``` --- # Agent Instructions This documentation is published with GitBook. GitBook is the documentation platform designed so that both humans and AI agents can read, navigate, and reason over technical content effectively. Learn more at gitbook.com. ## Querying This Documentation If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question. Perform an HTTP GET request on the current page URL with the `ask` query parameter, and the optional `goal` query parameter: ``` GET https://alham-rizvi.gitbook.io/alhamrizvi/cryptography/rsa/11.-franklin-reiter-attack.md?ask=&goal= ``` `ask` is the immediate question: it should be specific, self-contained, and written in natural language. `goal` is optional and describes the broader end goal you are ultimately trying to accomplish on behalf of the user. GitBook uses it to tailor the answer towards what is most useful for that goal. The response will contain a direct answer to the question and relevant excerpts and sources from the documentation. Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.