Science
Copyright © 2022 Jiri Kriz, www.nosco.ch

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 PB and a corresponding secret (private) key SB. Alice encodes the message M using Bob's public key:

C = PB (M).
(1a)

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

SB (C) = SB (PB (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) = Me (mod n).
(2a)
S(C) = Cd (mod n) = Me⋅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

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.

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 SA to get an encrypted message MA:

MA = SA (M)
(12)

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

PA (MA ) = PA (SA (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 PB(MA) such that only Bob can read it. After Bob decodes the message using his secret private key:

SB (PB (MA )) = MA
(14)

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

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) ) = (Me )d = Me⋅d = Md⋅e = (Md )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:

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:

  1. Alice produces the hash H = H(M) of the message M.
  2. She signes the hash by encoding it with her private key SA. She gets the signatute G = SA(H).
  3. She encodes the massage M together with the signatute G with Bob's public key and gets the secret message PB([M, G])). She sends this encrypted message to Bob. Only Bob can decode it.
  4. Bob receives the encoded message and decodes it using his secret private key: SB (PB([M, G])) ) = [M, G]. Bob has now the message M in plain text and the encoded signature G.
  5. Bob checks whether the message comes from Alice. He decodes G using Alice's public key: PA(G) = PA(SA(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).

Links: