2010 | OriginalPaper | Chapter
Efficient CRT-RSA Decryption for Small Encryption Exponents
Authors : Subhamoy Maitra, Santanu Sarkar
Published in: Topics in Cryptology - CT-RSA 2010
Publisher: Springer Berlin Heidelberg
Activate our intelligent search to find suitable subject content or patents.
Select sections of text to find matching patents with Artificial Intelligence. powered by
Select sections of text to find additional relevant content using AI-assisted search. powered by
Consider CRT-RSA with the parameters
p
,
q
,
e
,
d
p
,
d
q
, where
p
,
q
are secret primes,
e
is the public encryption exponent and
d
p
,
d
q
are the private decryption exponents. We present an efficient method to select CRT-RSA parameters in such a manner so that the decryption becomes faster for small encryption exponents. This is the most frequently used situation for application of RSA in commercial domain. Our idea is to choose
e
and the factors (with low Hamming weight) of
d
p
,
d
q
first and then applying the extended Euclidean algorithm, we obtain
p
,
q
of same bit size. For small
e
, we get an asymptotic reduction of the order of
${{1}\over{3}}$
in the decryption time compared to standard CRT-RSA parameters for large
N
=
pq
. In case of practical parameters, with 1024 bits
N
and
e
= 2
16
+ 1, we achieve a reduction of more than 27%. Extensive security analysis is presented for our selected parameters and benchmark examples are also provided.