Comment by nneonneo

20 hours ago

“d=4” is a perfectly legal RSA private key. The corresponding public key would probably have a weird e (not 65537, the usual choice), but would otherwise be legal, and could have an arbitrarily large modulus n (thus appearing “secure”).

Note that p,q (the primes you’re thinking of) are not actually required for decryption. They enable you to calculate d, the decryption exponent, and also enable decryption-time optimizations (exponentiation with d_p and d_q followed by CRT recombination), but that’s optional. In fact, p,q can be computed from n, e and d.

7 comments

nneonneo

Reply
nspaced  15 hours ago

d=4 is not a valid RSA private key. When p and q are prime λ(n) = lcm(p − 1, q − 1) is always even. e must be coprime with λ(n) so it's odd. de ≡ 1 (mod λ(n)) which means that de is 1 + an even number, so d must also always be odd.

  • nneonneo  10 hours ago

    p=84491346121303840713246978535231635954643146756451201037561748571580203988423

    q=82392744353585332429460820191121154258120959554076291572887591391377445536703

    n=6961473881062880999817189307002435362675293718841800458853975151946795609411283948376850761685158526939121778595276868395992041449207352173613540433589369

    e=1305276352699290187465722995062956630501617572282837586035120340990024176764584449553695476096002966088824142338449519554315283866861919281309484272012046

    d=4

    assert n == p * q

    assert pow(pow(123456789, e, n), d, n) == 123456789

    (This doesn't work for all messages `m`, so I agree with what you've said - d=4 is not a good choice. But it can work.)

    • nspaced  8 hours ago

      Sure, but I think you'll agree that calling this modified version RSA is a bit of a stretch :)

      Every definition of RSA I've ever seen requires d and e to be coprime with λ(n)

      1 reply →