## 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 `P _{A}` and
a corresponding secret (private) key

`S`. Bob encodes the message

_{A}`M`using Alice's public key:

_{A}(M).(1a)

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

_{A}(C) = S

_{A}(P

_{A}(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:

^{e}(mod n).(2a)

^{d}(mod n) = M

^{e⋅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`:

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

`e` is computed to be the multiplicative inverse:

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

^{ed}(mod n) = M.(6)

We will prove

^{e⋅d}(mod p) = M(7a)

^{e⋅d}(mod q) = M(7a)

and hence

^{e⋅d}(mod p ⋅ g) = M

^{ed}(mod n) = M.(8)

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

for some integer `k`.
So,

^{e⋅d}(mod p) =

^{k⋅(p-1)⋅(q-1)+1}(mod p)

^{k⋅(p-1)⋅(q-1)}⋅ M

^{1}(mod p)

^{(p-1)})

^{k⋅(q-1)}⋅ M (mod p)

^{k⋅(q-1)}⋅ M (mod p)

Here we used the Fermat's theorem

^{p-1}= 1 (mod p) (11)

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

### Links:

- RSA original paper R.L. Rivest, A. Shamir, and L. Adleman: A Method for Obtaining Digital Signatures and Public-Key Cryptosystems
- P. Keef and D. Guichard : Introduction to Higher Mathematics
- The Euclidean Algorithm and the Extended Euclidean Algorithm (DI Management Services)

## New Comment