RSA — Boxer Of Our Online World

The Carthouse of Cybersecurity

RSA — Boxer Of Our Online World

The Carthouse of Cybersecurity

Preface

I have just finished re-reading Animal Farm by George Orwell, and, for fun, I like to imagine its characters as cybersecurity ones. To me, Boxer — the cart-horse and who is generally the hero of the whole book — is the RSA method — as it is truly the cart-horse of the cybersecurity world. Overall, it’s a lumbering and slow beast that has just got larger over the years, but it does its work without any problems and always “must work harder”. In its youth, it was small and nimble, and almost unbeatable, but age has slowed it down.

But, still, Boxer is ever dependable, and he’s also been knocked down over the years, but always comes back stronger. And those pesky dogs — the Elliptic Curve methods — are forever nipping at his feet, but still, he manages to shake them off, and continues on with his sole quest to make the world a better place. And, the dogs, too, just like all the other animals on the farm, just can’t do what Boxer does. He’s irreplacable on the farm!

So, let’s have a look at the Boxer of Our Online World.

Introduction

RSA was first revealed to the world in 1977 within Martin Gardner’s Scientific America column, and it is still the most popular public key encryption method for encrypting data with a public key.

For encryption, Bob encrypts a plaintext message with Alice’s public key, and she decrypts the ciphertext with her private key:

For a digital signature, Alice signs a message with her private key, and Bob proves that she has signed it with her public key:

Along with being the most used public key encryption method, RSA is still the most popular method for digital signing (with most of the certificates we use to verify Web sites still mostly containing RSA public keys). While it’s not quantum robust, it is still the core of trust on the Internet. Without it, we could trust very little in our online world.

The basics

So, let’s do some RSA with a minimal number of Golang lines to create useable encryption. For this, we will use the OEAP padding method (as the core method can be cracked without padding).

First, we generate an RSA key pair and encode the key pair. With this we have two prime numbers (p and q), and compute the modulus (N):

N=pq

We then compute:

ϕ=(p−1).(q−1)

We then pick an encryption key value (e=0x010001) and compute:

d=e^{−1} (mod ϕ)

The public key is then (e,N) and the private key is (d,N). To encrypt a message (M), we create a cipher:

c=M^e (mod N)

and then decrypt with:

M=c^d (mod N)

Optimal Asymmetric Encryption Padding (OAEP)

The simplest way to pad is to use PKCS#v1.5. With this, we pad to the start of the message bytes, and where the first two bytes are 0x00 and 0x02, and followed by a number of non-zero bytes. We then add a 0x00 byte to identify the end of the padding, and then followed by the message bytes:

0x00 0x02 [some non-zero bytes ] 0x00 [message bytes]

When unpadding, the 0x00, 0x02 sequence is detected, and then we search for the 0x00 byte and take remove all of the preceding bytes. Unfortunately, Daniel Bleichenbacher published a paper that showed how the PCKS#v1.5 padding method could be cracked with a chosen cipher attack [here]:

In fact, Matthew Green puts it best when he said:

“PKCS#1v1.5 is awesome — if you’re teaching a class on how to attack cryptographic protocols. In all other circumstances, it sucks.”

The Bleichenbacker’s attack has been continually compromising some systems for decades, but TLS 1.3 now overcomes it by dropping support for PCKS#v1.5.

The solution to the problems of PKCS#v1.5 is to use Optimal Asymmetric Encryption Padding (OAEP), and was first published by Bellare and Rogaway as [here]:

It has since been standardized in PKCS#1 v2 and RFC 2437 [here]:

Overall we operate on n bits at a time, and where n is the number of bits in the modulus (Figure 1). This is based on a Feistel network, and where if we EX-OR sometime with the same value twice, we end up with the original value.

With this — as illustrated in Figure 1 — we have two fixed values of k_0 and k_1. k_1 defines the number of zeros to pad onto the message, and k_0 defines the number of bits in a random number (r). The number of bits we are processing in the message is thus n-k_0-k_1 bits. We then have two hashing functions of G and H. The G function expands the k_0 bits of r into n-k_0 bits, and which is EX-OR with the padded message. This produces X. Next we take the value and feed it into H, and which hashes the bits to produce k_0 bits. This is then EX-OR with r to produce Y (and which has k_0 bits).

Ref: Buchanan, William J (2022). *RSA Optimal Asymmetric Encryption Padding (OAEP) using Node.js*. Asecuritysite.com. https://asecuritysite.com/node/node_rsa

We now have X and Y for our padding (M_p). These values can now go into our cipher for:

C=M_p^e (mod N)

and then decrypted with:

P = C^d (mod N)

We can now strip off the padding. To recover the message we first recover the random value (r) from:

r= Y ⊕ H(X)

and then with r we recover the padded message:

m00…0 = X ⊕ G(r)

We then strip off k_1 zeros from the end of this message and recover m.

Coding

The following generates a key pair, and then encrypts and decrypts with OAEP padding [here]:

package main
import (
 "crypto/rsa"
 "crypto/rand"
 "fmt"
    "crypto/sha256"
 "os"
 "strconv"

)

func main() {
 input_string := "This is a test"
 size:=1024
 argCount := len(os.Args[1:])
 if argCount > 0 {
  input_string = string(os.Args[1])
 }
 if argCount > 1 {
  size,_ = strconv.Atoi(os.Args[2])
 }
 private_key, _ := rsa.GenerateKey(rand.Reader, size)
 public_key := &private_key.PublicKey

 message := []byte(input_string)
 label := []byte("")
 hash := sha256.New()

 ciphertext, _ := rsa.EncryptOAEP(hash, rand.Reader, public_key, message,label)
 plainText, _:= rsa.DecryptOAEP(hash, rand.Reader, private_key, ciphertext, label)
 fmt.Printf("\nInput message: [%s]", input_string)
 fmt.Printf("\n\nPrivate key:\nd=%x\nN=%x\n", private_key.D,private_key.N)
 fmt.Printf("\nPublic key:\ne=%x\nN=%x\n", public_key.E,public_key.N)
  fmt.Printf("\n\nCiphertext: %x\n",ciphertext)
 fmt.Printf("\nRSA decrypted to [%s]", plainText)

}

A sample run for a 1,024 bit modulus [here]:

Input message: [Test 123]
Key size: [1024]
Private key:
d=4947e018ea59228c14f41d5bd9d7478a58ec93b27c17802da544a8f419a38e4c53badb0bfbe554121c3504cccee034c1f6ab8d7df91a6600c91c2270bf33ed8606d90cc8e952559d69019f0204afe935898ccf9bb5ca6f8f4c0306c984b880d0640746a65eeaed46201870304a244bdd02397a6fb566ed8e4ef75d9cfb7101e1
N=9f9e55e843f2c4c20e0602733b0a6d0ea36b72f50a173f472d25e5efd275d2cd71875ff6f026cc43a935086345e120e5131b0eda01b47022297ea28478ed40f56ef3245b47b892544d1bf474e27214ba8bc1cef1b57a28c67ba797b7112421599fc212b0fb1c7642988e04789993289d2823e8442c3b338af1eafb25f413477d
Public key:
e=10001
N=9f9e55e843f2c4c20e0602733b0a6d0ea36b72f50a173f472d25e5efd275d2cd71875ff6f026cc43a935086345e120e5131b0eda01b47022297ea28478ed40f56ef3245b47b892544d1bf474e27214ba8bc1cef1b57a28c67ba797b7112421599fc212b0fb1c7642988e04789993289d2823e8442c3b338af1eafb25f413477d

Ciphertext: 9b13fc376e49fa2bc7424a10cc1c1e369a39c271162f6e91780a5e0301b8932a9fe25d6368ff2f7134caa4f536be40fd126b4a6395a91d886b29861d2bc2421f8422b537d0edef0680858afaf1f04ed7d71b045065f68c48696f07385fe8b68c452956f96bf34825766d5bb0ba9dcf8cde4b2dff698e5e1473d4075658c51dd4
RSA decrypted to [Test 123]

If you count the number of hex characters in the modulus (N) you see that we have 256 characters. Two hex characters make one byte, thus we have 128 bytes, and which is 1,024 bits. This will be created from two 512-bit prime numbers. For a 2,048 bit modulus [here]:

Input message: [Test 123]
Key size: [2048]
Private key:
d=955d833eb148ac9ebaee501c037ef35c20ab8b8ba94a089685be37331c9b05c8c1993be0a2953ae48db965a4ad3f283d53e83be6529b7c66c8524bb9a3b224c46e5a3b2ae991b5e8d3685259ade3ced4e00b9762d73cdfb4ead23a947546573fcf149149edbd49a37a708297259b758bd8b54d6f9f023419f60ec2c058643899bb62033f10e09cbef7be9cb270baf10eb017ee1cf01bbd99be2ea8c1f00e966f17010b2d78a9c84f18288827b8cb396a18576bdfb4afda33f95d998b55a3837d78d5fd39ed9ebcb0c3109dad0420fd3fc2bb7dfd267ba1732f1618a76e06e8890d185a4f1b1fa1c635e22c6846f7bb6cb031ae7cf966cdb1a628ee55f0592501
N=ecaa550452c897db1bf83212b6bffbcf73a02ab9c8289cf68525d8d15e72e981c2971394fd9905193e5cd5bd7eea754d4154c1253683872676ea26f7976675b5f896e0f30b548795cceef0df9b5f35252a6c8e57daaa26035b9bab1ff2b2b30e5c71ef2193aee4636661f1f5ecd455f3bc063a2f49e60c93dcc01e981a129943fcb02988a7368f83531d13a1994ee59ed5dc2f1ecf1c7b19667055a94411c1908136921e92990bfcca075df4d6db40692cb737c11a487f2ab066c2f4c7c0a18a75bcf34ab89bd1f36308c0ea00d90028e0f16a9bf1797066d7f0a85efaa181b4ab096fa30b2d1ea3a29d7ca9df0b06b4cf2cd9655d5357d0484a9bffb730ee4f
Public key:
e=10001
N=ecaa550452c897db1bf83212b6bffbcf73a02ab9c8289cf68525d8d15e72e981c2971394fd9905193e5cd5bd7eea754d4154c1253683872676ea26f7976675b5f896e0f30b548795cceef0df9b5f35252a6c8e57daaa26035b9bab1ff2b2b30e5c71ef2193aee4636661f1f5ecd455f3bc063a2f49e60c93dcc01e981a129943fcb02988a7368f83531d13a1994ee59ed5dc2f1ecf1c7b19667055a94411c1908136921e92990bfcca075df4d6db40692cb737c11a487f2ab066c2f4c7c0a18a75bcf34ab89bd1f36308c0ea00d90028e0f16a9bf1797066d7f0a85efaa181b4ab096fa30b2d1ea3a29d7ca9df0b06b4cf2cd9655d5357d0484a9bffb730ee4f

Ciphertext: 39d77ef936abf3b7adebc441e0dff3282c6ee7374f57fe893b21fb5b62ae9766a53c0d7b3272e56132fd4c2bc824a7c7ab4a79a4ab1cbc9e9f83ab8cfc8c1ce138a620e3ec822535a308d2e523d7336adc708a48da96bebea2d789f0359f964065eb5ec42f97d1c399b251bf182aa23983e0b89543f5033e1bce7666b013daf4bb3de077c04f5e3f00128a29ae7d0da7975f7cf2abde49d714e621c484d9a977774fc3e55041fedd59dc8b1fe1b3279293a5688a50a44b2e870dad3c8ec85f961494b637eea331ca669935101784578ac8657e49ecaf4f7fae49b6db006074e022da4c8c1a6b9b254dd218a3f653489a7a60869d77f419acc0be7aabb358108b
RSA decrypted to [Test 123]

If you count the number of hex characters in the modulus (N) you see that we have 512 characters. Two hex characters make one byte, thus we have 256 bytes, and which is 2,048 bytes. This will be created from two 1,024-bit prime numbers.

Conclusion

While not quantum robust, RSA makes our digital world a whole lot more secure and trustworthy. It’s still the workhorse of cybersecurity and will be for many years to come. So, say thanks to the Boxer of cybersecurity. While the elliptic curve dogs still nip at its feet, good old Boxer just keeps going on and on. It will drop its knees in the end, but only due to those evil quantum computers.

And the Elliptic Curve dogs, too, will fall to their knees, and a new workhorse will arise — the lattice workhorse. This new beast will has been proven to be the fastest and most nibble in any race — and as fast as those dogs.

And the next cart-house to replace Boxer? Those will be the McEliece and hash-based signature horses. In fact, we will need two carthorses to replace good old Boxer. These will be old, cumbersome and slow, but they will always do their work, and say, “Must work harder!” They are proven to be hard workers, and have been around for much longer that the nibble footed lattice methods, but they will likely outlast them.

Long live, animal farm! And may it long continue to be a guide in how not to run our society. Believe in freedom of thought and speech, fairness to all, and rein against oppression wherever it occurs. We are born equal, and we should die equal. Oh, and believe in cryptography, too, in building a better digital world!

Subscribe: https://billatnapier.medium.com/membership