Another item of interest, although the sequence it generates is not cryptosecure, is a pseudorandom number generator that has generated a great deal of excitement in the scientific world, the Mersenne Twister. It is essentially a large linear-feedback shift register, and thus its output has the same general weaknesses from the viewpoint of cryptosecurity; however, the output has excellent statistical properties, and given that and its long period, it is useful as a basic component within a stream cipher.
First described in a paper by Makoto Matsumoto and Takuji Nishimura published in 1998, and available on the web site of one of the authors, this random number generator has a period of 2^19937-1, and its output is free of long-term correlations when considered from a viewpoint of 623 dimensions. In comparison, when even a two-dimensional plot is used of the successive members of pairs of numbers produced by a conventional linear congruential pseudorandom number generator, obvious patterns are visible.
The algorithm operates on a seed value which is 19,937 bits long; this value is stored in an array with 624 elements which contain 32-bit values. There are 31 unused bits in the array, which migrate through the array as the next seed is calculated, so no single array element can be replaced with a one-bit storage cell. It is based on the fact that 2^19937-1 is a prime number (and, as it is one less than a power of two, it is also a Mersenne prime). As noted in the main page on ciphers based on shift registers, if a shift register has a number of cells which correspond to the exponent for a Mersenne prime, the process of testing that shift register for maximum period is simplified. A more advanced simplification of this testing process, known as the inversive decimation method, is used to permit the construction of a maximum-period shift register of the particular form dealt with here. It was the development of this method by the developers of the Mersenne Twister that made the creation of such a large maximum-period shift register possible.
The algorithm has two distinct phases; the recurrence which changes one 19,937-bit state to its successor, and the procedure for extracting multiple 32-bit values from that state.
The state succession algorithm is a kind of shift register:
for i = 0 to 623
temp = first bit of a(i) followed by last 31 bits of a(i+1) ;
a(i) = temp shifted right one bit xor
X'9908B0DF' if temp is odd xor
a(i+397) ;
next i
where all subscripts of a are modulo 624; thus, in practical implementations, the loop is broken into three pieces, one break occuring when i+397 falls off the end of the array, and one break before the last iteration, where i+1 falls off the end of the array.
Thus, a practical implementation looks like this, and several implementations in C are available on the Internet:
for i = 0 to 226
temp = first bit of a(i) followed by last 31 bits of a(i+1) ;
a(i) = temp shifted right one bit xor
X'9908B0DF' if temp is odd xor
a(i+397) ;
next i
for i = 227 to 622
temp = first bit of a(i) followed by last 31 bits of a(i+1) ;
a(i) = temp shifted right one bit xor
X'9908B0DF' if temp is odd xor
a(i-227) ;
next i
temp = first bit of a(623) followed by last 31 bits of a(0) ;
a(i) = temp shifted right one bit xor
X'9908B0DF' if temp is odd xor
a(396) ;
This particular Mersenne Twister belongs to a parameterized family of generators, whose parameters can be viewed as the following:
L = 19937 W = 32 M = 397 A = X'9908B0DF'
where W is the width in bits of the cells of the basic array, and L is the length in bits of the desired shift register, which has to be the exponent for a Mersenne prime; additional parameters can be derived from these:
N = floor( L/W ) + 1 R = L mod W
thus, after dividing L by W, R is the remainder, and N is one more than the integer quotient. These equations only apply when R is not zero, which is true in all but the trivial case for a prime N, and N must be prime to be a valid Mersenne exponent.
This makes the parametrizable code have the following appearance:
for i = 0 to N-M-1
temp = first R bits of x(i) followed by last W-R bits of x(i+1) ;
x(i) = temp shifted right one bit xor
A if temp is odd xor
x(i+M) ;
next i
for i = N-M to N-2
temp = first R bits of x(i) followed by last W-R bits of x(i+1) ;
x(i) = temp shifted right one bit xor
A if temp is odd xor
x(i+M-N) ;
next i
temp = first R bits of x(N-1) followed by last W-R bits of x(0) ;
x(N-1) = temp shifted right one bit xor
A if temp is odd xor
x(M-1) ;
and, indeed, the C implementations usually look like this, with bit masks with names like UM and LM (perhaps U and LL, or UPPER_MASK and LOWER_MASK) defined to obtain the upper R and the lower W-R bits of W-bit words, following the notation used in the original paper.
Note that the first step of the algorithm discards all but the first bit of a(0); thus, although the other bits of a(0) as calculated are used in the algorithm, the actual amount of information preserved from iteration to iteration is only 19937 bits (623*32 + 1). The second step discards all but the first bit of a(1), but the rest of a(1) was copied to a(0) by the first step. Thus, all 32 bits of all the elements of the array are needed, but the total information retained is 31 bits less than its total size.
The state succession algorithm of the Mersenne Twister can be depicted in an illustration as a kind of linear-feedback shift register:
It is clear from the diagram that we have a shift register with 19,937 cells which is wrapped around in 32 coils. At one point, a single bit is XORed with 14 other bits, as in the Galois configuration of a shift register; at another, 32 bits are XORed with 32 bits elsewhere, which can be thought of as being halfway between the conventional configuration, in which one bit is modified by being XORed with many other bits, and the Galois configuration, where many bits are modified by being XORed with the value of a single bit. Thus, the shift register, if converted to either standard representation, could be expected to have a large number of taps.
Also visible from the fact that this is an LFSR is the fact that one would wish to use only one bit per iteration. Since the diagram illustrates an arrangement that must be stepped 624 times to give the Mersenne Twister state succession function, this merely means that only one bit from each 32-bit output of the regular algorithm should be used. Of course, taking the 32-bit output, and using it as the input to a nonlinear function which gives a one-bit result would be simply following standard practice with linear-feedback shift registers, as we have seen in the preceding section.
Incidentally, because the algorithm is designed for convenience in extracting 32-bit values, with 624 iterations followed by taking all the bits of the internal state but one out in groups of 32, the most significant bits of the 32-bit values in the raw output produced in this fashion correspond to the output sequence of the underlying shift register with every 624th bit skipped.
The hexadecimal value 9908B0DF must have its leading bit equal to 1; the remaining bits are the variable parameter which makes this value the "magic number"; it is a value for this number which is searched for in order to obtain the maximum period for the generator.
The extraction function takes one value from elements 1 to 623 of the array in turn, and then subjects it to a transformation in order to spread randomness among its bits, giving the output a desired statistical property, k-distribution. If one takes only the first n bits of each 32 bit output, where n varies from 1 to 32, the intent of this is to ensure that the number k of consecutive n-bit values that can be taken such that all possible n-bit values for the next value are still equally likely (except for the small discrepancy common to all LFSRs that the all-zero state may never occur) is as high as possible:
temp = selected array element ;
temp = temp xor
temp shifted right 11 bits ;
temp = temp xor
((temp shifted left 7 bits) and X'9D2C5680') ;
temp = temp xor
((temp shifted left 15 bits) and X'EFC60000') ;
value = temp xor
temp shifted right 18 bits ;
and after a value was obtained from element 623, then the state succession transformation is used again.
This portion is also parameterized, since the tempering function is optimized to different Mersenne Twister arrangements; the four shifts are called U, S, T, and L in order (here, U=11, S=7, T=15, L=18) and the two values given in hexadecimal are called B and C; this type of parameterization allows different Mersenne Twister designs to be given in a compact tabular form.
The invention of the Mersenne Twister was preceded by the development, by the same inventors, of a related algorithm with an array of 25 rather than 624 elements, called TT800. This was a simpler algorithm; it is not simply a smaller Mersenne Twister, as the Mersenne Twister included additional innovations. In this algorithm, the state succession function is:
for i = 1 to 25
temp = a(i) ;
a(i) = temp shifted right one bit xor
X'8EBFD028' if temp is odd xor
a(i+7) ;
next i
The period here is 2^800 - 1. Originally, in a 1992 paper, the generator was proposed without tempering, and called T800. Then, in a 1994 paper, the tempering process used when values were extracted from the array was originally simpler for this method, including only half of the steps used for the later Mersenne Twister:
temp = selected array element ;
temp = temp xor
((temp shifted left 7 bits) and X'2B5B2500') ;
value = temp xor
((temp shifted left 15 bits) and X'DB8B0000') ;
and was subsequently, in the 1998 paper that also introduced the Mersenne Twister, improved to the following:
temp = selected array element ;
temp = temp xor
((temp shifted left 7 bits) and X'2B5B2500') ;
temp = temp xor
((temp shifted left 15 bits) and X'DB8B0000') ;
value = temp xor
temp shifted right 16 bits ;
so as to improve the less significant bits. The generator was named TT800 in both forms; the latter form, being the one provided in a routine available from an academic institution in Salzburg, is noted here as TT800S.
The paper on the Mersenne Twister also gave two versions with periods of 2^11213 - 1.
Their state transition is:
for i = 0 to 350
temp = first 13 bits of a(i) followed by last 19 bits of a(i+1) ;
a(i) = temp shifted right one bit xor
X'E4BD75F5' [or X'CCAB8EE7'] if temp is odd xor
a(i+175) ;
next i
and the practical form of this state transition function is:
for i = 0 to 175
temp = first 13 bits of a(i) followed by last 19 bits of a(i+1) ;
a(i) = temp shifted right one bit xor
X'E4BD75F5' [or X'CCAB8EE7'] if temp is odd xor
a(i+175) ;
next i
for i = 176 to 349
temp = first 13 bits of a(i) followed by last 19 bits of a(i+1) ;
a(i) = temp shifted right one bit xor
X'E4BD75F5' [or X'CCAB8EE7'] if temp is odd xor
a(i-176) ;
next i
temp = first 13 bits of a(350) followed by last 19 bits of a(0) ;
a(i) = temp shifted right one bit xor
X'E4BD75F5' [or X'CCAB8EE7'] if temp is odd xor
a(174) ;
and the extraction function, applied to elements 1 through 350 of the array, following precisely the pattern used for the regular Mersenne Twister, is:
temp = selected array element ;
temp = temp xor
temp shifted right 11 bits ;
temp = temp xor
((temp shifted left 7 bits) and X'655E5280' [or X'31B6AB00'] ) ;
temp = temp xor
((temp shifted left 15 bits) and X'FFD58000' [or X'FFE50000']) ;
value = temp xor
temp shifted right 17 bits ;
A subsequent paper, published in the year 2000, gave five additional forms of the Mersenne Twister with period 2^19937-1. All five were designed to be implemented with 64-bit arithmetic instead of 32-bit arithmetic. This allowed the effective number of taps in the shift register to be doubled; but in three of the forms, the number of taps was further increased by performing two extra simple XOR operations involving two additional words in the array; thus, the parameter M was replaced by three values, M(0), M(1), and M(2).
Those forms were not named in the paper; they are referred to here as MT19937A through MT19937E for ease of reference.
Thus, the three Mersenne Twister arrangements noted in the original paper, the four additional arrangements given in a subsequent paper, and several GFSR arrangements, including TT800, given in a previous paper, can all be given in parameter form in the following table:
Name length W N R M M(1) M(2) A U S T L B C MT19937 19937 32 624 1 397 -- -- X'9908B0DF' 11 7 15 18 X'9D2C5680' X'EFC60000' MT11231A 11231 32 351 13 175 -- -- X'E4BD75F5' 11 7 15 17 X'655E5280' X'FFD58000' MT11231B 11231 32 351 13 175 -- -- X'CCAB8EE7' 11 7 15 17 X'31B6AB00' X'FFE50000' TT400 400 16 25 -- 11 -- -- X'A875' -- 2 7 -- X'6A68' X'7500' TT403 403 31 13 -- 2 -- -- X'6B5ECCF6' -- 8 14 -- X'102D1200' X'66E50000' TT775 775 31 25 -- 8 -- -- X'6C6CB38C' -- 6 14 -- X'1ABD5900' X'776A0000' TT800 800 32 25 -- 7 -- -- X'8EBFD028' -- 7 15 -- X'2B5B2500' X'DB8B0000' TT800S 800 32 25 -- 7 -- -- X'8EBFD028' -- 7 15 16 X'2B5B2500' X'DB8B0000' T1600 1600 64 25 -- 3 -- -- X'B380C13AA838387E' MT19937A 19937 64 312 31 156 -- -- X'B5026F5AA96619E9' 29 17 37 41 X'D66B5EF5B4DA0000' X'FDED6BE000000000' MT19937B 19937 64 312 31 156 -- -- X'F6A3F020F058B7A7' 29 17 37 41 X'28AAF6CDBDB40000' X'FDEDEAE000000000' MT19937C 19937 64 312 31 63 151 224 X'B3815B624FC82E2F' 26 17 33 39 X'599CFCBFCA660000' X'FFFAAFFE00000000' MT19937D 19937 64 312 31 55 122 268 X'8EBD4AD46CB39A1E' 26 17 33 39 X'656BEDFFD9A40000' X'FDFECE7E00000000' MT19937E 19937 64 312 31 87 148 241 X'CACB98F78EBCD4ED' 26 17 33 39 X'A51DBEFFDA6C0000' X'FFEE9BF600000000'
If one is using the Mersenne Twister output as input to an additional stage of processing intended to achieve higher security, particularly if one is using either one bit, or all 32-bits, of each 32-bit output value, in most cases the extraction step above can be safely omitted (depending, of course, on the nature of the additional processing). On the other hand, it should definitely be retained if Mersenne Twister output is used to select array elements from a buffer for use in a MacLaren-Marsaglia algorithm.
Despite the fact that the Mersenne Twister is an extremely good pseudo-random number generator, it is not cryptographically secure by itself for a very simple reason. It is possible to determine all future states of the generator from the state the generator has at any given time, and either 624 32-bit outputs, or 19,937 one-bit outputs are sufficient to provide that state. Using a cryptographically-secure hash function, such as SHA-1, on the output of the Mersenne Twister has been recommended as one way of obtaining a keystream useful in cryptography.
Following some of the techniques seen on earlier pages of this section, I will outline here a rather speedier technique which will provide at least a modicum of security. Since the cause of insecurity is the visibility of the entire state, it is necessary to slow things down somewhat so that not all of the state will be visible.
Let us use both the full Mersenne Twister, known as MT19937, and the version with a period of 2^11213-1 using the second set of values shown above, known as MT11213B. When producing values with MT19937, we will take only the first bit of the 32 bits generated, and we will not use the tempering step. When producing values with MT11213B, we will use the tempering step, and then take the first eight bits of the 32 bits generated. (From the original paper, MT11213B has slightly better k-distribution properties than MT11213A.)
Generating a byte will involve the following steps:
One fills the 256-byte table by performing steps 1 through 3 repeatedly, and placing their successive results in the table.
Since 2^19937-1 and 2^11213-1 are both primes, and are different, they are relatively prime, and the period of the generator will be very long. Selecting irregularly half of the bits produced by the main generator prevents its state from being fully visible, and then using a MacLaren-Marsaglia type buffer makes it difficult to determine what bits contain what pieces of state information. Of course, the state of the other generator is also not readily apparent. Of course, if one has an enormous amount of keystream available (i.e., through known plaintext), one can simply take bits at intervals of repetitions of the period of the smaller generator to obtain bits from the main generator with a fixed relationship (although computing that relationship presents its own problems, it must be regarded as achievable). If keys are not regarded as outliving the period of the smaller generator, however, there are no obvious trivial attacks on this scheme. It might, however, be regarded as somewhat too simple to be genuinely secure.
Since the full 32-bit outputs of MT19937 can be regarded as widely separated parts of a single sequence, using the full output might be regarded as an entirely acceptable way to increase the speed of pseudorandom output generation. A faster procedure to generate pseudorandom 16-bit values could be as follows, this time using the tempering function for both generators:
This algorithm produces a 16-bit value using two calls to MT19937 and three calls to MT11213B, so it is relatively fast. However, the bits of that 16-bit value are each associated with only two possible sources in the 32-bit outputs of MT19937, and this may seem to be a weakness. In the first generator, however, the relationship between the bits is also approximately known, as successive first bit values, so the weakness may be illusory.
However, a more elaborate algorithm derived from the one above would seem to address these particular obvious concerns:
The use of a variable circular left shift might possibly conflict with a patent cited in the AES process, unfortunately; it is important here because it makes the sources of the bits considerably more uncertain.
Using two buffers and three successive masking decimation steps ensures that the initial 64 bits formed by two successive 32-bit values is reduced to 8 bits through the application of three values from MT11213B applied at widely separated and apparently random times.
This uses two calls to MT19937, and seven calls to MT11213B, to generate a pseudorandom byte. Ideally, of course, it would be desirable to replace the last five calls to MT11213B to calls to five other pseudorandom number generators, each one having a different period. Then, between steps 4 and 5 above, the value could also be XORed with the 16-bit output of yet another generator.
Even with all this elaboration, it should be noted that in general there is much less confidence placed in fast stream cipher methods than in the standard, if slow, block ciphers. Many of the simpler stream cipher schemes which have shift registers or linear congruential PRNGs at their base have been broken.
As noted on a previous page, the standard method of testing if a linear feedback shift register has maximum period is by first determining that it does, in fact, return to its initial state at the end of that period, and then establishing that it does not return to its initial state after any shorter period which is not a factor of the maximum period.
The maximum period of an LFSR is always one less than a power of two.
A prime number is a number which has no factors, except, of course, one (so one must also test that the generator actually changes state after a single step).
A prime number which is one less than a power of two is a Mersenne prime; hence, a shift register whose maximum period is a Mersenne prime is easier to test for maximum period. It is not so much the extra tests that are the problem as finding when to perform them by factoring the period when it is not a prime.
The same basic algorithm is used to run an LFSR for an enormous number of iterations as is used to raise numbers to large exponents when performing RSA; instead of thousands of repeated multiplications by the characteristic polynomial of the shift register, that polynomial can be squared, and the result squared, repeatedly.
The inversive decimation method achieves a modest, but important, increase in speed over the conventional method of testing an LFSR for maximum period; the time remains proportional to the length of the LFSR squared, but a factor proportional to the number of active taps on the LFSR is eliminated. This was sufficient to make testing the Mersenne Twister for maximum period practical.
An essential step in this method is the ability to invert the operation of the LFSR; given a stream of bits produced by the shift register, it is necessary to be able to determine the state which gave rise to it.
To make this easy, the bit which determines if the "magic number" A is XORed to the 32 bits of the array being processed is used as the output; thus, by knowing this output, one knows a very important piece of what is going on during the step that produced it.
Then, to run the shift register backwards, we begin by noting that the bottom row of bits will be output without modification. The bit at position M in that row will then modify the last bit in that row as it moves to the next higher row, while the bits in the output sequence will modify what other bits in the shift register will need to have been, through applying the XOR vector A.
The truly bizarre step in this algorithm is that, instead of squaring the polynomial of the shift register, one merely needs to take every second bit in its output sequence, and then obtain the state which would generate those bits. This unusual result is said to be a consequence of the fact that only XOR, rather than modular arithmetic with a higher modulus, is used.
Using the primitive polynomial
7 x +x+1
to provide an example of this astounding property of binary LSFRs, we see the following:
0000001 1 1 1000000 0 0100000 0 0 0010000 0 0001000 0 0 0000100 0 0000010 1 1 1000001 1 1100000 0 0 0110000 0 0011000 0 0 0001100 0 0000110 1 1 1000011 0 0100001 1 1001001 1 1010000 0 0101000 0 1100100 0 0010100 0 0001010 1 0110010 1 1000101 1 1100010 1 1011001 1 1110001 1 1111000 0 1101100 0 0111100 0 0011110 1 0110110 1 1001111 0 0100111 0 1011011 0 0010011 0 0001001 1 0101101 1 1000100 0 0100010 1 1010110 1
Starting the generator from 0000001, we then take seven bits of the output of the 'twice as fast' generator to derive the contents which the same generator would need to produce that sequence, and indeed the sequences continue to correspond with the same polynomial.
Squaring the sequence instead of the recurrence itself is what removes the dependence on the number of taps.
Many Mersenne primes are known; a list of them is available at this site, and it may also be noted that there is a relationship between the Mersenne primes and the perfect numbers.
The perfect numbers are those numbers which equal the sum of their proper divisors:
1 + 2 + 3 = 6 1 + 2 + 4 + 7 + 14 = 28
and it was proven by Euler that
n
when 2 - 1 is prime, then
(n-1) n
2 *(2 - 1) is perfect,
and, conversely, all even perfect numbers are generated by that rule. Odd perfect numbers may exist, but if so they must be very large and satisfy a number of stringent mathematical conditions.
Here is a list of the Mersenne primes now known:
Mersenne Primes Perfect Numbers 2 2 - 1 3 6 3 2 - 1 7 28 5 2 - 1 31 496 7 2 - 1 127 8,128 13 2 - 1 8,191 33,550,336 17 2 - 1 131,071 8,589,869,056 19 2 - 1 524,287 137,438,691,328 31 2 - 1 2,147,483,647 61 2 - 1 2,305,843,009,213,693,952 89 2 - 1 618,970,019,642,690,137,449,562,112 107 2 - 1 162,259,276,829,213,363,391,578,010,288,127 127 2 - 1 170,141,183,460,469,231,731,687,303,715,884,105,727 521 2 - 1 607 2 - 1 1,279 2 - 1 2,203 2 - 1 2,281 2 - 1 3,217 2 - 1 4,253 2 - 1 4,423 2 - 1 9,689 2 - 1 9,941 2 - 1 11,213 2 - 1 19,937 2 - 1 21,701 2 - 1 23,209 2 - 1 44,497 2 - 1 86,243 2 - 1 110,503 2 - 1 132,049 2 - 1 216,091 2 - 1 756,839 2 - 1 859,433 2 - 1 1,257,787 2 - 1 1,398,269 2 - 1 2,976,221 2 - 1 3,021,377 2 - 1 6,972,593 2 - 1 13,466,917 2 - 1 20,996,011 2 - 1 24,036,583 2 - 1 25,964,951 2 - 1 30,402,457 2 - 1 32,582,657 2 -1 37,156,667 2 -1 42,643,801 2 -1 43,112,609 2 -1 57,885,161 2 -1 74,207,281 2 -1 77,232,917 2 -1 82,589,933 2 -1 136,279,841 2 -1
Usually, when you see a news item about the discovery of the largest known prime number, it will be a Mersenne prime.
Note that
11,213 2 - 1
the smaller of the two primes used for Mersenne Twister examples shown here, was the one whose discovery was proudly proclaimed on the postage meters of the University of Illinois, as noted in Martin Gardner's Mathematical Games column in Scientific American. In 1963, this was the largest prime number known.
The next one after the one used in the Mersenne Twister,
21,701 2 - 1
caught the public's fancy, because its discoverers were then a pair of high school students, one of whom then discovered the next one on the list, and later, as an adult, discovered the largest non-Mersenne prime known at the time, and until when this page was originally written. A larger non-Mersenne prime has since been discovered.
In 1985, the largest prime number known was
216,091 2 - 1
and this was reported on the news as well. There may be other undiscovered Mersenne primes below 2^30,402,457-1 and between the later entries on the list above.
The Mersenne prime 2^24,036,583-1 was discovered on May 15th, 2004, also through the Great Internet Mersenne Prime Search, and 2^25,964,951-1 was discovered on February 18, 2005.
The first of the Mersenne primes to be discovered by computer were 2^521-1, 2^607-1, 2^1279-1, 2^2203-1, and 2^2281-1, all discovered by Raphael M. Robinson on the Standards Western Automatic Computer (SWAC) a computer with a small Williams Tube random-access memory and a larger auxilliary memory on a magnetic drum. A similar machine, but with a Williams Tube memory of twice the size (512 words instead of 256), the BESK, was used in Sweden by Hans Riesel to discover the next Mersenne prime, 2^3217-1.
Next
Chapter Start
Skip to Next Chapter
Table of Contents
Home Page