From msuinfo!agate!howland.reston.ans.net!cs.utexas.edu!not-for-mail Sat Mar 19 21:28:15 1994 Path: msuinfo!agate!howland.reston.ans.net!cs.utexas.edu!not-for-mail From: boucher@csl.sri.com (Peter K. Boucher) Newsgroups: sci.crypt Subject: Re: YASR (Yet Another Secure RNG) Date: 15 Mar 1994 14:55:21 -0600 Organization: UTexas Mail-to-News Gateway Lines: 68 Sender: daemon@cs.utexas.edu Message-ID: <9403152055.AA23352@redwood.csl.sri.com> NNTP-Posting-Host: cs.utexas.edu Here's the meat of the algorithm: 1) There's a table containing 256 permutations of the numbers 0-31. 2) There are two additive congruential generators based on the irreducible trinomials X**839 + X**54 + 1, and Y**719 + Y**150 + 1, respectively. 3) The output of the two additive congruential generators is combined in the following way: output = (((x<<9)^(x>>23)) + ((y<<18)^(y>>14))), where x comes from generator 1, and y comes from generator 2. 4) The table is used to select an ordering for 32 of the combined outputs. 5) The tables is also used to select an ordering for 32 such groups of 32 combined outputs, giving 1024 "shuffled" outputs. Here are the two routines used to generate the output. ====================== BEGIN SOURCE CODE FRAGMENT ====================== static unsigned long fill_rands() { register unsigned char *optr1, *optr2; register int i, j; register unsigned long x,y; register unsigned long *rptr; optr1 = otab[(indexr1 = (1103515245 * indexr1 + 12345))>>24]; for (i=32; i--;) { rptr = /* select a group of 32 outputs to fill in */ &(rands[((unsigned int)(*(optr1++)))*32]); optr2 = /* select an order to fill in those 32 outputs */ otab[(indexr2 = (1103515245 * indexr2 + 12345))>>24]; for (j=32; j--;) { x = (*frnt0 += *rear0); /* generator 1 */ y = (*frnt1 += *rear1); /* generator 2 */ rptr[*(optr2++)] = (((x<<9)^(x>>23)) + ((y<<18)^(y>>14))); if( ++frnt0 >= end0 ) { /* update generator 1 ptrs */ frnt0 = state0; ++rear0; } else { if( ++rear0 >= end0 ) rear0 = state0; } if( ++frnt1 >= end1 ) { /* update generator 2 ptrs */ frnt1 = state1; ++rear1; } else { if( ++rear1 >= end1 ) rear1 = state1; } } } num_rands = 1023; rand_ptr = &(rands[1]); return( rands[0] ); } unsigned long rand32() { return( (num_rands--) ? *(rand_ptr++) : fill_rands() ); } ======================= END SOURCE CODE FRAGMENT ======================= -- Peter K. Boucher -- DISCLAIMER: The above does not represent the opinions of my employer. From msuinfo!uwm.edu!cs.utexas.edu!not-for-mail Sat Mar 19 21:19:27 1994 Path: msuinfo!uwm.edu!cs.utexas.edu!not-for-mail From: boucher@csl.sri.com (Peter K. Boucher) Newsgroups: sci.crypt Subject: YASR (Yet Another Secure RNG) Date: 14 Mar 1994 14:32:41 -0600 Organization: UTexas Mail-to-News Gateway Lines: 238 Sender: daemon@cs.utexas.edu Message-ID: <9403142032.AA11659@redwood.csl.sri.com> NNTP-Posting-Host: cs.utexas.edu This is not as small, nor elegant as Jenkins' (which Colin James claims infringes on his patent). However, it has similar performance and randomness of output, and it does not use Knuth's algorithm M, which is what James appears to dislike. I can't think of a way to determine the state of this RNG by looking at it's output. Can any of you? == Peter K. Boucher == DISCLAIMER: The above does not represent the opinions of my employer. ======================= CUT HERE ============================ begin 660 rdm.c.Z M'YV0(\B4,9/&31D01(H<^0(#!(X9.10$'%CPX)0B4!B"J$%#@42!! TB5/@E M!H@;,2).#&D18TD0,6K \+BR(H@D3A)BD6(2!8J" O'(,=D#!(H8,6#,J!%3 M!HT:(%2 %I&J,D5,&7,>)HBA0\?3E-\I"@2ITXI,HS^=!-43MJB1Y,N;?HT MZE2V5=V"P!I#*U>O8&F(53"'3A@Z:<: J.-F3IHS!LF 8//&S1D0A0^7@;$E MX4(875A$-2/'#1T8HE7(*1-&#NJH9=@V+&H"168ZFSN3!)UB!V'#B!4S=@RY MC&3*EC$#+Q-#]\(8H4>7IA,C]>K6U6&S)0JB]FWFSDMVZ?W[<.+%C1]'GESY MLILZ;;[("<-V#HBB,'S?/C]<<>U=U=;,A!HGG 'KH?< M9:K11\87<- AAX/!H4>A_TA",(8:+0&PAN&B;&% M##78T 6),G1Q'PA[*+ ':C>P$ ,.+-3 @@U&HD8#"S(4*4-U*;& I%90HA;# MDS+D "62,U Y@Y%%]@4EDU[BR,*8,D#9)I5,SJ EE4HZU0<+0FK))I-.N6DD ME5*RZ65,:QJ)9'5/%GDE:G)^:62:9?)9W9MMAMEDDBP,RJ62-MR9IY%/>FEI ME4R:V6B;,O#Y)IF&LO!D#'R.26B71HY99)U<:HG:E%"6.>F52HZ)@Z=#MDIK ME$:R4*:26T+)K*R[QFHDJHQ6QV2HC_H90Y'"0CGIGU!RB22S<<) [*[6&AGG MF=I2B>2KW=)**+-2EKEJLUA:^N:NBSJ[II9>IIGHN>'6RFJJ5F99J)DRH.HO MKU1R6::7S%8WJK0R7.EEJ5HJ6>:[F?Y+<,;)-APRLH*N.>F8UX++ZZ&WLMML M#&R^ZN6RZK;::%(/:XGJR&E:K"RH_[(+*::P.JHFHN!N.VW!)LN@:\)'9BNM MO@;'1&QUJ W*+*IC4CJ,<-(<+X[LH!2[JC.4LJ;<+,P*DTRH MX*>^BFJ=7.-]Y9. HQHIVL96O.3382\^*.A5-GLJFU<"ZF?C4VN-YQY4OBFY MPH-.FF:\U2F9Z*5[FYVSTXS*+.NAN-H.YJYNXEWUJJEN[\QSGA%?%+IB@:QD_'I2O%BUK#V2$3A ME:J!/%,3M@0WRD0R,GOPPI2LWE0D/O%)=(O[F ,;MD23J4Y6 6L5(5V7.5GE MJE"O0LTHB8?&1#)I9>8R:<+/@'Y:I9"J:#LE!5!FFE+: MKBC%PP>Z+V';2R.?7"PJR"68HNI5AVH3)HLV,T@6*4WF'%/' M>-B^@]WRESYM%+;TQ4*HE0ES62LLN XWP-K-"DG3[!<*,3H]M>[A?3W44]YF MMREFUB]-:8.E%'>E*)?-T%14RETB3:@N8LV26O?4%O0*.L% %0JM8G :H1R$158M^>FJ N34IQ.;-CJ=C[&21Q"U, M 7%2XM3DH.AI8&:>+9'6G9YZ"25,33YN85P2KOV4^S:S9L]>*N-N(NG*).11 M[9?F-.2DG"NX"NLKM_'5X-ZNBU9=<7=4A2*@L;BWX*PE$V&[N4:8(.)I23^Y;=IEO0B$FU)1"]U+EFO6FPLL\PP27+4HLWEJ#4K( MVF)3G415'A?T8YT?,UKVN6:5:HPD]!2?D58ZR8HKX7EUI4B M/2PIJ60N1%M6=VUT6*- J#Z]R;1D)?4B<3M8NZ61D6AI4A4175LGV>K+S]A5 M$I*L/#Q4/AB_0Q/<*4&-NZ5*6%MOM).G!UJD&SIMIVWX:O47'1=.?P,X36W;FS/I75 DBSE<)"=A%B^G MV:P!RW7RYB@O3];' 4[V;:4V>,D.2/+A:3I[I$ORFZXFSO*J]E6/]2="ATDE M*A&;:K9J>E*9AL+*1JU.O6/F8D$X-5KA+V] 9FWFQ!4ZG(]/4N:,Z] I+3%H M\E/;P4M9HZ;&+,QY4DJ'LEC#>WKW[W$1>SD5ZRN1E5'99I5NQ1Z5:)G'6&TF MA>0(FW?4NK7.#D8]BW-+%K6_IE1:L55[ 'UC7XGUV9G?E]Y;WVHC_>I!9%J0 MM/(B> KQB:DTB7-_M XC4^PZSZ%H_6WR_ MQO[H_QY<^I;?NX$_/Q4='8CW[%E[=F^+2Z#<;- MQ"[0TDA*-#X3DS5"MECTE3>6,TS20RB1XR=LYT^UY&;854?0AF\&R"XDDWH_ MQS#&$CZO8CN$ SV )5O&M"Z9$S,IU4H,)23#V7\BKOLS/]=T[\U4#'TX1/8XB\)8#!@U[7 M1"9O:'W2Y8@1*"^O2'P=QT]"Z"?2@T!-ME5IESG&QF&KR$.OEHE%M"L>-31> M5CA?M(##,WGXERZ<-S-M@CK$-#Z0=%2(IV@FE4<<.%/"U"=H12BVYD\PE3.6 MV*$PL14HA=H3F%GUW29$<^&Z#&3B3)HGOLC5F56RPM6KR&)"SHFO0 M.#.E>"_,AVW/1%TP))'DDT_R H9F EU3YR_@-$[)Q'GV]5+<]H[#,RGN(E)/ MQ9DG\UG#=UXN%3KDE4(9TR\ITV-ID," MI%-H%F&L9TC-:98C1)SM53 /.4RMTSB%AT)L1F1#TU*LM98M-#,LHS1-^9I^ M,EGEIDE]]5>-A)/M5D:J$YQ+ TIW&6R%F)WJF3^HITNM$G2.E)],9EXF0USE M%G#4LY).PUEGHIX'.((H=3)S0C4O5)-)EJ&YHT7?N33[9BE^ADAU23[?TBAX MER^@&%S#1%?TXW='59@%J7(!]G:8=BRALC5DASVIYSMO]3^PR8ENLSHBA49X M9REZ]W-*1E],VD725V-FU(!.XWP_IHRUR#CQ*8QVF'(#NE5_\Z6]-T!Z8Z%\ M1H&MQ'I,&55C-DM,MH ]9XC(XEJ:Q%11B$WOHW,59IG#=8J\29$A-8--F$"T M%5CCHTEZ&DZSQ5K:$SXA(X?.-5#KED+/$CQIJB^IMRZP\J5>M'(9A4(E!TN* M2"@\F$)BFEU/Z3H[,TT?M6HW2CQ MR#E;8U1]QVHBM5.ELFU'Z&(>9T@@AX:3J:O%"C]F,ZWQ!DN,!)3EU3)C&)RS MPJRU-8'9,R8"=2]=>4KF&DMH=S*EAB^L^$]Y5C [16*II'?.40C=C.@EHN91)I5(VV:ECG1DJ]O&I[[V)OC!'V5.D&C7.C8U#V0 MFS^0-7DV1C+S%&!1^D:'8Y)4R9ZT$; [F\,EGY.5,RJD->IZPB%*X^BR3?R#"* M!8UM!"A;([D=Q%9>-&#QE3=8J4*FQH$(YWQJDC_#UG4?BC8!+%)K2%/T=FJ6 M)%4/8WX;AS(-9D$U9*ROM*O>4L&QM'VRECD$V4;50X40DW6TXH.,59YE);BM M@EHH;*7RPH,,1S59%V0)YC(YZ$4EE6%3^S;S8T\LA,(1;*S5](P,)"V^6X*" MHS9S>2DMC(N,!7CR4L'A>K(AV$J::,)2&W(!8AQQ"N5>*FR%JS-,X&;94Y<[$4AEDB:_$#=*&SW M9JR)O%UTW<&N(Z'P=IOG-$VSFKS@(EH"!S==9))SUID]O:<=Q*F:6+S),F9T M$TNDO#CJ3$NMM&C2.ZBO<]BGI<,*EMHI$DN2RK60\94(T#JNKV: M:K(/A)/"*[\/*"W$-2L %C,[(U#?E%1=6BOV;3(M](IN-*DWQIZEQBO_2-U,R9O?1F " MWHQ/E.#Y@Y,1*<+5;5*P&6SAC=S5][4\;&W[>8N&W;>&$)5R'H#B]:)O35J Y1< M"J0X8Y58@L8ON7 #9)QF):*E6,YQ_(3?ZTF%A[K5-$00EIJ2IBURYV+5D[>7 M.:A2KFZ7TI982,L]!'(4QL#5YWW^EYH2_-#!4SYU/LK"0R]@*EJ-(E&\YTVO M!'S,^9<&C#=)W3?6J'"C7A+3S/.U-L9CO#E&K_O(R4 MIJJ04^=NEV3[:XJC^3W$J(S6MCBP%<2!+*G1)=J#MS79.^R 1TVV1:&.V-FY M=)>>Y$$\5-OE1KTF).XE"=C:TGXH+=L'HZGWDGOK1)4Z1N'$U9:/>ZECQF-R MWBP4V=$SQ9-5*$"CTEDFWD,_*Y5C2ZCG[7(PS624AJ"^RT;=B2EY?5T$Z4GB M^#'T3LM]$NN%$ZPI1*2MC5:S&LD*]IM/\\CU$TN_&M$@I5 MN./6/5OE]F7S(C(&_T .5J9NT^T5RV[NMMN'2%;3"55F(M56?)W>_.Y21X+W MMM>3+M.W7#(@XY.)W4@BK2PR)+]6K.A;I?72^SPK7CO\'*"M"*:-PHICY89[ MM.P#Y"5FZW'_4X9.=C 66(*U8Y421$KPII!6\O;\&E6AJO7[*Z\Y^WB>%^'S MIG2//CT,A"^J2%ZI*U&K>''"M,ZHJ2'=XW)CAZT!; M%\^R:<6K_K[\U(13*U],+NP46K0=Y8(^S&DY'8SWL6VB1NF0(3KN8-2TUE/S MB,;.P#&C)-:5GE=#JBX%C*%L_4A(O(P'\X'&CN=Y-!PGJA XA<-.VD[J(7JA M1N3-- C(*N17"_I'<&:(:!75,H!,W0AK1I ENC Y#X>.!DH-FDZ.;TWY$P=2 M2RR;._LO\\,1=2JGTC3NR(WB*D9C@:D.DV/ GHZ%BB-JQIX0,^HR^E;.1)E\ M>R2$::6]L:\H#0!:+)/'[VT[QK(NSEL^ CZ A5K00#A5-)@*+_LL.\V3C"J* M%,*T'L; -2AH](T.&;(JL$N(V7,;9%D9&S_#:WB./]%I10/_ !F$ED<8H04I M(O(*QE09U[4[0%@:H6Z]1;B@M>\UBK!+>MHC;8+D&1VE8?><4,%(.:RKDG@O MRL606DEG@2XI5VVF7ZY=(^DVSL8> Z*A8P"A61#Z, M3B-\GL7GS+3J8\FVV7VS(S)$#$VWMY-%9AVU4AAJB"F%MVT86^262$%/"R[2 M]+\71F\Z5+O94S.#$[82CJ1F+A@5@FO!ZC:9C#CFXWB(:@%%)B,"A2@I> >E M2[ Z;V"%)J$T2O.@ID5&S!H4#BB=DU(A:RR;:-):H2V@Q9[(Q8=B(A'I,D\Q MB#@0L#2",M1X23<$28C]LFZ1\&Y;FFH[*B4L!BAY%?*6'J^!B,#CJ/2Y5%17 M3(7^^!ZH;DF$Q><1NR@4UM)1"S# @*C.]@V=5?,(9#9+]?R)L)A;9$L/N74@ MCJI9BA:BSJ *L;)&ETZB9!23)$,B#2\#)KIPLRD?6!)!^MQ&B1=("MNXG'2C M\C_,T/!V,9]T] 0Q;/1)T4BE4C@9B*ZNA9_@3FV$93 ML8#6C?PX;U[$_)RNC,4D+_J@W<:38*)*KQ$/<27QZ3#+D,<(1O3'+TMB;@HC BB4M MMP/9WW+&T>@6&>8%L3_2-(30E)8),*G)P>P,=55!2B(+*TU$RJ]9&==TZ2;( M@1I^>JF.Z#3QX_P 8=B[/<1,7JPF5SXA"Q24P9*'8!Q4PB_OT@&ZV11H+H#4L< MAI9P:K3"]B$E%^N95\R$XT7% !D"V=]U M>V1_3 U)0=*DW=+(2OIAY\1*\9J/LGW.DE.,FHP%X%C,RF;\)"+)0$_Z@H>= M+E;6A)Z,:(DZ=/*Z ,Z\HCI<8M/('3M$>0'$^)A&FAD7\4*EK@C.2, CO;@7 M%@P^D?(EV0Y#6#!R$43L()0S66C/M'ESI)!V+'(/)B'EGL#F7UX)1Y)-[PAD M? T9PA&EEU%#B5!CDZD6XN.5(E[>:'6S0V'Z"1ENU9*P MRQ#Y.9-FE-B<.,=3DB7[XT+E<-P,T(+A#&=+B8%\\E)PN$,8EUZD9?7DGZ1$ MD/%%6W4),U@38E0'AO@X%X?F9SP.M\P4,-3F5*9895.6^P=@L.; M1)6E&1K8)(;LD<\%"MOFS)D57\Z .2$ZM(?NTJ.I.M?EZ0T-GNC L!(!O33Y M ]+ FH3)*\S@O?$D5P,.71LO4@0#FCO#;?8$(!XF+Q2Q2ETV;%5$Q)6]&N C MNJ8H1\&;F%%$2;Q1Q+]:4^N:-M,CZT"?0(>J%"J60@$-]Q%@&U9&3*Y&0EKYGS 1'N]DA3@*5CBOM M]6"@DIL!2U@I_32A!O1*5M(%4AK=[JKT/\)F:&K8T[",M,BE% JVY??Z$FR! M))8-C;D5DH)&
LC$Q:H[YFB2EHNX91LHB)$MQ' NS4CII:6!B<"2$?PP6 MP0FPL-" JSCN2G$L.+92)KBI;N. 1@EFH*UTH&0D6=69'RSA(&H1221DJQ;W&4I7RIYG2970[>I1RU-7,B2 ?YGOU M&Y3&CYHD$W%[]<3"\2#EQ="D8IZ3'UB.W_4D\P.17,=G"ER?)Z::$TI%L9!% MBIHWV -GI) (U+2 :FTR&?AG2HF4571S-2<^ >-",B* BN,:C\E$F@QXR4)(@5 M'PHLQF$D)=!HHQ6YT'SZBUS20\04='$98FC]B;'C9GL(7D7%DB9PMIB=\F(, M71 ,\7.9XTT@5FN%EV:E@TIG;:="+8R+)(:U6K\,ZUQU;H7\) M3.=,UG/UBEP/T9,_F71"I8K=2AP_3!<)9)VH#>V?NZ+N9(8DQ9!;!0;.P[G2 M!Q1 'U 1^P%"?(C_,"% @ (@"&R #<@'"S$'4(!8"!(@(,""@-5P!M) 82@# M4B!TP%5I "]@!*0!(*( $( 34NQ_\+ I 6H !2@8V/ "E@!72$%J 401X2@(Y]"S.B1FP!(+L3>H1O M2 !&%LFJ 27;($" &G"R4%;*)@ ,BP=^A)@E#::A(:R HJ :6(-K:+,8-@\8 M6A6 :*G#7F"TUV$H0%H8&V&WP)A]LVT$MY(%3>R14+0K( U]A2Z19%3%H!6P:, ,H(,">V4K;$$" #R@*(" V MD(%B&V4%+9Z=#K-!.6B&_#!E$\"9S;34MM<&V#Z0;-G '#@(SO;7!MN]L *P M;8 ]M@%6V3+; &MNB\)WR+88MKUJVZD ;(7M"JBT)L'8(EMEFV^;;9!( ,_6 M-'"'[Q #[JRU+;>.MN!.V7C;;;]M@/VW"4#->6 '['N)#EK4/12$I: 4B.V M!(;0$%<6!9S<+0 =R .)+0-T MH Z4AF [-D$81D40)8M$?Y52(Q<=HMS=:X;"+8HH.3NU_K@ M9*/L#X@*,M?E1MA0"P)T C K_KUY/K7G^L;@N[0!1!GP.A:B!+Q!=K &R # M** -A $\(!;.;GV5NWC -P!8IKMA3^R,5;&700Z0@?A@!\( &R"R,=;OVET% MP0;20!M( Q^6U,( /& $*J_EK;Q,X 7@736[>7%L@/VU1@'O@@ > )D !.( MLJLAY^Y<&'!Z/2\(( -O0,IB6!@[>+] X64#AM8H2-V36W5!P-4=LUGVY[4U;)CU^9N6Q!P!]! &F #!T'FUM[;JV\G@^.%O.1AZ:9>IRM]":_A M!0$E 1T7O?J$>S &T@#9( P9-F^@ -L0QDP#M7AVQJ'-B%_R<"8J+^"0>A& M"/JJ(.IO_'V_9(#^ N#["X!I@-X="RP!!#"!(1 #4 6B+(.V"[8 !L VA M#HBU$ $&W <8 .>P@VX 6*A)HB$!2P#'# $Q@(2. ? !N0:CW"S>V["/8N M?-@TP )$[-+-L# 8Q>Y?HAMXIZ_A[0&LE^4FWAB\>%=L#_"_0EC#FE@BO(/1 M+@C( T<8 %O8&]QNI2UNH+88EMC&W'>[!2Y"1N -21@[<-SEH'"S\'3@#MZ! M#'=AEU!S72_S=;[05RW@ 1,0 Z)L#\ /4?;?%MJBL( ;,-UEN2%7P.99HY & M>H!G8 A,-@T VCQ\@[/PD34*>W;)_MDGRXCG+>B]M?VF#;"2 MU@O !5SK V+")][$HM@HS%H>L"U.L>#UOK@7+KQBVVMXT=!@$P(,J:8P7,@#VQQQ6PH7@4Y]H: M<(KCL2JFM2#X';-;:&QH9_'MM<4@ !>C %WLBWMQ=PC&PYCN%N-CK'RYL;PE MN%N@&?\(?VQX ?$-'L1)=LDJ8FW\;\MQ)D;'ZI@3M^,_/&7M\:V=QVW6)*_B M5GQG*7(L-@HN&2 +9()^1RGXTW,AT=R2@8!J?@DEV)Z?&=5,CYNLRZY'T-CF9R+\< NKLD'N=0* M8YQ,C'=R0P8!TWA!Y 4X*Y1=L(#% U'8.,P E@N%\2_+;;[/-_JR6CILAS6Q M'A;)?O@LIV6B_(TWLCB>LDE9$Z_C3DR2$X!*1LE5&2J/XJORM6X M$.>'J< #KG$BYKI[EQMCY$C<(,)Q)2;'9D 5?^2EO)B=LCY&Q?)X*M=CR7R/ M=[,KMLPP&3.S8LWL$SAS<5[(@$$T)V,!^Y#5L$1VSK!8.0OBZ R$$W%UW@W7 M&Y59]?LD K'Z^89>_^E>66XAM@YCFLO[7"]1?&9"DAW07$-9JV/W* L96%=@(OUGAX/=!@&K-P;O'OYZX]0N30 !+2 J2"$M2[,I0U9=T0T8Z"K #* end