RSA
Ronald L. Rivest, MIT
Adi Shamir, Weizmann
Len Adleman, USC
NEC C&C Award Lecture
November 25, 2009

Outline
Context and History
 Invention of RSA
 ImpactContext and History
“If I have seen a little
further, it is by standingon the shoulders of giants.”(Isaac Newton, 1676)

RSA

Giant #1: Gauss
Carl Frederich Gauss (1777-1855)


Father of modern
number theory

Disquisitiones
Arithmeticae (1801)

Giant #2: Claude Shannon

Giant(s) #3: H,S,B,C,K

Algorithms and Complexity Theory
 Cryptography needs:easy problems (such as multiplication or

prime-finding, for the “good guys”) and hard problems (such as factorization, todefeat an adversary).

Invention of Public-Key Crypto
Diffie and Hellman published “NewDirections in Cryptography” Nov ’76:
“We stand today at the brink of arevolution in cryptography.” Proposed “Public-Key Cryptosystem” .
(This remarkable idea developed
jointly with Merkle.)
 Introduced even more
remarkable notion of

digital signatures.

The challenge

Diffie and Hellman left open the problemof realizing a PKC: finding E and D s.t.
D(E(M)) = E(D(M)) = M

where E is public, D is private.
 At times, we thought it impossible…
 Since then, we have learned“Meta-theorem of Cryptography”:
Any apparently contradictory setof requirements can be met using
right mathematical approach…

S, R, and A in ‘78

Invention of RSA
Tried and discarded many approaches,including some “knapsack-based” ones.
(Len was great at killing off bad ideas.) “Group of unknown size” seemed usefulidea… as did “permutation polynomials”…
 After a “seder” at a student’s…
 “RSA” uses n = pq
product of primes:C = M e (mod n)
M = C d (mod n)[public key (e,n)][private key (d,n)]TM-82 4/77; CACM 2/78

(4000 mailed)Security of RSA
Security of RSA depends on difficulty offactoring n (i.e., finding p and q ) Difficulty appears to grow quickly as
length of n increases…
 But how fast does difficulty grow?
$100 RSA SciAm ChallengeMartin Gardner publishes Scientific Americancolumn about RSA in August ’77, including our$100 challenge (129 digit n) and our infamous “40quadrillion years” estimate required to factor
RSA-129:
114,381,625,757,888,867,669,235,779,976,146,61
2,010,218,296,721,242,362,562,561,842,935,706,
935,245,733,897,830,597,123,563,958,705,058,989,075,147,599,290,026,879,543,541(129 digits)
or to decode encrypted message.

$100 RSA Challenge Met ‘94
RSA-129 was factored in 1994, using
thousands of computers on Internet.

“The magic words are squeamish ossifrage.”

Cheapest purchase of computing timeever!
 Gives credibility to difficulty offactoring, and helps establish key
sizes needed for security.
Number Theory benefits
Hardy: ``Nothing I have ever done isof the slightest practical use.” Research in number theory andfactoring has grown, due to its
relevance to cryptography and its
practical implications!
Factoring milestones’84: 69 digits
 ’91: 100 digits
 ’94: 129 digits
 ’99: 155 digits ‘05: 200 digits(Sandia; Time magazine)(Quadratic sieve)($100 challenge number)(Number field sieve)(Number field sieve)

Factoring milestones’84: 69 digits
 ’91: 100 digits
 ’94: 129 digits
 ’99: 155 digits ‘05: 200 digits(Sandia; Time magazine)(Quadratic sieve)($100 challenge number)(Number field sieve)(Number field sieve)’01: 15 = 3 * 5(IBM quantum computer!)Cryptography blossoms


RSA becomes model for new cryptographic
proposals:
meet new requirements by utilizing mathematical structures connected to hard computational problems.


Field of cryptography has grown fast,with its own professional society(IACR) and dozens of conferences
every year.

Business impactFounding of RSA Security (1983)
and of spin-off Verisign (1995)
Invention of the World Wide Web(1992) and then integrationof RSA cryptography intobrowsers helps fuel growthof e-commerce.

From Len Adleman“It is one of life's great pleasures towatch the world being transformedby the technological marvels born outof the last half century of advancesin computation and communications.
It is a more personal pleasure to haveplanted a small seedling andwitnessed its struggles and growthduring this period of transformation.

From Len Adleman (cont.)“If, in addition, someone else notices
and appreciates the fruits of yourlabor, it is immensely satisfying.
 “I thank the NEC C&C Foundation,
its President Hajime Sasaki,
Executive Director Hiroshi Gokan,
and other distinguished members forthis award.”Thank you !

(The End)