How the "Unbreakable" Vigenere Cipher Was Broken
Vložit
- čas přidán 10. 06. 2024
- In this weeks video we dive deep into cryptography and explore the vigenere cipher. What it is, how it was created, and most importantly how it is broken. The mathematics surrounding this cipher is fascinating and at the end we show one way you make this easily broken cipher much stronger and actually unbreakable again!
Here is the code to break from the end of the video:
Ho nhdh fh tye dbplei? Iq hojty, tks twee-wlzi-X-uje-wvfh qlevhfdn zs xbcpii frf qwe kedqetr. Jhh rltse’t nbll wyeq mlj sgefwcxcrlom txlc uvs fi bvcdipt sye fok'i sve lbqd yfuu triuie. Wvb siwflqratp iq okhwvrlbd ihzs tibhtzoq zfts niwv xc idpowzxt rsvijetzoq vfsdvn esktakh wvb fuvswwlc. Tye vhrseet kop pn zdho lu tye nwkss ff vwqjakirbp ihrt vvb licl hbzduethf fc hvr owct, aed zvbc tye uspeoesh todm khh hbpcyeu rltse’t ddmay ko dbv df khhgb hikudhfdnj, tks jptyepoqxcj shsjh ujeosph. Blt lh fh fiaxrraeet wc xhslmh hept ne nbll ak a pcjtnk oi fbulvcwwlc tye nwkss ff vwqjakirbp xn nhlqe le dijvq jsv srabihznj. Ken? Bvcdipt wv drb’q znfw zvxi wv drb’q znfw.
Math The World is dedicated to bringing real world math problems into the classroom and answering the age old question “when will I ever use this?”
We use unique topics for algebra, trigonometry, calculus, and much more and go beyond context problems and use a technique called mathematical modeling to find solutions to real world questions and real world problems. These videos are great for students who plan to enter technical fields that require real world problem solving, and can be a great resource for teachers looking for ways to bring real world contexts into their classroom.
Instagram: / maththeworld
Twitter/X: / math_the_world
Facebook: / maththeworldproject
Email: MathTheWorld@byu.edu
Created by Doug Corey
Script: Doug Corey and Jennifer Canizales
Audio: Doug Corey
Animation: Jennifer Canizales
Music: Coma Media
© 2023 BYU
Just as a note: The One-Time-Pad is not only improbable to solve by guessing the key, it is impossible. Since you could decipher the encrypted text to any other text of that length, you have no way of checking, wether you had the right key.
Indeed. The one time pad is not just cryptographically secure, but information theoretic secure. Even an attacker with infinite computational power cannot decipher it.
Key: paradox
Plaintext: So what is the answer? In truth, the when-will-I-use-this question is unfair for the teacher. She doesn’t know when you specifically will use it because she can't see into your future. The difficulty in answering this question lies with an implicit assumption hidden beneath the question. The student has an idea of the kinds of situations that she will encounter in her life, and when the response from the teacher doesn’t apply to any of these situations, the mathematics seems useless. But it is fraudulent to assume that we know at a moment of reflection the kinds of situations in which we might use something. Why? Because we don’t know what we don’t know.
………..
this channel needs more subscribers 😭😭😭
Mathematical cryptography was my favorite math class in college! I like cryptographic stuff, it's really interesting, and an oddly practical use case for number theory.
It can be made stronger by modifying the encryption key at each round of encryption.
For example, the cypher can encrypt the first set of letters. The original letters can encrypt the next set, or the encrypted first set of letters can encrypt the next set. Any combination would work so long as the first set of letters could be decrypted using the key.
AES: CBC, PCBC, CFB, and OFB use such a method. The key could also be modified by some agreed method between each round as well: CTR.
Thanks for sharing this! That is clever (which is why I never thought of it).
Cryptography is just some of the most fun math.❤
(Knowing that it's much easier to decrypt a message encrypted by another message) I would have shifted the message by a certain amount (say 30 positions) and subtracted that from the original message. If you guessed an amount that corresponds to the length of the key, then the result is a (part of the) message minus another (part of the) message. And if you run frequency analysis on it, you can use the fact that E-E will be the most common combination of two letters followed by things like E-S, S-E and S-S. All frequencies will be much closer to 1/26th than in a simple substitution cypher, but will still be detectable for a long enough message. This is kind of like what the technique around 4:50 does, except that that only considers occurrences of E-E and S-S, but ignores E-S and S-E.
I wonder how much stronger the Vigenere Cipher would be if you used a "secret" alphabet order. In that case you can't decode a whole group that corresponds to one of the letters in the key at once.
Great video!
As a cryptographer I love this video
Thank you!
I've heard of a one-time-pad hard drive getting shipped by Amazon or some similar company as a worst-case post-quantum encryption method. In that case it would be much easier to securely send one large hard drive for many messages than the individual messages themselves.
I dont really understand how you're supposed to spot the "coincidences" if you can only see the encoded text.
Although on the 3rd line I do notice "Ebi" and 9 letters later again "Ebi". Both of them just happen to be the word "the".
I can send you a otp using the square root of 2 I use as many digits as I have in the message you would know the length of the message and the next message would continue from where we left off
You have now introduced a path dependency. If one message gets lost or even just a part of it, you will no longer be able to decipher any subsequent message.
And while that approach has a certain elegance in the age of computers, your OTP is not random. The fact that makes it so easy to transport, makes it also vulnerable to brute forcing after educated guess. De facto you are using the same pad multiple times, so once it is broken, all your messages are broken. Which is in stark contrast to true OTP where each message is independent and has to be broken separately.
I partially agree with you I did not intend to start from the very beginning for each message I intended for the next message to pick up from where the last left off
Here is a variation of your method. Pick a root, such as a 5th root, that the two communicators will use, then the secret key can just be a number that is not a perfect 5th root. You can use the infinite decimal representation for the encoding and decoding.
Additional you can provide a function to step though your 'magic' number
This is kind of what stream ciphers do. They use an algorithm or function (in this case "decimal expansion of the square root of the secret number") to turn a short secret (in this case the single digit number "5") into a stream of arbitrary length. And that stream can then be used like a one time pad.
The only problem here is that the secret key "5" is very easy to guess (it's the 5th key anyone brute forcing this guess would try), and that "decimal expansion of the square root" is not introducing very much randomness.
Please put the secret message in a comment or the description, thanks!
Ok, I will put it in the description. Just give me a few minutes.
@freshrockpapa-e7799 Here is the code: Ho nhdh fh tye dbplei? Iq hojty, tks twee-wlzi-X-uje-wvfh qlevhfdn zs xbcpii frf qwe kedqetr. Jhh rltse’t nbll wyeq mlj sgefwcxcrlom txlc uvs fi bvcdipt sye fok'i sve lbqd yfuu triuie. Wvb siwflqratp iq okhwvrlbd ihzs tibhtzoq zfts niwv xc idpowzxt rsvijetzoq vfsdvn esktakh wvb fuvswwlc. Tye vhrseet kop pn zdho lu tye nwkss ff vwqjakirbp ihrt vvb licl hbzduethf fc hvr owct, aed zvbc tye uspeoesh todm khh hbpcyeu rltse’t ddmay ko dbv df khhgb hikudhfdnj, tks jptyepoqxcj shsjh ujeosph. Blt lh fh fiaxrraeet wc xhslmh hept ne nbll ak a pcjtnk oi fbulvcwwlc tye nwkss ff vwqjakirbp xn nhlqe le dijvq jsv srabihznj. Ken? Bvcdipt wv drb’q znfw zvxi wv drb’q znfw.
What about this method. Both the sender and user have the same dictionary. Then the secret key could just be a word in the dictionary, but that is not what you use to code and decode the message. Both use the letters that come right after the key word in the dictionary and go as far as needed for the message. This makes it a one-time pad, but solves the problem of passing a long secret key.
Just as said by someone. Use the square root of 2 or pi or any other irregular pattern. Pick a starting point and some function to move through the digits and you can code/decide your secret message
@@troncooo409 but someone pointed out that if a message gets lost, or there is just one error, then it throws off the ability to decode. Although with computers, I guess you could just keep moving down the infinite decimal one space at a time until you get a comprehendible message.
This is reminiscent of a 'book code' - essentially, you and your partner both own a copy of a particular book, and agree on some way to know what page to use to encode-decode a given message, then use the text of that page as your encoding-text for any messages you send. If the middleman attempting to break your code doesn't know what book you're using, nor how you are choosing your page, then they won't be able to break the cypher, since the page text will generally be longer than any message you will send this way.
Yippe
Spoiler warning...
The key is "paradox".
There are two instances of the word "tye", which stick out as likely meaning "the", and the word "Ken?" almost certainly starts with "Wh". From that, we get the partial strings "ara" and "ox" as part of the key word.
The two instances of "tye" are 224 characters apart, so the key length is probably a factor of 224 (2,4,7,8,14,16,28). A length of 2 or 4 is impossible, given the partial strings known. With a length of 8, the positions of "ara" and "ox" in the key would collide. This leaves 7, 14 or 16 as the possible key lengths.
If it's 7 then the 2nd and 4th character should be an A, and every letter that's at 2 or 4 (mod 7) shouldn't be shifted. Checking the frequency of 2nd and 4th characters reveals that there are 6 and 17 E's respectively at those positions, the 4th and 1st most of any character. This makes it likely that the length is indeed 7.
Using this, the beginning of the text becomes "?o wh?t i? the". This quite obviously ends in "what is the", and the next word is "ans?er", revealing the final missing letters of the key: Paradox.
So what is the answer? In truth, the when-will-I-use-this question is unfair for the teacher. She doesn’t know when you specifically will use it because she can't see into your future. The difficulty in answering this question lies with an implicit assumption hidden beneath the question. The student has an idea of the kinds of situations that she will encounter in her life, and when the response from the teacher doesn’t apply to any of these situations, the mathematics seems useless. But it is fraudulent to assume that we know at a moment of reflection the kinds of situations in which we might use something. Why? Because we don’t know what we don’t know.
Alternatively: In the last sentence, "drb’q" appears twice, 14 characters apart (making the key length either 7 or 14), and the "b'q" must be "n't". This again gives the partial string "ox" at the end of the key word.
Or we may just guess at this point that "?ara?ox" is "paradox", and be done.
Lesson: Having a key word that includes two instances of the letter A a distance of 1 or 2 apart risks revealing the word "the" in the message.