David Wong

cryptologie.net

cryptography, security, and random thoughts

Hey! I'm David, cofounder of zkSecurity, research advisor at Archetype, and author of the Real-World Cryptography book. I was previously a cryptography architect of Mina at O(1) Labs, the security lead for Libra/Diem at Facebook, and a security engineer at the Cryptography Services of NCC Group. Welcome to my blog about cryptography, security, and other related topics.

← back to all posts

How does the Mersenne's Twister work?

blog

Someone asked that question on reddit, and so I replied with a high level answer that should provide a clear enough view of the algorithm:

From a high level, here’s what a PRNG is supposed to look like:

prng

you start with a seed (if you re-use the same seed you will obtain the same random numbers), you initialize it into a state. Then, every time you want to obtain a random number, you transform that state with a one-way function \(g\). This is because you don’t want people to find out the state out of the random output.

You want another random number? You first transform the state with a one way function \(f\): this is because you don’t want people who found out the state to be able to retrieve past states (forward secrecy). And then you use your function \(g\) again to output a random number.

Mersenne Twister (MT) is like that, except:

  • your first state is not used to output any random numbers
  • a state allows you to output not only one, but 624 random numbers (although this could be thought as one big random number)
  • the \(g\) function is reversible, it’s not a one-way function, so MT it is not a cryptographically secure PRNG.

With more details, here’s what MT looks like:

mersenne twister

the \(f\) function is called “twist”, the \(g\) function is called “temper”. You can find out how each functions work by looking at the working code on the wikipedia page of MT.

← back to all posts blog • 2016-02-08
currently reading:
How does the Mersenne's Twister work?
02-08 blog
📖 my book
Real-World Cryptography is available from Manning Publications.
A practical guide to applied cryptography for developers and security professionals.
🎙️ my podcast
Two And A Half Coins on Spotify.
Discussing cryptocurrencies, databases, banking, and distributed systems.
📺 my youtube
Cryptography videos on YouTube.
Video explanations of cryptographic concepts and security topics.