mersenne twister

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

Reply to
Bevan Weiss
Loading thread data ...

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?

Here's the MT inventor's home page, if it helps:

formatting link

--
  Max
Reply to
Max

Have a look at the document accessed from here:

formatting link

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

software

implementation

Reply to
Michael Chan

D'oh! Brain fade :o((

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
Reply to
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.
Reply to
Bevan Weiss

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:

formatting link

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):

formatting link
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
Reply to
Max

software

arrangement

(which

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 :)

Reply to
Bevan Weiss

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:

formatting link

--
  Max
Reply to
Max

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 +++
Reply to
Sander Vesik

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

+++ Redo from start +++
--
  Max
Reply to
Max

formatting link

--
	Sander

+++ Out of cheese error +++
Reply to
Sander Vesik

Yes, but which core are you referring to?

--
  Max
Reply to
Max

ElectronDepot website is not affiliated with any of the manufacturers or service providers discussed here. All logos and trade names are the property of their respective owners.