Cryptography Reference
In-Depth Information
polynomial applied as padding is insecure. Therefore, to defend against his
attack is to pad with a randomized polynomial, not a fixed one.
There are also attacks against naive padding algorithms. Let us enlist Alice,
Bob, and Mallory to describe one such method. Alice pads a message m that she
wants to send to Bob, then enciphers it, and transmits it. However, malicious
Mallory, applying a classic case of the man-in-the-middle attack, intercepts the
message and prevents it from reaching Bob. When Bob does not respond to her
message, Alice assumes he did not receive it, so she decides to randomly pad
m again, encrypts it, and sends it to him. Now Mallory intercepts the second
message and has two different encipherments of m using different random pads.
In [61], Coppersmith describes a method for Mallory to retrieve m . For instance,
if e = 3, then when the pad has maximum bitlength less than a ninth that of
the message length, Mallory can e8ciently recover m (see [170, page 117] for
illustrations and a deeper discussion).
Perhaps the most powerful attack developed by Coppersmith is his partial
key exposure attack (see [61]), which can be described as follows. Given an
RSA modulus n = pq of bitlength , the bitlength of either p or q is about / 2.
Knowledge of either the / 4 most significant bits of p or the / 4 least significant
bits of p , can be shown to allow one to e8ciently factor n . There is another
related attack (see [36]), which says that knowledge of the / 4 least significant
bits of the decryption exponent d , allows one to find d in O ( e log 2 ( e )) steps.
Thus, if e is small, a cryptanalyst can deduce d from just a few bits. Thus, we
have another lesson for the cryptographer: ensure that all bits of d are secure.
Low Secret RSA Exponent Attacks
Again, as with the reason for choosing small public exponents, we want
increased e8ciency in the decryption process, so we choose small secret expo-
nents. For instance, given a 1024-bit RSA modulus, the decryption process can
have e 8 ciency increased ten-fold with the choice of small d . However, Weiner
[280] developed an attack that yields a total break of the RSA cryptosystem,
(by a total break , we mean that a cryptanalyst can recover d , hence retrieve all
plaintext from ciphertext).
Weiner's Attack
If n = pq where p and q are primes such that q<p< 2 q and d<n 1 / 4 / 3,
then given a public key e with ed
1 (mod φ ( n )), d can be e8ciently calculated.
We conclude that use of small decryption exponents, in the sense given
by Weiner above, lead to a total loss of security in the RSA cryptosystem.
Weiner's method was improved in [35] by Boneh and Durfee who showed that
RSA is insecure if d<n 0 . 292 . Hence, the gain in e8ciency for using such small
decryption keys is a cryptographically lethal exercise.
Search WWH ::




Custom Search