Using RSA for Sending Messages
One of the key points made about the Diffie-Hellman algorithm is that it doesn't actually allow you to send a message from one party to another. DH is useful for constructing a new shared secret value but can't directly be used to exchange an existing secret. The alternative that is typically used for exchange is RSA (named after the inventors Ronald Rivest, Adi Shamir, and Leonard Adleman). A lot of people spell the last one as Adelman, which as far as I can tell is incorrect.
The idea of RSA is very similar to an earlier cipher called Pohlig-Hellman. RSA requires the recipient to publish two numbers, called n and e, in a directory with their identity. The n and e values play a very similar role as the group values p and g from DH. The value n is actually the product of two large prime numbers, called x and y, that the recipient keeps secret. The evidence we have is that the easiest way to break RSA is to factor n back into the primes x and y. This means that the security that the system provides is equivalent to the amount of work required to perform the factorization. This is again analogous to the security of DH provided through the difficulty of deriving the private keys A and B.
To send a message M with RSA, the sender first retrieves n and e from the directory. The sender then computes Me mod n and sends that value over the wire. Call the encrypted value M'. The recipient computes a value d such that d*e = 1 mod (x – 1) and d*e = 1 mod (y – 1). It isn't obvious how to efficiently compute this d, but it turns out to not be expensive using a variation of the Euclidean algorithm. The recipient then computes M'd mod n, which reverses the encryption and returns the original value M. No one else can find the d to do this unless they can factor out x and y first.
The similarities between DH and RSA don't stop at the description. The size of the RSA primes you need to protect your message M is roughly the same as the DH prime you need to protect your exchanged key. This means that I don't need to repeat the article on configuring the algorithm. Instead, I'll go off in a different direction and talk about how to chunk a large message into multiple M values for use with RSA.
Next time: Splitting Messages for RSA