Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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

Say you want to encrypt "Hello World!" with RSA.

The first important thing here is the encoding of that text. "Hello World!" as such cannot be encrypted since characters are a non-numerical concept. So an encoding is used convert the characters of that text to numeric values (e.g. the ASCII / Unicode table, but there are many others, especially for non-latin characters). Using Unicode-8, "Hello World" turns into this sequence of bytes (hex-notation):

48 65 6C 6C 6F 20 57 6F 72 6C 64

Such a sequence of bytes can then be interpreted as a number by assigning a most-significant and least-significant byte (e.g. the more left-sided, the more significant). That sequence would then equal the number

0x48656C6C6F20576F726C64 or 87521618088882538408046480

But since such a small number would not produce a secure ciphertext (as @SEJPM already said), a padding is applied. The sequence of bytes then might look something like this:

01 48 65 6C 6C 6F 20 57 6F 72 6C 64 98 9C 38 83 E1 64 E7 0B BC F2 43 C0 6B
26 D4 5E AC 9B C9 DC 2F 1B 87 46 3D 2E 6F 86 66 5E 1B CB 44 DA 5A 50 79 2F
40 79 88 83 84 3E 16 9D 7F 1F 05 2C DF F2 9B 9B 07 11 F6 7A CB 1C 35 9B 76
BD 8D 46 1C E0 09 2A 9F C5 B8 A9 FB 61 41 ... up to the bitsize of N

That sequence is then interpreted as a number and shoved through the algorithm.

share|improve this answer
    
Be careful, the older PKCS#1v1.5 padding is broken. Make sure to use the newer OAEP padding (described in PKCS#1v2.0). – CodesInChaos Jul 20 at 12:52

…what number do we have to put as $m$ in the RSA formula?

There are three possibilities what $m$ can be.

  1. A full-sized random bit-sequence, e.g. a random sort-of-key which is roughly as large as the modulus and will be used to derive a symmetric key for message encryption.
  2. Some padded message. This would mean you'd first apply some padding to your message, e.g. OAEP, and then apply the RSA primitive to it. The message in this case is really any long bit string you want to send over. This can be some binary computation data, or it can be an ASCII-encoded, \0 terminated string, whatever suits your needs.
  3. (not recommended) Some unpadded message. This would skip the padding stage and directly apply the RSA primitive to your message. This is highly dangerous and should not be done in a production setting as really basic attacks can recover the plaintext.
share|improve this answer

ASCII is one way to encode an alphabet into integers, which in return are mostly represented in binary or hexadecimal notation. But of course there are many other ways to encode alphabets into numbers, and exactly how you do that is entirely up to you.

For example you just have the letters from A to Z and got the string $s = s_0s_1s_2s_3....s_n$. Then you consider all the $s_i$ as numerical values in $\{0,1,2,3,...,25\}$ according to their aphabetical order. Then you encode a message like this:

$$x = s_0 + 26 \cdot s_1 + 26^2 \cdot s_2 + ... + 26^{n} \cdot s_n$$

Basically, you just consider a message to be a number in base 26, which can be expressed in any other number system, regardless of numbers of symbols in the alphabet. Binary numbers are nothing else than numbers represented in base 2, and it doesn't matter if we write $01011$, $ABABB$ or even $\oplus\otimes\oplus\otimes\otimes$.

On a similar note, if you embedd the actual message into some special format, e.g. by concatenating a fixed head and tail to the message, that doesn't change anything. Any kind of encoding works, as long as each message has a unique number assigned.

If you consider strings of arbitrary length, you also need arbitrary large integers for your encoding. However, RSA only allows messages smaller than $N$, which limits the length of the string in return. In that case, hybrid encryption is usually used: You don't encrypt the message itself, but you encrypt a random key for a symmetric cypher, and then use a mode of operation with that symmetric cipher and the random key in the RSA ciphertext.

share|improve this answer
    
Your encoding of $x$ is little-endian, which I have never met in the context of base 26. – fgrieu Jul 21 at 5:32
1  
@fgrieu I admit, the example isn't a standard one, since I wrote it on the fly. But invertnig the indices doesn't really change much, as long as it is clear how it is done. – tylo Jul 21 at 8:30

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

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

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.