7
\$\begingroup\$

I am working to develop an Android accessory hardware. Currently, I am trying to generate an random number (C language) on a embedded system, but the value doesn't change. I am wondering if there is any entropy source that I can use to generator random number.

If there is another way of generating random number other than using an entropy way, I would greatly want to hear it from you!

The software I am using:

MPLAB IDE Version 8.73 MPLAB C Compiler for PIC24 and dsPIC v3.30

The device/tools I am using:

DM240415 - PIC24F Accessory Development Starter Kit for Android

\$\endgroup\$
  • 1
    \$\begingroup\$ stackoverflow.com/questions/3764976/… \$\endgroup\$ – Toby Jaffey Aug 18 '11 at 11:24
  • 2
    \$\begingroup\$ What do you mean "the value doesn't change"? Like, it just outputs 9 every time you call it? \$\endgroup\$ – endolith Aug 18 '11 at 19:34
  • \$\begingroup\$ Example when I run a random generator to generate a array of random integer. The value is the same at the start no matter how many times I run it. E.g. Array[1] = 4; Array[2] = 49; Array[3] = 22; Array[4] = 91; Array[5] = 33; ... \$\endgroup\$ – Ezylryb Aug 19 '11 at 0:29
  • \$\begingroup\$ @Ezylryb - looks like a poorly designed PRNG. A PRNG always produces the same sequence, but usually they rely on a truly random event to determine where in the sequence it starts. This random event is often derived from the time a user action takes place, like when a button is pressed. The value of a free-running timer can then be used as a seed for the PRNG. Apparently your PRNG always starts with the same seed value. \$\endgroup\$ – stevenvh Aug 20 '11 at 8:45
  • 1
    \$\begingroup\$ Bingo! I am using some random value in a cryptographic application but I am not developing some gambling system. To a certain extend, yes. The user can be harm if someone are able to predict the random numbers @Dr X \$\endgroup\$ – Ezylryb Sep 15 '11 at 3:25
12
\$\begingroup\$

“Anyone who considers arithmetical methods of producing random digits is, of course, in a state of sin” \$-\$ John Von Neumann

A good noise source is the breakdown noise of a zener diode. The simple schematic below shows how to get white noise from a zener by cascading two LNAs (Low Noise Amplifiers) to increase the noise level.

white noise generator

If you don't care about the noise being white you can simply use an opamp amplifier with a high amplification, with a comparator following it. The opamp's amplification puts a limit to the bandwidth, and hence the rate of change in your digital signal. If necessary cascade two opamps like the LNAs in the given schematic to get a faster random bit stream.

You can use the SPI module to clock in bytes of random bits from this circuit.
(The SPI is just a simple way to automatically collect 8 random bits, it doesn't add any level of determinism: the input changes continuously and randomly and you never know what it will be at the next clock edge. You can also read an I/O pin and shift that bit's level into your result byte.)

This circuit is a possible alternative solution, also relying on a zener diode as a noise source:

random bit circuit

The schematic mentions the OPA2340 for the amplifier, but isn't clear on the comparator. While the OPA2340 is reasonably fast I would suggest to use a real comparator here as these are usually much faster than opamps. For instance the TL3016 has a propagation delay less than 10ns, and a rise time of 0.5ns typical. This means you can sample random values faster without the risk of coherence between successive samples.

To test the random number generator you can test for normality. This means creating a long string of random numbers, the longer the better. Best thing is to transport it to the PC for the analysis. Count the one-bit sequences, that's the 0s and 1s. There should be about the same number of each. Next repeat for two-bit sequences. There should be as many 00s as 01s, 10s and 11s. Repeat for three-bit sequences, etc.
I'm not a statistician, so there may be better/easier tests. Feel free to add them.


pseudo random number generator

\$\endgroup\$
  • \$\begingroup\$ Due to the PIC24FJ256GB110 limitation, white noise is impossible unless I add an additional hardware on it. You mention SPI to clock bytes of random bits. Is this truly random number?? or it is base on algorithm to output the random number \$\endgroup\$ – Ezylryb Aug 18 '11 at 15:23
  • \$\begingroup\$ @Ezylryb - this should give you a good random number. Just make sure there are enough level transitions in an SPI clock cycle. To test randomness you can run statistical tests. I'm not an expert, but I think testing for normality on a long sequence could be a good test. \$\endgroup\$ – stevenvh Aug 18 '11 at 15:31
  • 1
    \$\begingroup\$ @Ezylryb - Without the additional hardware shown in either circuit here, the SPI port will not generate truly random numbers. Not sure that we were clear on that. \$\endgroup\$ – Kevin Vermeer Aug 18 '11 at 16:10
  • \$\begingroup\$ @Kevin Vermeer So the SPI module of random number are also base on an math algorithm and not truly random via entropy. Hm.. It seem that there are no way of generating truly random on PIC24FJ256GB110 \$\endgroup\$ – Ezylryb Aug 18 '11 at 16:18
  • \$\begingroup\$ @Ezylryb - The SPI module has very little to do with random number generation, it's just a nice way to get data from the random number generators described above. You could also use a digital input to read the state of the output of the above circuits. \$\endgroup\$ – Kevin Vermeer Aug 18 '11 at 16:24
4
\$\begingroup\$

You're not using a PIC24FJ256GB110, which looks like this:

TQFP-100, not necessarily PIC24FJ256GB110

You're using an Android Starter Kit:

picture of board

which, as you understand, is a rather fixed PCB: You aren't designing the PCB, and a quick look at the schematic didn't reveal much that was built for or could be repurposed as a hardware entropy source, except some ADC traces that might function as antennas as suggested by Matt.

Assuming you're interacting with an Android device, though, you have three potential sources of random noise:

  1. You could measure the precise timings of asynchronous communications or communication happening on the Android, and use the lower bits of this measurement as a source of entropy. Note, of course, that this could be gamed by precisely controlling the Android device, and so isn't suitable for security applications.
  2. Use the lower bits of ADC reads to generate some random noise. You have several floating traces, so this should get unpredictable results.
  3. You have breakout headers to an Arduino shield! This means that you can add all kinds of hardware, like the solutions proposed by Steven, this shield, or the ones proposed in this question. Yes, this will require external hardware.

However, be aware that cryptographic security and true randomness is hard stuff. It sounds like you need to do some more reading before you try to produce something that people can depend on, or you could get yourself in some serious trouble.

\$\endgroup\$
3
\$\begingroup\$

The problem with pseudo-random number generators is that they aren't. They generate a sequence of numbers from a known starting point. This is usually random enough for most low-level uses, but not if you are security conscious, or want more than one system to interact without collisions (e.g., networking).

So yes, as you rightly say, you want a source of entropy. This can be used to set the 'seed' of the random number generator to an unknown value. Because it's only setting the seed and not actually generating the random numbers, the entropy only really needs to be used the once, so can be quite 'heavy' as regards clock cycles. It can run once at system startup, and from then on it should never need to be run again.

Most entropy is gathered (harvested?) from interrupts and other external sources. My first idea that springs to mind would be to leave an input floating (maybe an analog one?) with maybe a bit of track linked to it to act as an antenna. This should fairly randomly alternate between values, which you can use to create a numerical value of the right order to seed your pseudo-random number generator.

Another idea could be to have some form of transducer attached to that input so that it can reliably collect 'noise' to be used as your entropy source. That could be anything from a simple microphone and op-amp, to a couple of op-amps linked up to give huge gain, and thus a white-noise output. There are any number of possible sources of noise in a circuit, depending on what you have at your disposal in the way of board real-estate and budget.

\$\endgroup\$
  • 2
    \$\begingroup\$ I am under an impression that a good (security grade) entropy source is not that easy. OTOH for network protocols and other casual uses your analog solutions will probably be good enough. \$\endgroup\$ – jpc Aug 18 '11 at 10:43
  • 1
    \$\begingroup\$ yes, for security I'd definitely use an external security entropy generation chip, or a CPU with entropy and SHA (for example) built in. \$\endgroup\$ – Majenko Aug 18 '11 at 10:50
  • \$\begingroup\$ On the PIC24F256GB110, is it possible to have an truly random entropy source without any additional hardware add-on to it? \$\endgroup\$ – Ezylryb Aug 18 '11 at 15:29
  • \$\begingroup\$ @Ezylryb read the 3rd paragraph \$\endgroup\$ – Kellenjb Aug 18 '11 at 17:05
  • \$\begingroup\$ @Majenko: The antenna idea isn't good in practice; it will likely stay mostly high or low. \$\endgroup\$ – Brian Carlton Sep 27 '11 at 20:05

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.