Puppy love and encryption for the first time: classical encryption

Recently heard anecdotal, the son puppy love, to the little sister plug “love letter” was intercepted by the teacher in charge on the spot. The son does not think however, reason is strong refute: “now everything must pay attention to evidence, the teacher you cannot slander me! It’s not a love letter at all!” . In desperation, the teacher handed over the love letter to the old father, I asked myself to deal with.

Caesar password

Old father I am a programmer, open “love letter” a look, good guy. As expected is biological (of course not refers to puppy love. , write a love letter are thick programmer breath.

LoryhwkuhhwklqjvwkhvxqwkhprrqdqgbrxWkhvxql viruwkhgdbwkhprrqlviruwkhqljkwdqgbrxiruhyhu

Others may not understand, the old father can not know his own son’s trick? With his three-legged cat skills, classical encryption is the best he can do. The repeated appearance of WKH in the ciphertext was immediately revealed. This guy probably just moved all the letters in plain text by a certain number. For example, if all the letters are moved one to the right, a becomes B, b becomes C, and I love you is processed in this way, the ciphertext is J MPWF ZPV, naturally you cannot understand what is being said.

For this ancient form of encryption, brute force is enough. Take the frequent occurrence of WKH in ciphertext as a breakthrough, although I do not know how to move back, but a total of 26 English letters, I try 26 times also came out.

When we move back three places, we have “the,” which finally looks like an English word. Maybe it’s 3. Try moving the whole ciphertext back 3 bits:

IlovethreethingsthesunthemoonandyouThesuni sforthedaythemoonisforthenightandyouforever

Add space and punctuation,

I love three things:the sun ,the moon and you.

The sun is for the day ,the moon is for the night

and you forever.

Well, it’s nice. A mixed doubles dinner is a must.

The end of the story, to sum up the knowledge. The encryption method mentioned above is actually a very famous encryption method in the history of cryptography. Named after the Roman republican Julius Caesar who used it to communicate with his generals, it’s called the Caesar code. The number of digits it moves is called the key space, and the larger the key space, the harder it is to crack by force. However, the key space of Caesar cipher is limited and it is easy to brute force crack.

Simple substitution password

A fall into the pit, a gain in your wit. The son’s second love letter came again.

cjqtqtxxwzqtwnfqtxlskwnfqtxcwqxzzxewfxgjsxwhwlsxqbumbgfu bzekfzxwelbukbazjewmxqtwqygbllbelwzblxjnqtxfxxrlbuektxwzq

The word QTX, which appears repeatedly in the ciphertext, is similar to Caesar’s password, but as the son of a programmer, he would not make the same mistake. Based on the weakness of Caesar’s password, the key space is insufficient, and the encryption method adopted this time cannot be decrypted by brute force. It is easy to imagine simple substitution ciphers, also classical, in which each letter in the plaintext is replaced by another letter according to the substitution table. At first glance, it looks the same as the Caesar code, with letters replaced by other letters. However, because the simple substitution password is not moved by a certain number of digits, the letters in the substitution list are randomly corresponding. Again, take 26 letters as an example, A may correspond to X, b may correspond to N, in short, 26 letters correspond out of order. So, what is the key space for a simple substitution password? A can correspond to 26 letters, B can correspond to 25 letters, and so on. The total number of key Spaces is 26 * 25 * 24 * 23 *… It’s about 4 times 10^26, so it’s unlikely to be decrypted by brute force.

Here is a new decryption method called frequency analysis. In simple substitution ciphers, because the substitution table is fixed in one encryption, the plaintext letters and ciphertext letters are always corresponding one by one. Therefore, based on the frequency of ciphertext letters and the probability of the occurrence of plaintext letters in daily life, we can always see some clues. Here is the probability of letters appearing in ciphertext:

In fact, there is a certain regularity in the occurrence of plaintext letters. E is the most commonly used letter in English, with a frequency of one in eight. The nine most commonly used letters are E, T, A, O, N, I, R, S and H. More than half of all English words begin with t, a, O, S or W. Just 10 words (the, of, and, to, a, in, that, it, is and I) make up more than a quarter of a standard English article. Therefore, the longer the ciphertext is, the more likely it is to leak. Of course, the above example is very short, just for the convenience of frequency analysis.

It is always a good idea to replace e with the most frequently used letter in ciphertext. Here, replace x with e. To distinguish ciphertext from plaintext, plaintext is represented by uppercase letters:

cjqtqtEEwzqtwnfqtElskwnfqtEcwqEzzEewfEgjsEwhwlsEqbumbgfu bzekfzEwelbukbazjewmEqtwqygbllbelwzblEjnqtEfEErlbuektEwzq

The ciphertext above has replaced all x’s with E’s. The most common word in English that contains e is the, and qtE (highlighted in bold) frequently appears in the ciphertext above. If this is the, we can obtain that the ciphertext Q corresponds to the plaintext T, and the ciphertext T corresponds to the plaintext H. Continue to replace the corresponding letters in the ciphertext:

cjTHTHEEwzTHwnfTHElskwnfTHEcwTEzzEewfEgjsEwhwlsETbumbgfu bzekfzEwelbukbazjewmETHwTygbllbelwzblEjnTHEfEErlbuekHEwzT

The word EwzTH after THEEwzTH should be a word. Think of the word exxth. It’s easy to think of earth, and you can get the ciphertext W for plaintext A and z for plaintext R.

cjTH THE EARTH Anf THE lskAnf THE cATERREeAfEgjsEAhAlsETbumbgfu bRekfREAelbukbaRjeAmETHATygbllbelARblEjn THE fEErlbuek HEART

cjTH THE EARTH Anf THE lskAnf ,with the … and the … , where chTH should be with, Anf should be and, replace C, j, f with W, I, D respectively:

WITH THE EARTH AND THE lsk AND THE WATER REeADEgIsEAhAlsETbumbgDu bRekDREAelbukbaRIeAmETHATygbllbelARblEIN THE DEErlbuek HEART

A REeADE is probably a remade. Replace again;

WITH THE EARTH AND THE lsk AND THE WATERREMADEgIsEAhAlsETbumbgDu bRMkDREAMlbukbaRIMAmETHATygbllbMlARblEIN THE DEErlbuMk HEART

Ending Mk HEART could easily have thought of My HEART with Y instead of K:

WITH THE EARTH AND THE lsY AND THE WATER REMADE gIsEAhAlsET bu mbgDu bR MY DREAMl bu YbaRIMAmETHATygbllbMlARblEIN THE DEErl bu MY HEART

* * * * * * * * * * * * * * * * “Of my heart” is also a high frequency letter in the plain text, and “B” is also a high frequency letter in the ciphertext nine times, so it is probably “of”.

WITH THE EARTH AND THE lsY AND THE WATER REMADE gIsEAhAlsET OF mOgD FOR MY DREAMl OF YOaR IMAmE THAT ygOllOMlAROlEIN THE DEErl OF MY HEART

YOaR IMAmE: Your image YOaR IMAmE: Your image

WITH THE EARTH AND THE lsY AND THE WATER REMADE gIsEAhAlsET OF GOgD FOR MY DREAMl OF YOUR IMAGE THAT ygOllOMlAROlE IN THE DEErl OF MY HEART

OF GOgD FOR MY DREAMl, go what d, other than gold, there seems to be no word FOR gold. There seems to be no choice but to add the plural “s” after “dream”. Replace these two letters again:

WITH THE EARTH AND THE SsY AND THE WATER REMADE gIsEAhASsET OF GOLD FOR MY DREAMS OF YOUR IMAGE THAT yLOSSOMS A ROSE IN THE DEErS OF MY HEART

S what Y, sky, and Lossoms, great dictionary blossoms. K and B replace S and y:

WITH THE EARTH AND THE SKY AND THE WATER REMADE gIKE A hASKET OF GOLD FOR MY DREAMS OF YOUR IMAGE THAT BLOSSOMS A ROSE IN THE DEErS OF MY HEART

The general content is all out, manually render.

With the earth and the sky and the water,

remade, like a casket of gold.

For my dreams of your image that blossoms

a rose in the deeps of my heart.

Frequency analysis may seem cumbersome, but for professional translators, their extensive experience can be quickly deciphering. Simple substitution ciphers have been used for secret communications for hundreds of years, beginning before Christ. But after Arab scholars invented frequency analysis, the code was easy to crack.

conclusion

Caesar cipher is a kind of encryption method that forms ciphertext by moving the plaintext letters by a certain number of digits. Due to its limited space of key, it can be broken by force.

Simple substitution cipher is an encryption method that replaces plaintext letters according to the substitution table bit by bit to form ciphertext. It has a large key space and cannot be cracked by brute force, but can be cracked by using frequency analysis method.

The Caesar cipher is actually a simple substitution cipher.

Son again defeated, today is a women’s singles, the old father brain excessive. Before going to bed, I felt sorry to see my son and saw the notebook open with four big characters written on it, symmetric encryption! His sleeping son seemed to smile slyly.

See what happens next. (The above story is pure fiction. My son is 3 years old.)Copy the code

Article first published wechat public account: Bingxin said, focus on Java, Android original knowledge sharing, LeetCode problem solving.

More JDK source code analysis, scan code to pay attention to me!