Cryptography Reference
In-Depth Information
Thus, if we need to compute an inverse
a
−
1
mod
m
, we apply the EEA with the
input parameters
m
and
a
. The output value
t
that is computed is the inverse. Let's
look at an example.
Example 6.6.
Our goal is to compute 12
−
1
mod 67. The values 12 and 67 are rela-
tively prime, i.e., gcd(67
,
12)=1. If we apply the EEA, we obtain the coefficients
s
and
t
in gcd(67
,
12)=1 =
s
·
67 +
t
·
12. Starting with the values
r
0
= 67 and
r
1
= 12,
the algorithm proceeds as follows:
i q
i
−
1
r
i
s
i
t
i
2
57 1-5
3
15-1
6
4
12 2-11
5
21-5
28
This gives us the linear combination
−
5
·
67 + 28
·
12 = 1
As shown above, the inverse of 12 follows from here as
12
−
1
≡
28 mod 67
.
This result can easily be verified
28
·
12 = 336
≡
1 mod 67
.
Note that the
s
coefficient is not needed and is in practice often not computed.
Please note also that the result of the algorithm can be a negative value for
t
.The
result is still correct, however. We have to compute
t
=
t
+
r
0
, which is a valid
operation since
t
t
+
r
0
mod
r
0
.
For completeness, we show how the EEA can also be used for computing mul-
tiplicative inverses in Galois fields. In modern cryptography this is mainly relevant
for the derivation of the AES S-Boxes and for elliptic curve public-key algorithms.
The EEA can be used completely analogously with polynomials instead of inte-
gers. If we want to compute an inverse in a finite field
GF
(2
m
), the inputs to the
algorithm are the field element
A
(
x
) and the irreducible polynomial
P
(
x
). The EEA
computes the auxiliary polynomials
s
(
x
) and
t
(
x
), as well as the greatest common
divisor gcd(
P
(
x
)
,
A
(
x
)) such that:
≡
s
(
x
)
P
(
x
)+
t
(
x
)
A
(
x
)=gcd(
P
(
x
)
,
A
(
x
)) = 1
Note that since
P
(
x
) is irreducible, the gcd is always equal to 1. If we take the
equation above and reduce both sides modulo
P
(
x
), it is straightforward to see that
the auxiliary polynomial
t
(
x
) is equal to the inverse of
A
(
x
):
