23 / 03 / 24
Cryptography has always been a crucial aspect of protecting sensitive information from being viewed by an unauthorized entity. The evolution in technology brought with it the need for still more robust and secure methods of encryption. In the 1970s, Ron Rivest, Adi Shamir, and Leonard Adleman invented the RSA algorithm, and to date, it is one of the most commonly used public-key cryptosystems. In this blog post, we delve into the mathematics behind the RSA algorithm and how it provides the backbone for secure communication in the digital age.
But before we can understand the RSA algorithm, we need to understand the concept of public-key cryptography. Unlike symmetric-key cryptography, where a single key serves for both encryption and decryption, public-key cryptography employs two separate keys:
Public key, shareable and used to encrypt data.
Private key, the secret one to decrypt data.
The beauty of public-key cryptography is such that even if an attacker intercepts the encrypted data and knows the public key, he cannot decrypt the information without the private key. This asymmetry makes public-key cryptography much more secure than symmetric-key cryptography for large-scale communication.
The RSA algorithm is based on prime numbers and modular arithmetic. A prime number is a natural number greater than 1 that has only two different positive divisors: 1 and the number itself. For example, 2, 3, 5, and 7 are prime numbers. The RSA algorithm is based on the presumed difficulty of factoring large composite numbers into their prime factors.
Modular arithmetic, often known as "clock arithmetic," is a means of finding the remainder when a number is divided by another. In RSA, modular arithmetic is carried out so that after one applies the encryption or decryption algorithm to a message, the result is always a number in a properly chosen range.
The three basic steps of the RSA algorithm are key generation, encryption, and decryption.
Choose two large prime numbers, p and q. These numbers should be chosen randomly and kept secret.
Find the modulus, n, as the product of p and q: n = p * q. This value will be a modulus for public and private keys.
Evaluate Euler's totient function φ(n) defined by: φ(n) = (p-1)*(q-1).
Choose an integer e such that 1 < e < φ(n) and e is coprime to φ(n); that is, e has no factors in common with φ(n) other than 1. The number e is the public key exponent.
Do the following computation to find a private key exponent d such that: (d * e) % φ(n) = 1, i.e., d is the multiplicative inverse of e modulo φ(n).
The public key is represented with (n, e), and the private key with (n, d).
The ciphertext C for a message M is computed by the sender using the public key of the recipient (n, e):
C = M^e % n
The recipient, who has the private key (n, d), may decrypt the ciphertext C to the original message M by executing the following arithmetic:
M = C^d % n.
The security of the RSA algorithm stems from its being computationally difficult to find the prime factorization of a large composite number. If that were easy, then given the public key (n, e), an attacker could recover the private key (n, d) and decrypt messages at will. But no efficient factoring algorithms are currently known, hence RSA is secure for practical use.
RSA is used very widely in a vast number of applications:
Secure communication: RSA is often used to exchange symmetric encryption keys securely, which are then used to encrypt and decrypt large volumes of data.
Digital signatures: RSA, on the other hand, may be used to sign a message or document with the sender's private key in order to assert the authenticity and integrity.
Secure Transactions Online: In e-commerce and online banking, RSA is important to ensure secure communications between clients and servers.