If you're seeing this message, it means we're having trouble loading external resources on our website.

If you're behind a web filter, please make sure that the domains ***.kastatic.org** and ***.kasandbox.org** are unblocked.

Main content

Current time:0:00Total duration:2:25

the solution was found by another British mathematician in cryptographer Clifford Cox Cox 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 get 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 divided 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 numbers see 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 over