Random Generator

[Neil]

I was reading some recent posts & came across one about generating random sequences, I think it was jj who said that you need an outside influence to create truly random sequences. To that end I've adapted a routine from one of my programs whereby the keyboard is the outside influence, I've called it Password generator (it's not a cracker). The choice is 6 to 18 characters & these are generated from upper & lower case characters + the digits 0 to 9. I have made it so that each character can only be selected once, so to that end it is not truly random, more of a demo of what can be achieved. 12 'Passwords' can be saved of varying lengths so that they can be compared. If the moderators are happy with this post i'll upload the source.

[attachment deleted by admin]

[Neil]

Doesn't seem to be any complaints, so here's the source.
Use 'Console Assemble & Link' to build.

[attachment deleted by admin]

[Neil]

I've had another look at this program & decided that It could be made useful (my opinion). To that end I've removed the code that only allowed one instance of a character so that now it is about as random as you can get. I've also added a routine that allows you to save a password to a text file which makes it easy to copy & paste. Inside the zip file is a self extracting exe file that places the program in a folder in the root of drive C, no other changes are made so to remove it just delete the folder named 'Password'.
If anyone would like the source I'll be happy to post it.

[silentenigma]

Code Select Expand

http://www.sctzine.com/rastgele-sayi-ureteci-ve-gettickcount-rdtsc-nrandom-fonksiyonlari/

A random generator with sources. This is for newbies. Maybe useful!

[hutch--]

Neil,

It depends on how good a random sequence you need, the best stuff is external, the sound of the universe, radio noise, wind patterns on microphones etc .... but you will come close if you use a large external source and a pair of different random algos that repeatedly re-seed each other. The crypto guys are the fussiest and the actions is always on making the sequence unreproducable. Long ago I played with a 256 square pad that you scribbled on with the mouse until you got the sample size you wanted, it then checked if the range was large enough and rejected the result if it was too small.

If you have not already got it, get John Walker's ENT program, it is on the forum web site, does very useful analysis on random sequences.

[ToutEnMasm]

There is also a random generator in the crt library (c++ express 10) with source code in c.
Name rand_s.c.

[jj2007]

Code Select Expand

http://www.sctzine.com/rastgele-sayi-ureteci-ve-gettickcount-rdtsc-nrandom-fonksiyonlari/

A random generator with sources. This is for newbies. Maybe useful!

Not that useful, actually. Apart from the source being non-English, the code simply uses the Masm32 nrandom function that is documented in \masm32\help\masmlib.chm

[Neil]

Thanks for pointing out the link hutch, I've got it & will look at it when I've got time.
Going back to random, most peoples perception of random is nothing like reality. I remember a few years ago one of the universities did a test which went like this :-

A large number of students were given a blank sheet of A4 paper & told to put 1000 random dots on it, almost without fail they covered the sheet with a pretty uniform pattern of dots. Then they were given another sheet & told to put one dot anywhere on it, these dots were then combined onto one sheet & the result was very different. The sheet had clusters of dots with large blank spaces in between. This is how random works in the real world.

[jj2007]

It depends on how good a random sequence you need, the best stuff is external, the sound of the universe, radio noise, wind patterns on microphones etc...

Unless you need extreme security, I guess the (GetTickCount and 255) you get after a Sleep(0) is already pretty "random". Multiply it with PI, take the (whatever and 15)th decimal after the comma, and there you are with a namber between 0 and 9. Note this is not a high speed random generator, as Sleep(0) costs quite a bit of cycles.

[brethren]

on the subject of random number generators i've just done a quick asm translation of this version of the well512 rng http://www.lomont.org/Math/Papers/2008/Lomont_PRNG_2008.pdf

Code Select Expand

/* initialize state to random bits */
static unsigned long state[16];
/* init should also reset this to 0 */
static unsigned int index = 0;
/* return 32 bit random number */
unsigned long WELLRNG512(void)
   {
   unsigned long a, b, c, d;
   a = state[index];
   c = state[(index+13)&15];
   b = a^c^(a<<16)^(c<<15);
   c = state[(index+9)&15];
   c ^= (c>>11);
   a = state[index] = b^c;
   d = a^((a<<5)&0xDA442D20UL);
   index = (index + 15)&15;
   a = state[index];
   state[index] = a^b^d^(a<<2)^(b<<18)^(c<<28);
   return state[index];
   }


btw its only been quickly tested as i've not got round to writing a proc to seed the state so heres hoping there are no glaring errors:)

Code Select Expand

.data
state DWORD 16 DUP(?)    ;make sure you initialise the state to random bits
index DWORD 0            ;at init you should reset this to 0

;return 32 bit random number in eax
.code
WELLRNG512 PROC USES ebx ecx edx esi
    LOCAL tmp1:DWORD, tmp2:DWORD, tmp3:DWORD
    mov esi, index
    mov eax, state[esi*4]
    add esi, 13
    and esi, 15
    mov ecx, state[esi*4]
    mov tmp1, eax
    shl tmp1, 16
    mov tmp2, ecx
    shl tmp2, 15
    mov ebx, eax
    xor ebx, ecx
    xor ebx, tmp1
    xor ebx, tmp2
    mov esi, index
    add esi, 9
    and esi, 15
    mov ecx, state[esi*4]
    mov tmp1, ecx
    shr tmp1, 11
    xor ecx, tmp1
    mov esi, index
    mov tmp1, ebx
    xor tmp1, ecx
    mov eax, tmp1
    mov state[esi*4], eax
    shl tmp1, 5
    and tmp1, 0DA442D20h
    xor tmp1, eax
    mov edx, tmp1
    add index, 15
    and index, 15
    mov esi, index
    mov eax, state[esi*4]
    mov tmp1, eax
    shl tmp1, 2
    mov tmp2, ebx
    shl tmp2, 18
    mov tmp3, ecx
    shl tmp3, 28
    xor eax, ebx
    xor eax, edx
    xor eax, tmp1
    xor eax, tmp2
    xor eax, tmp3
    mov state[esi*4], eax

    ret
WELLRNG512 ENDP
END

[hutch--]

 :bg

JJ,

you would like my "quick and dirty" technique with GetTickCount. Convert it to string, reverse the string then chop a random offset of characters from the left side of the string and convert it back to an integer. I would not use it for crypto but it seems to do most things well and it is very hard to reproduce. I use this as a seeding technique to feed two different random algos that reseed each other while producing the random pad I am after.

[jj2007]

Hutch,
Sounds convincing. Why not start a little competition? Attached is a testbed that returns a number between 0 and 15 and counts its frequency:

Code Select Expand

15      499766
14      500351
13      499320
12      499228
11      499175
10      499827
9       500228
8       500401
7       499839
6       500762
5       499522
4       500195
3       500908
2       500337
1       500529
0       499613

Code size is 72 bytes only, and it's pretty fast, too.

[MichaelW]

Here is another test bed that in addition to the distribution also checks the arithmetic mean, and does a scatter plot. This version tests only Rand15.

Code Select Expand


;====================================================================
; Build as console app so print and printf will work.
;====================================================================
    include \masm32\include\masm32rt.inc
    .686
;====================================================================
    .data?
        array     dd    100000 dup(?)
    .data
        result    REAL8 ?
        counts    dd    16 dup(0)
        hInstance dd    0
        hDlg      dd    0
        hdc       dd    0
        msg       MSG   <>
        rc        RECT  <>
        sz        db    30 dup(0)
        ctr       dd    0
    .code
;====================================================================

Rand15 proc base:DWORD
.data?
r9Seed dd ?
.code
mov eax, r9Seed
push edx
push ecx
test eax, eax
jne @F
invoke Sleep, eax ; spend some cycles here and there
invoke GetTickCount ; get a seed value
mov r9Seed, eax
@@: ffree st(7) ; free a rarely used FP register
mov ecx, 0FFFFFFH
and eax, ecx
inc eax ; make sure it's not zero
push eax
fldpi ; push PI on FPU
fimul dword ptr [esp] ; 3.14159*[1...edx+1]
rdtsc ; we'll use only the loword
and eax, ecx ; and 0FFFFFFH
inc eax ; make sure it's not zero
mov [esp], eax ; second external influence is rdtsc
fimul dword ptr [esp] ; *(rdtsc and 0FFFFFFH)
pop eax
fstp r9Seed ; now a cheap trick: pop a Real4 from the FPU ...
mov eax, r9Seed ; ... but mov an integer ;-)
;and eax, 15 ; return a number between 0 and 15
xor edx, edx
mov ecx, base
div ecx
mov eax, edx
pop ecx ; restore two
pop edx ; precious registers
ret
Rand15 endp

;====================================================================

;-------------------------------------------------------
; This procedure calculates the arithmetic mean for the
; specified dword array and leaves the result in ST(0).
;-------------------------------------------------------

amean proc pddArray:DWORD, count:DWORD
    LOCAL sum:QWORD
    mov DWORD PTR [sum], 0
    mov DWORD PTR [sum+4], 0
    mov edx, pddArray
    mov ecx, count
    dec ecx
  @@:
    mov eax, [edx+ecx*4]
    add DWORD PTR [sum], eax
    adc DWORD PTR [sum+4], 0
    dec ecx
    jns @B
    finit
    fild sum
    fild count
    fdiv
    ret
amean endp

;====================================================================

DialogProc proc hwndDlg:DWORD, uMsg:DWORD, wParam:DWORD, lParam:DWORD

    SWITCH uMsg

      CASE WM_CTLCOLORDLG

        invoke GetStockObject, WHITE_BRUSH
        ret

      CASE WM_SIZE

        invoke InvalidateRgn, hwndDlg, NULL, TRUE

      CASE WM_CLOSE

        invoke DestroyWindow, hwndDlg

      CASE WM_DESTROY

        invoke PostQuitMessage, NULL

    ENDSW

    xor eax, eax
    ret

DialogProc endp

;====================================================================
start:
;====================================================================

    xor ebx, ebx
    .WHILE ebx < 8000000
        invoke Rand15, 16
        inc DWORD PTR [counts+eax*4]
        inc ebx
    .ENDW
    N=0
    REPEAT 16
        print str$(counts+N),13,10
        N=N+4
    ENDM

    xor ebx, ebx
    .WHILE ebx < 100000
        invoke Rand15, 16
        mov [array+ebx*4], eax
        inc ebx
    .ENDW
    invoke amean, ADDR array, 100000
    fstp result
    invoke crt_printf, cfm$("\n%f\n"), result


    invoke GetModuleHandle, NULL
    mov hInstance, eax

    Dialog "Test", \
           "FixedSys", 11, \
            WS_VISIBLE or WS_OVERLAPPEDWINDOW or \
            DS_CENTER, \
            0, \
            0,0,100,75, \
            1024

    CallModelessDialog hInstance, 0, DialogProc, NULL
    mov hDlg, eax

    invoke GetDC, hDlg
    mov hdc, eax

    invoke Sleep, 1000

  msgLoop:

    invoke PeekMessage, ADDR msg, NULL, 0, 0, PM_REMOVE
    .IF msg.message != WM_QUIT
      .IF eax != 0
        invoke TranslateMessage, ADDR msg
        invoke DispatchMessage, ADDR msg
      .ELSE
        invoke GetClientRect, hDlg, ADDR rc

        inc ctr
        cmp ctr, 1000
        jb  @f

        invoke szappend, ADDR sz, chr$("  "), 0
        mov esi, eax
        invoke szappend, ADDR sz, str$(rc.right), esi
        mov esi, eax
        invoke szappend, ADDR sz, chr$(" x "), esi
        mov esi, eax
        invoke szappend, ADDR sz, str$(rc.bottom), esi
        invoke SetWindowText, hDlg, ADDR sz
        mov ctr, 0

      @@:

        invoke Rand15, rc.right
        mov ebx, eax

        ;------------------------------------------
        ; Avoid a divide by zero when user resizes
        ; the dialog such that rc.bottom == 0.
        ;------------------------------------------

        .IF rc.bottom == 0
            mov rc.bottom, 1
        .ENDIF

        invoke Rand15, rc.bottom
        mov esi, eax
        invoke Rand15, 1 SHL 24
        mov edi, eax
        invoke SetPixel, hdc, ebx, esi, edi
      .ENDIF
      jmp msgLoop
    .ENDIF

    invoke ExitProcess, eax

;====================================================================
end start


[brethren]

heres the well512 random number generator i posted the other day:)
btw its been tested and its output matches the output from the reference implementation

anyway some info...

WELL Algorithm
Matsumoto (co-creator of the Mersenne Twister), L'Ecuyer (a major RNG researcher),
and Panneton introduced another class of TGFSR PRNGs in 2006 [Panneton06]. These
algorithms produce numbers with better equidistribution than MT19937 and improve
upon "bit-mixing" properties. WELL stands for "Well Equidistributed Long-period
Linear," and they seem to be better choices for anywhere MT19937 is currently used.
They are fast, come in many sizes, and produce higher quality random numbers.
WELL period sizes are presented for period 2^n for n = 512, 521, 607, 800, 1024, 19937,
21701, 23209, and 44497, with corresponding state sizes. This allows a user to trade
period length for state size. All run at similar speed. 2^512 is about 10^154, and it is
unlikely any video game will ever need that many random numbers, since it is far larger
then the number of particles in the universe. The larger periods ones aren't really needed
except for computation like weather modeling or earth simulations. A standard PC needs
over a googol7 of years to count to 2^512.
A significant place the WELL PRNGs perform better than MT19937 is in escaping states
with a large number of zeros. If MT19937 is seeded with many zeros, or somehow falls
into such a state, then the generated numbers have heavy bias towards zeros for a many
iterations. The WELL algorithms behave much better, escaping zero bias states quickly.
The only downside is that they are slightly slower than MT19937, but not much. The
upside is the numbers are considered to be higher quality, and the code is significantly
simpler. Here is WELL512 C/C++ code written by the author and placed in the public
domain8. It is about 40% faster than the code presented on L'Ecuyer's site, and is about
40% faster than MT19937 presented on Matsumoto's site.

[brethren]

here the ent results for 200000 random dword generated by the well512 algo

Entropy = 7.999756 bits per byte.

Optimum compression would reduce the size
of this 800000 byte file by 0 percent.

Chi square distribution for 800000 samples is 270.10, and randomly
would exceed this value 25.00 percent of the times.

Arithmetic mean value of data bytes is 127.5372 (127.5 = random).
Monte Carlo value for Pi is 3.146257866 (error 0.15 percent).
Serial correlation coefficient is -0.000857 (totally uncorrelated = 0.0).

and the same file using the -b flag

Entropy = 1.000000 bits per bit.

Optimum compression would reduce the size
of this 6400000 bit file by 0 percent.

Chi square distribution for 6400000 samples is 0.15, and randomly
would exceed this value 50.00 percent of the times.

Arithmetic mean value of data bits is 0.4999 (0.5 = random).
Monte Carlo value for Pi is 3.146257866 (error 0.15 percent).
Serial correlation coefficient is 0.000212 (totally uncorrelated = 0.0).