Cryptography Reference
In-Depth Information
hierarchically in a tree structure (see also Figure 2.1). A trustworthy 'root
computer' uses suitable cryptographic protocols to confirm that certain other
computers are trustworthy. These computers, in turn, certify other computers,
and so on. Leaving the details aside, it means that the entire security depends
on the root computer. That's a point to worry about. But the interlock protocol
can be used to periodically check a root computer.
PGP
is the popular counterpart to PEM, but rather than using a centralized trust
hierarchy, it works on a 'federal' principle: every PGP user (electronically)
signs the public key for parties he personally trusts (electronic signatures will
be dealt with in Section 6.3). According to the motto: 'my friend's friend is my
friend too', PGP builds a 'Web of Trust', a network with pretty secure connec-
tion channels. This network is hard to disturb because it is irregular — similar to
the Internet, the precursor of which was actually invented to guarantee secure
transmission of messages in times of war. More about PGP in Chapter 7.
This section actually belongs to Chapter 6 since it deals exclusively with cryp-
tographic protocols. But unless we are aware of such problems, dealing with
asymmetric methods gets somewhat dry.
4.5.3 The RSA Method and Eight Risks
You have probably heard of the RSA method since it is the most popular
asymmetric method. In contrast to the methods known up to then (knapsack
algorithm and Diffie - Hellman key exchange), RSA was the first method to
be suitable both for asymmetric encryption and digital signatures. The name
is composed of the initials of its three discoverers, Rivest, Shamir, and Adle-
man, who published the algorithm in 1978 [RSA]. (Gardner quoted it in 1977
[GardRSA].)
The RSA method is based on a mathematically 'hard' problem, namely factor-
ing very large numbers (currently 300 decimal places and more). The algorithm
is quickly described, but as so often in mathematics, it wouldn't explain how
they came by this idea. I will try to build such an idea in the following. What
we need is some number theory, but really very little.
Congruencies and Fermat's Little Theorem
You have been confronted with congruence arithmetic several times in this
topic. You know that two natural numbers,
a
and
b
, are called
congruent
