Which of the following asymmetric encryption algorithms is based on the difficulty of factoring LARGE
numbers?
A.
El Gamal
B.
Elliptic Curve Cryptosystems (ECCs)
C.
RSA
D.
International Data Encryption Algorithm (IDEA)
Explanation:
RSA is derived from the last names of its inventors, Rivest, Shamir, and Addleman.
This algorithm is based on the difficulty of factoring a number, N, which is the product of two large prime
numbers. These numbers may be 200 digits each. Thus, the difficulty in obtaining the private key from the
public key is a hard, one-way function that is equivalent to the difficulty of finding the prime factors of N.
In RSA, public and private keys are generated as follows:
Choose two large prime numbers, p and q, of equal length, compute p3q 5 n, which is the public modulus.
Choose a random public key, e, so that e and (p – 1)(q – 1) are relatively prime.Compute e x d = 1 mod (p – 1)(q – 1), where d is the private key.
Thus, d = e–1 mod [(p – 1)(q – 1)]
From these calculations, (d, n) is the private key and (e, n) is the public key.
Incorrect Answers:
A: El Gamal is based not on the difficulty of factoring large numbers but on calculating discrete logarithms in a
finite field.
B: Elliptic Curve Cryptosystems (ECCs) are not based on the difficulty of factoring large numbers.
D: International Data Encryption Algorithm (IDEA) is not based on the difficulty of factoring large numbers.Krutz, Ronald L. and Russel Dean Vines, The CISSP Prep Guide: Mastering the Ten Domains of Computer
Security, John Wiley & Sons, New York, 2001, p. 148