I've been in IT for more than 15 years, I've never seen a analogy as good as yours for public key encryption. Thanks for that padlock analogy, now it will be much easier for me to explain to people.
How to get the "secret" number: Let P and Q be the two primes that make the "big" number, and let X = (P - 1)(Q - 1). The secret number is the smallest positive integer S such that if you multiply S by the "small" number and subtract 1, you get a multiple of X. In the example, P = 2 and Q = 5, so X = (2 - 1)(5 - 1) = 1 * 4 = 4. Thus, we want 3*S - 1 to be a multiple of 4. The smallest S where this works is S = 3: 3*3 - 1 = 8. Hence, the secret number is 3. Note: For this to work, the "small" number must not share any factors (other than 1) with X.
@@sarveshp1727 a number that fits the requirement stated. (no shared factors with X) 2, 4, and 8 are the smallest numbers that *do not* fit the criteria for X = 4
"...so they lock it with a padlock, and you can't open it up." *over on another channel...* "This is the LockPickingLawyer, and what I have for you today is a padlock..."
That's because these are made for entertainment, so generally are about relatively entertaining mathematical principles. Where are lectures in class are about vital mathematical principles which are often not entertaining at all... and that you have to learn completely, not just vaguely understand from a video. There, problem solved.
I LOVE that Drewmo did the animation for this. I love seeing his work pop up randomly over the years. he is an awesome guy and i've been a super fan for a very long time lol
This kind of encryption is used in HTTPS (or better, SSL) but it doesn't make a site that uses a longer key inherently safer. HTTPS is essentially only there to make sure some guy on your wifi network can't intercept your traffic, but it does nothing to protect against bugs on the actual site which are far easier to exploit and are just as effective
Dilip Tien The most guys here didnt know how a current becomes a Bit. So why they watching this? Its not possible to solve RSA with barehand and this has device specified reasons.
I really enjoy these videos, where you take something that seems abstract, and show what it's really used for! Can you do a video (or maybe a series of videos) on Fourier transforms, and their use in computing?
He explained right after: you need to factorize the number used for encoding: 10 in this case. The factorization is obvious, it's 2 and 5. It is not that obvious when the number is 657 digits long (2048 bits).
@@jide7765 ok, forgive me here because I'm lacking understanding in this as well. The secret number or what would be the private key in this case is 3. How does the prime factors of 10, being 2 and 5 have anything to do with 3?
@@quplet the formula for the private key is: d = (k x (p-1) x (q-1) + 1 ) / e, where p and q are the prime numbers, in this case, p = 2 and q = 5, e is 3 (as shared publicly) and k could be any integer, here I think they have used k = 2 There could be another way, but this is how they generally do it.
None of this explained how the bank derived the 3 as the "secret number". He said he would gloss over that and come back to it, but never revisited the secret 3. He showed how the 10 was derived by two prime numbers, but those were 2 and 5, neither of which explain how the 3 was derived as the secret number. This was a terrible example, since the secret number was the same as the public number. It doesn't show how anyone grabbing the public number couldn't just use those exact same numbers to arrive back at the original message, defeating the entire purpose.
65537 is 10000000000000001 in binary en.wikipedia.org/wiki/Fermat_number it's apparently a fermat number, im guessing it has something to do with how the cpu calculates the modulo operation... i'll investigate further lol.
If I understand RSA correctly, and for the example given: Start with 2 = p and 5 = q (prime numbers that multiply to make n=10), multiply (p-1)×(q-1) = (2-1)×(5-1) = 4 = z, then pick a prime number k that is both smaller than, and does not divide into z. In this case, k=3. n and k are the public keys. That is, 10 and 3. The secret key is a number j such that (k × j) MOD z = 1 or (3 × j) MOD 4 = 1. j = 3 because (3×3)/4 = 2 remainder 1 and we only need to make sure we have a remainder of 1. The public keys are n = 10 and k = 3, and the secret key is j=3. If I had a huge piece of craft paper, I could draw the math out easier.
It's Me He did not explain it because it needs some advanced mathematical knowledge which would steal the video's purpose. The secret number is the inverse of e(the number 3 he picked) mod phi(n) where phi(n) is Euler's function
You do make a lot of great videos, but this one leaves us with so many questions and unexplained aspects of the problem, not to mention that this algorithm does not work for most strings, it just happens to do for the string used here. How 3 was calculated as the secret number was not explained, and it's just generally very un-mathematical. I would love to see this video remade with more detail and a more carefully thought-out example!
I'm very confused. He said that the numbers 3 and 10 were publicly available- anyone can see them. But he then said the key to braking the code, depends on determining the primes that were multiplied together to create that number... How? How does knowing 5 and 2 help? Can someone please explain?
Mining Forge Little late but if you're still curious... The secret number can be determined mathematically, it just needs the original primes first. Once you have the two primes, in this case 2 and 5, you can, somewhat quickly, determine the "secret" number. Without boring you with the actual proof, the secret number is the smallest number that can be multiplied by our first small number (3 in the video), have 1 subtracted from it, and then have (2-1)*(5-1) be a factor. In the video's case, 2-1 * 5-1 is 4, so we need 3*X-1=4. The first integer for which that works is X=3, so 3 is the secret number. So essentially, if we have publicly available number Z, and we find the two factors of the other publicly available number (p and q), then we can solve Z*X - 1 = (p-1)(q-1) until we find an integer solution for X, and that is the secret number (calculation is more commonly expressed as Z*x mod [(p-1)(q-1)]=1). That calculation is not very taxing on computers at all, so if you can get the 2 primes you can get the secret number pretty easily.
Dear Dr. Grime, I oh so wish you were my Math-teacher back in the days! Understanding math would be so much easier for me back then... Because you can explain those contexts (?, dt.: Zusammenhänge) perfectly! Greetings from Germany
to find out, click the lock by the https, click connection, certificate information, "Google Internet Authority G2", and under the details you'll see that the bit size (short answer yes). However, technically that's not what happens, if I remember correctly that's only used to sign the certificate that is actually used (a DSA, not RSA, totally different based on different math) to exchange the session key (which is just random, and used for a symmetric cipher for the duration of the secure connection)
I still don't understand one thing: If supercomputers are capable of finding primes MUCH bigger than those used in cryptography why would be difficult for those computers to find the primes of a 1024 bits key? For example: in 2013 was found that 2^57885161-1 is prime and that number is huge (17,425,170 digits), much bigger than the primes used in cryptography, which are about 2^1024. ("only" 308 digits). I am confused.
1) I thought that finding a random prime implies that you actually proved that the number is prime by FACTORING IT. 2) I thought that the only way to broke a key would be FACTORING IT. So shouldn't "1" and "2" take similar computer effort? If so, why "1" is easy (every now and then gigantic primes are found) and "2" is difficult (even for small keys like a 1024 bit key, generated with two 512 bit primes)?
I did some research, got some help (inStar-chan !) and I think I got the answer to why 2^57885161-1 is "easily" proved prime while smaller primes still too difficult to be factored. Because 1024 bit RSA numbers are completely general; the algorithms that create keys have been built to avoid kinds of numbers that are computationally easier to factor. Mersenne primes (like 2^57885161-1) can be found with a fast algorithm designed specifically for those kinds of numbers (search for Lucas-Lehmer primality test) and the formula for the algorithm is specifically why all largest prime numbers have been Mersenne primes since; it's ridiculously easier to prove a Mersenne number prime than any other kind of number known by the mathematical community today. Mersenne primes are found using the following theorem (Lucas-Lehmer Test): For p an odd prime, the Mersenne number 2p-1 is prime if and only if 2p-1 divides S(p-1) where S(n+1) = S(n)2-2, and S(1) = 4. Testing the Lucas-Lehmer Test is MUCH easier than factoring the number, but it has the downside of ignoring lots of legit primes on the list. Since the primes on a cryptography key have nothing to do with Mersenne numbers the Lucas-Lehmer Test does not help it in any way. The security of a 1024 bit key relies on the hope that there are no KNOWN tests that can work as an alternative to the boring and computational expensive factorization process.
comptia's network+ 6 episodes on it, pass the test, have a job as an sever tech. just now understand internet encrypting. i just memorized it before, but now i actually understand, thank you.
@4.30 why is he cubing? Is it because 3 is the bank's secret number? Or is it because it was cubed originally and to reverse the process? If he chose a different number for the bank's secret number, this point would have been clearer. An unnecassry obfuscation.
It was a simple example, purposefully using small numbers. The public key numbers probably need to be a certain size before the encryption avoids all collisions (such as the example you gave).
Uh, I missed the part where the video explains how knowing the two primes would help me figure out the secret number. 5-2=3, is it as simple as subtracting the smaller prime from the larger prime?
Take a look at Pohlig-Hellman cipher which is a 'simpler' version of RSA if you are interested in this topic. It's hard to answer your question without solid understanding of modular arithmetic, Euler's totient, etc.
e*s = 1 mod (p-1)(q-1) (in other words: the remainder of (e*s) / (p-1)(q-1) = 1) e: the public number(3) p,q: the two primes (2 and 5) s: the secret number With the numbers in the video it would be: 3 * s = 1 mod (2-1)(5-1) 3 * s = 1 mod 4 s = 3 mod 4 s = 3
p4ch1n0 The RSA is more like: You take modulus n = p*q, where p and q are primes, and then you need 2 numbers, e and d which will have the following function: Encryption: Coded_Message = Message^e mod n Decryption: Message = Coded_Message^d mod n The 2 public ones are "e" and "n", and the private one is "d" That is why RSA is, in fact, a method of asymmetric key cryptography. I praise my textbooks.
Raising to a large power would indeed be quite difficult, yes (not as difficult as factoring that huge number, but still). The trick is in the fact that you also divide by another number and leave only the remainder. This allows you to perform the calculation, while keeping the numbers small as you multiply each time. Wikipedia has a good article about it under "Modular Exponentiation". The beauty of RSA is that is fast to encrypt and decrypt, but impossibly slow to break.
Yeah, I think the way he did this encryption was weird. True RSA requires you to put all of the A1Z26 numbers together, and when you decrypt the code, it'll have all of the numbers put together. For example, if you get back a small number, let's say 1234, it could represent "A Y D" or "L C D" of just plain "A B C D".
This is a great video for explaining encryption! I teach an introduction to encryption theory (very basic - just the concept of how public/private key work) to a senior high school level and will definitely be giving them this video to watch.
G4mm4G0bl1n when you said that 23/31=0,74193448... And that 31/23 - 1=0,347826086... You didn't explain anything. Why does any of what you wrote matter?
Dilip Tien RSA Keys are nothing special. Its 2 prims which are dividet together. I wrote that. 23/31 = Private Key: 0,74193548387096774193548387096774 31/23 - 1 = Public Key: 0,3478260869565217391304347826087 31/23 brokes the Rule that a Key has to be float without integer staying before. That means an irrational number without a decimal before the commata. Thats the reason why modulo is here -1 to normalize the digit for key generation. Every of this 2 digits has a Secret number which is bound together. Thats because of the arithmetical logical unit embedded into the processor as calculation unit. It also calculates the keys in the wise a showed you. The arithmetical logical unit has pointers which can be turned till you get the numbers. Thats why you have to turn the pointers to the right position to reach the integer namespace. ((31 / 23) + (23 / 31)) - (((31 / 23) + (23 / 31)) - 2) = 2 -2 comes from the last digit in the calculation. Its one of the key numbers to get the other magical once and means nothing else as how wide the pointers in the ALU has turned and in which direction. We had used Modulo -1 to normalize the Public Key. Now we have to do this to his magic number: -2 -1 = -3 * -1 = 3 (-2 - 1) * -1 = 3
Well, we are at the 2 Kbits, (1 Kilo bit = 1024 bits) and if the 512-bit quantum pc can break it in a short period of time, i think that we will slowly go to greater multiples of 2, like the Mbit for these numbers
It works kind of like this (see wikipedia for more details): given primes p and q, compute n = p*q and x=(p-1)*(q-1). Then you take a random number d (the secret number at the bank), and your public number is the so-called inverse of d. You find the number that, when you compute y = e*d and then you divide y by x, your remainder is 1. I know that sounds complicated, but we have some extra math that makes it easy to work with these remainders without having to search all numbers all the time.
OK so it would take a classical computer thousands of years to break a 2048 bit code. would a quantum computer be able to do it any faster? from my understanding a quantum computer doesn't do calculations any faster than a classical computer, but it does many calculations at one, while a classical computer would have to do it step by step. (my understanding of quantum computers comes from veritasium's videos)
Currently, real life quantum computers do not perform tasks as fast classical computers; but theoretically you are correct. Eventually our understanding of building quantum computers will catch up to classical computers and cracking the RSA key encryption will be trivial.
Don't think of it just in terms of speed of calculation. A Quantum machine can exploit properties of physics that a classical computer can not. That is what makes Shor's algorithm work. Shor's algorithm itself is faster because it has a better runtime complexity than all other algorithms that are designed to find prime factors of large composite numbers.
I love your videos, and sometimes (usually) I don't understand fully. I find it interesting anyway. This video needs to be remade though, that made no sense what so ever.
+Barraco Barner Yes, every time I see this explained (on RUclips anyway), the lecturer is so concerned about making the maths easy, they forget that people might want to quickly test what they learned by encoding their own random messages. And they use tiny moduli which don't even allow for more than half the alphabet! I find it a little annoying.
Somewhere where they teach both extremely advanced mathematics and pedagogy to break it down to easy-to-understand. If I had this guy as my math teacher I would sign up for extra classes on friday nights.
RSA public-key encryption? Screw this, I have my own system. encrypt = function (text) { var result = []; for (var i = 0; i < text.length; ++i) { result.push(text.charCodeAt(i)); } return result; } decrypt = function (array) { var result = ""; for (var i = 0; i < array.length; ++i) { result += String.fromCharCode(array[i]); } return result; }
Banks don't have to crack it because they know the initial two numbers they multiplied together to create the public number. If you knew those two prime numbers you could decode the encryption easily, but it's very hard to work backwards from the product to find the factors. If you search "how encryption works" in google the first video is another good explanation.
thin air :) to create the key, two large primes are generated randomly (the true randomness here is extremely important for security) from which the public and private parts of the key are derived. once created, the key pair generally doesn't change for a while, as creating randomness is difficult on computers, and as long as the private key isn't compromised, there's little risk of it being derived from the public key.
That is an excellent question, because I couldn't possibly answer it well in 500 characters. Fermat numbers are of the form 2^(2^n) + 1, and if it is a prime, it is also of the form 2^n + 1. 65537 is the largest prime of this form. It benefits in that it is prime, is large enough to circumvent certain attacks on small RSA exponents, and because it's 2^16 + 1, you can use very fast exponentiation by squaring to calculate (m^65537)%n. It strikes a good balance between security and computation.
This video gave me the necessary gist of information, that when I was discussing China's cracking of Gmails encryption with someone who actually understands all of this, I didn't look foolish. Thanks numberphile. If any of you are wondering, the person I was discussing it with claims, that China essentially got lucky in cracking Gmail's encryption of 1024 bits so fast. I'm figuring he's probably right because to date its the only break of a 1024 bit encryption I've ever heard of.
What is described here is only the surface. TLS only uses this in an initial exchange to securely establish a symmetric session key. The session key is different for every single connection. And it is this session key which actually encrypts the data.
+omegadan , true: the message is, perfect prime number factorization. That's how you hack into banks. Presently, that's thought to be infeasible with 2048-bit keys.
+YiFei Yang Actually yes. If you can factorize that giant number that James showed in the beginning, then you can break the security of the bank. The entire bank. Not just individual people.
There are many ways to determine whether a number is prime or not without knowing all of its factors. One is by trial division where you take a number, N, and divide by all number from 2~root N. For larger primes that might not be practical so there are primality tests but they can only tell you that its probable that it is a prime. Different tests use different techniques and combining the results of different tests together can give you a definite answer. For more info, google primality test.
for those wondering, you never use the private key to encrypt. in pki, you have your message and an open session to who you are sending to. you encrypt the message with the person's public key, and generate a hash with your private key. you then put both in a digital envelope and encrypt that with the session key. The person then decrypts the envelope with your public key, the message with their private key. the hashof your private key is for integrity and nonrepudiation.
On the few Wikipedia pages I've just checked, they all appear to have the updated information. The RSA Labortories have on the page describing the challenge that the prizes are no longer avaliable, so I feel like that is a pretty reasonable source as well, with the FAQ on the RSA Labortories being used as the reference on Wikipedia. It's good to see other people care about keeping Wikipedia up to date :)
ssh can be used with RSA keys (ssh-keygen is used to generate the public-private key pair) But it is not required. It can use DSA when using the ssh2 protocol.
The formula for the private key is: d = (k x (p-1) x (q-1) + 1 ) / e, where p and q are the prime numbers, in this case, p = 2 and q = 5, e is 3 (as shared publicly) and k could be any integer, here I think they have used k = 2 There could be another way, but this is how they generally do it.
If I remember well : take your two prime integers p and q (2 and 5 here) and compute phi=(p-1)(q-1) (it gives 4 in our example). Your exponent e has to be chosen to be less than phi and coprime with phi (that is, e and phi cannot be divided by the same number greater than 1 and both give integer results). Here, only 1 or 3 could be chosen, as 2 and 4 are not coprime (they can both be divided by 2).
Great video; that was absolutely mind-blowing. One question though: since there is a finite amount of known prime numbers, couldn't a supercomputer just go through the list of super-large primes, multiplying them in pairs until it got a hit?
That might be possible with numbers made of 512 bits. Unless they make special cpus with very large registers, the best they can do is emulate the math with slower methods. Even by computer standards, large integers are very slow. It would take years for a supercomputer to crack one of these, not to mention the key probably changes all over the place.
With a lot of difficulty. This is why there's a lot of research into finding new, large prime numbers. It's not for the novelty of discovering neat new numbers, it's because it's extremely useful for encryption.
I would love a video with Dr James Grime talking about why the sum of an infinite number of zeros makes up a non-zero number, ie, a definite integral (or continuous probability distributions). In other words, why the area under each point of a curve is zero but the sum of them is a non-zero number.
The problem has the same "hardness", but the good part of EC is that it uses smaller keys, with the same level of security, and so some computations are easyer, specially in "slow" devices, like electronic cards. A 256 bit elliptic curve, gives the same security than a RSA of 3072 bits. And with 384, will be like 7680 bits of RSA (this is from the NIST actually)
I made a simple encryption program with C#, I had an array of characters, the key would be generated and each character would be the characterised position in the array. Then the string you want to encrypt that, it would multiply the key and the position of the character that matches the string and then to decrypt it, you would need the key otherwise it wouldn't work
Symmetric key encryption is used to encrypting your harddisk as well. So I don't think the fact that «it's used only once» has real bearing on the size of the key-space. The fact that it is symmetrical means you have less to worry about, and can be simpler. Which allows it to be as secure with a smaller key. (actually elliptic curves allow for far smaller keys, and is asymmetrical as well)
I do know what hashing is, but it's a slightly different concept that works for passwords but everything. You're right; they must have left something out. I've read a fuller explanation of RSA before and don't fully remember it, but based on vague memories and common sense, I believe the key is to not just encrypt each letter but blocks of several letters at once. So "BAD" "CHE" "F" turns into 3 numbers. Now someone has to encrypt every 3 letter combo. The longer the block the more secure.
For now 2048-bit key is considered less than ideal, and people now start to use 4096-bit and even 8192-bit RSA keys, or start use eclipse curve cryptography which is even more difficult to crack.
+陈北宗 You're a bit off there. 1024-bit keys are considered less than ideal (but are still strong enough for basically anything). People are using 2048-bit keys, and some crazy people are using 4096-bit keys. Nobody is using 8192-bit keys, simply because generating them and using them takes a ton of effort and the extra effort doesn't give much more effective security. Elliptic curve cryptography (ECC) is not more difficult to crack, it's just a *lot* more efficient. There are concerns, however, that the curves used in ECC as provided by NIST are possibly backdoored. Nobody knows for sure, but given how the NSA was able to pull off a backdoor in Dual_EC_DRBG, it isn't out of the question.
It's his choice. And it is actually one of the reason that the generation of such keys takes a rather long time (seconds to minutes on a home computer, depending on the size of the number), because a computer generating such keys has to generate quite some really large random numbers and check if one of them is prime.
Looping through the alphabet, meaning encrypted letters can become lower, higher or equal to what you see, is stronger encryption, than if you allow special characters, which would prevent looping, which would mean any encrypted text that is a normal letter, means the decrypted text, would have to be a letter lower in the alphabet.
This was a GREAT video on RSA. But can you make a follow-up video that uses not "3" in 2 places? I get "close" to understanding it, and trying it out in excel. But, I'd like to follow along with you in SOME PLATFORM that can use your example, and then try some of my own modifications. Did I say I enjoyed not only this incredible video, but your series?
RSA was actually found a few year before 1977 (when it was published), by a british mathematician Clifford Cocks, but his work was kept classified until 1997. Ron Rivest, Adi Shamir and Leonard Adleman found it independently, still impressive work, but Cocks also deserves credit.
What is this nonsense? I just use the password "12345" for everything.
+Shawn Smith i tried to stole your account and it didn't work :/
+Shawn Smith Excellent choice! That will confound all those dictionary attacks of all words known to mankind.
+Shawn Smith hahahahaaaaaaaaaaaaaaa :)
+Shawn Smith That's the stupidest combination I ever heard in my life! That's the kind of thing an idiot would have on his luggage!
some babies were dropped and some were clearly thrown at walls.
I've been in IT for more than 15 years, I've never seen a analogy as good as yours for public key encryption. Thanks for that padlock analogy, now it will be much easier for me to explain to people.
How to get the "secret" number:
Let P and Q be the two primes that make the "big" number, and let X = (P - 1)(Q - 1). The secret number is the smallest positive integer S such that if you multiply S by the "small" number and subtract 1, you get a multiple of X.
In the example, P = 2 and Q = 5, so X = (2 - 1)(5 - 1) = 1 * 4 = 4. Thus, we want 3*S - 1 to be a multiple of 4. The smallest S where this works is S = 3: 3*3 - 1 = 8. Hence, the secret number is 3.
Note: For this to work, the "small" number must not share any factors (other than 1) with X.
Why does all of that work? And how is it linked to p|X^p-X?
@@qwertz12345654321 At night, tony will still toss and turn 'tween his sheets, wondering why the algorithm is solid.
What is the "small" number?
@@sarveshp1727 a number that fits the requirement stated. (no shared factors with X)
2, 4, and 8 are the smallest numbers that *do not* fit the criteria for X = 4
I want you to repeat it
Red Salmon and make it a ringtone
I want you to repeat it
i approve your profile pic
As in the words of Red Salmon, I want you to repeat it
"...so they lock it with a padlock, and you can't open it up."
*over on another channel...*
"This is the LockPickingLawyer, and what I have for you today is a padlock..."
He's the best
"...nothing on 2...nothing on 3...click on 4."
xD
🤣🤣🤣
Glad to see an LPL fan here
I'm a horrible Math student. However there is a weird problem that I like these kinds of videos better than lectures in class.
Tell me about it it's so weird!!!
That's because these are made for entertainment, so generally are about relatively entertaining mathematical principles. Where are lectures in class are about vital mathematical principles which are often not entertaining at all... and that you have to learn completely, not just vaguely understand from a video.
There, problem solved.
Its easier as you think. :)
That's probably for the same reason that I like to see work of art, rather than learning about them in class.
Well, I was an EXCELLENT Math student, at least in high school, and I ALSO find these videos better then class lectures.
"1024 could be broken in a few years"
Me watchin in 2019....
Don't worry Google upgraded to 2048bit (just like NatWest) shortly after this videos release.
that was reason why Hillary emails were haked.
@@muhumedmohamud2356 No, that was due to a spear-fishing attack.
but could they have done the other way because of the lower Bits
quantum cryptography
cheers Drew - this was great! Just what we needed!
first like and reply in seven years
Second like and reply in seven years
twenty second like and third reply in seven years
This guy is amazing!
I LOVE that Drewmo did the animation for this. I love seeing his work pop up randomly over the years. he is an awesome guy and i've been a super fan for a very long time lol
Didn't he do that Einstein joke? What do you call a bird that doesn't eat? A polynomial! ... Polly...No Meal
This kind of encryption is used in HTTPS (or better, SSL) but it doesn't make a site that uses a longer key inherently safer. HTTPS is essentially only there to make sure some guy on your wifi network can't intercept your traffic, but it does nothing to protect against bugs on the actual site which are far easier to exploit and are just as effective
Andriy Shevchenko
Hey does whatsapp and facebook vedio calls are safe and secure
Why did you use 3 twice? It made it very difficult to follow!
Thats what makes RSA safe, because when you have difficults to follow a formular then imagine how hard it is to follow a coded forumlar. :)
G4mm4G0bl1n not useful for explanations though.
Dilip Tien
The most guys here didnt know how a current becomes a Bit. So why they watching this? Its not possible to solve RSA with barehand and this has device specified reasons.
G4mm4G0bl1n they're watching this to learn. You don't need to know about how current becomes a bit. They didn't need to use three twice.
Dilip Tien
Ohms Law, whats "U"? Whats 1 Tesla? Whats the Invention which Tesla makes important? Whats the "Tesla Integral" and how to calculate it? :)
I really enjoy these videos, where you take something that seems abstract, and show what it's really used for! Can you do a video (or maybe a series of videos) on Fourier transforms, and their use in computing?
I love the passion for mathematics that is conveyed through this video :)
@ 4:10
"there is a formula to work out the secret number, I'm going to gloss over that for a second"
So, how to you work out the secret number?
Try try try
He explained right after: you need to factorize the number used for encoding: 10 in this case. The factorization is obvious, it's 2 and 5.
It is not that obvious when the number is 657 digits long (2048 bits).
@@jide7765 ok, forgive me here because I'm lacking understanding in this as well. The secret number or what would be the private key in this case is 3. How does the prime factors of 10, being 2 and 5 have anything to do with 3?
@@quplet the formula for the private key is: d = (k x (p-1) x (q-1) + 1 ) / e,
where p and q are the prime numbers, in this case, p = 2 and q = 5,
e is 3 (as shared publicly) and
k could be any integer, here I think they have used k = 2
There could be another way, but this is how they generally do it.
@@AnuragSingh-rh8li How does one find k = 2? Is this just a number the user decides, if not, how is it calculated?
I am not into math at all, but I am able to listen to You for hours!
None of this explained how the bank derived the 3 as the "secret number". He said he would gloss over that and come back to it, but never revisited the secret 3. He showed how the 10 was derived by two prime numbers, but those were 2 and 5, neither of which explain how the 3 was derived as the secret number.
This was a terrible example, since the secret number was the same as the public number. It doesn't show how anyone grabbing the public number couldn't just use those exact same numbers to arrive back at the original message, defeating the entire purpose.
65537 is 10000000000000001 in binary
en.wikipedia.org/wiki/Fermat_number
it's apparently a fermat number,
im guessing it has something to do with how the cpu calculates the modulo operation... i'll investigate further lol.
If I understand RSA correctly, and for the example given:
Start with 2 = p and 5 = q (prime numbers that multiply to make n=10), multiply (p-1)×(q-1) = (2-1)×(5-1) = 4 = z, then pick a prime number k that is both smaller than, and does not divide into z. In this case, k=3. n and k are the public keys. That is, 10 and 3.
The secret key is a number j such that (k × j) MOD z = 1 or (3 × j) MOD 4 = 1. j = 3 because (3×3)/4 = 2 remainder 1 and we only need to make sure we have a remainder of 1.
The public keys are n = 10 and k = 3, and the secret key is j=3.
If I had a huge piece of craft paper, I could draw the math out easier.
+Jeff Harris thanks
It's Me Why don't you read the description?
It's Me He did not explain it because it needs some advanced mathematical knowledge which would steal the video's purpose. The secret number is the inverse of e(the number 3 he picked) mod phi(n) where phi(n) is Euler's function
I'm digging the animated format of this one! Good work Brady!
Would you please make a video about elleptical curves algorythms in comparison to RSA based in public cryptography
No kidding, an educational video that wants to cover the very basics of a subject being far from its real-life applications. How utterly astounding.
the piece of paper in this video is currently on ebay - see link in full video description
1 like in a decade???
I like that the subtitles say "DR James Grimes". Sweet detail.
You do make a lot of great videos, but this one leaves us with so many questions and unexplained aspects of the problem, not to mention that this algorithm does not work for most strings, it just happens to do for the string used here. How 3 was calculated as the secret number was not explained, and it's just generally very un-mathematical. I would love to see this video remade with more detail and a more carefully thought-out example!
Yes pleaseeee. I'm a computer science major and your videos just drive my engines up to create monumentally powerful code! Thank you!!!
I'm very confused. He said that the numbers 3 and 10 were publicly available- anyone can see them. But he then said the key to braking the code, depends on determining the primes that were multiplied together to create that number... How? How does knowing 5 and 2 help? Can someone please explain?
Mining Forge Little late but if you're still curious...
The secret number can be determined mathematically, it just needs the original primes first. Once you have the two primes, in this case 2 and 5, you can, somewhat quickly, determine the "secret" number.
Without boring you with the actual proof, the secret number is the smallest number that can be multiplied by our first small number (3 in the video), have 1 subtracted from it, and then have (2-1)*(5-1) be a factor. In the video's case, 2-1 * 5-1 is 4, so we need 3*X-1=4. The first integer for which that works is X=3, so 3 is the secret number.
So essentially, if we have publicly available number Z, and we find the two factors of the other publicly available number (p and q), then we can solve
Z*X - 1 = (p-1)(q-1) until we find an integer solution for X, and that is the secret number (calculation is more commonly expressed as Z*x mod [(p-1)(q-1)]=1). That calculation is not very taxing on computers at all, so if you can get the 2 primes you can get the secret number pretty easily.
Dear Dr. Grime, I oh so wish you were my Math-teacher back in the days! Understanding math would be so much easier for me back then... Because you can explain those contexts (?, dt.: Zusammenhänge) perfectly!
Greetings from Germany
Google just announced updates to their security of gmail, does anyone know if that means they bumped it to 2048 bit?
to find out, click the lock by the https, click connection, certificate information, "Google Internet Authority G2", and under the details you'll see that the bit size (short answer yes).
However, technically that's not what happens, if I remember correctly that's only used to sign the certificate that is actually used (a DSA, not RSA, totally different based on different math) to exchange the session key (which is just random, and used for a symmetric cipher for the duration of the secure connection)
I still don't understand one thing: If supercomputers are capable of finding primes MUCH bigger than those used in cryptography why would be difficult for those computers to find the primes of a 1024 bits key? For example: in 2013 was found that 2^57885161-1 is prime and that number is huge (17,425,170 digits), much bigger than the primes used in cryptography, which are about 2^1024. ("only" 308 digits). I am confused.
a personal computer can find a random prime of that magnitude pretty quickly... the problem is finding the right ones, there are very many of them
1) I thought that finding a random prime implies that you actually proved that the number is prime by FACTORING IT.
2) I thought that the only way to broke a key would be FACTORING IT.
So shouldn't "1" and "2" take similar computer effort?
If so, why "1" is easy (every now and then gigantic primes are found) and "2" is difficult (even for small keys like a 1024 bit key, generated with two 512 bit primes)?
I did some research, got some help (inStar-chan !) and I think I got the answer to why 2^57885161-1 is "easily" proved prime while smaller primes still too difficult to be factored.
Because 1024 bit RSA numbers are completely general; the algorithms that create keys have been built to avoid kinds of numbers that are computationally easier to factor.
Mersenne primes (like 2^57885161-1) can be found with a fast algorithm designed specifically for those kinds of numbers (search for Lucas-Lehmer primality test) and the formula for the algorithm is specifically why all largest prime numbers have been Mersenne primes since; it's ridiculously easier to prove a Mersenne number prime than any other kind of number known by the mathematical community today.
Mersenne primes are found using the following theorem (Lucas-Lehmer Test): For p an odd prime, the Mersenne number 2p-1 is prime if and only if 2p-1 divides S(p-1) where S(n+1) = S(n)2-2, and S(1) = 4.
Testing the Lucas-Lehmer Test is MUCH easier than factoring the number, but it has the downside of ignoring lots of legit primes on the list. Since the primes on a cryptography key have nothing to do with Mersenne numbers the Lucas-Lehmer Test does not help it in any way.
The security of a 1024 bit key relies on the hope that there are no KNOWN tests that can work as an alternative to the boring and computational expensive factorization process.
comptia's network+
6 episodes on it, pass the test, have a job as an sever tech.
just now understand internet encrypting. i just memorized it before, but now i actually understand, thank you.
@4.30 why is he cubing? Is it because 3 is the bank's secret number? Or is it because it was cubed originally and to reverse the process? If he chose a different number for the bank's secret number, this point would have been clearer. An unnecassry obfuscation.
It was a simple example, purposefully using small numbers. The public key numbers probably need to be a certain size before the encryption avoids all collisions (such as the example you gave).
Uh, I missed the part where the video explains how knowing the two primes would help me figure out the secret number. 5-2=3, is it as simple as subtracting the smaller prime from the larger prime?
Take a look at Pohlig-Hellman cipher which is a 'simpler' version of RSA if you are interested in this topic. It's hard to answer your question without solid understanding of modular arithmetic, Euler's totient, etc.
e*s = 1 mod (p-1)(q-1) (in other words: the remainder of (e*s) / (p-1)(q-1) = 1)
e: the public number(3)
p,q: the two primes (2 and 5)
s: the secret number
With the numbers in the video it would be:
3 * s = 1 mod (2-1)(5-1)
3 * s = 1 mod 4
s = 3 mod 4
s = 3
nope the way it works is encryption key is prime x prime = encryption key
I don't understand. What do you mean?
p4ch1n0 The RSA is more like:
You take modulus n = p*q, where p and q are primes,
and then you need 2 numbers, e and d which will have the following function:
Encryption: Coded_Message = Message^e mod n
Decryption: Message = Coded_Message^d mod n
The 2 public ones are "e" and "n", and the private one is "d"
That is why RSA is, in fact, a method of asymmetric key cryptography.
I praise my textbooks.
Thank you so much!! Looking forward to future animation work with you, Brady.
Its drewmo! you are still my favorite flash animator :D
"I
I want that shirt encrypted so that only I could read it!
Raising to a large power would indeed be quite difficult, yes (not as difficult as factoring that huge number, but still).
The trick is in the fact that you also divide by another number and leave only the remainder. This allows you to perform the calculation, while keeping the numbers small as you multiply each time. Wikipedia has a good article about it under "Modular Exponentiation".
The beauty of RSA is that is fast to encrypt and decrypt, but impossibly slow to break.
The ebay link in the description, is no longer valid. Maybe change it to "The brown paper from this video was sold on ebay: _(link)_"
the first frame of this video is incredible
He did a mod(10)? Any letter later than 'I' would have gotten scrambled and mapped onto another letter.
Yeah, I think the way he did this encryption was weird. True RSA requires you to put all of the A1Z26 numbers together, and when you decrypt the code, it'll have all of the numbers put together.
For example, if you get back a small number, let's say 1234, it could represent "A Y D" or "L C D" of just plain "A B C D".
This is a great video for explaining encryption! I teach an introduction to encryption theory (very basic - just the concept of how public/private key work) to a senior high school level and will definitely be giving them this video to watch.
This is the clearest explanation of the RSA algorithm that I've ever heard.
How did you get 3 as the secret number? You never explained the formula
G4mm4G0bl1n when you said that 23/31=0,74193448...
And that 31/23 - 1=0,347826086...
You didn't explain anything. Why does any of what you wrote matter?
G4mm4G0bl1n you write things without explaining them. They just look like arbitrary numbers to me.
Dilip Tien
RSA Keys are nothing special. Its 2 prims which are dividet together. I wrote that.
23/31 = Private Key: 0,74193548387096774193548387096774
31/23 - 1 = Public Key: 0,3478260869565217391304347826087
31/23 brokes the Rule that a Key has to be float without integer staying before. That means an irrational number without a decimal before the commata. Thats the reason why modulo is here -1 to normalize the digit for key generation.
Every of this 2 digits has a Secret number which is bound together. Thats because of the arithmetical logical unit embedded into the processor as calculation unit. It also calculates the keys in the wise a showed you.
The arithmetical logical unit has pointers which can be turned till you get the numbers.
Thats why you have to turn the pointers to the right position to reach the integer namespace.
((31 / 23) + (23 / 31)) - (((31 / 23) + (23 / 31)) - 2) = 2
-2 comes from the last digit in the calculation. Its one of the key numbers to get the other magical once and means nothing else as how wide the pointers in the ALU has turned and in which direction. We had used Modulo -1 to normalize the Public Key. Now we have to do this to his magic number:
-2 -1 = -3 * -1 = 3
(-2 - 1) * -1 = 3
G4mm4G0bl1n not trying to be mean, burnt think the issue is your grammar. I'm being serious. I want to understand what you're saying.
Dilip Tien
Sorry for this. Can understand english really well, but building sentences is my difficulty.
So if quantum computers became more widespread, what bit number would we need to stay secure? GG banks
8 bit
It would have to be disgustingly massive I'm afraid. GG banks indeed :(
***** That's super interesting. Cheers for sharing!
Information-theoretically secure numbers
Well, we are at the 2 Kbits, (1 Kilo bit = 1024 bits) and if the 512-bit quantum pc can break it in a short period of time, i think that we will slowly go to greater multiples of 2, like the Mbit for these numbers
It works kind of like this (see wikipedia for more details): given primes p and q, compute n = p*q and x=(p-1)*(q-1). Then you take a random number d (the secret number at the bank), and your public number is the so-called inverse of d. You find the number that, when you compute y = e*d and then you divide y by x, your remainder is 1.
I know that sounds complicated, but we have some extra math that makes it easy to work with these remainders without having to search all numbers all the time.
he made it so fun , damn it why aren't you my teacher?
heard such an explanation for the first time....mind blown
OK so it would take a classical computer thousands of years to break a 2048 bit code. would a quantum computer be able to do it any faster? from my understanding a quantum computer doesn't do calculations any faster than a classical computer, but it does many calculations at one, while a classical computer would have to do it step by step. (my understanding of quantum computers comes from veritasium's videos)
This would probably answer your question as best as it could be answered: en.wikipedia.org/wiki/Shor%27s_algorithm
Currently, real life quantum computers do not perform tasks as fast classical computers; but theoretically you are correct. Eventually our understanding of building quantum computers will catch up to classical computers and cracking the RSA key encryption will be trivial.
Don't think of it just in terms of speed of calculation. A Quantum machine can exploit properties of physics that a classical computer can not. That is what makes Shor's algorithm work. Shor's algorithm itself is faster because it has a better runtime complexity than all other algorithms that are designed to find prime factors of large composite numbers.
These animations are brilliant.
I love your videos, and sometimes (usually) I don't understand fully. I find it interesting anyway. This video needs to be remade though, that made no sense what so ever.
That is a fantastic analogy for how encryption/decryption works.
this example doesn't work if you use letters beyond J (numbers 10-27) because the remainder can't be greater than 9
+Barraco Barner Yes, every time I see this explained (on RUclips anyway), the lecturer is so concerned about making the maths easy, they forget that people might want to quickly test what they learned by encoding their own random messages. And they use tiny moduli which don't even allow for more than half the alphabet! I find it a little annoying.
Somewhere where they teach both extremely advanced mathematics and pedagogy to break it down to easy-to-understand. If I had this guy as my math teacher I would sign up for extra classes on friday nights.
RSA public-key encryption? Screw this, I have my own system.
encrypt = function (text) {
var result = [];
for (var i = 0; i < text.length; ++i) {
result.push(text.charCodeAt(i));
}
return result;
}
decrypt = function (array) {
var result = "";
for (var i = 0; i < array.length; ++i) {
result += String.fromCharCode(array[i]);
}
return result;
}
+Szymon Bartosiewicz (Simon) Facebook encryption in a nutshell.
really?
does facebook use my type of encryption?
This is the best math channel in the multiverse.
But if p=np.........
n = 1
or p = 0
This is really neat! This actually gave me an idea for my research (I am a computational biologist). Actually a great idea! many thanks!
I'd prefer you repeat it, You were kinda talking over yourself.
Banks don't have to crack it because they know the initial two numbers they multiplied together to create the public number. If you knew those two prime numbers you could decode the encryption easily, but it's very hard to work backwards from the product to find the factors. If you search "how encryption works" in google the first video is another good explanation.
1:09 How did 'Math' slip in there (instead of 'Maths'?)
Blimey, we got ourselves a Yank in the art department?
I can only assume that Americans can only count up to one, and that's why they call it 'Math'? :o
@@cleverbobby Canadians call it "math" as well. 🍁
thin air :)
to create the key, two large primes are generated randomly (the true randomness here is extremely important for security) from which the public and private parts of the key are derived. once created, the key pair generally doesn't change for a while, as creating randomness is difficult on computers, and as long as the private key isn't compromised, there's little risk of it being derived from the public key.
SMH...
He left us with enough questions at the end to wonder why he bother in the first place.
That is an excellent question, because I couldn't possibly answer it well in 500 characters. Fermat numbers are of the form 2^(2^n) + 1, and if it is a prime, it is also of the form 2^n + 1. 65537 is the largest prime of this form. It benefits in that it is prime, is large enough to circumvent certain attacks on small RSA exponents, and because it's 2^16 + 1, you can use very fast exponentiation by squaring to calculate (m^65537)%n. It strikes a good balance between security and computation.
bro thats amazing
I hope Gmail, Facebook and Twitter are no more using a 1012 bit number -.-
1024*
Just look it up
Thank you H41909, I've found the same thing after some research myself. I guess that calculating φ and the secret key, would complete this video.
Do the Chinese remainder theorem!!!
Love the production. Brady you're the best!
rewind to 0:00 and press "J" every half second
Well, your sarcasm was helpful. I did not know that "J" is backward 10 seconds, and "L" is forward 10 seconds (both in lower case)
And right and left arrow are 5 seconds.
This video gave me the necessary gist of information, that when I was discussing China's cracking of Gmails encryption with someone who actually understands all of this, I didn't look foolish. Thanks numberphile.
If any of you are wondering, the person I was discussing it with claims, that China essentially got lucky in cracking Gmail's encryption of 1024 bits so fast.
I'm figuring he's probably right because to date its the only break of a 1024 bit encryption I've ever heard of.
Funniest intro ever X'D
I absolutely love these videos, and even doing the simplest math makes me cry.
Pause at 0:00 XD
:p
Thank you for sharing Fermat's Little Theorem.
This boi look like linguini from ratatouille
What is described here is only the surface. TLS only uses this in an initial exchange to securely establish a symmetric session key. The session key is different for every single connection. And it is this session key which actually encrypts the data.
He just told the internet how to hack into banks
+omegadan Theoretically, yes, but the method is not practical.
+omegadan And it's not hack into banks, it's hack into other people's bank account.
+omegadan , true: the message is, perfect prime number factorization. That's how you hack into banks. Presently, that's thought to be infeasible with 2048-bit keys.
+omegadan No, he just told the internet why it is impossible to hack the banks.
+YiFei Yang Actually yes. If you can factorize that giant number that James showed in the beginning, then you can break the security of the bank. The entire bank. Not just individual people.
I absolutely love this explanation and video top marks guys!
There are many ways to determine whether a number is prime or not without knowing all of its factors. One is by trial division where you take a number, N, and divide by all number from 2~root N. For larger primes that might not be practical so there are primality tests but they can only tell you that its probable that it is a prime. Different tests use different techniques and combining the results of different tests together can give you a definite answer. For more info, google primality test.
these animations are the best! :D you are google too, but send my thanks to animators!
for those wondering, you never use the private key to encrypt. in pki, you have your message and an open session to who you are sending to. you encrypt the message with the person's public key, and generate a hash with your private key. you then put both in a digital envelope and encrypt that with the session key. The person then decrypts the envelope with your public key, the message with their private key. the hashof your private key is for integrity and nonrepudiation.
James is a national treasure
This video inspired me to rob a bank. Thank you for the inspiration, numberphile. I would never have done it without you.
On the few Wikipedia pages I've just checked, they all appear to have the updated information. The RSA Labortories have on the page describing the challenge that the prizes are no longer avaliable, so I feel like that is a pretty reasonable source as well, with the FAQ on the RSA Labortories being used as the reference on Wikipedia. It's good to see other people care about keeping Wikipedia up to date :)
ssh can be used with RSA keys (ssh-keygen is used to generate the public-private key pair) But it is not required. It can use DSA when using the ssh2 protocol.
Interesting explanation. Love the energy you put into it!
The formula for the private key is: d = (k x (p-1) x (q-1) + 1 ) / e,
where p and q are the prime numbers, in this case, p = 2 and q = 5,
e is 3 (as shared publicly) and
k could be any integer, here I think they have used k = 2
There could be another way, but this is how they generally do it.
If I remember well : take your two prime integers p and q (2 and 5 here) and compute phi=(p-1)(q-1) (it gives 4 in our example). Your exponent e has to be chosen to be less than phi and coprime with phi (that is, e and phi cannot be divided by the same number greater than 1 and both give integer results). Here, only 1 or 3 could be chosen, as 2 and 4 are not coprime (they can both be divided by 2).
The thumbnail of this video just made my day.
Great video; that was absolutely mind-blowing. One question though: since there is a finite amount of known prime numbers, couldn't a supercomputer just go through the list of super-large primes, multiplying them in pairs until it got a hit?
That might be possible with numbers made of 512 bits. Unless they make special cpus with very large registers, the best they can do is emulate the math with slower methods. Even by computer standards, large integers are very slow. It would take years for a supercomputer to crack one of these, not to mention the key probably changes all over the place.
With a lot of difficulty. This is why there's a lot of research into finding new, large prime numbers. It's not for the novelty of discovering neat new numbers, it's because it's extremely useful for encryption.
I would love a video with Dr James Grime talking about why the sum of an infinite number of zeros makes up a non-zero number, ie, a definite integral (or continuous probability distributions). In other words, why the area under each point of a curve is zero but the sum of them is a non-zero number.
The problem has the same "hardness", but the good part of EC is that it uses smaller keys, with the same level of security, and so some computations are easyer, specially in "slow" devices, like electronic cards. A 256 bit elliptic curve, gives the same security than a RSA of 3072 bits. And with 384, will be like 7680 bits of RSA (this is from the NIST actually)
I made a simple encryption program with C#, I had an array of characters, the key would be generated and each character would be the characterised position in the array. Then the string you want to encrypt that, it would multiply the key and the position of the character that matches the string and then to decrypt it, you would need the key otherwise it wouldn't work
Symmetric key encryption is used to encrypting your harddisk as well. So I don't think the fact that «it's used only once» has real bearing on the size of the key-space.
The fact that it is symmetrical means you have less to worry about, and can be simpler. Which allows it to be as secure with a smaller key. (actually elliptic curves allow for far smaller keys, and is asymmetrical as well)
I do know what hashing is, but it's a slightly different concept that works for passwords but everything.
You're right; they must have left something out. I've read a fuller explanation of RSA before and don't fully remember it, but based on vague memories and common sense, I believe the key is to not just encrypt each letter but blocks of several letters at once. So "BAD" "CHE" "F" turns into 3 numbers. Now someone has to encrypt every 3 letter combo. The longer the block the more secure.
i feel very happy about this thanks for your sharing knowledge sir
For now 2048-bit key is considered less than ideal, and people now start to use 4096-bit and even 8192-bit RSA keys, or start use eclipse curve cryptography which is even more difficult to crack.
+陈北宗 You're a bit off there. 1024-bit keys are considered less than ideal (but are still strong enough for basically anything). People are using 2048-bit keys, and some crazy people are using 4096-bit keys. Nobody is using 8192-bit keys, simply because generating them and using them takes a ton of effort and the extra effort doesn't give much more effective security. Elliptic curve cryptography (ECC) is not more difficult to crack, it's just a *lot* more efficient. There are concerns, however, that the curves used in ECC as provided by NIST are possibly backdoored. Nobody knows for sure, but given how the NSA was able to pull off a backdoor in Dual_EC_DRBG, it isn't out of the question.
It's his choice. And it is actually one of the reason that the generation of such keys takes a rather long time (seconds to minutes on a home computer, depending on the size of the number), because a computer generating such keys has to generate quite some really large random numbers and check if one of them is prime.
Mc frontalots 'Secrets from the future' comes to mind here, especially his remark about a childs speak and spell cracking this times code.
Vsauce, Minute Physics, ViHart and Numberphile are making me smarter every day. Thank you. ~sincerly Yoshidude01
Looping through the alphabet, meaning encrypted letters can become lower, higher or equal to what you see, is stronger encryption, than if you allow special characters, which would prevent looping, which would mean any encrypted text that is a normal letter, means the decrypted text, would have to be a letter lower in the alphabet.
This was a GREAT video on RSA. But can you make a follow-up video that uses not "3" in 2 places? I get "close" to understanding it, and trying it out in excel. But, I'd like to follow along with you in SOME PLATFORM that can use your example, and then try some of my own modifications. Did I say I enjoyed not only this incredible video, but your series?
RSA was actually found a few year before 1977 (when it was published), by a british mathematician Clifford Cocks, but his work was kept classified until 1997. Ron Rivest, Adi Shamir and Leonard Adleman found it independently, still impressive work, but Cocks also deserves credit.