Cryptography Reference
In-Depth Information
for index values
i
2. Like any recursion, we need starting values for
s
0
,
s
1
,
t
0
,
t
1
.
These initial values (which we derive in Problem 6.13) can be shown to be
s
0
=
1
,
s
1
= 0
,
t
0
= 0
,
t
1
= 1.
≥
Extended Euclidean Algorithm (EEA)
Input
: positive integers
r
0
and
r
1
with
r
0
>
r
1
Output
: gcd(
r
0
,
r
1
),aswellas
s
and
t
such that gcd(
r
0
,
r
1
)=
s
·
r
0
+
t
·
r
1
.
Initialization
:
s
0
= 1
t
0
= 0
s
1
= 0
t
1
= 1
i
= 1
Algorithm
:
1DO
1.1
i
=
i
+ 1
1.2
r
i
=
r
i
−
2
mod
r
i
−
1
1.3
q
i
−
1
=(
r
i
−
2
−
r
i
)
/
r
i
−
1
1.4
s
i
=
s
i
−
2
−
q
i
−
1
·
s
i
−
1
1.5
t
i
=
t
i
−
2
−
q
i
−
1
·
t
i
−
1
WHILE
r
i
= 0
2
RETURN
gcd(
r
0
,
r
1
)=
r
i
−
1
s
=
s
i
−
1
t
=
t
i
−
1
As mentioned above, the main application of the EEA in asymmetric cryptog-
raphy is to compute the inverse modulo of an integer. We already encountered this
problem in the context of the affine cipher in Chap. 1. For the affine cipher, we
were required to find the inverse of the key value
a
modulo 26. With the Euclidean
algorithm, this is straightforward. Let's assume we want to compute the inverse
of
r
1
mod
r
0
where
r
1
<
r
0
. Recall from Sect. 1.4.2 that the inverse only exists if
gcd(
r
0
,
r
1
)=1. Hence, if we apply the EEA, we obtain
s
·
r
0
+
t
·
r
1
= 1 = gcd(
r
0
,
r
1
)
.
Taking this equation modulo
r
0
we obtain:
s
·
r
0
+
t
·
r
1
= 1
s
·
0 +
t
·
r
1
≡
1mod
r
0
r
1
·
t
≡
1mod
r
0
(6.6)
Equation (6.6) is exactly the definition of the inverse of
r
1
. That means, that
t
itself
is the inverse of
r
1
:
t
=
r
−
1
1
mod
r
0
.
