Prime Numbers & RSA Encryption Algorithm - Computerphile

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.


This video was filmed and edited by Sean Riley.

[Sashenke]

Very hard to follow without visual representation of formulas and examples

[davidgillies]

It should be noted that RSA's exponent of 65537 is chosen because it is a) prime and b) 2^16 + 1 which is 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.

[paradicsompaszta]

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.

[charlieguan]

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.

[giga-chicken]

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.

[MegaRad]

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

[oliviervanlier]

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

[Twisted_Code]

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

[QYong-rqiw]

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

[QuantumHistorian]

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.

[JmanNo]

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.

[johnagapi]

The videos you are presenting are rare. Thank you

[oknpryk]

Please, add visual representations and timecodes. Timecode simplify the navigation through parts of video.

[ebadulislam]

Nice video of Jim Carrey explaining RSA.

[Antuan]

Can't watch it, very bad sound!...

[Uerdue]

Fun fact: Choosing modulus n = 5*7 = 35 and encryption e = 13 gives extra security! Try it out!

[blendingdude]

Legend says someone is trying to find the two prime factors since the release of this video to this day

[EmaMazzi]

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

[kahnfatman]

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!

[saddygamer]

Bruh I watched all the RSA videos rn for my project and shocked to see another one.