General Cryptanalytic Methods - Modern Cryptanalysis: Techniques for Advanced Code Breaking - page 132

Another method is to use mathematical properties to determine the values of a, c, m, for the standard linear
congruential method:
For example, if three consecutively generated values of X can be discovered (say, A, B, C ), then it is fairly
straightforward to solve the system of equations:
Here, we have two equations and two unknowns (assuming m is known). If we subtract the second equation
from the first (i.e., subtract the sides from the corresponding size), we obtain the relation
If we knew that m was a prime, then we could multiply ( C − B ) by the inverse of ( B − A) (modulo m ), and
obtain a . We can then compute C = B − a × A and check to make sure that c = C − a × B.
If m is not prime, or if we do not know m at all, then there are other fast methods to find all of the parameters
(see References [3] and [11]).
5.7 Summary
The methods described in this chapter, for the most part, are not successful with only one cipher or type of
cipher. I don't delve into the depths of how each cipher works, for example, to use rainbow tables. The tech-
niques are nearly identical for any cipher.
Random number generators can also play an important part in cryptanalysis; thus, a brief example was given
to show sample cryptanalysis of this. For more on cryptographic uses of random number generators, see Refer-
ence [12].
In the next two chapters, I am going to discuss several methods that do rely heavily on the internal structure
of individual ciphers. While the general principles of the attacks are the same, every attack will have to be
uniquely constructed to fit the properties of the cipher.
Exercises
Exercise 1. Can the meet-in-the-middle attack be extended to a normal cryptoscheme? For example, could we
use this to reduce the amount of computation required to brute-force DES down from 2 56 by trading space in a
similar way? Why or why not?
Exercise 2. Write an implementation of a rainbow table attack against the Microsoft LAN Manager password-
hashing scheme.
Exercise 3. Since the round functions of the Easy1 cipher are identical, attempt to mount a slide attack on, say,
a 20-round version of this cipher.