Announcement

Collapse
No announcement yet.

PB Rnd() keyspace size

Collapse
X
 
  • Filter
  • Time
  • Show
Clear All
new posts

  • PB Rnd() keyspace size

    Has anyone investigated what the key size is for the PB Rnd() statement?

    I did some searches of the forum and there was some hints:

    Someone found the cycle to be 2^32
    Someone found the keyspace using "randomize timer" only but suspected a large keyspace using other numbers.

    My question is, how many possible seeds are there that produce different random number sets? There is a hint in the docs that the randomize seeds are of type single (as the example uses CVS() ) but this just a hint really.

    People seems quite impressed by the way that RND stacked up in generator testers so if I had a one-time-pad generator for encryption, how many possible 2^32 length pads can I generate? or how many does a cracker have to generate to brute force the keyspace?

    Given that Y-rnd() where Y is an extended type according to the docs, it's not going to be over 80bits in length, but if I init randomise with an extended type will every possible number I pass produce a different set or does this ext get converted to a single first bringing me back to 32bits?

    (this is not intended as an algorithm debate, just the PB Rnd() keysize)

    ------------------
    Paul Dwyer
    Network Engineer
    Aussie in Tokyo



    [This message has been edited by Paul Dwyer (edited July 29, 2004).]

  • #2
    [deleted]

    [This message has been edited by Eddy Van Esch (edited July 29, 2004).]
    Eddy

    Comment


    • #3


      got a nibble on my thread but he got away!

      Maybe I need better bait

      ------------------
      Paul Dwyer
      Network Engineer
      Aussie in Tokyo

      Comment


      • #4
        Paul,
        the PB random number generator is 32 bit. It'll repeat after 2^32 numbers. It's easy enough to verify, run this..
        Code:
        FUNCTION PBMAIN()
        a##=RND()
        DO
           q&&=q&&+1
           IF a##=RND() THEN PRINT q&&
           LOOP
         
        END FUNCTION
        ..and note the period of the printed numbers.

        Code:
        My question is, how many possible seeds are there that produce different random number sets?
        There is likely to be a single sequence of 2^32 numbers and the seed determines where in that sequence you start.

        If you want more control overthe random numbers than this then write your own random number generator, there are plenty of examples around.

        Paul.


        ------------------

        Comment


        • #5
          It's bigger than 2^32!

          I'm looping though them now with the seed set on a quad.

          I've done 5,000,000,000 seeds so far with no match so I'll see how far I get. It takes my poor work PC about 30mins to loop 2^32.

          The random numbers for a given seed looped at 2^32 (exactly) though.

          according to the docs

          RND and RND() return a random Extended-precision value that is less than 1, but greater than or equal to 0.
          So it could be larger than the Quad seed loop I'm using

          ------------------
          Paul Dwyer
          Network Engineer
          Aussie in Tokyo

          Comment


          • #6
            10 billion, no match.

            I calculate it will take me 140,386 years at this pace with my work pc to go though 63bits of the possitive side of a quad.

            I might not even hit a match then as an ext is 80bits.

            Anyone interested in taking part in a distributed computing experiment?

            ------------------
            Paul Dwyer
            Network Engineer
            Aussie in Tokyo

            Comment


            • #7
              Paul,

              Give me the range you want for me to check, and the code you want
              me to use to check it, and I'll get her going.


              ------------------
              mailto:[email protected][email protected]</A>

              Comment


              • #8
                Cheers Clay!

                I'm up to about 25 billion so far.

                Perhaps if you start at 100 billion. I'm not sure how much power you are putting in.
                This will log progress and matches which we will need to check for false possitives but I haven't got any yet.

                change
                For Seedloop = 1 To 9223372036854775807
                to
                For Seedloop = 100000000000 To 9223372036854775807

                I think that running different loops in 2 or more threads would better take advantage of systems with multiple CPUs,
                I tried this on a server here for a brief test and it only ran on one of the CPUs according to taskman

                Code:
                #Compile Exe
                
                Function PbMain() As Long
                
                    Dim Seedloop As Quad 
                    Dim Checkloop As Long    
                    Dim RndNumbers(1 To 9) As Long  'if the first 9 match we might have it so we'll log these
                    Dim hFile As Long
                    
                    Randomize 1                     'The seed we are looking for a double of
                        RndNumbers(1) = Rnd(1,2147483647 ) 
                        RndNumbers(2) = Rnd(1,2147483647 )
                        RndNumbers(3) = Rnd(1,2147483647 )
                        RndNumbers(4) = Rnd(1,2147483647 )
                        RndNumbers(5) = Rnd(1,2147483647 )
                        RndNumbers(6) = Rnd(1,2147483647 )
                        RndNumbers(7) = Rnd(1,2147483647 )
                        RndNumbers(8) = Rnd(1,2147483647 )
                        RndNumbers(9) = Rnd(1,2147483647 ) 
                        
                    hFile = FreeFile
                    Open "C:\RndBrute.txt" For Append As hFile
                        Print # hfile, Date$ & " "& Time$ & " Starting...  "
                    Close hfile
                    
                    
                    For Seedloop = 1 To 9223372036854775807  '9,223,372,036,854,775,807
                    
                        Randomize seedloop
                        
                        If Rnd(1,2147483647) = RndNumbers(1) Then
                            If  Rnd(1,2147483647) = RndNumbers(2) Then   
                                If  Rnd(1,2147483647) = RndNumbers(3) Then
                                    If  Rnd(1,2147483647) = RndNumbers(4) Then
                                        If  Rnd(1,2147483647) = RndNumbers(5) Then
                                            If  Rnd(1,2147483647) = RndNumbers(6) Then
                                                If  Rnd(1,2147483647) = RndNumbers(7) Then
                                                    If  Rnd(1,2147483647) = RndNumbers(8) Then
                                                        If  Rnd(1,2147483647) = RndNumbers(9) Then
                                                            
                                                            hFile = FreeFile
                                                            Open "C:\RndBrute.txt" For Append As hFile
                                                                Print # hfile, Date$ & " "& Time$ & " Possible crack at seed: " & Format$(seedloop) 
                                                            Close hfile
                                                             
                                                        End If
                                                    End If
                                                End If
                                            End If
                                        End If
                                    End If
                                End If  
                            End If
                        End If
                
                        If seedloop Mod 1000000000 = 0 Then   'update the log every billion checks (5mins or so on my PC)
                            hFile = FreeFile
                            Open "C:\RndBrute.txt" For Append As hFile
                                Print # hfile, Date$ & " "& Time$ & " Seed Marker " & Format$(seedloop) & " Passed!"
                            Close hfile
                        End If    
                    
                    Next
                    
                    hFile = FreeFile
                    Open "C:\RndBrute.txt" For Append As hFile
                        Print # hfile, Date$ & " "& Time$ & " Loop Completed at seed " & Format$(seedloop -1)  
                    Close hfile
                                  
                End Function
                ------------------
                Paul Dwyer
                Network Engineer
                Aussie in Tokyo

                [This message has been edited by Paul Dwyer (edited August 02, 2004).]

                Comment


                • #9
                  don't those IF's look ugly though?

                  ------------------
                  Paul Dwyer
                  Network Engineer
                  Aussie in Tokyo

                  Comment


                  • #10
                    Hmmmm...what kind of system are you running the test on? I am trying
                    to form a guesstimate of how long my code will need to run until
                    it ends. My system is a PIII 600EB with XP Pro.

                    If the code takes all night to complete on my machine, that's OK.
                    It is already 23:25 hours here, and I have to be at the bank
                    promptly at 09:00 hours tomorrow, so I am up for the whole night.
                    In other words, I've got all night to kill.

                    JFYI, I had experimented with the exact same thing a long time ago.
                    If you want some surprising results, run your main loop BACKWARDS,
                    from %MAXQUAD to 1 STEP -1. It wasn't until I got down to a significantly
                    lower number than %MAXQUAD before the RND() stopped returning the same sequence.
                    Same thing when counting a LONG loop backwards (i.e., %MAXLONG to 1 STEP -1).

                    At any rate, you have my curisoity piqued, so I will resume my old tests as before.
                    I will use my own code, and count backwards from %MAXQUAD to %MINQUAD STEP -1.




                    ------------------
                    mailto:[email protected][email protected]</A>

                    Comment


                    • #11
                      #IF 0
                      OK, I just ran a simple test. Here is the code - you should
                      amend it so it compiles for you, then run it yourself - I think you
                      will be surprised:

                      ADDED: I will try to change it myself your can just copy-n-paste-compile.
                      #ENDIF


                      Code:
                      #COMPILE EXE
                      
                      DEFQUD Q
                      DEFLNG L, F
                      
                      
                      FUNCTION PBMAIN
                          Q = &H7FFFFFFFFFFFFFFF&&
                          DIM a1(1 TO 20) AS LOCAL LONG
                          DIM a2(1 TO 20) AS LOCAL LONG
                          RANDOMIZE Q
                          FOR L1 = 1 TO 20
                              a1(L1) = RND(&H80000000&, &H7FFFFFFF&)
                          NEXT
                          FOR L1 = 0 TO 62
                              BIT RESET Q, L1
                              RANDOMIZE Q
                              FOR L2 = 1 TO 20
                                  a2(L2) = RND(&H80000000&, &H7FFFFFFF&)
                              NEXT
                              RESET flaga
                              FOR L2 = 1 TO 20
                                  IF a1(L2) <> a2(L2) THEN flaga = -1
                                  a1(L2) = a2(L2)
                              NEXT
                              IF flaga THEN
                                  local dptr as dword ptr
                                  dptr = varptr(q)
                                  OPEN "test.txt" FOR OUTPUT AS #1
                                  PRINT #1, format$(q, "#,")
                                  PRINT #1, hex$(@dptr[1], 8) + hex$(@dptr[0], 8)
                                  PRINT #1, bin$(@dptr[1], 32) + bin$(@dptr[0], 32)
                                  CLOSE #1
                                  EXIT FOR
                              END IF
                          NEXT
                          msgbox "done"
                      END FUNCTION

                      ------------------
                      mailto:[email protected][email protected]</A>

                      Comment


                      • #12
                        Clay,

                        You have me a little lost.

                        Am I supposed to change the numbers here so that they don't just run 0-62?

                        I got this output

                        Code:
                        9,223,371,487,098,961,920
                        7FFFFF8000000000
                        0111111111111111111111111000000000000000000000000000000000000000
                        but I don't know what to do with it


                        ------------------
                        Paul Dwyer
                        Network Engineer
                        Aussie in Tokyo

                        Comment


                        • #13
                          Paul,

                          That test code I posted gives you an example of what I was trying
                          to say about QUAD's (or LONG's/DWORD's) when they're used as
                          the arguments for RANDOMIZE. What it illustrates is that if the
                          HIGH range of the argument is beyond a certain point, then MINOR
                          differences in the argument will not generate different patterns
                          returned from RND().

                          I found that stuff out a long time ago when I was trying to make the
                          MP3 player program I wrote as random as possible.


                          ------------------
                          mailto:[email protected][email protected]</A>

                          Comment


                          • #14
                            Really,

                            So something like 2^32 and (2^32) -1 in a dword seed are likely to generate the same sequense?

                            While working on other things, my PC has almost checked 40 billion seeds so far looking for a match on the values given by seed 1 with no success.

                            I want to atleast check the first 100bill for when I come into work tomorrow. After that I'll see if there is any interested in people donating CPU time before I bother to continue.



                            ------------------
                            Paul Dwyer
                            Network Engineer
                            Aussie in Tokyo

                            Comment


                            • #15
                              Paul,

                              That's the results I've come up with. And, that "high range" limit
                              after which minor changes in the argument to RANDOMIZE do not cause
                              changes in the returns from RND() seems
                              to be based on what TYPE of argument is used for RANDOMIZE.
                              In other words, if you use a QUAD as the argument to RANDOMIZE,
                              then that high limit will be a larger number than what it would for
                              a LONG or DWORD argument.

                              However, I am the FIRST to admit that I sometimes "jump the gun"
                              after such "observations" by myself. It could very well be that
                              my test coding, that time long ago, and this time tonight, is flawed.


                              ------------------
                              mailto:[email protected][email protected]</A>

                              Comment


                              • #16
                                Hmmmm....I just ran three tests, one using DWORD for the RANDOMIZE argument,
                                one using LONG, and one using QUAD. All three showed a repeat
                                in 20 RND()'s between seed numbers 16,777,216 and 16,777,217.

                                If anybody needs to see the test code, I suppose I could recreate it
                                easily enough. Note that in each iteration of the seed loop, it only
                                compared each iteration with the previous iteration.


                                ------------------
                                mailto:[email protected][email protected]</A>

                                Comment


                                • #17
                                  Clay,

                                  I just tested the last three seeds in a quad

                                  9223372036854775807
                                  9223372036854775806
                                  9223372036854775805

                                  and got the same sequence

                                  so you are right, at some stage the series stops before the end of the type's max.

                                  I wondering if you could determine that with the Timer as the seed that after a certain time all the sequences are the same!!! that could be a problem for people using the timer to get a different series, in fact we'd be getting close to the "B" word

                                  ------------------
                                  Paul Dwyer
                                  Network Engineer
                                  Aussie in Tokyo

                                  [This message has been edited by Paul Dwyer (edited August 02, 2004).]

                                  Comment


                                  • #18
                                    No, using RANDOMIZE TIMER should be OK, as there are only
                                    86,400 seconds in a day, and those three tests I ran just
                                    a little while ago (plus one test just now) shows that there
                                    will be a unique RND() sequence for the seeds -16,777,216 to +16,777,216.


                                    ------------------
                                    mailto:[email protected][email protected]</A>

                                    Comment


                                    • #19
                                      hmmmm....

                                      Looks like there's a little more to it than that though.

                                      Setting the search seed to 20,000,000 I ran a scan of 1-50,000,000 and got three matches,
                                      one on either side of the number too (My PC's CPU is rather busy so this was a little slow)

                                      08-02-2004 16:33:53 Starting...
                                      08-02-2004 16:33:55 Seed Marker 1000000 Passed!
                                      08-02-2004 16:33:56 Seed Marker 2000000 Passed!
                                      08-02-2004 16:33:57 Seed Marker 3000000 Passed!
                                      08-02-2004 16:33:58 Seed Marker 4000000 Passed!
                                      08-02-2004 16:33:59 Seed Marker 5000000 Passed!
                                      08-02-2004 16:34:00 Seed Marker 6000000 Passed!
                                      08-02-2004 16:34:01 Seed Marker 7000000 Passed!
                                      08-02-2004 16:34:02 Seed Marker 8000000 Passed!
                                      08-02-2004 16:34:03 Seed Marker 9000000 Passed!
                                      08-02-2004 16:34:04 Seed Marker 10000000 Passed!
                                      08-02-2004 16:34:06 Seed Marker 11000000 Passed!
                                      08-02-2004 16:34:07 Seed Marker 12000000 Passed!
                                      08-02-2004 16:34:08 Seed Marker 13000000 Passed!
                                      08-02-2004 16:34:09 Seed Marker 14000000 Passed!
                                      08-02-2004 16:34:10 Seed Marker 15000000 Passed!
                                      08-02-2004 16:34:11 Seed Marker 16000000 Passed!
                                      08-02-2004 16:34:12 Seed Marker 17000000 Passed!
                                      08-02-2004 16:34:13 Seed Marker 18000000 Passed!
                                      08-02-2004 16:34:14 Seed Marker 19000000 Passed!
                                      08-02-2004 16:34:15 Possible crack at seed: 19999999
                                      08-02-2004 16:34:15 Possible crack at seed: 20000000
                                      08-02-2004 16:34:16 Seed Marker 20000000 Passed!
                                      08-02-2004 16:34:16 Possible crack at seed: 20000001
                                      08-02-2004 16:34:17 Seed Marker 21000000 Passed!
                                      08-02-2004 16:34:18 Seed Marker 22000000 Passed!
                                      08-02-2004 16:34:19 Seed Marker 23000000 Passed!
                                      08-02-2004 16:34:20 Seed Marker 24000000 Passed!
                                      08-02-2004 16:34:21 Seed Marker 25000000 Passed!
                                      08-02-2004 16:34:22 Seed Marker 26000000 Passed!
                                      08-02-2004 16:34:23 Seed Marker 27000000 Passed!
                                      08-02-2004 16:34:24 Seed Marker 28000000 Passed!
                                      08-02-2004 16:34:25 Seed Marker 29000000 Passed!
                                      08-02-2004 16:34:26 Seed Marker 30000000 Passed!
                                      08-02-2004 16:34:27 Seed Marker 31000000 Passed!
                                      08-02-2004 16:34:28 Seed Marker 32000000 Passed!
                                      08-02-2004 16:34:30 Seed Marker 33000000 Passed!
                                      08-02-2004 16:34:31 Seed Marker 34000000 Passed!
                                      08-02-2004 16:34:32 Seed Marker 35000000 Passed!
                                      08-02-2004 16:34:33 Seed Marker 36000000 Passed!
                                      08-02-2004 16:34:34 Seed Marker 37000000 Passed!
                                      08-02-2004 16:34:35 Seed Marker 38000000 Passed!
                                      08-02-2004 16:34:36 Seed Marker 39000000 Passed!
                                      08-02-2004 16:34:37 Seed Marker 40000000 Passed!
                                      08-02-2004 16:34:38 Seed Marker 41000000 Passed!
                                      08-02-2004 16:34:39 Seed Marker 42000000 Passed!
                                      08-02-2004 16:34:40 Seed Marker 43000000 Passed!
                                      08-02-2004 16:34:41 Seed Marker 44000000 Passed!
                                      08-02-2004 16:34:42 Seed Marker 45000000 Passed!
                                      08-02-2004 16:34:43 Seed Marker 46000000 Passed!
                                      08-02-2004 16:34:44 Seed Marker 47000000 Passed!
                                      08-02-2004 16:34:45 Seed Marker 48000000 Passed!
                                      08-02-2004 16:34:46 Seed Marker 49000000 Passed!
                                      08-02-2004 16:34:48 Seed Marker 50000000 Passed!
                                      08-02-2004 16:34:48 Loop Completed at seed 50000000

                                      ------------------
                                      Paul Dwyer
                                      Network Engineer
                                      Aussie in Tokyo

                                      Comment


                                      • #20
                                        other times is fine though

                                        08-02-2004 16:38:16 Starting...
                                        08-02-2004 16:38:26 Seed Marker 10000000 Passed!
                                        08-02-2004 16:38:36 Seed Marker 20000000 Passed!
                                        08-02-2004 16:38:39 Possible crack at seed: 22222222
                                        08-02-2004 16:38:47 Seed Marker 30000000 Passed!
                                        08-02-2004 16:38:57 Seed Marker 40000000 Passed!
                                        08-02-2004 16:39:08 Seed Marker 50000000 Passed!
                                        08-02-2004 16:39:08 Loop Completed at seed 50000000

                                        ------------------
                                        Paul Dwyer
                                        Network Engineer
                                        Aussie in Tokyo

                                        Comment

                                        Working...
                                        X