Main content
Course: Computer science theory > 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?
© 2024 Khan AcademyTerms of usePrivacy PolicyCookie Notice
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?(37 votes)
I broke these up based on user advice. So now we have Ancient and Modern cryptography as separate lessons(117 votes)
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,11:14,15:19,26:33.
and 89 x 33 = 2937, & 113 x 26 = 2938. so the ratio26:33is 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? "(6 votes)
Since nobody answered this and for anyone reading the comments:
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).(11 votes)
at2:23you mentioned Euclid . Who is Euclid?(3 votes)- 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.(10 votes)
- 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 period1:45-2:12), more specifically I just can not understand how the formulas:
(1) : m^e mod N == c
(2) : c^d mod N == m
logically lead to the equation:
(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?(5 votes)- (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
For more info on modular arithmetic check out these lessons:
https://www.khanacademy.org/computing/computer-science/cryptography/modarithmetic/a/what-is-modular-arithmetic
Hope this makes sense(7 votes)
- So in the equation M^(e) mod n all raised to the power of d = M (1:59) why wouldn't mod(n) also be raised to the power of D.(3 votes)
- There's a couple ways of thinking about this:
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)
For more info check out the series on Modular Arithmetic:
https://www.khanacademy.org/math/applied-math/cryptography/modarithmetic/a/what-is-modular-arithmetic
Hope this makes sense(8 votes)
- 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.(3 votes)
- 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.(6 votes)
- what was the guys name at the beginning and what did he do?(4 votes)
Clifford Cocks. He thought up a way of creating a trapdoor function to be used in a public-key cryptosystem. As he worked for the UK's GCHQ, his work remained secret. The idea was later independently discovered and is known as the RSA algorithm.(2 votes)
could anyone explain to me how is this different to the diffie-hellmann key exchange?(3 votes)- 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.(2 votes)
What exactly is the ciphertext space?(2 votes)- 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(4 votes)
- Why do the equal signs have three lines instead of two?(2 votes)
- Triple equal signs are used in modular arithmetic to show congruence in that scope of "mod N", whereas equal signs are used to denote equivalence of two values. For instance, 8 ≡ 3 (mod 5) but 8 ≠ 3.(4 votes)
11:14Video transcript
- [Voiceover] The solution
was found by another British mathematician and
cryptographer, Clifford Cocks. Cocks needed to construct a
special kind of one-way function called a trapdoor one-way function. This is a function that is easy
to compute in one direction, yet difficult to reverse, unless you have special
information, called the trapdoor. For this, he turned to
modular exponentiation, which we introduced as clock arithmetic, in the Diffie–Hellman
key exchange, as follows. Take a number, raise it to some exponent, divide by the modulus
and output the remainder. This can be used to encrypt
a message as follows: Imagine Bob has a message, which is converted into a number, m. He then multiplies his number by itself, e times, where e is a public exponent, then he divides the result
by a random number, N, and outputs the remainder of the division. This results in some number, c. This calculation is easy to perform, however, given only c, e, and N, it is much more difficult to
determine which m was used, because we'd have to resort to some form of trial and error. So, this is our one-way
function that we can apply to m, easy to perform, but difficult to reverse. It is our mathematical lock. Now, what about the key? The key is the trapdoor, some piece of information that makes it easy to reverse the encryption. We need to raise c to some
other exponent, say d, which will undo the initial
operation applied to m and return the original message m. So, both operations
together, is the same as m to the power of e, all
raised to the power of d, which is the same as, m
to the power of e times d, e is the encryption, d is the decryption. Therefore, we need a way for
Alice to construct e and d, which makes it difficult
for anyone else to find d This requires a second one-way function which is used for generating d, and for this, he looked back to Euclid.