Post by thread:random seeds for PICs?

Hi all... Anybody know of a good way to get a number out of a PIC which will be randomly different each time it is powered up? I'm looking for one that doesn't require operator input such as timing a button push, etc. Preferably not involving any extra components such as measuring charge time for an RC network. For that matter, any other suggestions on differentiating multiple _identically_programmed_ PICs on the same I2C multi-master buss? Arbitration on this buss will only work if there is _something_ different about the conflicting messages! Thanks - I sure enjoy this group!! Oh - the PIC I'm currently using is a '74. ...Shel Michaels

At 03.41 1995-12-27 -0500, Shel Michaels wrote: >Hi all... > Anybody know of a good way to get a number out of a PIC which will be >randomly different each time it is powered up? I'm looking for one that >doesn't require operator input such as timing a button push, etc. Preferably >not involving any extra components such as measuring charge time for an RC >network. Use a linear feedback shift register with some good tap sequence. You may get every number in a say 15 bit register if you choose the tap sequence properly. One good sequence is: 15,1,0 which means that you should XOR the 15:th and the 1:st bit and put the result at the end of the "FIFO" register. +-|15|14|13|12|11|10|9|8|7|6|5|4|3|2|1|--- out | | | |---+--------------------------------+ This register will propagate through all 15-bit numbers until the initial seed will come back. (Store this register in EEPROM in case of power down) The sequence 63,1,0 works fine for 63-bit registers and there are a whole bunch of sequences, the only requirement is that the sequence must be primitive modulo 2. In an alternative representation, the sequence can be interpreted as a polynomial with degrees 63,1,0: x^63 + x + 1. This polynomial must be irreducible (cannot be factorized into two polynomials) in the same manner as with prime numbers. 15 = 5 * 3 but how about 17? 17 is a prime number and cannot be factorized. Oops, too much non-relevant theory here ... If you don't use the '84 or EEPROM:s? I guess you have to get some information from the world outside, e.g. measure the state of some independent 50-50 duty clock source, add a couple of these bits (modulo 2) and save the LSB as the first bit in your number. Do likewise for the other bits. If possible use more than one "random" source to collect bits. Real randomness is hard to produce but the above method should work quite well, the next is somewhat harder to implement in hardware.... I just feel like putting this text about rand tables in this reply as well, so enjoy: -------------------------------------------------- RAND Tables Back in 1955, when computers were still new, the Rand Corporation published a book that contained a million random digits. Their method is described in the book: "The random digits in the book were produced by rerandomization of a table generated by an electronic roulette wheel. Briefly, a random frequency pulse source providing on the average about 100,000 pulses per second, was gated about once per second by a constant frequency pulse, Pulse standardization circuits passed the pulses through a 5-place binary counter. In principle the machine was a 32-place roulette wheel which made, on the average, about 3000 revolutions per trial and produced one numher per second. A binary-to decimal converter was used which converted 20 of the 32 numbers (the other twelve were discarded) and retained only the final digit of two-digit numbers; this final digit was fed into an IBM punch to produce finally a punched card table of random digits," The book goes on to discuss the results of various randomness tests on the data It also suggests how to use the book to find a random number: "The lines of the digit table are numbered from 00000 to 19999. In any use of the table, one should first find a random starting position. A common procedure for doing this is to open the book to an unselected page of the digit table and blindly choose a five-digit number; this number with the first digit reduced modulo 2 determines the starting line; the two digits to the right of the initially selected five-digit number are reduced modulo 50 to determine the starting column in the starting line. To guard against the tendency of books to open repeatedly at the same page and the natural tendency of a person to choose a number toward the center of the pages every five-digit number used to determine a starting position should be marked and not used a second time for this purpose." -------------------------------------------------- -- Conny

Shel Michaels wrote: >Hi all... > Anybody know of a good way to get a number out of a PIC which will be >randomly different each time it is powered up? I'm looking for one that >doesn't require operator input such as timing a button push, etc. Preferably >not involving any extra components such as measuring charge time for an RC >network. The method I used was to set the WDT for its longest period, then count cycles until the PIC is reset by the WDT. Since several hundred thousand counts can occur during the WDT timeout, the low several bits of the count should be reasonably 'random', at least if the supply voltage, temperature, etc. have changed since the last power-up. To generate a large "random" (I say this in quotes since I haven't tested to see how random the resulting numbers are) number, repeat the process. This has the disadvantage that a relatively long time (several seconds) may be required to come up with the number. My application was to turn the PIC on and leave it on, so only an initial seed was required. Here is the code from that program, which was for a 16C84. It initializes 4 bytes to random numbers which range from 1-255 (not 0. Loading a feedback SR with all zeros causes it to 'jam' at 0). The rest of the progam must of course reset the WDT periodically. Probably some modification should be done to handle unexpected WDT timeouts more robustly. ========================================================= org 0 ; Reset starts here. ; Determine if it is a power-on or WDT timeout reset. If WDT timeout, do ; the seeding process (if necessary) start btfsc STATUS,4 ;Skip if WDT time out. goto start2 ;Power on for first time ;Here if WDT timed-out. movfw INDF ;See if seeded number ended up 0 (that's bad). skpnz ;No, it's OK. goto start3 ;Re-seed. Hope WDT or osc drifts some. incf FSR,1 ;Point to next number. movfw FSR ;Check if done. xorlw rndm+4 ;by testing if it points past the random #. skpz ;It does, seeding done. goto start3 ;No, seed this one. goto mainlps ;Seeding done. Commence normal operation. ;Here on initial power-up. start2 clrf rndm ;Start with all zeros. Seeding process clrf rndm+1 ; will replace them with non-zero values. clrf rndm+2 clrf rndm+3 movlw rndm ;Point FSR at the first one. movwf FSR start3 ; Here to increment @ FSR until WDT times out. incf INDF,1 ;Increment the indirectly addressed byte goto start3 ;and continue 'till WDT times out. ======================================================= Truly random numbers can come from a noisy linear electronic device, such as a transistor, zener diode, or op-amp. Simply amplify the signal up to TTL level then sample it with the PIC. Two pitfalls exist here, a bias toward 1 or zero, or periodic "artifacts" such as coupling from the AC power line also being amplified and included in the "random" sample. Making the sample rate random by making it depend on the last several samples may be a way around that. As Conny Andersson has already explained, a feedback shift register can be used to produce a sequence of psudorandom numbers from a starting 'seed'. Using a truly random number as the "seed" ensures that the same sequence isn't generated every time. > > For that matter, any other suggestions on differentiating multiple >_identically_programmed_ PICs on the same I2C multi-master buss? Arbitration >on this buss will only work if there is _something_ different about the >conflicting messages! Depends on how many PICs are involved, I suppose. What is the advantage of this, though, without knowing which PIC has which position in the system? Identically programmed PICs could learn their identity by pin-strapping, which is a bit of a problem since the number of pins is limited. There are various ways around this, for example connect one pin which is usually an output to one of several possible other outputs with a resistor. If an extra pin is available, just connect it directly. During initialization, set the one pin as input and scan the other outputs to learn which one has the resistor. Hopefully this can be done without upsetting the rest of the circuit. If the PICs form a chain, each one could signal the next that it is next in line for example by using two pins of each, one in and one out. The pins would indicate that an address is to be accepted. After reset, all PICs would force their output low. The PIC which has its input high after that process (which would be the first one in the chain, as it is strapped high by hardware) would take address 0, then force its output high. The next chip in line would see this high level and take the address sent over the I2C bus from the last one and add one to it, then continue the process: Psuedo-code: Reset 1. Output pin low Wait a short time to be sure all others have set output low. Is input pin high? No : to step 2 Yes : Address = 0, to step 3. 2. Wait until input pin is high. Receive from bus Address = data received + 1. 3. Output pin high Transmit address on bus Normal operation could begin here, but the bus may still be busy with the others transferring addresses. Something could probably be done with returning all the output pins low in sequence before starting operation. -Mike

On Wed, 27 Dec 1995, Conny Andersson wrote: > To guard against the > tendency of books to open repeatedly at the same page and the natural > tendency of a person to choose a number toward the center of the pages every > five-digit number used to determine a starting position should be marked and > not used a second time for this purpose." > -------------------------------------------------- Do you think they believed this was the original OTP? ;-) Arley Carter Tradewinds Technologies, Inc. email: spam_OUTacTakeThisOuThawk.twinds.com www: http://www.twinds.com "Trust me. This is a secure product. I'm from <insert your favorite corporation or government agency>."

Do you think they believed this was an original OTP? ;-) Arley Carter Tradewinds Technologies, Inc. email: .....acKILLspam@spam@hawk.twinds.com www: http://www.twinds.com "Trust me. This is a secure product. I'm from <insert your favorite corporation or government agency>." On Wed, 27 Dec 1995, Conny Andersson wrote: >To guard against the > tendency of books to open repeatedly at the same page and the natural > tendency of a person to choose a number toward the center of the pages every > five-digit number used to determine a starting position should be marked and > not used a second time for this purpose." > --------------------------------------------------

At 10.34 1995-12-28 -0500, Arley Carter wrote: >Do you think they believed this was the original OTP? ;-) No, if you *publish* the OTP in a book it's no longer OTP, right? Oh, by the way, I noticed there was a note about shift registers in the data book 95/96 on page 3-52. (appendix C, SQTP for PIC16C5X/5XA) Microchip states that they generate *truly* random numbers for serial numbers in their SQTP prog.spec. How? -- Conny

Conny Andersson <PICLISTKILLspamMITVMA.MIT.EDU> wrote: > Microchip states that they generate *truly* random numbers for > serial numbers in their SQTP prog.spec. How? Conny: This bothered me, too. In the newest revision of the PRO MATE User's Guide, Microchip now describes the two SQTP-file options as "Random: Numbers may repeat" and "Pseudo-Random Sequence: Numbers do not repeat until all numbers in the sequence have been generated". The Pseudo-Random Sequence is generated using the standard shift-and-XOR algorithms. I'm not sure, but I think that the longer sequences may actually start to repeat before 2^[number of bits] numbers have been generated. Still, you'll get very long sequences without repeats if you use use the "Pseudo-Random" option. -Andy Andrew Warren - .....fastfwdKILLspam.....ix.netcom.com Fast Forward Engineering, Vista, California http://www.geopages.com/SiliconValley/2499

At 17.07 1995-12-28 -0800, Andy Warren wrote: >This bothered me, too. In the newest revision of the PRO MATE >User's Guide, Microchip now describes the two SQTP-file options as >"Random: Numbers may repeat" and "Pseudo-Random Sequence: Numbers >do not repeat until all numbers in the sequence have been >generated". Nothing particular about that, what I was asking was how Microchip generates *true* random numbers. Do they (you) use some kind of electronic phenomena that has been proven "random"? I believe there is no *true* random numbers but one can get very close ... well that depends on how you define *true* of course. -- Conny

> Nothing particular about that, what I was asking was how Microchip generates > *true* random numbers. Do they (you) use some kind of electronic phenomena > that has been proven "random"? I believe there is no *true* random numbers > but one can get very close ... well that depends on how you define *true* of > course. Because Microchip does not specify anything about how their "random" numbers are generated, I would be strongly disinclined to make any assumptions about randomness though I would expect that it's unlikely that anyone would go through the trouble of exploiting any non-randomness for anything except highly-sensitive cryptographic systems, and for those I would strongly recommend doing the programming in-house anyway. Other- wise, my guess would be that Microchip is using something reasonably ran- domish, but nothing that can be relied on as such. PS--In the original specification for closed-captioning, it says that field 2 is supposed to contain "random" data. Can anyone think of any reason why something would be spec'ed to be "random" with no indication of required spectral properties, non-correlation, etc.?

Actually, I have a strange question. If I wanted to generate true random numbers in hardware, would a PIC for communication tied to a CCD with no outside view be able to generate true random numbers? I would assume that the thermal noise you normally have to filter out of the CCD output when doing astronomy would make a wonderful random number generator. Roger

Conny Andersson <EraseMEconanspam_OUTTakeThisOuTATVIDABERG.SE> wrote: > what I was asking was how Microchip generates *true* random > numbers. Do they (you) use some kind of electronic phenomena that > has been proven "random"? Conny: Sorry... I guess I wasn't too clear. Microchip uses the standard shift-and-XOR algorithms to produce their pseudo-random sequences. By the way, I assume from that "they (you)" bit that you may be under the impresion that I work for Microchip. While my company does a fair amount of work for them, I am not an employee. The PROMATE software was written by Jim Pepping (and, perhaps, others) at Microchip; as far as I know, no outside talent was utilized. -Andy Andrew Warren - fastfwdspam_OUTix.netcom.com Fast Forward Engineering, Vista, California http://www.geopages.com/SiliconValley/2499