import sys
sys.path.insert(0, '../../')

from toolkit import textToBinary, binaryToText

KidRSA¶

This section will cover one type of public key system, KidRSA named by Neal Koblitz in Cryptologia, Vol. 21, No. 4 after the full-blown RSA system to be covered in a future section. It shares many of the same features and mathematics as RSA, but is a bit easier to understand as a stepping-stone into public key cryptography. It’s important to note that KidRSA is not secure! However, it is much more secure than any of the systems that have been previously covered, and has all the benefits of not having to worry about key exchange.

The keys in KidRSA are pairs of integers, where the public key is $\left( e, n\right)$ (typically for encryption) and the private key is $\left( d, n \right)$ (typically for decryption). The “one way” function in KidRSA is determining multiplicative inverses in a particular modulo. You should recall from the section on Affine Ciphers, that the only way we were able to determine the multiplicative inverse in modulo 26 was to try all the possible inverses between 0 and 25, and multiply them with the key value to determine if it was actually an inverse. It didn’t take too long in modulo 26, but imagine if it was in modulo 104659, or 3267000013. That would take a lot longer to determine an inverse for a particular value. However, we’ll see that it’s not too difficult to quickly generate two integers that we know to be inverses in a modulo of our choosing. If we generate two numbers that are multiplicative inverses of each other, then one number will be part of the public key and the other part of the private key. This is the perfect set up for a public key cryptography system!

It’s easy to generate two numbers that are multiplicative inverses of each other in a given modulo
It’s difficult to determine one of the two numbers if you know the other

The Algorithm¶

Let’s walk through how to generate a pair of keys, $\left( e, n\right)$ and $\left( d, n\right)$ .

Choose 4 integers, $a, b, a', b'$ , and keep these secret!
Compute:
- $M = ab - 1$
- $e = a'M + a$
- $d = b'M + b$ .
- $n = \left(ed -1 \right) / M$ .
- Keep $M$ and $d$ secret, while $e$ and $n$ are public.
The public key is $\left( e, n\right)$
The private key is $\left( d, n\right)$
Let your message be an integer $m$ ( $m$ must be less than $n$ and share no factors with $n$ )
The encrypted message is $e \cdot m \pmod{n}$
To decrypt, multiply the encrypted message by $d$ and reduce by modulo $n$

Example #1 (Small Numbers)¶

Let’s start by working through an example where you’ll encrypt and decrypt a message using this system. This example uses relatively small numbers that can be computed using either mental math or a simple calculator.

Let $a = 5, b = 3, a' = 7, b' = 5$ . Next, you can compute that

$M = 5 \cdot 3 - 1 = 14$
$e = 7 \cdot 14 + 5 = 103$
$d = 5 \cdot 14 + 3 = 73$
$n = \left( 103 \cdot 73 -1 \right) / 14 = 537$

You now know that the public key is $\left( 103, 537 \right)$ and the private key is $\left( 73, 537 \right)$ .

A friend wants to encrypt a very simple message, the single character a. They would start by converting it to binary using ASCII to obtain, 01100001 and then to decimal 97. Next, compute $97 \cdot 103 \pmod{537}$ , which gives 325. Your friend could send this encrypted message, 325 as an integer or convert to binary 00000001 01000101 or as the base64 characters AUU= (all these representations are equivalent).

Upon receiving the message, you would use the integer value, 325 and compute $325 \cdot 73 \pmod{537}$ which returns 93, the original value of the plaintext message. This value can be converted back to text using ASCII to retrieve the plaintext message a.

Example #2 (Large Numbers)¶

This example will use larger numbers which may require Python or other specialized mathematics software to compute values. Such software will also be needed to display all the digits of your computation, as most hand held calculators can only display between 10-12 digits..

Let $a = 1933, b = 2609, a' = 1229,$ and $b' = 1373$ .

$M = \left(1933\right) \left(2609\right) - 1 = 5,043,196$
$e = \left(1229\right) \left(5043196\right) + 1933 = 6,198,089,817$
$d = \left(1373\right) \left(5043196\right) + 2609 = 6,924,310,717$
$n = \left(6198089817 \cdot 6924310717 - 1 \right) / 5043196 = 8,509,980,525,203$

We take our plaintext message NCSSM and convert to binary 01001110 01000011 01010011 01010011 01001101 which as the decimal representation of $m = 336,136,983,373$ . Since this message, $m$ , is less than $n$ and is relatively prime to $n$ , we can proceed.

To encrypt the message, multiply $m$ and $e$ , and reduce modulo $n$ . Here we’ll use Python to do this quickly.

print( (336136983373 * 6198089817) % 8509980525203 )

2376855076134

This is our encrypted message. As binary it would be represented as 00000010 00101001 01100111 10011010 00111101 00100110 or in base64 as Ailnmj0m.

To confirm decryption works as well, take the encrypted message as a decimal, 2376855076134 and multiply by $d$ and reduce modulo $n$ .

print( (2376855076134 * 6924310717) % 8509980525203 )

336136983373

Which returns the plaintext message $m$ in decimal format.

Why Does This Work?¶

While the example above illustrates that we were able to successfully encrypt and decrypt a message with this system, it doesn’t explain why this system works. Let’s dig into the mathematics.

After choosing $a, b, a',$ and $b'$ at random (although choosing prime numbers here will be helpful down the road), we first compute $e, d,$ and $n$ by way of the number $M$ (notice all three of the values that are part of the keys are based on this value of $M$ ). To compute $n$ we start with:

\begin{align} ed - 1 & = \underbrace{ \left( a'M + a \right) \left(b'M + b \right) }_{\text{multiply}} - 1 \\ & = a'b'M^2 + \underbrace{ ab'M + a'bM }_{\text{factor out } M}+ ab - 1 \\ & = a'b'M^2 + \left( ab' + a'b \right)M + \underbrace{ ab - 1 }_{\text{substitute } M = ab - 1} \\ & = \underbrace{ a'b'M^2 + \left( ab' + a'b \right)M + M }_{\text{factor out } M} \\ & = M \left( a'b'M + ab' + a'b + 1 \right) \\ \end{align}

(1)

Since $ed - 1$ is the product of $M$ and $\left( a'b'M + ab' + a'b + 1 \right)$ we now know that:

$ed - 1$ must be divisible by $M$
$ed - 1$ must also be divisible by $\left( a'b'M + ab' + a'b + 1 \right)$ ,
Since $n = \left(ed - 1\right) / M$ , the equation can be rearranged to determine that $nM = \left(ed - 1\right)$ .
- Since $\left( ed - 1 \right) = nM = \left( a'b'M + ab' + a'b + 1 \right) M$ , we can deduce that $n = \left( a'b'M + ab' + a'b + 1 \right)$
- Therefore, $ed - 1$ is also divisible by $n$ .
Since $ed - 1$ is divisible by $n$ , we know that $0 \equiv ed - 1 \pmod{n}$ . Therefore we also know that $1 \equiv ed \pmod{n}$ , which confirms that $e$ and $d$ are guaranteed to be multiplicative inverses in modulus $n$ .

This list of results is incredibly powerful and important. It explains why this algorithm will generate $e$ and $d$ such that they are multiplicative inverses of each other in modulus $n$ , and why $n$ is guaranteed to be an integer. Now that we know $e$ and $d$ are guaranteed to be inverses, it should make sense that when we take an encrypted message, $e \cdot m \pmod{n}$ and then multiply by $d$ , which results in $d \cdot e \cdot m \pmod{n}$ , the expression simplifies to $m \pmod{n}$ , since $d \cdot e = 1$ . Thus, multiplying by $d$ will decrypt the message and reveal the original value.

Notice that it would be very difficult to determine $e$ using only the public information $d$ and $n$ . You would need to multiply $d$ by all possible values of $e$ and reduce by modulus $n$ to check if $d$ and $e$ were inverses, which is extremely inefficient (for now).

Weakness of KidRSA¶

The math behind KidRSA ensures that correctly generated values of $e, d,$ and $n$ can be used to encrypt and decrypt messages without both parties having the full information about the public and private key pair. It also makes it incredibly difficult for an eavesdropper to determine $d$ when they only have $e$ and $n$ . However, there’s some even more advanced mathematics that benefits the eavesdropper! The Euclidean Algorithm can be used to quickly and easily calculate multiplicative inverses in any modulus, and thus explains why KidRSA is an insecure system.

We’ll see that KidRSA is improved upon in real RSA, where it’s not about finding multiplicative inverses such that $1 \equiv e \cdot d \pmod{n}$ but rather exponential inverses such that $1 \equiv e^d \pmod{ \varphi(n)}$ , where $\varphi(n)$ is very hard for a computer to calculate if $n$ is large.

Exercise for the Reader¶

Write a function that takes in a list of 4 numbers that represent $a, b, a',$ and $b'$ and returns a list containing $e, d,$ and $n$ .

Why Does This Work? The Little Details¶

Now that you understand how the key generation works, the last bit of mathematics you need to understand relates to the actual encryption and decryption processes. This next part will further explain how we know that $e$ and $d$ are inverses of each other.

To encrypt a message $m$ , you would multiply by $e$ and reduce modulo $n$ . Reducing the encrypted message, $m \cdot e$ by modulo $n$ , put another way, is equivalent to finding another integer that is smaller than $m \cdot e$ by some factor of $n$ . We can write that reduction as $m \cdot e - k \cdot n$ for some value of $k$ that ensures the result is between 0 and $n$ . For example, if $m = 13, e = 7$ and $n=29$ , then reducing $13 \cdot 7 \pmod{29}$ is equivalent to subtracting off multiples of 29 until $7 \cdot 13$ is between 0 and 29. In this example, $91 - \left( 3 \right) 29 = 4$ , so by setting $k=4$ we know that $4 \equiv 91 \pmod{29}$ , and 4 will be the encrypted message. The expression $m \cdot e - k \cdot n$ is a general representation for an encrypted message that we will transmit using KidRSA.

To decrypt the message $m \cdot e - k \cdot n$ , you multiply by $d$ and reduce modulo $n$ . Multiplying yields the following result:

\begin{align} d \left(m \cdot e - k \cdot n\right) & = med - kdn & \text{distribute } d\\ & = m \cdot \left(nM + 1\right) - kdn & \text{substitute for } ed \\ & = mnM + m - kdn & \text{distribute } m \\ & = m + mnM - kdn & \text{rearrange terms} \\ & = m + \left( mM - kd \right)n & \text{factor out } n\\ \end{align}

(2)

Which implies that $d \left(m \cdot e - k \cdot n\right)$ is equal to $m$ plus some integer multiple of $n$ . Since we know that $m$ is already less than $n$ by the rules of the system, then we know that $m$ is equivalent reducing by modulo $n$ is equivalent to subtracting off multiplies of $n$ until the value is less than $n$ , we know that $m \equiv m + \left( M - kd \right)n \pmod{n}$ , confirming that the decryption process will always yield the original message, $m$ .