How do ciphers change plaintext into numeric digits for computing?

Question

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?

Answer 1

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.

Answer 2

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

Answer 3

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.

Answer 4

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.

Answer 5

Introductory presentations often gloss over this, because it isn't necessary to understand the basic principles. But practical standards define this precisely.

For RSA, the defining document is PKCS#1, several versions of which have been published as RFC. In PKCS#1 v2.2, conversion between octet strings¹ and integers is specified in §4, with the functions I2OSP and OS2IP.

The characters in "hello" have an ASCII value if the text is represented in the ASCII encoding. RSA, like most cryptographic standards, doesn't care about text encodings, it works on (8-bit) bytes. So it doesn't see "hello" but (assuming you stored the string in the ASCII encoding) the 5-byte sequence consisting of the bytes with values 104, 101, 108, 108 and 111.

The conversion from strings and integers is concatenation, but as digits in base 256. There are two “obvious” ways to do this, depending on what order to put the digits. RSA assembles the digits in big-endian format, i.e. the first byte of the string corresponds to the most significant digit and so on.

Note that $m \mapsto m^e \bmod n$ is the RSA encryption primitive (calleed RSAEP in PKCS#1 v2). This primitive is not secure for actual encryption because it leaves many mathematical relationships exposed (e.g. $(m_1m_2)^e = m_1^e m_2^e$). The actual RSA encryption algorithm is what PKCS#1 calls RSAES-OAEP-Encrypt, and the scheme consisting of the pair of corresponding encryption and decryption function is called OAEP. OAEP is designed to ensure that those mathematical relationships never happen between numbers used in the RSA-OAEP scheme.

¹ _{“Octet” means 8-bit byte, as opposed to different byte sizes found on some rare platforms. This word is mostly used in networking and cryptographic standards.}

Answer 6

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.