The Basics of Cryptography: Past and Present

Cryptography, derived from the Greek words "κρυπτός" (hidden, secret) and "γράφειν" (writing), plays a crucial role in securing information in today's world where data protection is more important than ever. Cryptography, as highlighted in my previous post on "Basic Privacy Protection Tools", is the foundation behind tools like GPG.

The history of cryptography is long and complex, and there is a significant difference between classical cryptography and modern cryptography. As Wikipedia mentions, classical cryptography primarily relied on the creativity and ingenuity of its designers and attackers, existing as more of an art form without clearly defined cryptographic components. In contrast, modern cryptography benefits from advancements in computer science, mathematics, and related fields. Therefore, a good grasp of cryptography requires a solid understanding of certain mathematical principles, particularly number theory. I plan to cover number theory in a future post.

Speaking of mathematics, its beauty lies in how something seemingly unrelated to daily life can quietly drive scientific and technological progress. Number theory, for example, was once considered purely theoretical with no practical application. However, with the advent of computer technology, many problems in computing found solutions within number theory.

Now, let's dive into cryptography!

Table of Contents

History

Cryptography has been used in warfare since ancient times. For instance, an ancient Chinese military text, "The Six Secret Teachings," recorded the following:

The Grand Duke said, "There are secret codes between the ruler and the generals, divided into eight levels. A code for major victories and capturing enemies measures one foot long. Codes for breaking armies and capturing generals measure nine inches. Codes for capturing cities and lands measure eight inches. Codes for repelling enemies and reporting from afar measure seven inches... These codes are confidential to the ruler and the generals to communicate secretly, ensuring that even the wisest adversaries cannot decipher them."

Simply put, "secret codes" involved using strips of varying lengths to convey different meanings, while "secret writings" involved splitting messages into three parts, which could only be understood when combined. Although historical Chinese documents related to cryptography are scattered, and information on classical Chinese cryptography is limited, it's clear that some forms of cryptography were practiced in ancient China.

Apart from China, cryptography also developed in ancient Egypt and Greece. One well-known method is the "Shift Cipher" (also known as Caesar Cipher), which reportedly was used by Julius Caesar on the battlefield. The encryption process involved shifting the letters of the alphabet by a set amount. For example, shifting every letter by one position to the left: 

Plain:  ABCDEFGHIJKLMNOPQRSTUVWXYZ
Cipher: BCDEFGHIJKLMNOPQRSTUVWXYZA

To encrypt a message like "HELLO WORLD," you'd apply the shift: 

Plain text:   HELLO WORLD
Cipher text:  IFMMP XPSME

Decryption simply involves reversing the shift.

Although these early methods vary in execution, they share a common flaw: the need for both parties to establish a prior "agreement" (like the shift key in the above example) through physical means. Anyone with access to this agreement can easily decrypt the message.

As time went on, cryptographic techniques became more sophisticated and harder to crack, but they still faced the same fundamental limitation. Even the famous Enigma machine from World War II couldn't escape this constraint. However, cryptographic understanding didn't stagnate—19th-century cryptographer Auguste Kerckhoffs proposed Kerckhoffs's Principle: a system should remain secure even if everything except the key is publicly known. With the advent of computers, the weaknesses of classical cryptography became glaringly obvious, leading to the need for a more modern cryptographic framework.

Modern Cryptography

Today, cryptography is a highly interdisciplinary field, but protecting information remains its primary goal. In this section, I'll focus on explaining some well-known encryption algorithms and their underlying principles.

⚠ Note:

Diffie–Hellman Key Exchange

In 1976, Diffie and Hellman introduced an important concept that allowed for secure key exchange over public channels, now known as the Diffie–Hellman Key Exchange. Although this method was met with resistance from the NSA, it was eventually presented at the International Symposium on Information Theory in 1977. You can read more about its history here. Interestingly, in 1997, the British GCHQ declassified information showing that their researchers had already discovered public-key cryptography in 1969. In 2002, Hellman renamed the protocol "Diffie–Hellman–Merkle Key Exchange" to acknowledge Ralph Merkle's pioneering work on the public-key distribution system.

Steps

Here's how the Diffie–Hellman exchange works:

  1. Alice and Bob agree on a large prime \(p\) and a primitive root \(g\) (i.e., \((\mathbb{Z}/p)^{\times} = \langle g \rangle \)). ⚠ Note: Both \(p\) and \(g\) are publicly known.

  2. Alice selects a secret \(x\) and sends \(X \equiv g^{x} \bmod p\) to Bob.

  3. Bob selects a secret \(y\) and sends \(Y \equiv g^{y} \bmod p\) to Alice. ⚠ Note: Both \(X\) and \(Y\) are now publicly known.

  4. Alice computes \(k \equiv Y^{x} \bmod p\).

  5. Bob computes \(k \equiv X^{y} \bmod p\).

  6. Finally, Alice and Bob share a common secret \(k\).

Principle

The principle behind it is straightforward:

\(k \equiv Y^{x} \equiv (g^{y})^{x} \equiv g^{yx} \equiv (g^{x})^{y} \equiv X^{y} \bmod p\)

The security of this exchange relies on the difficulty of solving the discrete logarithm problem.

Attacks

As mentioned earlier, the security of Diffie–Hellman hinges on the difficulty of solving the discrete logarithm problem. If a more efficient solution is discovered, the entire system could be compromised.

Here are two methods currently used to attack Diffie–Hellman:

Baby-step Giant-step

The Baby-step Giant-step algorithm is a brute-force method that directly addresses the problem. Here's a simplified explanation of how it works:

⚠ Given a cyclic group \(G\) of order \(p-1\), a generator \(g\), and an element \(a\), the goal is to find an integer \(l\) such that: \(g^l = a \bmod p\).

  1. Set \(m = \lceil\sqrt{p-1}\rceil\), ensuring that \(p - 1 \leqslant m^2\).
  2. Express \(l\) as \(l = im + j\), where \(i, j < m\).
  3. (Baby-step) Compute and store \(g^0, g^1, g^2, \dots, g^{m-1} \bmod p\).
  4. You have \(g^l \equiv a \bmod p \Rightarrow g^{im+j} \equiv a \bmod p \Rightarrow g^j \equiv ag^{-im} \bmod p\).
  5. Compute \(g^{-m} \bmod p\).
  6. (Giant-step) Compute \(a(g^{-m})^i\) for \(i=0,1,2,3\dots\).
  7. Match the results from the Giant-step with those from the Baby-step to find the solution.

Once you understand the Baby-step Giant-step algorithm, breaking Diffie–Hellman is straightforward. Since \(p\), \(g\), \(X\), and \(Y\) are all public, you can use this method to solve for \(x\) in \(X = g^{x} \bmod p\) and \(y\) in \(Y = g^{y} \bmod p\). With \(g^{xy}\), you can derive the secret key.

Man-in-the-middle Attack (MITM)

In an open network, if authentication is not enforced, it's easy for an attacker to intercept communication between Alice and Bob using a Man-in-the-middle attack (MITM).

RSA

The development of Diffie–Hellman paved the way for more cryptographic breakthroughs. In 1977, Rivest, Shamir, and Adleman introduced RSA encryption, one of the most widely used algorithms today. Interestingly, in 1997, the British GCHQ revealed that their researchers had discovered a similar algorithm as early as 1973.

Steps

Here's how RSA works:

  1. Choose two large primes \(p \neq q\).

  2. Compute \(n = pq\) and \(\varphi(n)=(p-1)(q-1)\).

  3. Choose \(e\) such that \(\gcd(e,\varphi(n))=1\).

  4. Choose \(d\) such that \(de \equiv 1 ; (\bmod \varphi(n))\).

  5. The public key is \((e,n)\).

  6. To encrypt a message \(M\) (less than \(n\)), compute \(M^{e} (\bmod n)\).

  7. To decrypt, compute \((M^{e})^{d} \equiv M (\bmod n)\).

Principle

The principle lies in the final step:

\((M^{e})^{d} \equiv M (\bmod n)\).

The difficulty of breaking RSA is based on the challenge of solving the integer factorization problem.

Attacks

As mentioned earlier, breaking RSA depends on efficiently solving the integer factorization problem. Discussing this in detail would require more space, so I'll leave it for a future post (to be continued…).

Conclusion

Cryptography research is a challenging field, and information security often intersects with national interests, making it a frequent battleground for those fighting for human rights and freedom. Government responses vary—Diffie and Hellman faced opposition when trying to present their findings, but in some countries, simply sharing or publishing cryptographic knowledge could lead to prosecution or imprisonment. For instance, when Phil Zimmermann released PGP online, he faced a criminal investigation because exporting the code was deemed a violation of U.S. export controls. The source code was classified as military equipment, prohibiting its export. Zimmermann cleverly published the code as a book, using the First Amendment to protect himself. Although restrictions in Europe and the U.S. have eased, some laws still pose significant risks.

Cryptography can be a double-edged sword. While it allows individuals to protect their privacy, it can also be used by bad actors to hide illicit activities. Should we sacrifice our freedom for security? It's a question each person must answer for themselves. Personally, I believe we should defend our freedoms, as they are fundamental human rights. As expressed in France's Declaration of the Rights of Man and of the Citizen:

La liberté consiste à pouvoir faire tout ce qui ne nuit pas à autrui
—— Déclaration des Droits de l'Homme et du Citoyen de 1789

"Liberty consists in the freedom to do everything which injures no one else."

In summary, cryptography is a rich and evolving field. This article only scratches the surface, aiming to give readers a general idea of what cryptography is about and spark further interest. It's clear that no encryption method is foolproof—advances in technology will always lead to better decryption methods. For example, as quantum computing develops, widely used algorithms like Diffie–Hellman, RSA, and elliptic curve cryptography may become vulnerable. Cryptography is an ongoing battle between offense and defense, which is part of what makes it so fascinating.

Finally, I'd like to say that some parts of this article reflect my personal understanding. If you spot any errors, please feel free to correct me (,,・ω・,,)