## Cryptography: Public Key Cryptography

Topics

- Extended Euclidean Algorithm
- Modular Arithmetic
- Diffie-Hellman Key Exchange
- 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 send a secret message to Bob.
Bob generates a pair of keys: a public key `P _{B}` and
a corresponding secret (private) key

`S`. Alice encodes the message

_{B}`M`using Bob's public key:

_{B}(M).

Bob receives the cipher text `C` and decrypts it using his
secret private key to get the plain message `M` :

_{B}(C) = S

_{B}(P

_{B}(M)) = M.

When Bob wants to send secret message to Alice he does the same using Alice's public and private keys.

### RSA Method

First, let us note that any message can be encoded in a binary string that can be considered a number and thus worked on by mathematical operations. The RSA method is based on the following idea:

^{e}(mod n).

^{d}(mod n) = M

^{e⋅d}(mod n) = M.

I left out the subscript `B` 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.

We will prove

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

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

and hence

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

^{ed}(mod n) = M.

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

for some integer `k`.
So,

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

^{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)

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

### Digital signature

When Bob receives the message from Alice encoded with his public key he is sure that nobody could have read the message because only he can decode the message with his secrete private key. How does he know that the message came indeed from Alice? In fact, he does not know. Anybody could have send him the message encoded with his public key. Public cryptography solves this authenticity problem as well.

Alice first encodes the message `M`
with her secret private key `S _{A}` to get an encrypted
message

`M`:

_{A}_{A}= S

_{A}(M)

Anybody can verify that the message `M _{A}`
comes from Alice by decoding the message with Alice's
public key

`P`:

_{A}_{A}(M

_{A}) = P

_{A}(S

_{A}(M)) = M

After Alice "signed" her message by encoding it with her
secret private key, she encodes the signed message with Bob's
public key to `P _{B}(M_{A}) `
such that only Bob can read it.
After Bob decodes the message using his secret private key:

_{B}(P

_{B}(M

_{A})) = M

_{A}

he obtains the message `M _{A}` signed by Alice
and decodes it using her public key as in (13) to get
the plain message. He is sure that:

- nobody could have read the message
- the message was sent by Alice (authenticity)

In eq. (13) the commutativity of the public-key-cryptography was used. For any pair (P, S) of public and secret private keys it holds true:

This follows from eq. (2b) because

^{e})

^{d}= M

^{e⋅d}= M

^{d⋅e}= (M

^{d})

^{e}= P (S (M) (mod n) .

### Digital signature with hashing

In practice Alice does not sign the whole message but only a short "hash" of the message. This is much more efficient than encoding the long message. The hash of a message is a short hexadeximal string of a fixed length produced by a very efficient one-way function applied to the message. The hash value is a unique fingerprint ("digest") of the message with the following desirable properties:

- It is infeasible to deduce the message from the hash value
- It is infeasible to find two different messages with the same hash value
- A small change to the message results in a large change of the hash value

Examples of hash functions are:

Method | Hash length |
---|---|

MD5 | 128 bits (32 hex-chars) |

SHA1 | 160 bits (40 hex-chars) |

SHA256 | 256 bits (64 hex-chars) |

The hash value can easily be computed. For example, on Windows 10 Powershell:

```
get-filehash -Algorithm SHA1 Message.txt
SHA1 70906938DD01BDFE8EB8D90ED0D17F8FCEEBE57A
```

Sending a secret signed message proceeds as follows:

- Alice produces the hash
`H = H(M)`of the message`M`. - She signes the hash by encoding it with her private key
`S`. She gets the signatute_{A}`G = S`._{A}(H) - She encodes the massage
`M`together with the signatute`G`with Bob's public key and gets the secret message`P`. She sends this encrypted message to Bob. Only Bob can decode it._{B}([M, G])) - Bob receives the encoded message and decodes it using his secret private key:
`S`. Bob has now the message_{B}(P_{B}([M, G])) ) = [M, G]`M`in plain text and the encoded signature`G`. - Bob checks whether the message comes from Alice.
He decodes
`G`using Alice's public key:`P`. He hashes the message_{A}(G) = P_{A}(S_{A}(H)) = H`M`and checks whether`H(M) = H`. If so, he is sure that the message comes from Alice.

### Combining symmetric and asymmetric cryptography

As mentioned above the symmetric key cryptography suffers from the problem of sharing the common secret key by the communicating parties. However, the big advantage of this cryptography is that is very efficient. The assymetric cryptography solves the problem of key distribution at the price of complex and very time consuming algorithm. In practical applications both methods are combined to solve both problems: efficiency and key distribution.

Alice starts the communication with Bob by sending him not the whole encrypted message but only the encrypted common key. The key is usually much shorter than the message and can be encrypted using RSA very efficiently. This key is then used as a common symmetric key during the conversation between Alice and Bob. It is also called the session key.

At the start of any new conversation a new symmetric session key is generated and exchanged using RSA. This approach is also used for the communication of two computers over the internet with the https protocol.

Modern symmetric cryptography is performed with AES algorithms. AES stands for Advanced Encryption Standard (also known as Rijndael).

### Links:

- RSA original paper R.L. Rivest, A. Shamir, and L. Adleman: A Method for Obtaining Digital Signatures and Public-Key Cryptosystems
- Public Key Cryptography (P. Keef and D. Guichard : Introduction to Higher Mathematics)
- RSA: how to factorize N given d (DI Management Services)