I'm building a platform with a strong security. Security is based on encrypting data with AES-256 encryption. Yet the system needs to "share" these keys among the users and they need to be transferred in an encrypted way too. In order to do this, I'm using an RSA algorithm. The question is how can I generate a secure pair of RSA keys? I also read that p, q, φ(n) need obviously to be kept secret. By the way, when I send a public key, I also need to send the modulo n. Given that the totient function is publicly known, everybody could calculate φ(n), right? So, how can I keep secret φ(n)?

  • You can only efficiently calculate φ(n) if you know the factorization of n. – CodesInChaos Dec 30 '12 at 19:42
  • But most hard problems in crypto boil down to key distribution. i.e. how you associate a certain public key with an identity. – CodesInChaos Dec 30 '12 at 19:43
  • It is random. I mean: a user generate a random RSA public key, then sends it. User generates a new pair of keys every time it is needed. Eventually the private key could be stored in an encrypted format (AES) in case the "User A" isn't online when "User B" send his data. – user18215 Dec 30 '12 at 19:55
  • What is your threat model? – miniBill Dec 30 '12 at 20:15
  • Eh? ... I don't even... – miniBill Dec 30 '12 at 20:26

Computing φ(n) from n is equivalent to factoring n:

  • If you know the factors p and q then φ(n) = (p-1)(q-1).
  • Since φ(n) = n - (p+q) + 1, knowing n and φ(n) means that you know pq and p+q. It so happens that p and q are the two solutions of the quadratic equation X2-(p+q)X+pq = 0; finding the roots of a quadratic equation (in the real numbers) is easy.

Therefore, it is no empty banter than to call the public key "public": you can make it public without giving away the private key.

Generating a RSA key pair is not mathematically difficult, but, as with all things crypto, it can fail in many subtle ways that you would not be able to detect (as usual, you cannot test for security, only for functionality). Therefore, it is highly recommended that you use existing code and facilities for such jobs (i.e. a crypto library like OpenSSL, or something already included in your programming framework like Java's java.security.KeyPairGenerator).

Producing key pairs is the easy part. Public-Key Infrastructure is about the hard part: distributing the keys. Asymmetric algorithms like RSA split keys into a public key and a private key, and you only have to distribute the public part, and since it is public, such distribution requires no encryption. This makes key distribution easier; but not easy. THe main problem is how User A will make sure that it got the "right" public key for User B (i.e. the public key for which User B indeed knows the private key, and not another key which the attacker cunningly pushed in lieu of the right key).

PKI is known to be a very complex issue (and a difficult market as well); the best practice is not to rebuild it from scratch. Instead, research X.509 PKI (in particular this tutorial) and OpenPGP (X.509 is designed to support hierarchical PKI, while OpenPGP was meant for Webs of Trust).

|improve this answer|||||
  • That's a very brilliant answer! Thanks! So I can share the modulo as long as I keep secret p and q? – user18215 Dec 30 '12 at 20:41

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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