Speaker A
This video was sponsored by Coursera. If you and I wanted to, let's say, pass notes in class such that if anyone opened the note up, they would have no idea what it said, but we can still figure it out.
An introduction to cryptography covering classical ciphers, modular arithmetic, and key exchange methods.
Key Takeaways
- Simple ciphers like Caesar are easy to break, motivating more complex methods like Vigenère.
- Modular arithmetic is essential for understanding encryption and decryption processes.
- Frequency analysis can be used to crack repeated-key ciphers if keys are reused extensively.
- Secure key exchange is a critical problem in cryptography to prevent eavesdropping.
- Number theory provides the mathematical tools necessary for modern cryptographic algorithms.
What the video covers
- Explains basic encryption using the Caesar cipher and its limitations.
- Introduces the Vigenère cipher as a more secure method using a secret key.
- Discusses modular arithmetic and congruences as foundational math for cryptography.
- Explains the concept of wrapping numbers around a clock to understand modulo operations.
- Highlights the importance of relatively prime numbers in modular division.
- Describes frequency analysis as a method to break ciphers by analyzing letter frequency.
- Introduces the challenge of secure key exchange over public channels.
- Mentions the Euler's totient function (Phi) and its relevance to cryptography.
- Touches on number theory as the mathematical basis for modern cryptographic methods.
- Emphasizes that many cryptographic theorems exist beyond the scope of one video.
Chapters
- 00:00Introduction and Caesar Cipher Basics
- 00:43Decryption and Limitations of Caesar Cipher
- 02:00Modular Arithmetic and Letter Wrapping
- 02:40Using Secret Keys and the Vigenère Cipher
- 04:47Modulo Congruences and Number Theory Concepts
- 07:27Key Exchange Challenges in Cryptography
- 09:11Properties of Relatively Prime Numbers
- 10:32Frequency Analysis and Cipher Vulnerabilities
- 15:23Advanced Number Theory and Cryptographic Theorems
- 20:12Summary and Introduction to Number Theory
Full Transcript — Download SRT & Markdown
Speaker A
there are several methods for doing this for example maybe beforehand we could agree on shifting all the letters by three in order to encrypt our message otherwise known as the Caesar cipher so if I wanted to say hello I'd write a
Speaker A
There are several methods for doing this. For example, maybe beforehand we could agree on shifting all the letters by three in order to encrypt our message, otherwise known as the Caesar cipher. So if I wanted to say hello, I'd write a
Speaker A
that I send you then when you receive the snow all you do is ship the letters three to the left and you get the original message back but this is too simple so if someone could just try a
Speaker A
word with those same letters shifted by three. Instead of H, I'd write K, since K is one, two, three letters past H. Instead of E, I'd write H. L goes to O, and O goes to R. So this is the encrypted message
Speaker A
bunch of gibberish otherwise known as the cipher text that we saw earlier this is then decrypted back to plain text and this is what we just did using our specific encryption and decryption algorithm of shifting by three but let's
Speaker A
that I send you. Then when you receive the note, all you do is shift the letters three to the left, and you get the original message back. But this is too simple, so if someone could just try a
Speaker A
well since the message is longer than the key I'll just rewrite the key repeatedly until the end and now what you do is really just add the letters C is the third letter of the alphabet so we I go three past Y now since Y is at
Speaker A
bunch of shifts and figure out what the original message was. But hopefully, you can see the foundations of cryptography are pretty simple. You have some message you want to send, or the plain text like hello, and you encrypt this to create a
Speaker A
quickly remember that Z is the 26th letter so you could say 27 corresponds to a 28 with B which would make 30 go with deep and we can do this for the rest of the message to get our cipher text to
Speaker A
bunch of gibberish, otherwise known as the cipher text that we saw earlier. This is then decrypted back to plain text, and this is what we just did using our specific encryption and decryption algorithm of shifting by three. But let's
Speaker A
gave us B which is the second letter but we really know that 25 plus 3 is in fact 28 in fact we could say that 28 corresponds with 2 and we'll use this symbol to show that but this works
Speaker A
do something else instead. Let's come up with a secret word or key that will swap around the letters for us. For this scenario, let's just say our secret key is computer, and now I want to encrypt the message you can trust me.
Speaker A
is really 14 so 14 corresponds with 2 on a 12-hour clock because just like with the alphabet you wrap around to the beginning now the official way to write and say all of this is 14 is congruent to 2 modulo 12 the visual way to think
Speaker A
Well, since the message is longer than the key, I'll just rewrite the key repeatedly until the end. And now what you do is really just add the letters. C is the third letter of the alphabet, so we I go three past Y. Now, since Y is at
Speaker A
modulo 12 then algebraically the reason 26 is congruent to 2 mod 12 is because if you subtract 26 + 2 the result is divisible by 12 or you can see that 20 is congruent to 8 mod 12 since 20 minus
Speaker A
the end, all we do is wrap around back to A. So we go three letters past Y, wrap around, and land at B. O is the 15th letter. If we add O or another 15, we get 30, and to figure out the letter more
Speaker A
branch of mathematics used for cryptography but first the encryption we are just using is known as the Visionaire cipher which is used during the sixteenth century however there's a problem with it though if we used our secret key many times like over hundreds
Speaker A
quickly, remember that Z is the 26th letter. So you could say 27 corresponds to A, 28 with B, which would make 30 go with D. And we can do this for the rest of the message to get our cipher text to
Speaker A
comes up about nine one percent then a which comes up about eight point one percent followed by oh and so I was curious about this so I found an online frequency analysis tool and copied in the first chapter of Harry
Speaker A
decrypt it. You would just subtract by the secret key. Now, that wrapping around we just saw is actually the start of the real math I'm gonna get into soon. So we just saw the 25th letter Y plus the third letter C
Speaker A
is important in cryptography so now let's talk about key exchange or how to establish a secret key when you have to exchange it with someone over a public champ so I'll start this with a question a friend and I want to share a secret key
Speaker A
gave us B, which is the second letter. But we really know that 25 plus 3 is in fact 28. In fact, we could say that 28 corresponds with 2, and we'll use this symbol to show that. But this works
Speaker A
let's say it's a new friend so you guys don't know much about each other now the question is is this task even possible to come up with a secret key that only you two can understand but the eavesdropper cannot well give that some
Speaker A
specifically for the 26-letter alphabet, and this is the same math you do as with a 12-hour clock. If it's a lemon o'clock, disregarding a.m. or p.m., what time will it be in 3 hours? Well, obviously it'll be 2. But 11 plus 3
Speaker A
algebraically it's because 10 minus 6 is divisible by 4 visually if I had a clock with only 4 numbers I just kept wrapping integers around it 10 and 6 would land at the same location and since 10 is 5
Speaker A
is really 14, so 14 corresponds with 2 on a 12-hour clock because just like with the alphabet, you wrap around to the beginning. Now, the official way to write and say all of this is 14 is congruent to 2 modulo 12. The visual way to think
Speaker A
arithmetic we can apply to this like could I divide both sides by 2 and get 5 is congruent to 3 mod 4 well no this is incorrect because 5 minus 3 is not divisible by 4 but why didn't that work
Speaker A
about this is if the integers continue to wrap around a clock, 14 plus 2 would land at the same place. In fact, if we kept going, 26 would also land there, which means 26 is congruent to 14 as well as 2
Speaker A
2 from both terms does this also mean that this part the 5 minus 3 is also divisible by 4 well clearly that's not true which means 5 is not congruent to 3 mod 4 and one way to think about this is
Speaker A
modulo 12. Then algebraically, the reason 26 is congruent to 2 mod 12 is because if you subtract 26 minus 2, the result is divisible by 12. Or you can see that 20 is congruent to 8 mod 12 since 20 minus
Speaker A
just divide by 2 and have something that's correct but look at this 72 is congruent to 12 mod 15 which should be easy to see at this point if I divide both sides by 2 I get 36 is congruent to 6 mod 15 and this
Speaker A
8 is divisible by 12. Same goes for all these pairs of numbers on the clock. So this is where we're headed, and I'm going to get back to this soon, but this is the beginning of number theory, the main
Speaker A
the number that you're dividing and the modulus are relatively prime then you're able to do the division and relatively prime just means 1 is the only number that can go evenly into both like 9 and 10 are relatively prime since nothing
Speaker A
branch of mathematics used for cryptography. But first, the encryption we are just using is known as the Vigenère cipher, which was used during the sixteenth century. However, there's a problem with it. If we used our secret key many times, like over hundreds
Speaker A
equals 15 times some integer n if we factor out a 2 we get 2 times 36 minus 6 equals 15 times some integer n now you'll notice that the prime factors of 15 are 5 and 3 which means this side of
Speaker A
of messages, an adversary could intercept those, and using frequency analysis, they can eventually decipher what our original messages were. In the English language, the most popular letter is E, which comes up about twelve point seven percent of the time. Next up is T, which
Speaker A
again relatively prime then the five and the three must appear in this term and in fact five times three times two would get us what this is thirty and that means that this term is divisible by 15 because it contains the factors five and
Speaker A
comes up about nine point one percent, then A, which comes up about eight point one percent, followed by O and S. I was curious about this, so I found an online frequency analysis tool and copied in the first chapter of Harry
Speaker A
is obviously wrong and six is not relatively prime to 15 since three goes into both of them now those are some of the basics but there's so many theorems in this field that no one video could cover but a lot of them show some really
Speaker A
Potter, and the most popular letters corresponded pretty accurately. O and A were just a little mixed up, but yeah, using this, there are ways to crack the Vigenère cipher over many, many messages. You can see that having a key
Speaker A
we can see that 2 to the 4th or P minus 1 is congruent to 1 mod 5 since to the 4th is 16 16 minus 1 is 15 which is divisible by 5 but instead if P is let's
Speaker A
is important in cryptography. So now let's talk about key exchange, or how to establish a secret key when you have to exchange it with someone over a public channel. So I'll start this with a question. A friend and I want to share a secret key,
Speaker A
subtract 1 from it that will be divisible by a hundred and thirteen there's another similar theorem but to understand it let me first ask this how many integers less than or equal to 10 are relatively prime to 10 well there's
Speaker A
or in this case, a secret number. Now, the problem is there's an eavesdropper who can see or hear anything that we say or write or whatever. Okay, literally anything. We can't use another language, we can't whisper to each other, or nothing like that. And
Speaker A
could be Phi of 15 is 8 because there are 8 integers that are relatively prime to 15 notice for a prime number that Phi of P is always P minus 1 and this is because nothing goes into a prime but
Speaker A
let's say it's a new friend, so you guys don't know much about each other. Now, the question is, is this task even possible? To come up with a secret key that only you two can understand, but the eavesdropper cannot? Well, give that some
Speaker A
integer n is always congruent to 1 mod n assuming that X and n are relatively prime so if n is 15 we saw that Phi of 15 is 8 meaning some integer let's say 14 raised to the 8th power is congruent
Speaker A
thought because now we've reached a point where we need the real math I want to talk about, or number theory, aka the study of integers. So pop quiz: is 10 congruent to 6 modulo 4? Well, yes it is.
Speaker A
always equals P minus 1 so if I use P for n here and then plug in P minus 1 up here I get X to the P minus 1 is congruent to 1 mod P which is the same
Speaker A
Algebraically, it's because 10 minus 6 is divisible by 4. Visually, if I had a clock with only 4 numbers and just kept wrapping integers around it, 10 and 6 would land at the same location. And since 10 is 5
Speaker A
couldn't figure it out or at least they'd have a very difficult time trying to figure it out even if they had a computer you
Topics:cryptographyCaesar cipherVigenère ciphermodular arithmeticnumber theorykey exchangefrequency analysisencryptiondecryptionEuler's totient function
