Module 4.3

Public-key cryptography

In symmetric encryption the same key is used both for encryption and decryption. In public key cryptography we have a separate key for encryption and another one for decryption. This makes sense if it is hard to determine the decryption key even if the encryption key is known.

If this is the case then you could tell everybody how to encrypt messages they want to send to you but still only you would know how to decrypt these messages. This explains the name: encryption key could be made public while the corresponding decryption key still remains secret.

Typically the keys are longer and the algorithms are slower in public-key cryptography than in the symmetric encryption. But with public-key cryptography you are able to do things which cannot be done with symmetric encryption.

The above mentioned possibility for even strangers to send confidential messages to you is one such thing. Digital signature is another such thing: Using public-key cryptography it is possible to sign messages electronically and to authenticate users and their messages.

Let us denote by amodba \mod b the remainder when aa is divided by bb. The bb here is called the modulus. For example, 12mod5=212 \mod 5 = 2 and 77mod8=577 \mod 8 = 5.

Also, we make use of prime numbers, shortly primes. An integer, larger than 1, is a prime if it is only divisible by 1 and itself. For example, 7, 101 and 7823 are primes but 6, 15 and 100 are not.

Given integers aa, bb and cc, it is easy (at least in principle) to calculate abmodca^b \mod c. This modular exponentiation is relatively easy to do even when the integers aa, bb and cc are very big. With big aa and bb the power aba^b becomes huge. Luckily we do not have to compute this huge number at all. Instead, it is possible to compute the remainder for each intermediate value before continuing. Let us take a simple example: a=2a = 2, b=60b = 60, c=1003c = 1003. Now ab=(210)6a^b = (2^{10})^6.

We first compute 210=10242^{10}=1024. Then we take the remainder of this intermediate result: 1024mod1003=211024 \mod 1003 = 21. Next we raise 21 to the power of 3. The result is 9261. Taking the remainder again with the modulus 1003 we get 234. The final step is to raise 234 to the power of 2: the result is 54756. Taking the remainder again we get the final result: abmodc=594a^b \mod c = 594.

On the other hand, when arbitrary integers aa, cc and dd are given, it is very hard to find an integer bb such that abmodc=da^b \mod c = d. This problem is called the discrete logarithm problem. We use the notation

logadmodc=b.\log_a d \mod c = b.

Because modular exponentiation can be done relatively fast even for large numbers but the inverse problem of finding the discrete logarithm becomes very hard for large numbers, modular exponentiation with large numbers is an example of a one-way function.

Let us take a closer look at the discrete logarithm with small numbers. We choose c=101c = 101 and below see a graph depicting 2xmod1012^x \mod 101.

Note that the graph is not smooth and it is not growing like the ’normal’ exponential function defined for real numbers. Instead, the graph seems to make random-looking moves.

A key agreement protocol is a method for two parties, say Alice and Bob, to agree on a shared secret key over an insecure channel, but still in such way that nobody else who is eavesdropping on the channel is able to learn the shared secret. An example of such method is Diffie-Hellman key agreement protocol.

The Diffie-Hellman key exchange begins by Alice and Bob agreeing on a modulus pp and a number gg. Then Alice picks a random number aa and sends Bob the number gamodp=ug^a \mod p = u. Similarly, Bob picks a random number bb and sends Alice the number gbmodp=vg^b \mod p = v. Now Alice can calculate vamodpv^a \mod p and Bob can calculate ubmodpu^b \mod p. These two values are both equal to gabmodpg^{ab} \mod p and that value can now be used as the new shared secret key.

Our HTTPS example (TLS_ECDHE_RSA_WITH_AES_256_GCM_SHA384_256 bit keys,TLS 1.2) makes use of a certain variant of the Diffie-Hellman key exchange.


Next we take a look at how public-key cryptosystems look like. The most used system is called RSA. It is based on the following mathematical fact:

If pp and qq are primes, and ee and dd are such that

edmod(p1)(q1)=1e \cdot d \mod (p - 1)(q - 1) = 1

then for all values of xx it holds that xedmodn=xx^{e \cdot d} \mod n = x, where n=pqn = p \cdot q.

To set up RSA keys, Alice first needs to find two large primes pp and qq. Both primes should be at least 1000 bits long. She then needs to pick an integer ee such that it is possible to find another integer dd for which

edmod(p1)(q1)=1e \cdot d \mod (p-1)(q-1) = 1

holds. The public key of Alice is now the pair (e,n)(e, n), where n=pqn = p\cdot q. The private key that Alice needs to decrypt messages is the pair (d,n)(d,n). Alice should not reveal the primes pp and qq to anybody.

Let us assume that Alice has given her public key to Bob. Bob can now encrypt any "message" xx that is (encoded as) an integer between 0 and nn by calculating xemodn=yx^e \mod n = y .Bob would send the result to Alice. Alice can decrypt the cryptotext yy because she knows the secret decrypting exponent dd. She calculates ydmodn=xy^d \mod n = x.

A traditional signature is some ink on a paper. It is based on the assumption that only one person can write a signature in a certain way. A digital signature is always different for every message (otherwise you could just copy-paste it to any document) and only a person who has the signing key can calculate it correctly. The signature can be verified by anybody who has the verification key.

RSA can be used also for digital signing and verification. Alice reveals the verification key (e,n)(e,n) and uses herself the signing key (d,n)(d,n). If Alice wants to sign message xx, she calculates the signature as xdmodn=sx^d \mod n = s. When Bob receives the message xx and the signature ss, he can check that semodn=xs^e \mod n = x. If this is true then the signature must be from Alice because nobody else knows the parameter dd thats is necessarily needed to calculate Alice’s signatures.

Usually the signature is not computed for the entire message but, instead, a hash of the message is computed first, and then the hash value is signed. This guarantees that the value to be signed does not become too big. On the verification side, similarly, the received message is first given as an input to the hash function, and parallel to that, the verification key (e,n)(e,n) is applied to the signature. If outputs from each operation are equal then the signature is accepted. The hash value of the message is called its fingerprint, and it can be used instead of the entire message if no collisions have been found for the hash function.

Our HTTPS example (TLS_ECDHE_RSA_WITH_AES_256_GCM_SHA384_256 bit keys,TLS 1.2) makes use of RSA for digital signatures.

You have reached the end of this section! Continue to the next section:

Remember to check your points from the ball on the bottom-right corner of the material!