This video introduces when and why the problems of modern cryptography emerged. We are introduced to the concept behind the Diffie-Hellman public key exchange - the first step towards RSA encryption.
Transcript
Transcript generated by YouTube auto-captions. May contain errors.
[Music] after World War II with most of Europe and ruins tensions grew between the Soviet Union and the United States it was clear that the next Global superpower required the ability to both launch and successfully defend nuclear attacks from intercontinental ballistic missiles the United States most vulnerable point of attack was over the North Pole so in 1958 a joint effort between United States and Canada was established NORAD the North American Aerospace Defense command an important line of defense was the semi-automatic ground environment it was an automated system of over 100 longdistance Radars scattered across North America they were connected to computerized radar systems that transmitted tracking data using telephone lines or radio waves all this information was fed into the primary warning Center buried deep inside Cheyenne Mountain in Colorado this application of machine to machine communication allowed operators to make split-second decisions using the information transmitted and processed automatically by computers this idea of being online was quickly adapted and advanced by universities in the following years as they understood the potential of computer networking the thing that makes the computer communication Network special is that it puts the workers the the team members who are geographically distributed in touch not only with one another but with the information base with which they work all the time and this is obviously going to make a tremendous difference in how we plan organize and execute almost everything of any intellectual consequence if we get into a mode in which everything is handled electronically and your only identification is some little plastic thing you stick into the Machinery then I can imagine that they want to get that settled up with your bank account just right now and put it through all the checks and that would require Network money transfers were just one of a growing number of applications which require encryption to remain secure as the internet grew to Encompass Millions around the world a new problem emerged at the time encryption required two parties to First share a secret random number known as a key how could two people who have never met agree on a key without letting Eve who is always listening also obtain a copy in 1976 Whitfield Diffy and Martin Helman devised an amazing trick to do this first let's explore how this trick is done using colors how could Alice and Bob agree on a secret color without Eve finding it out the trick is based on two facts one it's easy to mix two colors together to make a third color and two given a mixed color it's hard to reverse it in order to find the exact original colors this is the basis for a lock easy in One Direction hard in the reverse Direction This is known as a one-way function now the solution works as follows first they agree publicly on a starting color let's say yellow next Alice and Bob both randomly select private colors and mix them into public yellow in order to disguise their private color now Alice keeps her private color and sends her mixture to Bob and Bob keeps his private color and sends his mixture to Alice now the heart of the trick Alice and Bob add their private colors to the other person person's mixture and arrive at a shared secret color notice how Eve is unable to determine this color since she needs one of the private colors to do so and that's the trick now to do this with numbers we need a numerical procedure which is easy in one dire C and hard in the other this brings us to modular arithmetic which is also known as clock arithmetic for example to find 46 mod 12 we take a rope of length 46 units and wrap it around a clock of 12 units which is called the modulus and where the Rope ends is the solution so we say 46 mod 12 is congruent to 10 easy now to make this work we need a prime modulus such as 17 instead of 12 then we find a primitive root of 17 in this case three which has this important property that when raised to different exponents the solution distributes uniformly Around the Clock three is known as the generator so if we raise three to any exponent x the solution is equally likely to be any integer between 0 and 17 now the reverse procedure is hard given 12 find the exponent three needs to be raised to this is called the discrete logarithm problem and now we have our one-way function easy to perform but hard to reverse given 12 we would have to resort to trial and error to find the matching exponent how hard is this with small numbers it's easy easy but if we use a prime modulus which is hundreds of digits long it gets seriously hard even if you had access to all computational power on Earth it could take thousands of years to go through all possibilities so the strength of a one-way function is based on time needed to reverse it now this is our solution first Alice and Bob agree publicly on a prime modulus and a generator in this case 3 and 17 then Alice selects a private random number say 15 and calculates 3 to the^ of 15 mod 17 and sends the result publicly to Bob then Bob selects his private random number 13 and calculates 3 to the^ of 13 mod 17 and sends the result publicly to Alice and now the heart of the trick Alice takes Bob's public result and raises it to the power of her private number to obtain the shared secret which in this case is 10 Bob takes Alice's public result and raises it to the power of his private number resulting in the same shared secret now notice they did the same calculation though it may not look like it at first first look at Alice the 12 she received from was calculated as 3 to ^ 13 mod 17 so her calculation was the same as 3 to the power of 13 to the power of 15 mod 17 now look at Bob the six he received from Alice was calculated as 3 to ^ 15 mod 17 so his calculation was the same as 3 to the power of 15 to the power of 13 mod 17 notice they did the same calculation with the exponents in a different order they both end up with three raised to the power of their private numbers without one of these private numbers 15 or 13 Eve will not be able to find the solution this is how it's done while Eve is stuck grinding away at the discrete logarithm problem and with large enough numbers we can say it's practically impossible for her to break the encryption