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.

## Computer science theory

### Course: Computer science theory>Unit 2

Lesson 4: Modern cryptography

# RSA encryption: Step 2

Setting up a trapdoor one-way function. Created by Brit Cruise.

## Want to join the conversation?

• Are these meant to be broken up like this? Also aren't the full videos already on the site? •   I broke these up based on user advice. So now we have Ancient and Modern cryptography as separate lessons
• mod(N) = (p - 1 )*(q - 1) where 'p' & 'q' are two equal length binary prime integers of uniform bit length, say 512 bits each resulting in a dual-prime composite of 1024 bit length.
127, 63, 31, 15, 7, 3, 1,
1 1 1 1 1 1 1
1 0 0 0 0 0 0
64 32 16 8 4 2 0
So two primes of say 7 bit length would be primes between 67 & 127.
67, 71, 73, 79, 83, 89, 97, 101, 103, 107, 109, 113, 127.
Suppose we have a dual-prime composite 10057, we could divide by all the possible primes, and when we got to 89, BINGO! 89 x 113 = 10057.
Interestingly, 101 x 101 = 10201, and 10201 - 10057 = 144 = 12 x 12. AND, 101 + 12 = 113, and 101 - 12 = 89.
Also of note, there is an asymptopic series or sub ratios, 3:4, 4:5, , , .
and 89 x 33 = 2937, & 113 x 26 = 2938. so the ratio is a perfect sub-ratio.
This asymtotic series of sub-ratos is easy to calculate with basic algebra, and the result obtained within polynomial time constraints. So my question is, "Why do folk believe the factoring of any length dual-prime composite is exceptionally difficult? or of substantial asymetric complexity? " • Your example used only 7 bits. That's nothing compared to 512 bits. 512 bits would be a number with about 150 digits (log10(2) is around 3.3 bits which mean every 3.3 bit in binary is one digit in decimal, 512/log10(2) is about 154).

Now with 10 digits we already have about 400 million primes. You can begin to imagine how many primes there are with 150 digits. The number of primes smaller than n can be approximated with n/ln(n). n=150 would give us about 2*10^149. So the number of primes with 150 digits is in the magnitude of 10^149 (and 512 bit is actually 154 digits). That's just for finding prime numbers, after that you have to brute force the factorization.

We do not have the computational power to even begin a brute force attack, although if quantum computers are invented it can be done (but we are not even close to that possibility yet).
• at you mentioned Euclid . Who is Euclid? • Euclid is a dead guy who discovered/invented Euclidean geometry, which is all the laws of geometry that govern our three-dimensional world. Basically, he's this dead guy who did a lot of cool things with numbers, kind of like another dead guy whose name is sort of similar named Euler.
• I would like to thank the Khan Academy for the ambition to try to teach something as complex in nature as discrete logarithm, however I seem to have totally failed this lecture on the "RSA Encryption (step 2)" lecture(time period - ), more specifically I just can not understand how the formulas:
(1) : m^e mod N == c
(2) : c^d mod N == m
(final): (m^e)^d mod N == m

First I will explain what I do understand. The first two equations teach that the message/data sent must be first encrypted (e), e.g. m^e mod N == c
and then the message/data received must be decrypted (d), e.g. c^d mod N == m.

Moreover this is to explain briefly how the message will be decrypted, and to point out that the original process used to encrypt the message/data must be reversed.
However, using algebraic substitution, when one substitutes c = m^e mod N into the "c" of the decryption formula (c^d mod N == m), one is left with an algebraic knot:
Orig: [c]^d mod N == m
Sub: c == m^e mod N
Knot: [m^e mod N]^d mod N == m

The last line above is quite a problem because [m^e mod N]^d mod N
does not equal to (m^e)^d mod N, anotherwords
(m^e)^d NOT = [m^e mod N]^d.
I showed this is not equal with the clinical values below: [ ** = ^ ]
[code]
\$ ./modOfMod.sh
Modular of a discrete log containing an identical modular
Enter starting number> 243
SingleModulo = R % 17; yy = \${SingleMod} ** e; yyy= \$yy % 17
Enter power > 5
243: SingleModulo = 5 yy = 3125 yyy = 14
244: SingleModulo = 6 yy = 7776 yyy = 7
245: SingleModulo = 7 yy = 16807 yyy = 11
246: SingleModulo = 8 yy = 32768 yyy = 9
247: SingleModulo = 9 yy = 59049 yyy = 8
248: SingleModulo = 10 yy = 100000 yyy = 6
249: SingleModulo = 11 yy = 161051 yyy = 10
250: SingleModulo = 12 yy = 248832 yyy = 3
251: SingleModulo = 13 yy = 371293 yyy = 13
252: SingleModulo = 14 yy = 537824 yyy = 12
253: SingleModulo = 15 yy = 759375 yyy = 2
254: SingleModulo = 16 yy = 1048576 yyy = 16
255: SingleModulo = 0 yy = 0 yyy = 0
256: SingleModulo = 1 yy = 1 yyy = 1
257: SingleModulo = 2 yy = 32 yyy = 15
258: SingleModulo = 3 yy = 243 yyy = 5
259: SingleModulo = 4 yy = 1024 yyy = 4
[/code]

Through my above values test I have showed that the SingleModulo [m^e mod N] and yyy {[m^e mod N]^d mod N} are NOT equal.

I just do not how Brit Cruise made the logical step to say that the two equations:
m^e mod N == c
c^d mod N == m
lead somehow logically to the equation:
(m^e)^d mod N == m

The final equation I am clear on. Naturally I can see that there does certainly exist some number d that can reverse the effect e had on m before, that is the multiplication identity [ N * (1/N) =1]. The problem is simplly that I have absolutely no idea how he got from the two encrypt/decrypt problems to the final equation.

I guess I am missing some fundamental understanding of mathematics. Can anyone help me? • (1) m^e mod N = c
(2) c^d mod N = m
substitute (1) into (2)
(m^e mod N)^d mod N = m

Believe it or not:
(m^e mod N)^d mod N = (m^e)^d mod N
This is not the same as saying:
(m^e mod N)^d = (m^e)^d
The final mod N on each side matters!
Just because A mod N = B mod N, we can not conclude that A = B
e.g.
7 mod 4 = 11 mod 4
3 = 3
But it would be incorrect to say:
7 = 11

Proof that (m^e mod N)^d mod N = (m^e)^d mod N
LHS (left hand side) = (m^e mod N)^d mod N
RHS (right hand side) = (m^e)^d mod N
We'll show that LHS = RHS

By the quotient remainder theorem:
A = B * Q + R where 0 < R < B and A,B,Q,R are integers
So:
m^e = N * Q + R

LHS = (m^e mod N)^d mod N
LHS = ((N * Q + R) mod N)^d mod N
multiples of N are 0 under mod N, and R is < N so R mod N = R
LHS = R^d mod N

RHS = (m^e)^d mod N
RHS = ( N * Q + R )^d mod N
expand the terms
RHS = ((N * Q)^d + (N * Q)^(d-1) * R^1 + ... + (N * Q)^1 * R^(d-1) + R^d) mod N
apply mod N to all the terms in the brackets, multiples of N are 0 under mod N
RHS = R^d mod N

LHS = R^d mod N = RHS
thus
(m^e mod N)^d mod N = (m^e)^d mod N

Hope this makes sense
• So in the equation M^(e) mod n all raised to the power of d = M () why wouldn't mod(n) also be raised to the power of D. Approach #1)

m^e mod N ≡ c
notice the ≡ is used, not the =

m^e mod N ≡ c is equivalent to:
m^e mod N = c mod N
notice here we do use =, and not ≡

We can think of mod as a function that takes some value and returns a result

So this would be like writing:
f(m^e)=f(c) where in our case f(x)= x mod N

if we wanted to raise m^e to the power of d we could write:
f((m^e)^d)=f(c^d)

but since f(x)= x mod N this is the same as:
(m^e)^d mod N = c^d mod N

Which we can write in congruence modulo form as:
(m^e)^d ≡ c^d (mod N)
or as:
(m^e)^d (mod N) ≡ c^d
or if we understand that we are working in mod N as:
(m^e)^d ≡ c^d

Some people put brackets around the mod N, others don't.
Personally, I prefer to use brackets around mod N, when working with ≡.

Approach #2)
mod N just describes the mathematical system we are using
to perform our equations in.
It isn't a term in one of our expressions.

e.g. lets say I have a mathematical system called (odd or even world)
where the result of all calculations are only odd, or even
we could then write:
2+3 (odd or even world) ≡ 17
which basically says that in (odd or even world) the result of 2+3 is equivalent to
the result of 17 (both are odd in our (odd or even world), so they are equivalent)

(odd or even world) is just a reminder as to what system we were using to
perform our calculations

similarly:
11+7 (mod 11) ≡ 7
is just saying, that in our world we do all our calculations (mod 11),
11+7 is equivalent to 7. (This is true since 11+7=18, 18 mod 11=7 and 7 mod 11=7)

Hope this makes sense
• I'm a little confused by this concept. Does this mean Alice can only receive a secret message from Bob? What if she wants to send him something? I might have understood it wrong, but it seems Alice is sending him an open lock so he can send her back a locked message which she then opens up to read. • Alice has an infinite supply of the exact same lock (which only Alice has the key to), so she lets anybody grab one of these open locks whenever they want to. This allows anyone to send a locked message to Alice.

If Alice wants to send a message to Bob, then Bob needs to give Alice an open lock that only he has a key to.

So, in practice, anyone who wants to receive messages advertises their locks publicly, so that anyone can grab one of their open locks.
• what was the guys name at the beginning and what did he do? • could anyone explain to me how is this different to the diffie-hellmann key exchange? • RSA vs Diffie-Hellman key exchange (DH)

How they are the same:
-both rely on the Discrete Log problem being hard

How they are different:
-RSA requires factoring large primes to be hard, DH does not
-RSA uses a public key for the sender and a private key for the receiver, but DH creates a shared secret between the two parties. Fundamentally RSA is a public key encryption scheme while DH is a key exchange scheme. That is RSA is designed to encrypt any message, where DH is devised to generate a shared secret (a key).

In practice, they are both typically used so that both parties will end up with a key for a symmetric key cipher. RSA can encrypt the key as the message, and send it to the other party, while DH can use the shared secret to generate a key.
• What exactly is the ciphertext space? • Message Space= The collection of all possible message we can send
Key Space= The collection of all possible keys we can use
CipherText Space= The collection of all possible ciphertexts we can generate

Generally when Alice wants to send a message securely to Bob she does the following :
-she picks a message from the message space
-she picks a key from the key space
-she encrypts the message using the key and the cipher, which generates a cipher text (this cipher text will be part of the cipher text space)
-she sends the cipher text to Bob
-Bob decrypts the cipher text (using the key) into message text (sometimes called plain text)

Hope this makes sense 