Main content
Computer science
Course: Computer science > Unit 2
Lesson 4: Modern cryptography- The fundamental theorem of arithmetic
- Public key cryptography: What is it?
- The discrete logarithm problem
- Diffie-hellman key exchange
- RSA encryption: Step 1
- RSA encryption: Step 2
- RSA encryption: Step 3
- Time Complexity (Exploration)
- Euler's totient function
- Euler Totient Exploration
- RSA encryption: Step 4
- What should we learn next?
© 2023 Khan AcademyTerms of usePrivacy PolicyCookie Notice
Public key cryptography: What is it?
After WWII, the US and Soviet Union raced to become global superpowers, leading to the creation of NORAD and computer networking. As the internet grew, encryption became essential for secure communication. Diffie & Hellman devised a trick using one-way functions to share secret keys without eavesdroppers intercepting them. Created by Brit Cruise.
Want to join the conversation?
- I don't understand. Eve has the public color (yellow), as well as each of the colors created by Alice and Bob. Couldn't Eve simply use logic and the color wheel to determine the private colors by both Alice and Bob? Example: Bob's color was green. Eve could just "subtract" yellow from the color green to get blue, therefore getting Bob's "secret color", therefore getting the mixture, or key. Right?(76 votes)
- Certainly Eve can try to guess what their original colors were, but only come close to the exact colors. On the other hand neither Alice nor Bob need to struggle to know their joint combination color.(46 votes)
- How do they end up with the same color? I watched this video twice and still don't get it.(15 votes)
- But EVE got Public-Yellow + (Public-Yellow+ Alice-Red) + (Public-Yellow+ Bob-Blue) = 4 x Public-Yellow+ Alice-Red+ Bob-Blue
4 x Public-Yellow= Public-Yellow (I mean, more yellow is yellow too)
That's why the explanation using colors is not accurate.
EDIT: Well, maybe 4 x Public-Yellow make a different color when mixing Red and Blue.(5 votes)
- I dont understand how they end up with the same color. I mean. if you mix Your public color with bobs red, how is it that is it guarenteed that they will end up with the same color!?(0 votes)
- They both mix the same colours, but in a different order. Because order does not matter, they end up with the same colour.(21 votes)
- how come Eve can not make her own private number?(3 votes)
- bacause bob and alices private colour is never revealed. Eve only gets to see to half constructed keys. But no way to find out how the yellow was converted to these half constructed keys. Except to try every possible combination, and it is arranged to be a lot of guesses.(2 votes)
- couldn't eve just not mix all the colours she has? that way she would(probably) get the common colour(1 vote)
- This wouldn't work and wouldn't be practical in the numerical procedure.(4 votes)
- Man yall so old man(2 votes)
- Justin Hunt for the win.(2 votes)
- why do they have a white colour and why does eve have a yellow colour(2 votes)
- why does eve have a yellow colour if she is not using it.?(2 votes)
- how does the mixing of the colors make the same color?(2 votes)
- How is it hard to reverse colors?
I mean we learn about the colors to make the colors so all
We need to to do is know the colors to make colors, right?
seems simple!(2 votes)
Video transcript
Brit: After World War 2,
with most of Europe in 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 successively 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 scattered 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. Man: The thing that makes the computer communication network
special, is that it puts the workers -- that'd be 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 a network. Brit: Money transfers are 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 have never met agree on a secret shared key without letting Eve,
who is always listening, also obtain a copy? In 1976, Whitfield Diffie
& 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 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, say yellow. Next, Alice and Bob both
randomly select private colors, and mix 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 add their private colors
to the other person's mixture and arrive 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.