Transcript RSA Encryption

RSA encryption
1. RSA basics
2. Key generation
3. What it would take to break RSA
1. RSA basics
•
•
•
•
Two large prime numbers (p, q): n = pq
Small number e relatively prime to (p-1)(q-1)
(e,n) is the public key
Number d (multiplicative inverse of d, modulo (p-1)(q-1))
d e = 1 ( modulo (p-1)(q-1) )
• (d,n) is the secret key
It works because (Me)d = Med = M ,
[1]
[1] Proof of RSA: http://cactus.eas.asu.edu/Partha/Teaching/Crypto.2000S/RSA-Proof.htm
1. RSA basics
M  encrypt: C = PublicKey(M) = Me (mod n)
M
Public Key
(e,n)
C
Secret key
(d,n)
M
C  decrypt: M = SecretKey(C) = Cd (mod n)
2. Key generation
• Each pair public/private key requires two large primes
(around 512 bits)
• RSA widely used  needs lots of large primes
• Primality tests:
- try all possible factors (good for small numbers)
- probable tests (may be enough)
- recently shown (2002): primality can be proven in
just polynomial time in the number of digits [2]
[2] Agrawal, M., N. Kayal, and N. Saxena. Preprint. Primes is
in P. Available at http://www.cse.iitk.ac.in/primality.pdf.
3. What it would take to break RSA
What does “breaking RSA” mean?
A:
– Factor n  find d
– C = Me (mod n)  computing e-th roots (mod n)
B:
– Guessing the message
C:
– Attacking a particular implementation
Experiment: Breaking DES using brute force
Project statistics:
Start of contest: January 29, 1997
Announcement of DESCHALL project: February 18, 1997
End of contest: June 17, 1997
Size of keyspace: 72,057,594,037,927,936
Keys searched: 17,731,502,968,143,872
Peak keys/day: 601,296,394,518,528
Peak keys/second: 7,000,000,000 (approx)
Peak clients/day: 14,000 (approx, based on IP address)
Total clients, since start: 78,000 (approx, based on IP address)
The computer that found the key: CPU: Pentium 90
RAM: 16 megabytes
Operating System: FreeBSD 2.2.1
Speed (keys/second): 250,000 (approx)
Client: FreeBSD v0.214, built March 12, 1997
Owner: iNetZ Corporation, Salt Lake City,
Utah Operator: Michael K. Sanders