Cryptography

Cryptography: Public Key Cryptography

Topics

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_B. Alice encodes the message M using Bob's public key:

C = P_B (M).

(1a)

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

S_B (C) = S_B (P_B (M)) = M.

(1b)

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:

C = P(M) = M^e (mod n).

(2a)

S(C) = C^d (mod n) = M^e⋅d (mod n) = M.

(2b)

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:

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

M^ed (mod n) = M.

(6)

We will prove

M^e⋅d (mod p) = M

(7a)

M^e⋅d (mod q) = M

(7a)

and hence

M^e⋅d (mod p ⋅ g) = M^ed (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)

M^e⋅d (mod p) = M^{k⋅(p-1)⋅(q-1)+1} (mod p)

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

= (M^(p-1) )^k⋅(q-1) ⋅ M (mod p)

= 1^k⋅(q-1) ⋅ M (mod p)

= 1 ⋅ M (mod p)

= M (mod p)

Here we used the Fermat's theorem

M^p-1 = 1 (mod p)

(11)

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:

M_A = S_A (M)

(12)

Anybody can verify that the message M_A comes from Alice by decoding the message with Alice's public key P_A:

P_A (M_A ) = P_A (S_A (M)) = M

(13)

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:

S_B (P_B (M_A )) = M_A

(14)

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:

P (S (M) ) = S (P (M) ) = M

(15)

This follows from eq. (2b) because

S( P(M) ) = (M^e )^d = M^e⋅d = M^d⋅e = (M^d )^e = P (S (M) (mod n) .

(16)

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_A. She gets the signatute 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_B([M, G])). She sends this encrypted message to Bob. Only Bob can decode it.
Bob receives the encoded message and decodes it using his secret private key: S_B (P_B([M, G])) ) = [M, G]. Bob has now the message 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_A(G) = P_A(S_A(H)) = H. He hashes the message 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).