avatar

Brief Introduction to RSA Cryptosystem

This is a note on the RSA cryptosystem which covered by Prof. Lauchie MacDonald's course MATH 312 at University of British Columbia.

Public Key Cryptography

In a "public key cryptosystem" there are two keys: a public key and a private key. The public key is used to encrypt messages, and the private key is used to decrypt messages. The public key is made public, and the private key is kept secret.

We denote an encryption procedure EE, a decryption procedure DD. They has four properties:

  1. Deciphering a ciphertext yields the original plaintext MM: D(E(M))=MD(E(M)) = M.
  2. Both EE and DD are efficiently computable.
  3. By publicly revealing EE, it is not easy to compute DD.
  4. If a message MM is first deciphered and then enciphered, MM is obtained: E(D(M))=ME(D(M)) = M.

Encryption and Decryption Methods

Notations and Definitions

Let's denote:

  • MM as the message or plaintext
  • CC as the ciphertext
  • EE as the encryption procedure
  • DD as the decryption procedure
  • The pair of positive integers (e,n)(e, n) as the public key
  • The pair of positive integers (d,n)(d, n) as the private key

The encryption and decryption algorithm EE and DD are defined as:

C≡E(M)≡Me( mod n), for a message MD(C)≡Cd( mod n), for a ciphertext C\begin{aligned} C \equiv & E(M) \equiv M^e(\bmod n), \text { for a message } M \\ & D(C) \equiv C^d(\bmod n), \text { for a ciphertext } C \end{aligned}

How to Choose the Keys

The public key (e,n)(e, n) and the private key (d,n)(d, n) are chosen as follows:

  1. You first compute nn as the product of two large primes pp and qq, i.e. n=pqn = pq.
  2. Pick a large integer dd that is relatively prime to (p−1)(q−1)(p - 1)(q - 1), i.e. gcd⁡(d,(p−1)(q−1))=1\gcd(d, (p - 1)(q - 1)) = 1.
  3. The integer ee is finally computed from dd and (p−1)(q−1)(p - 1)(q - 1) by solving the equation ed≡1( mod (p−1)(q−1))ed \equiv 1(\bmod (p - 1)(q - 1)). Note there must be a solution for ee because gcd⁡(d,(p−1)(q−1))=1\gcd(d, (p - 1)(q - 1)) = 1.

The Underlying Mathematics

We demonstrate the correctness of the deciphering algorithm using an identity due to Euler and Fermat: for any integer (message) MM which is relatively prime to nn,

Mϕ(n)≡1( mod n)M^{\phi(n)} \equiv 1(\bmod n)

where ϕ(n)\phi(n) is the Euler's totient function, which is the number of positive integers less than nn and relatively prime to nn. For prime numbers pp,

ϕ(p)=p−1\phi(p) = p - 1

In our case, because the totinent function is multiplicative, we have

ϕ(n)=ϕ(pq)=ϕ(p)ϕ(q)=(p−1)(q−1)\begin{aligned} \phi(n) &= \phi(pq) \\ &= \phi(p)\phi(q) \\ &= (p - 1)(q - 1) \end{aligned}

Since dd is relatively prime to ϕ(n)\phi(n), there exists an multiplicative inverse ee of dd modulo ϕ(n)\phi(n), i.e.

ed≡1( mod ϕ(n))ed \equiv 1(\bmod \phi(n))

Now, we want to prove that D(E(M))=MD(E(M)) = M and E(D(M))=ME(D(M)) = M.

D(E(M))=(E(M))d( mod n)=(Me)d( mod n)=Med( mod n)=M1+kϕ(n)( mod n)=M(Mϕ(n))k( mod n)=M( mod n)\begin{aligned} D(E(M)) &= (E(M))^d(\bmod n) \\ &= (M^e)^d(\bmod n) \\ &= M^{ed}(\bmod n) \\ &= M^{1 + k\phi(n)}(\bmod n) \\ &= M(M^{\phi(n)})^k(\bmod n) \\ &= M(\bmod n) \end{aligned}

The proof of E(D(M))=ME(D(M)) = M is similar.

Now, we have proved that the encryption and decryption algorithm EE and DD are correct.