In the first part of this series, we delved into RSA cryptography, its history, applications, and relevance in today’s world^{1}. As we learned, RSA cryptography is a powerful tool widely used to secure digital communication and information. However, its strength and effectiveness do not come from thin air. Profound mathematical principles and concepts underpin RSA cryptography.

In this second part of the series, our goal is to unravel the mathematics behind RSA cryptography. We aim to explain the fundamental mathematical principles used in RSA, including prime numbers, modular arithmetic, and Euler’s totient function. Further, we will illuminate how these principles are applied in generating RSA keys and the encryption and decryption processes.

We will also shed light on how these mathematical principles contribute to the security of RSA and why despite potential weaknesses, RSA remains a vital tool in securing digital information. We will use formulas and provide examples to illustrate these concepts to assist in understanding.

A prime number is a natural number greater than 1 that has no positive integer divisors other than 1 and itself. For example, the first six prime numbers are $2, 3, 5, 7, 11,$ and $13$^{2}. The fundamental role of prime numbers in RSA cryptography cannot be overstated. It is the difficulty in factoring large prime numbers that provides the security backbone of RSA^{3}.

Modular arithmetic, also known as “clock arithmetic”, is a system of arithmetic for integers, where numbers “wrap around” after they reach a certain value, referred to as the modulus^{4}. If we denote the modulus by $n$, the result of a modular operation can be written as:

$a \equiv b \mod n$

This means that $a$ and $b$ leave the same remainder when divided by $n$. In the context of RSA, modular arithmetic allows computations to be managed with large numbers by transforming them into equivalent, smaller numbers^{3}.

Euler’s totient function, often denoted by $\phi(n)$, is an important mathematical function used in RSA. It is used to determine the number of integers that are relatively prime to a given number, $n$ (i.e., numbers that do not share any factor with $n$ except 1)^{5}. For a prime number $p$, $\phi(p)$ is simply $p-1$.

In the context of RSA, where the modulus $n$ is the product of two prime numbers $p$ and $q$, Euler’s totient function can be calculated using the formula:

$\phi(n) = (p-1)(q-1)$

This totient function plays a pivotal role in the generation of the RSA public and private keys^{3}.

The process of generating an RSA key pair involves the following steps^{1}:

First, we need to select two distinct prime numbers, $p$ and $q$. These primes should be chosen randomly and be of similar bit-length to ensure the security of the key^{6}. The larger these prime numbers are, the more secure the RSA key will be, but it will also make the computations slower.

The modulus $n$ is calculated by multiplying the two prime numbers. The modulus is a part of both the public and private keys, and it is used in both the encryption and decryption processes.

$n = p \cdot q$

Next, Euler’s totient function, $\phi(n)$, is calculated. As mentioned earlier, for a modulus $n$ that is a product of two primes $p$ and $q$, Euler’s totient function can be computed using the formula:

$\phi(n) = (p-1) \cdot (q-1)$

The public key exponent, typically denoted by $e$, is a number that should be relatively prime to $\phi(n)$ and $1 < e < \phi(n)$. In practice, common choices for $e$ are $3$, $17$, or $65537$ (which is $2^{16}+1$)^{7}.

The private key exponent, typically denoted by $d$, is calculated such that it is the multiplicative inverse of $e$ modulo $\phi(n)$. In other words, we need to find a $d$ that satisfies the following condition:

$e \cdot d \equiv 1 \mod \phi(n)$

This means that when $e \cdot d$ is divided by $\phi(n)$, the remainder is $1$.

The Extended Euclidean Algorithm is often used to calculate $d$, and the result is kept private^{8}.

Once we have computed $n, e,$ and $d$, the public key consists of $(n, e)$, and the private key consists of $(n, d)$.

The encryption process in RSA cryptography involves taking a plaintext message, $m$, and raising it to the power of the public key exponent, $e$, then taking the modulus by $n$. This results in the ciphertext, $c$, which can be represented by the following formula^{1}:

$c = m^e \mod n$

As a result of the modulus operation, the ciphertext $c$ will be a number in the range $0$ to $n - 1$. In practical scenarios, the plaintext message is often transformed into a numerical form before applying the encryption process^{6}.

Decryption is performed by taking the ciphertext, $c$, and raising it to the power of the private key exponent, $d$, then taking the modulus by $n$. This returns us to the original plaintext message, $m$, and can be represented by the following formula^{1}:

$m = c^d \mod n$

The operations for encryption and decryption in RSA are symmetric, except for the use of different exponents. This symmetry comes from the relationship between the public and private keys, specifically, the way that $d$ is calculated to be the multiplicative inverse of $e$ modulo $\phi(n)$^{7}.

This encryption and decryption process is what makes RSA a Public Key Cryptosystem - anyone can encrypt a message using the public key, but only the holder of the private key can decrypt it. This makes RSA valuable for ensuring the confidentiality and integrity of data^{8}.

The security of RSA cryptography hinges on the assumption that factoring large composite numbers is computationally difficult. This is often referred to as the RSA assumption^{1}.

The RSA assumption postulates that, given a large composite number $n$ (the product of two large primes $p$ and $q$), it is computationally infeasible to find the prime factors $p$ and $q$ of $n$^{1}. If someone could efficiently factor $n$, they could compute $\phi(n)$ and subsequently calculate the private key $d$ from the public key $e$^{8}.

The computational complexity of factoring large composite numbers is what provides RSA’s security. At the time of writing, the most efficient classical factoring algorithm is the General Number Field Sieve (GNFS), which operates in sub-exponential time^{9}. However, even with GNFS, factoring a large composite number formed from two large prime numbers (200+ digits each) is beyond the reach of current computational resources^{6}.

While RSA cryptography is considered secure against classical computers, the advent of quantum computers could potentially pose a threat. If run on a sufficiently powerful quantum computer, Shor’s algorithm could theoretically factor large composite numbers in polynomial time, thereby breaking RSA^{10}.

The RSA algorithm has stood the test of time as a fundamental tool in public-key cryptography. By harnessing the mathematical principles of number theory, including modular arithmetic, primality, and the difficulty of factoring large composite numbers, RSA provides a secure and reliable method for encryption and decryption^{1}.

Throughout this post, we’ve delved into the mathematical underpinnings of RSA, understanding how keys are generated and how the encryption and decryption processes work. We’ve also discussed the security of RSA, underlining the importance of the RSA assumption and the computational difficulty of factoring large composite numbers^{8}.

However, we must be mindful of the evolving landscape of computation. With the rise of quantum computing, the RSA assumption could potentially be challenged by quantum algorithms such as Shor’s ^{10}. While this is still a theoretical concern as of 2021, it underscores the necessity of ongoing research and development in the field of cryptography to keep pace with such technological advancements.

In conclusion, while RSA cryptography might face challenges in the future, it remains a cornerstone of secure data transmission, demonstrating the profound impact of mathematical concepts when applied to real-world issues of security and privacy^{6}.

Each of the following resources provides unique and comprehensive insights into the mathematical and practical aspects of RSA cryptography, offering a more in-depth understanding of this essential cryptographic algorithm.

- [1] J. Katz and Y. Lindell, ‘Introduction to Modern Cryptography’, 2007.
- This book provides an excellent overview of the principles of modern cryptography, including a comprehensive section on RSA and public-key cryptography.

- [2] D. Boneh and V. Shoup, ‘A Graduate Course in Applied Cryptography’, 2017.
- This is a more advanced book, which covers RSA and other cryptographic protocols in great detail.

- [3] P. W. Shor, ‘Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer’, 1997.
- This is a seminal paper that introduced Shor’s algorithm, which has implications for the security of RSA in the face of quantum computing.

- [4] R. E. Crandall and C. Pomerance, ‘Prime Numbers: A Computational Perspective’, 2005.
- This book offers a deep dive into the computational and number-theoretical aspects related to prime numbers, which are a key aspect of RSA.

- [5] C. Pomerance, ‘A Tale of Two Sieves’, in Biscuits of Number Theory, 2009.
- This is a great paper to understand the importance of factoring large numbers in RSA and how the difficulty of this task contributes to RSA’s security.

- R. L. Rivest, A. Shamir, and L. Adleman, ‘A Method for Obtaining Digital Signatures and Public-Key Cryptosystems’, 1977.↩
- K. H. Rosen, Elementary Number Theory and Its Applications. 1984.↩
- D. Boneh and V. Shoup, ‘A Graduate Course in Applied Cryptography’, 2017.↩
- T. H. Cormen, Ed., Introduction to Algorithms, 3rd ed. Cambridge, Mass: MIT Press, 2009.↩
- W. Stein, Elementary Number Theory: Primes, Congruences, and Secrets: A Computational Approach. Springer New York, 2009. doi: 10.1007/b13279.↩
- B. Schneier, Applied Cryptography: Protocols, Algorithms, and Source Code in C, 20th anniversary edition. Indianapolis, IN: Wiley, 2015.↩
- A. J. Menezes, P. C. Van Oorschot, and S. A. Vanstone, Handbook of Applied Cryptography. Boca Raton: CRC Press, 1997.↩
- D. R. Stinson and M. B. Paterson, Cryptography: Theory and Practice, Fourth edition. Boca Raton: CRC Press, Taylor & Francis Group, 2019.↩
- C. Pomerance, ‘A Tale of Two Sieves’, in Biscuits of Number Theory, A. Benjamin and E. Brown, Eds., Providence, Rhode Island: American Mathematical Society, 2009, pp. 85–104. doi: 10.1090/dol/034/15.↩
- P. W. Shor, ‘Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer’, 1997.↩

Previous Article

Introduction to RSA CryptographyNext Article

Introduction to Parallel Programming with OpenMPQuick Links