Definition 16.2. Trapdoor Function.
An invertible function \(E\) is called a trapdoor function if the inverse of \(E\) can only be evaluated efficiently when in possession of some additional information.
Section 16.1 Introduction
Symmetric-key crypto systems, like the Caesar cipher in Chapter 8, use the same key for encryption and decryption of a message. So, both parties need to share a key to be able to encrypt and decrypt messages. A significant disadvantage is that the key has to be distributed through secure channels.
In public-key crypto systems each person has two keys. The public key is used for encryption and may be freely distributed. The corresponding private key is used for decryption and must remain secret.
Public-key cryptography is widely used for all secure digital communication over the Internet, such as secure web sites and online banking. It is used to secure your privacy and your finances. Public-key cryptography is realized by using certain mathematical functions called trapdoor functions, that can be evaluated quickly but cannot be inverted in a reasonable amount of time. If one knows the secret, the function can be inverted efficiently.
Example 16.3. Trapdoor functions.
Examples for functions that are easy to evaluate but whose inverse is difficult to evaluate are:
- Multiplication of integers is much easier than factorization of integers.
- Exponentiation in the groups \((\Z_p^\otimes,\otimes)\) is much easier than finding discrete logarithms (compare Section 15.4).
The RSA crypto system [7] is based on the difficulty of factorization. Section 16.3 and Section 16.2 we describe crypto systems that rely on the difficulty of efficiently computing discrete logarithms, namely the Diffie-Hellman key exchange and the ElGamal public key crypto system.
1
Clifford Cocks described an equivalent system in 1973, but it was classified by the UK intelligence agency GCHQ until 1997
See Figure 16.4 for the general setup of a public-key crypto system.
The padlock analogue given in Example 16.5 illustrates how public key cryptography can be practiced outside the digital world of computers.
Example 16.5. Padlock Analogue.
To compare symmetric key and public key cryptography we use the mechanical analogue of a padlock. Let’s assume that secure messages are send in a box that can be locked with a padlock.
In symmetric key cryptography both Alice and Bob have a key to the same padlock. To send a secure message to Bob, Alice places the message into a box and locks it with the padlock using her key. Bob receives the box, opens it with his key, and reads the message.
In public key cryptography Bob makes his own padlocks to which only he can open, and distributes them to everyone who wants to send him secure messages. Alice writes her message, puts it in a Box, and locks it with one of Bob’s padlocks. She sends it to Bob, and only Bob, who has the key to unlock the padlock, open the box to read the message.
Subsection Digital Signatures
A digital signature is a mathematical scheme for demonstrating the authenticity of a digital message. A valid digital signature gives a recipient reason to believe that the message was created by a known sender.
Assume that Bob has generated a public key and a private key and published his public key. Now he can sign messages and others can verify his signature.
- Bob encrypts a message with his private key.
- Bob sends the message to Alice.
- Alice obtains Bob’s public key form the key directory.
- Alice decrypts Bob’s message using Bob’s public key. Thereby confirming its authenticity.
In the next section we present realizations of the ideas described above. We start with the Diffie-Hellman key exchange and continue with he ElGamal public key crypto system that is based on the Diffie-Hellman key exchange.
