I am currently developing a messaging application that uses rsa end to end encryption. The client generates permanent rsa keys, and sends the public key to my server for account management. As it currently is, my program will take any keys, without validation. This is a big security risk, so I need to validate the keys in some way, without knowlege of the private keys. How would I go about doing this?


While there are some obvious checks you can do, you can't cover everything:

  • You can check that the modulus is a composite odd number of the appropriate size

  • If you want to put in the effort, you can do a quick check if the modulus has any small factors

  • You can check if the public exponent is an odd number > 1

However, you can't check beyond that; you can't check if the modulus might not be specially built to be easy to factor, and you can't check if the public exponent is actually relatively prime to $\phi(N)$. What is likely more important to you, RSA doesn't provide a way to verify that the public key entered is the specific public key of the intended receiver.

BTW: you said that this is a big security risk; what is the scenario that you fear that an attacker might introduce a bogus key, and gain some advantage? If it's the fear that someone might substitute their public key, well, since they're likely to substitute a valid key, a validity check on the key isn't likely to protect you. Instead, you need some other mechanism to tie the public key with the identity.

  • 1
    $\begingroup$ The only such scenario I'm aware of is NIZK proofs. $\;$ $\endgroup$ – user991 Mar 2 '14 at 23:19
  • $\begingroup$ Also, Atsch could check that the modulus is not a perfect power. $\;$ $\endgroup$ – user991 Mar 3 '14 at 1:01
  • $\begingroup$ Blind RSA signatures might have some issues if the modulus has a small factors since padded signatures/blinding factors might share factors with the modulus. $\endgroup$ – CodesInChaos Mar 3 '14 at 9:21

Not the answer you're looking for? Browse other questions tagged or ask your own question.