CATEGORY
Showing 6 post(s) in this category.
Diffie-Hellman's security rests on the discrete logarithm problem being hard. For a small prime, it isn't. Baby-step giant-step trades a brute-force search of size p for one of roughly √p, and that's the whole reason real DH needs huge safe primes.
ElGamal's private key is just another discrete logarithm. The same baby-step giant-step technique that breaks Diffie-Hellman over a small prime recovers ElGamal's private key too, and from there decrypts any captured ciphertext directly.
Sharing one RSA modulus across multiple key pairs looks like a harmless shortcut: skip prime generation, reuse n. If the same message ever gets encrypted under two of those keys, no private key is needed to read it back.
RSA's security assumes factoring n back into p and q is infeasible. That assumption quietly breaks if the key generator picks p and q too close together. Fermat's 1643 factoring method recovers them both in seconds.
A low public exponent like e=3 is efficient and, by itself, still safe. Broadcast the same message to three recipients using e=3 with no padding, and the Chinese Remainder Theorem recovers it with no private key at all.
Small private exponents make RSA decryption and signing faster. Michael Wiener showed in 1990 that a d small enough to help performance is also small enough to recover from the public key alone, via continued fractions.
