Cryptography | The Mathematics of RSA and the Diffie-Hellman Protocol

Click here to enroll in Coursera's "Cryptography I" course (no pre-req's required): click.linksynergy.com/deeplin...
STEMerch Store: stemerch.com/
Support the Channel: / zachstar
PayPal(one time donation): www.paypal.me/ZachStarYT
If you missed part 1: • The Mathematics of Cry...
Instagram: / zachstar
Twitter: / imzachstar
Join Facebook Group: / majorprep
►My Setup:
Space Pictures: amzn.to/2CC4Kqj
Magnetic Floating Globe: amzn.to/2VgPdn0
Camera: amzn.to/2RivYu5
Mic: amzn.to/2BLBkEj
Tripod: amzn.to/2RgMTNL
Equilibrium Tube: amzn.to/2SowDrh
►Check out the MajorPrep Amazon Store: www.amazon.com/shop/zachstar

[@zachstar]

In case you missed part 1: kzbin.info/www/bejne/q3_dkoComNqHg5I

[@zeuscesar]

Good 2 part video dude! thanks for that!

[@cardcode8345]

Which college major should I go for Computer science or Electrical engineering?

[@ajaydabral5672]

Wanna discuss with you something ,if possible to contact you

[@Michael-vf2mw]

@@cardcode8345Mechanical

[@raadwan]

Now I'm smarter than I ever intended to be. Thank You.

[@mfadhilal-fatih1427]

Ye

[@zajec11]

After trying to understand this algorithm for about 4 months, this single video has effectively set in motion the change of my life

[@JamesPerez328]

I learned the Caesar Cipher and RSA Encryption in my Hardware Security class. It's honestly so cool.

[@fiNitEarth]

Wtf i just randomly got the first part recommended, watched it and landed here 20 minutes after the upload xD So thats kinda creepy :D

[@mhh5002]

Second here. U r such an underrated KZbinr. Another great video again

[@digitalconsciousness]

The new thing in cryptography now is lattice cryptography. The idea is that you form a multidimensional lattice with vectors that are mostly orthogonal, read in your byte from your plaintext (ex: 'g'), find a lattice coordinate that is also 'g' (you associate L points with bytes), but instead of choosing the cardinal coordinate of that lattice point, you choose a point near it; that point is then written to your ciphertext. It is impossible for an attacker to read the point from the ciphertext and match it to the lattice to discover the byte it is because they do not have the lattice basis (vectors) to reconstruct the lattice. All they have is a random point in space. They cannot even reconstruct the lattice from many sample points because the points were not chosen at the exact lattice coordinate: they were only chosen near them. So the sample of all points is completely random. The math part of this comes in with cryptographers wanting to represent a string of vector coordinates as a polynomial. They are, as I understand it, able to write coordinates (4,7,3,5,etc) as a polynomial, then they appear to write the exponents of the polynomial + coefficient backwards and this is the final thing that is written to the ciphertext. Anyway, if you ever feel like exploring the polynomial aspect of it and doing a video about it, I would love that. It's cutting edge stuff, mainly because lattice encryption is resistant to quantum computing attacks so far.

[@qigongandthemartialarts3273]

you do an excellent job explaining things in your videos keep up the good work

[@baraaali4147]

Really good videos! I'm watching this to educate myself on what I want to major in and this by far has made computer science a really interesting and fun field.

[@AjayKumar-fd9mv]

Omg, this is great. Keep posting such great videos.

[@zdravkotraykov3752]

Thank you so much! You explain it so simple and easy!

[@vovan101]

The only explanation of correctness I found after 2 days internet search. Thank you very much.

[@SzechSauce]

Awesome thank you so much for the super clear explanation!

[@thedoublehelix5661]

The proof for Euler's Theorem is so nice. You should do a video on that!

[@matt-in8td]

You actually saved my exam, I did not understand DH protocol at all. Thanks a lot!!

[@arwaaldurehim2727]

After studying number theory in my math major classes I’m glad to know all its applications and how cool it actually is

[@sky-sight]

You know a video is good when there are more then 9k views but 0 dislikes there is usually that 1 hater who dislikes and leave so good job.

[@dreaminfinity7716]

Mindboggling 🙄😮😮

[@kid_kulafu_1727]

We want more!!!!!

[@inshafahmed8656]

Ur awesome man!!!

[@mbjelica947]

Great videos on cryptography! How about maybe sometime doing a video on Nikola Tesla and his inventions, including some of the technical aspects? So fascinating and revolutionary.

[@zachstar]

Thanks! And could definitely be a good video idea. I’ll see what I can do with that.

[@shivashankar28]

Please we need more Electrical engineering videos not CS stuff

[@skyline7532]

This is awesome

[@gamesniper98]

You’re awesome

[@samgallon1273]

First video I have ever seen with 0 dislikes despite having more than 10 k views

[@chinkeehaw9527]

Sam Gallon Now it has 4 dislikes

[@aashitashyam6060]

People probably saw your comment and disliked the video just to prove you wrong.

[@hassanm.1887]

@@aashitashyam6060 true

[@OneCatholicSpeaks]

Interesting video. I was just thinking that if the uncracked code was a string of letters, then I could enter that string into a computer programmed with the formula. Have the computer cycle through possible cypher numbers until a string of three letters to a viable word such as or and see if the rest of the cypher follows and translates.

[@jayh5992]

You should maybe mention what is considered a "safe prime number" on the Diffie-Hellman.

[@andreavecchio4674]

at 7:23, shouldn’t x and n(so m and n in the demonstration) be coprime to apply euler’s formula? Great stuff btw

[@stevenshrii]

If you know e, but to find d.. d=1:while(d< some-number){if ((e*d) mod n)= 1){print d}:d++} it will show all the possible of d

[@rocksonrong8401]

Hey I have a question. I noticed that there can be multiple values of d(private key) (e.g.- d=63 also works for the above example). But isn't the private key supposed to be unique?? How do you explain that??

[@carlfels2571]

I take Cryptography I at my university this semester :)

[@benoit__]

So, the key is chosen by the Prime number and number on the Diffie-Hellman Protocol or is it random?

[@user-um7tw6kx4r6]

That Stanford course is NOT for beginners, unless "beginners" means "advanced math students, who never used their advanced math for Cryptography specifically"!

[@aizhigitmamatov5214]

why do the values you and your friend select for diffie hellman protocol have to be less than the mod divisor (in this case 23)?

[@BrunoValleBR]

How did you get to congruent to 8 in the first calculation?

[@1Backi]

Thank you for the Video - im trying to get warm for potential studies next year and even for someone that didnt study much of anything durring the last decade it really gives some understanding in how these encryptions can work - so big credits for that. I actually have a hard time understanding why the mod(N) is not really "reflected" in the term m^ed at 6:39 if some smart people want to explain it to me :-)

[@gamereditor59ner22]

Interesting notion. Can one time pad work with end to end encryption to pass the secret key successfully without "Eve" detecting it?

[@zachstar]

Technically yeah it could but you need a key for the one time pad anyway so if you were able to establish that key somehow beforehand then you wouldn't need to send one.

[@gamereditor59ner22]

@@zachstar Thanks for the information and keep up the good work!

[@woobilicious.]

Addition & subtraction under modulo 128/256 in binary is just xor, and most symmetric cyphers just generate a fake one time pad that is xor'd with the plaintext. And again xor'd to decrypt.

[@-B-n-S]

when I divided the value of G to the power of A by the Value of P i got a remainder of 0. is that a problem?

[@alleygh0st]

So what you are saying is p and g are the public key, a is my own private key and g^ab (mod p) is our secret key? Or am I missing something?

[@steventran739]

Make video about architecture

[@erdemyilmaz6172]

Can you make a video on sha256?

[@user-dg8rr8pl6f]

I have a question, what do e and d mean?

[@AakashKumar-gl2fk]

Today I felt: Prime numbers r prime for many reasons. Salute to all prime numbers serving for humanity and cryptography

[@imagineaworldwhereallyourw7859]

5:00 Not explained how one chooses 7 and 23; is 23 easy to calculate knowing 7 and Fi(N)?

[@SamvitAgarwal]

Doesn't the entire security of RSA rely on the value m then? Since an eavesdropper knows e,n and the value of m^e mod n, couldn't they just brute-force to find the value of m?

[@hughjazz4936]

Yes, they can. That's why those values are chosen such that bruteforcing it would take 10 to 15 years with the best computers available. Every code can be cracked given enough time, but the point is that this time is long enough for the message to not be relevant anymore. Once computers get fast enough to crack codes in a reasonable time, you simply choose bigger values.

[@MSneberger]

It is thought that the number of atoms in the universe is around 10^80, which is roughly equivalent to 2^265. This means that brute forcing a 256-bit encryption key would be equivalent to counting every atom in the universe, which while theoretically possible, is not "really" possible.

[@rizolli-bx9iv]

Generally euler theorem is the fundamental of cryptography

[@BederikStorm]

Is it Dan Boneh's course?

[@tomtian895]

turns out your professor may not care more about your grade than an youtuber.

[@gazfilm693]

2:27 ".. and this means they either need the value of a or b. Either one works because once they have it they can figure out what this entire value is." Um, what? Huh? Why? How? Thank you

[@rickyleung5890]

why can't the eavesdropper solve the equation? e.g. 5^a mod 23 = 8 i.e. 5^a = 23n + 8 where n is an integer i.e. a = log(23n + 8, 5)

[@zachstar]

How are you gonna find n? n is gonna be so big that even a super computer wouldn’t be able to do it fast enough.

[@mathematicalninja2756]

I would use quantum computer to find the discrete logarithms.

[@Darticus42]

Mathematical Ninja good luck finding a quantum computer with more than 5 qubits and can run Shor's Algorithm

[@Darticus42]

Ricky Leung also keep in mind that the primes everyone knows (23 and 5 in the example, and thus 8 as well) are also extremely large. Taking a log of a number like that is also going to be very difficult with a classical computer when you have to compute it so many times to find a and n

[@SeeingGreenDevils]

ok so do we use RSA OR DH? or are they used together? i know DH exchanges secret keys so why need RSA? I'm missing something there obviously.

[@woobilicious.]

Both are used, DH is used to exchange a key for symmetric algorithm (because RSA is slow), but RSA is used for identity authentication, so you're not doing DH with Eve pretending to be Bob (man in the middle attack)

[@maddyIncubus]

where is the link to the course ?!

[@zachstar]

top of description

[@zajec11]

How do you select e and d? It seems that you've picked them somewhat at random, but what are the rules for picking those numbers computationally?

[@jameswang7362]

You can select e relatively prime to phi(n) and then compute d (the multiplicative inverse of e) with the Extended Euclidean Algorithm.

[@Gotta270101]

Great video! But please somebody help me out: at 6:32 you raise (m^e) to the power of d. But how? You don't know m^e, you just know (m^e MOD N). Shouldn't (m^e MOD N) be raised to d?

[@1Backi]

same question, could you find an answer?

[@Tejas-mm6tu]

Hey did you get ans?

[@Tejas-mm6tu]

@@1Backi hey did you get ans?

[@1Backi]

@@Tejas-mm6tu kzbin.info/www/bejne/rYmlXomVgMqcq5o&ab_channel=ArtoftheProblem i guess this helped me understand better

[@UMAIRKHAN-cz3pn]

Make a video on blockchain also.

[@jamesedward9306]

I realize this is an old video, with the most recent comment being several months old but I have a specific question on some confusion I have. First let me say I viewed part one and this video and I'm with it all except for a small part at the 1:30 -1:50 mark. As you summarize how it all works you say that what you and the friend did was: (g^b)^a (mod p) (g^a)^b (mod p) and that = g^(a*b) (mod p). But that's not what you actually did a little earlier. You did g^a (mod p) and sent THAT result to your friend, who then applied his secret key, b to it. And you did vice versa. Thus yielding your common secret key, or 2. With the notation (g^b)^a (mod p) are you saying 5^4^6 (mod p) ?? 5^4^6 is an enormous number. Shouldn't that notation read read: ((g^b) mod p)^a (mod p) = 2 the shared secret key. I only raise the issue because you talk about g^(ab) and I don't see you doing that exact calculation anywhere earlier. It could be I just don't understand mod notation. Zach or anyone else, help here would be appreciated. Big fan Zach, love your stuff.

[@PandaBros863]

Can someone explain how he got 5^6(mod23)=8, I saw his first video but I don’t understand the math behind this specific problem I’m lost

[@moveonvillain1080]

5^6mod(23)=remainder of ((5^6)÷23) which is 8

[@moveonvillain1080]

This mod is what u use in programming language , its the algebraic operator denoted by % in programming language

[@PandaBros863]

Tanay Verma thank you

[@tsunami5884]

why is the 0 with a line in it 5?

[@hammadibrahim39]

It's phi (φ), not 5.

[@PhysicsBro-xb8qx]

WHAT IS YOUR DEGREE OR PROFESSION IN MY OPINION YOUR A ENGINEER

[@Thmyris]

He is an engineer

[@adrianokano8949]

He is an Electrical Engineer

[@x78340]

He is a Math wizard

[@rickh3714]

I have just posted my new Zodiac Killer Z340 decryption. It is in a Billowy wave format not in the dreaded cryptographical grid beloved of some mathematical types! Please click on the round abstract humanoid profile icon to see. Thanks.

[@Darticus42]

Rick H rule 1 of crypto: never roll your own crypto

[@harjitsingh7308]

Darticus the Great that doesn't mean you can't make your own crypto and play with it ;)

[@rickh3714]

Darticus the not so great? What rot! This case has not been 'solved' for 50 years because people have not thought outside the box. There are no explicit rules for the cryptographical methods of the esoteric and unhinged. They subvert the existing orthodoxies don't they? I have solved- to a coherent English sentence and pertinent appended German word , by an 'Archimedean' spiral algorithm, the Ebeorietemethhpiti letter remainder of the Z408. Also the Riverside Confession letter's 50 year hidden Morse transcript. 'Intestis as I hone Z... Mete Stine I ensure it fund... etc etc. My Z34O solution may not satisfy an exclusively (myopic?) mathematical mind that is blind to the visual and geometric clues of an esoteric thinker. Godel himself showed that solving something and being able to provide a mathematical proof are not necessarily co-evident. What is wrong with finding a ' liquid' state solution to the Z340? 'Zodiac' hints at this a multiplicity of times with his wordplay (some in Latin). There are more clues to the initial 340 keyword in another communique that I have yet to present. Throw away Occam's rusty old razor and conventionality when it comes to esoteric coding and highly complex personalities.

[@unitedstatesofindia1460]

Only 44k made it .... Not-at-all-strange

[@alwaysincentivestrumpethic6689]

Difficult

[@matthewto7406]

First again?

[@rakra4551]

what's with the annoying background music ?

[@TheRealInky]

Mind your ps and qs :D

[@xamael1989]

Your looks more like 5

[@ShopperPlug]

Coursera is garbage, Udemy.com is way better.

[@shivashankar28]

Please we need more Electrical engineering videos, not CS stuff

[@Darticus42]

Shiva Shankar Nah this is fine too