Method for generating a random number sequence and a relative random bit generator

• US 20030219119A1
• Filed: 12/13/2002
• Published: 11/27/2003
• Est. Priority Date: 12/13/2001
• Status: Abandoned Application

• Current Assignee: STMicroelectronics SRL (STMicroelectronics NV)
• Original Assignee: STMicroelectronics SRL (STMicroelectronics NV)
• Inventors: Stojanovski, Toni, Rizzotto, Gianguido, Kocarev, Ljupco, Italia, Francesco, Porto, Domenico
• Application Number:
  US10/319,378
• Publication Number:
  US 20030219119A1
• Time in Patent Office: Days
• US Class Current: 380/28
• CPC Class Codes: G06F 7/588 Random number generators, i.e. based on natural stochastic processes
• CPC Class Codes: H04L 9/0861 Generation of secret information including derivation or calculation of cryptographic keys or passwords

Abstract

A method for generating a random number sequence whose randomness properties are determined a priori, includes defining a parametric map, calculating, in function of parameters of the map, the entropy and the Lyapunov exponent of random number sequences obtainable using the parametric map, and identifying at least a set of values of parameters for which the entropy and the Lyapunov exponent are positive numbers the map has no attracting point. The method further includes assigning a pre-established value as a first feedback value and cyclically carrying out the following steps for generating a random number sequence: determining the parameters inside the set as the numerical values of respective physical quantities, outputting a random number, according to the map with the parameters and the assigned feedback value, and assigning as new feedback value the output random number.

Claims

1. A method for generating a random number sequence, comprising the following steps:

defining a parametric map;

calculating, in function of parameters of said map, the entropy and the Lyapunov exponent of random number sequences obtainable using said parametric map;

identifying at least a set of values (P) of said parameters, for which said entropy and said Lyapunov exponent are positive numbers and said parametric map has no attracting point;

assigning a pre-established value as a first feedback value and carrying out cyclically the following steps for generating a random number sequence;

a) determining said parameters inside said set (P) as the numerical values of respective physical quantities;

b) outputting a random number, according to said map with said parameters and said assigned feedback value;

c) assigning as new feedback value said output random number.

2. The method of claim 1, comprising

calculating the redundancy or the Markov character of the sequence generated by said parametric map;

and

identifying a set of values (P) of said parameters for which the generated sequence has a desired redundancy or Markov character.

3. The method of claim 1 or 2, wherein said map is a piecewise linear one-dimensional parametric map with saturation values.

4. A method for generating a random bit sequence with pre-established entropy and Lyapunov exponent, comprising

defining a pair of sets of values first (C₁) and second (C₂) by a Markov partition of the set of real numbers;

producing random numbers according to the method of one of claims from 1 to 3;

outputting a high (1) or a low (0) random bit for each random number, whether said random number is comprised in said first set (C₁) or said second set (C₂), respectively.

5. The method of claim 4, wherein the output random bit sequence is further filtered by way of a redundancy reduction technique.

6. The method of claim 5, wherein said redundancy reduction technique consists in carrying out the following steps:

producing each bit of the filtered sequence as the sum modulo 2 of a corresponding number (p) of consecutive bit of said output sequence.

7. The method of claim 5, wherein said redundancy reduction technique consists in taking only one bit over a certain number (p) of bits of said output random bit sequence.

8. A closed loop oscillating random bit generator for producing a random bit sequence according to the method of claim 4 for a piecewise linear one-dimensional map with null threshold value (T_L) and constituted by two linear segments having the same slope (k) and opposite constant value (q), comprising an amplifier initially input with a loop excitation signal (I_in) and successively with a feedback signal (I_out), outputting a multiplication signal (I₁) obtained multiplying its input signal (I_in, I_out) by said slope value (k);

a comparing and adding stage producing said feedback signal (I_out) as the sum of, or as the difference between, a multiplication signal (I₁) and a constant signal (I_a) representing said constant value (q), respectively whether said multiplication signal (I₁) is smaller or greater than zero, and producing an active or an inactive random output bit (Q) whether said feedback signal (I_out) is greater or smaller than zero, respectively.

9. The generator of claim 8, wherein said amplifier is a switched current circuit comprising a pair of switched current mirrors (T11, T13, T12;

T14, T30, T15) in parallel between them, whose switches (T12;

T15) are driven by two non overlapping clock signals (Φ

₁, Φ

₂), each switched current mirror has a respective diode connected transistor (T22;

T23) as an active load, and each switch (T12;

T15) has a current terminal connected to a respective anti feed-through capacitor (C1;

C2) and to a respective anti feed-through short-circuited transistor (T26;

T27) driven in phase opposition ({overscore (Φ

₁)}, {overscore (Φ

₂)}). 0