RSA is a public-key cryptosystem for both encryption and authentication;
it was invented in 1977 by Ron Rivest, Adi Shamir, and Leonard Adleman,
who where working at the MIT
math labs.
It works as follows:
Here is how RSA works in real life :
RSA privacy encryption: Suppose Jad wants to send a message m
to Ziad. Jad
creates the ciphertext c by exponentiating:
c=m^e mod n, where e
and n are Ziad’s
public key. He sends c to Ziad. To
decrypt, Ziad also exponentiates: m=c^d mod n;
the
relationship between e and d
ensures that Ziad correctly recovers m. Since
only Ziad
knows d, only Ziad can decrypt the
message m.
RSA authentication: Suppose Jad wants to send a message
m to Ziad in such away
that Ziad is assured that the message is authentic and is from Jad.
Jad creates a digital signature s by exponentiating:
s=m^d mod n, where d
and n are Jad’s private key. he then
sends m and s
to Ziad. To verify the signature, Ziad exponentiates and checks that the
message m is recovered: m
= s^e mod n, where e and n
are Jad’s public key.
Thus encryption and authentication take place without any sharing
of private keys: each person uses only other people’s public keys and his
or her own private key. Anyone can send an encrypted message or verify
a signed message, using only public keys, but only someone in possession
of the correct private key can decrypt or sign a message.
-- Brute Force RSA Factoring --
An attacker has access to the public-key. In other words, the attacker
has e and n.
The
attacker wants the private key. In other words the attacker wants
d. To get d,
n needs to be factored (which will yield p
and q, which can then be used to calculate
d).
Factoring n is the best known attack against RSA to date. (Attacking RSA by trying to deduce (p-1)(q-1) is no easier than factoring n, and executing an exhaustive search for values of d is harder than factoring n.) Some of the algorithms used for factoring are as follows:
- Trial division: The oldest and least
efficient. Exponential running time. Try all the
prime numbers less than sqrt(n).
- Quadratic Sieve (QS): The fastest algorithm for numbers smaller than 110 digits.
- Multiple Polynomial Quadratic Sieve (MPQS): Faster version of QS.
- Double Large Prime Variation of the MPQS: Faster still.
- Number Field Sieve (NFS): Currently
the fastest algorithm known for numbers larger
than 110 digits. Was
used to factor the ninth Fermat number.
These algorithms represent the state of the art in warfare against
large composite numbers
(therefore against RSA). The best algorithms have a super-polynomial
(sub-exponential)
running time, with the NFS having an asymptotic time estimate closest
to polynomial behavior.
Still, factoring large numbers is hard. However, with the advances
in number theory and
computing power, it is getting easier. In 1977 Ron Rivest said that
factoring a 125-digit
number would take 40 quadrillion years. In 1994 RSA129 was factored
using about 5000
MIPS-years of effort from idle CPU cycles on computers across the
Internet for eight
months. In 1995 the Blacknet key (116 digits) was factored using
about 400 MIPS-years of effort (1 MIPS-year is a 1,000,000
instruction per second computer running for one year) from several
dozen workstations and a MasPar for about three months. Given current trends
the keysize that can be factored will only increase as time goes on. The
table below estimates the effort required to factor some common PGP-based
RSA public-key modulus lengths using the General Number Field Sieve:
KeySize MIPS-years required
to factor
-----------------------------------------------------------------
512
30,000
768
200,000,000
1024
300,000,000,000
2048
300,000,000,000,000,000,000
-- Chosen cipher-text attack --
An attacker listens in on the insecure channel in which RSA messages
are passed. The
attacker collects an encrypted message c,
from the target (destined for some other party). The attacker wants to
be able to read this message without having to mount a serious factoring
effort. In other words, she wants m=c^d.
To recover m, the attacker first chooses
a random number, r < n. (The attacker has
the
public-key [e,n].) The attacker computes:
x=r^e mod n (She encrypts r with the target's public-key)
y=xc mod n (Multiplies the target ciphertext with the temp)
t=r^-1 mod n (Multiplicative inverse of r mod n)
The attacker counts on the fact that:
If x=r^e mod n, Then r=x^d mod n
The attacker then gets the target to sign y
with her private-key,(which actually decrypts y)
and sends u=y^d mod n to the attacker.
The attacker simply computes:
tu mod n = (r^-1)(y^d) mod n = (r^-1)(x^d)(c^d) mod n = (c^d) mod n = m
To foil this attack do not sign some random document presented to you. Sign a one-way hash of the message instead.
-- Timing attack against RSA --
A very new area of attack publicly discovered by Paul Kocher deals with the fact that different cryptographic operations (in this case the modular exponentiation operations in RSA) take discretely different amounts of time to process. If the RSA computations are done without the Chinese Remainder theorem, the following applies:
An attacker can exploit slight timing differences in RSA computations to, in many cases, recover d. The attack is a passive one where the attacker sits on a network and observes the RSA operations. The attacker passively observes operations measuring the time it takes to compute each modular exponentiation operation: m=c^d mod n. The attacker also knows c and n.
-- Keysizes --
It is pointless to make predictions for recommended keysizes. The
breakneck speed at which technology is advancing makes it difficult and
dangerous. Respected cryptographers will not make predictions past 10 years
and I won't embarrass myself trying to make any. For today's secrets, a
1024-bit is probably safe and a 2048-bit key definitely is. I wouldn't
trust these numbers past the end of the century. However, it is worth mentioning
that RSA would not have lastest this long if it was as fallible as some
crackpots with middle initials would like you to believe.