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 3

RSA Encryption (step 3). Created by Brit Cruise.

Want to join the conversation?

  • blobby green style avatar for user Trevor Paulsen
    I've heard quantum computing has the potential to do prime factorization very easily. If quantum computers become a reality, will this spell doom for encryption as we know it? What will happen then?
    (18 votes)
    Default Khan Academy avatar avatar for user
  • mr pink red style avatar for user brit cruise
    1. Click 'explore this concept' in top right corner to interact with graph used in video.
    2. Still curious why factorization is hard? Watch this next http://www.khanacademy.org/math/applied-math/comp-number-theory
    (44 votes)
    Default Khan Academy avatar avatar for user
  • mr pants teal style avatar for user Nathan Wailes
    Around Brit says that it's really hard to figure out the factorization of the 300-digit number if you use two 150-digit numbers. But if the person trying to find the factors KNOWS that you're multiplying primes together to generate those long numbers, couldn't they just limit their brute-force search to prime numbers? In other words, when looking for the factorization of the 300-digit number, couldn't they just try multiplying different primes together to see what they get? That would seem to greatly reduce the amount of time it would take to figure out what factors were used to generate the 300-digit number.
    (14 votes)
    Default Khan Academy avatar avatar for user
  • leaf green style avatar for user SteveSargentJr
    How long would it take to generate a random prime number over 150 digits long? And how would you even go about generating said prime number??
    (10 votes)
    Default Khan Academy avatar avatar for user
  • piceratops ultimate style avatar for user Derik Paquette
    As far as prime numbers are concerned, are they a result of our base 10 system? or are the prime numbers consistent throughout different bases?
    (4 votes)
    Default Khan Academy avatar avatar for user
    • mr pink red style avatar for user Varun
      That's a really good question; great thinking! Don't think of primes as being only for mathematicians - think of them in terms of things, like seeds or coins. No matter what base you are in, the point is to assign a value to a certain number of things - humans use base 10 because we are used to that since we have 10 fingers (according to the anthropologists, anyway). Base 60 was also common in ancient times, but the end goal of any number system is to assign a value. No matter what base you are in, there will be some values that cannot be split evenly between a certain amount of people - this is easily visualized. If you have 5 things, you could say 5 or 0101, but in the end, you wouldn't be able to divide those things evenly between 2 (10) people. What makes prime numbers special is that they can't be divided evenly between any number of people except that number, or if one person takes them all. Especially if the things in question are cookies. Then they're mine. The only thing that really changes between bases is the arithmetic and algorithms involved in finding primes - dividing multiple times in anything but base 10 makes my head hurt. Hope this helped!
      (8 votes)
  • winston default style avatar for user ΓΩǨɆ
    When you click on 'explore this concept' it shows the factorization estimating thing.

    How does it estimate how long a factorization will take without doing it?
    How much CPU does it assume?

    thanks
    (5 votes)
    Default Khan Academy avatar avatar for user
  • winston default style avatar for user ☢Haseeb Alam☢
    What was that website at ?
    (3 votes)
    Default Khan Academy avatar avatar for user
  • piceratops seed style avatar for user martinahysi
    What is the website that calculates time needed to multiply or factorize and plots values on the graph? I need an answer as soon as possible!
    (5 votes)
    Default Khan Academy avatar avatar for user
  • primosaur ultimate style avatar for user Luke
    couldn't you just run through primes that were roughly the right size? also, why not use squares and SQRTs, since you have to guess to get those too?
    (3 votes)
    Default Khan Academy avatar avatar for user
  • male robot hal style avatar for user Alan
    Can I have the link to that program that showed how long it takes a computer to multiply and factor numbers?
    (3 votes)
    Default Khan Academy avatar avatar for user

Video transcript

- [Voiceover] Over 2,000 years ago, Euclid showed every number has exactly one prime factorization, which we can think of as a secret key. It turns out that prime factorization is a fundamentally hard problem. Let's clarify what we mean by "easy" and "hard", by introducing what's called "time complexity". We have all multiplied numbers before, and each of us our own rules for doing so, in order to speed things up. If we program a computer to multiply numbers, it can do so much faster than any human can. Here is a graph that shows the time required for a computer to multiply two numbers. And, of course, the time required to find the answer increases as the numbers get larger. Notice that the computation time stays well under one second, even with fairly large numbers. Therefore, it is "easy" to perform. Now, compare this to prime factorization. If someone told you to find the prime factorization of 589, you will notice the problem feels harder. No matter what your strategy, it will require some trial and error until you find a number which evenly divides 589. After some struggle, you will find 19 times 31 is the prime factorization. If you were told to find the prime factorization of 437, 231, you'd probably give up and get a computer to help you. This works fine for small numbers, though if we try to get a computer to factor larger and larger numbers, there is a runaway effect. The time needed to perform the calculations increases rapidly, as there are more steps involved. As the numbers grow, the computer needs minutes, then hours, and eventually it will require hundreds, or thousands of years to factor huge numbers. We therefore say it is a "hard" problem due to this growth rate of time needed to solve it. So factorization is what Cocks used to build the trapdoor solution. Step one, imagine Alice randomly generated a prime number over 150 digits long; call this "p one". Then, a second randon prime number roughly the same size; call this "p two". She then multiplies these two primes together to get a composite number, N, which is over 300 digits long. This multiplication step would take less than second; we could even do it in a web browser. Then, she takes the factorization of N, p one times p two, and hides it. Now, if she gave N to anyone else, they would have to have a computer running for years to find the solution. Step two, Cocks needed to find a function which depends on knowing the factorization of N. For this, he looked back to work done in 1760 by Swiss mathematician, Leonhard Euler.