3

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

5
  • You can only efficiently calculate φ(n) if you know the factorization of n. Commented Dec 30, 2012 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. Commented Dec 30, 2012 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
    Commented Dec 30, 2012 at 19:55
  • What is your threat model?
    – miniBill
    Commented Dec 30, 2012 at 20:15
  • Eh? ... I don't even...
    – miniBill
    Commented Dec 30, 2012 at 20:26

1 Answer 1

4

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

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

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .