Shor’s Part 1/5: RSA

Shor’s Part 1/5: RSA#

In this notebook, we’ll begin our series on Shor’s algorithm, one of the most famous quantum algorithms. Shor’s algorithm gives an efficient quantum algorithm for factoring integers, and thus, can be used to break cryptographic protocols based on the hardness of factoring integers such as RSA. In preparation for introducing Shor’s algorithm, we’ll begin by reviewing the RSA algorithm.

References

Introduction#

RSA (Rivest–Shamir–Adleman) is a public-key cryptosystem named after its inventors Ron Rivest, Adi Shamir and Leonard Adleman who publicly described the algorithm in 1977.
RSA is commonly used to secure communication on the internet, e.g., Openssl.
Its security assumes the hardness of factoring integers. Thus, if we had an efficient algorithm for factoring integers, we would be able to compromise the security of RSA.

Public Key Cryptosystem#

A public key cryptosystem involves two main concepts.

A public key is a key that is shared openly and can be used by any party to encrypt messages or create signatures.
A private key is a key that is kept secret by its owner and is used to decrypt messages or verify signatures.

One application of a public key cryptosystem is for creating digital signatures. A digital signature is a protocol that enables autheticity and identity verification.

The party whose identity we would like to verify can create a public and private key pair. That party keeps the private key private and distributes the public key openly.
To prove identity, that party can sign a message with their private key and distribute to any third party.
The third party can use the public key to verify the message.

Components of RSA Algorithm#

RSA is a public key cryptosystem that uses the following keys.

The public key is a pair of natural numbers $(N, e)$.
The private key is a natural number $d$.

The keys are generated using basic concepts from number theory (see Appendix: Factoring) using the following steps.

Choose $p$ and $q$ large primes.
- Such $p$ and $q$ can be efficiently obtained with Rabin-Milner’s primality test.
- $p$ and $q$ must be kept private.
Compute $N = pq$.
- $N$ is public.
Compute Euler’s totient function $\phi(N)$.
- Recall $\phi(N) = (p − 1)(q − 1)$.
- $\phi(N)$ is private.
Choose $2 < e < \phi(N)$ relatively prime to $N$, e.g., $e = 7$ when $N = 15$
- $e$ is public.
Solve $1 \equiv de \, (\text{mod} \, \phi(n))$ for d (known as multiplicative modular inverse).
- $d$ is kept private.

We’ll cover the encryption and decryption steps next.

RSA Encryption#

A sender encrypts a message $m$ with RSA by sending the cyphertext $c = m^{e} \, (\text{mod} \, N)$. Note that we only use the public key $(N, e)$ and not the private key $d$.

def naive_rsa_encrypt(public_key: Tuple[int, int], m: int) -> int:
    N, e = public_key
    return (m ** e) % N

RSA Decryption#

A receiver decrypts a cyphertext $c$ by computing $m = c^{d} \, (\text{mod} \, N)$. Note that we use the private key $d$ and part of the public key $N$.

def naive_rsa_decrypt(private_key: Tuple[int, int], c: int) -> int:
    N, d = private_key
    return (c ** d) % N

Optional: Why does it work?#

We’ll show that the RSA encryption and decyption scheme is sound, i.e., the decryption of the encryption of a message $m$ gives the original message. In symbols, we want to show

\[ (m^{e})^{d} \, (\text{mod} \, pq) \equiv m \, (\text{mod} \, pq) \,. \]

This follows from the calculation

\[\begin{align*} (m^{e})^{d} \, (\text{mod} \, pq) & \equiv m^{ed - 1}m \, (\text{mod} \, pq) \tag{rearranging} \\ & \equiv m^{j\phi(N)}m \, (\text{mod} \, pq) \tag{$ed \equiv 1 \, (\text{mod} \, \phi(N)))$} \\ & \equiv (m^{(p-1)(q-1)})^j m \, (\text{mod} \, pq) \tag{Euler's totient} \\ & \equiv (1)^j m \, (\text{mod} \, pq) \tag{Euler's theorem} \\ & \equiv m \, (\text{mod} \, pq) \tag{simplification} \,. \end{align*}\]

Example#

We now walkthrough a toy example to concretize the discussion.

# Step 1: Choose p and q large primes

# For pedagogical purposes, we'll choose small primes
p = 29   
q = 37

# Step 2: Compute N = pq
N = p * q
N

# Step 3: Compute Euler's totient function
phi_N = euler_totient(N)  # 1008
phi_N

# Step 4: Choose 2 < e < euler_totient(N) relatively prime to N
def choose_e(phi_N: int) -> int:    
    while True:
        e = 5
        if math.gcd(e, N) == 1:
            return e
        e += 2
    
e = choose_e(phi_N)
e

# Step 5: Perform multiplicative modular inverse
def solve_mult_mod_inv(x, m):
    # Needed for step 5
    a = 0
    while True:
        if (a * x) % m == 1:
            return a
        a += 1
#         if a % 500 == 0:
#             print(f"Solving mult_mot_inv({x}, {m}) at iteration: {a}")
        
d = solve_mult_mod_inv(e, phi_N)
d

# Form the public and private keys
public_key = (N, e)
private_key = (N, d)
print("public key", public_key)
print("private key", private_key)

public key (1073, 5)
private key (1073, 605)

# Testing the implementation

message = 65
cyphertext = naive_rsa_encrypt(public_key, message)
print(f"Encrypting {message} gives {cyphertext}")
message2 = naive_rsa_decrypt(private_key, cyphertext)
print(f"Decrypting {cyphertext} gives {message2}")

Encrypting 65 gives 1002
Decrypting 1002 gives 65

Aside: Modular Exponentiation#

Computing

\[ b^e \, (\text{mod} \, m) \]

for large $e$ is inefficient and may lead to overflow if we aren’t careful.

Aside: This step is the reason why Shor’s algorithm is actually difficult to implement in practice.

def mod_exp_by_square(base, expon, modulus):
    if expon == 1:
        return base
    elif expon % 2 == 0:
        # Solution 2: Repeated squaring
        res = mod_exp_by_square(base, expon / 2, modulus)
        return (res ** 2) % modulus
    else:
        # Solution 2: Repeated squaring
        res = mod_exp_by_square(base, (expon-1) / 2, modulus)
        return (base * res ** 2) % modulus

print("Naive computation", 23 ** 20 % 345)
print("Smart computation", mod_exp_by_square(23, 20, 345))

Naive computation 46
Smart computation 46

def less_naive_rsa_encrypt(public_key: Tuple[int, int], m: int) -> int:
    N, e = public_key
    return mod_exp_by_square(m, e, N)

def less_naive_rsa_decrypt(private_key: Tuple[int, int], c: int) -> int:
    N, d = private_key
    return mod_exp_by_square(c, d, N)

message = 65
cyphertext = less_naive_rsa_encrypt(public_key, message)
print(f"Encrypting {message} gives {cyphertext}")
message2 = less_naive_rsa_decrypt(private_key, cyphertext)
print(f"Decrypting {cyphertext} gives {message2}")

Encrypting 65 gives 1002
Decrypting 1002 gives 65

Putting it all together#

The code below gathers the steps needed for a naive implementation of RSA.

def naive_generate_rsa_key_pair() -> Tuple[Tuple[int, int], Tuple[int, int]]:
    # Step 1: Pick primes (small for pedagogical purposes)
    primes = np.array(prime_seive(50)[1:])  # Skip 2
    np.random.shuffle(primes)
    p, q = primes[0], primes[1]
    
    # Step 2: Compute N = pq
    N = p * q
    
    # Step 3: Compute Euler's totient function
    phi_N = euler_totient(N)
    
    # Step 4: Choose 2 < e < euler_totient(N) relatively prime to N
    e = choose_e(phi_N)
    
    # Step 5: Perform multiplicative modular inverse
    d = solve_mult_mod_inv(e, phi_N)
    
    # Output
    print(f"p: {p}, q: {q}, N: {N}, phi_N: {phi_N}, e: {e}, d: {d}")

    # Return
    public_key = (N, e)
    private_key = (N, d)
    return public_key, private_key

public_key2, private_key2 = naive_generate_rsa_key_pair()

message = 65
cyphertext = less_naive_rsa_encrypt(public_key, message)
print(f"Encrypting {message} gives {cyphertext}")
message2 = less_naive_rsa_decrypt(private_key, cyphertext)
print(f"Decrypting {cyphertext} gives {message2}")

p: 29, q: 19, N: 551, phi_N: 504, e: 5, d: 101
Encrypting 65 gives 1002
Decrypting 1002 gives 65

Shor’s Algorithm Preview#

Shor’s algorithm is a polynomial time algorithm for factoring integers. It is comprised of

quantum order finding to efficiently solve the order finding problem,
a classical continued fractions algorithm for interpreting the results of quantum order finding, and
a classical reduction for solving integer factorization in terms of a solution to the order finding problem.

In the next series of notebooks, we will study quantum order finding in more detail. This algorithm is comprised of several quantum sub-routines:

the Quantum Fourier Transform (QFT),
modular exponentiation, and
quantum phase estimation (QPE). We will then put this all together to implement Shor’s algorithm end-to-end.

Summary#

We reviewed the RSA public key cryptosystem. The security of the RSA public key cryptosystem depends on the hardness of factoring integers.
We previewed Shor’s algorithm, which gives an efficient quantum algorithm for factoring integers.