Is the encryption function in the RSA cipher an exponential function modulo n and the decryption function an exponential function with a different exponent?

by Theresa Sittel / Friday, 16 May 2025 / Published in Cybersecurity, EITC/IS/CCF Classical Cryptography Fundamentals, Introduction to public-key cryptography, The RSA cryptosystem and efficient exponentiation

The RSA cryptosystem is a foundational public-key cryptographic scheme based on number-theoretic principles, specifically relying on the mathematical hardness of factoring large composite numbers. When examining the encryption and decryption functions in RSA, it is both accurate and instructive to characterize these operations as modular exponentiations, each employing a distinct exponent.

Key Generation in RSA

The RSA algorithm begins with the generation of two large prime numbers, denoted as $p$ and $q$ , which are kept secret. Their product $n = pq$ forms the modulus for both the public and private keys. The totient (Euler’s phi function) of $n$ is computed as $\varphi(n) = (p-1)(q-1)$ . The public exponent $e$ is chosen such that $1 < e < \varphi(n)$ and $\gcd(e, \varphi(n)) = 1$ , ensuring that $e$ is invertible modulo $\varphi(n)$ . The private exponent $d$ is then computed as the modular multiplicative inverse of $e$ modulo $\varphi(n)$ , satisfying $ed \equiv 1 \pmod{\varphi(n)}$ .

– Public key: $(n, e)$
– Private key: $(n, d)$

Encryption Function

Given a plaintext message $m$ , where $0 \leq m < n$ , the encryption operation transforms $m$ into ciphertext $c$ using the recipient's public key:

$c = E(m) = m^e \bmod n$

This is unequivocally an exponential function, where the base is the message $m$ and the exponent is the public key exponent $e$ , all computed modulo $n$ . The operation is performed in the mathematical group of integers modulo $n$ , denoted as $\mathbb{Z}_n$ .

Decryption Function

To recover the original message $m$ from the ciphertext $c$ , the recipient uses the private key exponent $d$ :

$m = D(c) = c^d \bmod n$

Again, the decryption function is an exponential function modulo $n$ , this time with the ciphertext $c$ as the base and the private exponent $d$ as the exponent. The operation takes advantage of the modular arithmetic properties and the mathematical relationship between $e$ and $d$ .

Why Modular Exponentiation?

The use of modular exponentiation is no accident. The core of RSA's security and correctness is rooted in Euler’s theorem, which states that for any integer $a$ coprime to $n$ :

$a^{\varphi(n)} \equiv 1 \pmod{n}$

Since $ed \equiv 1 \pmod{\varphi(n)}$ , there exists an integer $k$ such that $ed = 1 + k\varphi(n)$ . Therefore, decryption undoes encryption, as shown below:

$D(E(m)) = (m^e)^d \bmod n = m^{ed} \bmod n = m^{1 + k\varphi(n)} \bmod n = m \cdot (m^{\varphi(n)})^k \bmod n$

Since $m^{\varphi(n)} \equiv 1 \pmod{n}$ , this simplifies to $m$ .

Didactic Example

Let us consider a concrete example using small primes for clarity (note: in practice, primes must be hundreds of digits for security):

1. Choose primes: $p = 61$ , $q = 53$ .
2. Compute $n = pq = 3233$ .
3. Compute $\varphi(n) = (p-1)(q-1) = 60 \times 52 = 3120$ .
4. Choose $e = 17$ (commonly used, coprime to 3120).
5. Compute $d$ such that $ed \equiv 1 \pmod{3120}$ . Here, $d = 2753$ .

Suppose Alice wishes to encrypt $m = 65$ for Bob:

– Encryption:

$c = 65^{17} \bmod 3233 = 2790$

– Decryption:

$m = 2790^{2753} \bmod 3233 = 65$

Both operations are modular exponentiations; encryption uses exponent 17, decryption uses exponent 2753, both modulo 3233.

Efficient Exponentiation

In practical implementations, computing $m^e \bmod n$ or $c^d \bmod n$ directly by performing exponentiation then reducing modulo $n$ would be computationally infeasible for large exponents. Instead, algorithms such as "square-and-multiply" (also known as binary exponentiation) are used. These algorithms break down the exponentiation into a sequence of squarings and multiplications, each followed by a modular reduction, which enables efficient computation even for very large exponents and moduli.

Mathematical Properties Ensuring Correctness

The correctness of RSA depends on the following properties:

– The mapping $m \mapsto m^e \bmod n$ is injective (one-to-one) on the set of valid messages, provided $m$ is coprime to $n$ .
– The inverse mapping $c \mapsto c^d \bmod n$ recovers the original message $m$ , owing to the relationship $ed \equiv 1 \pmod{\varphi(n)}$ .
– The security of RSA is predicated on the difficulty of deducing $d$ from $e$ and $n$ , or equivalently, factoring $n$ to find $p$ and $q$ , which then enables computation of $\varphi(n)$ .

Theoretical Underpinnings

The algebraic structure underlying RSA is the multiplicative group of integers modulo $n$ , denoted as $\mathbb{Z}_n^*$ . For messages that are not coprime to $n$ , certain technical adjustments are made, but in typical circumstances, messages are required or padded to ensure coprimality.

From group theory, the modular exponentiation function is a group automorphism when restricted to $\mathbb{Z}_n^*$ . This automorphism is invertible, with the inverse map given by exponentiation to the power $d$ .

Summary of the Functions

– Encryption function: Exponential function modulo $n$ with exponent $e$ : $E(m) = m^e \bmod n$ .
– Decryption function: Exponential function modulo $n$ with exponent $d$ : $D(c) = c^d \bmod n$ .

Both processes are mathematically equivalent to raising the input to a power (either $e$ or $d$ ) and reducing the result modulo $n$ .

Potential Pitfalls and Security Considerations

It is important to note that textbook RSA (as described above) is deterministic and malleable; that is, encrypting the same message twice yields identical ciphertexts, and certain algebraic manipulations on ciphertexts translate into predictable changes in the plaintext. For these reasons, practical deployments use padding schemes (such as PKCS#1 v1.5 or OAEP), which randomize the plaintext before encryption, thus greatly enhancing security.

Additionally, if improper values are chosen for $e$ or if the primes $p$ and $q$ are too small or poorly generated, the RSA system can be compromised. The exponents must be large enough to prevent certain attacks but small enough to allow efficient computation.

The encryption and decryption functions in RSA are both modular exponentiation operations, differing solely in the exponent used—public exponent $e$ for encryption, private exponent $d$ for decryption. The mathematical symmetry and invertibility of these functions are central to the operation and security of the RSA cryptosystem.

EITCA Academy

Is the encryption function in the RSA cipher an exponential function modulo n and the decryption function an exponential function with a different exponent?

Other recent questions and answers regarding The RSA cryptosystem and efficient exponentiation:

More questions and answers:

EITCA Academy is a part of the European IT Certification framework

We care about your privacy

Necessary

Functional

Preferences

External media and social features

Analytics

Marketing and conversions

EITCA Academy

LOG IN TO YOUR ACCOUNT

FORGOT YOUR PASSWORD?

CREATE AN ACCOUNT

Is the encryption function in the RSA cipher an exponential function modulo n and the decryption function an exponential function with a different exponent?

Other recent questions and answers regarding The RSA cryptosystem and efficient exponentiation:

More questions and answers:

We care about your privacy