Which of the following encryption algorithms does not deal with discrete logarithms?

The RSA (Rivest-Shamir-Adleman) algorithm's security is founded on the computational difficulty of the integer factorization problem—specifically, factoring the product of two large prime numbers. This mathematical foundation is distinct from the discrete logarithm problem (DLP). In contrast, El Gamal, Diffie-Hellman, and Elliptic Curve Cryptography (ECC) are all based on the intractability of solving the DLP or its variants within a specific mathematical group. RSA's operations involve modular exponentiation with a composite modulus, whereas DLP-based systems use a prime modulus or an elliptic curve group structure.

A. El Gamal: The security of the El Gamal encryption system is directly based on the difficulty of computing discrete logarithms in a finite field.

B. Diffie-Hellman: This key exchange protocol's security relies entirely on the computational difficulty of the discrete logarithm problem over a finite field.

D. Elliptic Curve: The security of Elliptic Curve Cryptography (ECC) is based on the Elliptic Curve Discrete Logarithm Problem (ECDLP), a variant of the standard DLP.

1. Katz

J.

& Lindell

Y. (2014). Introduction to Modern Cryptography (2nd ed.). CRC Press.

Chapter 11

Section 11.2

"The RSA Cryptosystem

" describes its security as relying on the hardness of factoring.

Chapter 10

Section 10.3

"The Diffie-Hellman Key-Exchange Protocol

" and Section 11.3

"The El Gamal Cryptosystem

" explicitly state their reliance on the discrete logarithm problem.

2. Boneh

D. (n.d.). CS255: Introduction to Cryptography

Lecture 9. Stanford University.

Slide 4 differentiates the two main families of public-key systems: "Integer factorization (e.g. RSA)" and "Discrete log problem (e.g. Diffie-Hellman

ElGamal

DSA

ECC)."

3. National Institute of Standards and Technology (NIST). (2013). FIPS PUB 186-4: Digital Signature Standard (DSS).

Section 5

"RSA Digital Signature Algorithm

" specifies the algorithm based on a modulus n=pq

where factoring n is difficult.

Section 6

"Elliptic Curve Digital Signature Algorithm (ECDSA)

" describes the algorithm's basis in the Elliptic Curve Discrete Logarithm Problem (ECDLP).

4. Rivest

R. L.

Shamir

A.

& Adleman

L. (1978). A Method for Obtaining Digital Signatures and Public-Key Cryptosystems. Communications of the ACM

21(2)

120–126. https://doi.org/10.1145/359340.359342

The seminal paper on RSA

which states on page 121

"The security of our method rests in part on the difficulty of factoring large numbers."