Random number slip and swap generators

• US 7,206,797 B2
• Filed: 04/14/2003
• Issued: 04/17/2007
• Est. Priority Date: 04/14/2003
• Status: Expired due to Fees

• Current Assignee: SanDisk IL Ltd. (Western Digital Corporation)
• Original Assignee: M-Systems Flash Disk Pioneers Ltd. (Western Digital Corporation)
• Inventors: Gressel, Carmi David, Cooper, Simon, Slobodkin, Michael, Aizman, Evgeny, Shevachman, Alex
• Primary Examiner(s): MALZAHN, DAVID H
• Application Number:
  US10/413,430
• Publication Number:
  US 20040205095A1
• Time in Patent Office: 1,464 Days
• Field of Search: 708/250, 708/252
• US Class Current: 708/250
• CPC Class Codes: G06F 2207/583 Serial finite field implementation, i.e. serial implementation of finite field arithmetic, generating one new bit or trit per step, e.g. using an LFSR or several independent LFSRs; also includes PRNGs with parallel operation between LFSR and outputs
• CPC Class Codes: G06F 7/582 Pseudo-random number generators
• CPC Class Codes: G06F 7/588 Random number generators, i.e. based on natural stochastic processes
• CPC Class Codes: H03K 3/84 Generating pulses having a predetermined statistical distribution of a parameter, e.g. random pulse generators

Abstract

A microelectronic apparatus and method for generating random binary words including at least one clocked pseudorandom binary number sequence generator normally operative to generate a cyclic output sequence of binary numbers, each number including a string of binary symbols, the cyclic output sequence including a basic sequence which is generated repeatedly, at least one bit stream generator generating a clocked bit stream including a stream of binary symbols of a first type occasionally interrupted by a binary symbol of a second type, wherein a first varying time interval between the occasional interruptions is intractably correlated to the output sequence of the number sequence generator, wherein each occurrence of an interruption of the stream of binary symbols of the first type by a binary symbol of the second type causes a pseudorandom modification of the cyclic output sequence of the number sequence generator and a sampling device operative to sample the cyclic output sequence of binary numbers thereby to generate a sampled output sequence including at least one sampled binary word.

Claims

1. A microelectronic apparatus for generating random binary words comprising:

at least one clocked pseudorandom binary number sequence generator normally operative to generate a cyclic output sequence of binary numbers, each number comprising a string of binary symbols, the cyclic output sequence comprising a basic sequence which is generated repeatedly;

at least one bit stream generator generating a clocked bit stream including a stream of binary symbols of a first type occasionally interrupted by a binary symbol of a second type, wherein a first varying time interval between the occasional interruptions is intractably correlated to the output sequence of said number sequence generator, wherein each occurrence of an interruption of the stream of binary symbols of the first type by a binary symbol of the second type causes a pseudorandom modification of the cyclic output sequence of said number sequence generator; and

a sampling device operative to sample said cyclic output sequence of binary numbers thereby to generate a sampled output sequence comprising at least one sampled binary word.

2. Apparatus according to claim 1 wherein the sampling device is operative to sample responsive to receipt of CPU requests and wherein sampling responsive to at least one CPU request occurs a random waiting interval after the CPU request has been made.

3. Apparatus according to claim 1 wherein the sampling device is operative to sample responsive to receipt of CPU requests and wherein sampling responsive to at least one CPU request occurs during the clock cycle immediately following the CPU request.

4. Apparatus according to claim 1 wherein the pseudorandom modification comprises a pseudorandom displacement.

5. Apparatus according to claim 4 wherein the clocked pseudorandom binary number sequence generator comprises a feedback shift register and wherein the pseudorandom displacement is caused by complementing the serial feedback bit in the feedback shift register using pulsed “

1”

bits which are externally generated at intractably difficult to estimate intervals of time.

6. Apparatus according to claim 1 wherein the pseudorandom modification of the cyclic output sequence comprises a pseudorandom cycle rearrangement.

7. Apparatus according to claim 6 wherein the pseudorandom cycle rearrangement is caused by a Random Swap of the set of feedback taps actuated by an externally generated pulsed “

1”

bit at an intractably difficult to estimate clock period.

8. Apparatus according to claim 1 wherein said pseudorandom modification comprises a random slip in which a portion of the cyclic output sequence is omitted.

9. Apparatus according to claim 1 wherein said pseudorandom modification comprises a random swap in which the basic sequence is modified.

10. Apparatus according to claim 9 wherein said random swap comprises a permutation of the basic sequence.

11. Apparatus according to claim 1 wherein said at least one bit stream generator comprises at least two bit stream generators generating first and second streams, wherein each occurrence of an interruption of the first stream by a binary symbol of the second type causes a random slip in which a portion of the cyclic output sequence is omitted and each occurrence of an interruption of the second stream by a binary symbol of the second type causes a random swap in which the basic sequence is modified.

12. A microelectronic apparatus according to claim 1 and also comprising an apparatus for enhancing the randomness of said random binary words including apparatus for generating an output binary stream by combining a plurality of n-bit samplings of said sampled output sequence.

13. A microelectronic apparatus according to claim 12 wherein said apparatus for generating comprises XOR apparatus for XORING the plurality of n-bit samplings.

14. A microelectronic apparatus according to claim 1 and also comprising:

an internal XOR masking intermediate latch operative to receive said sampled output sequence and at least a portion of at least one of said cyclic output sequence and said clocked bit stream and to mask at least one of said at least one of said cyclic output sequence and said clocked bit stream by word-wise XOR, thereby to generate an internal XOR masked output; and

an output port for receiving the internal XOR masked output.

15. A microelectronic apparatus for generating binary words comprising:

at least one clocked pseudorandom binary number sequence generator normally operative to generate a cyclic output sequence of binary numbers, each number comprising a string of binary symbols, the cycling output sequence comprising a basic sequence which is generated repeatedly;

at least one bit stream generator generating a clocked bit stream including a stream of binary symbols of a first type occasionally interrupted by a binary symbol of a second type,

wherein each occurrence of an interruption of the stream of binary symbols of the first type by a binary symbol of the second type causes a pseudorandom modification of the cyclic output sequence of said number sequence generator,

wherein said pseudorandom modification comprises a random slip in which a portion of the cyclic output sequence is omitted.

16. A microelectronic apparatus for generating binary words comprising:

at least one clocked pseudorandom binary number sequence generator normally operative to generate a cyclic output sequence of binary numbers, each number comprising a string of binary symbols, the cycling output sequence comprising a basic sequence which is generated repeatedly;

at least one bit stream generator generating a clocked bit stream including a stream of binary symbols of a first type occasionally interrupted by a binary symbol of a second type,

wherein each occurrence of an interruption of the stream of binary symbols of the first type by a binary symbol of the second type causes a pseudorandom modification of the cyclic output sequence of said number sequence generator,

wherein said pseudorandom modification comprises a random swap in which the basic sequence is modified.

17. Apparatus according to claim 16 wherein said pseudorandom modification also comprises a random slip in which a portion of the cyclic output sequence is omitted.

18. A sampling device comprising:

an interface for receiving a CPU request to sample an at least pseudorandom binary stream; and

a sampler operative to sample the binary stream, responsive to at least one CPU request received by the interface, after a random waiting interval has elapsed.

19. A method for generating a sequence of random numbers comprising:

using an nLFSR to generate an nLFSR generated string;

operating a random slip actuating triggering process which randomly and without correlation to the nLSFR generates at least one slip actuating triggers respectively triggering at least one slip generating process, thereby to define a modified string comprising the nLFSR generated string to which the at least one slip generating processes have been applied, wherein each slip generating process, responsive to occurrence of a slip actuating trigger, reverses the most significant bit of a current number in said nLFSR generated string; and

operating a random sampling triggering process which, randomly and without correlation to the nLSFR and without correlation to the random slip actuating triggering process, triggers a sampling of the modified string, thereby to generate a subsequence of the modified string which comprises an output string of random numbers.

20. A method according to claim 19 and also comprising:

masking internal variables of at least one of said nLFSR and said at least one slip actuating trigger by word-wise XOR.