Cryptography Reference
In-Depth Information
(2
2
3)=(2
2
2
1
)(3
1
3
0
)=(4
Φ
(12)=
Φ
·
−
−
−
2)(3
−
1)=4
.
Now we can verify Euler's theorem:
5
Φ(12)
= 5
4
= 25
2
= 625
≡
1 mod 12
.
It is easy to show that Fermat's Little Theorem is a special case of Euler's theorem.
If
p
is a prime, it holds that
(
p
)=(
p
1
p
0
)=
p
Φ
−
−
1. If we use this value for
Euler's theorem, we obtain:
a
Φ(
p
)
=
a
p
−
1
≡
1 ( mod
p
), which is exactly Fermat's
Little Theorem.
6.4 Discussion and Further Reading
Public-Key Cryptography in General
Asymmetric cryptography was introduced
in the landmark paper by Whitfield Diffie and Martin Hellman [58]. Ralph Merkle
independently invented the concept of asymmetric cryptography but proposed an
entirely different public-key algorithm [121]. There are a few good accounts of the
history of public-key cryptography. The treatment in [57] by Diffie is recommended.
Another good overview on public-key cryptography is [127]. A very instructive and
detailed history of elliptic curve cryptography, including the relatively intense com-
petition between RSA and ECC during the 1990s, is described in [100]. More recent
development in asymmetric cryptography is tracked by the Workshop on Public-Key
Cryptography (PKC) series.
Modular Arithmetic
With respect to the mathematics introduced in this chapter,
the introductory topics on number theory recommended in Sect. 1.5 make good
sources for further reading. In practical terms, the Extended Euclidean Algorithm
(EEA) is the most crucial, since virtually all implementations of public-key schemes
incorporate it, especially modular inversion. An important acceleration technique
for the scheme is the binary EEA. Its advantage over the standard EEA is that it
replaces divisions by bit shifts. This is in particular attractive for the very long num-
bers occurring in public-key schemes.
Alternative Public-Key Algorithms
In addition to the three established families
of asymmetric schemes, there exist several others. First, there are algorithms which
have been broken or are believed to be insecure, e.g., knapsack schemes. Second,
there are generalizations of the established algorithms, e.g., hyperelliptic curves,
algebraic varieties or non-RSA factoring-based schemes. These schemes use the
same one-way function, that is, integer factorization or the discrete logarithm in
certain groups. Third, there are asymmetric algorithms which are based on differ-
ent one-way functions. Four families of one-way function are of particular interest:
hash-based, code-based, lattice-based and multivariate quadratic (MQ) public-key
algorithms. There are, of course, reasons why they are not as widely used today.
