11.1. 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\)

    • \(d = b'M + b\).

    • \(n = \left(ed -1 \right) / M\).

    • Keep \(M\) and \(d\) secret, while \(e\) and \(n\) are public.

  3. The public key is \(\left( e, n\right)\)

  4. The private key is \(\left( d, n\right)\)

  5. Let your message be an integer \(m\) (\(m\) must be less than \(n\) and share no factors with \(n\))

  6. The encrypted message is \(e \cdot m \pmod{n}\)

  7. 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{split} \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} \end{split}\]

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