About this video
Clifford Cocks needed a trapdoor one-way function: easy to compute, hard to reverse unless you know a special piece of information. He used modular exponentiation as the lock: Bob turns his message into a number m and computes c = m^e mod N. The key is another exponent d that undoes it, since (m^e)^d = m^(e x d), and generating d needs a second one-way function from Euclid.
You'll be able to
- define a trapdoor one-way function.
- encrypt a small number using c = m^e mod N.
- explain how a decryption exponent d undoes the encryption exponent e.
Key words
- trapdoor one-way function
- A function that is easy to compute but hard to reverse unless you know a secret called the trapdoor.
- trapdoor
- The special information that makes a one-way function easy to reverse.
- modular exponentiation
- Raising a number to an exponent, dividing by the modulus and keeping the remainder.
- public exponent (e)
- The encryption exponent that anyone can use to lock a message.
- decryption exponent (d)
- The secret exponent that undoes e and returns the original message.
Transcript
- [Voiceover] The solution was found by another British mathematician and cryptographer, Clifford Cocks. Cocks needed to construct a special kind of one-way function called a trapdoor one-way function. This is a function that is easy to compute in one direction, yet difficult to reverse, unless you have special information, called the trapdoor.
For this, he turned to modular exponentiation, which we introduced as clock arithmetic, in the Diffie–Hellman key exchange, as follows. Take a number, raise it to some exponent, divide by the modulus and output the remainder. This can be used to encrypt a message as follows: Imagine Bob has a message, which is converted into a number, m.
He then multiplies his number by itself, e times, where e is a public exponent, then he divides the result by a random number, N, and outputs the remainder of the division. This results in some number, c. This calculation is easy to perform, however, given only c, e, and N, it is much more difficult to determine which m was used, because we'd have to resort to some form of trial and error.
So, this is our one-way function that we can apply to m, easy to perform, but difficult to reverse. It is our mathematical lock. Now, what about the key? The key is the trapdoor, some piece of information that makes it easy to reverse the encryption. We need to raise c to some other exponent, say d, which will undo the initial operation applied to m and return the original message m.
So, both operations together, is the same as m to the power of e, all raised to the power of d, which is the same as, m to the power of e times d, e is the encryption, d is the decryption. Therefore, we need a way for Alice to construct e and d, which makes it difficult for anyone else to find d This requires a second one-way function which is used for generating d, and for this, he looked back to Euclid.
Video © Khan Academy, used under CC BY-NC-SA. Watch on Khan Academy. Puzzicle is not affiliated with Khan Academy.