RSA is a type of asymmetric cryptographic system that allows people to encrypt a message. Moreover, it permits the receiver of said message to decrypt it.
As this is a complex topic, this article will serve as an introduction to the RSA cryptosystem. Specifically, what it stands for, how its computation works, and various facts and speculations surrounding it.
What does RSA mean?
RSA is an acronym for ‘Rivest-Shamir-Adleman.’ It gets its title from the surnames of its initial creators. Essentially, RSA is an asymmetric system in which there’s a generation of a key pair: a public key and a private key. Obviously, you keep your private key close to you, but you can pass around your public key.
The algorithm’s publication dates back to 1977 and was created by Ron Rivest, Adi Shamir, and Leonard Adleman. It is one of the first public-key cryptosystems and is a common tool for secure data transmissions. In this particular system, the encryption key is public and it’s a separate structure from the decryption key. Conversely, that key remains private.
Factorization
The asymmetry draws from the practical difficulty of the ‘factorization’ of the product of two large prime numbers. This is the “factoring problem.” In mathematics, factorization (or ‘factoring’) pertains to writing a number or any mathematical object as a product of various factors. These are typically smaller or simpler objects of a very similar kind.
While factorization isn’t meaningful within systems possessing division, it’s possible to obtain a meaningful one for a rational number/function. To do this, you write it in lowest terms and separately factor both its numerator and denominator.
Prime numbers and the problem
An RSA user constructs a public key before inevitably publishing it, deriving from two large prime numbers. Moreover, an auxiliary value accompanies it and the prime numbers must remain a secret. Pretty much anyone can utilize the public key in order to encrypt a message, but only with current methods. If the public key is large enough, an individual with knowledge of the prime numbers is the only one who can decode the message.
By breaking RSA encryption, it incites the ‘RSA problem’. The question as to whether it’s about as difficult as the factoring problem is up in the air. This particular problem basically summarizes the task of carrying out an RSA private-key operation with only the public key.
The RSA algorithm is relatively slow. It’s because of this that it is less common to find it aiding the direct encryption of user data. More often than not, it passes encrypted shared keys for symmetric key cryptography. Consequently, it can perform bulk encryption-decryption operations at a considerably higher speed.
Facts & Speculation
There are two elementary facts and one speculation when it comes to prime generation and integer factorization. All three pave the way for the RSA public-key cryptosystem nowadays.
- Fact: Prime generation is a simple task
It’s pretty easy to find a random prime number of any given size. This fact is the result of two other important points. One is that prime numbers of any size are quite commonplace. The other is that it is easy to test if a number is prime; even a large prime.
In order to produce a random prime, one can generate random numbers of any size. Then, you test them for any trace of primality until you find a prime. The Price Number Theorem states that the expected number of candidates will be on the order of In x. This is basically the natural logarithm of x, and in this case, the x is the typical number of the size.
- Fact: Multiplication is very easy
With p and q, it is quite easy to find their product, n = pq. There are several ways to efficiently multiply two large numbers. This starts with the method of multiplying one number by another digit-by-digit, then summing the tableau of in-between results.
- Speculation: Factoring is a tricky task
With such an n, it appears to be difficult to recover the prime factors p and q. We have been researching and studying the problem for years. Yet, despite these efforts, finding the factors of a large number still takes a very long time to complete.
Computer scientist, Dr. Burt Kaliski, furthering explains this point in his essay:
“The fastest current methods are much faster than the simple approach of trying all possible factors one at a time. (Such a method would take on the order of n steps.) However, they are still expensive. For instance, it has been estimated recently that recovering the prime factors of a 1024-bit number would take a year on a machine costing US $10 million. A 2048-bit number would require several billion times more work.”
These estimations are a lot less than the predictions in the 1970s when the problem was initially proposed in cryptography. The sizes that many recommend have accordingly experienced an increase over the years. This is primarily due to the discovery of faster methods of factoring, as well as gradual advances in computing power.
It’s a mystery as to whether faster methods may come to light in the future. Regardless, no one has discredited the possibility that there can’t be. Both components continue to be crucial areas in the field of mathematics.
The system
The public key in this system possesses the value of n (which is the Modulus) and the value of e (the Public Exponent). The private key consists of both Modulus n and the value of d (the Private Exponent). The generation of an RSA public-key/private key pair is done by the following steps:
- Generate a pair of large, random primes: p and q.
- Calculate the Modulus n as n = pq.
- Pick an odd Public Exponent e between 3 and n-1 that is somewhat prime to p-1 and q-1.
- Calculate the Private Exponent d from e, p, and q.
- Output (n,e) as the public key and (n,d) as the private key.
The encryption operation in RSA is exponentiation to the eth power modulo n. The following formula illustrates this:
c = Encrypt (m) = m^e mod n
The input m refers to the Message and the output c is the resulting Ciphertext. The Message m is usually some kind of key of the appropriate format that one will share. The actual message is encrypted with the key by way of using traditional encryption algorithm. This makes encrypting a message of any length with just one exponentiation possible.
The decryption operation in RSA is exponentiation to the dth power modulo n. The following formula illustrates this:
m = Decrypt (c) = m^d mod n
The relationship between e and d guarantees that encryption and decryption are inverses. This is so that the decryption operation reclaims the original Message m. Without the private key (n,d) or the equivalence of p and q, it’s tricky to recover m from c. Therefore, n and e can be public without compromising the security, which is the most basic requirement for a public-key cryptosystem.
Conclusion
Once again, there’s so much intricacy to the RSA cryptosystem. This article only scratched the surface of what this system encompasses, so doing additional research will open you up to more insightful elements pertaining to it.
If you want to learn more about how the cryptosystem works and how to earn from it, I'd recommend a book called 'The Crypto Millionaire Bible: [5 in 1] How to Easily Make Life-Changing Money in The Next Big 2024-2025 Bull Run with Smart Investing and Trading Any Cryptocurrency (Altcoins, Meme, NFT, Airdrops)' which is available on Amazon here - https://amzn.to/40uN2jg
