Practical 12: RSA Encryption and Decryption

Check the key generation by hand, because an examiner may ask you to. 61 times 53 is 3233. 60 times 52 is 3120. And 17 times 2753 is 46,801, which is 15 times 3120 plus 1, so e times d really is 1 modulo phi.

The modular inverse is the one step that needs an algorithm. The program uses the extended Euclidean algorithm, which finds x and y with ax + by = gcd(a, b); when the gcd is 1, that x is the inverse. Searching for d by trying every value works for 3120 and does not work for a real key, so learn the algorithm.

pow(m, e, n) is not an optimisation, it is the only way. Writing m ** e % n computes m to the power e in full first: for a real key that is a number with hundreds of thousands of digits, and the program stops responding. Python's three-argument pow reduces modulo n at every step, and every other language has the same function under some name.

Step 2: the properties MU asks for

The PROPERTIES section of that output demonstrates three, and each is worth a paragraph in the journal.

RSA works in both directions. Encrypting with d and decrypting with e gives the message back just as encrypting with e and decrypting with d does. That symmetry is not a curiosity: it is what a digital signature is made of, and Practical 14 uses it.

Textbook RSA is deterministic. The same message gives the same ciphertext every time. The program shows it three times over, and the letter table shows it again: both Ls in HELLO became 2726. If an attacker knows the message is one of Yes or No, they encrypt both with your public key, compare, and read your message without touching your private key. Real RSA is never used this way, which is what padding is for.

RSA is multiplicative. E(7) times E(9) mod n came out equal to E(63), both 3216. An attacker who cannot decrypt anything can still take your ciphertext, multiply it by the encryption of a number of their choosing, and hand you a ciphertext that decrypts to a message altered in a predictable way. That is a chosen-ciphertext attack, and again, padding is the answer.

Step 3: a real key, with OpenSSL

$ openssl genrsa -out lab.pem 1024 2>/dev/null
$ openssl rsa -in lab.pem -pubout -out lab.pub 2>/dev/null
$ openssl rsa -in lab.pem -text -noout 2>/dev/null | grep -E "Private-Key|publicExponent"
Private-Key: (1024 bit, 2 primes)
publicExponent: 65537 (0x10001)
$ head -1 lab.pub
-----BEGIN PUBLIC KEY-----
$ echo -n "Meet me at four" > msg.txt
$ wc -c < msg.txt
15

The key is generated fresh every time this runs, and none of it is printed here. A private key printed in a book is a private key that ends up in somebody's project, so this chapter prints only what is the same on every run: the size, the exponent, and what the operations do.

publicExponent: 65537 (0x10001) will appear for almost every RSA key you ever meet. It is chosen because it is prime, so the gcd test almost always passes, and because its binary form has only two one-bits, which makes the exponentiation fast.

Step 4: padding, and the difference it makes

$ openssl pkeyutl -encrypt -pubin -inkey lab.pub -in msg.txt -out c1.bin -pkeyopt rsa_padding_mode:oaep -pkeyopt rsa_oaep_md:sha256
$ openssl pkeyutl -encrypt -pubin -inkey lab.pub -in msg.txt -out c2.bin -pkeyopt rsa_padding_mode:oaep -pkeyopt rsa_oaep_md:sha256
$ wc -c < c1.bin
128
$ cmp -s c1.bin c2.bin && echo "the two ciphertexts are the SAME" || echo "the two ciphertexts DIFFER"
the two ciphertexts DIFFER
$ openssl pkeyutl -decrypt -inkey lab.pem -in c1.bin -pkeyopt rsa_padding_mode:oaep -pkeyopt rsa_oaep_md:sha256; echo
Meet me at four
$ openssl pkeyutl -decrypt -inkey lab.pem -in c2.bin -pkeyopt rsa_padding_mode:oaep -pkeyopt rsa_oaep_md:sha256; echo
Meet me at four

Encrypting the same message twice gave two different ciphertexts, and both decrypt to it. That is what padding buys: OAEP mixes random bytes into the block before the exponentiation, so the determinism of step 2 is gone, and with it the dictionary attack.

Now do it the textbook way, with no padding at all. Raw RSA needs the input to be exactly the size of the modulus, so the message is placed at the end of a block of zero bytes.

$ ( head -c 113 /dev/zero; cat msg.txt ) > block.bin
$ wc -c < block.bin
128
$ openssl pkeyutl -encrypt -pubin -inkey lab.pub -in block.bin -out t1.bin -pkeyopt rsa_padding_mode:none
$ openssl pkeyutl -encrypt -pubin -inkey lab.pub -in block.bin -out t2.bin -pkeyopt rsa_padding_mode:none
$ cmp -s t1.bin t2.bin && echo "the two ciphertexts are the SAME" || echo "the two ciphertexts DIFFER"
the two ciphertexts are the SAME

The same, twice. That is textbook RSA, and it is the behaviour the program in step 1 demonstrated with small numbers. The two sessions together are the whole argument for padding, and they belong side by side in the journal.

RFC 8017 is the specification that defines both, and it does not hedge: "RSAES-OAEP is REQUIRED to be supported for new applications; RSAES-PKCS1-v1_5 is included only for compatibility with existing applications." The same section says the same of signatures: RSASSA-PSS is required in new applications and RSASSA-PKCS1-v1_5 is there for compatibility, which is the point Practical 14 returns to.

Step 5: what RSA is actually used for

One more measurement, and it settles a question students often have.

$ head -c 200 /dev/zero > big.bin
$ openssl pkeyutl -encrypt -pubin -inkey lab.pub -in big.bin -out big.enc -pkeyopt rsa_padding_mode:oaep -pkeyopt rsa_oaep_md:sha256 2>&1 | sed -E 's/^[0-9A-F]{8,}:/<this run>:/' | tail -2
Public Key operation error
<this run>:error:0200006E:rsa routines:ossl_rsa_padding_add_PKCS1_OAEP_mgf1_ex:data too large for key size:../crypto/rsa/rsa_oaep.c:87:

The long hexadecimal string OpenSSL puts at the front of an error is an identifier for that one run, so it is replaced above with a fixed word; everything after it is the message itself.

A 1024-bit key cannot encrypt 200 bytes. The most it can take with OAEP and SHA-256 is the modulus size, 128 bytes, minus two digests of 32 bytes, minus 2: 62 bytes. A 2048-bit key manages 190. No RSA key encrypts a file.

So RSA is never used to encrypt data. It is used to encrypt a key: a random AES key is generated, the data is encrypted with AES, and only the AES key, a few dozen bytes, is encrypted with RSA. That arrangement is called a hybrid cryptosystem, and it is what TLS does, what PGP does and what every encrypted messenger does.

$ openssl rand -out aes.key 32
$ openssl enc -aes-256-cbc -pbkdf2 -in big.bin -out big.aes -pass file:aes.key
$ openssl pkeyutl -encrypt -pubin -inkey lab.pub -in aes.key -out aes.key.enc -pkeyopt rsa_padding_mode:oaep -pkeyopt rsa_oaep_md:sha256
$ ls -l big.bin big.aes aes.key aes.key.enc | awk '{print $5, $9}'
32 aes.key
128 aes.key.enc
224 big.aes
200 big.bin

The 200-byte file is encrypted by AES, and only the 32-byte key is encrypted by RSA. That is the shape of every real system.

Step 6: the security considerations

The key length. NIST SP 800-131A Revision 2 is the document that says what may still be used, and its table is blunt: for signature generation an RSA modulus shorter than 2048 bits is Disallowed and one of 2048 bits or more is Acceptable. SP 800-57 Part 1 Revision 5 is where the strengths those lengths correspond to are set out, and 3072 bits is what it points to where the data must stay secret for a long time. The key in this chapter is 1024 bits because it is a teaching key that exists for two minutes, and the chapter says so rather than leaving a student to copy the number.

p and q must be far apart and truly random. If they are close together, n can be factored by searching near its square root. If the random source is weak, two people can generate keys sharing a prime, and then one gcd between two public moduli recovers both private keys. That has been found in the wild on network devices.

Never use textbook RSA. Steps 2 and 4 above are the demonstration.

e is public and small; d is private and large. Both are fine. What must never leak is d, p, q or phi: any one of them gives the others.

Timing. A naive exponentiation takes measurably longer for some exponents than others, and an attacker who can time your decryptions can recover d. Real libraries blind the input to prevent it; your own implementation does not, which is another reason a hand-written RSA is a teaching exercise and not a product.

And the one that is coming. A sufficiently large quantum computer would factor n efficiently by Shor's algorithm, which ends RSA. That machine does not exist, and replacement algorithms are being standardised; a student should know the sentence and should not repeat any prediction of a date.

Procedure

1. Write egcd and inverse_mod using the extended Euclidean algorithm.
2. Pick two small primes, compute n and phi, choose e with gcd(e, phi) = 1, and find d. Check e times d modulo phi is 1 by hand.
3. Encrypt and decrypt one number with modular exponentiation.
4. Encrypt a word one letter at a time and note that two identical letters give identical ciphertext.
5. Show that encrypting with d and decrypting with e also works.
6. Show that E(a) times E(b) equals E(a times b) modulo n.
7. Factor your own small n and say how long a real one would take.
8. Generate a real key with openssl genrsa, look at its exponent, and encrypt and decrypt with OAEP twice, recording that the two ciphertexts differ.
9. Repeat with rsa_padding_mode:none and record that they do not.
10. Try to encrypt 200 bytes, record the failure, and build the hybrid arrangement instead.

Observations

Result

RSA was implemented from nothing with p = 61 and q = 53, giving n = 3233, phi = 3120, e = 17 and d = 2753, and e times d was confirmed to be 1 modulo phi. A number and a word were encrypted and decrypted correctly, and three properties were demonstrated: the algorithm works with the two exponents exchanged, it is deterministic without padding, so both Ls of HELLO produced 2726, and it is multiplicative, so E(7) times E(9) equals E(63). The same operations were then performed with OpenSSL on a 1024-bit key with public exponent 65537: with OAEP padding the same message gave two different ciphertexts that both decrypted correctly, and with no padding it gave the same ciphertext twice. A 200-byte file could not be encrypted at all, and was instead encrypted with AES under a 32-byte key that RSA encrypted, which is the hybrid arrangement every real system uses.

Where marks are lost

Computing the power in full instead of using modular exponentiation. It never finishes on a real key.

Searching for d in a loop. It works on 3120 and not on a real phi. Use the extended Euclidean algorithm.

Encrypting a message larger than n. Every value must be less than the modulus; a longer message has to be split, or, properly, encrypted with a symmetric cipher under an RSA-wrapped key.

Saying RSA encrypts files. It does not. 62 bytes on a 1024-bit key, and the chapter shows the failure.

Presenting textbook RSA as secure. Say in the same breath that it is deterministic and multiplicative, and that OAEP is what is actually used.

Quoting 1024 bits as a key length without a note. It is below the current minimum. Say the key is a teaching key.

Not destroying p, q and phi. Anyone with any one of them has d.

Confusing the public and private exponents. e is small and published; d is large and secret.

For the journal

Aim; the six steps of key generation with your own p and q and every number checked by hand; the encryption and decryption formulas; the program and its output; the three properties, each with the output that shows it; the factorisation of your n; the OpenSSL key with its exponent; the OAEP session showing two different ciphertexts; the no-padding session showing one; the failed 200-byte encryption and the hybrid arrangement with the file sizes; the security considerations in your own words with the key length from NIST; the observation table; the result.

Quick revision

• Public key (e, n), private key (d, n). n = p times q; phi = (p-1)(q-1); e times d = 1 mod phi.
• c is m to the power e mod n; m is c to the power d mod n. Use modular exponentiation.
• d is found with the extended Euclidean algorithm.
• Security rests on factoring n being hard. Destroy p, q and phi.
• Textbook RSA is deterministic and multiplicative, so it is never used raw.
• OAEP adds randomness: the same message gives a different ciphertext every time.
• e is almost always 65537.
• A 1024-bit key with OAEP and SHA-256 takes at most 62 bytes; 2048 bits takes 190.
• So RSA encrypts a symmetric key and the symmetric cipher encrypts the data. That is a hybrid cryptosystem.
• 2048 bits is the minimum for a new key; SP 800-131A Rev.2 disallows anything shorter.
• Two keys sharing a prime, from a weak random source, are both broken by one gcd.

Questions you must be able to answer

1. What makes RSA hard to break? That recovering p and q from their product n is beyond any computer we have when the primes are large. Everything else about the key is public.

2. How is d computed? As the multiplicative inverse of e modulo phi(n), found with the extended Euclidean algorithm. Here 17 inverse modulo 3120 is 2753.

3. Why must you use modular exponentiation rather than computing the power first? Because the power itself, for a real key, is a number with hundreds of thousands of digits. Reducing modulo n at every step keeps every intermediate value small.

4. Both Ls in HELLO encrypted to 2726. Why is that a problem? Because textbook RSA is deterministic, so an attacker who guesses a message can encrypt their guess with your public key and compare. Padding removes the determinism.

5. What is the multiplicative property, and what does it allow? That E(a) times E(b) mod n equals E(a times b). An attacker can therefore alter a ciphertext in a predictable way without any key, which is a chosen-ciphertext attack.

6. What does OAEP do? It mixes random bytes and a hash into the block before exponentiation, so the same message encrypts differently every time and the structure an attacker would exploit is gone. RFC 8017 recommends it for new applications.

7. How much data can a 2048-bit RSA key encrypt? 190 bytes with OAEP and SHA-256: 256 minus two 32-byte digests minus 2. Not a file.

8. So how is a large file encrypted with RSA? It is not. A random symmetric key encrypts the file and RSA encrypts that key. The combination is a hybrid cryptosystem, and this chapter builds one.

9. What key length should a new RSA key have? At least 2048 bits: SP 800-131A Revision 2 disallows anything shorter for signature generation. 3072 where the secret must last. The 1024-bit key in this chapter is a teaching key and is below the acceptable minimum.

10. Name two ways RSA fails even when the mathematics is right. A weak random source, which can give two keys a shared prime that one gcd recovers; and timing, where the time a decryption takes leaks the private exponent unless the implementation blinds it.