A Revolutionary Algorithm
Earth-Shattering
A cryptographic algorithm that can only be cracked by computational power
1
The History of Cryptography
5th Century BC, the ancient Greeks used a stick called scytale to transmit encrypted messages. To encrypt, a strip of paper was wrapped around the stick, and the message was written horizontally along the stick. After writing a character, the stick was rotated until completed. Once unwrapped, the text on the paper was jumbled, forming ciphertext. By wrapping it around another stick of the same size, the original message could be read. If the thickness of the stick was unknown, the content could not be decrypted.
The scytale stick used by the ancient Greeks for encryption
1st Century BC, Julius Caesar invented the Caesar cipher to ensure that communications with distant generals were not intercepted by enemy spies. Each letter was replaced by the letter three positions down the alphabet, for example, “a” became “d,” “b” became “e,” and so on.
Early 20th Century, Germany invented the Enigma machine, which could automatically encrypt plaintext, with possibilities reaching 1016. It was at the forefront of the world and was widely used by the German army during World War II. The Allies struggled for a long time. Later, the Poles were the first to crack the German codes and invented the Bomba decryption machine, which could decode messages within two hours. Just before the occupation, the Poles handed the Bomba to the British and continued development at Bletchley Park.
“A fallen knight hands his sword to his comrade at the last moment.”
Here, through the efforts of many scientists, the world’s first electronic computer, Colossus, was designed, cracking a large number of German ciphertexts and providing crucial intelligence to turn the tide. If the codes had not been cracked, the Allies might have lost, and history could have been rewritten.
The core component of the Enigma machine: control wheels
There are many touching stories about the history of cryptography, but in fact, cryptography has developed slowly. Before 1976, all encryption methods followed the same pattern:
(1) Party A chooses an encryption rule to encrypt information;
(2) Party B uses the same rule to decrypt the information.
Since both encryption and decryption use the same rule (known as a ‘key’), this pattern is called symmetric encryption algorithm.
This pattern has a major weakness: Party A must tell Party B the key; otherwise, decryption is impossible. Storing and transmitting the key becomes the most troublesome issue.
2
A Revolutionary Encryption Algorithm
RSA Algorithm Steps into the Historical Stage
In 1976, two American computer scientists, Whitfield Diffie and Martin Hellman, first proved that decryption could be completed without directly transmitting the key. This is known as the Diffie-Hellman key exchange algorithm.
The emergence of the DH algorithm is of epoch-making significance: from this moment, it inspired people that encryption and decryption could use different rules, as long as there was some correspondence between the rules.
This new pattern is also known as the asymmetric encryption algorithm:
(1) Party B generates two keys, public key and private key. The public key is open and can be obtained by anyone, while the private key is kept secret.
(2) Party A obtains Party B’s public key and uses it to encrypt information.
(3) Party B receives the encrypted information and uses the private key to decrypt it.
Information encrypted with the public key can only be decrypted with the private key; as long as the private key is not leaked, communication is secure.
Just one year after the invention of the DH algorithm, in 1977, Ron Rivest, Adi Shamir, and Leonard Adleman proposed the RSA algorithm at MIT, with RSA being formed from the initials of their surnames.
The newly born RSA algorithm has more powerful features than the DH algorithm, as it can be used for both information encryption and digital signatures. Additionally, the longer the RSA key, the exponentially harder it becomes to crack.
Due to its powerful performance, it is not an exaggeration to say that wherever there is a computer network, there is the RSA algorithm.
The three inventors of the RSA algorithm
3
Multiplying Two Large Prime Numbers
This is how the RSA algorithm works
The RSA algorithm is famous; how does it actually work?
First, randomly select two distinct prime numbers p and q.
Second, calculate the product n of p and q. The length of n is the key length, generally represented in binary, typically 2048 bits. The longer the bit length, the harder it is to crack.
Third, calculate Euler’s totient function φ(n) for n.
Fourth, randomly choose an integer e, where 1< e < φ(n), and e is coprime to φ(n).
Fifth, calculate the modular multiplicative inverse d of e modulo φ(n). The so-called “modular inverse” means that there exists an integer d such that ed leaves a remainder of 1 when divided by φ(n).
Sixth, encapsulate n and e as the public key (n,e), and n and d as the private key (n,d).
Assuming user A wants to send encrypted information m to user B, he will use the public key (n,e) to encrypt m. The encryption process is actually calculating an expression:
After user B receives the information c, he uses the private key (n,d) to decrypt it. The decryption process is also calculating an expression:
Thus, user B knows that the information sent by user A is m.
As long as user B keeps the number d private, others will not be able to derive the encrypted information m from the transmitted information c.
Using (n,e) as the public key, is it possible to deduce d given n and e?
(1) ed≡1 (mod φ(n)). Only knowing e and φ(n) can d be calculated.
(2) φ(n)=(p-1)(q-1). Only knowing p and q can φ(n) be calculated.
(3) n=pq. Only by factoring n can p and q be determined.
Therefore, if n can be factored easily, it is easy to calculate d, which means the information can be cracked.
However, factoring large integers is currently a very difficult task. At present, aside from brute force, no other effective methods have been discovered. This means that as long as the key length is sufficiently long, information encrypted with RSA is practically unbreakable.
4
RSA Algorithm Gradually Applied to
Various Aspects of Humanity
Due to the reliability of the RSA algorithm, it is now widely applied in many areas.
The most important application is ensuring the security of information transmitted over the internet. By using the RSA algorithm, even if intercepted during transmission, it is difficult to decrypt, ensuring the safety of information transmission. Only those with the private key can interpret the information.
The U-shield for bank transactions is the only proof of user identity. When first used, it employed the RSA algorithm to generate a private key stored within the U-shield. In subsequent uses, the private key decrypts transaction information to execute further transaction operations, protecting the user’s interests.
Today, with the prevalence of counterfeit products, businesses need to employ anti-counterfeiting measures. The most common method currently is QR code anti-counterfeiting, allowing consumers to verify products with a simple scan. However, if the QR code is displayed in plaintext, it can be easily exploited by criminals. Currently, some have used the RSA algorithm to encrypt the plaintext of QR codes to protect consumer interests.
Google Security Key
5
Computational Power Is Set to Increase Dramatically
Existing Algorithms May Be Vulnerable
The RSA algorithm is one of the best encryption algorithms of this era, with its security based on a mathematical fact:Multiplying two large prime numbers is very easy, but factoring their product is very difficult. Therefore, their product can be made public as the encryption key.
“Talents emerge in every generation, each leading the way for hundreds of years.” Every era inevitably has its own excellent algorithms, and RSA is a standout of our time. However, with the advent of quantum computers, computational power is set to increase dramatically, making computational power potentially not a scarce resource in the future.
And computational power is the only key to cracking the RSA algorithm. At that time, what algorithms will be able to ensure our information security?
This article is part of NetEase News · NetEase’s “Different Attitudes” special content
Some materials sourced from the internet
For reprints, please reply “reprint” in the public account
—–This is the gathering place for mathematical thinking——“Super Mathematical Modeling” (WeChat ID supermodeling), learn a little knowledge every day, easily understand various thinking, and be a fun rationalist. 500,000 math elites are following!
