Prime Numbers & RSA Encryption Algorithm - Computerphile
HTML-код
- Опубликовано: 14 май 2024
- RSA is widespread on the Internet, and uses large prime numbers - but how does it work? Dr Tim Muller takes us through the details.
Apologies for the poor audio quality of this video which is due to the remote nature in which it was recorded.
/ computerphile
/ computer_phile
This video was filmed and edited by Sean Riley.
Computer Science at the University of Nottingham: bit.ly/nottscomputer
Computerphile is a sister project to Brady Haran's Numberphile. More at www.bradyharan.com
It should be noted that RSA's exponent of 65537 is chosen because it is a) prime and b) 2^16 + 1 which is 10000000000000001 binary. This makes modular exponentiation very much faster without sacrificing security. We find e and d mod (p - 1)(q - 1) because that is how modular multiplicative inverses work. Out exponent e must be coprime to (p - 1)(q - 1) but it is very unlikely that if we choose e prime, a randomly chosen p and q will yield either p - 1 or q - 1 as a multiple of e. If we are unlucky, we just choose new primes. There are other factors in the choice of p and q that must be taken into consideration, such that even though they should be roughly the same size, they shouldn't be too close to sqrt(n) i.e. if you want a 2048 bit modulus, don't make both p and q be 1024 bits. Simple checks like this make cracking n much more difficult.
Thanks for the additional info!
Very hard to follow without visual representation of formulas and examples
And the audio quality is not the top of the best :(
open your terminal and cross-check, lol
i studied RSA in college a few years ago, and our assignments would often involve encrypting/decrypting messages by hand, so i could follow it & it was a nice refresher but yeah I can’t imagine how many people new to the topic would follow it
@@user46346bdtgry What's the course called?
you need more ram
Without visual presentation this is hard to follow. Math explanations without a whiteboard are like chess games without a chess board: very few can do it. Also where does p and q come from? You should have shown all the equations which were drawn on the iPad.
My understanding is that they can be any pair of prime numbers that are different from each other. Choosing a different prime number combos will result in a different public and private key. You can correct me if I am wrong. I am trying to learn this too.
Came here to say the same. I know how RSA works, and still I was a bit lost to what was going on. Needing to draw a whiteboard in your head is so much more difficult thatn to have it simply on screen. I know another channel which does nice visuals. I think it's called numberphile :-D
P and Q are sufficiently large random prime numbers chosen at random at the time of key generation. There are some rules for choosing P and Q, but, for the most part they're chosen at random.
tl;dr multiplying primes easy, factoring primes hard, p and q are secret primes used to encrypt stuff.
Ok so here's the deal, RSA relies on what is known as the fundamental theorem of arithmetic, which basically states that all composite numbers can be represented as a unique product of primes. For example, the number 15 can be repersented as 3*5, and those are the only prime numbers you can multiply together to get 15. If you get two very large prime numbers _p_ and _q_ (could be any primes, just make them hard to guess) and multiply them together, you obtain a new number _n,_ known also as the modulus. The thing is that while it's very easy for computers to multiply the two primes together, factoring them is as currently understood very hard; _n,_ due to the fundamental theorem of arithmetic, can only be factored into _p_ and _q._
The second trick to RSA is the Euler totient function. Basically the Euler totient function, in the case of a product of two primes p and q, spits out (p-1)*(q-1). The trick here is that you have to know the prime factors in order to calculate the Euler totient of _n_ (usually referred to as phi(n) or just phi), which means we can use to create a pair of public and private keys. By picking a number _e_ that shares no common prime factors with phi(n), we can do what's called the modular inverse to find a corresponding d such that e*d = 1 (mod phi(n)).
Due to some special properties of the totient function, we can now pick any number _m,_ raise it to the power _e_ to obtain some number _c_ modulo _n._ If we now take _c_ and raise it to _d_ modulo _n,_ we obtain _m._ We cannot obtain _d_ without first knowing the prime factors of _n,_ because _d_ is calculated using the totient function, which can only be calculated by knowing the prime fators of _n._
@@deidara_8598 thank you for taking your time and posting this
OMG. This is my cyber security professor this semester in Nottingham University. His tutorial is really nice and it is so nice to see him in the youtube channel.
This was very informative. With this I was able to make my own little set of encryption numbers by hand: powers of 7 and 63 reverse each other on modulo 253.
this video let me finally break the barrier on my understanding of how the PK and SK are related and enable encryption: exponentiation under modular arithmetic!
up till now, I got the understanding that the product of two primes is hard to factor unless you know one of the primes, but I didn't understand how that led to being able to create a one-way function that's reversible with another one-way function
The clock is a good way of explaining it visualy, but analytically show the full eqeation with the mod N or % N notation to avoid confusion ...
Probably the most convoluted way i ever heard to explain primeproducts, an RSA number is simply a primeproduct (two primes multiplied by eachother). You can use clockarithmetic to factor out the numbers not to explain what they are. Now find these two prime numbers is hard for some people to find, and it maybe that a single RSA 2048 primeproduct, simply can't be resolved in a lifetime on todays "homecomputers", on the other hand RSA 128 "message/challenge" which was used in the 90's is solvable in a matter of hours on a single 68040 Motorla processor found in any Amiga, Atari or Machintosh of the late 80's era.
Many thought that factorisation was a NP hard problem, but it has pseudolinear timecomplexity.
You probably should check that with Stefan Cronholm LiU IDA
A university professor making simple concepts unnecessarily convoluted? Hmm why am I not surprised 😂
The videos you are presenting are rare. Thank you
DITTO!!!!!!!!!!!!!!!!
You've got to write the equations down. No one can do more than a couple of lines of maths in their hand. Going through an example with small numbers is nice, but you have to show the actual formulas at the some point, not just say them.
Please, add visual representations and timecodes. Timecode simplify the navigation through parts of video.
4:43 say no more
the devil is in the details. Trapdoor functions are fun, but the beauty to me is in how they work and how they can be
Finally.... He is back
"deduce that m to the power of ed minus 1 simplifies to one on our clock, now because we have this minus one we have one little m leftover so what we end up with is one times m, which is m, which is how it cancels out in the end. :)"
???? what?? waht?? wahht???
It is CRAZY! I'm reading about group theory. That modulo clock and binary operations of members of that set constitutes a group! How cool!
I like your guitars! I've got a couple over in the corner of my family room. I hope you play yours more than I play mine. 🙂
Show the damn equations. Your words are wasted
x^d mod(n)=y, y^e mod(n)=x
p1 * p2 = n
7 * 13 = 91
6 * 12 = 72
d * e mod(72) = 1
d = 5, e = 29
18^5 mod(91)=44, 44^29 mod(91)=18
you've got your variables mixed up e.g. d=29, e=5
@@An.Individual it doesn't matter which order, the whole point is that it's reversible
@@MegaRad666 it could matter because the public key is n and e. if you supply d then e can be calculated
@@An.Individual ah. you're absolutely right then. my bad
Other tidbit that the video didn't properly explain is: x and y must be less than n, otherwise the reversibility ain't happening due to the nature of the mod operation.
I believe that why he choose to use clock analogy to make you to not think about number for x (or y) that is equal or greater than n. 6:06
Legend says someone is trying to find the two prime factors since the release of this video to this day
Thanks for the great explanation, I finally feel like I understand RSA!
Bruh I watched all the RSA videos rn for my project and shocked to see another one.
Very nice video; I understood everything except the last part. What did Dr Muller mean when he said M^((ED)-1) simplifies to 1 and then one little M left over? I did not understand the last part about the little M. I guess I have to research Farrat's theorem tomorrow.
There is something very strange with the numbers Tim chose for thise example. The encryption with the public or private key encrypts to the same cipheretext, which is not how asymmetric encryption is supposed to work. You can actually reverse the encryption using 91.
Fun fact: Choosing modulus n = 5*7 = 35 and encryption e = 13 gives extra security! Try it out!
Not sure who this Bruh person popular in the commentary is :-) All I can say, is that you gave a well paced, excellent informative video. Do keep it up.
Other than breaking RSA cryptography (which I suspect would upset a lot of people and Institutions) what possible applications could arise from any advancing in factorization technics
Can't watch it, very bad sound!...
6:30 and 7:00 where do the exponents 5 and 29 come from?
9:30 okay I see how someone with both the prime numbers can get the decryption key (29) now, but don't they need both prime numbers to get mod 72 (the 72 hour clock) and therefore determine that 5 is co-prime to this? I'm still a bit confused. Maybe I should keep watching...
wait, I think I get it! Is the first number "e" (in this case 5) just "handed out" as part of the public key so that people can encrypt data? oh that is brilliant... so basically, everyone knows e, but only someone that knows the factors of the modulus, or m which is derived from it, can decrypt blocks of data encrypted with e! that's beautiful!
Pretty neat that you noted down your thought process, it might help others understand it better.
Nice video of Jim Carrey explaining RSA.
What font do you use?
Extrauniversal artificial superintelligence can easily break those algorithms. I need lattice based post quantum algorithms
Here's my layman's question: I've been told (please correct me if this is wrong, it's from a single source) that all of the primes in the size range to be relevant to RSA have been found. How does this not make RSA susceptible to dictionary attack?
i know this is a late reply but hopefully it helps.
the problem comes down to combinations. while primes are rare there's still a lot of them. approximately n/ln(n) for range {0-n}. just between 0 and 100 we have 25 primes. of those 25 primes we have 300 pairs. (for n choose k the formula is n!/(k!(n-k)!) ) and as a general rule of thumb factorials grow faster than logs. so while might know every prime in that range, it would be hard to brute force every combination. (i hope this helps)
@@zackburton7500 that actually sounds much less secure than the alternative of taking “longer than the age of the universe” to compute… googled it a bit and found this much more convincing:
“RSA encryption, as per the standard, mandates the use of a padding method which includes random bytes, precisely to avoid the problem you describe. This makes RSA encryption non-deterministic (encrypt the same message twice with the same key, and you won't get the same output; but decryption removes the padding and recovers the message, of course).”
All of the primes up until RSA sized primes are not known. We know all of the primes up to around 4x10^18, maybe 10^19 by now. So that's maybe 20 decimal digits. 2048 bits is about 617 decimal digits long.
I think the challenge can not be solved with the given premisses. The modulus to factorize in two 300 digit primes is 617 digits long and when I square the largest number with 300 (decimal) digits (all nines) this results in a product which is only 600 digits long.
Hi Computerphile!
Please remake this video with visual explanations
Samwell Tarly: You know nothing "Very hard to follow without visual representation".
"it is easy for a computer to determine whether any number is prime, but not what its factors are". I knew that it is easy to check that a number is a strong candidate to be prime, or for some special types of numbers, but is it easy to check definitively for all numbers? Any videos on that already?
There are several (quite complex) algorithms to check the primality of a number. One of the most famous ones is Miller-Rabin. However, most of them (like Miller-Rabin) are "just" probabilistic. However, some years ago a few handful brilliant researchers also found a polynomial time algorithm (AKS primality test) for this problem (that unfortunately is still too slow for real life applications).
@@MrFair Hmm, thanks! However, just checking whether numbers up to sqrt(n) are a divisor is polynomial time already. Would not call that "easy", as said in the video. Or do you mean it is polynomial in the number of digits, hence O(log(n))?
I was aware of heuristics that mostly get it right, but that too is not making it "easy", in my view.
I guess that was a bit of an overstatement then.
@@landsgevaer Polynomial in the number of digits! :) And I definitely agree that it is not an easy problem and that this is an overstatement. You could see it from the viewpoint that there are fast algorithms, so it is easy in a way for a computer. But these algorithms are definitely not easy ;)
I had a problem. A calculator problem. With 70's calculator one could write text like 0.553 for Esso or 77345 for Shell. In finnish 'to Esso' is "essolle" or 3ll0553. What are the primes of it? So i wrote a script with Commodore 64 to find out. So the calculator story goes like this:
"Two countries had a battle for an oil field. One had 1231 and other 1021 troops. They fight 3 days. To whom did the oil field belong?
.
.
.
1231*1021*3=
3770553
Aka Essolle, " to Esso".
Hi, everyone. I'm about to start my computer science engineering and I want to be well prepared for it. I have two doubts that i would like to get an answer for.
1 is abstract algebra and number theory important in CS?
2 How much of these subjects should I study?
Thank you :)
read and study as much computer stuff as possible. that includes math, physics, electronics, history and you will be more than fine
Depends on what "start my engineering" means.
In general: no, it's not important UNLESS you go into something computationally-heavy. And there are tons of fields like that. Security, machine learning, visual computation, theoretical computer science...
So if you start at a university, you will learn a fair bit at the start of your studies just in case you will need it later.
But once you get past that, you are free to go into a direction where you're perfectly fine without.
It doesn't hurt if you still know a bit, though.
*Disclaimer: or at least you were at the university I went to.
So "how much should you study"?
AS MUCH AS YOU CAN STAND.
Because I'll be honest, there were moments at the beginning of my studies that would have been SO much easier if I had just known a bit more maths.
But I thought maths was too boring and didn't do that preparation myself, of course. :P
It is paramount. Study as much as you can.
I also study Computer Science & Engineering, and this could of course differ for your study, but neither is really that important in my opinion. Probability, linear algebra and set theory were of much more use to me. Just my experience though :)
ouch i feel this is the best video but with no whiteboard i am lost.... i'm sure the equations are vivid in his mind... i didn't know that RSA was based on a novel method like this though, thanks
I bet there's an algorithm that could clean up this audio
tell something about your strats
Should have used a whiteboard to show the calculations instead of his face, would have been more helpful
I wish I knew what I am going to do with this foreign, foreign knowledge ............... yet I force myself to ponder through it all ....... on a 'Friday night'.
even my $15 headset from 2010 had decent audio quality wtf is this
I'm sure there is a rainbow table of sorts that that contains the product of a significant amount of prime numbers. Why couldn't a lookup of this table be used to find the prime factors? Sure the numbers of entries would be absolutely massive, but computers are fast at these types of tasks.
Well, there are about 10^300 300-digit numbers, and only about 10^80 particles in the observable universe. You go ahead and create that lookup table, but when you invent some fancy new physics to create enough matter on which to store it, be sure to share it with the rest of us!
@@esquilax5563 how is the key created in the first place then? Oh wait, is this why creating it takes a very long time? Is the computer actually trying to find two 300 digit prime numbers without resorting to a dictionary?
@@polpotube it is trying to do that, but it doesn't actually take very long, because it uses probabilistic primality tests which are fast to execute. The process can give numbers which are expected to be prime, to within any desired threshold of probability, but doesn't actually guarantee it. I'll try to post a link in my next reply, but apparently RUclips sometimes deletes comments with links, so you might have to Google it
@@esquilax5563 by "very long" I meant like 5 to 15 minutes
@@polpotube it's more on the order of milliseconds. Maybe hundreds of milliseconds, but def less than a second
I can’t believe people who get interviewed still don’t get they need a proper microphone.
4:08 I wonder why the exponent is 2^16 + 1, can anyone explain this? I guess it's not just randomly chosen.
I think Mike Pound talked about this in a different video. Has to do with the ease of using the square-multiply algorithm, since in binary it's 10000000000000001
04:43 challenge accepted. Kind of...
Most intelligence agencies would pay better, though...
@@Uerdue hm i deleted it
@@Uerdue not that
Interesting, but I honestly don’t understand how this relates to the Diffie-Hellman key exchange.
Thanks for the information. It's a tough one though for most. people.
If instead, the 2 prime numbers were simply added together, I think it would be easy to decrypt, because there would always only be 1 answer.
"here are the secret plans": deathstar
Davie504 would be proud of this guy.
Does he plays bass?
Few visuals, and the audio is terrible. Feels like Computerphile sort of phoned this one in.
Where’s Mike Pound?
The audio is quite bad. A simple lapel mic or desktop mic would have worked much better than a laptop built-in mic. As a last resort, a pair of earbuds with an attached mic is ok. This audio is not ok.
I hope that offer will stand because I will be factoring it the moment I get access to a quantum computer that’s powerful enough
Challenge accepted at 4:43
So, how is it going ? XD
This is a really good explanation.
Thanks to Edward Snowden my favorite number is 2²⁵⁵-19
I can't process all of this.
I have cryptography exam in one week and was studying this right now
they dont offer classes like this in USA.. None of my Masters included cryptology and only briefly covered security and this stuff is kept secret....USA dumbed down hard since obnoxious Trump has been blowing his horn..
@@fokkenhotz1 I guess it depends. I'm not from the USA, but several of the most brilliant and important cryptographers work and teach at American universities.
you lost me at aroud 2:30 ;-)
wa GL4?
hard to follow if you dont show the formula, terrible explanation video, I understand the person knows a lot, but maybe he was confident those formulas will be shown on edition
The clock metaphor for remainder division/modulo is more confusing then helpful imo
use a visualisation rather than just saying out loud all the mathematical equations.
Didnt get this at all lol
diffie hellman explanation was way more understandable and clear
Not very clear explanation, i didn't understand a thing ...
a 600 digit randomly generated number, for visual purposes:
578888365663129492622608820118234364768663492993020406242022204476455824501802400932005342018698823339755181753664847201258392525761787865258634675248461394617611462098708361595646435400849504223730513648140094912587866359723807923191933166152318301534387812301653872562211060525739823648550632623636259744908085553684356155140779847578905695304250510474417656240606324720101213153461730988167222900973506877228946434680756251047331429593835840837979230616351286499565501355687066154968673457716510685042783324038125423282320515383004734120670621283061979664403602629265317569104102727515884734043435
what?
nice
just have a j then it's easy to follow
Can all you Genius uses atleast a whiteboard and no just use youtube for views
Not gonna lie, I can't follow through with the explanation past 8:45.
ث
69696969.... that's the number
thats= only 60 where's the nine???
@@fokkenhotz1 this video is fake the real answer i have commented 😆🤟
This was quite bad explanation. I couldnt follow basically any of it besides the single steps alone
Oof, make a powerpoint or something
"Where does the number 29 comes from?" - I don't know, but I can tell you where the number 69 comes from.
Rivest, Shamir, Adleman patented the algorithm, they did not invent it i.e. were not first to discover it.
You can't just leave a comment like that without also naming who actually discovered it. Unless it's unknowable?
stupidly parallelizable
pump up the size of the super computers
all smoke and mirrors, eye tricks
he sounded like a robot lol
Why is there something rather than nothing? 🤔
1. Is nothing a thing?
2. No, nothing is not a thing.
3. If nothing is not a thing, that means it can’t exist.
4. If nothing can’t exist, that means that everything can.
🤯🤯🤯🤯🤯🤯
And here I was thinking I had a terrible mic. Had to legit stop watching after 30s, shitty audio was too painful.
the other guy needs a better microphone
bruh
Pog
yee
awful