Cryptography Reference
In-Depth Information
(
x
Φ(
n
)
)
t
= 1 +
u
·
q
,
where
u
is some integer. We multiply this equation by
x
:
(
x
Φ(
n
)
)
t
=
x
+
x
x
·
·
u
·
q
=
x
+(
r
·
p
)
·
u
·
q
=
x
+
r
·
u
·
(
p
·
q
)
=
x
+
r
·
u
·
n
(
x
Φ(
n
)
)
t
x
·
≡
x
mod
n
.
(7.6)
Inserting Eq. (7.6) into Eq. (7.4) yields the desired result:
d
k
pr
=(
x
Φ(
n
)
)
t
·
x
≡
x
mod
n
.
If this proof seems somewhat lengthy, please remember that the correctness of
RSA is simply assured by Step 5 of the RSA key generation phase. The proof be-
comes simpler by using the Chinese Remainder Theorem which we have not intro-
duced.
7.4 Encryption and Decryption: Fast Exponentiation
Unlike symmetric algorithms such as AES, DES or stream ciphers, public-key al-
gorithms are based on arithmetic with very long numbers. Unless we pay close
attention to how to realize the necessary computations, we can easily end up with
schemes that are too slow for practical use. If we look at RSA encryption and de-
cryption in Eqs. (7.1) and (7.2), we see that both are based on modular exponentia-
tion. We restate both operations here for convenience:
x
e
y
=
e
k
pub
(
x
)
≡
mod
n
(encryption)
y
d
≡
x
=
d
k
pr
(
y
)
mod
n
(decryption)
A straightforward way of exponentiation looks like this:
SQ
−→
MU L
−−−→
MU L
−−−→
MU L
−−−→
x
2
x
3
x
4
x
5
x
···
where
SQ
denotes squaring and
MU L
multiplication. Unfortunately, the exponents
e
and
d
are in general very large numbers. The exponents are typically chosen in the
range of 1024-3072 bit or even larger. (The public exponent
e
is sometimes chosen
to be a small value, but
d
is always very long.) Straightforward exponentiation as
shown above would thus require around 2
1024
or more multiplications. Since the
number of atoms in the visible universe is estimated to be around 2
300
, comput-
ing 2
1024
multiplications to set up one secure session for our Web browser is not
