Pipelined digital randomizer based on permutation and substitution using data sampling with variable frequency and non-coherent clock sources

• US 6,760,739 B2
• Filed: 03/01/2001
• Issued: 07/06/2004
• Est. Priority Date: 03/01/2001
• Status: Expired due to Fees

• Current Assignee: Exelis Incorporated (L3Harris Technologies, Inc.)
• Original Assignee: Corrent Corp.
• Inventors: Takahashi, Richard J.
• Primary Examiner(s): Malzahn, David H.
• Application Number:
  US09/796,913
• Publication Number:
  US 20020124033A1
• Time in Patent Office: 1,223 Days
• Field of Search: 708/250-256
• US Class Current: 708/250
• CPC Class Codes: G06F 7/58 Random or pseudo-random number generators
• CPC Class Codes: G06F 7/588 Random number generators, i.e. based on natural stochastic processes

Abstract

A system and method for generating an indeterminate random digital data string based on a sampling source, which varies in frequency and phase, sampling an entropy source that also varies in frequency and phase, and additionally based on the principles of permutation and substitution. The system includes a random number generation circuit and a data substitution circuit coupled to receive random data output from the random number generation circuit. A data permutation circuit is coupled to receive substituted random data output from the data substitution circuit. A data compression circuit is coupled to receive permuted and substituted random data output from the permutation circuit and output at least a portion of the indeterminate random data string. A plurality of variable frequency clocks, each operating at different clock frequencies, are selectively coupled to various of the circuits within the system.

Claims

1. A system for generating an indeterminate random data string, comprising:

a first random number generation circuit;

a data substitution circuit coupled to receive random data output from said random number generation circuit, wherein the data substitution circuit uses the random data output as addresses to generate first and second random data segments which are concatenated to form substituted random data output;

a data permutation circuit coupled to receive the substituted random data output from said data substitution circuit and providing permuted data output; and

a data compression circuit coupled to receive the permuted data output from said permutation circuit and output at least a portion of the indeterminate random data string having reduced data length as compared to the permuted data output.

2. A system for generating an indeterminate random data string, comprising:

a first random number generation circuit;

a data substitution circuit coupled to receive, random data output from said random number generation circuit;

a data permutation circuit coupled to receive substituted random data output from said data substitution circuit;

a data compression circuit coupled to receive the permuted and substituted random data output from said permutation circuit and output at least a portion of the indeterminate random data string; and

a plurality of variable frequency clocks, each operating at different clock frequencies, selectively coupled to at least said random number generation circuit, said data substitution circuit, said data permutation circuit, and said data compression circuit.

3. The system of claim 2, wherein Said plurality of variable frequency clocks includes at least a first, a second, and a third variable frequency clock, operating at a first variable frequency magnitude, a second variable frequency magnitude, and a third variable frequency magnitude, respectively.

4. The system of claim 3, wherein the first variable frequency magnitude is an odd multiple of the second variable frequency magnitude and a different odd multiple of the third variable frequency magnitude.

5. The system of claim 3, wherein the first variable frequency magnitude is greater than the second variable frequency magnitude, and the second variable frequency magnitude is greater than the third variable frequency magnitude.

6. The system of claim 3, wherein the first variable frequency magnitude is a prime number.

7. The system of claim 6, wherein the prime number is greater than 80 MHz.

8. The system of claim 2, wherein each of said plurality of variable frequency clocks comprise unstable phase-lock-loop (PLL) clock circuits, which vary in frequency and phase during operation.

9. The system of claim 2, wherein each of said plurality of variable frequency clocks comprises a rate multiplier counter circuit, which vary in frequency and phase during operation.

10. The system of claim 2, wherein said first random number generation circuit comprises:

an N-bit pseudo random number generator circuit; and

M number of JK-type flip-flops each coupled to receive two of the N-bits output by said N-bit pseudo random number generator circuit.

11. The system of claim 10, further comprising:

a first variable frequency clock, coupled to a clock input port of said N-bit pseudo random number generator circuit, causing said N-bit pseudo random number generator circuit to operate at a first variable frequency magnitude; and

a second variable frequency clock, coupled to a clock input of each of said JK flip-flops, causing each of said JK flip-flops to operate at a second variable frequency magnitude.

12. The system of claim 11, wherein the first variable frequency magnitude is an odd multiple of the second variable frequency magnitude.

13. The system of claim 12, wherein the first variable frequency magnitude is approximately nine times the second variable frequency magnitude.

14. The system of claim 12, wherein the first variable frequency magnitude is a prime number.

15. The system of claim 14, wherein the prime number is greater than 80 MHz.

16. The system of claim 10, wherein M and N are both integers, and M is less than N/2.

17. The system of claim 10, wherein M is equal to 48 and N is equal to 128.

18. The system of claim 10, wherein the two bits coupled to each of said JK flip-flops are non-adjacent bits.

19. The system of claim 2, wherein the data substitution circuit comprises a plurality of substitution boxes (S-boxes).

20. The system of claim 19, wherein each of said plurality of S-boxes is based on Data Encryption Standard (DES) S-boxes.

21. The system of claim 19, wherein each of said plurality of S-boxes is arranged in a symmetric n×

n array configuration.

22. The system of claim 21, wherein n is an integer equal to 24.

23. The system of claim 2, wherein said data permutation circuit comprises a plurality of Benes-type non-blocking switching networks.

24. The system of claim 23, wherein each of said Benes networks comprises a plurality of individual permuter elements arranged in an n×

n array, with each individual permuter element including an element select line.

25. The system of claim 24, wherein said data permutation circuit further comprises a second random number generation circuit including individual output lines, coupled to each of said individual permuter element select lines.

26. The system of claim 25, wherein said second random number generation circuit comprises:

an R-bit pseudo random number generator circuit; and

L number of JK-type flip-flops each coupled to receive two of the R-bits output by said R-bit random number generator portion.

27. The system of claim 26, wherein the two bits coupled to each of said JK flip-flops are non-adjacent bits.

28. The system of claim 26, further comprising:

a first variable frequency clock, coupled to a clock input port of said R-bit pseudo random number generator circuit, causing said R-bit pseudo random number generator circuit to operate at a first variable frequency magnitude; and

a second variable frequency clock, coupled to a clock input of each of said JK flip-flops, causing each of said JK flip-flops to operate at a second variable frequency magnitude.

29. The system of claim 28, wherein the first variable frequency magnitude is an odd multiple of the second variable frequency magnitude.

30. The system of claim 29, wherein the first variable frequency magnitude is approximately nine times the second variable frequency magnitude.

31. The system of claim 29, wherein the first variable frequency magnitude is a prime number.

32. The system of claim 31, wherein the prime number is greater than 80 MHz.

33. The system of claim 24, wherein said data permutation circuit further comprises:

a first crossbar switching circuit coupled between said data substitution circuit and said plurality of Benes networks; and

a second crossbar switching circuit coupled between said plurality of Benes networks and said data compression circuit.

34. The system of claim 33, wherein said first and second crossbar switching circuits each comprises a plurality of individual switch circuits that include (i) two inputs ports, (ii) two output ports, and (iii) a switch selection port.

35. The system of claim 34, wherein said data permutation circuit further comprises a second random number generation circuit including output lines individually coupled to (i) each of said individual permuter element select lines and (ii) each of said switch selection ports.

36. The system of claim 35, wherein said second random number generation circuit comprises:

an R-bit pseudo random number generator circuit; and

L number of JK-type flip-flops each coupled to receive two of the R-bits output by said R-bit random number generator portion.

37. The system of claim 36, wherein the two bits coupled to each of said JK flip-flops are non-adjacent bits.

38. The system of claim 36, further comprising a first variable frequency clock, coupled to a clock input port of said R-bit pseudo random number generator circuit, causing said R-bit pseudo random number generator circuit to operate at a first variable frequency;

and

a second variable frequency clock, coupled to a clock input of each of said JK flip-flops, causing each of said JK flip-flops to operate at a second frequency.

39. The system of claim 38, wherein the first variable frequency magnitude is an odd multiple of the second variable frequency magnitude.

40. The system of claim 39, wherein the first variable frequency magnitude is approximately nine times the second variable frequency magnitude.

41. The system of claim 39, wherein the first variable frequency magnitude is a prime number.

42. The system of claim 41, wherein the prime number is greater than 80 MHz.

43. The system of claim 2, wherein said data compression circuit comprises a non-linear logic element (NLE).

44. The system of claim 43, wherein said NLE comprises:

a plurality of logic NAND gates, each of said logic NAND gates including (i) two inputs, each selectively coupled to receive a predetermined bit of the permuted and substituted random data, and (ii) an output; and

a logic exclusive-OR (XOR) tree circuit including (i) a plurality of inputs, select ones of which are coupled to each of said logic NAND gate outputs, and others of which are coupled to receive the permuted and substituted random data that is not selectively coupled to one of said plurality of logic NAND gates and (ii) at least two outputs each providing identical portions of the indeterminate random data string.

45. The system of claim 44, wherein the predetermined bits coupled to each of said logic NAND gate inputs are non-adjacent bits.

46. The system of claim 43, further comprising:

an M-bit sampling source selectively sampling the permuted and substituted random data output from said permutation circuit and transmitting the sampled data to said NLE.

47. The system of claim 46, wherein said M-bit sampling source comprises M number of JK-type flip-flops each coupled to receive two of the permuted and substituted random data bits output from said permutation circuit.

48. The system of claim 47, further comprising a third variable frequency clock, coupled to a clock input of each of said JK flip-flops, causing each of said JK flip-flops to operate at a third frequency.

49. The system of claim 43, wherein said NLE comprises:

a plurality of logic NAND gates, each of said logic NAND gates including (i) two inputs, each coupled to receive one bit of the permuted and substituted random data, and (ii) an output; and

a logic exclusive-OR (XOR) tree circuit including (i) a plurality of inputs individually coupled to each of said logic NAND gate outputs and (ii) at least two outputs each providing identical portions of the indeterminate random data string.

50. The system of claim 49, wherein the bits coupled to each of said logic WAND gate inputs are non-adjacent bits.

51. The system of claim 2, further comprising a plurality of N-bit serial registers each coupled to receive unique portions of the indeterminate random data string from said data compression circuit and output an N-bit indeterminate data string.

52. The system of claim 51, wherein N is an integer equal to 128.

53. The system of claim 51, further comprising:

a processor coupled to receive the N-bit indeterminate random data string from each of said plurality of N-bit serial registers.

54. The system of claim 53, wherein the processor performs functionality testing of the N-bit indeterminate random data string.

55. The system of claim 53, wherein the processor performs testing of the N-bit indeterminate data string in each of the N-bit serial registers to determine which of the plurality of N-bit serial registers outputs the N-bit indeterminate data string.

56. The system of claim 53, wherein the processor combines the N-bit indeterminate data string in each of the plurality of N-bit serial registers together and outputs the combination thereof.

57. A method of generating an indeterminate random data string, comprising:

generating a first random number of a first predetermined bit length;

substituting the first random number with different data based upon the first random number, wherein the first random number provides addresses to generate first and second random data segments which are concatenated to form substituted random data;

permuting the substituted random data to provide permuted data; and

compressing the permuted data to form at least a portion of the indeterminate random data string having reduced data length as compared to the permuted data.

58. A method of generating an indeterminate random data string, comprising:

generating a first random number of a first predetermined bit length by sampling an entropy source that varies in frequency and phase with a first sampling source that also varies in frequency and phase;

substituting the first random number with different data based upon the first random number;

permuting the substituted random data; and

compressing the permuted and substituted random data to form at least a portion of the indeterminate random data string.

59. The method of claim 58, further comprising:

permuting random data output from the entropy source prior to the random data being sampled by the sampling source.

60. The method of claim 58, wherein the substitution step comprises:

dividing the first random number into one or more random addresses of a predetermined bit length;

accessing predetermined substitution data based upon the one or more random addresses; and

concatenating the substitution data to form the substituted random data having the first predetermined bit length.

61. The method of claim 58, wherein the step of permuting the substituted random data comprises randomly permuting the substituted random data based on a generated second random number.

62. The method of claim 61, wherein the second random number is generated by sampling a second entropy source that varies in frequency and phase with a second sampling source that also varies in frequency in phase.

63. The method of claim 58, wherein the step of compressing the permuted and substituted random data comprises selectively performing logic NAND operations on predetermined pairs or bits of the permuted and substituted random data and performing a series of logic XOR operations on the logically NANDed data and the remaining bits of the permuted and substituted random data string not logically NANDed.

64. The method of claim 58, wherein the step of compressing the permuted and substituted random data comprises selectively performing logic NAND operations on the permuted and substituted random data that is sampled by the third sampling source and performing a series of logic XOR operations on the logically NANDed data.

65. The method of claim 58, further comprising the step of sampling the randomly permuted and substituted data with a third sampling source that varies in frequency and phase, prior to compressing the permuted and substituted random data.

66. The method of claim 65, wherein the step of compressing the permuted and substituted random data comprises selectively performing logic NAND operations on predetermined pairs of bits of the permuted and substituted random data and performing a series of logic XOR operations on the logically NANDed data and the remaining bits of the permuted and substituted random data string not logically NANDed.

67. The method of claim 65, wherein the step of compressing the permuted and substituted random data comprises selectively performing logic NAND operations on the permuted and substituted random data that is sampled by the third sampling source and performing a series of logic XOR operations on the logically NANDed data.

68. A system for generating an indeterminate random data string, comprising:

a first random number generation circuit comprising (i) an N-bit pseudo random number generator circuit and (ii) M number of JK-type flip-flops each coupled to receive two of the N-bits output by said N-bit pseudo random number generator circuit;

a data substitution circuit, including a plurality of substitution boxes (S-boxes) arranged in an n×

n array configuration, coupled to receive random data output from said first random number generation circuit;

a data permutation circuit coupled to receive substituted random data output from said data substitution circuit, said data permutation circuit comprising a plurality of Benes-type non-blocking switching networks each formed from a plurality of individual permuter elements arranged in an n×

n array, with each individual permuter element including an element select line;

a second random number generation circuit including output lines individually coupled to each of said individual permuter element select lines, said second random number generation circuit including (i) an R-bit pseudo random number generator circuit and (ii) L number of JK-type flip-flops each coupled to receive two of the R-bits output by said R-bit random number generator portion;

a data compression circuit coupled to receive permuted and substituted random data output from said permutation circuit and output at least a portion of the indeterminate random data string;

a first variable frequency clock, coupled to a clock input port of said N-bit pseudo random number generator circuit and said R-bit pseudo random number generation circuit, causing each to operate at a first variable frequency magnitude; and

a second variable frequency clock, coupled to a clock input of each of said L and M number of JK flip-flops, causing each to operate at a second variable frequency magnitude.

69. The system of claim 68, further comprising:

an N-bit sampling source selectively sampling the permuted and substituted random data output from said permutation circuit and transmitting the sampled data to said data compression circuit, said M-bit sampling source including M number of JK-type flip-flops each coupled to receive two of the permuted and substituted random data bits output from said permutation circuit.

70. The system of claim 69, further comprising:

a third variable frequency clock, coupled to a clock input of each of said M number of JK flip-flops, causing each to operate at a third frequency.

71. The system of claim 68, wherein said data permutation circuit further comprises:

an input crossbar switching circuit including a plurality of individual switching circuits having a plurality of input ports and output ports, and a switch selection port; and

an output crossbar switching circuit, having a plurality of input ports and output ports, and a switch selection port, coupled to an output portion of said plurality of Benes networks,

wherein said second random number generation circuit includes output lines individually coupled to each of said switch selection ports.

72. A method of generating an indeterminate random data string, comprising:

sampling an entropy source that varies in frequency and phase with a first sampling source that also varies in frequency and phase to generate a first random number of a first predetermined bit length;

substituting the first random number with different data based upon the first random number;

sampling a second entropy source that varies in frequency and phase with a second sampling source that also varies in frequency in phase to generate a second random number of a second predetermined bit length;

randomly permuting the substituted random data based on the generated second random number;

sampling the randomly permuted and substituted data with a third sampling source that varies in frequency and phrase, prior to compressing the permuted and substituted random data; and

compressing the permuted and substituted random data to form at least a portion of the indeterminate random data string.

73. The method of claim 72, further comprising:

permuting random data output from the entropy source prior to the random data being sampled by the sampling source.

74. The method of claim 72, wherein the substitution step comprises:

dividing the first random number into one or more random addresses of a predetermined bit length;

accessing predetermined substitution data based upon the one or more random addresses; and

concatenating the substitution data to form the substituted random data having the first predetermined bit length.

75. The method of claim 72, wherein the step of permuting the substituted random data comprises randomly permuting the substituted random data based on a generated second random number.

76. The method of claim 72, wherein the step of compressing the permuted and substituted random data comprises selectively performing logic NAND operations on predetermined pairs of bits of the permuted and substituted random data and performing a series of logic XOR operations on the logically NANDed data and the remaining bits of the permuted and substituted random data string not logically NANDed.

77. The method of claim 72, wherein the step of compressing the permuted and substituted random data comprises selectively performing logic NAND operations on the permuted and substituted random data that is sampled by the third sampling source and performing a series of logic XOR operations on the logically NANDed data.

78. A system for generating an indeterminate random data string, comprising:

a first random number generation circuit comprising (i) an N-bit pseudo random number generator circuit and (ii) M number of JK-type flip-flops each coupled to receive two of the N-bits output by said N-bit pseudo random number generator circuit;

a data substitution circuit, including a plurality of substitution boxes (S-boxes) arranged in an n×

n array configuration, coupled to receive random data output from said first random number generation circuit;

a data permutation circuit coupled to receive substituted random data output from said data substitution circuit, said data permutation circuit comprising;

an input crossbar switching circuit including a plurality of individual switching circuits having a plurality of input ports and output ports, and a switch selection port;

a plurality of Benes-type non-blocking switching networks including an input portion coupled to said input crossbar switching circuit, each of said networks formed from a plurality of individual permuter elements arranged in an n×

n array, with each individual permuter element including an element select line; and

an output crossbar switching circuit, having a plurality of input ports and output ports, and a switch selection port, coupled to an output portion of said plurality of Benes networks;

a second random number generation circuit including output lines individually coupled to (i) each of said individual permuter element select lines and (ii) each of said switch selection ports, said second random number generation circuit including (i) an R-bit pseudo random number generator circuit and (ii) L number of JK-type flip-flops each coupled to receive two of the R-bits output by said R-bit random number generator portion;

a data compression circuit coupled to receive permuted and substituted random data output from said permutation circuit and output at least a portion of the indeterminate random data string, said data compression circuit comprising;

a plurality of logic NAND gates, each of said logic NAND gates including (i) two inputs, each selectively coupled to receive a predetern1/2ined bit of the permuted and substituted random data, and (ii) an output; and

a logic exclusive-OR (XOR) tree circuit including (i) a plurality of inputs, select ones of which are coupled to each of said logic NAND gate outputs, and others of which are coupled to receive the permuted and substituted random data that is not selectively coupled to one of said plurality of logic NAND gates and (ii) at least two outputs each providing two different portions of the indeterminate random data string;

an M-bit sampling source selectively sampling the permuted and substituted random data output from said permutation circuit and transmitting the sampled data to said data compression circuit, said M-bit sampling source including M number of JK-type flip-flops each coupled to receive two of the permuted and substituted random data bits output from said permutation circuit;

a first variable frequency clock, coupled to a clock input port of said N-bit pseudo random number generator circuit and said R-bit pseudo random number generation circuit, causing each to operate at a first variable frequency magnitude;

a second variable frequency clock, coupled to a clock input of each of said L and M number of JK flip-flops, causing each to operate at a second variable frequency magnitude; and

a third variable frequency clock, coupled to a clock input of each of said M number of JK flip-flops, causing each to operate at a third frequency.

79. A method of generating an indeterminate random data string, comprising:

sampling an entropy source that varies in frequency and phase with a first sampling source that also varies in frequency and phase to generate a first random number of a first predetermined bit length;

dividing the first random number into one or more random addresses of a predetermined bit length;

accessing predetermined substitution data based upon the one or more random addresses;

concatenating the substitution data to form the substituted random data having the first predetermined bit length;

sampling a second entropy source that varies in frequency and phase with a second sampling source that also varies in frequency in phase to generate a second random number of a second predetermined bit length;

randomly permuting the substituted random data based on the generated second random number;

sampling the randomly permuted and substituted data with a third sampling source that varies in frequency and phase, prior to compressing the permuted and substituted random data; and

selectively performing logic NAND operations on predetermined pairs of bits of the permuted and substituted random data, and performing a series of logic XOR operations on the logically NANDed data and the remaining bits of the permuted and substituted random data string not logically NANDed, to compress the sampled data to form at least a portion of the indeterminate random data string.