Encryption and HUGE numbers - Numberphile

[@shawn576]

What is this nonsense? I just use the password "12345" for everything.

[@F_Sacco]

+Shawn Smith i tried to stole your account and it didn't work :/

[@MatCendana]

+Shawn Smith Excellent choice! That will confound all those dictionary attacks of all words known to mankind.

[@NACHOXVALLE]

+Shawn Smith hahahahaaaaaaaaaaaaaaa :)

[@tony2es]

+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!

[@Aemilindore]

some babies were dropped and some were clearly thrown at walls.

[@autohmae]

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.

[@redsalmon9966]

I want you to repeat it

[@KlaxontheImpailr]

Red Salmon and make it a ringtone

[@tristanawesome23]

I want you to repeat it

[@yashp1nth]

i approve your profile pic

[@whatdoiputhere224]

As in the words of Red Salmon, I want you to repeat it

[@clickrick]

"...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..."

[@dannyhuffman3587]

He's the best

[@bscottlam]

"...nothing on 2...nothing on 3...click on 4."

[@shervilgupta92]

xD

[@hhppecit]

🤣🤣🤣

[@hayden.A0]

Glad to see an LPL fan here

[@piguy314159]

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.

[@qwertz12345654321]

Why does all of that work? And how is it linked to p|X^p-X?

[@chrysanthosbouroutzoglou1599]

@@qwertz12345654321 At night, tony will still toss and turn 'tween his sheets, wondering why the algorithm is solid.

[@sarveshp1727]

What is the "small" number?

[@shiwanabe]

@@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

[@matthewclifford7217]

I'm a horrible Math student. However there is a weird problem that I like these kinds of videos better than lectures in class.

[@ccosplayer5901]

Tell me about it it's so weird!!!

[@Svilly12]

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.

[@G4mm4G0bl1n]

Its easier as you think. :)

[@Xorume.]

That's probably for the same reason that I like to see work of art, rather than learning about them in class.

[@darreljones8645]

Well, I was an EXCELLENT Math student, at least in high school, and I ALSO find these videos better then class lectures.

[@harvyhun]

"1024 could be broken in a few years" Me watchin in 2019....

[@danielb7006]

Don't worry Google upgraded to 2048bit (just like NatWest) shortly after this videos release.

[@muhumedmohamud2356]

that was reason why Hillary emails were haked.

[@danielb7006]

@@muhumedmohamud2356 No, that was due to a spear-fishing attack.

[@muhumedmohamud2356]

but could they have done the other way because of the lower Bits

[@gkollias14]

quantum cryptography

[@numberphile]

cheers Drew - this was great! Just what we needed!

[@lightflame_669]

first like and reply in seven years

[@nonasuomynona1734]

Second like and reply in seven years

[@visforvalerie]

twenty second like and third reply in seven years

[@blackmadra]

Why did you use 3 twice? It made it very difficult to follow!

[@G4mm4G0bl1n]

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. :)

[@prosincr]

G4mm4G0bl1n not useful for explanations though.

[@G4mm4G0bl1n]

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.

[@prosincr]

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.

[@G4mm4G0bl1n]

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? :)

[@Gunbudder]

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

[@michaelbauers8800]

Didn't he do that Einstein joke? What do you call a bird that doesn't eat? A polynomial! ... Polly...No Meal

[@GaussTruth]

@ 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?

[@lels3618]

Try try try

[@jide7765]

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).

[@quplet]

@@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?

[@AnuragSingh-rh8li]

@@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.

[@Markus8Markus8]

@@AnuragSingh-rh8li How does one find k = 2? Is this just a number the user decides, if not, how is it calculated?

[@numberphile]

the piece of paper in this video is currently on ebay - see link in full video description

[@MarloTheBlueberry]

1 like in a decade???

[@valentinmoeller]

This guy is amazing!

[@andriyshevchenko6689]

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

[@malikfaisalpanezai2061]

Andriy Shevchenko Hey does whatsapp and facebook vedio calls are safe and secure

[@therealfreeman]

I love the passion for mathematics that is conveyed through this video :)

[@numberphile]

check the equations in the video description (and lots of comments in this discussion)

[@this_mfr]

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.

[@juicyclaws]

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.

[@jeffharris4714]

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.

[@siddharthdash8946]

+Jeff Harris thanks

[@TBaruah27]

It's Me Why don't you read the description?

[@Diego01201]

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

[@RoSi4You]

I am not into math at all, but I am able to listen to You for hours!

[@jomiar309]

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?

[@mydemon]

I like that the subtitles say "DR James Grimes". Sweet detail.

[@nerhu59]

Google just announced updates to their security of gmail, does anyone know if that means they bumped it to 2048 bit?

[@foobargorch]

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)

[@RSP13]

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.

[@foobargorch]

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

[@RSP13]

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)?

[@RSP13]

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.

[@Vulcapyro]

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.

[@ger128]

This is the clearest explanation of the RSA algorithm that I've ever heard.

[@element_m2498]

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

[@artisticcheese]

Would you please make a video about elleptical curves algorythms in comparison to RSA based in public cryptography

[@prosincr]

How did you get 3 as the secret number? You never explained the formula

[@prosincr]

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?

[@prosincr]

G4mm4G0bl1n you write things without explaining them. They just look like arbitrary numbers to me.

[@G4mm4G0bl1n]

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

[@prosincr]

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.

[@G4mm4G0bl1n]

Dilip Tien Sorry for this. Can understand english really well, but building sentences is my difficulty.

[@ericeinarson6654]

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?

[@scollinbball]

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.

[@StepSkatin]

Yes pleaseeee. I'm a computer science major and your videos just drive my engines up to create monumentally powerful code! Thank you!!!

[@reodor1499]

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!

[@DustinScherer]

I'm digging the animated format of this one! Good work Brady!

[@IqbalHamid]

@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.

[@djskippimusic]

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.

[@Sylocat]

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?

[@adhamuhajier]

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.

[@p4ch1n0]

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

[@emmettochrach-konradi2785]

nope the way it works is encryption key is prime x prime = encryption key

[@p4ch1n0]

I don't understand. What do you mean?

[@1spiceatatime]

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.

[@ZivanVasquez]

This is the best math channel in the multiverse.

[@foreverofthestars4718]

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)

[@supertacticalbacon]

This would probably answer your question as best as it could be answered: en.wikipedia.org/wiki/Shor%27s_algorithm

[@loloynage]

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.

[@christophcooneyoff]

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.

[@jeroonk]

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.

[@FusionDeveloper]

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)_"

[@kekke2000]

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.

[@ckmishn3664]

He did a mod(10)? Any letter later than 'I' would have gotten scrambled and mapped onto another letter.

[@shardulheda]

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".

[@numberphile]

see equations in the full video description

[@MegaDutchuch]

"I

[@andmicbro1]

I want that shirt encrypted so that only I could read it!

[@GhostInTheShell29]

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.

[@CoreGamerPlus]

So if quantum computers became more widespread, what bit number would we need to stay secure? GG banks

[@DrDankuS]

8 bit

[@JustLacksZazz]

It would have to be disgustingly massive I'm afraid. GG banks indeed :(

[@JustLacksZazz]

***** That's super interesting. Cheers for sharing!

[@Reitenshii]

Information-theoretically secure numbers

[@1spiceatatime]

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

[@ascetica0]

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.

[@xlsmafia]

this example doesn't work if you use letters beyond J (numbers 10-27) because the remainder can't be greater than 9

[@PopeLando]

+Barraco Barner Yes, every time I see this explained (on KZbin 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.

[@namnatulco]

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.

[@trafmus]

he made it so fun , damn it why aren't you my teacher?

[@Waniou137]

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.

[@flobiish]

I'd prefer you repeat it, You were kinda talking over yourself.

[@nebonit]

Mc frontalots 'Secrets from the future' comes to mind here, especially his remark about a childs speak and spell cracking this times code.

[@fbicknel]

1:09 How did 'Math' slip in there (instead of 'Maths'?) Blimey, we got ourselves a Yank in the art department?

[@cleverbobby]

I can only assume that Americans can only count up to one, and that's why they call it 'Math'? :o

[@nousername5673]

@@cleverbobby Canadians call it "math" as well. 🍁

[@DrewMokris]

Thank you so much!! Looking forward to future animation work with you, Brady.

[@Gunbudder]

Its drewmo! you are still my favorite flash animator :D

[@88Domination]

rewind to 0:00 and press "J" every half second

[@peterlindner3283]

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)

[@Ken.-]

And right and left arrow are 5 seconds.

[@ZantierTasa]

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).

[@inwencja2009]

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; }

[@herecomedatboi]

+Szymon Bartosiewicz (Simon) Facebook encryption in a nutshell.

[@inwencja2009]

really? does facebook use my type of encryption?

[@theRealPlaidRabbit]

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.

[@dimasveliz6745]

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!

[@jkjkhoyolula]

But if p=np.........

[@robin-vt1qj]

n = 1

[@connfdm]

or p = 0

[@jarnMod]

My secret...I hate math until I discover your channel I wish my middle school math teacher has a way to make math interesting like this.

[@dannyspeagle10]

SMH... He left us with enough questions at the end to wonder why he bother in the first place.

[@lordkango]

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.

[@RedellaStrada47]

I hope Gmail, Facebook and Twitter are no more using a 1012 bit number -.-

[@prosincr]

1024* Just look it up

[@Vulcapyro]

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.

[@TheJackfrost88]

bro thats amazing

[@sergioavila2720]

Do the Chinese remainder theorem!!!

[@robehickmann]

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.

[@matszz]

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.

[@jknew1832]

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.

[@colefaraday6577]

Pause at 0:00 XD

[@greekfire995]

:p

[@Almondsareodd]

the first frame of this video is incredible

[@gigglysamentz2021]

Funniest intro ever X'D

[@juanfmacias3]

This is really neat! This actually gave me an idea for my research (I am a computational biologist). Actually a great idea! many thanks!

[@nicklagrow5310]

This boi look like linguini from ratatouille

[@N0Xa880iUL]

heard such an explanation for the first time....mind blown

[@themasstermwahahahah]

He just told the internet how to hack into banks

[@linnaea_lavia]

+omegadan Theoretically, yes, but the method is not practical.

[@linnaea_lavia]

+omegadan And it's not hack into banks, it's hack into other people's bank account.

[@DrRChandra]

+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.

[@stefan1draganov]

+omegadan No, he just told the internet why it is impossible to hack the banks.

[@DaffyDaffyDaffy33322]

+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.

[@KeenanTims]

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.

[@keksi365]

4:21 I wish he gave an example that made sense, the banks secret code is literally just the public code, not very secret. In that example anyone who intercepted the code and knew your public key code (which is public) can decrypt the message.

[@TheOlliemath]

+kek Si The first example I can think of with different keys is to have 22 as your large number and 3 as the public exponent. The bank's private exponent would then be 7. Even in the example in the video the attacker doesn't necessarily know that the public 3 given out is also the private key - they have to do some work to figure that out.

[@eduardogomes4865]

No, did you saw the animation? When you encrypt with a public key, only the private key can decrypt it.

[@keksi365]

That's correct, it just would be worth while using an example where the public and private keys are not the same. In his example the public key is "cube then divide by 10 and use the remainder" and then his private key works the same way "cube then divide by 10 and use the remainder". It's taking advantage of a property where the numbers just happen to work out. If it was "square a number then divide by 10 and use the remainder" none of it would work. The private key could not also be "square a number then divide by 10 and use the remainder". Example for the letter "b" using my key that replaces cubing with squaring: B=2 Public encryption of 2: 2^2 = 4 4/10 has a remainder of 4 the coded number is 4 Private decryption of 4: 4^2 = 16 16/10 has a remainder of 6 6 =/= 2 So his just happens to work with his numbers, the key he made up is not an example of how a real key could possibly work. Also, I would like to see his key work for numbers higher then 10 what if your letters were "a" and "k" a=1 k=11 a: 1^3 = 1 1/10 has a remainder of 1 k: 11^3 = 1331 1331/10 has a remainder of 1 both would have a remainder of 1 and both would translate back as "a"

[@eduardogomes4865]

kek Si I agree with you in the 10 complaint. He should have used a number higher than 26 to do this example. Now, about the same number being both keys, while that's quite problematic and some people got confused, he explictly said it's only in the example, so it's not a big problem.

[@dalilarobledodebasabe191]

Love the production. Brady you're the best!

[@adammcgarrity28]

These animations are brilliant.

[@honrilful]

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.

[@triiberg]

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.

[@FusionDeveloper]

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.

[@miskee11]

This video inspired me to rob a bank. Thank you for the inspiration, numberphile. I would never have done it without you.

[@hikaru-live]

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.

[@DaffyDaffyDaffy33322]

+陈北宗 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.

[@golightning291]

I feel like a math whiz knowing it took James long enough to remember that H was the 8th letter in the alphabet that he had to skip over and come back to it when I already had that letter locked down.

[@Suicidal_Muffin]

The thumbnail of this video just made my day.

[@noodlescodes]

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 :)

[@djtomoy]

James is a national treasure

[@StarEclipse506]

Thank you for sharing Fermat's Little Theorem.

[@pbaumgarten]

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.

[@honrilful]

«Computers are able to factorize numbers into primes [in] polynomial run-time» - Nales Kla «As far as I know that algorithm was just tested on the number 15. [Producing] 3 and 5.» - rangedfighter For what reason would you calculate 3^5?

[@deaggi]

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.

[@Worldwideweb1994]

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.

[@KemaTheAtheist]

That is a fantastic analogy for how encryption/decryption works.

[@kyzercube]

This power raise number @ 8:45 65,537. Does it have any relation to the number of internet ports which is at 65,563?

[@linnaea_lavia]

+kyzer cube no. 65537 was chosen because it has only two 1's in its binary representation, which would allow that calculation to be done faster on the computer. And it's a prime, and it's not too small. Using a small number, like 3 which some people used to use, may cause the result of m^e to be to small for the modulo operation to mean anything, and you would end up with a ciphertext that can be decrypted by raising it to the power of 1/3, which is easy for a computer to do.

[@_tarnished_]

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

[@leonjacob5846]

Quick question. At 4:35, he says "like we did before, we're going to divide by 10." The secret number that the bank has is 3, so I understand that we should cube each number in the code. But why do we divide by 10 afterward?

[@FostersLab]

Okay, I'll take a wild guess here: There is a reoccuring scheme in the way cubed numbers end with a certain digit. i.e. if any number ends with a 1 then its cube ends with a 1. It goes the same with 4, 5, 6, 9 and 0. But they also work in pair: if any number ends with a 3 then its cube ends with a 7, and the other way around. 3 and 7 form a pair, and 2 and 8 form a pair. This way, if you have a cube's last digit, as is the case for the bank, you can find the original number's last digit by cubing it again and looking at the last digit.. Hence looking at the remainder of the division by 10. This is a particular case because no encrypted number (or, in this case, "letter") is bigger than 10, so you're certain that no two encrypted numbers will be the same. But I don't know how you can generalize this with other numbers than 3 and 10, which, by the way, is the "real" key as the product of two prime numbers.

[@Elliesium37]

Basically, you pick two prime numbers, you do a set of calculations with them, and you will end up with Modulo value : n , then you will have public key : e , and secret key : d . To encrypt the data, you use this: (data)^e mod(n) ... and to decrypt : (data)^d mod(n)...

[@AnuragSingh-rh8li]

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.

[@niabride7636]

these animations are the best! :D you are google too, but send my thanks to animators!

[@Vulcapyro]

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.

[@DocteurZeuhl]

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).

[@telaferrum]

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.