RSA Cryptography Simplified

I will demonstrate how to make a simple cryptographic algorithm using prime number factorization in the style of RSA. For this example we will be using smaller prime numbers where in real world these would rely on very large prime numbers hundreds of digits long.

Building blocks

1. Two Prime Numbers \(p, q\)
2. Product \(N = p \cdot q\)
3. Euler’s Totient Function \(\phi(N) = (p - 1)(q - 1)\)
4. Encryption Key \(\begin{equation} e = \begin{cases} 1 < e < \phi(N)\\ e \perp N, e \perp \phi(N) \end{cases} \end{equation}\) We say \(a\) is mutually prime with \(b\) as \(a \perp b\)
5. Decryption Key \(d = (d \cdot e)\mod\phi(N) = 1\)

Notes

\(x \mod y\) is the Modulo function which we can calculate by dividing 2 numbers x and y and taking the reminder. For example:

\[6\mod4 = 2\] \[6\mod5 = 1\] \[6\mod6 = 0\]

Totient Function

The original RSA paper uses Euler’s Totient Function. The real world implementation uses Carmichael’s Totient Function instead.

Example

1. Pick two prime numbers p and q

   \[p = 13, q = 41\]

2. N is the product of p and q which is the divisor used in our modulo function

   \[N = p \cdot q\] \[N = 533\]

3. Use Euler’s Totient Function

   \[\phi(N) = (13 - 1)\cdot(41 - 1)\] \[\phi(N) = 480\]

4. Choose e (encryption key)

   First Condition:

   \[1 < e < \phi(N)\] \[\{2,3,4,5,6,7,8,9,\dots,479\}\]

   Second Condtion:

   \[e \perp N, e \perp \phi(N)\]

   We choose:

   \[e = 37\] \[37 \perp 533\] \[37 \perp 480\]

   37 and 480 have no common factor greater than 1.

   Method:

   \[n = 480 = \{1, 2, 3, 4, 5, 6, 8, 10, 12, 15, 16, 20, 24, 30, 32, 40, 48, 60, 80, 96, 120, 160, 240, 480\}\] \[n = 533 = \{1, 13, 41, 533\}\] \[n = 37 = \{1, 37\}\]

5. Choose d (decryption/secret key)

   \[d = (d \cdot e)\mod\phi(N) = 1\] \[(d \cdot 37)\mod 480 = 1\] \[(13 \cdot 37)\mod 480 = 1\]

6. We arrive with the following key pairs:

   \[e = (37, 533)\] \[d = (13, 533)\]

Encryption

From our previous example we came up with the following key pairs:

1. Encryption Key

   \[e = (37, 533)\]

2. Decryption Key

   \[d = (13, 533)\]

3. Given secret text “X” which converts to the Integer ordinal \(120\)

4. The encryption function to generate the ciphertext \(C\) we encrypt secret \(S\)

   \[C = S^e \mod 533\] \[C = 120^{37} \mod 533\] \[C = 3\]

Decryption

1. Using decryption key

   \[d = (13, 533)\]

   Ciphertext:

   \[C = 3\]

2. We can decrypt using:

   \[S = C^{d} \mod N\] \[S = 3^{13} \mod 533\] \[S = 120\]

Explanation

This works because of the Fundamental Theorem of Arithmetic which states that any number \(n > 1\) can be expressed as a product of prime numbers (i.e. \(77 = 7 \cdot 11\))

This gives us the following properties:

1. It’s easy to find the product \(N\) of two very large prime numbers.
2. It’s very difficult to find the 2 prime numbers that would produce the product \(N\).

Which gives us the building blocks needed to create a system that is easy to encrypt but difficult to decrypt. The concept of one transformation being easy while going the opposite direction being difficult underpins one of the key requirements of a cryptographic system. One would say that it’s easy for someone to encrypt a file given a public encryption key \(e\) but without decryption key \(d\) it would be computationally time consuming to decrypt without.

Cryptographic hashing works under the same premise that it is easy to generate Digest \(D\) but it is difficult to find the original message.

One good way of thinking about all of this is to think about the game Sudoku. It is easy to verify that one’s solution to the puzzle is correct while it will take time to find the correct solution.

---