An encryption algorithm that can only be cracked by computing power
1
The History of Human Encryption
In the 5th century BC, the ancient Greeks used a stick called scytale to transmit encrypted messages. To encrypt, one would wrap a strip of paper around the stick and write the message horizontally along the stick, rotating it slightly after each letter until finished. When unwrapped, the text on the paper appears jumbled, which is the ciphertext. Wrapping it around another stick of the same size reveals the original message. If one does not know the thickness of the stick, the content cannot be decrypted.
The scytale used by the ancient Greeks for encryption
In the 1st century BC, Julius Caesar invented the Caesar cipher to ensure that communications with distant generals were not intercepted by enemy spies. Each letter corresponds to the letter three positions ahead, for example, “a” corresponds to “d,” “b” corresponds to “e,” and so on.
In the early 20th century, Germany invented a rotating encryption machine called Enigma, which could automatically encrypt plaintext, producing as many as 1016 possible configurations, making it a world leader at the time, widely used by the German military during World War II. The Allies struggled for a long time. Later, the Poles were the first to decipher the German codes and invented a code-breaking machine called Bomba, which could crack codes in 2 hours. Before being occupied, the Poles handed Bomba over to the British and continued research 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 codes and providing vital intelligence to turn the tide. If the codes had not been successfully deciphered, the Allies might have lost, and history could have been rewritten.
The core component of the Enigma machine: the control wheel
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 the information;
(2) Party B uses the same rule to decrypt the information.
Since both encryption and decryption use the same rule (abbreviated as “key”), this pattern is known as the symmetric encryption algorithm.
This pattern has one major weakness: Party A must tell Party B the key; otherwise, decryption is impossible. Thus, storing and transmitting the key becomes the most troublesome issue.
2
Revolutionary Encryption Algorithms
RSA Algorithm Steps into History
In 1976, two American computer scientists, Whitfield Diffie and Martin Hellman, first proved that decryption can be completed without directly transmitting the key. This is known as the Diffie-Hellman key exchange algorithm.
The emergence of the DH algorithm is revolutionary: from this moment on, it was revealed that encryption and decryption can use different rules, as long as there is 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 public, anyone can obtain it, while the private key is confidential.
(2) Party A obtains Party B’s public key and uses it to encrypt the information.
(3) Party B receives the encrypted information and uses the private key to decrypt it.
The information encrypted with the public key can only be decrypted with the private key, as long as the private key is not leaked, the 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 together at MIT; RSA is formed by the initials of their last names.
The newly born RSA algorithm has more powerful features than the DH algorithm because the DH algorithm is only used for key distribution, while the RSA algorithm can encrypt information and also be used for digital signatures. Additionally, the longer the RSA algorithm’s key, the exponentially harder it becomes to crack.
Due to its powerful performance, it can be said without exaggeration 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
How the RSA Algorithm Works
The RSA algorithm is famous, but how does it actually work?
First, randomly choose two unequal prime numbers p and q.
Second, calculate the product n of p and q. The length of n is the key length, typically represented in binary, generally 2048 bits long. The longer the bit length, the harder it is to crack.
Third, calculate the Euler function φ(n) of n.
Fourth, randomly choose an integer e such that 1< e < φ(n) and e is coprime with φ(n).
Fifth, calculate the modular inverse d of e with respect to φ(n). The so-called “modular inverse” means there is an integer d such that ed leaves a remainder of 1 when divided by φ(n).
Sixth, package 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, they will encrypt m using the public key (n,e). The encryption process is actually calculating an expression:
After user B receives the information c, they will decrypt it using the private key (n, d). The decryption process is also calculating an expression:
Thus, user B knows that the information sent by user A is m.
User B must keep the number d confidential; otherwise, others will be able to derive the encrypted information m from the transmitted information c.
With (n, e) as the public key, is it possible to derive d if n and e are known?
(1) ed≡1 (mod φ(n)). Only knowing e and φ(n) allows the calculation of d.
(2) φ(n)=(p-1)(q-1). Only knowing p and q allows the calculation of φ(n).
(3) n=pq. Only by factoring n can one find p and q.
Thus, if n can be easily factored, it becomes easy to calculate d, which means the information is compromised.
However, factoring large integers is currently a very difficult task. At present, no effective method has been found other than brute force. 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, this technology is now applied in many areas.
The most important application is the assurance of information transmission over the Internet. Using the RSA algorithm, even if intercepted during transmission, it is difficult to decrypt, ensuring the security of information transmission. Only those who possess the private key can interpret the information.
The U-shield for bank transactions is the unique 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 is used to decrypt transaction information to execute further transaction operations, protecting the user’s interests.
With the prevalence of counterfeit products, companies need to use anti-counterfeiting measures. Currently, the most common method is QR code anti-counterfeiting, allowing consumers to verify products easily through a simple scan. However, if QR codes are displayed in plaintext, they can be 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
Computing Power Set to Increase Dramatically
Current Algorithms May Not Withstand
The RSA algorithm is one of the best encryption algorithms of this era, its security is based on a mathematical fact:Multiplying two large prime numbers is very easy, but factoring their product is very difficult. Thus, their product can be made public as the encryption key.
“Talent emerges 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, computing power is set to increase dramatically, and computing power may not be a scarce resource in the future.
And computing power is the only key to cracking the RSA algorithm. When that time comes, what algorithms will be able to ensure our information security?
This article is a featured content from NetEase News – NetEase Account “Each Has Its Attitude”
Some materials sourced from the internet
Reprinted from: Super Mathematical Modeling
