2010 | OriginalPaper | Buchkapitel
Efficient CRT-RSA Decryption for Small Encryption Exponents
verfasst von : Subhamoy Maitra, Santanu Sarkar
Erschienen in: Topics in Cryptology - CT-RSA 2010
Verlag: Springer Berlin Heidelberg
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. 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.