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

RSA encryption: Step 1

Introduction to why we would need RSA. Created by Brit Cruise.

Want to join the conversation?

  • leaf green style avatar for user Serena
    Who noticed that he ends videos on cliff-hangers a lot?
    (29 votes)
    Default Khan Academy avatar avatar for user
    • starky sapling style avatar for user Rebecca Stay🐇🐶🐲
      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.
      (9 votes)
  • orange juice squid orange style avatar for user Alex L
    couldn't eve just find the opposite of the public key and add it to the mixture?
    (11 votes)
    Default Khan Academy avatar avatar for user
    • blobby green style avatar for user LD
      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.
      (19 votes)
  • primosaur ultimate style avatar for user Sujal J.👍
    Around Britt 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?
    (3 votes)
    Default Khan Academy avatar avatar for user
    • male robot hal style avatar for user Cameron
      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.
      (11 votes)
  • purple pi purple style avatar for user old account of @nimcord
    couldnt eve just find the complementary of cyan?
    (4 votes)
    Default Khan Academy avatar avatar for user
    • mr pink red style avatar for user Varun
      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)
  • old spice man blue style avatar for user 18zigmonl
    Aren't red and green complementary colors?
    (4 votes)
    Default Khan Academy avatar avatar for user
  • duskpin ultimate style avatar for user Flyed
    Isn't this kind of like the Diffie-hellman key exchange?
    (3 votes)
    Default Khan Academy avatar avatar for user
  • aqualine ultimate style avatar for user jjoyalazo
    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?
    (3 votes)
    Default Khan Academy avatar avatar for user
    • male robot hal style avatar for user Cameron
      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, from to , 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
      (1 vote)
  • ohnoes default style avatar for user Nameless
    How would Alice communicate to Bob? In this case, only Bob can communicate to anyone else.
    (2 votes)
    Default Khan Academy avatar avatar for user
  • piceratops tree style avatar for user Alvin Mao
    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)
    Default Khan Academy avatar avatar for user
  • piceratops ultimate style avatar for user Farhan
    At , Alice uses a " secret color machine to find the exact compliment of her red, cyan. Do those kind of color machines exist?
    (2 votes)
    Default Khan Academy avatar avatar for user

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.