Crypto++  8.4
Free C++ class library of cryptographic schemes
mersenne.h
Go to the documentation of this file.
1 // mersenne.h - written and placed in public domain by Jeffrey Walton.
2 
3 /// \file mersenne.h
4 /// \brief Class file for Mersenne Twister
5 /// \warning MersenneTwister is suitable for Monte-Carlo simulations, where uniformaly distrubuted
6 /// numbers are required quickly. It should not be used for cryptographic purposes.
7 /// \since Crypto++ 5.6.3
8 #ifndef CRYPTOPP_MERSENNE_TWISTER_H
9 #define CRYPTOPP_MERSENNE_TWISTER_H
10 
11 #include "cryptlib.h"
12 #include "secblock.h"
13 #include "misc.h"
14 
15 NAMESPACE_BEGIN(CryptoPP)
16 
17 /// \brief Mersenne Twister class for Monte-Carlo simulations
18 /// \tparam K Magic constant
19 /// \tparam M Period parameter
20 /// \tparam N Size of the state vector
21 /// \tparam F Multiplier constant
22 /// \tparam S Initial seed
23 /// \details Provides the MersenneTwister implementation. The class is a header-only implementation.
24 /// \details You should reseed the generator after a fork() to avoid multiple generators
25 /// with the same internal state.
26 /// \warning MersenneTwister is suitable for simulations, where uniformaly distrubuted numbers are
27 /// required quickly. It should not be used for cryptographic purposes.
28 /// \sa MT19937, MT19937ar
29 /// \since Crypto++ 5.6.3
30 template <unsigned int K, unsigned int M, unsigned int N, unsigned int F, word32 S>
32 {
33 public:
34  CRYPTOPP_STATIC_CONSTEXPR const char* StaticAlgorithmName() { return (S==5489 ? "MT19937ar" : (S==4537 ? "MT19937" : "MT19937x")); }
35 
36  ~MersenneTwister() {}
37 
38  /// \brief Construct a Mersenne Twister
39  /// \param seed 32-bit seed
40  /// \details Defaults to template parameter S due to changing algorithm
41  /// parameters over time
42  MersenneTwister(word32 seed = S) : m_seed(seed), m_idx(N)
43  {
44  Reset(seed);
45  }
46 
47  bool CanIncorporateEntropy() const {return true;}
48 
49  /// \brief Update RNG state with additional unpredictable values
50  /// \param input the entropy to add to the generator
51  /// \param length the size of the input buffer
52  /// \details MersenneTwister uses the first 32-bits of <tt>input</tt> to reseed the
53  /// generator. If fewer bytes are provided, then the seed is padded with 0's.
54  void IncorporateEntropy(const byte *input, size_t length)
55  {
56  word32 temp = 0;
57  ::memcpy(&temp, input, STDMIN(sizeof(temp), length));
58  Reset(temp);
59 
60  // Wipe temp
61  SecureWipeArray(&temp, 1);
62  }
63 
64  /// \brief Generate random array of bytes
65  /// \param output byte buffer
66  /// \param size length of the buffer, in bytes
67  /// \details Bytes are written to output in big endian order. If output length
68  /// is not a multiple of word32, then unused bytes are not accumulated for subsequent
69  /// calls to GenerateBlock. Rather, the unused tail bytes are discarded, and the
70  /// stream is continued at the next word32 boundary from the state array.
71  void GenerateBlock(byte *output, size_t size)
72  {
73  // Handle word32 size blocks
74  word32 temp;
75  for (size_t i=0; i < size/4; i++, output += 4)
76  {
77  temp = NextMersenneWord();
78  memcpy(output, &temp, 4);
79  }
80 
81  // No tail bytes
82  if (size%4 == 0)
83  {
84  // Wipe temp
85  SecureWipeArray(&temp, 1);
86  return;
87  }
88 
89  // Handle tail bytes
90  temp = NextMersenneWord();
91  switch (size%4)
92  {
93  case 3: output[2] = CRYPTOPP_GET_BYTE_AS_BYTE(temp, 1); /* fall through */
94  case 2: output[1] = CRYPTOPP_GET_BYTE_AS_BYTE(temp, 2); /* fall through */
95  case 1: output[0] = CRYPTOPP_GET_BYTE_AS_BYTE(temp, 3); break;
96 
97  default: CRYPTOPP_ASSERT(0); ;
98  }
99 
100  // Wipe temp
101  SecureWipeArray(&temp, 1);
102  }
103 
104  /// \brief Generate a random 32-bit word in the range min to max, inclusive
105  /// \return random 32-bit word in the range min to max, inclusive
106  /// \details If the 32-bit candidate is not within the range, then it is discarded
107  /// and a new candidate is used.
108  word32 GenerateWord32(word32 min=0, word32 max=0xffffffffL)
109  {
110  const word32 range = max-min;
111  if (range == 0xffffffffL)
112  return NextMersenneWord();
113 
114  const int maxBits = BitPrecision(range);
115  word32 value;
116 
117  do{
118  value = Crop(NextMersenneWord(), maxBits);
119  } while (value > range);
120 
121  return value+min;
122  }
123 
124  /// \brief Generate and discard n bytes
125  /// \param n the number of bytes to discard, rounded up to a <tt>word32</tt> size
126  /// \details If n is not a multiple of <tt>word32</tt>, then unused bytes are
127  /// not accumulated for subsequent calls to GenerateBlock. Rather, the unused
128  /// tail bytes are discarded, and the stream is continued at the next
129  /// <tt>word32</tt> boundary from the state array.
130  void DiscardBytes(size_t n)
131  {
132  for(size_t i=0; i < RoundUpToMultipleOf(n, 4U); i++)
133  NextMersenneWord();
134  }
135 
136 protected:
137 
138  void Reset(word32 seed)
139  {
140  m_seed = seed;
141  m_idx = N;
142 
143  m_state[0] = seed;
144  for (unsigned int i = 1; i < N+1; i++)
145  m_state[i] = word32(F * (m_state[i-1] ^ (m_state[i-1] >> 30)) + i);
146  }
147 
148  /// \brief Returns the next 32-bit word from the state array
149  /// \return the next 32-bit word from the state array
150  /// \details fetches the next word frm the state array, performs bit operations on
151  /// it, and then returns the value to the caller.
152  word32 NextMersenneWord()
153  {
154  if (m_idx >= N) { Twist(); }
155 
156  word32 temp = m_state[m_idx++];
157 
158  temp ^= (temp >> 11);
159  temp ^= (temp << 7) & 0x9D2C5680; // 0x9D2C5680 (2636928640)
160  temp ^= (temp << 15) & 0xEFC60000; // 0xEFC60000 (4022730752)
161 
162  return temp ^ (temp >> 18);
163  }
164 
165  /// \brief Performs the twist operaton on the state array
166  void Twist()
167  {
168  static const word32 magic[2]={0x0UL, K};
169  word32 kk, temp;
170 
171  CRYPTOPP_ASSERT(N >= M);
172  for (kk=0;kk<N-M;kk++)
173  {
174  temp = (m_state[kk] & 0x80000000)|(m_state[kk+1] & 0x7FFFFFFF);
175  m_state[kk] = m_state[kk+M] ^ (temp >> 1) ^ magic[temp & 0x1UL];
176  }
177 
178  for (;kk<N-1;kk++)
179  {
180  temp = (m_state[kk] & 0x80000000)|(m_state[kk+1] & 0x7FFFFFFF);
181  m_state[kk] = m_state[kk+(M-N)] ^ (temp >> 1) ^ magic[temp & 0x1UL];
182  }
183 
184  temp = (m_state[N-1] & 0x80000000)|(m_state[0] & 0x7FFFFFFF);
185  m_state[N-1] = m_state[M-1] ^ (temp >> 1) ^ magic[temp & 0x1UL];
186 
187  // Reset index
188  m_idx = 0;
189 
190  // Wipe temp
191  SecureWipeArray(&temp, 1);
192  }
193 
194 private:
195 
196  /// \brief 32-bit word state array of size N
198  /// \brief the value used to seed the generator
199  word32 m_seed;
200  /// \brief the current index into the state array
201  word32 m_idx;
202 };
203 
204 /// \brief Original MT19937 generator provided in the ACM paper.
205 /// \details MT19937 uses 4537 as default initial seed.
206 /// \details You should reseed the generator after a fork() to avoid multiple generators
207 /// with the same internal state.
208 /// \sa MT19937ar, <A HREF="http://www.math.sci.hiroshima-u.ac.jp/~m-mat/MT/ARTICLES/mt.pdf">Mersenne twister:
209 /// a 623-dimensionally equidistributed uniform pseudo-random number generator</A>
210 /// \since Crypto++ 5.6.3
211 #if CRYPTOPP_DOXYGEN_PROCESSING
212 class MT19937 : public MersenneTwister<0x9908B0DF /*2567483615*/, 397, 624, 0x10DCD /*69069*/, 4537> {};
213 #else
214 typedef MersenneTwister<0x9908B0DF /*2567483615*/, 397, 624, 0x10DCD /*69069*/, 4537> MT19937;
215 #endif
216 
217 /// \brief Updated MT19937 generator adapted to provide an array for initialization.
218 /// \details MT19937 uses 5489 as default initial seed. Use this generator when interoperating with C++11's
219 /// mt19937 class.
220 /// \details You should reseed the generator after a fork() to avoid multiple generators
221 /// with the same internal state.
222 /// \sa MT19937, <A HREF="http://www.math.sci.hiroshima-u.ac.jp/~m-mat/MT/MT2002/emt19937ar.html">Mersenne Twister
223 /// with improved initialization</A>
224 /// \since Crypto++ 5.6.3
225 #if CRYPTOPP_DOXYGEN_PROCESSING
226 class MT19937ar : public MersenneTwister<0x9908B0DF /*2567483615*/, 397, 624, 0x6C078965 /*1812433253*/, 5489> {};
227 #else
228 typedef MersenneTwister<0x9908B0DF /*2567483615*/, 397, 624, 0x6C078965 /*1812433253*/, 5489> MT19937ar;
229 #endif
230 
231 NAMESPACE_END
232 
233 #endif // CRYPTOPP_MERSENNE_TWISTER_H
SecureWipeArray
void SecureWipeArray(T *buf, size_t n)
Sets each element of an array to 0.
Definition: misc.h:1470
RoundUpToMultipleOf
T1 RoundUpToMultipleOf(const T1 &n, const T2 &m)
Rounds a value up to a multiple of a second value.
Definition: misc.h:1154
MT19937ar
Updated MT19937 generator adapted to provide an array for initialization.
Definition: mersenne.h:226
secblock.h
Classes and functions for secure memory allocations.
CRYPTOPP_ASSERT
#define CRYPTOPP_ASSERT(exp)
Debugging and diagnostic assertion.
Definition: trap.h:68
MersenneTwister::MersenneTwister
MersenneTwister(word32 seed=S)
Construct a Mersenne Twister.
Definition: mersenne.h:42
MersenneTwister::CanIncorporateEntropy
bool CanIncorporateEntropy() const
Determines if a generator can accept additional entropy.
Definition: mersenne.h:47
word32
unsigned int word32
32-bit unsigned datatype
Definition: config_int.h:62
MersenneTwister::DiscardBytes
void DiscardBytes(size_t n)
Generate and discard n bytes.
Definition: mersenne.h:130
RandomNumberGenerator
Interface for random number generators.
Definition: cryptlib.h:1418
MersenneTwister
Mersenne Twister class for Monte-Carlo simulations.
Definition: mersenne.h:32
misc.h
Utility functions for the Crypto++ library.
MT19937
Original MT19937 generator provided in the ACM paper.
Definition: mersenne.h:212
STDMIN
const T & STDMIN(const T &a, const T &b)
Replacement function for std::min.
Definition: misc.h:635
BitPrecision
unsigned int BitPrecision(const T &value)
Returns the number of bits required for a value.
Definition: misc.h:822
FixedSizeSecBlock< word32, N+1 >
MersenneTwister::GenerateBlock
void GenerateBlock(byte *output, size_t size)
Generate random array of bytes.
Definition: mersenne.h:71
Crop
T Crop(T value, size_t bits)
Truncates the value to the specified number of bits.
Definition: misc.h:906
CryptoPP
Crypto++ library namespace.
MersenneTwister::GenerateWord32
word32 GenerateWord32(word32 min=0, word32 max=0xffffffffL)
Generate a random 32-bit word in the range min to max, inclusive.
Definition: mersenne.h:108
cryptlib.h
Abstract base classes that provide a uniform interface to this library.
MersenneTwister::IncorporateEntropy
void IncorporateEntropy(const byte *input, size_t length)
Update RNG state with additional unpredictable values.
Definition: mersenne.h:54