Cryptography Reference
In-Depth Information
required for these calculations. Whenever, we suggest a computer for cal-
culations henceforth, we will be assuming, tacitly, that a software package
such as
Maple
or
MATLAB
is available.
≡
4.23. (
p,q
) = (5443
,
4327),
n
= 23551861,
e
= 5, and
c
1960142 (mod
n
).
(
Hint: Without repeated squaring, even with a computer, raising the ci-
phertext to the deciphering exponent
d
, will take considerable time to exe-
cute. Thus, you should first factor
d
, then raise
c
to the factors successively
until
m
is found. This will quite considerably reduce the calculation time.
The same comment holds for Exercises 4.24-4.26.
)
4.24. (
p,q
) = (6113
,
7001),
n
= 42797113,
e
= 11, and
c
≡
3430667 (mod
n
).
4.25. (
p,q
) = (7499
,
8237),
n
= 61769263,
e
= 7, and
c
≡
16695987 (mod
n
).
4.26. (
p,q
) = (8999
,
9547),
n
= 85913453,
e
= 13, and
c
≡
63358885 (mod
n
).
4.27. Explain why neither
e
= 3 nor
e
= 11 can be employed with the modulus
in Exercise 4.26.
4.28. The
Carmichael function
,
λ
(
n
), is defined as follows. If
n
∈
N
, and
n
=2
a
p
a
1
1
p
a
2
2
p
a
k
k
·
·
···
is its canonical prime factorization, namely, 2
<p
1
<p
2
<
···
<p
k
, then
λ
(
n
)=
φ
(
n
)
if
n
=2
a
, and 1
≤
a
≤
2
,
2
a
−
2
=
φ
(
n
)
/
2
if
n
=2
a
,a>
2
,
lcm(
λ
(2
a
)
,φ
(
p
a
1
)
,...,φ
(
p
a
k
))
if
k
≥
1
,
where
φ
is Euler's totient (see Definition A.22 on page 479), and where
lcm is the least common multiple (see page 471).
Suppose that
p
and
q
are primes and
n
=
pq
is an RSA modulus. Fur-
thermore, assume that
x
with gcd(
x,n
) = 1 and that
e
and
d
are the
RSA-enciphering and deciphering exponents, respectively. Show that the
following hold.
∈
Z
1.
x
λ
(
n
)
≡
1 (mod
n
).
2.
x
ed
≡
x
(mod
n
).
(
In particular, if
p
and
q
are safe primes, then
λ
(
n
)=
φ
(
n
)
/
2
, so the
above shows that
φ
(
n
)
/
2
may be used in place of
φ
(
n
)
in the RSA cipher.
(
See page 200 for a definition and application of safe primes.
)
In fact,
even when
p
and
q
are not safe primes,
λ
(
n
)
may be employed in the RSA
cryptosystem since
φ
(
n
)
and
λ
(
n
)
are roughly the same size. The reason
for the latter is that the
gcd(
p
−
1
,q
−
1)
has an expectation of being small
when
p
and
q
are chosen arbitrarily.
)
Search WWH ::
Custom Search