Cryptography Reference
In-Depth Information
complexity of the three algorithm families grows roughly with the cube bit length.
As an example, increasing the bit length from 1024 to 3076 in a given RSA signature
generation software results in an execution that is 3 3 = 27 times slower! On modern
PCs, execution times in the range of several 10 msec to a few 100 msec are common,
which does not pose a problem for many applications. However, public-key perfor-
mance can be a more serious bottleneck in constrained devices where small CPUs
are prevalent, e.g., mobile phones or smart cards, or on network servers that have
to compute many public-key operations per second. Chaps. 7, 8 and 9 introduce
several techniques for implementing public-key algorithms reasonably efficiently.
6.3 Essential Number Theory for Public-Key Algorithms
We will now study a few techniques from number theory which are essential for
public-key cryptography. We introduce the Euclidean algorithm, Euler's phi func-
tion as well as Fermat's Little Theorem and Euler's theorem. All are important for
asymmetric algorithms, especially for understanding the RSA crypto scheme.
6.3.1 Euclidean Algorithm
We start with the problem of computing the greatest common divisor (gcd) . The gcd
of two positive integers r 0 and r 1 is denoted by
gcd( r 0 , r 1 )
and is the largest positive number that divides both r 0 and r 1 . For instance gcd(21 , 9)=
3. For small numbers, the gcd is easy to calculate by factoring both numbers and
finding the highest common factor.
Example 6.1. Let r 0 = 84 and r 1 = 30. Factoring yields
r 0 = 84 = 2
·
2
·
3
·
7
r 1 = 30 = 2
·
3
·
5
The gcd is the product of all common prime factors:
2
·
3 = 6 = gcd(30 , 84)
For the large numbers which occur in public-key schemes, however, factoring
often is not possible, and a more efficient algorithm is used for gcd computations, the
Euclidean algorithm. The algorithm, which is also referred to as Euclid's algorithm,
is based on the simple observation that
Search WWH ::




Custom Search