← Back to context

Comment by breakwaterlabs

19 hours ago

EC, not RSA. RSA would *never* allow something like that.

It would need to be a 3, 5, or 7, since a prime is required.

8 comments

breakwaterlabs

Reply
nneonneo  19 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.

  • nspaced  14 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.)

      2 replies →