Main content

## 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

# RSA encryption: Step 3

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

## Want to join the conversation?

- 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)
- 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)- what does "size of imput" means on the "explore this concept" page?(2 votes)

- Around2:20Brit 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)
- Saying "factorization" in this context means "prime factorization". And such knowledge will not help to break encryption in a reasonable time, anyway. There is still huge number of combinations to search.(6 votes)

- 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)
- How long it would take depends on what kind of computing power you have and how you use it. The latter - the algorithm/method - is more important than the computers used.(4 votes)

- 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)
- 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)

- 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)- It's just an estimation using a formula/table of stored value, it doesn't actually perform the factorization. It is based on a modern, though fairly slow, single CPU(5 votes)

- What was that website at1:53?(3 votes)
- It's an exploration I put on Khan Academy labs:

https://www.khanacademy.org/labs/explorations/time-complexity

Though you can find it a similar version in this lesson following the video(6 votes)

- 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)
- 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)
- Choosing numbers of roughly the right size is the basis behind Fermat's factorization method. See: http://en.wikipedia.org/wiki/Fermat%27s_factorization_method

It works well if the factors are close to sqrt(n), however, it performs worse than trial division when they are not. When we select prime numbers for RSA, one of the several things we want to check for is that, they are sufficiently far apart to prevent Fermat's factorization method and similar techniques from being effective.(2 votes)

- Can I have the link to that program that showed how long it takes a computer to multiply and factor numbers?(3 votes)
- It's the very next step in the playlist.(1 vote)

## 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.