## D - My first D project: Mersenne Twister

- "Andrew Edwards" <edwardsac spamfreeusa.com> Sep 30 2003
- Olaf Rogalsky <olaf.rogalsky theorie1.physik.uni-erlangen.de> Sep 30 2003
- Helmut Leitner <leitner hls.via.at> Sep 30 2003

Gentlemen, (Are there any ladies here?) I've successfully compiled the Mersenne Twister RNG in D. In it's current state, it is simply a C program modified to compile in D. I would like to make it a true "D" program and would appreciate some suggestions on how to improve upon it! As pointed out by the original authors (http://www.math.keio.ac.jp/matumoto/emt.html), MT is "NOT SECURE for CRYPTOGRAPHY", I would like to remedy this situation and eventually provide an OO version of the RNG. All guidance and suggestions will be greatly appreciated. Code is attached. Andrew

Sep 30 2003

Andrew Edwards wrote:I've successfully compiled the Mersenne Twister RNG in D. In it's current state, it is simply a C program modified to compile in D. I would like to make it a true "D" program and would appreciate some suggestions on how to improve upon it!

deficiencies.As pointed out by the original authors (http://www.math.keio.ac.jp/matumoto/emt.html), MT is "NOT SECURE for CRYPTOGRAPHY", I would like to remedy this situation

mainly stems from two aspects of the RNG: 1) Randomness. Software RNG's aren't random at all, once the seed is known, the sequence is completely predictable. Therefore, the RNG's in cryptographic software is continuously seeded with truly random data from some source of entropy. This truly random data usually is drawn from monitored system events, like the time interval between two successive key strokes or the time interval between the arrival of two network packets. Of course these data events are highly correlated and therefore not suitable for cryptography. The subject of the RNG then is to mix and mangle the correlated data to a new sequence of data, which is not obviously correlated. 2) Invertability. Consider the (mathematical) function f, which maps the seed data to the random numbers. For simplicity lets assume, that f is bijective, such that there exists a inverse function g: g(f(x))=f(g(x))=x. If it is feasible to compute the inverse function g, then an attacker could compute the seed data from the output of the RNG. But since the seed data is highly correlated, he can predict with good probability the seed data for the next random number. But if he knows the seed, he easily can compute the next random number by applying the function f to the new seed. You therefore must prove (if you do so, you probably will be awarded the Fields Medal) or at least make plausible to the experts, that it is unfeasible to compute the inverse function g.and eventually provide an OO version of the RNG.

for the production of random numbers, drawn from some random distribution, most importantly: Uniformly distributed integers in some range. Uniformly distributed floats/doubles in some range. Binomial distributed integers. Poissonian distributed floats/doubles. Gaussian distributed floats/doubles. I hope, I haven't been too discouraging, cheers Olaf -- +----------------------------------------------------------------------+ I Dr. Olaf Rogalsky Institut f. Theo. Physik I I I Tel.: 09131 8528440 Univ. Erlangen-Nuernberg I I Fax.: 09131 8528444 Staudtstrasse 7 B3 I I rogalsky theorie1.physik.uni-erlangen.de D-91058 Erlangen I +----------------------------------------------------------------------+

Sep 30 2003

Andrew Edwards wrote:Gentlemen, (Are there any ladies here?) I've successfully compiled the Mersenne Twister RNG in D. In it's current state, it is simply a C program modified to compile in D. I would like to make it a true "D" program and would appreciate some suggestions on how to improve upon it! As pointed out by the original authors (http://www.math.keio.ac.jp/matumoto/emt.html), MT is "NOT SECURE for CRYPTOGRAPHY", I would like to remedy this situation and eventually provide an OO version of the RNG. All guidance and suggestions will be greatly appreciated. Code is attached.

Sometime ago I started a experimental Venus library as a testbed for future Modules to Phobos / standard library. As part of it I reworked the existing Phobos random generator to separate the generator part from special functions like producing numbers for an integer or fp range or for Gauss distributions. The generators are also pluggable via an interface. Your work would fit nicely in. The MT could be a third generator, the 53-bit-part a nice addition to the "outer layer" of the system usable with any other generator too. Take a look at my code at: <http://www.prowiki.org/wiki4d/wiki.cgi?VenusLibrary> - interfaces.d - random1.d - random2.d If you can live with the "Donation to Digital Mars" statement, you can do the integration yourself or leave the task to me. I suppose it will make its way (not necessarily in this exact form for library standards are not yet discussed) to a future standard library sooner or later. If have have any additional random number expert knowledge it would be nice to integrate it into the environment. Anyway, thank you for your work! -- Helmut Leitner leitner hls.via.at Graz, Austria www.hls-software.com

Sep 30 2003