Announcement

Collapse
No announcement yet.

BCryptGenRandom Output

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

  • Ribeiro Alvo
    replied
    David

    It looks like zeros are generated, which answers the question. However I only have version 5 of the PB Console and your code does not run on it.

    Leave a comment:


  • David Roberts
    replied
    Originally posted by Ribeiro
    For that to happen, an exhaustive search (a large number of iterations) will be necessary.
    Point taken.

    BTW, your code needs Print j and not Print i.

    OK, try this.

    Find the maximum minimum brute force value of j for 1000 trials.

    It is better to use Log2.

    A session takes about 11 seconds on my machine.

    Code:
    Function PBMain
    Local hRand As Dword
    Local Result As Integer
    Local j As QUAD
    Local i, lMax As Long
     
    BCryptOpenAlgorithmProvider(hRand, $$BCRYPT_RNG_ALGORITHM, $$Nul, 0)
     
    For i = 1 to 1000
      For j = 1 To 1152921504606846976  '2^60
       BCryptGenRandom(hRand, VarPtr(Result), 2, 0)
       If Result = 0 Then Exit For
      Next
      If j > lmax Then lMax = j
    Next
    Print Log2(lMax)
    BCryptCloseAlgorithmProvider(hRand, 0)
    Waitkey$
    End Function
    With five sessions, I get 18.8, 18.7, 19.1, 19.0, and 18.8.

    So with an expected value of 2^15 we could find ourselves waiting until about 2^19 before a zero occurs; which is still less likely than being struck by lightning in the UK, but only half as much. Gulp!

    Leave a comment:


  • Ribeiro Alvo
    replied
    David, Hi

    Originally posted by David Roberts View Post

    ...
    Your code only does one test - mine calculates an average of 10,000 tests.
    ...
    What is sought here is to know if this algorithm generates zeros.
    This piece of code uses brute force to find zero.
    For that to happen, an exhaustive search (a large number of iterations) will be necessary.
    Even so, if a zero is never found, this does not prove that the generator produces them.
    It is a matter of mathematical analysis to the generator in question.

    Leave a comment:


  • David Roberts
    replied
    Hi Ribeiro

    Since we are populating an integer, -2^15 to 2^15 -1, the chance of getting anywhere near 2^60 iterations before we see a zero is highly unlikely with the expected number of iterations being 2^15.

    Perhaps I should have pushed 'i' beyond 2^16 a little but not as far as 2^60.

    Your code only does one test - mine calculates an average of 10,000 tests.

    It is worth noting that the theoretical average of 2^15 will not be obtained even if we did an infinite number of tests. BCryptGenRandom has an excellent distribution uniformity but it is not perfect.

    Come to think of it my code may be one way of testing distribution uniformity. With a group test the generator which seems to be 'homing in' closer to an average 2^15 will be displaying the better distribution uniformity.

    Leave a comment:


  • Ribeiro Alvo
    replied
    Jerry

    Maybe this will answer you.

    https://www.freebasic.net/forum/viewtopic.php?t=25393


    Or use David's code, with the changes I made (I hope he doesn't mind).
    This gives us more iterations, thus increasing the probability to find the value zero (0).

    Code:
    [FONT=Calibri][FONT=Courier][COLOR=#2c2c2c]#Break On[/COLOR][/FONT][/FONT]
    [FONT=Calibri][FONT=Courier][COLOR=#2c2c2c]#Compile exe[/COLOR][/FONT][/FONT]
    [FONT=Calibri][FONT=Courier][COLOR=#2c2c2c]#Dim All[/COLOR][/FONT][/FONT]
    [FONT=Calibri][FONT=Courier][COLOR=#2c2c2c]#Include "win32api.inc"[/COLOR][/FONT][/FONT]
    
    [FONT=Calibri][FONT=Courier][COLOR=#2c2c2c]Function PBMain[/COLOR][/FONT][/FONT]
    [FONT=Calibri][FONT=Courier][COLOR=#2c2c2c]Local hRand As Dword[/COLOR][/FONT][/FONT]
    [FONT=Calibri][FONT=Courier][COLOR=#2c2c2c]Local Result As Integer[/COLOR][/FONT][/FONT]
    [FONT=Calibri][FONT=Courier][COLOR=#2c2c2c]Local j As QUAD[/COLOR][/FONT][/FONT]
    [FONT=Calibri][FONT=Courier][COLOR=#2c2c2c]BCryptOpenAlgorithmProvider(hRand, $$BCRYPT_RNG_ALGORITHM, $$Nul, 0)[/COLOR][/FONT][/FONT]
    
    [FONT=Calibri][FONT=Courier][COLOR=#2c2c2c]For j = 1 To 1152921504606846976  '2^60[/COLOR][/FONT][/FONT]
    [FONT=Calibri][FONT=Courier][COLOR=#2c2c2c]BCryptGenRandom(hRand, VarPtr(Result), 2, 0)[/COLOR][/FONT][/FONT]
    [FONT=Calibri][FONT=Courier][COLOR=#2c2c2c]If Result = 0 Then Exit For[/COLOR][/FONT][/FONT]
    [FONT=Calibri][FONT=Courier][COLOR=#2c2c2c]Next[/COLOR][/FONT][/FONT]
    
    [FONT=Calibri][FONT=Courier][COLOR=#2c2c2c]Print j [/COLOR][/FONT][/FONT]
    [FONT=Calibri][FONT=Courier][COLOR=#2c2c2c]BCryptCloseAlgorithmProvider(hRand, 0)[/COLOR][/FONT][/FONT]
    [FONT=Calibri][FONT=Courier][COLOR=#2c2c2c]Waitkey$[/COLOR][/FONT][/FONT]
    [FONT=Calibri][FONT=Courier][COLOR=#2c2c2c]End Function[/COLOR][/FONT][/FONT]
    Last edited by Ribeiro Alvo; 12 Feb 2021, 04:06 PM. Reason: Bug fix as suggested by David on post #9

    Leave a comment:


  • David Roberts
    replied
    Here is a simple test using an Integer as a buffer.

    The trial calls BCryptGenRandom 2^16 times. The integer could be zero on the first trial but that is highly unlikely. It could be zero on the 2^16th trial but that is equally unlikely. On average, we should get zero after 2^15, 2^16/2, trials; provided we have a perfect distribution uniformity.

    So, I did 10,000 trials and got an average of 41,633.6572. That is 2^15.35 which isn't that far from 2^15. 10,000 trials isn't that large and a larger test should see us getting closer to 2^15.

    With could do the same for a Dword buffer but then the average would be 2^31, so I wouldn't hold my breath on that test. Estimates vary but the chance of being struck by lightning in the UK is about 2^20 to 1 against.

    I have done distribution uniformity tests on all my generators using a few more metrics than Formilab's Ent uses and found that BCryptGenRandom is one of the best and even beats Intel's RdRand but only just.
    Code:
    #Break On
    #Compile exe
    #Dim All
    #Include "win32api.inc"
     
    Function PBMain
    Local hRand As Dword
    Local Result As Integer
    Local j, i, tot As Long
      BCryptOpenAlgorithmProvider(hRand, $$BCRYPT_RNG_ALGORITHM, $$Nul, 0)
      For j = 1 To 10000
        For i = 1 To 2^16
          BCryptGenRandom(hRand, VarPtr(Result), 2, 0)
          If Result = 0 Then Exit For
        Next
        tot += i
      Next
      Print tot/10000
      BCryptCloseAlgorithmProvider(hRand, 0)
      Waitkey$
    End Function

    Leave a comment:


  • David Roberts
    replied
    Originally posted by Jerry
    More specifically, could BCryptGenRandom fill a buffer with n number of bytes and all bytes (implying all bits in each byte) having a value of zero.
    I cannot give a definitive answer to that but will say that if the answer is no then the output would not be random. The likelihood of a null buffer should be inversely proportional to n.

    It is a bit like coin tossing. If 1,048,576 people, 2^20, tossed an unbiased coin twenty times then we should expect one to see either twenty heads or twenty tails. If only one person was involved, and they saw either twenty heads or twenty tails then we would have very strong evidence of a biased coin.

    If your application prohibits a null buffer then a 'check and reject' mechanism will be mandatory.

    Many people use Intel's RdRand without checking a potential failure. The chance of that is minuscule but not impossible. I allow six tries and if all fail I then revert to RtlGenRandom. I expect that scenario to never happen.

    Leave a comment:


  • Jerry Wilson
    replied
    More specifically, could BCryptGenRandom fill a buffer with n number of bytes and all bytes (implying all bits in each byte) having a value of zero. Really, its an academic question since a line or two of code can be used to test the buffer with, virtually, no hit to app performance. According to Microsoft:

    The default random number provider implements an algorithm for generating random numbers that complies with the NIST SP800-90 standard, specifically the CTR_DRBG portion of that standard.
    SP800-90 is over 100 pages long so I'm trying to be lazy and skip reading that tome - hoping that someone else has

    Leave a comment:


  • Stuart McLachlan
    replied
    If it is generating random bits, which it is supposed to, any bit pattern should be equally possible including all 0s and all 1s.

    Note that it can use different algorithms

    Leave a comment:


  • Jerry Wilson
    started a topic BCryptGenRandom Output

    BCryptGenRandom Output

    Does anyone know if BCryptGenRandom COULD create a value of zero? I don't want it to but do want to know if I need to check to detect if it does.
Working...
X