Cryptography Reference
In-Depth Information
Thus, a public-key cryptosystem was achievable if one could find func-
tions that could be efficiently computed in forward mode (using the public
key) but were computationally infeasible to invert unless one knew of a
certain trapdoor (the private key). Diffie and Hellman could not, however,
offer a practical realization of the principle. Although they examined a
number of possible solutions to the problem, including matrix inversion,
none proved sufficiently hard to invert. The honor of finding a suitable
candidate for the first trapdoor one-way function would instead befall in
1978 to three MIT computer science researchers, Ronald Rivest, Adi Shamir,
and Leonard Adleman (whose last names would provide the RSA acronym).
11
Their solution tapped into classical number theory problems, the compu-
tational differential between multiplication and prime decomposition
(factoring) of integers.
The fundamental theorem of arithmetic states that every positive integer
n
can be written as the product of prime factors, that is, numbers no further
divisible. 1, 2, 3, 5, 7, 11, 13, 17, and 19 are prime numbers; 20 is a com-
posite number that can be written as the product 2 × 2 × 5. The interest
of this lies in the fact that though there are known efficient procedures for
multiplying two numbers, no similarly efficient procedure is known to
exist for calculating the
inverse function
, that is, finding the prime decom-
position of a composite number. In computational terms, it is “easy” to
multiply any two numbers and obtain their product, but it is “difficult” to
reverse the procedure and find the prime factors of a number, unless of
course one happens to know this decomposition in advance. In the RSA
system, this decomposition is Diffie and Hellman's trapdoor: Alice gener-
ates the public key by multiplying two large prime numbers, but because
she has knowledge of the prime decomposition of the public key, she can
easily compute the inverse, yet anyone who has access to only the public
key is forced to attempt to calculate its prime decomposition. Although
such a calculation is conjectured to be “computationally infeasible,” the
absence of formal proof of the difficulty of factoring integers constitutes
one of cryptography's most famous “known unknown.”
12
Regardless of this uncertainty, the RSA paper established number theory
as the new practical foundation for the mathematics of cryptography. It
spurred a gold rush for the discovery of additional suitable problems—
discrete logarithms, quadratic residuosity, factorization of polynomials
over finite fields, and so on—on which to base public-key cryptographic
