Cryptography Reference
In-Depth Information
Use the Chinese remainder theorem (CRT) to Decrypt.
1
e
−
1
Let
d
p
≡
(mod
p
−
1) and
e
−
1
d
q
≡
1). These are called the
CRT private exponents
. Given a cipher-
text
c
one computes
m
p
=
(mod
q
−
c
d
q
(mod
q
). The message
m
is then
computed using the Chinese remainder theorem (it is convenient to use the method of
Exercise
2.6.3
for the CRT).
For
c
d
p
(mod
p
) and
m
q
=
this
system
the
private
key
is
then
sk
=
(
p,q,d
p
,d
q
).
If
we
denote
by
T
=
c
log(
N
)
M
(log(
N
)) the cost of a single exponentiation modulo
N
to a power
d
N
then the cost using the Chinese remainder theorem is approximately
2
c
(log(
N
)
/
2)
M
(log(
N
)
/
2) (this is assuming the cost of the Chinese remaindering is
negligible). When using Karatsuba multiplication this speeds up RSA decryption by a
factor of approximately 3 (in other words, the new running time is a third of the old
running time).
≈
24.1.2 Variants of RSA
There has been significant effort devoted to finding more efficient variants of the RSA
cryptosystem. We briefly mention some of these now.
Example 24.1.3
(
Multiprime-RSA
2
)Let
p
1
,...,p
k
be primes of approximately
κ/k
bits
and let
N
p
k
. One can use
N
as a public modulus for the RSA cryptosystem.
Using the Chinese remainder theorem for decryption has cost roughly the same as
k
exponentiations to powers of bit-length
κ/k
and modulo primes of bit-length
κ/k
. Hence,
the speedup is roughly by a factor
k/k
2
.
58
=
p
1
···
1
/k
1
.
58
.
To put this in context, going from a single exponentiation to using the Chinese remainder
theorem in the case of 2 primes gave a speedup by a factor of 3. Using 3 primes gives an
overall speedup by a factor of roughly 5
.
7, which is a further speedup of a factor 1
.
9 over the
2-prime case. Using 4 primes gives an overall speedup of about 8
.
9, which is an additional
speedup over 3 primes by a factor 1
.
6.
However, there is a limit to how large
k
can be, as the complexity of the elliptic curve
factoring method mainly depends on the size of the smallest factor of
N
.
=
Exercise 24.1.4
(Tunable balancing of RSA) An alternative approach is to construct the
public key (
N
pq,e
) so that the Chinese remainder decryption exponents are relatively
short. The security of this system will be discussed in Section
24.5.2
.
Let
κ,n
e
,n
d
be the desired bit-lengths of
N,e
and
d
(mod
p
=
−
1)
,d
(mod
q
−
1).
Assume that
n
e
+
n
d
>κ/
2. Give an algorithm to generate primes
p
and
q
of bit-length
κ/
2, integers
d
p
and
d
q
of bit-length
n
d
and an integer
e
of bit-length
n
e
such that
ed
p
≡
1(mod
p
−
1) and
ed
q
≡
1(mod
q
−
1).
p
r
q
.For
The fastest variant of RSA is due to Takagi and uses moduli of the form
N
=
some discussion about factoring such integers see Section
19.4.3
.
1
This idea is often credited to Quisquater and Couvreur [
443
] but it also appears in Rabin [
444
].
2
This idea was proposed (and patented) by Collins, Hopkins, Langford and Sabin.
