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.

# 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? •   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
• 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? •  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
• How close to the primes have to be to be 'Simalar size'? •  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.
• If m^(phi[n]) = 1 mod n,
4^(phi) = 1 mod 8
4^4 = 1
256 = 1?
please tell me what's wrong with this. • 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.
• can you tell me how K is 2 at in d
where d formula is d = (k *(phi(n)) + 1)/e • 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:
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
• 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? • 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"? • 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
• 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! • I believe someone else asked the question below, but it seems c^d mod n as described in the video at is 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? • 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. 