I understand that RSA encryption uses this formula:

C = M^e (mod N)

public key is e and N

N is pq - p and q are private key.

mod N makes above function one-way - ie cannot be reversed. Hence given C, e and N, it is not possible (easily) to find M.

Basic idea is that modulo arithmetic on an exponent is a one way function.

The practical bit I am struggling on now is that M (the message) must be a number. How is the text eg "I love you" converted to a number. I am looking to understand the basic concepts but also in reality what scheme is used to create a number from the text. What are the options and what is generally used in practice? Please explain the mathematics as required.

You could take the byte stream of the text message above:


and treat as a LARGE binary number. I guess the numbers would get pretty large like this so probably not the way its done.


How it is done in practice is that no one uses RSA to encrypt messages. They use RSA to encrypt (and sign) an encryption key, and then encrypt the message with the encryption key. They send the encrypted key and the encrypted message to the other party. The other party uses their RSA private key to decrypt the key, then uses that key to decrypt the message. Furthermore, in practice, they also add padding to the key before encrypting it with RSA.

That said, RSA can indeed encrypt any message that is smaller than the modulus N. So, if your byte stream in the question is smaller than the modulus, you can encrypt it with RSA. If the byte stream were larger than N, you could theoretically break it up into smaller messages and encrypt them individually. The problem with this is RSA is deterministic; so you'd have to add some random padding to make it non-deterministic. Typically people just don't bother with RSA for bulk encryption, however.

  • $\begingroup$ ignoring signing, is it a negotiation where the RSA encrypted key is sent first, followed by the symmetric encrypted cipher? Or can it be send as one item, and if so what is mechanism. $\endgroup$ – user619818 May 15 '14 at 13:11
  • $\begingroup$ You can send them together. You just have to specify a protocol format. It could be anything: a simple binary protocol (first N bytes are the encrypted key; remaining bytes are the ciphertext); xml; json; base64 encode each and put a newline in-between. $\endgroup$ – mikeazo May 15 '14 at 13:29
  • 1
    $\begingroup$ Encoding is pretty trivial: E.g. it doesn't matter if you send two messages with 1 bit information each, or send one 2-bit message or a specific format with delimeters (e.g. $111b_10101010b_2000$). Regarding the answer, the according terms for these mechanics might be useful: hybrid encryption and as a practically used padding scheme RSA-OAEP $\endgroup$ – tylo May 15 '14 at 13:48

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.