mersenne twister

[Bevan Weiss]

I'm trying to find some information on how the mersenne twister pseudo
random number generator would be implemented in hardware. So far the only
descriptions I can find for the algorithm relate to 32bit (or more) software
operations.

If anyone has any information on how I might go about such an implementation
or any links on where I might be able to get more information on how to
perform such an implementation it would be greatly appreciated.

Thanks,
Bevan Weiss

 

[Max]

On Fri, 5 Mar 2004 00:29:01 +1300, Bevan Weiss wrote:

I'm trying to find some information on how the mersenne twister pseudo
random number generator would be implemented in hardware. So far the only
descriptions I can find for the algorithm relate to 32bit (or more) software
operations.

Why do you particularly want to use a Mersenne Twister? It's fast, and
it has a long period, but other RNGs might be more suitable for your
application. MT is patented, as well, though it's currently freely
licensed for commercial use.

I wouldn't want to try to convert it to use less than 32-bit
operations though, since you're inevitably going to lose a great deal
of the performance that presumably caused you to choose it in the
first place. What would be the period of a 16-bit implementation, for
instance?

If anyone has any information on how I might go about such an implementation
or any links on where I might be able to get more information on how to
perform such an implementation it would be greatly appreciated.

Here's the MT inventor's home page, if it helps:
http://www.math.keio.ac.jp/~matumoto/emt.html

--
Max

 

[Michael Chan]

Have a look at the document accessed from here:
http://innovexpo.itee.uq.edu.au/2003/exhibits/s354025/

On page 96, the hardware for the TT800 RNG is described, which is
essentially a smaller version of the mersenne twister.

"Bevan Weiss" <kaizen__@NOSPAMhotmail.com> wrote in message
news:aqE1c.1764$Nc3.27111@news.xtra.co.nz...

I'm trying to find some information on how the mersenne twister pseudo
random number generator would be implemented in hardware. So far the only
descriptions I can find for the algorithm relate to 32bit (or more)
software
operations.

If anyone has any information on how I might go about such an
implementation
or any links on where I might be able to get more information on how to
perform such an implementation it would be greatly appreciated.

Thanks,
Bevan Weiss

 

[Max]

On Thu, 4 Mar 2004 17:34:25 +0000 (UTC), Max wrote:

I wouldn't want to try to convert it to use less than 32-bit
operations though, since you're inevitably going to lose a great deal
of the performance that presumably caused you to choose it in the
first place. What would be the period of a 16-bit implementation, for
instance?

D'oh! Brain fade ((

MT essentially operates on a single 19937-bit number, so the period
will remain the same irrespective of how that number is stored in
hardware. Using other than 32-bit words would make the logic very
awkward and slow to implement, however.

What's the problem with using 32-bit wide registers, anyway?

--
Max

 

[Bevan Weiss]

"Max" <mtj2@btopenworld.com> wrote in message
news:af0g401l1him14b1a9sadnq7n7229fk6p3@4ax.com...

On Thu, 4 Mar 2004 17:34:25 +0000 (UTC), Max wrote:

I wouldn't want to try to convert it to use less than 32-bit
operations though, since you're inevitably going to lose a great deal
of the performance that presumably caused you to choose it in the
first place. What would be the period of a 16-bit implementation, for
instance?

D'oh! Brain fade ((

MT essentially operates on a single 19937-bit number, so the period
will remain the same irrespective of how that number is stored in
hardware. Using other than 32-bit words would make the logic very
awkward and slow to implement, however.

What's the problem with using 32-bit wide registers, anyway?

--
Max

I'm after a PRBS so it just seems a bit awkward to go from a twisted
generalised shift register (TGSFR) type algorithm (which the mersenne
twister is based on) to a 32bit register type approach (as all the software
processes use) only to have to go back to a shift register type arrangement
at the output to get back into a serial stream.

My desire would be for a feedback shift register type implementation (which
is easily and efficiently done in an fpga or a cpld)

It's for a type of cryptology application. I want to use the output to
simply encrypt some bitstream, using a simple XOR gate. Decryption would
then be exactly the same process, just XOR the encrypted stream with the
same PRBS to get back the original data.

I actually want to expand the operation so that it performs it on a single
19937bit shift register as opposed to many 32bit registers.

 

[Bevan Weiss]

"Max" <mtj2@btopenworld.com> wrote in message
news:3eeg4057v3c12078lt0dgpnfenfbs1mn1v@4ax.com...

On Fri, 5 Mar 2004 19:09:12 +1300, Bevan Weiss wrote:

I'm after a PRBS so it just seems a bit awkward to go from a twisted
generalised shift register (TGSFR) type algorithm (which the mersenne
twister is based on) to a 32bit register type approach (as all the
software
processes use) only to have to go back to a shift register type
arrangement
at the output to get back into a serial stream.

My desire would be for a feedback shift register type implementation
(which
is easily and efficiently done in an fpga or a cpld)

The problem there is that the MT is specifically designed to be
efficiently implemented in software on a 32-bit CPU (as is it's little
brother, TT800). This gives the general idea:
http://choices.cs.uiuc.edu/~akapadia/project2/node10.html

It's for a type of cryptology application. I want to use the output to
simply encrypt some bitstream, using a simple XOR gate. Decryption would
then be exactly the same process, just XOR the encrypted stream with the
same PRBS to get back the original data.

Ouch! MT is definitely not suitable for cryptographic use as it
stands, and the sort of system you propose would be straightforward to
break with differential cryptanalysis. It's intended for Monte-Carlo
simulations only.

The MT inventor's page I linked before highlights this (near the top
of the page):
http://www.math.keio.ac.jp/~matumoto/emt.html
You could run the output from the MT through a trapdoor hash such as
MD5 to secure the cyphertext, but there would still be potentially
crucial weaknesses in key exchange, if you're not very careful.

Why not use an existing cryptosystem which is known to be secure?
There's a variety to choose from, and many are designed to be easy to
implement in hardware. How about triple-DES, for example? Or even
straight DES (with CBC) if your security needs are not quite so
stringent?

Rolling your own cryptosystem is rarely a good idea, unless you're a
specialist in the field - and even they can get it wrong. For a
general discussion of this, Phil Zimmerman's background documentation
for PGP is worth reading. He once made exacly the same mistake you did
;o)

--
Max

sorry I kind of simplified a bit... I wasn't just going to use the output
from the mersenne twister algorithm to feed into the XOR. The output was
going to be buffered and gated by another PRBS. A little more involved to
explain...
Essentially take two bits of the gating PRBS then for each different half
nibble perform a particular gating operation on the mersenne twister output:
ie
00 - ignore output of mersenne twister completely
01 - place mersenne twister output into buffer
10 - place inverted version of mersenne twister output into buffer
11 - ignore output of mersenne twister completely

The gating PRBS would also be a mersenne prime GFSR, although one with
reduced periodicity to that of the mersenne twister.

I also read some information about such algorithms as blum blub shub. But
again couldn't find any kind of hardware based implementations (ie designed
for a fpga or cpld).

I was really just looking for something slightly removed from mainstream...
Just like a bit of challenge I guess.
I'll have a look at the common algorithms too, I think they be sufficient
for the requirements also.

Thanks

 

[Max]

On Fri, 5 Mar 2004 19:09:12 +1300, Bevan Weiss wrote:

I'm after a PRBS so it just seems a bit awkward to go from a twisted
generalised shift register (TGSFR) type algorithm (which the mersenne
twister is based on) to a 32bit register type approach (as all the software
processes use) only to have to go back to a shift register type arrangement
at the output to get back into a serial stream.

My desire would be for a feedback shift register type implementation (which
is easily and efficiently done in an fpga or a cpld)

The problem there is that the MT is specifically designed to be
efficiently implemented in software on a 32-bit CPU (as is it's little
brother, TT800). This gives the general idea:
http://choices.cs.uiuc.edu/~akapadia/project2/node10.html

It's for a type of cryptology application. I want to use the output to
simply encrypt some bitstream, using a simple XOR gate. Decryption would
then be exactly the same process, just XOR the encrypted stream with the
same PRBS to get back the original data.

Ouch! MT is definitely not suitable for cryptographic use as it
stands, and the sort of system you propose would be straightforward to
break with differential cryptanalysis. It's intended for Monte-Carlo
simulations only.

The MT inventor's page I linked before highlights this (near the top
of the page):
http://www.math.keio.ac.jp/~matumoto/emt.html
You could run the output from the MT through a trapdoor hash such as
MD5 to secure the cyphertext, but there would still be potentially
crucial weaknesses in key exchange, if you're not very careful.

Why not use an existing cryptosystem which is known to be secure?
There's a variety to choose from, and many are designed to be easy to
implement in hardware. How about triple-DES, for example? Or even
straight DES (with CBC) if your security needs are not quite so
stringent?

Rolling your own cryptosystem is rarely a good idea, unless you're a
specialist in the field - and even they can get it wrong. For a
general discussion of this, Phil Zimmerman's background documentation
for PGP is worth reading. He once made exacly the same mistake you did
;o)

--
Max

 

[Max]

On Fri, 5 Mar 2004 23:01:01 +1300, Bevan Weiss wrote:

I was really just looking for something slightly removed from mainstream...
Just like a bit of challenge I guess.
I'll have a look at the common algorithms too, I think they be sufficient
for the requirements also.

An interesting project might be to implement Rijndael/AES in an FPGA.
It's pretty efficient for a block cypher algorithm, and about as
secure as you can get:
http://www.esat.kuleuven.ac.be/~rijmen/rijndael/

--
Max

 

[Sander Vesik]

Max <mtj2@btopenworld.com> wrote:

On Fri, 5 Mar 2004 23:01:01 +1300, Bevan Weiss wrote:

I was really just looking for something slightly removed from mainstream...
Just like a bit of challenge I guess.
I'll have a look at the common algorithms too, I think they be sufficient
for the requirements also.

An interesting project might be to implement Rijndael/AES in an FPGA.
It's pretty efficient for a block cypher algorithm, and about as
secure as you can get:
http://www.esat.kuleuven.ac.be/~rijmen/rijndael/

There is a core on opencores.org that is probably suitable for a prng
(its slightly lacking for my taste as a general crypto core)

--
Sander

+++ Out of cheese error +++

 

[Max]

On Fri, 5 Mar 2004 20:07:24 +0000 (UTC), Sander Vesik wrote:

There is a core on opencores.org that is probably suitable for a prng
(its slightly lacking for my taste as a general crypto core)

Got a link? I'm not sure what I'm looking for otherwise.

+++ Out of cheese error +++
+++ Redo from start +++

--
Max

 

[Sander Vesik]

Max <mtj2@btopenworld.com> wrote:

On Fri, 5 Mar 2004 20:07:24 +0000 (UTC), Sander Vesik wrote:

There is a core on opencores.org that is probably suitable for a prng
(its slightly lacking for my taste as a general crypto core)

Got a link? I'm not sure what I'm looking for otherwise.

www.opencores.org

--
Sander

+++ Out of cheese error +++

 

[Max]

On Sat, 6 Mar 2004 03:50:49 +0000 (UTC), Sander Vesik wrote:

www.opencores.org

Yes, but which core are you referring to?

--
Max