Take the 2-minute tour ×
Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It's 100% free, no registration required.

For example, in RSA, we use this for encryption: $ciphertext = (m^e \mod n)$ and for decryption.

If our message is "hello world", then what number do we have to put as $m$ in the RSA formula?

share|improve this question
add comment

3 Answers

I am not an expert on this, and from what I understand there are different ways to use RSA. But I know of this one way that might answer your question.

Alice wants to send a message to Bob. The first thing she does is to choose a "nice" cipher, say the blocks cipher AES. She generates an arbitrary key for this one message. This key might be say 256 bits long. So the key is string of 256 ones and zeros. If you convert each 8 bits to one byte, then you get a key of length 32 bytes. Now this key again can be written as a long string of ones and zeros. So that makes a large (binary) number.

(As a concrete example. If the key was 16 bits long, say 1001011010001101, then that is the same as 38541)

Take this number (the key) as your $m$ in your question and use RSA to encrypt the key using Bob's public key.

Then Alice sends the message that has been encrypted with AES and the encrypted key to Bob. So the ciphertext that is sent really consists of an encrypted (using AES) message with an encrypted (using RSA) key.

Bob can then decrypt the key using his secret key, and use the result to decrypt the message using AES.

share|improve this answer
1  
In practice you don't use the symmetric key as m. You add specialized padding. –  CodesInChaos Aug 24 '12 at 17:27
    
@CodesInChaos: Thanks! I didn't know. I will research this and update my answer or delete the answer. –  Thomas Aug 24 '12 at 20:31
    
The method described is flawed. See e.g. Twenty Years of Attacks on the RSA Cryptosystem –  fgrieu Sep 13 '12 at 16:46
add comment

Every piece of information can be codes as a number. For messages, first encode each character, for example ord("h") = 104, ord("e") = 101, ord("l") = 108,.... As usually, there are tons of available encodings, e.g., latin-1. Now you have a sequence of bytes, which is how computers stores strings anyway.

Compute the resulting number e.g. using the following recurrence x = 256*x + nextByte. Start with 0 and get

  • 256*0 + 104 = 104
  • 256*104 + 101 = 26725
  • 256*26725 + 108 = 6841708

This would work, but the numbers quickly became unusable long for RSA. In practice, you generate a key for a symmetrical cipher (e.g. AES) and encrypt this key using RSA.

share|improve this answer
    
in https they use AES then ? or RSA for whole SSL ? –  Ted Aug 24 '12 at 5:27
    
HTTPS uses a symmetric cipher, which one is subject to negotiation between the parties. It's all quite complicated, but for sure it doesn't use RSA for the whole communication as this would be extremely inefficient. –  maaartinus Aug 24 '12 at 12:01
    
For most SSL transfer modes including HTTPS, the security certificate issued to the server has a public RSA key. That key is used to encrypt and send the certificate holder your own RSA public key, establishing a two-way communication channel through which the actual encryption scheme (usually symmetric-key) to be used is negotiated between client and server. Once a scheme is agreed on, the key, IV and other secrets are transmitted by one party to the other over RSA, and all further communication happens over the symmetric-key encryption channel. –  KeithS Sep 5 '12 at 3:53
    
Symmetric key algorithms such as AES are much faster than RSA and hard to break due to the dynamic key generation, but because both Alice and Bob must know the same key to use it, and they may have never met before nor had any other opportunity to exchange secret data "offline", RSA is used to protect this secret data from Carol, who may be listening to the entire conversation. –  KeithS Sep 5 '12 at 3:56
    
No, the direct method described would not be secure for short plaintext. In particular, anyone can verify a guess of the plaintext; and sending the same plaintext to multiple recipients is unsafe. See e.g. Twenty Years of Attacks on the RSA Cryptosystem. –  fgrieu Sep 13 '12 at 16:51
show 2 more comments

For most real-life ciphers implemented on computer, plaintext is first changed into a sequence of bytes, similarly to the way text is stored in file. Variants abound: ASCII, UTF8.. and may involve lossless compression. For some encryption methods (e.g block cipher in CBC mode), that sequence of bytes is padded in order to make its size convenient, e.g. multiple of 128 bits.

In a typical use case, RSA does not directly encrypt plaintext. Rather, the plaintext is handled as above, then enciphered using a block cipher, which key $K$ (perhaps 128-bit or 256-bit) is randomly drawn, RSA-encrypted, and send along the encrypted plaintext (typically as a header). This is called hybrid encryption.

In that typical use case, RSA encryption shall yield a ciphertext representing $K$ encrypted (or if hybrid encryption is not used, a short message). One reasonably safe and popular way to proceed is known as RSAES-PKCS1-V1_5, and described in PKCS#1v2.1. Most good schemes follow a similar process:

  1. $K$, which is short, is padded or otherwise turned into a longer byte string (most of what's added is random).

  2. That byte string is turned into a number $m$ (the one in the question's example) by considering the byte string as the representation in base 256 of $m$, usually with first byte the most significant byte. That is, if the byte string has $b$ bytes $B_0\cdots B_{b-1}$ then $m=\sum_{j=0}^{j=b-1}B_j\cdot256^{b-1-j}$. The padding in step 1 is usually such that after step 2 we have $m<n$, but $\log_2m\approx \log_2n$ (and hope is that $m$ behaves close enough to random in $[0\dots n-1]$).

  3. RSA encryption is applied, computing the number $m^e\bmod n$.

  4. That result is turned into a byte string by writing the number in base 256, usually with first byte the most significant byte (that is the reverse of step 2).

Note: Step 4 is seen in two variants; one outputs a fixed-width byte string, the other a variable-width byte string with the first byte never equal to 00h. On top of that some wrapper bytes are often added.

Note: Each of the four steps is reversible (with step 3 requiring the private key), so that decryption can work.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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