Method and device for generating a pseudorandom string

Translation of description of equivalent WO 2007116171 A2

p0001Method and apparatus for generating a pseudorandom sequence

p0002The present invention relates to the production of pseudorandom sequences of symbols belonging to a given alphabet. Such suites are especially used in some cryptographic procedures.

p0003Called pseudo-random sequence a sequence which, although produced deterministically, is impossible to distinguish, at least one time "reasonable", a series of symbols in which each symbol is chosen entirely at random in the alphabet (the meaning of what is meant by a time "reasonable" is obviously related to the intended application and the computing power available). In practice, it usually produces a pseudorandom sequence by setting an appropriate algorithm using a secret parameter (referred to as the context, "seed" or "key"), and if necessary an additional parameter, secret or not, called "initialization vector".

p0004The alphabet mentioned above can, for example, be the binary set {θ, l}, or all of the digits 0 to 9, or the alphanumeric set comprising numbers and uppercase and lowercase letters. In the context of the present invention, the symbols of the alphabet is assumed that only belong to a finite field (or "Galois field" GF (q)) K of cardinal q ≥ 2.

p0005An important application of pseudorandom sequence is the "stream encryption." This technique is used to encrypt (in the sense of cryptography) a series of clear data {x} ,. (indexed by z), with values ​​in the alphabet, using another sequence {zj values ​​in the same alphabet, {where zj is precisely the result produced by a pseudo-random generator, to obtain an encrypted sequence {y.}, also with values ​​in the alphabet. In other words, we opted for an internal composition law there_ι = χ_ι * z_ι in the alphabet; for example, that internal law may be the "exclusive OR when the alphabet is the binary alphabet {θ, l}. The stream cipher encryption is also called" on the fly "due to the fact that the data is encrypted there one by one. - versus encryption methods involving data blocks the stream cipher has, relative to block cipher, the advantage of reducing the problems of delay in transmission and storage of data, but it requires obviously a rate of pseudo-random symbols at least as high as the data rate in the clear;. the application to stream encryption is therefore reserved for generators relatively fast pseudorandom sequence stream encryption is implemented notably in the Internet exchange protection protocol called "TLS" (initials of the words "Transport Layer Sβcurity", see the article by T. Dierks, C. Allen and titled "the TLS Protocol Version 1.0, RFC 2246" January 1999), one of whose encryption algorithms commonly used afloat is the algorithm "RC4" (see the article by JD Golic entitled "Linear Statistical Weakness of Alleged RC4 Keystream Generatoi" Acts "Advances in Cryptology - EUROCRYPT" 97 ", 226 pages 238, W. Fumy editor, Lecture Notes in Computer Science vol. 1233, Springer-Verlag), and encryption of traffic and signaling on the radio path in the system "GSM", using algorithms whose most common is the "A5 / 1" algorithm (see the article by A. Biryukov, Shamir A. and D. Wagner titled "Real Time Cryptanalysis of A5 / 1 was PC", Proceedings of "ESF 2000" pages 1 to 18, B. Schneier publisher, Springer Verlag 2000).

p0006There are other important applications of pseudorandom sequences, for example stochastic calculations and cryptographic protocols with public key authentication.

p0007Many current flow algorithms, such as A5 / 1 algorithm mentioned above, use linear recursive sequences generated by linear feedback registers, optionally combined with non-linear functions (see the article A. Canteaut entitled "encryption on the fly", special issue of the magazine folder "to Science", pages 86 and 87,

p0008Paris, July-October 2002). These algorithms can be implemented in fast pseudorandom sequence generators, but their safety is questionable for lack of strong security arguments on which to base a lot of confidence in the practical impossibility of distinguishing the pseudo suites -aléatoires produced perfectly random sequences.

p0009French patent application No. 05 06041 discloses a pseudo-random sequence generator of terms belonging to a finite field K of cardinal q ≥ 2 for use in a cryptographic process.

p0010This generator has means for iteratively calculating, from an n X initialization tuple^m = (X^mι X^m₂, ..., X^m,,) Of elements of K, n - tuples X^{I) = (Λ, Λ, ..., Λ.) Of elements of K (where z = l, 2, ...), each n - tuple X⁰⁾ resulting in a predetermined manner at least one m-tuple

p0011Y^w = (7^ωi, 7^(O2, ..., y^(O_m) Of elements of K and the terms of said pseudorandom sequence being extracted predetermined manner of n tuples X⁰⁾ and / or m tuples Y^ω . This generator is characterized in that it further comprises means for obtaining, for at least one value of i, at least one component Y^ωk (where k = l, 2, ..., m) of the m-tuple y⁽⁰ applying a predetermined quadratic form, with coefficients in K, the components of the "tuple X^{{I ~ ι)} .

p0012This pseudo-random generator uses an algorithm providing a high level of safety resulting from the difficulty of the problem of solving a system of quadratic equations over a finite field. It can be shown in effect (subject to the verification of the actual conjecture "P ≠ NP" commonly accepted, the "complexity theory"), that, whatever the finite K considered, solving this problem requires a time more than polynomial, although the verification that a given candidate is or is not solving this system of equations can itself be carried out in a polynomial time (such problem is known as "NP-hard"). Moreover, even for relatively modest sizes rn and n (for example for K = GF (T) and m and greater than or equal n 100), it is currently known, in the case where the values ​​of m and n are sufficiently close to one another, no effective solution method of random instances of this problem.

p0013However, Ia question arises whether a pseudorandom generator according to French Application No. 05 06041 can be sufficiently effective, that is to say require computing resources (time, memory, and so on) by symbol the result produced low enough (at least for moderate parameter values ​​but large enough that the problem that we just mentioned can still be considered difficult) so that we can consider the use of such generator industrially.

p0014This issue of the required computing resources concerns including the possibility of integrating a pseudorandom generator of this type in electronic systems at low cost, such as chips wired logic. It recalls in this respect that the electronic circuits wired logic are composed of "logic gates" made from transistors (it is possible to design all logical functions of a program from logic gates of two types, one called "nAND" and the other called

p0015"Nor"). The number of logic gates required to implement a logic circuit thus reflects in particular the size of the circuit, its current consumption, and cost.

p0016Let us examine more closely the calculations used in the pseudorandom generator according to French Application No. 05 06041.

p0017The generator calls iteratively one (or more) form (s) quadratic (s) associating, at the iteration n ° z, at least one variable Y⁽'\ (Where k = l, 2, ..., m) with n variables X °^{~ Ι)}j (where j = 1,2, ..., "). This association is therefore a certain function "G", which, to a "tuple X = (x_ι, x₂, ..., X_not) Of input values, combines Wi-tuple Y = (yι, y₂, -, Y_m) Output values. This function G corresponds to a system (G) of m polynomials multivariate quadratic (that is to say in n variables x, x_not With n> 1) over a finite field K. So these polynomials are of the form

p0018Σ X af₁X₁ Σ + #> X_j + r_k = y_k 0- ≤ k ≤ m),

p0019where the coefficients a%^J) , Β [^J) and γ_k belong to K, and where the quantities y_k Also belong to K.

p0020Conventionally, to implement such a generator, would be stored in a memory the value of these coefficients, and calculate the value of m polynomials with each iteration. Should therefore storing a total number of coefficients equal to m - N, where N denotes the number of by polynomial terms. It is easily verified that, for a quadratic polynomial with n variables, the number N of words is equal to

p0021<img id="imgf000006_0001" he="10" wi="19" file="imgf000006_0001.tif" img-format="tif" img-content="drawing" orientation="portrait" inline="no" />

p0022Furthermore, for solving a system of m quadratic equations in n unknowns over K can be considered difficult, it is desirable that the values ​​of m and n are sufficiently large, and their magnitudes are sufficiently close the one of the other.

p0023Thus, for large values ​​of n, and m the order of n, it is seen that the number of coefficients to be stored is of the order of n³ . For example, to "≈ 100, you must memorize a million coefficients.

p0024As a result, the conventional implementation of a pseudorandom generator according to French Application No. 05 06041 requires a number of electronic gates far too high to be considered to insert it into a logic chip wired. It goes without saying that could be even less consider inserting a chip wired logic a pseudo-random generator using a system of multivariate polynomials some of which are global degree greater than 2, while the increase in the degree of polynomials advantageously would increase the safety of the generator in return for a modest increase in computing resources.

p0025The present invention therefore relates to a pseudo-random sequence generator of terms belonging to a cardinal finite body K q ≥ 2 for use in a cryptographic procedure, said generator having means for iteratively calculating a system (T) of m polynomials with n variables belonging to a finite body K. This pseudorandom sequence generator is characterized in that the coefficients of the m polynomials are regenerated at each iteration.

p0026Thus according to the invention, the coefficients of the polynomial are generated (for example recalculated) on each iteration from a small number of parameters, so that the memory size required to operate the generator of the invention is very modest.

p0027Indeed, the authors of the present invention have realized that, contrary to what one might think naively, the additional computational load implied by the invention little strike total calculation time. As the computing time for fairly significant degree polynomial (even if they are many and function of many variables) is, as is well known, quite short, is obtained thanks to the invention a pseudo-random generator to both fast (eg used for stream encryption) and well suited for computing devices at low cost, these benefits in addition to the high safety mentioned above.

p0028In case the aim is especially great speed, it is advantageously take as polynomials of degree at most equal to two. According to particular features, the pseudo-random sequence generator comprises a module for generating the coefficients produced in the form of a linear shift register.

p0029Alternatively, one may perform this coefficient generation module in the form of a non-linear shift register, or in the form of a finite state machine.

p0030With these provisions, it can generate a large number of coefficients using an electronic memory small.

p0031According to particular features, to calculate the m-tuple of values ​​iy_vthere₂, -, Y_m) Taken to a "tuple of variables (X₁₅X₂, ..., ,, *) Given by the m polynomials of a system (T) in which these polynomials are all of global degree less than or equal to Z⁾ , The generator comprises means for:

p0032- Choose a processing order for a selected set of terms of the general polynomial in n variables of degree D,

p0033- For processed terms, calculating, in accordance with said order, the monomial due to variables, then successively for the m polynomials, generating the coefficient of that term and multiplying that coefficient by said monôme to get the value of that term. Thanks to these provisions, each factor due to the variable is calculated once rather than m times.

p0034Correlatively, the invention relates to a method for generating a pseudo-random sequence of terms belonging to a finite field K of cardinal q ≥2 for use in a cryptographic procedure, said method comprising iteratively calculating a system (F) of m polynomials with n variables belonging to a finite body K. This method for generating a pseudo-random sequence is characterized in that the coefficients of the m polynomials are regenerated at each iteration.

p0035According to particular characteristics, each of these m polynomials of degree at most equal to two.

p0036According to particular features, to calculate the m-tuple values ​​(γ_ι, y₂, ..., Y_m) Taken to a "tuple of variables (x ,, x₂, ..., Xj given, by the m polynomials of a system (T) in which these polynomials are all of global degree less than or equal to D, it comprises the following steps:

p0037- Choosing a processing order for a selected set of terms of the general polynomial in n variables of degree D,

p0038- For processed terms, calculating, respecting the said order, the monomial due to variables, then successively for the m polynomials, it generates the coefficient of that term and multiplying that coefficient by said monôme to get the value of that term. The advantages offered by these methods are essentially the same as those offered by generators correlative pseudorandom string briefly described above.

p0039The invention also provides: - an electronic circuit including a logic chip cable, comprising any of the pseudorandom sequence generators briefly described above,

p0040- A non-removable data storage means containing computer program code instructions for executing the steps of any of methods for generating a pseudorandom string briefly described above,

p0041- A partially or totally removable data storage means containing computer program code instructions for executing the steps of any of methods for generating a pseudorandom string briefly described above, and

p0042- A computer program containing instructions such that, when said program controls a programmable data processing device, said instructions cause said data processing device implements any of the methods for generating a pseudo-random sequence briefly described above.

p0043The advantages offered by this electronic circuit, these data storage means and the computer program are essentially the same as those offered by said methods.

p0044Other aspects and advantages of the invention appear on reading the detailed description below of particular embodiments, given as nonlimiting examples. The description refers to the accompanying drawings, wherein:

p0045- Figure 1 is a block diagram illustrating one embodiment of the method for generating a pseudo-random sequence according to the invention, and - Figure 2 is a block diagram illustrating one embodiment of the pseudo-random generator according to the invention .

p0046As explained above, the security of the pseudo-random sequence generator according to the present invention (that is to say the impossibility for a "forward" to calculate the (z + l) '^th term of the sequence output from the first words i) based on the difficulty of the problem of solving m equations in n unknowns over a finite field K.

p0047According to one embodiment, these equations can all be chosen quadratic as in French application No. 05 06041 (by language of simplicity, we use the expression of equations, polynomials, respectively, "quadratic", even in the where any of these equations, respectively some of these polynomials, are linear - provided that at least one equation, to respectively least one polynomial, the system is actually two degrees). This problem can be formulated precisely as follows: given a system (T) m quadratic equations in n unknowns X₁ x_not belonging to a finite body K, shape

p0048Σ &lt;*_** + ΣΛ^{J) χ}j ⁺ r * = y_k a ≤ * ≤ w).

p0049where the coefficients a ^^j) , Β [^J) and γ_k belong to K, and where the quantities y_k Also belong to K, a solution X = (x_ux₂, ..., X_not).

p0050Is denoted by T "function, described by the system of equations (r), which in a" tuple X = (X₁₅X₂, ..., * ,,) Input values ​​associated with the m-tuple

p0051Y = (y_ι, y₂, ..., Y_m) Output values.

p0052The pseudorandom generator calls iteratively one (or) form (s) squared (s) involving at least a variable Y^(L)k (where

p0053A: = 1,2, ..., m) with n variables X^{{~ Ι ι)}j (where 7 = 1,2, ..., "). As explained above, the parameters q, m and n are preferably selected so that:

p0054- Solving a system of m quadratic equations in n unknowns over K can be considered difficult, which requires that the values ​​of m and R are sufficiently large, and their magnitudes are sufficiently close to one of the other (eg, you can take q "and q" both between 2⁸⁰ and 2⁴⁰⁰ ), And

p0055- The calculations can be performed efficiently, which requires that the values ​​of q, m and n are sufficiently small (eg, you can take q less than a hundred, with m and n less than a few hundred).

p0056In addition, according to the invention, is regenerated at each iteration (e.g. by recalculating) the coefficients of these quadratic forms.

p0057Clearly, the greater the number of zero coefficients, and faster will these calculations; However, it will ensure that a sufficient number of coefficients of quadratic terms (referred to as a%^J) above) are non-zero for solving the system of equations is impractical; in case, for speed of execution, we allow some equations (not all of course) are linear in all variables, it is recommended to keep secret the mode of generation of coefficients to compensate for the fact the resolution of the system of equations is (theoretically) facilitated.

p0058The embodiment of the correlative method of generating a pseudorandom sequence of the invention is illustrated in Figure 1. In this embodiment, is calculated for each value of i, all components of "? tuple F^{0 by applying quadratic forms with coefficients in K the components of the n-tuple X^{{~ Ι ι)} .

p0059Firstly, during an initialisation stage, it is an n-tuple X^m . According to the intended use of the generator, X⁽⁰⁾ may depend seed of a public or a secret key, either an initialization vector or a combination of several of these elements; an initialization vector is an additional parameter, usually not secret, which allows to use several times the same secret key to generate several distinct pseudo-random sequences.

p0060then implements iterative steps to produce, from the initial condition X^φ) and as described below, following a pseudo Z^w (Where i = 1,2, ...) consisting of i-tuples of elements of K, where t is a constant between 1 and m. The total number of iterations may for example be between 1 and 2⁵⁰.

p0061At iteration No. z, a current state X⁽'^{~ Ι)} consisting of a "tuple of elements of K is taken as an input value to implement the following sub-steps:

p00621) a tuple 7 m^W K values ​​are derived from X^M) using the function T defined above, ie 7^W = T (X '^{~ L)})

p00632) an output value Z^w is obtained by applying the pair (x⁽'-^l), Y^ω) S output function selected, ie Z^w S = (X °^AT), Y^ω), And

p00643) a new current state X^(Ι) Consisting of a "tuple of values ​​of K, is obtained by applying torque \ X^{'^-1) , 7⁽⁰) A feedback function F selected, ie Z^w = F (X^(M), 7^W).

p0065This process is illustrated in Figure 1 sequentially (two successive iterations), but it might as well be illustrated looped manner. The important point to note here is that the successive steps of this method may be implemented by a single electronic circuit.

p0066Reference is also in the French application No. 05 06041 for examples of possible choices for the feedback function F and to output the function S mentioned above. Reference is also made to this request for examples of ways to form, from at least the following Z^w Various pseudo-random sequences of symbols (for example binary) output.

p00672 schematically illustrates an embodiment of the pseudo-random sequence generator according to the invention. This generator includes the following modules: - A memory (100) for containing the values ​​of the input variables of the system to calculate polynomials,

p0068- A memory (500) for holding at the end of the calculation, the value taken by one or more polynomials to calculate, and to serve concurrently unit of storage of intermediate values,

p0069- A module (200) of generation (in a predetermined order) values ​​of different monomials involved in the polynomial system to calculate the module (200) generating monomials being optionally provided with its own memory, - a module (300) for generating the sequence of coefficients describing the polynomials to calculate system, the module (300) being provided with its own memory, and

p0070- A module (400) combination for the multiplication of coefficients and monomials values ​​so as to update the memory (500) containing the values ​​of polynomials.

p0071We will describe now a particularly advantageous embodiment for the module (300) for generating the coefficients mentioned above.

p0072Note that it is not necessary for the proper functioning of the pseudo-random generator according to the invention, to apply the same in each iteration r function; ie, nothing prevents the value of each of m polynomial coefficient can vary from one iteration to another, if this is convenient. The present embodiment is a clever use of this observation. According to a first alternative embodiment, the module (300) generating the coefficients in the form of a linear shift register LFSR (original English words, "Linear Feedback Shift Register").

p0073An LFSR consists of a set of / α memories_ι, α_ï..., Α_ι refreshed at each clock stroke substituting the value in each α memory_t by the value contained in the α memory_{i + ι} Except as regards the value in the α memory, which is replaced by a given linear combination of values ​​in various submissions to blow the previous clock.

p0074The output bits of the linear shift registers are conventionally used as a pseudo-random bit sequences. According to the present invention, the LFSR output data are advantageously used not to generate the Z output values ​​directly⁽⁰ But to generate the coefficients of the polynomial m. Indeed, an LFSR generates a pseudo-random sequence of length (2 '^' - I) from only r bits in memory and an electronic circuit having a number of logic gates only the r order. For example, in the case of a system of equations (T) including m = 80 multivariate polynomials in n = 80 variables on the binary field GF (2), the m - N ≈ 259200 coefficients of this system may be generated in from a size linear shift register r = 18 bits instead of 259200 bit of a naive implementation.

p0075In a second alternative embodiment, the module (300) generating the coefficients in the form of a non-linear shift register NLFSR (original English words, "Non-Linear Feedback Shift Register"). This implies, based on a linear offset, a very small overhead in terms of number of electronic gates, but can significantly improve the randomness of the sequence of terms produced by the output generator.

p0076According to a third variant, the module is carried out (300) of coefficients generating in the form of a finite state machine comprising:

p0077- A memory updated at each clock pulse,

p0078- An updating circuit of said memory, and

p0079- A data expansion circuit stored in this memory.

p0080The term "expansion circuit" means a circuit adapted to generate a number / bits from g bits in memory, f> g. For example, if / is a multiple of h, we can divide the set of / bits into subsets of h bits each, and then pass each of these subsets of h bits through a series of different mixers, and finally concatenating the bit sequences thus obtained. In a finite state machine, it refreshes with every blow of all memory clock values ​​(before expansion), while in a shift register, it is refreshing to every clock one Memory value. A finite state machine allows faster calculations than a shift register, but at the cost of some increase in the number of electronic gates.

p0081All these different variants however possible to generate at each iteration the coefficients of the equation system (F) quickly, and by a small number of electronic gates.

p0082One may also consider various embodiments for the module (200) for generating monomials values. To simplify the discussion, we will consider here that the calculation of quadratic terms (type X₁X_j , Where i and j vary from 1 to n).

p0083Implementation "naive" is to consider all pairs of variables one after the other; Ie calculation then requires n² clock strokes. But alternatively, one can calculate the monomials as follows: in memory is placed two copies of the current sequence of values ​​of variables (x_ι, x₂, ..., X_not). Calculating the terms "next", is first obtained the square n x). Then, applying a circular permutation of a position in one of the suites of values ​​of the variables (X₁₅X₂, ..., * ,,); by recalculating the terms "next", the n X products obtained₁X₂ , X₂X₃ ..., Χ ,, χ,. monomials continue this process of calculating n by n until we get the n² products. In the end, it only took (the multiplication is commutative) n / 2 clock cycles, but this device requires twice as much memory as in the implementation "naive".

p0084Finally, we can also work faster and save storage capacity by combining the generation of coefficients in the module (300) with the generation of monomials in the module (200) to calculate each term of the same type " in parallel "for all polynomials, before moving to the next term. Thus, if, for example, a system of quadratic polynomials, we will calculate the corresponding monomial (type x respectively x_there. , x_there or 1) due to variables, then successively for the m polynomials, we generate the coefficient of this term (the type ajp respectively β [^J) or γ_k ) And multiply this ratio by said monôme to get the value of that term.