  EN → DE A-AA+ Sitemap Search

## Public Key Cryptography

I present the mathematics behind the RSA public key cryptography.

### Introduction

Until about 1970, cryptography was based on sharing a common secret key between the communicating parties. This cryptography is called symmetric key or secret key cryptography. The problem with this approach is the exchange of the secret key between the two parties. In 1976, W. Diffie and M. Hellman published a revolutionary method for establishing a secret key over a public channel and layed the basis for public key cryptography.

In 1978, R.L. Rivest, A. Shamir, and L. Adleman published a method that does not need the key exchange at all. The method uses a pair of keys for each party: a public key for encryption and a private key for decryption. This new type of cryptography is called the assymmetric cryptography and the method is called the RSA method.

Suppose that Alice wants to receive secret message from Bob. She generates a pair of keys: a public key PA and a corresponding secret (private) key SA. Bob encodes the message M using Alice's public key:

C = PA (M).
(1a)

Alice receives the cipher text C and decrypts it using her private key to get the plain message M :

SA (C) = SA (PA (M)) = M.
(1b)

When Bob wants to receive secret message from Alice he does the same using his own public and private keys.

### RSA Method

The RSA method is based on the following idea:

C = P(M) = Me (mod n).
(2a)
S(C) = Cd (mod n) = Me⋅d (mod n) = M.
(2b)

The message M is considered to be a number. I left out the subscript A for clarity. The numbers e, n build the public key of Alice, such that anybody can encrypt a message for her. The number d is kept secret by Alice and it enables her to decrypt the ciphertext. The pair d, n is considered the secret key. The quintessence of RSA is how to construct the numbers d, e, n such that the equations (2) hold true.

The modulus n is chosen to be a product of two primes p, q:

n = p ⋅ q.
(3)

Although n will be public, the factors p, q are hidden. The number d is chosen such that

gcd(d, (p - 1) ⋅ (q - 1)) = 1.
(4)

e is computed to be the multiplicative inverse:

e ⋅ d ≡ 1 (mod (p - 1) ⋅ (q - 1)).
(5)

Such a number e exists because of equation (4). With the above choices we prove that

Med (mod n) = M.
(6)

We will prove

Me⋅d (mod p) = M
(7a)
Me⋅d (mod q) = M
(7a)

and hence

Me⋅d (mod p ⋅ g) = Med (mod n) = M.
(8)

Let us start with the equation (7a). From equation (5) we have

e⋅d = k ⋅ (p-1) ⋅ (q-1) + 1
(9)

for some integer k. So,

(10)
Me⋅d (mod p) = Mk⋅(p-1)⋅(q-1)+1 (mod p)
= Mk⋅(p-1)⋅(q-1) ⋅ M1 (mod p)
= (M(p-1) )k⋅(q-1) ⋅ M (mod p)
= 1k⋅(q-1) ⋅ M (mod p)
= 1 ⋅ M (mod p)
= M (mod p)

Here we used the Fermat's theorem

Mp-1 = 1 (mod p)
(11)

because p is prime. The equation (7b) is proved analogously and the equation follows.