Which of the following ASYMMETRIC encryption algorithms is based on the difficulty of FACTORING LARGE NUMBERS?

The RSA (Rivest-Shamir-Adleman) algorithm is a widely used asymmetric cryptosystem. Its security is fundamentally based on the computational difficulty of the integer factorization problem. The public key consists of a modulus n (the product of two large, secret prime numbers) and a public exponent e. To derive the corresponding private key, an attacker would need to determine the original prime factors of n. For sufficiently large numbers, factoring n is computationally infeasible with current technology, which ensures the security of the private key.

A. El Gamal: Its security is based on the difficulty of solving the Discrete Logarithm Problem (DLP) over a finite field.

B. Elliptic Curve Cryptosystems (ECCs): Security relies on the Elliptic Curve Discrete Logarithm Problem (ECDLP), a more complex variant of the DLP.

D. International Data Encryption Algorithm (IDEA): This is a symmetric-key block cipher and does not use the principles of asymmetric cryptography like factoring or discrete logarithms.

1. Paar

C.

& Pelzl

J. (2010). Understanding Cryptography: A Textbook for Students and Practitioners. Springer. In Chapter 6

Section 6.2

"The RSA Cryptosystem

" it is stated: "The security of RSA relies on the fact that it is difficult to factor large integers." (p. 161).

2. Katz

J.

& Lindell

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

Section 11.3

"The RSA Assumption

" directly connects the security of the RSA cryptosystem to the hardness of the factoring problem. (p. 378).

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

"RSA Key Pair Generation

" details the process where the modulus n is the product of two secret primes

p and q

establishing that the security relies on the secrecy of these factors. (DOI: https://doi.org/10.6028/NIST.FIPS.186-4).

4. Boneh

D. (1999). Twenty Years of Attacks on the RSA Cryptosystem. Notices of the American Mathematical Society

46(2)

203-213. The paper's introduction states

"The security of the RSA system is based on the assumption that factoring a large number is difficult." (p. 203).