Definition 16.1.1. Trapdoor Function.
An invertible function \(E\) is called a trapdoor function if the inverse of \(E\) can be evaluated efficiently only when some extra information is known.
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 matching private key is used for decryption and must remain secret.
Public-key cryptography protects digital communication over the Internet, including secure websites and online banking. It helps protect privacy and finances. It uses mathematical functions called trapdoor functions. These functions are quick to evaluate but take an unreasonable amount of time to invert. If one knows the secret, the function can be inverted efficiently.
Example 16.1.2. Trapdoor functions.
The following functions are easy to evaluate, but their inverses are hard to evaluate:
-
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] depends on how difficult factorization is. In Section 16.3 and Section 16.2, we describe crypto systems that depend on the difficulty of computing discrete logarithms efficiently. These systems are 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.1.3 for the general setup of a public-key crypto system.
The padlock example in Example 16.1.4 shows that public key cryptography can also be used outside computers and other digital systems.
Example 16.1.4. 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 way to show that a digital message is authentic. A valid digital signature gives the recipient reason to believe that a known sender created the message.
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 check 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 put the ideas above into practice. We start with the Diffie-Hellman key exchange. Then we study the ElGamal public key crypto system, which is based on the Diffie-Hellman key exchange.
