www.digitalmars.com         C & C++   DMDScript  

D - My first D project: Mersenne Twister

reply "Andrew Edwards" <edwardsac spamfreeusa.com> writes:
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


begin 666 mt.d

M97( 9V5N97)A=&]R("TM($0-"B  ($)A<V5D(&]N(&-O9&4 8GD 36%K;W1O




M('-T871E(&)Y('5S:6YG(&EN:71?9V5N<F%N9"AS965D*2 -"B  (&]R(&EN



M97< 0RX 161W87)D<PT*("  06QL(')I9VAT<R!R97-E<G9E9"X-" T*("  
M4F5D:7-T<FEB=71I;VX 86YD('5S92!I;B!S;W5R8V4 86YD(&)I;F%R>2!F

M97)M:71T960 <')O=FED960 =&AA="!T:&4 9F]L;&]W:6YG(&-O;F1I=&EO

M('-O=7)C92!C;V1E(&UU<W0 <F5T86EN('1H92!A8F]V92!C;W!Y<FEG:'0-
M"B  ("  ("  ;F]T:6-E+"!T:&ES(&QI<W0 ;V8 8V]N9&ET:6]N<R!A;F0 

M8G5T:6]N<R!I;B!B:6YA<GD 9F]R;2!M=7-T(')E<')O9'5C92!T:&4 86)O

M;F1I=&EO;G, 86YD('1H92!F;VQL;W=I;F< 9&ES8VQA:6UE<B!I;B!T:&4-
M"B  ("  ("  9&]C=6UE;G1A=&EO;B!A;F0O;W( ;W1H97( ;6%T97)I86QS
M('!R;W9I9&5D('=I=&  =&AE(&1I<W1R:6)U=&EO;BX-" T*("  (" S+B!4
M:&4 ;F%M97, ;V8 :71S(&-O;G1R:6)U=&]R<R!M87D ;F]T(&)E('5S960 
M=&\ 96YD;W)S92!O<B!P<F]M;W1E( T*("  ("  ("!P<F]D=6-T<R!D97)I
M=F5D(&9R;VT =&AI<R!S;V9T=V%R92!W:71H;W5T('-P96-I9FEC('!R:6]R

M5%=!4D4 25, 4%)/5DE$140 0ED 5$A%($-/4%E224=(5"!(3TQ$15)3($%.


M24U)5$5$(%1/+"!42$4 24U03$E%1"!705)204Y42453($]&($U%4D-(04Y4


M4%E224=(5"!/5TY%4B!/4 T*("  0T].5%))0E543U)3($)%($Q)04),12!&



M1B!354)35$E4551%($=/3T13($]2(%-%4E9)0T53.R!,3U-3($]&(%5312P 
M1$%402P 3U(-"B  (%!23T9)5%,[($]2($)54TE.15-3($E.5$524E505$E/



M5TE312D 05))4TE.1R!)3B!!3ED 5T%9($]55"!/1B!42$4 55-%($]&(%1(
M25,-"B  (%-/1E1705)%+"!%5D5.($E&($%$5DE3140 3T8 5$A%(%!/4U-)





M(&5D=V%R9'-A8T!I965E+F]R9R!O;B!A;&P 8V]R<F5S<&]N9&5N8V4-"BHO


M-#L-"F-O;G-T(&EN="!-(#T ,SDW.PT*8V]N<W0 =6EN="!-051225A?02 ]



M9F953#L
M6$))5%,H=6EN="!U+"!U:6YT('8I('L <F5T=7)N("AU("8 54U!4TLI('P 
M*'8 )B!,34%32RD[('T-"G5I;G0 5%=)4U0H=6EN="!U+'5I;G0 =BD >R!R
M971U<FX *$U)6$))5%,H=2QV*2 ^/B Q*2!>("AV)C$ /R!-051225A?02 Z



M" T*+RH :6YI=&EA;&EZ97, <W1A=&5;3ET =VET:"!A('-E960 *B\-"G9O
M:60 :6YI=%]G96YR86YD*'5I;G0 <RD-"GL-"B  ("!S=&%T95LP73T <R F


M+3%=(%X *'-T871E6VHM,5T /CX ,S I*2 K(&HI.R -"B  ("  ("  +RH 


M<RP 35-"<R!O9B!T:&4 <V5E9"!A9F9E8W0 (" J+PT*("  ("  (" O*B!O
M;FQY($U30G, ;V8 =&AE(&%R<F%Y('-T871E6UTN("  ("  ("  ("  ("  
M("  ("  ("  *B\-"B  ("  ("  +RH ,C P,B\P,2\P.2!M;V1I9FEE9"!B



M"B\J(&EN:71I86QI>F4 8GD 86X 87)R87D =VET:"!A<G)A>2UL96YG=&  
M*B\-"B\J(&EN:71?:V5Y(&ES('1H92!A<G)A>2!F;W( :6YI=&EA;&EZ:6YG
M(&ME>7, *B\-"B\J(&ME>5]L96YG=&  :7, :71S(&QE;F=T:" J+PT*+R]U

M=%]B>5]A<G)A>2AU:6YT(&EN:71?:V5Y6UTL('5I;G0 :V5Y7VQE;F=T:"D-
M"GL-"B  ("!I;G0 :2P :BP :SL-"B  ("!I;FET7V=E;G)A;F0H,3DV-3 R

M/R!.(#H
M("  ("!S=&%T95MI72 ]("AS=&%T95MI72!>(" H<W1A=&5;:2TQ72!>("AS
M=&%T95MI+3%=(#X



M/CU.*2![('-T871E6S!=(#T

M+3$[(&L[(&LM+2D >PT*("  ("  ("!S=&%T95MI72 ]("AS=&%T95MI72!>
M(" H<W1A=&5;:2TQ72!>("AS=&%T95MI+3%=(#X
M.30Q54PI*0T*("  ("  ("  ("T :3L +RH ;F]N(&QI;F5A<B J+PT*("  
M("  ("!S=&%T95MI72 F/2 P>&9F9F9F9F9F54P[("\J(&9O<B!73U)$4TE:

M*&D^/4XI('L <W1A=&5;,%T /2!S=&%T95M.+3%=.R!I/3$[('T-"B  ("!]





M969A=6QT(&EN:71I86P <V5E9"!I<R!U<V5D("  ("  ("  *B\-"B  ("!I


M(&H]3BU-*S$[("TM:CL <"LK*2 -"B  ("  ("  *G  /2!P6TU=(%X 5%=)

M*2 -"B  ("  ("  *G  /2!P6TTM3ET 7B!45TE35"AP6S!=+"!P6S%=*3L-
M" T*("  ("IP(#T <%M-+4Y=(%X 5%=)4U0H<%LP72P <W1A=&5;,%TI.PT*


M("  ('5I;G0 >3L-" T*("  (&EF(" M+6QE9G0 /3T ,"D ;F5X=%]S=&%T



M3#L-"B  ("!Y(%X]("AY(#X


M('5I;G0 >3L-" T*("  (&EF(" M+6QE9G0 /3T ,"D ;F5X=%]S=&%T92 I



M"B  ("!Y(%X]("AY(#X


M>PT*("  ('5I;G0 >3L-" T*("  (&EF(" M+6QE9G0 /3T ,"D ;F5X=%]S




M8FQE*7D *B H,2XP+S0R.30Y-C<R.34N,"D[( T*("  ("\J(&1I=FED960 




M(%1E;7!E<FEN9R J+PT*("  ('D 7CT *'D /CX ,3$I.PT*("  ('D 7CT 
M*'D /#P -RD )B P>#ED






M"B  (" O*B!496UP97)I;F< *B\-"B  ("!Y(%X]("AY(#X
M("!Y(%X]("AY(#P
M/#P








M" T*:6YT(&UA:6XH*0T*>PT*("  ('-T871I8R!U:6YT(&EN:71;-%T]6S!X

M.PT*("  (&EN:71?8GE?87)R87DH:6YI="P ;&5N9W1H*3L-"B  (" O*B!4
M:&ES(&ES(&%N(&5X86UP;&4 ;V8 :6YI=&EA;&EZ:6YG(&)Y(&%N(&%R<F%Y
M+B  ("  (" J+PT*("  ("\J(%EO=2!M87D =7-E(&EN:71?9V5N<F%N9"AS

M965D(&9O<B!A('-I;7!L97( :6YI=&EA;&EZ871I;VX ("  ("  ("  ("  


M"B  ("  ('!R:6YT9B B)3$P;'4 (BP 9V5N<F%N9%]I;G0S,B I*3L-"B  


M("  (&9O<B H:6YT(&D],#L




,(&9R;VT 0R!T;R!$
`
end
Sep 30 2003
next sibling parent Olaf Rogalsky <olaf.rogalsky theorie1.physik.uni-erlangen.de> writes:
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! 
Congratulations, MT is my favorite RNG: Both, fast and without known 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 
Well, I wish you good luck, but this is not an easy task. Good security 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.
Why the hack an OO version??? What's the benefit of it? Just provide a simple API 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
prev sibling parent Helmut Leitner <leitner hls.via.at> writes:
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