How the RSA Algorithm Works?
History and Motivation
The RSA algorithm, named after its inventors Ron Rivest, Adi Shamir, and Leonard Adleman, was introduced in 1977. The key motivations behind the development of the RSA algorithm include:
- Secure Communication
In the late 1970s, there was a growing need for secure communication over insecure channels, particularly in the field of electronic communication and data transmission. - Key Distribution Problem
Traditional cryptographic systems at a time faced challenges related to key distribution. In symmetric-key cryptography, if two parties want to communicate securely, they need to share a secret key beforehand. This poses a logistical challenge, especially when dealing with a large number of users. RSA’s use of public and private keys eliminates the key distribution problem associated with symmetric-key systems. - Public-Key Cryptography
The RSA algorithm is one of the earliest practical implementations of public-key cryptography. Unlike traditional symmetric-key cryptography, public-key cryptography allows for the use of two keys: a public key for encryption and a private key for decryption. This eliminates the need for a secure initial exchange of secret keys between communicating parties.
The RSA algorithm provided a groundbreaking solution to the challenges of secure communication in the digital age. Its development marked a significant advancement in the field of cryptography, and RSA remains widely used today for securing various forms of digital communication and transactions.
RSA Algorithm
RSA makes extensive use of arithmetic operations using modulo-n (mod n) arithmetic. x mod n simply means the remainder of x when divided by n. For example, 17 mod 5 = 2.
In general, RSA consists of three major parts:
- Generate the public key and the private key
- Encrypt data using generated public key
- Decrypt data using generated private key
Sometimes it makes sense to add public key sharing between Alice and Bob (two fictional characters who have become the industry standard for discussions about cryptography).
Generate RSA Public and Private Keys
To generate the public and private RSA keys, Alice and Bob would perform the following steps:
- Choose two large prime numbers, P and Q. The larger the values, the more difficult it is to break algorithm, but the longer it takes to perform the encoding and decoding.
- Compute N = PQ
- Compute Z = (P — 1)(Q — 1). This is called Euler’s totient function.
- Choose an integer number E such that 2 < E < N, that has no common factors other than 1, with Z or their greatest common divisor (gcd) equals 1, gcd(E, Z) = 1. In this case, E and Z are said to be relatively prime (coprime). Note that E will be used in encryption.
- Find a number D, such that ED — 1 is exactly divisible by Z. In another way ED mod Z = 1. Note that D will be used in decryption.
- The public key that Bob or Alice makes available to the world is the pair of numbers (N, E) and the private, which must be secret, is the pair of numbers (N, D).
Encrypt Data Using Public Key
Suppose Alice wants to send Bob a message, which is represented by bit pattern integer number M (plaintext message), where M < N. The encrypted value C (ciphertext) of plaintext message M is
C = M^E mod N
Ciphertext C will be sent to Bob. Note that Alice encrypts the message using Bob’s public key: (N, E).
Decrypt Data Using Private Key
To decrypt received ciphertext C, Bob computes
M = C^D mod N
which requires use of his private key (N, D).
Digital Signature and RSA
RSA can be used for creating digital signatures, allowing the authentication of the sender and the integrity of the message to be verified. This is crucial for applications like secure online transactions, digital certificates, and electronic authentication.
The RSA Algorithm Security
The RSA algorithm is based on the mathematical difficulty of factoring large composite numbers into their prime factors. The security of RSA relies on the practical impossibility of factoring the product of two large prime numbers.
The RSA Algorithm Example
Let’s illustrate the above steps with a simple example and observe how it works. While understanding the theory is valuable, an example can enhance your retention of the concept.
- Choose two prime numbers, P and Q. For simplicity, let’s select small prime numbers P = 2 and Q = 5.
- Compute N = PQ and Z = (P — 1)(Q — 1). Therefore, N = 2 * 5 = 10.
- Compute Z = (P — 1)(Q — 1). Therefore, Z = (2–1) * (5–1) = 1 * 4 = 4
- Choose an integer number E such that 2 < E < N and gcd(E, Z) = 1. Therefore, we can select E = 3 as 2 < E < N is satisfied, and its greatest common divisor with Z is 1. Remember, E=3 will be used for encryption.
- Find a number D, such that ED — 1 is exactly divisible by Z or ED mod Z = 1. So, in this case, D=7 is a number such that ED−1 (3*7–1 = 20) is exactly divisible by Z=4 when E=3. Remember, D=7 will be used for decryption.
As a result, the following pairs are public and private keys:
- Public Key is the (N, E) pair, which is (10, 3).
- Private Key is the (N, D) pair, which is (10, 7).
Now, let’s assume that the above public and private keys belong to Bob and Alice wants to send Bob a message, which is represented by bit pattern integer number 7 (M = 7) and M< N. Therefore the encrypted value C (ciphertext) of plaintext message M is
C = M^E mod N = 7^3 mod 10 = 343 mod 10 = 3
Ciphertext C=3 will be sent to Bob. Note that Alice encrypts the message using Bob’s public key: (N, E).
Now, when Bob receives ciphertext C = 3, he needs to decrypt it to obtain the real message, and to do so, he needs his private key: (N, D). To decrypt received ciphertext C Bob computes the following operation:
M = C^D mod N = 3^7 mod 10 = 2187 mod 10 = 7
So, as a result Bob received a message which is represented by bit pattern integer number 7.