A Brief History of Cryptography: From Art to Science

In May 2017, the WannaCry ransomware virus broke out globally, with some university students in mainland China reporting that their computers were attacked by the virus and documents were maliciously encrypted. The ransomware wreaked havoc, resembling a global internet disaster, causing significant losses to computer users. According to the latest statistics, over 100 countries and regions saw more than 100,000 computers attacked and infected by the ransomware.[1]

WannaCry is a “worm-type” ransomware software that uses AES-128 and RSA encryption algorithms to maliciously encrypt user software to extort Bitcoin. The AES-128 and RSA algorithms are excellent symmetric encryption algorithms used to encrypt communication information to prevent adversaries from obtaining it, but in the hands of criminals, they are used to maliciously encrypt users’ files, becoming tools for extortion. It is precisely because of the strong security of AES-128 and RSA that, to date, there has been no thorough solution other than patching system vulnerabilities to avoid infection.

So what are AES and RSA, such powerful tools that leave the world helpless?

To understand AES and RSA, first, let’s take a look at what encryption is and what cryptography is.

Cryptography includes cryptographic coding and cryptanalysis, and these two branches form a contradictory yet unified entity. A secure cryptographic mechanism promotes the development of more powerful analytical methods, while powerful analytical methods force the birth of more secure cryptographic mechanisms. They progress together in mutual struggle, so the history of cryptography embodies the wisdom of human civilization.

When discussing encryption issues, we are based on a communication model, assuming that two parties, Alice and Bob, communicate through an insecure channel while an attacker, Trudy, is eavesdropping on their exchange. This kind of eavesdropping is always difficult to prevent, so Alice and Bob need to process their exchanged messages into “text” that only they can understand, while to others, it appears as a pile of garbled characters.

Classical cryptography mainly uses substitution methods for encryption. The earliest encryption algorithms can be traced back to the time of Julius Caesar, who used the Caesar cipher, and during the time of King Wu of Zhou, the Yinfu Yinshi was used. The Caesar cipher is a simple substitution cipher technique, where all letters in the plaintext are shifted forward (or backward) by a certain number of positions in the alphabet. Here is an example of shifting forward by 13 positions:

Plaintext: goodgoodstudydaydayup

Key: 13

Ciphertext: tbbqtbbqfghqlqnlqnlhc

A slightly more complex substitution is the Vigenère cipher. Although this substitution encryption appears chaotic at first glance, it can be recovered through statistical methods. For example, by analyzing the frequency of letters in the ciphertext and comparing it with the frequency of letters in natural languages, the hidden encryption patterns behind the disordered ciphertext can be revealed. The author first encountered this encryption method in the chapter “The Dancing Men” of the Sherlock Holmes series, where it describes using simple little man patterns to replace English letters, and Holmes’s decryption method was frequency analysis.

1. Plaintext space P: a finite set of all possible plaintexts;

2. Ciphertext space C: a finite set of all possible ciphertexts;

3. Key space K: a finite set of all possible keys;

4. Encryption rule E;

5. Decryption rule D; for any key k, there exists an encryption rule ek and a corresponding decryption rule dk, and for any plaintext x, dk(ek(x))=x holds.

How to ensure the security of a cryptographic mechanism? Most people believe that as long as others do not know how the plaintext is encrypted, it is sufficient to keep the encryption algorithm confidential. However, this method is not reliable because the types of encryption algorithms are limited, and exhaustive searching is not impossible. Once the encryption algorithm is known, cracking it becomes a matter of minutes. Therefore, in the 19th century, Dutch linguist and cryptographer Auguste Kerckhoffs proposed that the security of a cryptographic mechanism does not depend on the secrecy of the algorithm. A cryptographic system should remain secure even if everyone knows the operational steps of the system, as long as the key is not leaked. Public encryption algorithms allow everyone to analyze and decipher them, which raises higher requirements for the security of the algorithm itself. Once an attack is successful, the results are generally published, allowing users of the algorithm to make timely adjustments to avoid greater losses. Currently, most civilian confidentiality uses public algorithms, but the encryption algorithms used for government or military secrets are usually still kept confidential.

The highest demand for cryptography is undoubtedly in the military field, where information is the most valuable. The leakage of a short message may determine the outcome of a war and the lives of thousands. During World War II, it was the Polish and British cryptographers who decrypted the Enigma machine used by the German army that turned the tide of the war and saved more lives. The representative figure in this history is Turing, and the 2014 film “The Imitation Game” brought this history to the public’s attention.

Turing

The Imitation Game

In 1949, Shannon published the paper “Communication Theory of Secrecy Systems”[3], which proposed the two major design principles of confusion and diffusion, establishing the theoretical foundation for symmetric cryptography (which primarily studies encryption systems where the sender’s encryption key and the receiver’s decryption key are the same or easily derivable). From then on, cryptography became a science.

Shannon

Symmetric cryptography mainly consists of block ciphers and stream ciphers. In block cipher algorithms, plaintext messages are divided into several blocks, and both encryption and decryption operate on these blocks. In contrast, stream ciphers use a key stream generator to produce a stream of key bits that is the same length as the message, which is then XORed with the plaintext. Stream ciphers encrypt one bit at a time, requiring greater processing power compared to block ciphers, making stream ciphers more suitable for hardware implementations, while block ciphers are more suitable for software implementations. Classic block cipher algorithms include DES and AES, while stream cipher algorithms include Trivium and the ZUC algorithm designed by Chinese scholars.

In the design of block ciphers, effectively utilizing diffusion and confusion can resist opponents’ attempts to infer plaintext or keys based on the statistical properties of the ciphertext.

Diffusion means that each bit of the plaintext affects many bits of the ciphertext, or that each bit of the ciphertext is influenced by many bits of the plaintext. This can obscure the statistical properties of the plaintext. Ideally, each bit of the plaintext should influence all bits of the ciphertext, or each bit of the ciphertext should be influenced by all bits of the plaintext. For example, this occurs in the ShiftRows part of AES. Confusion means making the statistical relationship between the ciphertext and the key as complex as possible, so that even if opponents obtain some statistical properties regarding the ciphertext, they cannot deduce the key. Using complex nonlinear substitutions can achieve better confusion effects, such as using multiple S-boxes, while simple linear substitutions yield poor confusion effects, such as the Caesar cipher. Products and iterations help achieve diffusion and confusion, and of course, this process should be reversible.

In 1976, Whitfield Diffie and Martin Hellman published the paper “New Directions in Cryptography”[4], marking the birth of public key cryptography, for which they received the Turing Award in 2015.

The characteristic of public key cryptography is the use of two related keys to separate encryption and decryption operations. One key is public, known as the public key, used for encryption; the other key is kept secret, proprietary to the user, known as the private key, used for decryption. Public key cryptography is fundamentally different from earlier cryptography because the basis of public key algorithms is no longer the substitutions and permutations proposed by Shannon, but is based on a special mathematical function — the one-way trapdoor function. The characteristics of the one-way trapdoor function are: easy to compute, but difficult to invert, satisfying the following points:

1. If k and x are known, it is easy to compute y = fk(x);

2. If k and y are known, it is easy to compute x = fk-1(y);

3. If y is known but k is unknown, it is infeasible to compute x = fk-1(y).

Here, easy to compute refers to being solvable in polynomial time, while infeasible computation refers to a time complexity that is exponential.

The most classic public key encryption algorithm is the RSA algorithm, constructed in 1978 by Rivest, Shamir, and Adleman using number theory methods[5]. It is theoretically the most mature and complete public key cryptosystem and has been widely used. The security of the RSA algorithm can be reduced to the difficulty of factoring large integers, that is, given two large prime numbers, their product is easy to compute, but given their product, finding their factors is very difficult. To date, there has been no reliable means to attack the RSA algorithm; as long as its key length is sufficiently long and used correctly, information encrypted with RSA cannot be cracked. This is why the WannaCry virus is so difficult to deal with.

With the advancement of human technology, the computational power of computers is growing rapidly, which undoubtedly provides powerful tools for cryptanalysis, thus raising higher requirements for the security of cryptographic mechanisms, driving cryptography practitioners to continuously innovate to protect the security of cyberspace. At the same time, we must remain vigilant to prevent cryptographic algorithms from harming users themselves and to avoid the recurrence of ransomware viruses like WannaCry. Ultimately, the weakest link in information security is the users themselves; many security incidents are not due to technical vulnerabilities, but human negligence. Therefore, we hope everyone can pay attention to cryptography and protect their own security in cyberspace.

1. Tencent News: Global Outbreak of Computer Ransomware, Many Universities in China Attacked http://news.qq.com/a/20170513/001170.htm

2. Stinson D R. Cryptography: theory and practice[M]. CRC press,2005.

3. Shannon C E. Communication theory of secrecy systems[J]. Bell Labs Technical Journal, 1949, 28(4):656-715.

4. Diffie W, Hellman M. New directions in cryptography[J]. IEEE transactions on Information Theory, 1976, 22(6):644-654.

5. Rivest R L, Shamir A, Adleman L. A method for obtaining digital signatures and public-key cryptosystems[J]. Communications of the ACM, 1978, 21(2):120-126.

This article is reprinted from the WeChat public account “Institute of Physics, Chinese Academy of Sciences” (ID: cas-iop)

The annual special issue of “Global Science” “Multiverse Special Issue” is now on pre-sale! Buy now for an 8.8% discount. Click at the endRead the original text to purchase the exciting journal.