Genuinely random numbers

[Richard Russell]

It is well-known that the RND function in BBC BASIC doesn't generate truly random numbers but pseudo-random numbers: an entirely predictable and repeatable set of numbers which happens to have such a long cycle length (it repeats after 2^33-1 calls to RND) and distribution that it gives the impression of being random, but isn't.

If one needs genuinely unpredictable numbers one cannot use RND, there has to be an 'external' source of randomness, such as something derived from a truly random process like thermal noise. If you're lucky your Operating System may provide such a function, for example the Windows CryptGenRandom function.

Failing such an API function you could attempt to introduce unpredictability by for example timing how long it takes the user to press a key or how long it takes to retrieve data from a distant web site or something. These would be better than nothing but it would be hard to demonstrate that they really do introduce much 'entropy'.

Is there another way? It turns out that if you have a modern CPU it may provide a solution. Some x86 CPUs have the RDSEED instruction and some ARM CPUs the RNDR function; I don't know how they work internally but they claim to generate unpredictable random numbers. Here's a little program you can run in BB4W, BBCSDL or BBCTTY, when running on an x86 CPU (32 or 64 bits):

Code: Select all

      DIM ]^P% 100

      [OPT 2
      .avail
      mov eax, 7     ; set EAX to request function 7
      xor ecx,ecx    ; set ECX to request subfunction 0
      cpuid
      bt  ebx, 18
      sbb eax,eax
      ret

      .rdseed
      db &0F : db &C7 : db &F8 ; rdseed eax
      jnc rdseed
      ret
      ]

      IF NOT USR(avail) THEN PRINT "RDSEED instruction not available" : END

      REPEAT
        PRINT "Random integer = &" ; ~USR(rdseed)
        WAIT 1
      UNTIL FALSE

      END

[DDRM]

Yes, RDSEED and RDRAND use thermal entropy within the chip. They're pretty secure, but quite slow (they typically take > 1000 clock cycles), so they are slower (often much slower) than even very good PRNG output. That's unlikely ever to be an issue for an interpreted language, though, I would think.

There has been some suggestion that some chip makers may / may have built in "back doors", potentially accessible to the US government, and it has been shown that if you can be running code on another core on the same chip at the same time it may be possible to "leak" information on them, but it's pretty difficult, and I think you have to have simultaneous access to the machine. I think one might consider those theoretical risks rather than real ones, unless you are trying to spy on the CIA...



D

[Richard Russell]

They're pretty secure, but quite slow (they typically take > 1000 clock cycles), so they are slower (often much slower) than even very good PRNG output. That's unlikely ever to be an issue for an interpreted language, though, I would think.

That's precisely why RDSEED is called that, as I understand it, to emphasise that it is most usefully used to seed a faster PRNG. If you periodically use RDSEED to re-seed a conventional long-period PRNG, such as a LFSR which is what BBC BASIC uses, the result should be both fast (mostly) and unpredictable.

Indeed RDRAND is exactly that: a PRNG seeded using the same on-chip entropy source as RDSEED, so the work is done for you (although you then have no control over the PRNG used, and it's conceivably that which is vulnerable to a 'back door' having been added).