Number Theoretical Ciphers - Modern Cryptanalysis: Techniques for Advanced Code Breaking - page 37

There are algorithms to keep track of these successive multiplications and combinations as you go down the
Euclidean algorithm so that you don't have to “run backward” through it. Such an algorithm, used to calculate
inverses modulo p, is called an extended Euclidean algorithm.
Cohen [2] gives one such algorithm (his Algorithm 1.3.6). This iterative algorithm takes just a few steps
(note that x means to convert x to an integer by rounding down, throwing away any fractional part).
Extended Euclidean Algorithm. For the following, assume that we are computing the GCD of two num-
bers, a and b. The output of the algorithm is three integers: u, v, and d , such that d is the GCD of a and b , and u
and v satisfy au + bv = d .
1. Set u ← 1and d ← 0.
2. If b = 0, then set υ ← 0 and stop.
3. Set υ 1 ← 0 and υ 3 ← b.
4. If υ 3 = 0, then set υ ← ( d - a × u ) ÷ b and stop.
5. Set q ← d / υ 3 and t 3 ← d mod υ 3 .
6. Set t 1 ← u - qυ 1 , u ← υ 1 , υ 1 ← t 1 , υ 3 ← t 3 .
7. Go to Step 4.
The proof that this algorithm correctly computes the desired numbers can be found in Reference [2].
Finite fields are used quite often throughout cryptography. For example, Rijndael [3] (the algorithm that
makes up the Advanced Encryption Standard, AES) uses finite field arithmetic for some of its calculations. In
fact, Neal Koblitz has an entire topic devoted to the connections between algebra and cryptography [5].
Nowthat wehavesomemathematics underourbelt, let'sreview somecryptographic schemes basedonthese
principles.
2.4 Factoring-Based Cryptography
One very popular problem to use as the basis for cryptography is the factoring problem: Given an arbitrary
(and typically very large) number n, it is very difficult to calculate all of its prime factors in a reasonable amount
of time. The difficulty typically increases as the number of prime factors shrinks, reaching the most difficult
case when n is the product of two large primes. Several cryptosystems are based on the current knowledge that
there is no very good algorithm to calculate these prime numbers easily.
2.4.1 The RSA Algorithm
The RSAalgorithm, firstpublishedinthe1970sbyRonaldRivest,AdiShamir,andLeonardAdleman,remains
the most popular algorithm currently in use whose security is based on the factoring problem.
Specifically, RSA is based on a particular assumption. First, assume p and q to be very large prime numbers
(many hundreds of digits long). If we let n = pq be their product, then we assume that, knowing n, it is very
difficul to derive p and q . The larger the values of p and q , theoretically, the more difficult it is to factor n.
The trick is to use some number theory principles to form a way to encode information using these numbers.
RSA works by the following method:
1. Let n = pq , where p and q are two distinct, large prime numbers.