Cryptography Reference
In-Depth Information
p r q where p and q are primes and r> 1.
Suppose the public exponent e in RSA is small. One can compute c d (mod N ) as follows.
Let d p
Example 24.1.5 ( Takagi-RSA [ 538 ]) Let N
=
c d p (mod p )
d (mod p
1) and d q
d (mod q
1). One first computes m p =
c d q (mod q ).
To determine m (mod p r ) one uses Hensel lifting. If we have determined m i =
m (mod p i ) such that m i
and m q =
c (mod p i ) then we lift to a solution modulo p i + 1
by writ-
xp i , where x is a variable. Then
ing m i + 1 =
m i +
m i + 1 =
xp i ) e
m i +
x ( e m e i ) p i
c (mod p i + 1 )
( m i +
(24.1)
gives a linear equation in x modulo p . Note that computing m i (mod p i + 1 ) in equation ( 24.1 )
is only efficient when e is small. If e is large then the Hensel lifting stage is no faster than
just computing c e 1 (mod ϕ ( p r )) (mod p r ) directly.
The total cost is two “full” exponentiations to compute m p and m q , r
1 executions
of the Hensel lifting stage, plus one execution of the Chinese remainder theorem. Ignoring
everything except the two big exponentiations, one has an algorithm whose cost is 2 / ( r
+
1) 2 . 58
2 this is about 9 times
faster than standard RSA (i.e., about 1 . 6 times faster than using 3-prime RSA) and taking
r
times faster than naive textbook RSA decryption. Taking r
=
3 is about 18 times faster than standard RSA (i.e., about 2 times faster than using
4-prime RSA).
=
(2 20
7) 3 (2 19
Exercise 24.1.6 Let N
474776119073176490663504
be the RSA encryption of a message m using public exponent e
=
+
+
21) and let c
=
=
3. Determine the message
using the Takagi decryption algorithm.
Exercise 24.1.7 Describe and analyse the RSA cryptosystem using moduli of the form
N
=
p r q s . Explain why it is necessary that r
=
s .
24.1.3 Security of textbook RSA
We have presented “textbook” RSA above. This is unsuitable for practical applications for
many reasons. In practice, RSA should only be used with a secure randomised padding
scheme. Nevertheless, it is instructive to consider the security of textbook RSA with respect
to the security definitions presented earlier.
Exercise 1.3.4 showed that textbook RSA encryption does not have OWE-CCA security
and Exercise 1.3.9 showed that textbook RSA signatures do not have existential forgery
security even under a passive attack. We recall one more easy attack.
Exercise 24.1.8 Show that one can use the Jacobi symbol to attack the IND-CPA security
of RSA encryption.
Despite the fact that RSA is supposed to be related to factoring, the security actually
relies on the following computational problem.
Search WWH ::




Custom Search