Main content
Computer science theory
Course: Computer science theory > 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
RSA encryption: Step 1
Introduction to why we would need RSA. Created by Brit Cruise.
Want to join the conversation?
- Who noticed that he ends videos on cliff-hangers a lot?(30 votes)
- It is not to get you to watch the next one! I think that this whole section is one big video, split into pieces so it's not an hour long. If you look at the end of one and the begining of the succeding snippet, a small chunk is exactly the same. That chunk is on both videos to give you a relatively convenient ending spot, then on the following again to give you a good idea about what the preceding video is about.(10 votes)
- couldn't eve just find the opposite of the public key and add it to the mixture?(10 votes)
- The idea is that she can't. Not easily. Example is bad in a way it uses colors, since you can actually find complementary color very fast. But actual RSA uses real, proven trapdoor function which is explained in the later videos.(21 votes)
- AroundBritt says that Alice could openly send the lock to Bob. What if Eve(an interceptor) got it and the open lock never got to Bob? 2:00(3 votes)
- Bob could just ask Alice to send another lock.
A bigger problem occurs if Eve intercepts Alice's lock and then sends Bob a lock that Bob thinks belongs to Alice, but actually belongs to Eve. Bob will unknowingly use the lock and send the package to Alice. But Eve could intercept the package, open her lock, read the contents, relock it with Alice's lock, and then send it Alice. Neither Alice nor Bob would be aware that Eve has seen the contents of the package. This is known as a "man in the middle" attack. The solution to prevent this type of attack is for Alice to sign her locks.(16 votes)
- couldnt eve just find the complementary of cyan?(4 votes)
- With colors, if you are a few ppm (parts per million) of each primary color off, you will still get pretty close to the same color at the end right? But with numbers, missing by a couple will make the final answer waaaay off, because with each multiplication, division, combobulatoriation and whatnot, the number you are off by gets bigger and bigger.(5 votes)
- Aren't red and green complementary colors?(4 votes)
- Yellow = Red + Green
Orange = Red + 1/2 Green
Blue = Blue
Purple = Red + Blue
RGB tells us that Red and Cyan are complementary. Red and Green gives Yellow (see top).(2 votes)
- Isn't this kind of like the Diffie-hellman key exchange?(3 votes)
- I think they look very similar. It seems to be the same basic concept of encryption, but the twist is how it is used with multiple communication lines. Seeverses 0:521:42(1 vote)
- Starting from, the example given with colors requires that Alice sends the complementary color of red (cyan) and Eve intercepts it, then Eve can get the secret red from getting the complementary color of the cyan which she intercepted and is not too hard to do. When Bob sends his color, then Eve will have the red to be able to find the secret color. Is this a flaw in the explanation, my reasoning, or is it more complex and difficult in a way not easily demonstrated by this example? 2:05(3 votes)
- Here's the misconception in the above:
"Eve can get the secret red from getting the complementary color of the cyan which she intercepted and is not too hard to do "
In the example, fromto 2:48, it says that, for the purposes of the example, figuring out complementary colors is assumed to be hard to do i.e. it require the machine that only Alice has 3:18(1 vote)
- How would Alice communicate to Bob? In this case, only Bob can communicate to anyone else.(2 votes)
- She would do the same -- get Bob's public key and encrypt messages using it.(2 votes)
- How well would it work if Eve could stop the communication, Eve is shown like this:
E
A-^-B
What if it was more like this:
A-E-B
Couldn't Eve pretend to be both and have an apparently secure connection to both?(1 vote)- Yes, Eve could launch a man in the middle attack, which is why it is very important for public keys to be signed so that they can be authenticated by their users. In practice, public keys are signed by a Certificate Authority (see https://en.wikipedia.org/wiki/Certificate_authority) which people trust.(3 votes)
- Isn't it somewhat dangerous to have a centralized key?
If a hacker were to find a single key they'd be able to masquerade as the banker to all the banker's clients.
Wouldn't this make the inefficient approach of having a 1:1 mapping of keys more secure?(2 votes)- Yes, that is one flaw, but if you are a bank, you'd have thousands of keys to have to maintain secret instead of just one- but very important- key.(1 vote)
Video transcript
Up until the 1970s, cryptography had been
based on symmetric keys. That is, the sender encrypts their message using a specific key, and the receiver decrypts
using an identical key. (lock clinking) As you may recall, encryption is a mapping from some message using a specific key, to a ciphertext message. To decrypt a ciphertext, you use the same key
to reverse the mapping. So for Alice and Bob to
communicate securely, they must first share identical keys. However, establishing a
shared key is often impossible if Alice and Bob can't physically meet or requires extra communications overhead when using the Diffy-Hellman key exchange. Plus, if Alice needs to
communicate with multiple people, perhaps she's a bank, then she's going to have
exchange distinct keys with each person. Now she'll have to
manage all of these keys and send thousands of messages
just to establish them. Could there be a simpler way? In 1970, James Ellis, a British
engineer and mathematician, was working on an idea
for non-secret encryption. It's based on a simple,
yet clever concept: Lock and unlock are inverse operations. Alice could buy a lock, keep the key, and send the open lock to Bob. Bob then locks his message
and sends it back to Alice. No keys are exchanged. This means she could
publish the lock widely and let anyone in the world
use it to send her a message. And she now only needs to
keep track of a single key. Ellis never arrived at
a mathematical solution, though he had an intuitive
sense of how it should work. The idea is based on splitting
a key into two parts, an encryption key and a decryption key. The decryption key performs
the inverse or undo operation which was applied by the encryption key. To see how inverse keys could work, let's do a simplified
exampled with colors. How could Bob send Alice a specific color, without Eve, who is always
listening, intercepting it? The inverse of some color is
called a complimentary color, which when added to it, produces white, undoing the effect of the first color. In this example, we
assume that mixing colors is a one-way function because
it's fast to mix colors and output a third, and
it's much slower to undo. Alice first generates her private key by randomly selecting a color, say red. Next, assume Alice uses
a secret color machine to find the exact compliment of her red and nobody else has access to this. This results in cyan,
which she sends to Bob as her public key. Let's say Bob wants to send
a secret yellow to Alice. He mixes this with her public color and sends the resulting
mixture back to Alice. Now Alice adds her private
color to Bob's mixture. This undoes the effect
of her public color, leaving her with Bob's secret color. Notice Eve has no easy
way to find Bob's yellow, since she needs Alice's
private red to do so. This is how it should work. However, a mathematical
solution was needed to make this work in practice.