Search
KidRSA

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)$.

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

Example #1 (Easy)

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 simply base64 text message a. They would start by converting it to binary, 011010 and then to decimal 26, and then computes $26 \cdot 103 \pmod{537}$, which gives $530$. You friend could send this encrypted message, $530$ as an integer or convert to binary 1000010010 or as the base64 characters IS (all these representations are equivalent).

Upon receiving the message, you would use the integer value, $530$ and compute $ 530 \cdot 73 \pmod{537}$ which miraculously returns $26$, which we can convert back to the plaintext message a.

Example #2 (Hard)

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 001101000010010010010010001100 which as a decimal integer is $m = 218,702,988$. 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( (218702988 * 6198089817) % 8509980525203 )
2984971737732

This is our encrypted message. As binary it would be represented as 101011011011111110001011100001101010000100 or in base64 as rb+LhqE.

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

print( (2984971737732 * 6924310717) % 8509980525203 )
218702988

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} $$

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{n}$, which is much, much, more difficult to do.

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