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)?
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
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).