⇐ Use this menu to view and help create subtitles for this video in many different languages.
You'll probably want to hide YouTube's captions if using these subtitles.

# Part 11: Diffie-Hellman key exchange: Diffie-Hellman Key Exchange

相關課程

選項
分享

0 / 750

- After World War II with most of European ruins,
- tension 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.
- In North America, the most vulnerable point of attack
- was over the North Pole.
- So in 1958, a joint effort between United States and Canada
- was established, known as NORAD,
- or North American Aerospace Defense Command.
- An important line of defense
- was the semi-automatic ground environment.
- It was an automated system of over 100 long distance radars
- gathered across North America.
- They were connected to computerized radar stations
- that transmitted tracking data
- using telephone lines or radio waves.
- All of this radar information was fed into a primary warning center,
- buried a mile deep inside Cheyenne Mountain in Colorado.
- This application of machine to machine communication
- allowed operators to make split-second decisions
- using 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 that
- either a team member who're geographically distributed in touch,
- not only with one another, but with the information base
- with which they worked all the time,
- and this is obviously going to make a tremendous difference
- in how we plan, organize, and execute
- almost everything with any intellectual consequence.
- If we get into a mode
- in which everything is handled electronically,
- and your own identification is
- a simple plastic you stick into a machinery,
- that I can imagine that they wanted to get that settled up
- with your bank account just right now,
- and put it through all the checks,
- and that would require a network.
- Money transfers were
- just one of a growing number of applications
- which required encryption to remain secure.
- And 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;
- so how could two people who've never met
- agreed on a secret shared key
- without letting Eve, who's always listening,
- also obtain a copy.
- In 1976, Whitfield Diffie and Martin Hellman
- 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 mixed 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 agreed publicly on a starting color, say yellow.
- Next, Alice and Bob both randomly select private colors,
- and mixed them into the public yellow,
- in order to disguise their private colors.
- 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 added their private colors
- to the other person's mixture,
- and arrived at a shared secret color.
- Notice how Eve is unable to determine this exact color,
- since she needs one of their private colors to do so,
- and that is the trick.
- Now, to do this with numbers,
- we need a numerical procedure
- which is easy in one direction, and hard in the other.
- This brings us to modular arithmetic,
- also known as clock arithmetic,
- for example, to find "46 mod 12",
- we could take a rope of length 46 units,
- and wrapped it around a clock of 12 units,
- which is called the modulus,
- and where the rope ends is the solution;
- so we said "46 mod 12" is congruent to 10, easy.
- Now, to make this work, we use a prime modulus, such as 17
- then we find a primitive root of 17,
- in this case, 3, which has this important property,
- that when raised to different exponents,
- the solution distributes to uniformly around the clock,
- 3 is known as the generator,
- if we raised 3 to any exponent X,
- then the solution is equally likely to be
- any integer between 0 and 17.
- Now, the reverse procedure is hard, say given 12,
- find the exponent 3 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 matching exponents.
- How hard is this?
- Well, with small numbers, it's easy;
- but if we used a prime modulus which is 100s of digits long,
- it becomes impractical to solve.
- Even if you had access to all computational power on Earth,
- it could take 1000s of years to run through all possibilities,
- so the strength of a one-way function
- is based on the time needed to reverse it.
- Now, this's our solution:
- First, Alice and Bob agreed publicly
- on a prime modulus and a generator, in this case 17 and 3.
- Then, Alice selects a private random number, say 15,
- and calculates 3 to the power 15 mod 17,
- and sends this result publicly to Bob.
- Then, Bob selects his private random number, say 13,
- and calculates 3 to the power 13 mod 17,
- and sends this result publicly to Alice;
- and now the heart of the trick,
- Alice takes Bob's public result
- and raised 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.
- Notice they did the same calculation,
- though it may not look like it at first.
- Consider Alice, the 12 she received from Bob
- was calculated as 3 to the power 13 mod 17,
- so her calculation was the same as
- 3 to the power 13 to the power 15 mod 17.
- Now consider Bob, the 6 he received from Alice
- was calculated as 3 to the power 15 mod 17,
- so his calculation was the same as
- 3 to the power 15 to the power 13.
- Notice they did the same calculation
- with the exponents in the different order.
- When you flipped the exponent, the result doesn't change.
- So they both calculated 3 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.
- And 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 in a reasonable amount of time.
- This solves the key exchange problem.
- It can be used in conjunction with
- a pseudorandom generator to encrypt messages
- between people who've never met.

載入中...