The Math Behind The RSA Encryption Algorithm
By: Doruk Alp Uzunarslan
In the age of digitalization and global communication, encryption of private data has become an absolute necessity. By converting sensitive information into unreadable code, encryption methods ensure that unauthorized individuals cannot access private data. From securing financial transactions and personal communications to protecting sensitive governmental and corporate information, encryption plays a vital role in maintaining confidentiality in the digital age. Various encryption algorithms have been devised to secure communication between computers and technological devices. Some algorithms are efficient in time while others are efficient in encrypting large amounts of data. This trade-off must be made in accordance with data specifications and the level of security. In this article, a widely used algorithm called RSA encryption will be explored in detail.
RSA Algorithm was first defined in 1977 by Ron Rivest, Adi Shamir, and Leonard Adleman, who named the algorithm after the initials of their surnames. This encryption method is widely used in various fields of communication such as email content, chat messages, and websites. The algorithm uses public and private keys to encrypt the data. These types of algorithms are labeled “asymmetric encryption,” for the reason that there are two different keys (public and private). These keys are mathematically connected but cannot be accessed to one by another. As their names suggest, the public key is accessible to anyone, whereas the private key remains confidential. The main mathematical concept this algorithm depends on is the computational cost of large prime number factorization.
The data is encrypted with the public key and only be decrypted with a private key. This ensures that the transmitted data is only read by authorized users in a network. To start, these keys should be generated. In realistic situations, the length of these keys varies from 512 bits to 2048 bits commonly, but smaller numbers are selected for the sake of calculation simplicity for now. The algorithm starts by determining two small prime numbers, for example:
𝑝 = 3 and 𝑞 = 11
Then, we shall find the number n by:
n = p・q = 3・11 = 33
Now we have to calculate the value of ϕ(n) function by:
ϕ(n) = (p - 1)(q - 1) = 2・10 = 20
After this step, we can freely choose a positive number that is smaller than ϕ(n) and relatively prime.
let e = 7;
gcd(7, 20) = 1
Now, the d variable should be selected in a way that it satisfies (d・e) mod(ϕ(n)) = 1. This can be calculated via the Extended Euclidean Algorithm:
d = 3
Now, the public key is defined as (e, n) = (7, 33), and the private key is defined as (d, n) = (3, 33). To encrypt a message, we can use our keys as shown:
let our message m = 26;
C = me mod n ⇒ 267 mod 33 = 5
C = 5
The number 5 will be sent along with the public key over the communication between devices. After the transmission, the data will then be decrypted by the following procedure:
m = Cd mod n ⇒ 53 mod 33 = 26
As is clearly shown, we can encrypt and decrypt numbers and thus data, utilizing the inefficiency of calculating prime factors. Its reliance on asymmetric encryption and the use of public and private keys promote this algorithm for protecting sensitive information from unauthorized access. While RSA is computationally challenging, its widespread use in securing websites, emails, and digital transactions highlights its effectiveness and trustworthiness. An algorithm critical to this degree in digital encryption depends on mathematical concepts like modular arithmetic and prime number factorization, which indicates the implications of mathematics in everyday life.
Sources: