International Journal of Scientific & Engineering Research Volume 2, Issue 9, September-2011 1
ISSN 2229-5518
Attack on RSA Cryptosystem
Sachin Upadhyay
Abstract— The RSA cryptosystem is most widely used cryptosystem it may be used to provide both secrecy and digital signatures and its secu- rity is based on the intractability of the integer factorization. The security of RSA algorithm depends on the ability of the hacker to factorize num- bers. New, faster and better methods for factoring numbers are constantly being devised. The Trent best for long numbers is the Number Field Sieve. Although the past work has proven that none of the attacks on RSA cryptosystem were dangerous. Indeed most of the dangers were be-
cause of improper use of RSA. In this paper what I am trying to do is to analyze the different types of possible attacks on RSA Cryptosystem.
Index Terms— Cryptology, Cryptography, Cryptanalysis, CRT, Decryption, Encryption, RSA.
—————————— ——————————
he RSA Cryptosystem developed in 1977, by three peoples: Ronald Rivest, Adi Shamir & Len Adleman which is based upon the difficulty of factorization of two
large primes. The cryptosystem is most commonly used for providing privacy and ensuring authencity of digital data. These days RSA is deployed in many commercial systems. It is used by web servers and browsers to secure web traffic, it is used to secure login sessions and it is at the heart of electronic credit card payment systems. So we can say that RSA is very frequently used in some or the other applications. The RSA Cryptosystem has been analysed for vulnerability by many researchers. Although the past work has proven that none of the attacks on RSA cryptosystem were dangerous. Indeed most of the dangers were because of improper use of RSA. Our goal is to survey some of these attacks and describe the underlying mathematical tools they use. Throughout the sur- vey we follow standard naming conventions and use Alice and Bob to denote two generic parties wishing to communi- cate with each other. We use Marvin to denote a malicious attacker wishing to eavesdrop or tamper with the communica- tion between Alice and Bob.
We begin by describing some old elementary attacks. These attacks illustrate blatant misuse of RSA. Although many such attacks exist, we are considering few ones
To avoid generating a different modulus N = p.q for each user one may wish to fix N once and for all. The same N is used by all users. A trusted central authority could provide user i with a unique pair ei, di from which user i forms a public key (N, ei) and a secret key (N, di).
————————————————
Department of Mathematical Sciences & Computer Applications, Bundelk- hand University, Jhansi, UP, India, PH-09452736650. E-mail: sachinupad- hyay2010@yahoo.co.in
At first glance this may seem to work: a cipher text
C = Mea mod N intended for Alice cannot be decrypted by Bob
since Bob does not possess da. However, this is incorrect and
the resulting system is insecure. Bob can use his own expo-
nents eb , db to factor the modulus N. Once N is factored Bob
can recover Alice's private key da from her public key ea. This
observation, due to Simmons, shows that an RSA modulus
should never be used by more than one entity.
Let (N, d) be Bob's private key and (N, e) be his corresponding public key. Suppose an adversary Marvin wants Bob's signa-
ture on a message M є Z*N. Being no fool, Bob refuses to sign
M. Marvin can try the following: he picks a random r є Z*N
and sets M’ = r^e M mod N. He then asks Bob to sign the
random message M’. Bob may be willing to provide his signa-
ture S’ on the innocent-looking M’. But recall that S’ = M’^d
mod N. Marvin now simply computes S = S’/r mod N and ob-
tains Bob's signature S on the original M. Indeed
S^e = (S’) ≦e / r≦e = (M’) ≦ed / r≦e ≡ M’/ r≦e = M (mod N) (1)
This technique, called blinding, enables Marvin to obtain a valid signature on a message of his choice by asking Bob to
sign a random “blinded" message. Bob has no information as
to what message he is actually signing. Since most signature
schemes apply a “one-way hash" to the message M prior to
signing, the attack is not a serious concern. Although we pre-
sented blinding as an attack, it is actually a useful property of
RSA needed for implementing anonymous digital cash.
To reduce decryption time (or signature-generation time), one may wish to use a small value of d rather than a random d. Since modular exponentiation takes time linear in log2 d, a small d can improve performance by at least a factor of 10 (for a 1024 bit modulus). Unfortunately, a clever attack due to M. Wiener shows that a small d results in a total break of the cryptosystem.
Theorem: (M.Wiener) Let N = p.q with q < p < 2q. Let d < 1/3
N1/4. Given (N, e) with e.d = 1 mod ϕ (N), Marvin can effi-
ciently recovered
IJSER © 2011
International Journal of Scientific & Engineering Research Volume 2, Issue 9, September-2011 2
ISSN 2229-5518
e
(N )
k
d
1
d (N )
C1 = M3 mod N1 C2 = M3 mod N2 C3 = M3 mod N3
We may assume that gcd (Ni, Nj) = 1 for all i ≠ j since otherwise
Using N in place of (N), we obtained:
Marvin can factor some of the Ni's. Hence, applying the Chi- nese Remainder Theorem (CRT) to C1, C2, C3 gives a C’є
ZN1N2N3 satisfying C’ = M≦3 mod N1N2N3. Since M is less than
all the Ni's, we have M^3 < N1N2N3. Then C’ = M^3 holds over
e k
N d
ed k ( N ) kN k ( N )
Nd
l k ( N N ( N )) 3k N 3k
the integers. Thus, Marvin may recover M by computing the real cube root of C. More generally, if all public exponents are
equal to e, Marvin can recover M as soon as k ≥ e. The attack is
Nd
Now k (N) = ed-1< ed.
Nd d N
feasible only when a small e is used.
Hastad describes a far stronger attack. To motivate Hastad's
Since e < (N), we see that k < d ½ N1/4. Hence we obtained
result, consider a naive defence against the above attack. Ra-
ther than broadcasting the encryption of M, Bob could “pad"
e k
N d
1
dN 1 / 4
1
2d 2
(2)
the message prior to encryption. For instance, if M is m bits
long, Bob could send Mi = i2^m + M to party Pi. Since Marvin
obtains encryptions of different messages, he cannot mount
the attack. Unfortunately, Hastad showed that this linear pad-
This is a classic approximation relation. The number of frac-
tions k/d with d < N approximating e/N so closely is bounded
by log2 N. In fact, all such fractions are obtained as convergent
of the continued fraction expansion of e/ N. All one has to do
is compute the logN convergent of the continued fraction for e/N One of these will equal k/d. Since ed- kψ (N) = 1, we have
gcd (k, d) = 1, and hence k/d is a reduced fraction. This is a linear-time algorithm for recovering the secret key d.
Since typically N is 1024 bits, it follows that d must be at least
256 bits long in order to avoid this attack. This is unfortunate for low-power devices such as “smartcards", where a small d
would result in big savings. All is not lost however. Wiener describes a number of techniques that enable fast decryption and are not susceptible to his attack.
To reduce encryption or signature-verification time, it is cus- tomary to use a small public exponent e. The smallest possible value for e is 3, but to defeat certain attacks the value e = 2^16 +1 = 65537 is recommended. When the value 2^16 +1 is used, signature verification requires 17 multiplications, as op-
posed to roughly 1000 when a random e < ψ (N) is used. Un-
like the attack of the previous section, attacks that apply when
a small e is used are far from a total break.
As a first application of Coppersmith's theorem, we present an improvement to an old attack due to Hastad. Suppose Bob wishes to send an encrypted message M to a number of parties
P1, P2,,…. Pk. Each party has its own RSA key (Ni, ei) we as-
sume M is less than all the Ni. Naively, to send M, Bob en-
crypts it using each of the public keys and sends out the ith
ciphertext to Pi. An attacker Marvin can eavesdrop on the con-
nection out of Bob's sight and collect the k transmitted cipher
texts. For simplicity, suppose all public exponents ei are equal
to 3. A simple argument shows that Marvin can recover M if
k >= 3. Indeed, Marvin obtains C1, C2, C3, where
ding is insecure. In fact, he proved that applying any fixed
polynomial to the message prior to encryption does not pre-
vent the attack.
Franklin and Reiter found a clever attack when Bob sends
Alice related encrypted messages using the same modulus. Let
(N, e) be Alice's public key. Suppose M1, M2 є Z*N are two dis-
tinct messages satisfying M1 = f (M2) mod N for some publicly
known polynomial. To send M1 and M2 to Alice, Bob may
naively encrypt the messages and transmit the resulting cipher
texts C1, C2. We show that given C1, C2, and Marvin can easily
recover M1, M2. Although the attack works for any small e, we
state the following lemma for e = 3 in order to simplify the
proof .Coppersmith's Short Pad Attack The Franklin-Reiter
attack might seem a bit artificial. After all, why should Bob
send Alice?
M1 ≠ M2 є Z*N satisfy M1 = f (M2) mod N for some linear poly-
nomial f = ax + b є ZN*x+ with b≠0. Then given (N, e, C1, C2, f),
Marvin can recover M1, M2 in time quadratic in log N.
Proof: To keep this part of the proof general, we state in using an arbitrary e (rather than restricting to e = 3). Since C1=M1e mod N, we know that M2 is a root of the polynomial
g1(x) = f(x)e – C1 є ZN[x], Similarly M2 is a root of
g2(x) = f(x)e – C2 є ZN[x]. The linear factor x-M2 divides both
polynomials. Therefore, Marvin may use the Euclidean algo-
rithm to compute the gcd of g1 and g2. If the gcd turns out to
be linear, M2 is found. The gcd can be computed in quadratic
time in c and log N.
We show that when e = 3 the gcd must be linear. The poly- nomial x3- C2 factors, modulo both p and q into a linear factor
and an irreducible quadratic factor (recall that gcd(e,ψ(N))=1
and hence x3 - C2 has only one root in ZN). Since g2 cannot di-
vide g1, the gcd must be linear, for e > 3 the gcd is almost al-
IJSER © 2011
International Journal of Scientific & Engineering Research Volume 2, Issue 9, September-2011 3
ISSN 2229-5518
ways linear. However for some rare M1, M2 and f, it is possible to obtain a nonlinear gcd, in which case the attack fails.
For e > 3 the attack takes time quadratic in e. Consequently, it can be applied only when a small public exponent e is used. For large e the work in computing the gcd is prohibitive. It is an interesting question to device such an attack for arbitrary e. In particular, can the gcd of g1 and g2 above be found in time polynomials in log e?
Let (N, d) be a private RSA key, suppose by some means Mar- vin is able to expose a fraction of the bits of d, say a quarter of them. Can he reconstruct the rest of d? Surprisingly, the an- swer is positive when the corresponding public key is small. Recently Boneh, Durfee, and Frankel showed that as long as e < sqrt N, it is possible to reconstruct all of d from just a frac- tion of its bits. These results illustrate the importance of safe- guarding the entire private RSA key.
most significant bits of d.
Now we are moving to a completely different type of attacks. Rather than attacking the underlying structure of the RSA function, these attacks focus on the implementation of RSA
Implementation of RSA decryption and signature frequently use the CRT to speed up the computation of Md mod N. In- stead of working modulo N, the signer Bob first computes the signatures modulo p and q and then combines the results us- ing the CRT. More precisely, Bob first computes
Cp = Mdp mod p and Cq = Mdq mod q
Where dp = d mod (p-1) and dq = d mod (q-1). He then obtains the signature C by setting
By definition of e and d, there exists an integer k such that
ed-k (N-p-q+1)=1 (3)
Where
C = T1Cp + T2Cq (mod N) (6)
T1
and T2
Since d< ϕ(N), we must have 0 ≤ k ≤ e. Reducing the equation
modulo 2n/4 and setting q = N/p, we obtain
(ed) p - kp (N - p+1)+ kN = p (mod 2n/4) (4)
Since Marvin is given the n/4 least significant bits of d, he knows the value of ed mod 2n/4. Consequently, he obtains equ- ations an equation in k and p. For each of the e possible values of k, Marvin solves the quadratic equation in p and obtains a number of candidate values for p mod 2n/4. For each of these candidate values, he runs the algorithms of above theorem in order to factor N. One can show that the total number of can- didate values for p mod 2n/4 is at most e log2e. Hence after at most e log2e attempts, N will be factored.
Finally when the encryption exponent e is small, the RSA sys- tem leaks half the most significant bits of the corresponding private key d. To see this consider once again the equation
ed-k (N-p-q+1) = 1 for an integer 0 ≤ k ≤ e. Given k, Marvin
may easily compute
d’ =*(kN + 1)/e+
Then
|d’-d| ≤ k (p+q)/e ≤ 3k√N/e < 3√N (5)
Hence, d’ is a good approximation for d. The bound shows that, for most d, half the most significant bits of d’ are equal to
those of d. Since there are only e possible values for k, Marvin can construct a small set of size e such that one of the element in the set is equal to half the most significant bits of d. The case e = 3 is especially interesting. In this case one can show that always k = 2 and hence the system completely leaks half the
The running time of the last CRT step is negligible compared to the two exponentiations. Note that p and q are half the length of N. Since simple implementations of multiplication take quadratic time, multiplication modulo p is four times faster than modulo N. Furthermore, dp is half the length of d and consequently computing Mdp mod p is eight times faster than computing Md mod N. Overall signature time is thus re- duced by a factor of four. Many implementations use this me- thod to improve performance.
Boneh, DeMillo and Lipton observed that there is an inherent danger in using the CRT method. Suppose that while generat-
ing a signature, a glitch on Bob’s computer causes it to miscal-
culate in a single instruction. Say, while copying a register
from one location to another, one of the bits is flipped. Given
an invalid signature, an adversary Marvin can easily factor
Bob’s modulus N.
Suppose a single error occurs while Bob is generating a signa- ture. As a result, exactly one of Cp or Cq will be computed in-
correctly. Say Cp is correct, but C’q is not. The resulting signa-
ture C’, he knows it is a false signature since C’e ≠ M mod N.
However, notice that
C’e = M mod p while C’e ≠ M mod q
As a result, gcd (N,C’e - M) exposes a nontrivial factor of N.
For the attack to work Marvin must have full knowledge of M.
namely, we are assuming Bob does not use any random pad-
ding procedure. Random padding prior to signing defeats the
attack. A simpler defense is for Bob to check the generated
signature before sending it out to the world. Checking is espe-
IJSER © 2011
International Journal of Scientific & Engineering Research Volume 2, Issue 9, September-2011 4
ISSN 2229-5518
cially important when using the CRT speedup method. Ran- dom faults are hazardous to many cryptographic systems. Many systems, including a non-CRT implementation of RSA, can be attacked using random faults. However, these results are far more theoretical.
Let N be an n-bit RSA modulus and M be an m-bit message with m < n. Before applying RSA encryption it is natural to pad the message M to n bits by appending random bits to it. An old version of standard known as Public Key Cryptogra- phy Standard 1 (PKCS 1) uses this approach. After padding the message looks as follows:
02 | Random | 00 | M |
The resulting message is n bits long and is directly encrypted using RSA. The initial block containing “02” is 16 bits long and
is there to indicate that a random pad has been added to the message.
When PKCS 1 message is received by Bob’s machine, an appli- cation decrypts it, checks the initial block, and strips off the
random pad. However some applications check for the “02”
initial block and if it is not present they send back an error
message saying “invalid message”. Bleichenbacher showed
that this error message can lead to disastrous consequences:
using the error message, an attacker Marvin can decrypt ci-
pher text of his choice.
Suppose Marvin intercepts a cipher text C intended for Bob and wants to decrypt it. To mount the attack, Marvin picks a
random r є Z*N, computes C’ = rC mod N, and sends C’ to
Bob’s machine. An application running on Bob’s machine rece-
ives C’ and attempts to decrypt it. It is either responds with an
error message or does not respond at all. Hence, Marvin learns
whether the most significant 16 bits of the decryption of C’ are
equal to 02. In effect, Marvin test whether the 16 bits most sig-
nificant bits of the decryption of rC mod N are qual to 02, for
any r of his choice. Bleichenbacher showed that such an at-
tempt is sufficient for decrypting C.
Two decades of research into inverting the RSA function pro- duced some insightful attacks, but no devastating attack has ever been found. The attacks discovered so far mainly illu- strate the pitfalls to be avoided when implementing RSA. At the moment it appears that proper implementations can be trusted to provide security in the digital world. These attacks illustrate that a study of the underlying mathematical struc- ture is insufficient. Desmedt and Odlyzko , Joye and Quisqua- ter and deJonge and Chaum describe some additional at- tacks. Throughout the paper we observed that many attacks can be defeated by properly padding the message prior to en- cryption or signing.
[1] D. Boneh, G.Durfee. New results on cryptanalysis of low private exponent RSA. Preprint, 1998.
[2] D.Bleichenbacher. chosen ciphertext attacks against protocols based
on the RSA encryption standard PKCS 1. In CRYPTO ’98, volume
1462 of Lecture Notes in Computer Science, pages 1-12, Springer-
Verlag, 1998
[3] D. Boneh, R.DeMillo and R. Lipton. On the importance of checking cryptographic protocols for faults. In EUROCRYPT ’97, volume
1233 of Lectuer Notes in Computer Science, pages 37 51.Springer- Verlag, 1997.
[4] P.Kocher. Timing attacks on implementations od Diffie-Hellman,
RSA, DSS and other systems. In CRYPTO’96, volume 1109 of lecture
Notes in Computer Science, pages 104 113 Springer-Verlag, 1996.
[5] J.Hastad Solving simultaneous modular equations of low degree, SIAM J. of Computing, 17:336-341, 1988.
IJSER © 2011