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 4

RSA worked example. Created by Brit Cruise.

## Want to join the conversation?

- The choice of k is not made clear. By observation it must be chosen such that d is an integer but are there any other rules, tips or guidelines on the choice of k? For example in the lesson it appears that k = e - 1 but is that simply a coincidence or does it hold for all values of e?(142 votes)
- Yes, It only needs to be chosen such that d is an integer - finding k is the easy part requiring only some algebra (sorry for not being clear, I'll do another video with a worked example). Remember that there is no single value for k, in fact there are an infinite number of k's that would work(80 votes)

- Does this mean that if anyone ever figures out a pattern in the distribution of prime numbers (which is possible, yet unlikely in the near future), the security of RSA will be broken?(37 votes)
- Correct. However there is no easily computable formula for all the primes. Factorization must remain a hard problem for RSA to be secure. I'll have a new series soon on hard vs easy problems(37 votes)

- How close to the primes have to be to be 'Simalar size'?(11 votes)
- An educated guess would be that if the prime numbers were very different in size, then the prime factorization of N would become easier. If you are checking for factors of N from smaller to larger numbers, then the one with fewer digits would be discovered first. Once a prime factor is discovered then a primality test could determine if the remainder is prime, and if it is composite, then the number to factorize would be much smaller. If p1 = 7, and p2 = 127 you would discover 7 as a factor much sooner than if the pairs of primes were something like p1 = 71, p2 = 89.(25 votes)

- If m^(phi[n]) = 1 mod n,

4^(phi[8]) = 1 mod 8

4^4 = 1*256 = 1?*

please tell me what's wrong with this.(16 votes)- Firstly, addressing what you are mentioning, you did the products correctly, but however, Euler's theorem is proven for all m not a factor of n, so you are not applying Euler's theorem properly.

Consider the set of all distinct numbers less than and coprime to n. Then we choose m. Multiply all the numbers in the set by m. Then we have another set where all numbers are coprime to n and different modulo n.

If you are not convinced that all are different, suppose 2 are the same. Then we can divide them by m, since m is coprime to n. Then this will result in 2 same numbers.

Take the product of the elements in each set. Obviously, they are the same modulo n.

Note there are phi(n) such numbers. Thus we have 1=m^phi(n) mod n.

There is still the case where m is not coprime to n. In that case we will have to prove instead that m^[phi(n)+1]=m mod n.

So considering the prime factorization of n=p*q, for primes p, q. Let p be a factor of m.

Obviously, m^p=m mod p. Since if m is coprime with p , the proof above holds, if m is 0 mod p, it also works.

We thus have m=0 mod p, m^q=m mod q.

Note since phi(n)+1=(p-1)(q-1)+1

=>

m^[phi(n)+1]=0 mod p, m^[phi(n)+1]=[m^((q-1)(p-1)+1)=m*1=m mod q

By Chinese Remainder Theorem, we can be certain that m^[phi(n)+1]=m mod n.(17 votes)

- can you tell me how K is 2 at2:49in d

where d formula is d = (k *(phi(n)) + 1)/e

please quick(13 votes)- Here's what is going on:

d = (k * phi(n) + 1)/e

which is really just

d * e = k * phi(n) +1

which is really just

d * e mod phi(n) = 1

The value of k doesn't really matter (if we are clever we can calculate d without knowing k). What does matter is that:

-some k exists

-d is the**modular inverse**of e ( mod phi(n) )

A modular inverse of a value A (mod C) is a number , Ainv, such that (A * Ainv ) mod C =1. We find the modular inverse by using the**Extended Euclidean Algorithm**. This program:

https://www.khanacademy.org/cs/modulo-inverse-using-the-extended-euclidean-algorithm/1604704343

finds the modular inverse of 3 (mod 3016) is 2011.

Again, k doesn't really matter, but... here's where it comes from

Remember, we had the equation in this form.

d * e = k * phi(n) +1

2011* 3 = 6033 = 2 * 3016 + 1

Hope this makes sense(16 votes)

- How, specifically, is the encryption exponent e chosen? I understand the rules it must follow, but how would Alice choose one? Does she just chose a random value that satisfies the conditions? How large can this value be? How large are these values in real world applications?(8 votes)
- Great answer.

I just want to say that the key that makes e small insecure is that you only need as much ciphered messages as the value of e to compute e using the chinese remainder theorem.

In most implementations, that need to make lot of ciphers, it would be easy for Eve to get enough of that messages to break it easily.(0 votes)

- Since Euler theorem states that m^phi(n) mod n is 1 such that m is relatively prime to n, does that mean the message has to be relatively prime to n? And since 3 is not relatively prime to 3033(which is n in the video), and if I make 3 into alphabet it is c, does that mean I cannot send "c"?(5 votes)
- In RSA, n is the product of two primes.

In the video: n is the product of the primes 53 and 59

n = 53 * 59 = 3127

So as long as you don't pick a message that contains 53 or 59 as a factor, Euler's theorem guarantees that you are ok.

We can tell how many of these messages are guaranteed by Euler's theorem by looking at phi(n) which is a count of all the numbers <=n that are coprime to n.

phi(3127) = (59-1) * (53-1) = 3016

So there are 3016 guaranteed messages and only (3127-3016) = 121 messages not guaranteed by Euler's theorem.

When we use much larger primes, the chances of stumbling upon one of these messages not guaranteed by Euler's theorem becomes incredibly small. In fact, finding one would be equivalent to factoring n, which would break RSA.

So, what about these messages not guaranteed by Euler's theorem ?

They will still work !

i.e. encrypting and decrypting these messages will return the original message

They just work for different reasons

i.e. they work because of the Chinese Remainder Theorem, not because of Euler's Theorem(5 votes)

- i'm trying to work through this problem with excel, but is seems excel can't handle too large or small or a number. i get it to work with smaller exponents, but keep getting errors when trying to decrypt the message 1394^2011 = 89 mod3127. anyone have any advice for a better program that can run rather large computations, preferably free/cheap? or any other programs designed for computing/creating encryptions like this? Thanks!(4 votes)
- We can calculate this value by using a clever technique that keeps the numbers small

We use fast modular exponentiation

See the program here:

https://www.khanacademy.org/math/applied-math/cryptography/modarithmetic/p/fast-modular-exponentiation

Here's some lessons which explains how it works:

https://www.khanacademy.org/math/applied-math/cryptography/modarithmetic/a/modular-exponentiation

https://www.khanacademy.org/math/applied-math/cryptography/modarithmetic/a/fast-modular-exponentiation(4 votes)

- I believe someone else asked the question below, but it seems c^d mod n as described in the video at3:26is a rather heavy computation. Even for the simplified example of 1394^2011 mod 3127, my desktop calculator bogs out and begins to smoke. I can't imagine how strenuous calculations with practical key sizes of say, 2048 bits might be… especially on ICCs. Am I missing something here?(4 votes)
- You are correct.
**c^d mod n**is difficult to compute if you try and calculate**c^d**first then perform**mod n**after. Luckily there are many simple algorithms for**fast modular exponentiation**which circumvent the need to calculate c^d since we are working mod n and can perform some reductions.

One simple example is exponentiation by squaring. Imagine you want to calculate 3^5 mod 7. Instead of finding out 3^5 = 243 (let's pretend 3 digit numbers are too hard for us :-)

we could observe:

1. 3^5 = 3^4 * 3

2. 3^4 = 3^(2*2)

3. 3^2 = 9

4. 9 mod 7 = 2

5. 3^4 mod 7 = 2*2 =**4**

6. 3^5 mod 7 = 3***4**mod 7 = 5

done! No 3 digit numbers needed

There are much faster methods, especially since we can reduce the base**c**and the exponent**d**before doing anything. For a list of these algorithms check out: http://en.wikipedia.org/wiki/Modular_exponentiation

I will plan to do a video on this as part of a number theory playlist soon.(3 votes)

- I'm not quite sure what happens at1:27when you simplify m * m^(k*phi(n)) to m^(k*phi(n)+1) could anyone please explain?(3 votes)
- Recall the exponent rule: a^x * a^y = a^(x+y)

a * a^x = a^1 * a^x = a^(1+x)

similarly

m * m^(k*phi(n)) = m^1 * m^(k*phi(n)) = m^(1 +k*phi(n)) = m^(k*phi(n) + 1)(4 votes)

## Video transcript

- [Voiceover] We now have
a trapdoor for solving phi. If you know the factorization for N, then finding phi N is easy. For example, the prime factorization of 77 is seven times 11, so phi
of 77, is six times 10, 60 Step three, how to
connect the phi function to modular exponentiation. For this, he turned to Euler's Theorem, which is a relationship
between the phi function and modular exponentiation, as follows: m to the power of phi n, is congruent to one mod n. This means you can pick any two numbers, such that they do not
share a common factor, let's call them "m" and "n". Say m equals five and n equals eight. Now, when you raise m to
the power of phi n, or 4, and divide by n, you will
always be left with one. Now, we just need to modify this equation using two simple rules. First, if you raise the number one to any exponent, k, you always get one. In the same way, we can
multiply the exponent phi n by any number k, and the
solution is still one. Second, if you multiply
one by any number, say m, it always equals m. In the same way, we can
multiply the left side by m, to get m on the right hand side. And this can be simplified as m to the power of k,
times phi n, plus one. This is the breakthrough. We now have an equation
for finding e times d, which depends on phi n. Therefore, it's easy to calculate d, only if the factorization of n is known. Meaning d should be Alice's private key. It's the trapdoor which will allow her to undo the effect of e. Let's do a simple example, to see all of this in action. Say Bob has a message he
converted into a number, using a padding scheme. Let's call this "m". Then, Alice generates her public
and private key as follows: First, she generates
two random prime numbers of similar size and multiplies
them to get n, 3,127. Then she calculates phi of n easily, since she knows the factorization of n, which turns out to 3,016. Next, she picks some
small public exponent, e, with the condition that
it must be an odd number that does not share a factor with phi n. In this case she picks e equals three. Finally, she finds the value
of her private exponent, d, which in this case is two
times phi of n, plus one, divided by three, or 2,011. Now, she hides everything
except the value of n and e, because n and e make up her public key. Think of it as an open lock. She sends this to Bob to
lock his message with. Bob locks his message by calculating m to the power of e, mod n. Call this "c", his encrypted message, which he sends back to Alice. Finally, Alice decrypts his message using her private key, d, accessed through her trapdoor. c to the power of d, mod n, equals Bob's original message, m. Notice that Eve, or anyone else, with c, n, and e, can
only find the exponent d, if they can calculate phi n, which requires that they know
the prime factorization of n. If n is large enough, Alice can be sure that this will take hundreds of years, even with the most powerful
network of computers. This trick was immediately
classified after its publication, however, it was independently redisovered in 1977 by Ron Rivest, Adi
Shamir and Len Adleman, which is why it's now
known as RSA in encryption. RSA is the most widely
used public key algorithm in the world, and the most
copied software in history. Every internet user on earth is using RSA, or some variant of it, whether they realize it or not. Its strength relies on the
hardness of prime factorization. which is a result of deep questions about the distribution of prime numbers. A question which has remained unsolved for thousands of years. (dramatic music)