Random Number Generator

Hi,

I need a random number generator for a project. Just found out that Math.random() always returns the same sequence after a reboot, making it not usable in my case. Especially because it is not possible to seed it. I want something less predictable. I guess that's the case in many applications, for example dice based games (you do not want to have the same game again and again after starting up), or for encryption when controlling something over radio.

First question: Would it make sense to allow to seed Math.random()? That would not force everyone who wants unpredictable randomness to implement their own RNG.

As this is not possible right now, I set out to implement something more random. After finding out that the MCU does not have the hardware random number generator some of the STM32F4 do have, I hacked together a little hardware based random number generator; similar to one which some people use on Arduinos.

It looks like this:

function random()
{
  var sum = 0;
  var v1 = Math.floor(E.getAnalogVRef() * 100000000000) % 2;
  for (var s = 0; s < 32; s++)
  {
    sum *= 2;
    var v2 = Math.floor(E.getAnalogVRef() * 100000000000) % 2;
    if (v1 == v2)
      sum++;
  }
  
  return sum;
}

It uses the least significant bits of the analog reference as a source of random bits. Note that the output seemed to be a bit biased (more 0s than 1s). The "if (v1==v2) is for whitening the random bits to remove that bias. It looks pretty good after that.

It is pretty slow but also pretty random - at least with my board when powered over USB. Have to try it with a battery to see how it behaves there. While I would not necessarily use it for hard cryptography, it is better than having to use the same sequence over and over again. It might also be interesting to couple it with the elapsed time to add more randomness.

Is this something which should be added to Espruino? I could also make a C module out of it, would be much faster. Maybe it would also be useful to use it only as a source for a random seed for Math.random - if seeing is added.

Any thoughts?

Stevie

Hi,

Yes, I think allowing a seed to be set makes a lot of sense. I've just added a bug for this and I'll see if I can get it in the next release.

I'm not convinced that the random number generator you have is going to produce random enough values to be useful all the time, but it could be great as a Seed as you say.

I wonder if there's another source of entropy available? I guess the only other thing is to use unconnected analog inputs, and maybe the temperature...

Thanks, the seed would be a great start!

As for the RNG: I let it run for a while and the distribution looks okay - superficially. I am thinking about generating a bunch of random numbers and dumping them to a file. Then I could put them into a statistical test on the PC to see how good it is. But it might be dependent on the board and on the power supply. So it does not necessarily apply to all situations. But the general principle seems to be sound.

I tried the analog inputs as well, they seem to give the same results, pretty much. In my first version, you could select the input. The temperature also looks like a great idea! In addition, as mentioned the time since the startup could be used as an additional source.

If there is interest, I could put that in a library. I would then use the temperature and time as well to collect enough randomness.

Okay, I did a test with 10000 samples between 0..1. The mean was 0.51 (expected is of course 0.5 for a uniform distribution), the variance was 0.086631417 (expected variance is 0.083333333). I did a Kolmogorov-Smirnov test (I hope that I got it right). The maximum was 0.032498016, that should also be fine (between 0.07089 and 1.5174). Also optically the numbers look good. That was only with the analog reference.

I am no expert by any means, and I would not bet my life on it. But for me for anything except hard cryptography it should be fine.

Thanks - good to know! It would make a good module... I think once I add the ability to set the Seed it's something that people would be really interested in.

I'm a little worried about multiplying by such a large number (the ADC is only 12 bit, so multiplying so much might hurt the randomness), but hey - if it works :)

Okay, I will look into writing a C module implementing the same thing. I agree about the multiplication thing. But I guess when doing it in C we can do without and just do this on the bit level.

If you really want a random generator, you take a noisy diode or transistor signal... used that in early (encription) software to create secret code sequences years back with early 8-bit mPs in the signal corp in the army... (when every cycle was crucial). Instead of messing with the javascript syntax, you can run the random generator for a random time and take the current (real) time (as seed) into account. Agreed, it is not as random as other options, but it is unpredictable. In testing, predictable and nicely distributed 'random' values are required to run true regression, over and over, and that is the requirement what Math.random() is based of.

I'm having the same problem here: The current random generator is based on the state of the machine and time. If you disconnect the power and reconnect it again, the number sequence will be the same, which is for some usages not suitable.
I've thought about fixes for it: Adding a number of how many times it has booted or analog reading something unused(getting random noise).
I'm not a RNG expert thought, but randomness should always be unpredictable.

Hi allObjects,

Math.random() is not random at all, because it will always create the same sequence after rebooting. So that's not really helpful at all. Gordon wrote he will add the possibility to seed it. That's a first step. The second is a hardware based random number generator which can be used to produce a seed for it which is truly random.

As for the diodes: Yes, that's pretty much the idea. But in my experience just taking the analog reading of a diode as such won't be enough. You need to collect the least significant bits of multiple readings to get something less predictable. So instead of letting everyone write the code and mess around with diodes, there can be a library and it can be based on the analog reference instead of diodes, so no external parts needed at all.

I tried to find out if the analog reference is random enough to give a good seed. Which it apparently is - at least good enough for me.

Hi,

here is a first prototype of the RNG as a C module:

\#include "jswrap_rng.h"  // We need the declaration of the jswrap_rng_random function
\#include "jsinteractive.h" // Pull in the jsiConsolePrint function

// Let's define the JavaScript class that will contain our `random()` methods. We'll call it `RNG`
/*JSON{
  "type" : "class",
  "class" : "RNG"
}*/

// Now, we define the `jswrap_rng_random` to be a `staticmethod` on the `RNG` class
/*JSON{
  "type" : "staticmethod",
  "class" : "RNG",
  "name" : "random",
  "generate" : "jswrap_rng_random",
  "return" : ["JsVar","The random number or NAN, if it is not supported on the platform."]
}*/

// Now, we define the `jswrap_rng_random_long` to be a `staticmethod` on the `RNG` class
/*JSON{
  "type" : "staticmethod",
  "class" : "RNG",
  "name" : "random_long",
  "generate" : "jswrap_rng_random_long",
  "return" : ["JsVar","The random number or NAN, if it is not supported on the platform."]
}*/

// TODO: We need a better way to pull this in! This will not work on all boards. And we need
// to make the jshAnalogRead function non-static where it is defined.
extern int jshAnalogRead(JsvPinInfoAnalog analog, bool fastConversion);

static int get_bit() {
  jshDelayMicroseconds(10);
  int v = jshAnalogRead(JSH_ANALOG1 | JSH_ANALOG_CH17, false);
  // It seems the lower 4 bits are always zero.
  v >>= 4;
  v &= 1;
  return v;
}

static long long rng_random() {
\#if defined(STM32F1) || defined(STM32F4)
  // enable sensor
  ADC_TempSensorVrefintCmd(ENABLE);

  long long sum = 0;
  int s;
  int v1 = get_bit();
  for (s = 0; s < 32; s++)
  {
    int v2 = get_bit();
    sum <<= 1;
    if (v1 != v2)
       sum++;
    v1 = v2;
  }

  // disable sensor
  ADC_TempSensorVrefintCmd(DISABLE);
  return sum;
\#else
  return NAN;
\#endif
}

JsVar *jswrap_rng_random_long() {
\#if defined(STM32F1) || defined(STM32F4)
  long long v = rng_random();
  return jsvNewFromLongInteger(v);
\#else
  return jsNewFromFloat(NAN);
\#endif
}

JsVar *jswrap_rng_random() {
\#if defined(STM32F1) || defined(STM32F4)
  long long v = rng_random();
  double value = ((double)(v)) / 4294967296.0;
  return jsvNewFromFloat(value);
\#else
  return jsNewFromFloat(NAN);
\#endif
}

Seems to work fine. But there are some flaws: Namely it pulls in some function from the hardware abstraction layer. I had to make the function non-static there. I am not sure what the best way would be to do this. Add the function to the hardware layer itself? Add a function which takes the analog reading as an int?

Math.random() is not random at all, because it will always create the same sequence after rebooting. So that's not really helpful at all.

It all depends... on the intended purpose... for games/rolling dices: absolutely useless, for regression testing with values covering a range: perfect.

Interesting what you verified and good to hear:

I tried to find out if the analog reference is random enough to give a good seed. Which it apparently is - at least good enough for me.

The 'noise' in the ADC process has obviously the issue, and with the resolution and combination of multiple readings give already a good base.

A few Javascript lines based on your observations, could that become a 95% solution?

It all depends... on the intended purpose... for games/rolling dices: absolutely useless, for regression testing with values covering a range: perfect.

100% agree. That's why in C there is always a seed for the standard random generator. So it allows you to do both - and even for regression testing one might want to use different sequences just to be sure that the one sequence there is is not a lucky one... I never understood why JavaScript does not have it.

A few Javascript lines based on your observations, could that become a 95% solution?

I guess the lines above are good enough for that purpose. Either as it is or we could put this into a JavaScript module. Not sure. Do you have any opinion? For my purposes, the C version is what I want. I will certainly keep it around and use it, even if it is not integrated.

I know that binaries can be loaded with js as well... but have not done it yet myself... That would allow a version(s) that do not need to go into board specific builds... for the users not familiar -yet - with firmware building... like me :(... @JumJum worked on such things and posted in various conversations (assembler/binaries): module to handle assembler/binaries, Some functions to handle assembler, even though he too ran (many) builds.

@Stevie, wow - looks nice! Using the analog values directly seems like a great plan (analogRead gives a 16 bit value, but the ADC is only 12 bit - hence the low 4 bits being 0).

I think it probably does make sense to include something like that in jshardware.c (especially as some hardware actually has a proper RNG). I'll add that to the bug, and will probably expose it in something like E.random()...

Also, at some point I need to come up with an example of compiling your own function that can be loaded in dynamically. The work done for compiled functions could easily be applied to C - then you could have your own native code without having to recompile your own image.

@allObjects - actually the code @JumJum posted there isn't needed any more. Native code can now be stored in a String in Espruino's memory, so it works even when it's saved and Espruino is restarted.

Ok, just added this - it'll be in the next release. The random number generator will automatically seed itself from the voltage reference at startup, or you can use E.hwRand() to get a random value from hardware, or E.srand(..) to seed Math.random

Very cool. I tested it and it works very nicely! Thanks very much! This way we have the best of both worlds.

The only thing I might do differently is to let E.hwRand() return a long int. This way you would not get signed values back but always unsigned. Signed random values are a bit unusual I would say. But it does not really matter much.

Being able to load C stuff directly would also be very cool. Although it is not too difficult to compile your own version - the documentation is very good...

Great - thanks!

The long int thing is tricky... I know what you mean about negative numbers.

Espruino stores ints in a normal 32 bit value, but anything larger in a double. I guess it's unlikely to cause problems, but code would actually end up getting an int half the time, and a double the other half (where the number got too big). I guess I could do it as a float between 0 and 1 again, but often I think it'd be quite handy to be able to get at the raw integer.

Understood. And I agree with wanting to get an integer. But getting to an unsigned version from that one is also easy, so that's also fine.