Post by thread:[OT] Software Random function

Hi, everyone. I try to make a 8bit random function by software. I want the simple method and the poor registers. Otherwise, i also want to know the hardware method. Anyway, I expect someone give me answers and other information. regards. ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ Shuji Hashimoto Laboratory. Waseda.Univ.Dept.of.Applied Physics. Keishiro Tabe spam_OUTtabTakeThisOuTshalab.phys.waseda.ac.jp ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Keishiro Tabe <.....PICLISTKILLspam@spam@MITVMA.MIT.EDU> wrote: > I try to make a 8bit random function by software. > I want the simple method and the poor registers. Load a register called "RANDOM" with any non-zero value, then call this routine each time you'd like a new pseudo-random value: LFSR: RLF RANDOM,W RLF RANDOM,W BTFSC RANDOM,4 XORLW 1 BTFSC RANDOM,5 XORLW 1 BTFSC RANDOM,3 XORLW 1 MOVWF RANDOM RETLW 0 Or, if you prefer, you can use this routine (written by Marv Isaacman) instead: MARV: MOVLW 01DH CLRC RLF RANDOM SKPNC XORWF RANDOM RETLW 0 -Andy === Andrew Warren - fastfwdKILLspamix.netcom.com === Fast Forward Engineering - San Diego, California === http://www.geocities.com/SiliconValley/2499

Thanks Andy! I'm trying the code you sent. But I have a few question. > Or, if you prefer, you can use this routine (written by Marv > Isaacman) instead: > > MARV: MOVLW 01DH > CLRC > RLF RANDOM > SKPNC > XORWF RANDOM > RETLW 0 "CLRC", "SKPNC" I think about CLRC that C flag clear. About SKPNC, if C flag is 0, then next is skipped. Is it wrong? I have never used the macro. If you introduce me how to write these macro, I will be a better PICer!! Regards. ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ Shuji Hashimoto Laboratory. Waseda.Univ.Dept.of.Applied Physics. Keishiro Tabe .....tabKILLspam.....shalab.phys.waseda.ac.jp ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Konichiwa, Yep you got it on the macro stuff for a start, SKPNC is shorthand for Skip if No Carry. These macros can be found in MPASM. Take a look at them first and attempt to get the general flavour, they are not totemo muzalcahci, but do require that you give them some thought. Macros will make your code more readable, but like all things they should not be abused. Make sure that you understand the PIC assembly first. Dennis > {Original Message removed}

Hi Andrew, Andrew Warren wrote: > > Keishiro Tabe <EraseMEPICLISTspam_OUTTakeThisOuTMITVMA.MIT.EDU> wrote: > > > I try to make a 8bit random function by software. > > I want the simple method and the poor registers. > > Load a register called "RANDOM" with any non-zero value, then call > this routine each time you'd like a new pseudo-random value: > > LFSR: RLF RANDOM,W > RLF RANDOM,W why did you put that double-RLF here? should that be RLF RANDOM,F; RLF RANDOM,W or could one be omitted?? > BTFSC RANDOM,4 > XORLW 1 > BTFSC RANDOM,5 > XORLW 1 > BTFSC RANDOM,3 > XORLW 1 > MOVWF RANDOM > RETLW 0 Stefan Sayer

On Mon, 17 Apr 2000, Sayer wrote: > Hi Andrew, > > Andrew Warren wrote: > > > > Keishiro Tabe <PICLISTspam_OUTMITVMA.MIT.EDU> wrote: > > > > > I try to make a 8bit random function by software. > > > I want the simple method and the poor registers. > > > > Load a register called "RANDOM" with any non-zero value, then call > > this routine each time you'd like a new pseudo-random value: > > > > LFSR: RLF RANDOM,W > > RLF RANDOM,W > why did you put that double-RLF here? should that be RLF RANDOM,F; > RLF RANDOM,W or could one be omitted?? Since Andy is asleep (probably), I'll answer: Andy is implementing 'roll left' where the most significant bit of RANDOM will get copied to least significant position. This is how it works. The first RLF will copy the most significant bit of RANDOM into the carry. What ever was in the carry prior to the first RLF will get copied into the least significant bit position - but we don't care. Also, since the destination is the W register, the variable RANDOM is unaffected. The second RLF repeats the same rotate operation, but this time the carry has been initialized to the MS bit of random. So this second rotate will copy the MS bit into the least significant bit. All of the other bits are of course shifted left one bit position. See? Scott

Keishiro Tabe <@spam@PICLISTKILLspamMITVMA.MIT.EDU> wrote: > "CLRC", "SKPNC" > I think about CLRC that C flag clear. > About SKPNC, if C flag is 0, then next is skipped. That's exactly correct. "CLRC" is equivalent to: BCF STATUS,C and "SKPNC" is equivalent to: BTFSC STATUS,C > I have never used the macro. > If you introduce me how to write these macro, I will be a better > PICer!! Those macros are built into MPASM; the assembler ALREADY understands them. You can use them just as you'd use any of the "real" PIC instructions. A description of the CLRC and SKPNC pseudo-instructions, along with all the others that MPASM understands, is in the MPASM User's Guide. -Andy === Andrew Warren - KILLspamfastfwdKILLspamix.netcom.com === Fast Forward Engineering - San Diego, California === http://www.geocities.com/SiliconValley/2499

Stefan Sayer <RemoveMEPICLISTTakeThisOuTMITVMA.MIT.EDU> wrote: > > LFSR: RLF RANDOM,W > > RLF RANDOM,W > > why did you put that double-RLF here? should that be RLF RANDOM,F; > RLF RANDOM,W or could one be omitted?? and Scott Dattalo <spamBeGonePICLISTspamBeGoneMITVMA.MIT.EDU> replied: > Since Andy is asleep (probably), I'll answer: > > Andy is implementing 'roll left' where the most significant bit of > RANDOM will get copied to least significant position. Thanks, Scott. Stefan: Scott's explanation is correct; I wanted W to contain a rotated copy of RANDOM. In other words, if RANDOM contained "abcdefgh", I wanted W to contain "bcdefgha". Here's a diagram that shows what happens to RANDOM, the W register, and the carry flag after each of those instructions: RANDOM W-Reg Carry -------- -------- -------- abcdefgh XXXXXXXX X RLF RANDOM,W abcdefgh bcdefghX a RLF RANDOM,W abcdefgh bcdefgha a I could have made it "RLF RANDOM,F / RLF RANDOM,W" as you suggest -- that would still have given me what I wanted in W -- but then RANDOM would have been shifted, so I'd have had to change the following BTFSCs from bits 4, 5, and 3 to bits 5, 6, and 4. If I'd done that, everything would STILL work, but it wouldn't match the "classic" description of the operation of an 8-bit LFSR. Also... Imagine that an interrupt routine was using the value of RANDOM. With my code as written, RANDOM always follows the LFSR pseudo-random sequence; it holds one value, then switches to the next in a single cycle when the MOVWF is executed. If I'd allowed RANDOM to be modified by the first RLF, an interrupt that occurred between that RLF and the final MOVWF would see a non-sequential value in RANDOM... Which might not be good if my interrupt routine were expecting an even distribution of values in RANDOM. . Besides, I kinda LIKE the look of two "RLF x,W" instructions in a row. -Andy === Andrew Warren - TakeThisOuTfastfwdEraseMEspam_OUTix.netcom.com === Fast Forward Engineering - San Diego, California === http://www.geocities.com/SiliconValley/2499

Marc <RemoveMEmarcTakeThisOuTAARGH.FRANKEN.DE> 17/04/2000 17:51 Please respond to pic microcontroller discussion list <PICLISTEraseME.....MITVMA.MIT.EDU> To: EraseMEPICLISTMITVMA.MIT.EDU cc: (bcc: Dan Lloyd/GBPTD/ABB) Subject: Re: [OT] Software Random function Security Level:? Internal {Quote hidden}> LFSR: RLF RANDOM,W > RLF RANDOM,W > BTFSC RANDOM,4 > XORLW 1 > BTFSC RANDOM,5 > XORLW 1 > BTFSC RANDOM,3 > XORLW 1 > MOVWF RANDOM > RETLW 0 Pretty predictable (short-term), isn't it? * That's what I was thinkning. I imagine you have to be pretty careful how you use this. Dan

part 0 4307 bytes Marc <RemoveMEmarcEraseMEEraseMEAARGH.FRANKEN.DE>> 17/04/2000 17:51 Please respond to pic microcontroller discussion list <RemoveMEPICLISTspam_OUTKILLspamMITVMA.MIT.EDU>> To:   RemoveMEPICLISTTakeThisOuTspamMITVMA.MIT.EDU cc:    (bcc: Dan Lloyd/GBPTD/ABB) Subject:  Re: [OT] Software Random function Security Level:?         Internal >     LFSR:   RLF     RANDOM,W >             RLF     RANDOM,W >             BTFSC   RANDOM,4 >             XORLW   1 >             BTFSC   RANDOM,5 >             XORLW   1 >             BTFSC   RANDOM,3 >             XORLW   1 >             MOVWF   RANDOM >             RETLW   0 Pretty predictable (short-term), isn't it? * That's what I was thinkning. I imagine you have to be pretty careful how you use this. Dan </UL> It's utterly predicatble.  It is after all, a PSEUDO random number generator.  It produces a repeating pattern of a very limited length.  Not sure if its 127 or 255 for this arrangement.  You could use a 24 bit (or more) register to get longer patterns though, using the same principle.  The Art of Electronics has a good section on maximal length PRBS generators. Mike </BODY> </HTML> </x-html>

D Lloyd <spamBeGonePICLISTSTOPspamEraseMEMITVMA.MIT.EDU> wrote: > > LFSR: RLF RANDOM,W > > RLF RANDOM,W > > BTFSC RANDOM,4 > > XORLW 1 > > BTFSC RANDOM,5 > > XORLW 1 > > BTFSC RANDOM,3 > > XORLW 1 > > MOVWF RANDOM > > RETLW 0 > > Pretty predictable (short-term), isn't it? Well, yeah... But that's because the original question asked for an 8-bit pseudo-random number generator. "RANDOM" is only 8 bits wide, so the routine produces a 255-step sequence. -Andy === Andrew Warren - KILLspamfastfwdspamBeGoneix.netcom.com === Fast Forward Engineering - San Diego, California === http://www.geocities.com/SiliconValley/2499

Andrew Warren wrote: {Quote hidden}> > D Lloyd <EraseMEPICLISTEraseMEMITVMA.MIT.EDU> wrote: > > > > LFSR: RLF RANDOM,W > > > RLF RANDOM,W > > > BTFSC RANDOM,4 > > > XORLW 1 > > > BTFSC RANDOM,5 > > > XORLW 1 > > > BTFSC RANDOM,3 > > > XORLW 1 > > > MOVWF RANDOM > > > RETLW 0 > > > > Pretty predictable (short-term), isn't it? > > Well, yeah... But that's because the original question asked for > an 8-bit pseudo-random number generator. "RANDOM" is only 8 bits > wide, so the routine produces a 255-step sequence. > > -Andy > Would it be better to take a few bits out of a longer sequence? As an example, you could use 8 bits from a 24 bit random number generator. If it is a shift register type of PRNG like the one above, it may not matter which bits are chosen. For some thoughts on noise generation see my web page: http://www.idcomm.com/personal/ottosen/ Look at the heading "Pseudo-random noise generation like the National Semiconductor MM5437N". There are PIC and Scenix examples. -- Rich > === Andrew Warren - @spam@fastfwd@spam@spam_OUTix.netcom.com > === Fast Forward Engineering - San Diego, California > === http://www.geocities.com/SiliconValley/2499

Richard Ottosen <spamBeGonerottosenKILLspamidcomm.com> wrote: > > the original question asked for an 8-bit pseudo-random number > > generator. "RANDOM" is only 8 bits wide, so the routine produces > > a 255-step sequence. > Would it be better to take a few bits out of a longer sequence? As an > example, you could use 8 bits from a 24 bit random number generator. Richard: It would be DIFFERENT... But "better" would depend on the intended application. If, for example, the application required that the generator never return the same value twice in a row, taking 8 bits out of a longer shift-register WOULDN'T be better. Also, the original question asked for code that used as few registers as possible. An "8 out of 24" solution would require at least 3 or 4 times as many registers as the one-register 8-bit solution. -Andy === Andrew Warren - .....fastfwdspam_OUTix.netcom.com === Fast Forward Engineering - San Diego, California === http://www.geocities.com/SiliconValley/2499

Andrew Warren wrote: {Quote hidden}> > Richard Ottosen <TakeThisOuTrottosen.....TakeThisOuTidcomm.com> wrote: > > > > the original question asked for an 8-bit pseudo-random number > > > generator. "RANDOM" is only 8 bits wide, so the routine produces > > > a 255-step sequence. > > > Would it be better to take a few bits out of a longer sequence? As an > > example, you could use 8 bits from a 24 bit random number generator. > > Richard: > > It would be DIFFERENT... But "better" would depend on the intended > application. If, for example, the application required that the > generator never return the same value twice in a row, taking 8 bits > out of a longer shift-register WOULDN'T be better. > > Also, the original question asked for code that used as few registers > as possible. An "8 out of 24" solution would require at least 3 or 4 > times as many registers as the one-register 8-bit solution. > > -Andy > > === Andrew Warren - TakeThisOuTfastfwdKILLspamspamix.netcom.com > === Fast Forward Engineering - San Diego, California > === http://www.geocities.com/SiliconValley/2499 Andy: You are right. "Better" was a very bad choice of words. No *one* pseudo random generator is best for every application. These shift register/XOR feedback PRNG's work well for making what sounds like noise to the ears. If you feed the bits to a digital to analog convertor and look at the result on a scope, the waveform looks like a bunch of exponential curves. To the eyes this appears very non-random. Even random pulses from nuclear decay is not the right random for all uses. If you want to use the values for a test, make changes, and test again then you don't want true random numbers! It makes it hard to tell whether your change or the different random sequence made the the difference when retesting. I forgot the requirement of only a few registers available. Oops, if all else fails read the instructions :-) The original letter letter also asked about hardware solutions. The first idea that comes to my mind is to implement the hardware of shift registers and XOR gates to do the equivalent of the software that has been suggested for the PIC.

Richard Ottosen <.....rottosenRemoveMEidcomm.com> wrote: > These shift register/XOR feedback PRNG's work well for making what > sounds like noise to the ears. If you feed the bits to a digital to > analog convertor and look at the result on a scope, the waveform > looks like a bunch of exponential curves. To the eyes this appears > very non-random. And then there are those waveforms which look EXTREMELY random on a scope... But when you listen to them, you discover that they're recordings of Beethoven's symphonies. To make the visual representation match your ears' perception of the waveforms, you really have to look at the data not on an oscilloscope, but on a spectrum analyzer. -Andy === Andrew Warren - RemoveMEfastfwdspamBeGoneix.netcom.com === Fast Forward Engineering - San Diego, California === http://www.geocities.com/SiliconValley/2499

> Richard Ottosen <spamBeGonerottosen@spam@spam_OUTidcomm.com> wrote: > > > These shift register/XOR feedback PRNG's work well for making what > > sounds like noise to the ears. If you feed the bits to a digital to > > analog convertor and look at the result on a scope, the waveform > > looks like a bunch of exponential curves. To the eyes this appears > > very non-random. > I am reluctant to enter a discussion I know little about.. (there are great volumes in the library on random number generation). But... If I had to generate random numbers for an application with a PIC it would seem appropriate to generate serious random numbers on a PC and copy them into a rom, and ones pseudo--random PIC routine could access the random numbers from the rom. I imagine pseudo-random selecting random should be fairly usable. _____________________________ Lance Allen Technical Officer Uni of Auckland Psych Dept New Zealand http://www.psych.auckland.ac.nz _____________________________

there are two kinds of random numbers: 1) Statistically random numbers 2) unpredictable numbers The first are important for things like simulations and white noise and such - over time the numbers provided meet mathematical definitions of "random" such that algorithms that count on that will work right. shift registers with feedback generate fine random numbers of this sort. The second type is more often used in assorted cryptography-related schemes. Mathematically correct randomness is less important than being unpredictable and unrepeating. shift registers are NOT good at providing this sort of random number. See: RFC1750 Randomness Recommendations for Security. D. Eastlake, 3rd, S. Crocker, J. Schiller. December 1994. (Format: TXT=73842 bytes) (Status: INFORMATIONAL) for reasonably understandable explanations and some suggestions... true random numbers (generated from radioactive decay or somesuch) are both unpredictable AND statistically random, but they're not so easy to get. BillW

It appears from what I have read that there is actually no formal definition of what "ramdom" means, and that the only thing we really know is that a certain source yields a given distribution, and there is considerable dispute over whether, in fact, one can assume that quantum-mechanical sources are "truely" random, in the sense of being unpredictable or not following laws. Have a look at: http://www.io.com/~ritter/REALRAND/REALRAND.HTM#EssenRand Sean At 03:10 PM 4/18/00 PDT, you wrote: >true random numbers (generated from radioactive decay or somesuch) are both >unpredictable AND statistically random, but they're not so easy to get. > >BillW > | | Sean Breheny | Amateur Radio Callsign: KA3YXM | Electrical Engineering Student \--------------=---------------- Save lives, please look at http://www.all.org Personal page: http://www.people.cornell.edu/pages/shb7 TakeThisOuTshb7spamcornell.edu ICQ #: 3329174

Some time ago I have to make a game were the players have to remember some Tunes. (Like in Saimon4s Game) It was a C-MOS based system, but I was obligated to build a Random Function. I solved it with a 1Mhz oscilator (LM555) and a counter (It was the 4520? or the 4510?). The counter was working all the time. But the value of the counter was reading only when the player press the "NEXT TUNE" botton. It works terrible fine. I bet that you can4t guess the value of a counter that runs at 1Mhz. What do you think? {Original Message removed}

> true random numbers (generated from radioactive decay or somesuch) are both > unpredictable AND statistically random, but they're not so easy to get. In a security project of mine I plan to generate (un)predictable random numbers by implementing an EEPROM based always-increasing counter and encrypting the each output with an algorithm like DES. I believe that this gives me unique "random" numbers that only I can predict (because only I have the secret key).

> It works terrible fine. I bet that you can4t guess the value of a counter > that runs at 1Mhz. Sounds good when asynchronous and fast compared to the read-rate. Like in your particular implementation. A dangerous implementation would be to use the internal TMR of a controller instead of an asynchronous one. Probably you have your keyboard reader in the TMR interrupt. Probably you need a new "random" value when the user starts a game - by pressing the START _key_! THAT would be a bad implementation of the (good) idea. When it comes to security/cryptography, you must avoid that the user can influence the random number algorithm. In your example that could be to remove the external counter and replace it by his own generated signal, and thereby enforce the generation of weak session keys etc.

a no-parts solution to seeding the routine is to use a closed loop counter to trigger the WDT. Because WDT is temperature- sensitive, the LSB of the counter might be random enough for use in seeding the rest of the routine. alice {Quote hidden}> > It works terrible fine. I bet that you can4t guess the value of a counter > > that runs at 1Mhz. > > Sounds good when asynchronous and fast compared to the read-rate. Like in > your particular implementation. > > A dangerous implementation would be to use the internal TMR of a controller > instead of an asynchronous one. Probably you have your keyboard reader > in the TMR interrupt. Probably you need a new "random" value when the > user starts a game - by pressing the START _key_! THAT would be a bad > implementation of the (good) idea. > > When it comes to security/cryptography, you must avoid that the user can > influence the random number algorithm. In your example that could be > to remove the external counter and replace it by his own generated signal, > and thereby enforce the generation of weak session keys etc.