The RSA encryption algorithm is the most commonly used asymmetric encryption algorithm, proposed by Ron Rivest, Adi Shamir, and Leonard Adleman in 1977. The name RSA is derived from the initials of their last names. It is the first relatively complete public key algorithm, which can be used for both encryption and digital signatures.
This algorithm is based on the difficulty of large number factorization, where the public key and private key are functions of a pair of large prime numbers. The difficulty of recovering plaintext from a public key and ciphertext is equivalent to factoring the product of two large prime numbers, which is a well-known mathematical problem. Currently, RSA has become the most popular public key algorithm, widely used in online banking, digital signatures, and other applications.
Before introducing the RSA encryption algorithm, it is necessary to review a few mathematical concepts:
Prime Numbers
A prime number, also known as a natural number greater than 1, is an integer that cannot be formed by multiplying two smaller natural numbers. For example, 13 is a prime number because it can only be expressed as 13 * 1; whereas 15 is not a prime number because 15 = 3 * 5.
Coprime Numbers
According to elementary mathematics, two natural numbers are called coprime if their only common divisor is 1. There are various methods to determine this, such as:
Two prime numbers are always coprime, such as 2 and 7, or 13 and 19.
A prime number that does not divide another composite number means these two numbers are coprime, such as 3 and 10, or 5 and 26.
1 and any natural number are coprime, such as 1 and 9908.
Two consecutive natural numbers are coprime, such as 15 and 16.
Two consecutive odd numbers are coprime, such as 49 and 51.
Two numbers where one is a prime and the other is not a multiple of the prime are coprime, such as 7 and 16.
Modular Exponentiation
First perform the exponentiation, then take the result modulo. Modular arithmetic is integer arithmetic where an integer m is divided by n, and the remainder is taken as the result, denoted as m mod n.
For example, (5^3) mod 7 = (125 mod 7) = 6.
Introducing the Encryption Algorithm through an Example
Example: A user has the username A, and we plan to use RSA to encrypt this username. Assume we select two prime numbers p = 47 and q = 71, and the public key encryption exponent e = 3. Please calculate the private key and encrypt the username for transmission.
1. What is the private key of the RSA encryption algorithm?
(1) Select Prime Numbers
Select a pair of different, sufficiently large prime numbers p = 47 and q = 71. In practical applications, the larger these two primes, the harder they are to crack.
(2) Calculate the Modulus
Calculate n = p * q = 3337.
The length of n is the key length; 3337 in binary is 110100001001, which has 12 bits, so this key is 12 bits long. In practical applications, RSA keys are generally 1024 bits, and for important situations, 2048 bits.
(3) Calculate the Euler’s Totient Function
Using the formula, calculate the Euler’s function f(n) = (p – 1) * (q – 1) = 3220, while keeping p and q strictly confidential.
(4) Choose the Public Key Exponent
Find a number e that is coprime to the Euler’s function f(n) as the public key exponent, where 1 < e < f(n). According to the known conditions, e = 3 (this is set to a smaller value for easier calculation. In practical applications, 65537 is often chosen).
(5) Calculate the Private Key Exponent
Calculate the private key exponent d such that d satisfies (d * e) mod f(n) = 1, i.e., (d * 3) mod 3220 = 1. The private key d = 2147.
(6) Generate the Key Pair
Public Key KU = (e, n) = (3, 3337), Private Key KR = (d, n) = (2147, 3337). The sender can publish the public key while keeping the private key secure.
2. How to Encrypt and Transmit Information?
During encryption, first convert the plaintext into an integer M ranging from 0 to n – 1. We use ASCII to convert the username A into the integer M = 65.
Using the public key for encryption, the ciphertext C = M^e mod n = 65^3 mod 3337 = 991.
Using the private key for decryption, the plaintext M = C^d mod n = 991^2147 mod 3337 = 65.
The process of the RSA encryption algorithm has been fully introduced. You may find the steps quite simple, but how secure is it?
Is the RSA Encryption Algorithm Secure?
From the decryption process above, we can see that to crack the plaintext, one must know the private key, which is determined by KR = (d, n). Since the public key KU = (e, n) has already been published, with e = 3 and n = 3337 being known, one only needs to calculate d to break the private key.
According to the formula (d * e) mod f(n) = 1, e is known, and calculating d requires first calculating f(n).
Using the Euler’s function f(n) = (p – 1) * (q – 1), calculating f(n) requires knowing the values of p and q.
Using the formula n = p * q, one needs to factor the large integer n. However, in reality, n is a binary number of 1024 bits or even 2048 bits, which is too large for current computing power to factor into the large primes p and q.
Conclusion: RSA encryption is secure; you cannot crack it.
END
Efficiency Symbol
Sharing practical tips and new knowledge, focusing on improving efficiency
Disclaimer
According to the “Cybersecurity Law of the People’s Republic of China”, “Data Security Law of the People’s Republic of China”, “Personal Information Protection Law of the People’s Republic of China”, and other relevant laws and regulations, any unauthorized network attacks, data theft, system intrusion, etc., are illegal acts. The content of this article is intended for learning and sharing experiences in cybersecurity technology, aiming to enhance public awareness and protective skills in cybersecurity. The technical means, programs, tools, and other information mentioned in this article are based on a legally authorized environment and are strictly prohibited for any illegal use.