Cryptography Reference
In-Depth Information
and in addition to add random redundancy to broadcast messages before
their encryption. This can take place by filling in the message in some
appropriate way up to a suitable value less than the modulus. Such a process
is called padding (cf. page 396 and [Schn], Section 9.1).
3. Small secret exponents and small intervals between p and q
Even more problematic than small public exponents are small secret
exponents: M. Wiener [Wien] showed already in 1990 how, given a key
e, n
with e<φ ( n ) , the associated private key component d can be
calculated if d is too small. Wiener's result was further sharpened by D.
Boneh and G. Durfee [Bone], who showed that d can be computed from
if d<n 0 . 292 . However, it is conjectured that the result holds as well
for d<n 0 . 5 .
It is plausible that the modulus n can be easily f ac tored when p ≈ q ≈ n ,
by dividing by odd natural numbers close to n . The situation is also
dangerous when the difference between p and q is less than n 1 / 4 , for then
the factorization method of Fermat can be applied: To factor n it suffices to
produce natural numbers x, y ∈{n − 1 ,n +1 }
e, n
such that 4 n = x 2
− y 2 ,
for then, the factor s o f n are 2 ( x + y ) a nd 2 ( x
y ) . The search for x and y
runs over x = 2 n , 2 n +1 , 2 n +2 ,... until x 2
4 n is a square
(which can be checked with the aid of the fun ct ion issqr_l ). The cost of
factorization by this method is O ( p − q ) 2 / n , and it is easy to manage
when
|p − q| <cn 1 / 4 ,withaconstant c n 1 / 4 .
Work of B. de Weger, extended with proven methods of attack by Wiener,
Boneh, and Durfee, shows how the security of the procedure depends on the
sizes of both the secret key and the difference of the prime factors
|p−q|
: Let
|p − q| = n β and d = n δ . The modulus n = pq can be factored efficiently
if 2 4 β<δ< 1
2 β −
3 (4 β + 5)(4 β − 1)
1
2 or δ< 6 (4 β +5)
1
(see [deWe]).
As a consequence of his results, de Weger recommends choosing p , q ,and
d such that δ +2 β> 4 .For δ ≥
1
2 , as suggested in the previous result, β
must be chosen to be greater than 8 to follow this suggestion.
This is in accord with suggestions to be found elsewhere, according to which
0 . 5 < | log 2 p − log 2 q| < 30 should hold (see [EESSI]).
4. Encryption of small texts
Boneh, Joux, and Nguyen have presented a particularly efficient method
with which it is frequently possible to determine, for an arbitrary public key
2 m from the cipher text C = M e . The necessary
time for this corresponds to 2 · 2 m/ 2 modular exponentiations. Additionally,
2 m/ 2 m bits of memory are required (see[Bon2]). RSA encryption with
symmetric keys of length less than 128 bits without additional redundancy
e, n
,theplaintext M
 
Search WWH ::




Custom Search