Abstract:
A method for determining the entropy of a noise source providing a bit flow, a method and a device for generating a bit flow, including parallelizing the bit flow to obtain first words over a first number of bits, applying to the successive words a compression function, and evaluating a second number of bits over which the compression function provides its results, the second number representing the number of useful bits in the first words.

Description:
BACKGROUND OF THE INVENTION  
       [0001]     1. Field of the Invention  
         [0002]     The present invention generally relates to the non-deterministic determination of numbers and more specifically to the processing of a bit flow provided by a non-deterministic noise source (desired to be random).  
         [0003]     The present invention, for example, applies to the non-deterministic generation of digital quantities intended to form ciphering or authentication keys used in cryptographic functions.  
         [0004]     2. Discussion of the Related Art  
         [0005]     The generation of a bit flow to form digital quantities in non-deterministic fashion uses a noise source capable of providing, directly or after conversion, a flow of binary states. The noise source may be digital or analog and exploit various disturbances (thermal noise, frequency variation, of an oscillator, etc.). The bit flow is generally exploited by words of fixed size (number of bits). The bit sequence distribution which characterizes the generator quality regarding the random character is evaluated by taking into account the desired word size.  
         [0006]     It is frequently attempted to improve the random character of a bit flow by submitting it to processings downstream of the noise source. Such is the case, for example, for devices known as debiasers.  
         [0007]     However, another problem regarding the generation of numbers, especially to form authentication or ciphering keys relates to the bit flow entropy, that is, the amount of useful information borne with respect to the number of transmitted bits. This phenomenon can be understood by considering a 64-bit word formed by the repeating of 8 identical bytes having equiprobable bit combinations. The useful information only comprises 8 bits, the other bits of the 64-bit word bearing no non-redundant information. The entropy then is one eighth with respect to a maximum entropy (1).  
         [0008]     For example, a digital quantity generator to form a ciphering or authentication key over 1,024 bits cannot be considered as effectively providing keys over 1,024 bits if the representation of these keys is not optimal regarding entropy, that is, if some bits contain no useful information. The entropy is calculated according to the size of the words taken into account with respect to the possible repeating of sequences of lower sizes in the flow generated in non-deterministic fashion. Assuming that each byte in fact has a single entropy bit (entropy of one eighth), this amounts to stating that the key over 1,024 bits is equivalent to a key over 128 bits.  
         [0009]     To qualify a random number generator, statistic entropy tests are conventionally performed by examining the results a posteriori to determine the number of information-bearing bits per word.  
         [0010]     An example of such a test method is described in article “On the Security of Random Sources” by J-S. Coron published in 1999 in H. Imai and Y. Zheng (Eds.): PKC&#39;99, LNCS 1560, pp. 29-42 (Springer Verlag).  
         [0011]     A disadvantage of such statistic solutions is that they require significant and long calculations. In fact, the tests are performed on characterization of the non-deterministic generator, due to the number of required samples (several millions). It cannot be envisaged to integrate such mechanisms in the manufactured product, for example, for periodic evaluations throughout the product lifetime.  
       SUMMARY OF THE INVENTION  
       [0012]     The present invention aims at overcoming all or part of the disadvantages of electronically-generated bit flow entropy test mechanisms.  
         [0013]     The present invention more specifically aims at checking in real time the quality of the generated bit flow as far as its entropy is concerned.  
         [0014]     The present invention also aims at providing a generator of bit words originating from a non-deterministic source, all the bits of which carry useful information.  
         [0015]     To achieve all or part of these objects as well as others, the present invention provides a method for determining the entropy of a noise source providing a bit flow, comprising the steps of:  
         [0016]     parallelizing the bit flow to obtain first words over a first number of bits;  
         [0017]     applying a compression function to the successive words; and  
         [0018]     evaluating a second number of bits over which said compression function provides its results, the second number representing the number of useful bits in the first words.  
         [0019]     According to an embodiment of the present invention, the compression function is a Huffman function.  
         [0020]     The present invention also provides a method of non-deterministic word generation from a noise source providing a bit flow, comprising the steps of:  
         [0021]     parallelizing the bit flow provided by the noise source to obtain first words over a first number of bits;  
         [0022]     applying in parallel to said first words a compression function providing second words over a second number of bits and a diffusion/confusion function providing third words over a third number of bits; and  
         [0023]     selecting a number of bits equal to the second number in the third words.  
         [0024]     According to an embodiment of the present invention, the diffusion/confusion function is a hash function, preferably selected from among functions SHA1 and MD5.  
         [0025]     According to an embodiment of the present invention, the diffusion/confusion function is a ciphering algorithm, preferably, of DES type.  
         [0026]     The present invention also provides a non-deterministic generator of numbers from a noise source providing a bit flow, comprising:  
         [0027]     a function for compressing first words over a first number of bits obtained from the noise source, providing second words over a second number of bits;  
         [0028]     a function of diffusion/confusion of said first words; and  
         [0029]     a selector of a number of bits equal to the second number in words resulting from the diffusion/confusion function.  
         [0030]     According to an embodiment of the present invention, the diffusion/confusion function is a hash function, preferably selected from among functions SHA1 and MD5.  
         [0031]     According to an embodiment of the present invention, the diffusion/confusion function is a ciphering function, preferably of DES type.  
         [0032]     According to an embodiment of the present invention, the compression function is a Huffman function.  
         [0033]     The foregoing and other objects, features, and advantages, of the present invention will be discussed in detail in the following non-limiting description of specific embodiments in connection with the accompanying drawings. 
     
    
     BRIEF DESCRIPTION OF THE DRAWINGS  
       [0034]      FIG. 1  very schematically shows in the form of blocks an embodiment of a method for determining the entropy of a bit flow according to the present invention; and  
         [0035]      FIG. 2  very schematically shows in the form of blocks an embodiment of a non-deterministic generator of binary words according to the present invention. 
     
    
     DETAILED DESCRIPTION  
       [0036]     The same elements have been designated with the same reference numerals in the different drawings. For clarity, only those steps and elements which are useful to the understanding of the present invention have been shown in the drawings and will be described hereafter. In particular, the forming of the noise source providing the initial bit flow tested or processed by the present invention has not been described in detail, the present invention being compatible with any conventional bit source providing a bit flow. Similarly, the exploitation that is made of the digital words generated by the present invention has not been described in detail, the present invention being here again compatible with any conventional exploitation of digital quantities generated in non-deterministic fashion.  
         [0037]     A feature of an embodiment of the present invention is to use a compression function to estimate the number of useful bits provided by a non-deterministic bit source. According to the present invention, the compression function is used to determine the ratio between the number of useful bits and the number of input bits and not to provide bits, conversely to the current use of such a compression function.  
         [0038]     A compression function is characterized by the fact that the more often a piece of data appears in a set of data, the less the function requires space (bits) to represent it. Conversely, the more seldom a piece of data of data appears in a set of data, the more space (bits) is used. It can thus be seen that as applied to a binary word set, the greater the number of repeated words, the lower the number of bits required to represent these words (make out the words from one another).  
         [0039]      FIG. 1  very schematically shows in the form of blocks an embodiment of the method for estimating the entropy of a bit flow BS provided by a noise source  1  (NS). A compression function  2  (COMP) provides words over n 2  bits based on n 1 -bit words built from bit flow BS. A function  6  (hardware or software) calculates ratio k between numbers n 2  and n 1 , after having evaluated number n 2  (and possibly number n 1 ).  
         [0040]     By applying compression function  2  to a set of several words over n 1  bits derived from noise source  1 , a set of words over n 2  bits is obtained, with n 2  smaller than or equal to n 1 . Ratio n 2 /n 1  determines ratio k of the compression function. In fact, number n 2  represents the number of bits to be taken in the n 1 -bit words to only obtain useful bits.  
         [0041]     Thus, the present invention uses number k to determine the entropy of the bit flow provided by noise source  1 , as being equal to the ratio of the compression function.  
         [0042]     The number of words to be taken into account depends on the size (n 1 ) of the input words. The greater the number of words in the set, the more reliable the result, and the greater number n 1 , the greater the number of words in the set must be. For example, the set of words comprises at least 2 2n1  words.  
         [0043]     As an example, a Huffman compression function such as described in “A Method for the Construction of Minimum-Redundancy Codes”, published in Proceedings of the I.R.E., 40, September 1952, may be used.  
         [0044]     According to another example, a compression function described in “Arithmetic Coding+Statistical Modeling=Data Compression”, Part 1—Arithmetic Coding of Mark Nelson, published in “Dr. Dobb&#39;s Journal”, February 1991, may be used.  
         [0045]     According to a first embodiment, the method of the present invention is used to characterize the entropy of a non-deterministic generator. The greater the number k, the better the quality in terms of non-deterministic character of the generator, and thus the more efficient the noise source is to generate words in non-deterministic fashion.  
         [0046]     According to another embodiment, the method illustrated in relation with  FIG. 1  is used to, from a noise source providing a bit flow, generate words forming ciphering or authentication quantities.  
         [0047]      FIG. 2  schematically shows in the form of blocks an embodiment of a non-deterministic number generator according to the present invention exploiting the qualification method illustrated in  FIG. 1  to select, in the generated bit flow, a number corresponding to the number of useful bits.  
         [0048]     As in the case of  FIG. 1 , the bit flow originating from noise source  1  is processed by a word over n 1  bits. In  FIG. 2 , a temporary storage element  4  (BUFF) is assumed, for example, registers used to parallelize flow BS over n 1  bits and to store a set of words (in  FIG. 1 , this function is assumed to be comprised in block  2 ).  
         [0049]     The n 1 -bit words are submitted in parallel to a compression function  2  of the type described in relation with  FIG. 1  providing words over n 2  bits and to a diffusion/confusion function, for example, a hash function  3 , which stirs the n 1  bits and provides words over n 3  bits with n 3  smaller than or equal to n 1 . A hash function is characterized by the fact that knowing the resulting data, it is difficult to go back to the input data, and by the fact that it is deprived of collision, that is, it is impossible to find two data providing the same result.  
         [0050]     As a variation, functions  2  and/or  3  manipulate series bit flow BS and are in charge of obtaining the words over n 2  and n 3  bits. According to another variation, noise source  1  provides n 1 -bit words.  
         [0051]     Any hash function may be used, for example, the functions known as SHA1 and MD5. As a variation, a DES-type cryptography algorithm (Data Encryption Standard) may also be used to mix the bits in function  3 .  
         [0052]     According to this embodiment of the present invention, number n 2  of bits at the output of compression function  2  is evaluated (block  7 , EVAL n 2 ) and is used to select (block  5 , SEL) n 2  bits from the n 3 -bit words provided by the hash function. As a result, the words over n 2  bits provided by selector  5  only contain useful bits (bearing information). These words are then exploited as digital quantities according to the application. It should be noted that the content of the words provided by function  2  is not exploited, only the number of bits of these words being used.  
         [0053]     As a variation, the exploitation of number n 2  (directly or after calculation of ratio k,  FIG. 1 ) may take different forms. Number n 2  may for example be compared with a range of acceptable values. The current number n 2  may also be compared with the preceding value (or with several values). Number n 2  may also be directly used to adapt in real time the number of provided bits, etc.  
         [0054]     An advantage of the present invention is that it enables testing the entropy of a non-deterministic generator while requiring fewer calculation resources than conventional solutions.  
         [0055]     Another advantage of the present invention is that the test can be integrated with the circuit generating in non-deterministic fashion the words exploited by the application.  
         [0056]     Another advantage of the present invention is that it enables optimizing the entropy per bit by exploiting the result of the compression function to select the useful bits in words provided by a hash function supplied with the bits of the noise source.  
         [0057]     Another advantage of the present invention is that it enables detecting a possible drift in the entropy of a non-deterministic generator throughout the product lifetime. This detection can be exploited either to warn the user, or to control in real time the number of bits of the generated words.  
         [0058]     Of course, the present invention is likely to have various alterations, modifications, and improvements which readily occur to those skilled in the art. In particular, the selection of the number of bits exploited by the generator of the present invention depends on the application and especially on the number of desired bits for the words generated in non-deterministic fashion.  
         [0059]     Such alterations, modifications, and improvements are intended to be part of this disclosure, and are intended to be within the spirit and the scope of the present invention. Further, the implementation of the present invention, be it by hardware or software means, is within the abilities of those skilled in the art based on the functional indications given hereabove.  
         [0060]     Accordingly, the foregoing description is by way of example only and is not intended to be limiting. The present invention is limited only as defined in the following claims and the equivalents thereto.