Attacks on RSA and the Generic Group Model
Stub. Beyond the basic factoring/discrete-log algorithms already covered: discrete log in composite-order groups and the information leakage this causes, an attack on static (reused) Diffie-Hellman keys, a lower bound on discrete log in generic prime-order groups (formalizing why no "structural" attack can beat square-root time there), and concrete RSA failure modes from poor key generation, fault injection, and small secret exponents.
Corresponds to Chapter 16 (the core factoring and discrete-log algorithms — Pollard’s methods, the quadratic sieve, baby-step/giant-step, Pohlig-Hellman, index calculus — are already covered in number-theory-for-cryptography). Covers additional, more specific attack surface: discrete log is easy in a group of composite order factoring into small primes (via Pohlig-Hellman-style reduction to the prime-order factors), which leaks partial information even when the full order is hard to factor, and a related attack against static (long-term, reused) Diffie-Hellman key pairs. The generic group model is a formal framework (an algorithm that can only manipulate group elements as opaque labels, via the group operation) in which discrete log provably needs square-root time — a lower bound explaining why only structure-specific algorithms (index calculus, exploiting ‘s extra structure) can beat that bound, as covered for the general number field sieve. Closes with concrete RSA pitfalls: attacks from poor randomness in key generation, a fault-injection attack on optimized RSA implementations, and the classical attack on RSA with a small secret exponent.
Outline (TODO — flesh out each)
- Discrete log in groups of composite order
- Information leakage in composite-order groups
- An attack on static Diffie-Hellman
- The relation between DL, CDH, and DDH
- A lower bound on discrete log in generic prime-order groups
- Attacks on RSA from poor key generation
- A fault injection attack on optimized RSA
- An attack on low secret exponent RSA