Lecture 2: Modular Arithmetic and Historical Ciphers by Christof Paar

For slides, a problem set and more on learning cryptography, visit www.crypto-textbook.com

[@VladimirDjokic]

Some professors are boring but this professor makes learning interesting and fun! Thank you :)

[@IvoirRienna]

Agreed 100%

[@Sudiptmalakar2009]

100% correct

[@alexkotusenko302]

100% correct

[@YahyaKhan1254]

Write

[@rvgprodss]

keep preachin

[@mr.shanegao]

Modular arithmetic 0:01 Rings 52:30 Shift(or Caesar) cipher 1:14:40 Affine cipher 1:23:00

[@mdtanveerhasan1453]

bless your heart

[@all462]

I just started learning German, and being able to recognize few german words just feels amazing. Plus I am learning cryptography.

[@muthuramaganesh]

Excellent..I liked they way the professor explained equivalence classes passionately. My target is to finish this course for the pleasure it gives. I have done my under graduation 20 years before

[@vgdevi5167]

elo, I'm about to start my CS undergrad in 3 months, any other course recommendations pls?

[@alialtan8182]

Hi, my recommendation for you is to NOT start with cryptography, but start with mathematics for computer science, networking or a low level language course (learn C++ 😅).

[@Xardas_]

I love the fact that we're learning new words in german as well ! Thank you.

[@diencai1812]

Watching this in 2022! Thank you for making this available professor (I am still awake at 37:30!!!)

[@thebudkellyfiles]

This professor is on fire! I never had a professor with this much fervor and energy and brilliance, and I have well over 300 semester credits, mainly math, science, and computer science. This course is freakin' amazin' and free!@#$%

[@itsworkinprogress]

Loving the lecture and I really appreciate, that you explain what is meant by the special mathematical notations. In a lot of books an lectures it is just anticipated, that you know it, but how? Thank you for making learning easy.

[@abstractapproach634]

Quick tip, using the negative mod can be very useful, what time is 23:00? Notice 23 is one less than a multiple of 12, thus 23 ≡ -1 (mod 12) so you know 23 ≡ 11 (mod 12) thus it's 11pm. (Of course 23 - 12 is just as easy, but when numbers get larger negative modulo equivalents can make life easier)

[@jerrymahone335]

are there learning algorithms associated with cryptography? ie can a crypher be taught to defend it self from attacks?? an AI crypher would be a great thing.

[@Stillshot10200]

Maybe I missed something. At 1:29:14 he said gcd(13,26) = 2. Isn't it 13?

[@finne5450]

Yes

[@topdayunky4134]

​@@finne5450 isnt gcd(12,26) = 2 ? making 12 a bad number for a? I thought the gcd had to exactly equal to 1?

[@anatolicvs]

my professor uses mr. paar's book "Understanding Cryptography - A Textbook for Students and Practitioners" for our "Network Security and Cryptography" lesson, so I'm very much glad to watch him lessons on youtube, on the other hand, him explanation is far better than others did. thank you for sharing these series.

[@EmielBlom]

"Since there are only 26 different keys (shift positions), one can easily launch a brute-force attack by trying to decrypt a given ciphertext with all possible 26 keys. If the resulting plaintext is readable text, you have found the key." @1:20:40 Sure, from an attacker point of view there is a 26 sized keyspace, only after 26 iterations of shifting will you have %100 certainty to see the decrypted version of the ciphertext But is this true for choosing a key? Because you have 26 minus 1, so 25 possible 'shifts'. Maybe purely from a mathematical point of view shifting by 26 would be "correct", but in practise the result would be the same plaintext again, so is the 'keyspace' always defined from an attacker point of view?

[@littlebigphil]

If the identity key doesn't count for choosing a key, then why would it count for an attacker? The attacker only needs to perform the 25 shifts that would actually be chosen to get a 100% certainty.

[@kishsaam]

Sir you are a genius... nobody can ever make cryptography simpler than this....

[@deemdoubleu]

I'm a bit confused about the "a equiv r mod m". In programming we would say r = a mod m. Why isn't it "r equiv a mod m"?

[@kylebrown2903]

I love this. I've always wanted a more in depth look into cyphers. Is this a university where students to learn english while learning other subjects? Ich moechte wissen wo und was diese ist.

[@introductiontocryptography4223]

Thanks for your interest. We are just a plain German university (and are, of course, public :)). Teaching is mostly in German, at least the B.Sc. courses. We have every year several foreign exchange students, that's why I had taught this one year in English. The approximately 150 students in the room are 1st year students and since most of them are German, I explain some tricky questions in German. Regards, christof

[@kylebrown2903]

Danke für ihre beantwörte! Ich studierte Computer Ingenieurwesen als hauptfach und natürlich Deutsch als nebenfach an der Uni aber möchte immer lerner. Ich wünsche ihnen nur das beste.

[@arulselvalakshmi3806]

Great lecture prof. I'm no expert. But around 1.29.00 How can #a be 12? isn't gcd(12,26) =2 ? and not 1? apologies if im wrong :)

[@introductiontocryptography4223]

+arul selva lakshmi The possible values for "a" are: (1,3,5,7,9,11,15,17,19,21,23,25). Hence, #a = 12 Cheers, christof

[@arulselvalakshmi3806]

Just realized it was a silly question '#a'.. !! Thank you Prof :) Cheers, Lakshmi

[@mukul30051990]

cheers Mukool :P :P

[@JohnSmith-he5xg]

Why can't you exceed 26? gcd(27,26) =1 (unless I goofed)

[@introductiontocryptography4223]

Note that for the affine cipher all arithmetic is done mod 26. That means that 27 == 1 mod 26 and, thus, the value of "a" must be from (0,1, ..., 25). hope this helps, christof

[@padakoo]

Wow, wish we had more Professors like you Sir. Thanks for sharing this.

[@peeledbanana311]

Clocks are actually infinite sets that just increment the day by 1 every time the base of 24 is satisfied. And we are just truncating the incrementing day value. A better example of a modular set would be the alphabet, since once you get to the end of the set, it doesn't increment a higher place value. If a clock is a modular set then it follows that the decimal system's 1s place is a modular set if you don't show the tens place.

[@hachimitsuchai]

@1:08:35 how did he get 2^-1 ≡ 5 mod 9? And @1:13:18 he uses German to describe a structure that uses all four operations + - * /. What is the English? Field Structure?

[@officialversetile1770]

in the video he said the set Zm ={0,1,...m-1} i get that. but how many Modules are there ? 1- infinity or does it end ? just trying to clear this up ?

[@prajganesh]

In the notes, he has total key space for Caeser Cipher is 26! is it just 26 or 26!?

[@opticintrusion6063]

Thank you, thank you, thank you!!! I was struggling so much with the modular arithmetic and why the number of keys in the affine cipher is 312. Now I understand. THANK YOU!

[@roseb2105]

i have a stupid question so would we replace 3 to the expondent of 8 with any number from the 7 equivalence classs and then see how many time 7 goes into that number to find the remainder

[@prakashgourav]

This is an incredible lecture, thanks Prof Christof Paar! Kudos!

[@roseb2105]

can pick any number basically to sqaure beacuse the set is inifinite so even if 4 was from the 5 equivalence class it is also form the 7 equivalence class so I can square it to get a smaller number which is easier to divide by 7?

[@abhayahettiarachchige6853]

i wish i had a prof. like you during my studies. your teaching is very nice and active. thanks a lot

[@ThatNateGuy]

This is a fantastic tutorial series. I will almost certainly purchase your book, Herr Paar!

[@erikwg3814]

He looks like an older, German version of David Tennant... Great Lecture and thanks for all the wisodm!

[@freshman04]

thanks for the great lesson! I think at 1:29:07 there might be a Freudian slip because gcd(13,26) does not equal to 2.

[@yoloboss1432]

Hi Professor Christof May I ask please why the remainder was taken in to account on 43:00? The equation before that was totally understandable but why did we enquire about the remainder of diving 55 to 5? Many Thanks and thank you for continuously supporting us

[@introductiontocryptography4223]

+YOLOBOSS In this example we always look at results that we obtain if we compute modulo 5. Please have also a look at the first equation (2 lines above the 55 = 0 mod5 line). There we consider 200 modulo 5. Hope this helps. regards, christof

[@markmatter2411]

I'm watching this lectures and studying from your awesome book for my cybersecurity exam and i'm loving it. I just wanted to thank yo for making this fantastic lectures available on KZbin. If you will ever read this comment i'd like to learn modular arithmetic deeply. Can you recommend some books for beginners? Thanks a lot!

[@SS-605]

Hi Professor, Thank you for your video lectures. Can you please tell from where we can get access to the homework. Also I want to ask do you have lectures on other subjects too like discrete maths?

[@introductiontocryptography4223]

For problem sets, please visit www.crypto-textbook.com and go to online course -> videos. The solutions to the ODD NUMBERED problems are also on the website, look at "book". Sorry, but we are not allowed to release the other solutions. cheers, christof

[@roseb2105]

so instead of 81 you take i number from the equivalence class?

[@roseb2105]

also im confused with equaivalence class if I create an equivalence class of ( 7, 15,22, 29,3 etc) and of these numbers if i substitute them instead of 81 I will get a remainder of of then i would get 1 mode 7? someone please explain.

[@thehumancondition3]

27:46 how is it possible to have a remainder of 7 if a = 12 and mod = 5? Surely it should be 8? Where am I going wrong?

[@nournote]

5 does not divide 12-8 (which is 4)

[@raghavendraprabhu1913]

Thank you professor.. your lectures we're really helpful. It is a great service you are doing by putting it on KZbin

[@roseb2105]

so to clarify we can replace the 81 with any number form the 7 equivalence class such as 13 and get the correct remainder?

[@introductiontocryptography4223]

13 would not be correct, but 11 would work. regards, christof

[@phanikrishna7450]

Hi Sir , I have one question. Let's consider ( 13 * 16 ) mod 5 Here i replace one with +ve and one with -ve number ( 8 * -4 ) mode 5 = -32 mod 5 Does this equal to 3 or 2 ?

[@introductiontocryptography4223]

Since -32 = (-7) * 5 + 3 it follows -32 = 3 mod 5 regards, christof

[@CarloLavezzari]

You must turn the clock's arm in the opposite way

[@potkettle]

This was great. Looking forward to watching the remainder (pun intended) of the series soon. Based on where I am now in my career, this is what I wish I'd studied at university.

[@Elitios]

Thanks for th lectures! I'm leraning a lot thatnks to you. Out f curiosity, what happens in a shift cipher when you chose a key that varies, for example 3+position of the letter in the alphabet?

[@introductiontocryptography4223]

+Elitios In principle, a varying key is a good idea. However, your proposal will not work. In your example A and N would both be mapped to the same ciphertext with the shift cipher. Assume k=1, the "A" would be encrypted as e(A) = 0 + 0 + 1 = 1 =B but also e(N) = 13 +13 + 1 = 27 = 1 = B mod 26 But again, a varying key is exactly what we need for a strong cipher, but it must be constructed wiith a more sophisticated rule. Cheers, christof

[@Elitios]

+Introduction to Cryptography by Christof Paar Oh! I see. Thanks a lot for the answer christof!

[@TheAnimeist]

@9:30 "And what we're going to do for the next 80 minutes ..." Pure gold.

[@DavidTheSkeptic]

I found your lecture series, I find them quite informative, thank you for making them available

[@roseb2105]

so is what makes cryptography challenging is the key is the remainder but with the same a and m you can get so many different remainder?

[@mastaskep]

This is at the undergraduate level? What is the major?

[@DeckSeven]

A finite set is one which resets to 0 or some other start-value when a certain end-value is overreached. Programmers call it "overrun". In other words, it's a fixed number range. The complete range of ASCII codes 0 to 255, for instance, is a finite set too. If you add 1 + 255 you get 0 again. Same with time. After 2359 hrs comes 0000 hrs again and not 2400 or 2401. So "finite set" basically means "fixed number range". That's how a crypto developer like me calls it. And yes, you can envision it as a circle, a loop or even a ring.

[@officialversetile1770]

ReptorULTRA7 are modules infinte or finite . meaning mod 1,2,3,4,5.... does it reset at a certain nunber or keep going ?

[@cipherbenchmarks]

Could this also be called a base? Such as octal hex or decimal then?

[@JamesBall-v1s]

Christof! you are such a good teacher and professor. Honestly so based - your students are extremely lucky

[@AndreyLomakin]

Would be cool to see more course videos conducted by the professor Christof Paar

[@samkelemdoyi3720]

wow thank you for the privilege of a step by step understanding of the concept and it's inside. God bless you

[@Chaaminda]

The way he was teaching stored subject matter in mind clearly.

[@roseb2105]

but then if i take 15 and i square and I divide by 7 my remainder is not 2?

[@YahyaKhan1254]

Does we shuld learn any programing language for advanced cryptography

[@aakashnair4031]

Sir, One doubt..........in the clock method you told 24 is the remainder.....Then how does 6 made the remainder

[@greenlight6436]

Hello, is it possible to find the Homework you give to your students somewhere ? :)

[@introductiontocryptography4223]

Please visit www.crypto-textbook.com and click Online Course -> Videos. You'll find the complete problem set for each chapter of Understanding Cryptography. My lectures closely follow the book. Under Book -> Solution Manual you'll find the solutions to all odd-numbered problems, i.e., Problems 1, 3, ... cheers, christof

[@greenlight6436]

+Introduction to Cryptography by Christof Paar Oh Vielen Dank ! Your courses are really helpfull

[@roseb2105]

what would be the value for your y in the equation x=a-1(y-b)?

[@cbzha]

A perfect lecture to learn english, computer science and German. :)

[@TheGenerationGapPodcast]

And latin

[@aayushpaudel2379]

Isn’t gcd of 13 and 26 = 13 itself ? Or is it 2 ? 1:29:05

[@MikhailFederov]

Yes. It's 13

[@dermaoling]

it is really helpful, and making cryptography lecture very fun!!!

[@epictetus__]

Sir which book were you refering to in class?

[@introductiontocryptography4223]

The lecture closely follows my textbook "Understanding Cryptography": www.amazon.de/Understanding-Cryptography-Textbook-Students-Practitioners/dp/3642041000 Please note that the 2nd edition should become available in appr. 2 months.

[@amrmahdi8522]

why is mod(n) used so frequently in cryptography?

[@elishawaugh]

Why does 13 not work in the last problem? I am confused

[@5Pectral]

because though 13 is prime it is divisible by itself and 26/13 = 2, thus gcd(13,26)= 2 and not 1

[@bluejimmy168]

Great job, this lecture was actually fun and easy to follow.

[@dimitrisproios1860]

Are there some solutions to the writtent exercises of crypto-textbook?

[@introductiontocryptography4223]

Please visit www.crypto-textbook.com and click Book -> Solution Manual. You will find solutions to all odd-numbered problems (1, 3, 5, ...) from the book. Enjoy learning cryptography!

[@avrelyy]

Very clear explanation of integer ring. Thank you!

[@youmah25]

great lecture may i ask you what text book you are using???

[@introductiontocryptography4223]

+Youcef Mahdadi Sure, we are using "Understanding Cryptography" by Jan Pelzl and myself. The video lectures follow the book very closely. You find more information about the book and sample chapters at www.crypto-textbook.com. You may also want to check out the reviews at Amazon.com. People seem to really like the book. Regards, Christof

[@youmah25]

Danke i will download the book

[@roseb2105]

how is frequence perserved with a -b forumula?

[@klabboy13]

So around 50:00 the professor refers to a mod 5 class and substitute 81*81 with 4*4. Wouldn't he need to make a mod 7 class and substitute 2.

[@tehwinsam3522]

yes it require to do so , the final answer will be 16 ≡2 mod 7 . i think he didn't do the final step but in his book he show up the final answer as the answer which i have mentioned .

[@user-pi6mx]

What's the purpose of blocking the transcript?

[@SkynetDrone12]

Thank you so much, you make learning this fun and so interesting and not easy but much easier!

[@md.rezaulkarimreza2763]

{ON 1:29 } The gcd(12,26) = 2. But the inverse will only exist if gcd = 1, then how could #a =12. Somebody please help me out here!

[@tehwinsam3522]

#a is the number of possible answer for a . "NUMBER" . {1,3,5,7,9,11,15,17,19,21,23,25}

[@younglatino134]

awesome and im learning a little bit of german lol

[@youmah25]

Ja

[@RecursiveTriforce]

Nikt wirklik

[@amitsrivastava5391]

Is their any more session of yours on ECC ?

[@caffeinetablet2898]

37:51 I don’t speak German. Did he call out students? If so, good for him!

[@shivertalks1691]

Yes he did :)

[@pradippaul9703]

You are absolutely great teacher.. I have learnt so many things..👍

[@ramyfarid2296]

The lectures are great, I am really grateful, professor

[@АлексейБыстров-с1ю]

Thank you so much, that was great. How did you even decide to record the lessons? I thought it was a kind of secret. Or else one won't need to enter the university :D But don't stop, if you occasionally see my comment, please!

[@Pulkit__7]

I love how you wake everyone who were sleeping during important topics lol

[@Pulkit__7]

Lol, there is also a comment of go back to sleep 😂💀

[@HighArchingCrests]

57:50 the chalk makes the Mario theme rhythm

[@mrnobody1321]

if A = m*q + r, and we have 15*17 = X mod 6, we're just replacing (m1*q1+r1)*(m2*q2+r2) but every term having m is divisible by "6", then you're left with the remainders. In this case it could be (2*6+3)(2*6+5) and the only trouble is 3*5/6. so it's 3 mod 6 I guess the corollary is we can find remainders easier. It was a bit overly complicated from the video to me.

[@MissNorington]

1:19:35 (You subtract modulo 26). I am here to try to understand the modulo operator. So if you have the encrypted letter "b" which is 1, and you subtract the key 3, you will obviously get a negative number here: -2. Try dividing -2 with 26 to get the remainder and you will be surprised it is outside the alphabet set. The result is -2 for 1 - 3 mod 26. -2 is an integer still. It is just not the result you would expect. I am here to try to solve this by mathematics, and not by special exceptions such as, if the value before division is less than 26, add 26, just so we'll never go below 0...... I am not expecting this to be solved without special exceptions.

[@aparnaammu1444]

Very nicely explained. You are my inspiration.

[@DieFliegeinderSuppe]

BUCKLE UP NOW!! love it

[@colinwithers1969]

at 29:13 when defining the set the number to the right of 12 shoukd be 17 not 15

[@hannahjp1505]

In your lecture you said that the key space for shift cipher is 26. But actually, it is 25 only. Because shift by 0 is the plain text itself. Your lectures are useful for me and I am trying to listen all the lectures by you. Thanks and regards.

[@bartomiejjakubowski2900]

Hannah Jp Nope he's right. You have 26 letters in the alphabet shown @1:19:14. If you use modulo 25, you are never able to get "Z"

[@frtard]

Hannah JP, it's true that a shift of 0 results in plaintext, but it still in the key space. bartłomiej Jakubowski Yup. With the modulo operator, you can't get a result the same as the modulus. It *has* to be 26.

[@hannahjp1505]

bartłomiej Jakubowski You should not use modulo 25. It should be modulo 26 only. But the shift by 0 gives the plain text itself.

[@bartomiejjakubowski2900]

Hannah Jp Modulo is not for shifting here, only to stay within the range (alphabet). In this Cipher the shift comes from "K". PS: Now i got it, you are right.

[@hannahjp1505]

frtard Yes it is a genuine argument also. Thanks

[@smrititiwari8243]

thanks ! I liked it a lot.. as usual u were really clear and interesting . :) hope I complete the next too.

[@giovaniventrue3420]

How do you model a circular clock in code?

[@akhishesh]

You are a great professor, this course if helping me a lot. Thank you sir :).

[@peeledbanana311]

Zank yew fau zis lektur! Schnitzel-dwaf!

[@ovais217]

Excellent, excellent lecture !!

[@CarloLavezzari]

Is the gcd between 12 and 26 = 1?

[@introductiontocryptography4223]

No, gcd(26, 12) = 2 regards, christof

[@arbab64]

Thank you very much for your elucidated exposition. Good luck.

[@matiassolomon7198]

thanks for this video!

[@bananian]

26:33 hey that's also the line equation y=mx+b

[@nournote]

25:40 the remainder IS unique!!! It's your definition of the remainder that is non-standard and unjustifiably counter-intuitive.

[@JohnSmith-vs9oe]

Nice, interesting lecture. Thank you!

[@emmyzhou9552]

Thank you so much for these lectures!

[@itshertz37]

There is a mistake @1:29:15 - The gcd(13,26) is not 2, 13 is a prime, but it is 13 itself.

[@GrahamCrannell]

41:26 - i'll be honest, that *did* actually blow my mind a little bit. Dr. Paar wasn't lying haha. [edit] okay the part with the negative numbers *definitely* blew my mind

[@giovaniventrue3420]

Can modular arithmetic deal with mutiplication

[@nournote]

Of course.

[@sitinurayesyamdfuzi6723]

Can anyone tell me why at 1:29:25, the number of a=12?

[@sitinurayesyamdfuzi6723]

Already got the answer. Thank you Prof for this valuerable knowledge