Cryptography Reference
In-Depth Information
6.6.
Using the extended Euclidean algorithm, compute the greatest common divisor
and the parameters
s
,
t
of
1. 198 and 243
2. 1819 and 3587
For every problem check if
sr
0
+
tr
1
= gcd(
r
0
,
r
1
) is actually fulfilled. The rules are
the same as above: use a pocket calculator and show what happens in every iteration
step.
6.7.
With the Euclidean algorithm we finally have an efficient algorithm for finding
the multiplicative inverse in
Z
m
that is much better than exhaustive search. Find the
inverses in
Z
m
of the following elements
a
modulo
m
:
1.
a
= 7,
m
= 26 (affine cipher)
2.
a
= 19,
m
= 999
Note that the inverses must again be elements in
Z
m
and that you can easily verify
your answers.
6.8.
Determine
(
m
),for
m
= 12
,
15
,
26, according to the definition: Check for each
positive integer
n
smaller
m
whether gcd(
n
,
m
)=1. (You do
not
have to apply Eu-
clid's algorithm.)
φ
6.9.
Develop formulae for
φ
(
m
) for the special cases when
1.
m
is a prime
2.
m
=
p
q
, where
p
and
q
are primes. This case is of great importance for the
RSA cryptosystem. Verify your formula for
m
= 15
,
26 with the results from the
previous problem.
·
6.10.
Compute the inverse
a
−
1
mod
n
with Fermat's Theorem (if applicable) or Eu-
ler's Theorem:
a
= 4,
n
= 7
a
= 5,
n
= 12
a
= 6,
n
= 13
6.11.
Verify that Euler's Theorem holds in
Z
m
,
m
= 6
,
9, for all elements
a
for which
gcd(
a
,
m
)=1. Also verify that the theorem does not hold for elements
a
for which
gcd(
a
,
m
)
= 1.
6.12.
For the affine cipher in Chapter 1 the multiplicative inverse of an element
modulo 26 can be found as
a
−
1
a
11
≡
mod 26
.
Derive this relationship by using Euler's Theorem.
6.13.
The extended Euclidean algorithm has the initial conditions
s
0
= 1
,
s
1
= 0
,
t
0
=
0
,
t
1
= 1.
Derive
these conditions. It is helpful to look at how the general iteration
formula for the Euclidean algorithm was derived in this chapter.
