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.
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
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
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.
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?
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.
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
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.
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.
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
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
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.
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.
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.
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!
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.
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.
Using "10" for the divide-by-and-take-remainder number only works for a 10-letter alphabet. To encode English text this way you'd need bigger numbers than "3" and "10". And in reality, that's what they do. He chose small numbers to show how the process works without having to do heinous calculations.
the only REALLY MINDED comment in this video is this one that you've made! All those who tried with any character above : j(10th) might found problems deconding the message. Thank you very much!
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.
Can anyone help me please ... I dont get it ... when he decoded the message he didn't use the original prime numbers ( 2 and 5 ) so why do he even need them ? any help is appreciated ...
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".
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.
@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.
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.
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.
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.
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.
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; }
But, what hapens when you use the letter "J" number 10? The remander would be 0, how do you decode back to 10, I mean, it´s OK from 1 to 9, what hapens when the remander repeats it self?
+Barraco Barner Yes, every time I see this explained (on RU-vid 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.
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).
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.
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.
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.
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.
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.
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.
+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.
Maybe to put things into perspective a little bit: "A lucky guess" finding both primes through a completely random search would essentially amount to winning Lotto 649. And winning again the week after that. And then also every week after that, until you've won 86 weeks in a row.
The Fundamental Theorem of Arithmetic says that any number can be constructed from the product of a unique combination of prime numbers. This means that if the product of two prime numbers equals that secret key, then those are the only two numbers that can do so.
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
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 secret number 3 works for his example of 3 and 10. You actually get it from a formula which involves 3, 2, 5. The trick is that you need to know that 10=2*5. It's simple for small numbers but very hard for giant ones.
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
to put it simply, the 2 prime numbers are used to create a lock and a key for the lock. u get a public key and a secert k using a formula. (this 1 is RSA ALGORITHM i think). u give out the public key to ur friend which will scramble his message. u get the scrambled message and u turn it back to readable message using the secert key. the trick is that these 2 prime numbers are so big that once you multiply them, its hard for a computer to turn the product back into 2 primes.
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.
What makes this work is the fact that there's no way to factor a number except by trial and error. For instance, let's suppose I gave you a very simple puzzle: P x Q = 3763 Find P and Q (besides 1 and 3763) The crux is that there's no technique that will directly spit out the answer for you. All you can do is trial and error... does P=2 work? does P=3 work? does P=4 work? etc. And for very very large numbers, a computer would require thousands of years to do this.
If that would be the case, a bad encryption would just mean that the recipient would not be able to decrypt the information, thus a failed transaction. This can happen all the time, not necessarily at the CPU level, but the software level. If I close my browser unexpectedly while I'm in the processes of making an online purchase, the same would happen. A failed encryption doesn't compromise the information it fails to encrypt, it just corrupts it.
The D-Wave can do several interesting things, but it (un)fortunately can't run Shor's Algorithm; to do that you'd need a full-on entangled quantum computer, while the D-Wave is merely an adiabatic quantum computer. Still a very powerful machine, kudos to the company for making it.
I use 8192-bit RSA keys where I'm forced to use RSA. Everywhere else I've switched to ECDSA, an even more mathematically interesting algorithm involving points of intersection of a curve by a line. The mathematical basis for ECDSA makes it faster than RSA, but also more secure.
its not really the bits that matter, but the encryption algorithm. Thats why AES 256-bit is considered the most secure and strong algorithm of all time.
I was told the "math" behind the RSA encrypting worked a little different. Yes there is the public key and then the secret key which is actually 4 numbers but the way they encrypt the word or credit card number was different.
RSA is not considered outdated, it is and always have been only to exchange keys for a symmetric crypto. The reason for this is that everything on a encrypted site needs to be encrypted and decrypted. The calulations for a assymetric crypto is time consuming, so this is why we use RSA for passwords and key exchange and AES for everything else. You are allowed to only use RSA for encryptions, but the modulo calulation will make it slow.
I've learned this at school but I had no Idea what I was doing cause it was a DIY group work to learn about codes and stuff. In this 9:22 min I've learned and understood more than the 2 hours a week for 6 months "learning codes" at school.. Yep, school should find a new method to make learning more interesting and easier..
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)
