US-12621138-B2 - Method for generating an independent bit sequence

US12621138B2US 12621138 B2US12621138 B2US 12621138B2US-12621138-B2

Abstract

Provided is a method for generating, by a random number generator of a cryptographic system, an independent bit sequence from a binary candidate random stream, said random generator comprising a source of randomness configured to generate a random noise, an analog to digital converter configured to generate a binary raw random stream by digitizing said random noise, said candidate random stream being obtained from said raw random stream. Other embodiments disclosed.

Inventors

Benjamin Duval
Olivier FOURQUIN
Yannick Teglia

Assignees

THALES DIS FRANCE SAS

Dates

Publication Date: 20260505
Application Date: 20221202
Priority Date: 20211203

Claims (6)

1 . A method for generating, by a random number generator of a cryptographic system, an independent bit sequence from a binary candidate random stream, said random number generator comprising a source of randomness configured to generate a random noise, an analog to digital converter configured to generate a binary raw random stream by digitizing said random noise, said candidate random stream being obtained from said raw random stream, said method comprising: performing a test to check the independency of the bits of the binary candidate random stream, comprising: acquiring repeatedly (S 1 ) at least one bit from the candidate random stream until said acquired bits form a test sequence comprising at least N first pairs of successive bits, wherein the value of a first bit of each of said first pairs is 0, and N second pairs of successive bits, wherein the value of a first bit of each of said second pairs is 1, N being a predetermined integer, and counting in said test sequence a number of pairs of successive bits comprising 0 as both first and second bit, called “n00”, and/or a number of pairs of successive bits comprising 0 as first bit and 1 as second bit, called “n01”, until n00+n01=N, and counting in said test sequence a number of pairs of successive bits comprising 1 as both first and second bit, called “n11”, and/or a number of pairs of successive bits comprising 1 as first bit and 0 as second bit, called “n10”, until n11+n10=N, verifying (S 2 ) if the difference between “n00” and “n10” and/or the difference between “n01” and “n11” for said test sequence is within a predetermined acceptance range, if verification is a success, generating (S 3 ) the independent bit sequence from said candidate random stream, wherein a difference, in a sequence of independent bits, between a number of pairs of successive bits comprising 0 as both first and second bit, and a number of pairs of successive bits comprising 1 as first bit and 0 as second bit follows a predetermined distribution and the acceptance range is set to have a chosen probability of false negative for the predetermined distribution in the verification of the independency of the bits of the candidate random stream.
2 . The method of claim 1 , wherein the predetermined acceptance range is based on a standard deviation σ of a Gaussian distribution centered on 0 followed by a difference, in a sequence of independent bits, between a number of pairs of successive bits comprising 0 as both first and second bit, and a number of pairs of successive bits comprising 1 as first bit and 0 as second bit, wherein said standard deviation σ is equal to √(2pqN), with p and q the probability for a bit of the binary candidate random stream of being equal to respectively 0 and 1.
3 . The method of claim 2 , wherein the predetermined acceptance range corresponds to a predetermined confidence interval of said Gaussian distribution.
4 . The method of claim 1 , comprising a step (S 0 ) of configuring said random number generator with a given value of a configuration parameter (Q) on which a level of independency of bits of said candidate random stream depends, and generating said candidate random stream depending on said configuration parameter, and comprising, repeatedly performing, until verification is a success: if verification is a failure for said candidate random stream obtained using said given value of said configuration parameter (Q), generating a new binary candidate random stream from an output of said analog to digital converter using a new value of said configuration parameter (Qnew) defined by increasing or decreasing by a predetermined step the given value of the configuration parameter (Q), and generating the independent bit sequence from said new binary candidate random stream, including performing said test to check the independency of the bits of the new binary candidate random stream.
5 . The method of claim 4 , wherein said candidate random stream is obtained by under-sampling said raw random stream and the configuration parameter (Q) is an under-sampling factor used for performing said under-sampling.
6 . A cryptographic system comprising a random number generator, said random number generator comprising a source of randomness configured to generate a random noise and an analog to digital converter configured to generate a binary raw random stream by digitizing the random noise generated by the source of randomness, said random number generator being configured to perform the steps of the method for generating an independent bit sequence from a binary candidate random stream as follows, said candidate random stream being obtained from said raw random stream, performing a test to check the independency of the bits of the binary candidate random stream, comprising: acquiring repeatedly (S 1 ) at least one bit from the candidate random stream until said acquired bits form a test sequence comprising at least N first pairs of successive bits, wherein the value of a first bit of each of said first pairs is 0, and N second pairs of successive bits, wherein the value of a first bit of each of said second pairs is 1, N being a predetermined integer, and counting in said test sequence a number of pairs of successive bits comprising 0 as both first and second bit, called “n00”, and/or a number of pairs of successive bits comprising 0 as first bit and 1 as second bit, called “n01”, until n00+n01=N, and counting in said test sequence a number of pairs of successive bits comprising 1 as both first and second bit, called “n11”, and/or a number of pairs of successive bits comprising 1 as first bit and 0 as second bit, called “n10”, until n11+n10=N, verifying (S 2 ) if the difference between “n00” and “n10” and/or the difference between “n01” and “n11” for said test sequence is within a predetermined acceptance range, if verification is a success, generating (S 3 ) the independent bit sequence from said candidate random stream, wherein a difference, in a sequence of independent bits, between a number of pairs of successive bits comprising 0 as both first and second bit, and a number of pairs of successive bits comprising 1 as first bit and 0 as second bit follows a predetermined distribution and the acceptance range is set to have a chosen probability of false negative for the predetermined distribution in the verification of the independency of the bits of the candidate random stream.

Description

FIELD The invention relates to the field of random number generator, and more particularly to a method for ensuring the independency of the bits of a binary random sequence. BACKGROUND Random numbers are needed for securely performing many sensitive operations, such as for masking sensitive data in a cryptographic operation. Pseudo Random Number Generators (PRNG) or Physical True Random Number Generators (PTRNG) may be used to generate such random numbers. The random numbers produced by such generators should be truly unpredictable otherwise an attacker could guess the next value produced by such a generator and remove the protection provided by the usage of a random number. In order to be unpredictable the output stream of a PTRNG should be as close as possible to an independent and identically distributed (IID) distribution. The biais of such an output stream should be minimal: in case of a binary stream, the proportion of 0 and 1 in the output stream should be the same. Such a property is easy to verify by checking in a long stream that the proportion of 0 or 1 is within a predetermined range around 0.5. Another property to be verified is the independency of the bits of the stream one to another. The probability for a given bit in the stream to be equal to 0 or 1 should not depend on the values taken by previous bits in the stream. Properly testing the independency of an output stream of a random generator often requires storing a long random sequence on which an independency test is run, such as a test based on autocorrelation of the sequence. Therefore, such tests cannot be performed online, on-the-fly on the output stream by the RNG itself, but are rather a posteriori tests to be performed by a computing device with bigger computing and storage means such as a computer. Lighter, on-the-fly, tests exist, such as tests checking for abusive repetitions of a given value within the random sequence in a timeframe, but they have a much larger false negative rate. Therefore, there is a need for a method, able to be performed on-the-fly on an output stream of a random generator, and enabling to accurately verify the independency of the bits of the output stream. SUMMARY The invention aims at solving the above mentioned technical problem. For this purpose and according to a first aspect, this invention therefore relates to a method for generating, by a random number generator of a cryptographic system, an independent bit sequence from a binary candidate random stream, said random generator comprising a source of randomness configured to generate a random noise, an analog to digital converter configured to generate a binary raw random stream by digitizing said random noise, said candidate random stream being obtained from said raw random stream, said method comprising: performing a test to check the independency of the bits of the binary candidate random stream, comprisingacquiring repeatedly, at least one bit from the candidate random stream until said acquired bits form a test sequence comprising at least N first pairs of successive bits, wherein the value of a first bit of each of said first pairs is 0, and N second pairs of successive bits, wherein the value of a first bit of each of said second pairs is 1, N being a predetermined integer, and counting in said test sequence a number of pairs of successive bits comprising 0 as both first and second bit, called “n00”, and/or a number of pairs of successive bits comprising 0 as first bit and 1 as second bit, called “n01”, until n00+n01=N, and counting in said test sequence a number of pairs of successive bits comprising 1 as both first and second bit, called “n11”, and/or a number of pairs of successive bits comprising 1 as first bit and 0 as second bit, called “n10”, until n11+n10=N, verifying if the difference between “n00” and “n10” and/or the difference between “n01” and “n11” for said test sequence is within a predetermined acceptance range, if verification is a success, generating the independent bit sequence from said candidate random stream. By doing so, it is verified, with a very limited amount of calculation, if the distributions of bit pairs in the candidate random stream are characteristic of a binary sequence in which bits are independent one from each other. The predetermined acceptance range may be based on a standard deviation a of a Gaussian distribution centered on 0 followed by a difference, in a sequence of independent bits, between a number of pairs of successive bits comprising 0 as both first and second bit, and a number of pairs of successive bits comprising 1 as first bit and 0 as second bit, and said standard deviation σ may be equal to √(2 pqN), with p and q the probability for a bit of the binary candidate random stream of being equal to respectively 0 and 1. The predetermined acceptance range may correspond to a predetermined confidence interval of said Gaussian distribution. Such an acceptance range enables to have a chos