Cryptography Reference
In-Depth Information
2.
Now
A
would like to send an encrypted message
M
to
B
(0
≤
M < n
B
)
.
Since
A
has received from
B
his public key
e
B
,n
B
,
A
calculates
C
=
M
e
B
mod
n
B
and sends the encrypted value
C
to
B
.
3.
After
B
has obtained the encrypted message
C
from
A
, then
B
decodes this
message by calculating
C
=
M
d
B
mod
n
B
d
B
,n
B
. Now
B
possesses the plain text
M
of the
using his secret key
message.
1mod
φ
(
n
)
, there
exists an integer
k
such that
d · e
=1+
k · φ
(
n
)
. We thus obtain
It is not difficult to see why this works. Because
d
·
e
≡
M
φ
(
n
)
k
C
d
≡ M
de
≡ M
1+
k
·
φ
(
n
)
≡ M ·
≡ M
mod
n,
(17.3)
where we have made use of the theorem of Euler quoted on page 177, from
which we deduce that
M
φ
(
n
)
≡
1mod
n
if
gcd(
M, n
) = 1
. For the more
theoretically interesting case that
gcd(
M, n
)
>
1
, equation (17.3) holds as well:
For relatively prime
p
and
q
, we have the isomorphism
Z
Z
p
× Z
q
. Since
ve ≡
1 mod gcd(
p −
1
,q−
1)
, it follows that
M
ve
=
M
in
Z
p
and in
Z
q
(obviously for
M
=0
as well), and therefore also in
Z
n
.
An alternative to key generation is the use of
univeral exponents
λ
:=
lcm(
p
1)
instead of
φ
(
n
)
. The basis for this is the following theorem
of Carmichael: Let
λ
()
denote the Carmichael function, defined by
λ
(
n
) :=
lcm (
λ
(2
a
0
)
,φ
(
p
a
1
)
,...,φ
(
p
a
r
))
for all
n
=2
a
0
φ
(
p
a
1
)
−
1
,q
−
φ
(
p
a
r
)
, where the
···
p
i
are distinct prime numbers and
λ
2
t
:=
2
t
−
1
if
t <
3
,
2
t
−
2
if
t ≥
3
.
Then for all
a ∈
Z
×
n
, we have
a
λ
(
m
)
≡
1mod
n
. For a proof, see page 15 of
[Kran]. As above, this can also be extended to the case
gcd(
M, n
)=1
, since from
ev
=1+
kλ
(
n
)
we have
ve ≡
1 mod gcd(
p −
1
,q−
1)
, and so in
Z
p
and
Z
q
we
have
M
ve
=
M
. On account of the isomorphism
Z
Z
×
Z
q
, this holds in
Z
n
as well. The advantage of using
λ
lies in a smaller exponent
e
, since
λ
is always a
proper divisor of
(
p
p
1)
. In practice, this advantage is negligible, since
gcd(
p −
1
,q−
1)
for random values of
p
and
q
is small with high probability.
It is clear that the security of the RSA algorithm depends on the ease of
factorability of
n
.If
n
can be factored into its components
p
and
q
, then the secret
key
d
can be determined from the public key
e
. Conversely, the factorization
of
n
can be easily accomplished if both key components
d
and
e
are known: If
k
:=
de −
1
, then
k
is a multiple of
φ
(
n
)
, and therefore we have
k
=
r ·
2
t
with
−
1)(
q
−
