Cryptopals 21 - Implement the MT19937 Mersenne Twister RNG

TL;DR

Challenge 21 in Cryptopals.

This challenge is one of those drills that teach me modesty the hard way. There’s the pseudocode in the Wikipedia page, it’s correct and all, and yet I managed to fail it multiple times for not reading it properly.

It served me right!

One thing that is always handy to have in this these occasions is some reference outputs to compare with. It is strange that nothing appears in the Wikipedia page, not even a reference to OEIS A221557 a.k.a. Consecutive values produced by the C++ mt19937 (Mersenne twister) random number generator with the default seed (5489).:

3499211612, 581869302, 3890346734, 3586334585, 545404204, ...

If we get these first values right we’re OK.

Fun fact: the OEIS A221557 page also includes the C++ code generating the values above (I’m adding a little extra main, to make it compile and run right off the bat):

#include <iostream>
#include <random>
void A221557(int max)
{
  std::mt19937 gen;
  for (int i = 1; i <= max; ++i)
    std::cout << i << ' ' << gen() << '\n';
}
int main (int argc, char *argv[]) {
   int max = 5;
   if (argc > 1)
      max = std::stoi(argv[1]);
   A221557(max);
}

I know, I should not be using the if-without-curly-braces idiom, but I like to live dangerously in my write-and-ditch experiments. So much for wishing to stay safe and secure! uh?!?

Enough for digressions, without further ado, here’s my Perl implementation:

#!/usr/bin/env perl
use v5.24;
use warnings;
use experimental 'signatures';
no warnings 'experimental::signatures';

my $mt = mt19937_factory();

say $mt->() for 1 .. 20;

sub mersenne_twister_factory (%args) {
   my ($w, $n, $m, $r, $a, $u, $d, $s, $b, $t, $c, $l, $f, $seed) =
     @args{qw< w n m r a u d s b t c l f seed >};

   my $lower_mask = 0;
   $lower_mask = ($lower_mask << 1) | 1 for 1 .. $r;

   my $wmask = $lower_mask;
   $wmask = ($wmask << 1) | 1 for ($r + 1) .. $w;

   my $upper_mask = $wmask ^ $lower_mask;

   # initialization
   my @MT = $seed &= $wmask;
   push @MT, $seed = ($_ + $f * ($seed ^ ($seed >> ($w - 2)))) & $wmask
     for 1 .. $n - 1;

   my $index = $n;
   return sub {
      if ($index == $n) {    # twist
         for my $i (0 .. $n - 1) {
            my $x =
              ($MT[$i] & $upper_mask) + ($MT[($i + 1) % $n] & $lower_mask);
            my $xA = $x >> 1;
            $xA ^= $a if $x & 0x01;
            $MT[$i] = $MT[($i + $m) % $n] ^ $xA;
         }
         $index = 0;
      } ## end if ($index == $n)

      my $y = $MT[$index];
      $y = $y ^ (($y >> $u) & $d);
      $y = $y ^ (($y << $s) & $b);
      $y = $y ^ (($y << $t) & $c);
      $y = $y ^ ($y >> $l);
      ++$index;

      return $y & $wmask;
   };
} ## end sub mersenne_twister_factory (%args)

sub mt19937_factory ($seed = 5489) {
   mersenne_twister_factory(
      w    => 32,
      n    => 624,
      m    => 397,
      r    => 31,
      a    => 0x9908B0DF,
      u    => 11,
      d    => 0xFFFFFFFF,
      s    => 7,
      b    => 0x9D2C5680,
      t    => 15,
      c    => 0xEFC60000,
      l    => 18,
      f    => 1812433253,
      seed => $seed,
   );
} ## end sub mt19937_factory ($seed = 5489)

The mt19937_factory gives back an iterator, i.e. a sub that will give us the next value at each call.

It’s probably clear at this point that I coded this during the heath wave, so my lazyness was out of scale. I mean, I’m assuming that there will be more than 32 bits in integers, which I’m lucky enough to have in my virtual machine, but it’s still a bold assumption. Whatever, I already coded assuming only 16-bits architectures and there’s Math::BigInt for something more professional.

Stay safe and secure!

ETOOBUSY 🚀 minimal blogging for the impatient