Cryptography Reference
In-Depth Information
necessary in a full-fledged implementation of the RSA classes (see in this regard
the pointer on page 384).
However, we do not wish to do without an effective possibility of speeding
up the calculations for decryption or signing. By application of the Chinese
remainder theorem (see page 203) the RSA operations with the secret key
d
can
be made about four times as fast as with the usual method of calculating a single
power: Given a secret key
with
n
=
pq
we form
d
p
:=
d
mod (
p −
1)
and
d
q
:=
d
mod (
q −
1)
and employ the extended Euclidean algorithm to
compute the representation
1=
rp
+
sq
, from which we extract the value
r
as
the multiplicative inverse of
p
modulo
q
(cf. Section 10.2). We then employ the
components
p, q, d
p
,d
q
,r
to calculate
c
=
m
d
mod
n
as follows:
1.
Calculate
a
1
← m
d
p
mod
p
and
a
2
← m
d
q
mod
q
.
d, n
2.
Calculate
c ← a
1
+
p
((
a
2
− a
1
)
r
mod
q
)
.
After step 1 we have
a
1
≡ m
d
p
≡ m
d
mod
q
.
To see this, just use the little theorem of Fermat (cf. page 177), according to which
m
p
−
1
≡ m
d
mod
p
and
a
2
≡ m
d
q
≡
1mod
p
, respectively
m
q
−
1
≡
1mod
q
.From
d
=
(
p −
1) +
d
p
with
integral
it follows that
m
p
−
1
m
d
≡ m
(
p
−
1)+
d
p
m
d
p
≡ m
d
p
mod
p,
≡
(17.9)
and analogously, we have the same for
m
d
mod
q
. An application of the Garner
algorithm (see page 207) with
m
1
:=
p
,
m
2
:=
q
, and
r
:= 2
shows us at once
that
c
in step 2 represents the desired solution. Rapid decryption is implemented
in the auxiliary function
RSAkey::fastdecrypt()
. All exponents modulo
p
,
q
,or
n
are calculated via Montgomery exponentiation with the
LINT
function (cf. page
344).
// Selection from the include file rsakey.h
...
#include "flintpp.h"
#include "ripemd.h"
#define BLOCKTYPE_SIGN 01
#define BLOCKTYPE_ENCR 02
// The RSA key structure with all key components
typedef struct
{
LINT pubexp, prvexp, mod, p, q, ep, eq, r;
USHORT bitlen_mod;// binary length of modulus
USHORT bytelen_mod; // length of modulus in bytes
} KEYSTRUCT;
