Results 1 to 22 of 22

Thread: rnd - simple pseudo random number generator

  1. #1
    The Founder encode's Avatar
    Join Date
    May 2006
    Location
    Moscow, Russia
    Posts
    3,954
    Thanks
    359
    Thanked 332 Times in 131 Posts
    OK, check out my simple random number generator. It's very small, simple and looks like generates nice random sequence with very long period, even taking into account that it has no tables.

    Usage:
    rnd file password

    file - output file. rnd will generate 128 MB long file with random numbers
    password - your password, used to seed the generator

    The core:
    Code:
     
    // 32-bit version 
    class TRnd { 
    private: 
      unsigned int x; 
    public: 
      TRnd(char *pwd) { 
        x=1; 
        for (int i=0; pwd[i]!=0; i++) 
          x=(x+pwd[i])*987660757; 
      } 
      int operator()() { 
        x*=123456791; 
        x=(x<<16)|(x>>16); 
        x*=234567891; 
        return (x>>24); 
      } 
    };
    Just a few lines of code.

    Have fun!


  2. #2
    The Founder encode's Avatar
    Join Date
    May 2006
    Location
    Moscow, Russia
    Posts
    3,954
    Thanks
    359
    Thanked 332 Times in 131 Posts
    Hm, interesting, is it possible to find the password using random number file?

    Can someone? (A la SHARND challenge! )

    The file:
    1.rnd (4 MB)

    The file has been generated using rnd.exe (the source posted above), the generated file length was restricted to 4 MB.


  3. #3
    The Founder encode's Avatar
    Join Date
    May 2006
    Location
    Moscow, Russia
    Posts
    3,954
    Thanks
    359
    Thanked 332 Times in 131 Posts
    This file looks like incompressible... I guess, I need feedback.

    Also post what do you think about this generator. Am I inventor or just a kid...

  4. #4
    Administrator Shelwien's Avatar
    Join Date
    May 2008
    Location
    Kharkov, Ukraine
    Posts
    3,134
    Thanks
    179
    Thanked 921 Times in 469 Posts
    > Hm, interesting, is it possible to find the password using random number file?
    > Can someone? (A la SHARND challenge! )
    > 1.rnd <http://www.encode.ru/downloads/1.rnd> (4 MB)

    Its not really possible.
    That is, there'd be too many candidates.
    But there's still only 2^32 possible key values,
    so its no problem to find the correct one even
    with dumb bruteforce, in like a hour.
    But even that is not needed actually, as its
    possible to calculate the key value with some
    discrete math, when function is like that.

    > The file has been generated using rnd.exe (the source posted above), the
    > generated file length was restricted to 4 MB.

    I'm too lazy to calculate it, but guess 16 bytes would be enough
    to restore the seed value. And with 4MB of statistics its quite
    possible to decrypt eg. the text xored with that sequence.

    > This file looks like incompressible... I guess, I need feedback.

    Well, that one is normal PRNG already, I'd say.
    Comparable to the one used in paq etc.

    > Also post what do you think about this generator. Am I inventor or just a kid...

    Yeah, go patent it
    Though better just invent something more surprising next time.

  5. #5
    The Founder encode's Avatar
    Join Date
    May 2006
    Location
    Moscow, Russia
    Posts
    3,954
    Thanks
    359
    Thanked 332 Times in 131 Posts
    I noticed that PAQ's rnd uses table driven algorithm. Also the standard C++ CRT rand() algo is extremely poor.

  6. #6
    The Founder encode's Avatar
    Join Date
    May 2006
    Location
    Moscow, Russia
    Posts
    3,954
    Thanks
    359
    Thanked 332 Times in 131 Posts
    Quote Originally Posted by Shelwien
    But theres still only 2^32 possible key values,
    OK, 64-bit version:
    rnd.zip (30 KB)


  7. #7
    The Founder encode's Avatar
    Join Date
    May 2006
    Location
    Moscow, Russia
    Posts
    3,954
    Thanks
    359
    Thanked 332 Times in 131 Posts
    Code:
    class TRnd { 
    private: 
      unsigned __int64 x; 
    public: 
      TRnd(char *s) { 
        x=1; 
        for (int i=0; s[i]!=0; i++) 
          x=(x+s[i])*987660757; 
      } 
      int operator()() { 
        x*=123456791; 
        x=(x<<32)+(x>>32); 
        x*=234567891; 
        return ((x>>24)&255); 
      } 
    };
    Here we still use, 32-bit primes. That's why we use (x>>24). So, it can be regarded as an extended 32-bit version.

  8. #8
    Administrator Shelwien's Avatar
    Join Date
    May 2008
    Location
    Kharkov, Ukraine
    Posts
    3,134
    Thanks
    179
    Thanked 921 Times in 469 Posts
    Your seed is always a multiple of 987660757, so its around 34 bits of information actually. Look at md5 implementation or something...

  9. #9
    The Founder encode's Avatar
    Join Date
    May 2006
    Location
    Moscow, Russia
    Posts
    3,954
    Thanks
    359
    Thanked 332 Times in 131 Posts
    Delphi/ASM routine:
    Code:
    function GetRnd: Cardinal; 
    asm 
      MOV EAX, Seed 
      IMUL EAX, 123456791 
      ROL EAX, 16 
      IMUL EAX, 234567891 
      MOV Seed, EAX 
      SHR EAX, 24 
    end;

  10. #10
    The Founder encode's Avatar
    Join Date
    May 2006
    Location
    Moscow, Russia
    Posts
    3,954
    Thanks
    359
    Thanked 332 Times in 131 Posts
    Pure Delphi:

    Code:
    procedure SetPwd(S: string); 
    var 
      I: Integer; 
    begin 
      Seed := 1; 
      for I := 1 to Length(S) do 
        Seed := (Seed + Cardinal(S[I])) * 987660757; 
    end; 
     
    function GetRnd: Cardinal; 
    begin 
      Seed := Seed * 123456791; 
      Seed := (Seed shl 16) or (Seed shr 16); 
      Seed := Seed * 234567891; 
      Result := Seed shr 24; 
    end;

  11. #11
    The Founder encode's Avatar
    Join Date
    May 2006
    Location
    Moscow, Russia
    Posts
    3,954
    Thanks
    359
    Thanked 332 Times in 131 Posts
    In short:
    Code:
    class TRnd { 
    private: 
      unsigned int x; 
    public: 
      TRnd(char *s) { 
        x=1; 
        for (int i=0; s[i]!=0; i++) 
          x=(x+s[i])*987660757; 
      } 
      int operator()() { 
        return ((x=(_rotl((x*123456791), 16)*234567891))>>24); 
      } 
    };

  12. #12
    Moderator

    Join Date
    May 2008
    Location
    Tristan da Cunha
    Posts
    2,034
    Thanks
    0
    Thanked 4 Times in 4 Posts
    Thanks for the PRNG Ilia!

  13. #13
    The Founder encode's Avatar
    Join Date
    May 2006
    Location
    Moscow, Russia
    Posts
    3,954
    Thanks
    359
    Thanked 332 Times in 131 Posts
    Hopefully, I will write some small file encryptor on Delphi based on this RND engine.

  14. #14
    The Founder encode's Avatar
    Join Date
    May 2006
    Location
    Moscow, Russia
    Posts
    3,954
    Thanks
    359
    Thanked 332 Times in 131 Posts
    By the way, to enhance security we can:
    + Add absolutely random bytes at the beginning of a file (user can strike any keys on a keyboard)
    + Do not use any CRCs. So bruteforce cannot be done for unknown data.
    + Use multiple generators with different keys + one for generator/generators selection.

    Code:
     
    RNDSelector -> RNDGen1..4 
                         -> RNDGen1..4 xor RNDGen1..4
    Rnd selector generates a pseudo random number and using this number we accordinly use one or more generators together...


  15. #15
    Administrator Shelwien's Avatar
    Join Date
    May 2008
    Location
    Kharkov, Ukraine
    Posts
    3,134
    Thanks
    179
    Thanked 921 Times in 469 Posts
    > By the way, to enhance security we can:
    > + Add absolutely random bytes at the beginning of a file (user can strike any
    > keys on a keyboard)

    Won't help much with algorithm like that as it won't use more
    information than seed size.

    > + Do not use any CRCs. So bruteforce cannot be done for unknown data.

    With uncompressed data that won't change anything.
    And with LZ compression there might be "impossible sequences".
    But proper compression really helps.
    Also CRC for error correction can be calculated over encrypted data.
    And CRC for decoding validation can be encoded into compressed stream,
    so impossible to check without full decoding.

    > + Use multiple generators with different keys + one for generator/generators
    > selection.

    One really working idea for a change

  16. #16
    The Founder encode's Avatar
    Join Date
    May 2006
    Location
    Moscow, Russia
    Posts
    3,954
    Thanks
    359
    Thanked 332 Times in 131 Posts
    Re uploaded the file:
    rnd.zip (33 KB)

    Now RND uses two PRNG.

    The core:
    Code:
    class TRnd { 
    private: 
      unsigned int x1; 
      unsigned int x2; 
    public: 
      TRnd(char *s) { 
        x1=1; 
        x2=1; 
        for (int i=0; s[i]!=0; i++) { 
          x1=(x1+s[i])*987660757; 
          x2=(x2+s[i])*345689647; 
        } 
      } 
      int operator()() { 
        x1=_rotl((x1*123456791), 16)*234567891; 
        x2=_rotl((x2*234577751), 16)*876546821; 
        return ((x1^x2)>>24); 
      } 
    };

  17. #17
    Expert
    Matt Mahoney's Avatar
    Join Date
    May 2008
    Location
    Melbourne, Florida, USA
    Posts
    3,255
    Thanks
    306
    Thanked 778 Times in 485 Posts
    Quote Originally Posted by Shelwien
    > Also post what do you think about this generator. Am I inventor or just a kid...

    Yeah, go patent it
    Though better just invent something more surprising next time.
    Prior art! Here is a little code snip from lpaq1.

    <div class=""jscript""><pre>
    template <int B>
    inline U8* HashTable<B>:perator[](U32 i) {
    i*=123456791;
    i=i<<16|i>>16;
    i*=234567891;
    int chk=i>>24;
    [/code]

  18. #18
    The Founder encode's Avatar
    Join Date
    May 2006
    Location
    Moscow, Russia
    Posts
    3,954
    Thanks
    359
    Thanked 332 Times in 131 Posts
    Quote Originally Posted by Matt Mahoney
    Prior art! Here is a little code snip from lpaq1.
    Yep!

    OK, Ive done some changes:
    rnd.zip (33 KB)

    The core:
    <div class=""jscript""><pre>class TRnd {
    private:
    unsigned int s1;
    unsigned int r1;
    unsigned int r2;
    public:
    TRnd(char *p) {
    int n=strlen(p);
    s1=((n>>1)+1)*251;
    r1=(n*101)+1;
    r2=(n*103)+1;
    for (int i=0; i<n; i++) {
    s1=(s1+p[(n-1)-i])*876546821;
    r1=(r1+p[i])*987660757;
    r2=(r2+p[i])*345689647;
    }
    }
    int operator()() {
    s1=_rotl((s1*789123473), 16)*678913561;
    r1=_rotl((r1*123456791), 16)*567891217;
    r2=_rotl((r2*456765059), 16)*234577751;
    unsigned int r=0;
    if ((s1>>20)&1) r^=r1;
    if ((s1>>20)&2) r^=r2;
    if (!r) r=s1;
    return (r>>24);
    }
    };[/code]

    New RND consists from three independent generators - one so called selector (S1) and two generators (R1, R2). Based on selector the PRNG output is:
    R1
    R2
    R1+R2
    S1

  19. #19
    Administrator Shelwien's Avatar
    Join Date
    May 2008
    Location
    Kharkov, Ukraine
    Posts
    3,134
    Thanks
    179
    Thanked 921 Times in 469 Posts
    Code:
     
    >     unsigned int r=0; 
    >     if ((s1>>20)&1) r^=r1; 
    >     if ((s1>>20)&2) r^=r2; 
    >     if (!r) r=s1; 
    >     return (r>>24); 
    > R1      s1[20..21]=10 
    > R2      s1[20..21]=01 
    > R1+R2   s1[20..21]=11 
    > S1      s1[20..21]=00

    > New RND consists from three independent generators - one so called selector (S1)
    > and two generators (R1, R2). Based on selector the PRNG output is:

    I think you've broken it now, as distribution of s1[24..31] probably
    correlates with s1[20..21] and in 25% cases you output s1[24..31] with
    known s1[20..21]==0.

    Also afaik its better to simply xor all 3 generators.

  20. #20
    The Founder encode's Avatar
    Join Date
    May 2006
    Location
    Moscow, Russia
    Posts
    3,954
    Thanks
    359
    Thanked 332 Times in 131 Posts
    OK, then we can do something like this:
    rnd.zip (34 KB)

    Core (Four PRNGs XORed together):
    Code:
    class TRnd { 
    private: 
      unsigned int r[4]; 
    public: 
      TRnd(char *s) { 
        memset(&r, 0, sizeof(r)); 
        int n=strlen(s); 
        for (int i=0; i<n; i++) { 
          r[0]=(r[0]+s[(n-1)-i])*972694033; 
          r[1]=(r[1]+s[(n-1)-i])*382491853; 
          r[2]=(r[2]+s[i])*788931739; 
          r[3]=(r[3]+s[i])*107571329; 
        } 
      } 
      int operator()() { 
        r[0]=_rotl((r[0]*167015977), 16)*215602549; 
        r[1]=_rotl((r[1]*817499983), 16)*193186571; 
        r[2]=_rotl((r[2]*499770923), 16)*970939267; 
        r[3]=_rotl((r[3]*683066977), 16)*512268461; 
        return (((r[0]^r[1])^(r[2]^r[3]))>>24); 
      } 
    };

  21. #21
    Administrator Shelwien's Avatar
    Join Date
    May 2008
    Location
    Kharkov, Ukraine
    Posts
    3,134
    Thanks
    179
    Thanked 921 Times in 469 Posts
    Code:
     
    >     r[0]=_rotl((r[0]*167015977), 16)*215602549; 
    >     r[1]=_rotl((r[1]*817499983), 16)*193186571; 
    >     r[2]=_rotl((r[2]*499770923), 16)*970939267; 
    >     r[3]=_rotl((r[3]*683066977), 16)*512268461; 
    >     return (((r[0]^r[1])^(r[2]^r[3]))>>24);

    Well, now you can remove half of multiplications
    because they don't really help.

    x*215602549*167015977 = x*36009070364925373 = x*130751933

    And some more suggestions:
    1. several different multipliers are better than one,
    so you can make it r[1]=f(r[0]) etc, or even swap the
    states randomly.
    2. ROL reg,16 isn't any better than ROL reg,15 so you
    can add some variation.
    3. Seems that IntelC is able to generate a normal 32*32=64 MUL instruction, so something like this is possible:
    Code:
     
    ;;;   volatile uint r = 123; 
            mov       DWORD PTR [esp+8], 123 
    ;;;   qword tmp = r; 
    ;;;   tmp *= 167015977; 
            mov       eax, 167015977 
            mul       DWORD PTR [esp+8] 
    ;;;   r = (tmp>>32)^tmp; 
            xor       edx, eax 
            mov       DWORD PTR [esp+8], edx

  22. #22
    Expert
    Matt Mahoney's Avatar
    Join Date
    May 2008
    Location
    Melbourne, Florida, USA
    Posts
    3,255
    Thanks
    306
    Thanked 778 Times in 485 Posts
    Quote Originally Posted by Shelwien
    Seems that IntelC is able to generate a normal 32*32=64 MUL instruction
    So does g++ 3.4.2

    <div class=""jscript""><pre>
    C:&#92;tmp>type a.cpp
    extern "C" unsigned int f(unsigned int a, unsigned int b) {
    return (unsigned long long)a*b>>32;
    }

    C:&#92;tmp>g++ -S -O -fomit-frame-pointer a.cpp

    C:&#92;tmp>type a.S
    .file "a.cpp"
    .text
    .align 2
    .globl _f
    .def _f; .scl 2; .type 32; .endef
    _f:
    movl 8(%esp), %eax
    mull 4(%esp)
    movl %edx, %eax
    ret
    [/code]

Similar Threads

  1. Test data generator
    By Lasse Reinhold in forum Data Compression
    Replies: 1
    Last Post: 28th February 2010, 14:53
  2. goodbye and some random thoughts
    By Christian in forum The Off-Topic Lounge
    Replies: 72
    Last Post: 25th January 2010, 05:40
  3. Searching for special file generator
    By nimdamsk in forum Data Compression
    Replies: 5
    Last Post: 19th March 2009, 01:33
  4. Dark Space Random Thoughts
    By Tribune in forum The Off-Topic Lounge
    Replies: 19
    Last Post: 14th March 2009, 15:22
  5. Random Data Question.
    By Tribune in forum Data Compression
    Replies: 7
    Last Post: 13th June 2008, 19:30

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •