Public-Key Encryption (Optional)

CS1302 Introduction to Computer Programming

This notebook will introduce the idea of public-key (asymmetric key) cryptography called the RSA algorithm.

Motivation¶

What is public key encryption?

Suppose there is one receiver trying to receive private messsages from multiple senders.

Solution to Exercise 1

Easy to share keys: Encryption key can be shared to all senders publicly.
Easy to store keys: Only the receiver needs to know the private key.

Is public key encryption possible?

Unfortunately, public key encryption is an invertible function given a public key:

YOUR ANSWER HERE

How to make public key encryption secure?

We can make it computationally infeasible to invert $E(\cdot, k_e)$ unless with the private key $k_d$ is available. Such a function is called the trapdoor function. An example of a trapdoor function is:

As the size of $p$ and $q$ increases, the time required to factor $n$ increases dramatically as illustrated here.

RSA Algorithm¶

How to encrypt/decrypt?

The encryption and decryption use modulo exponentiation instead of addition:

\begin{align} E(x, k_e) &:= x^e \bmod n && \text{where }k_e:=(e,n)\\ D(c, k_d) &:= c^d \bmod n && \text{where }k_d:=(d,n), \end{align}

(4)

and $e$ , $d$ , and $n$ are positive integers.

Computing exponentiation can be fast using repeated squaring. The built-in function pow already has an efficient implementation:

%%timeit
x, e, n = 3, 2 ** 1000000, 4
pow(x, e, n)

%%timeit
def modulo_power(x, e, n):
    # YOUR CODE HERE
    raise NotImplementedError()


x, e, n = 3, 2 ** 1000000, 4
pow(x, e, n)

How to ensure decryptability?

For $x = D(E(x, k_e), k_d) = x^{ed} \bmod n$ , we need $0\leq x < n$ and

x^{ed} \equiv x \mod n.

(5)

Solution to Exercise 4

\begin{align} x &= D(E(x, k_e), k_d) \\ &= (x^{e} \bmod n)^{d} \bmod n \\ &= x^{ed} \bmod n. \end{align}

(6)

RSA makes use of the following result to choose $(e, d, n)$ :

There are elegant and elementary combinatorial proofs.

Since (7) implies $x^p = x \bmod p$ , can we choose

$n=p$ and
$ed=p$

to satisfies (5)?

No because the private key can then be easily computed from the public key: $d = n/e$ .

Alternatively, by raising (7) to the power of any integer $m$ ,

x^{m(p-1)} \equiv 1 \mod p.

(8)

Can we have $n=p$ and $ed \equiv 1 \bmod p-1$ ?

No because $d$ is the modular multiplicative inverse of $e$ , which is easy to compute, e.g., using pow with an exponent of -1. In particular, for prime modulus here, the inverse is $d=e^{p-2}\bmod p$ :

e, n = 3, 7
d = pow(e, -1, n)
d, e * d % n == 1 and d == e ** (n - 2) % n

How to make it difficult to compute $d$ ?

RSA makes use of the hardness of factoring a product of large primes to create the desired trapdoor function.

In particular, with $m(p-1)$ in (8) being the least common multiple $\operatorname{lcm}(p-1,q-1)$ for another prime number $q$ , we have

\begin{align} x^{\operatorname{lcm}(p-1, q-1)} &\equiv 1 \mod p && \text{and}\\ x^{\operatorname{lcm}(p-1, q-1)} &\equiv 1 \mod q && \text{by symmetry.} \end{align}

(9)

This implies $x^{\operatorname{lcm}(p-1, q-1)} - 1$ is divisible by both $p$ and $q$ , and so

x^{\operatorname{lcm}(p-1, q-1)} \equiv 1 \mod p q.

(10)

Raising both sides to the power of any positive integer $m$ give:

Although $d$ is still the modulo multiplicative inverse of $e$ , it is with respect to $\operatorname{lcm}(p-1, q-1)$ , which is not easy to compute without knowing the factors of $n$ , namely $p$ and $q$ . It can be shown that computing $d$ is as hard as computing $\operatorname{lcm}(p-1, q-1)$ or factoring $n$ .

How to generate the public key and private key?

By (12), we can compute $d$ as the modulo multiplicative inverse of $e$ . How to choose $e$ then?

We can choose any $e \in \{1, \dots, \operatorname{lcm}(p-1, q-1)\}$ such that $e$ does not divide $\operatorname{lcm}(p-1, q-1)$ .

YOUR ANSWER HERE

The following function randomly generate the e, d, n for some given prime numbers p and q:

from math import gcd
from random import randint


def get_rsa_keys(p, q):
    n = p * q
    lcm = (p - 1) * (q - 1) // gcd(p - 1, q - 1)
    while True:
        e = randint(1, lcm - 1)
        if gcd(e, lcm) == 1:
            break
    d = pow(e, -1, lcm)
    return e, d, n, lcm

Note that

\operatorname{lcm}(p-1, q-1) = \frac{(p-1)(q-1)}{\operatorname{gcd}(p-1, q-1)}.

(13)

As an example, if we choose two prime numbers $p=17094589121$ and $q=1062873761$ :

e, d, n, lcm = get_rsa_keys(17094589121, 1062873761)
e, d, n, e * d % lcm == 1

The integer $1302$ can be encrypted as follows:

x = 1302
c = pow(x, e, n)
print(f'The plain text "{x}" has been encrypted into "{c}".')

With the private key $k_d$ , the ciphertext can be decrypted easily as

output = pow(c, d, n)
print(f'The cipher "{c}" has been decrypted into "{output}".')

Exercise 6

Using the rsa module, generate a RSA key pair with suitable length and then use it to encrypt and decrypt your own message. You can install the module by running the following command in a terminal:

pip install rsa