Method and device for generating a pseudorandom string

0001The present invention relates to the production of pseudo-random sequences of symbols belonging to a given alphabet. Such suites are used in particular in certain cryptographic procedures.

0002We call a pseudo-random sequence a sequence which, although produced in a deterministic manner, is impossible to distinguish, at least in a "reasonable" time, from a sequence of symbols in which each symbol would be chosen perfectly at random in the alphabet (the meaning of what is meant by "reasonable" time is obviously linked to the intended application and to the available computing power). In practice, a pseudo-random sequence is usually produced by initializing an appropriate algorithm using a secret parameter (called, depending on the context, "seed" or "key"), and if necessary an additional, secret parameter or not, called "initialization vector".

0003The alphabet mentioned above can, for example, be the binary set {0,1}, or the set of numbers from 0 to 9, or even the alphanumeric set comprising the upper and lower case numbers and letters. In the context of the present invention, it will only be assumed that the symbols of the alphabet belong to a finite body (or "Galois body" GF (<i>q</i>)) <i>K</i> cardinal <i>q</i> ≥ 2.

0004An important application of pseudo-random sequences is "flow encryption". This technique makes it possible to encrypt (in the sense of cryptography) a series of data in clear {<i>x_i</i>} (indexed by <i>i</i>), with values ​​in the alphabet, by means of another sequence {<i>z_i</i>} with values ​​in the same alphabet, where {<i>z_i</i>} is, precisely, the sequence produced by a pseudo-random generator, to obtain an encrypted sequence {<i>y</i>_i}, also with values ​​in the alphabet. In other words, we choose a law of internal composition<i>y_i = x_{i *} z_i</i> in the alphabet; for example, this internal law can be the "exclusive OR" when the alphabet is the binary alphabet {0,1}. Floating encryption is also called "on-the-fly" encryption due to the fact that data is encrypted there one by one - as opposed to encryption methods involving<i>blocks</i> of data. Stream encryption has the advantage over block encryption of reducing data transmission and storage delay problems, but it obviously requires pseudo-random symbol bit rate at least as high as data rate clear ; the application to flow encryption is therefore reserved for generators of relatively rapid pseudo-random sequences.

0005Floating encryption is used in particular in the Internet exchange protection protocol called "TLS" (initials of the English words <i>"Transport Layer Security</i>", see the article by <nplcit id="ncit0001" npl-type="s"><text>T. Dierks, and C. Allen entitled "The TLS Protoco /, version 1.0, RFC 2246", January 1999</text></nplcit>), one of the most widely used afloat encryption algorithms is the "RC4" algorithm (cf. <nplcit id="ncit0002" npl-type="b"><text>JD Golic entitled "Linear Statistical Weakness of Alleged RC4 Keystream Generator", Proceedings of "Advances in Cryptology - EUROCRYPT '97", pages 226 to 238, editor W. Fumy, Lecture Notes in Computer Science vol. 1233, Springer-Verlag</text></nplcit>), and in the encryption of traffic and signaling on the radio channel in the "GSM" system, using algorithms, the most common of which is the "A5 / 1" algorithm (cf. <nplcit id="ncit0003" npl-type="b"><text>A. Biryukov, A. Shamir and D. Wagner entitled "Real Time Cryptanalysis of A5 / 1 on a PC", Proceedings of "FSE 2000", pages 1 to 18, editor B. Schneier, Springer Verlag 2000</text></nplcit>).

0006There are other important applications of pseudo-random sequences, for example in stochastic calculations and in cryptographic authentication protocols with public key.

0007Many current flow algorithms, for example the A5 / 1 algorithm mentioned above, use linear recurrent sequences produced by linear feedback registers, possibly combined using non-linear func tions (see article of <nplcit id="ncit0004" npl-type="s"><text>A. Canteaut entitled "Encryption on the fly", special issue of the magazine "Pour la Science", pages 86 and 87, Paris, July-October 2002</text></nplcit>). These algorithms can be implemented in fast pseudo-random sequence generators, but their security is questionable, for lack of strong security arguments on which one can base great confidence in the practical impossibility of distinguishing pseudo sequences - random produced by perfectly random sequences.

0008The patent application <patcit id="pcit0001" dnum="FR0506041"><text>French n ° 05 06041</text></patcit> discloses a pseudo-random sequence generator of terms belonging to a finite field <i>K</i> cardinal <i>q</i> ≥ 2 intended for use in a cryptographic procedure. This generator has means for calculating iteratively, from a<i>not</i> - initialization tuple <i>X</i>⁽⁰⁾ = (<i>X</i>⁽⁰⁾₁,<i>X</i>⁽⁰⁾₂,..., <i>X</i>⁽⁰⁾<i>_not</i>) elements of <i>K,</i> of <i>not -</i> tuples <i>X</i>^(<i>i</i>) = (<i>X</i>^(<i>i</i>)₁<i>, X</i>^(<i>i</i>)₂<i>, ..., X</i>^(<i>i</i>)<i>_not</i>) elements of <i>K</i> (or <i>i</i> = 1,2, ...), each tuple <i>X</i>^(<i>i</i>) resulting predetermined from at least one <i>m</i> -tuplet <i>Y</i>^(<i>i</i>) = (<i>Y</i>^(<i>i</i>)₁,<i>Y</i>^(<i>i</i>)₂,...,<i>Y</i>^(<i>i</i>)<i>_m)</i> elements of <i>K</i> and the terms of said pseudo-random sequence being extracted in a predetermined manner from <i>not</i> - tuples <i>X</i>^(<i>i</i>) and / or <i>m</i> - tuples <i>Y</i>^(<i>i</i>). This generator is remarkable in that it further comprises means for obtaining, for at least one value of<i>i</i>, at least one Y component^(<i>i</i>)<i>_k</i> (or <i>k</i> = 1,2,..., <i>m</i>) of <i>m</i> -tuplet <i>Y</i>⁽ⁱ⁾ by applying a predetermined quadratic form, with coefficients in <i>K</i>, to the components of <i>not -</i>tuple <i>X</i>^(<i>i</i>-1).

0009This pseudo-random generator uses an algorithm offering a high level of security, which results from the difficulty of the problem consisting in solving a system of quadratic equations on a finite field. We can show indeed (subject to the verification of the so-called "P ≠ NP" conjecture, commonly accepted, of the "complexity theory"), that, whatever the finite field<i>K</i> considered, the resolution of this problem requires more than polynomial time, even if the verification that a given candidate is or is not a solution of this system of equations can be done in polynomial time (such a problem is called "NP-hard"). In addition, even for fairly modest sizes of<i>m</i> and of <i>not</i> (for example for <i>K</i> = GF (2) and <i>m</i> and <i>not</i> greater than or equal to 100), we do not currently know, if the values ​​of <i>m</i> and <i>not</i> are sufficiently close to each other, no effective method for solving random instances of this problem.

0010However, the question arises whether a pseudo-random generator according to French demand n ° <patcit id="pcit0002" dnum="FR0506041"><text>05 06041</text></patcit> can be sufficiently efficient, that is to say to require computing resources (time, memory, and so on) per symbol of the sequence produced sufficiently low (at least for moderate parameter values ​​but large enough for the problem that we just mentioned can always be considered difficult) so that we can consider the use of such a generator on an industrial level.

0011This question of the computing resources required relates in particular to the possibility of integrating a pseudo-random generator of this type in low-cost electronic systems, such as wired logic chips. It is recalled in this regard that electronic circuits with wired logic are composed of "logic gates" produced from transistors (it is possible to design all the logic functions of a program from logic gates of two types, one called "nand" and the other called "nor"). The number of logic gates required to set up a logic circuit therefore notably reflects the size of the circuit, its current consumption, and its cost.

0012So let's take a closer look at the calculations implemented in the pseudo-random generator according to demand <patcit id="pcit0003" dnum="FR0506041"><text>French n ° 05 06041</text></patcit>.

0013The generator iteratively calls one (or more) quadratic form (s) associating, with iteration n °<i>i</i>, at least one variable <i>Y</i>^(<i>i</i>)<i>_k</i> (or <i>k</i> =1,2,..., <i>m)</i> at <i>not</i> variables <i>X</i>^(<i>i-</i>1)<i>_j</i> (or <i>j</i> = 1,2,..., <i>not</i> ). This association therefore consists of a certain function "<i>G</i>", who has a <i>not</i> -tuplet <i>X</i> = (<i>x</i>₁<i>, x</i>₂,...,<i>x_not</i>) of input values, associate the <i>m</i>-tuplet <i>Y</i> = (<i>y</i>₁,<i>y</i>₂,...,<i>y_m</i>) of output values. This function<i>G</i> therefore corresponds to a system (<i>G</i>) of <i>m</i> multivariate quadratic polynomials (i.e. <i>not</i> variables <i>x_l</i> at x<i>_not</i>, with <i>not</i> > 1) on a finite body <i>K</i>. These polynomials are therefore of the form<maths id="math0001"><math display="block"><mstyle displaystyle="true"><munder><mo>∑</mo><mrow><mi mathvariant="normal">l</mi><mo>≤</mo><mi>i</mi><mo>≤</mo><mi>j</mi><mo>≤</mo><mi>not</mi></mrow></munder><mo>⁢</mo><msubsup><mi>α</mi><mi>k</mi><mfenced><mi mathvariant="italic">ij</mi></mfenced></msubsup><mo>⁢</mo><msub><mi>x</mi><mi>i</mi></msub></mstyle><msub><mi>x</mi><mi>j</mi></msub><mo>+</mo><mstyle displaystyle="true"><munder><mo>∑</mo><mrow><mi mathvariant="normal">l</mi><mo>≤</mo><mi>j</mi><mo>≤</mo><mi>not</mi></mrow></munder><mo>⁢</mo><msubsup><mi>β</mi><mi>k</mi><mfenced><mi>j</mi></mfenced></msubsup></mstyle><msub><mi>x</mi><mi>j</mi></msub><mo>+</mo><msub><mi>γ</mi><mi>k</mi></msub><mo>=</mo><msub><mi>γ</mi><mi>k</mi></msub><mspace width="8em" /><mfenced><mn>1</mn><mo>≤</mo><mi>k</mi><mo>≤</mo><mi>m</mi></mfenced><mo>,</mo></math><img file="EP2005290B1_D0001.tif" /></maths>where the coefficients <maths id="math0002"><math display="inline"><msubsup><mi>α</mi><mi>k</mi><mfenced><mi mathvariant="italic">ij</mi></mfenced></msubsup><mo>,</mo><msubsup><mi>β</mi><mi>k</mi><mfenced><mi>j</mi></mfenced></msubsup></math><img file="EP2005290B1_D0002.tif" /></maths> and γ<i>_k</i> belong to <i>K</i>, and where the quantities <i>y_k</i> also belong to <i>K.</i>

0014Conventionally, to implement such a generator, the value of these coefficients would be stored in a memory, and the value of the <i>m</i> polynomials at each iteration. It would therefore be necessary to memorize a total number of coefficients equal to<i>m · N.</i> or <i>NOT</i> denotes the number of terms by polynomial. We can easily verify that, for a quadratic polynomial with<i>not</i> variables, this number <i>NOT</i> of terms equals <maths id="math0003"><math display="block"><mi>NOT</mi><mo>=</mo><mn>1</mn><mo>+</mo><mfrac><mrow><mi>not</mi><mo>⁢</mo><mfenced><mi>not</mi><mo>+</mo><mn>1</mn></mfenced></mrow><mn>2</mn></mfrac><mn>.</mn></math><img file="EP2005290B1_D0003.tif" /></maths>

0015Furthermore, so that the resolution of a system of <i>m</i> quadratic equations to <i>not</i> unknown on <i>K</i> may be considered difficult, it is desirable that the values ​​of <i>m</i> and <i>not</i> are sufficiently large, and that their orders of magnitude are sufficiently close to each other. So for large values ​​of<i>not</i>, and for <i>m</i> of the order of <i>not</i>, we see that the number of coefficients to memorize is of the order of <i>not</i>³<i>.</i> For example, for <i>not</i> At 100, approximately one million coefficients must be memorized.

0016It follows that the conventional production of a pseudo-random generator according to French application no. <patcit id="pcit0004" dnum="FR0506041"><text>05 06041</text></patcit> requires too many electronic gates to be considered for insertion into a wired logic chip. It goes without saying that we could even less consider inserting into a wired logic chip a pseudo-random generator using a system of multivariate polynomials, some of which are of global degree greater than 2, while the rise in the degree of polynomials would advantageously increase the safety of the generator in return for a modest increase in computing resources.

0017The document <nplcit id="ncit0005" npl-type="s"><text>"A Tutorial On Uniform Variate Generation", P.L'Ecuyer, Proceedings of the 1989 Winter Simulation Conference, December 4, 1989 (1989-12-04), pages 40-49</text></nplcit> presents several types of pseudo-random generators. The document<nplcit id="ncit0006" npl-type="b"><text>"Public Quadratic Polynomialtuples for Efficient Signature-Verification and Message-Encryption", by Tsutomu Matsumoto et Al., Advances in Cryptology- Eurocrypt International Conference on the Theory and Application of Cryptographyc Techniques, Springer Verlag, DE, May 25, 1988, pages 419- 453</text></nplcit> describes an asymmetric crypto-system which uses quadratic equations. However, the generation of the coefficients of polynomials requires significant resources. The document<nplcit id="ncit0007" npl-type="b"><text>"Generating Uniform Random Numbers", by Knuth DE, Seminumerical Algorithms, Art of Computer Programming, Reading, Addison Wesley, US, Vol.2, 1980, pages 9-37</text></nplcit>, deals with number generators with linear congruences and extends the linear case to the quadratic case. Again, significant resources are required to generate the coefficients of the quadratic equations. Thus, the pseudo-random generators described in these documents are not suitable for being inserted into wired logic chips.

0018The present invention therefore relates to a pseudo-random sequence generator of terms belonging to a finite body. <i>K</i> cardinal <i>q</i> ≥ 2 intended to be used in a cryptographic procedure, said generator having means for iteratively calculating a system (┌) of <i>m</i> polynomials at <i>not</i> variables belonging to a finite field <i>K</i>. This pseudo-random sequence generator is remarkable in that the coefficients of the<i>m</i> polynomials are regenerated at each iteration.

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

0020In fact, the authors of the present invention have realized that, contrary to what one might naively think, the additional computational load implied by the invention hardly affects the total computation time. As the computation time for polynomials of fairly large degree (even if they are numerous and a function of many variables) is, as is well known, fairly short, we obtain thanks to the invention a pseudo-random generator with the times fast (for example usable for flow encryption) and well suited for low-cost computing devices, these advantages adding to the high security mentioned above.

0021In the case where one aims above all for a great speed, one will advantageously take only polynomials of degree at most equal to two.

0022According to particular characteristics, the pseudo-random sequence generator comprises a module for generating the coefficients produced in the form of a linear shift register.

0023According to particular characteristics, the pseudo-random sequence generator comprises a module for generating the coefficients produced in the form of a linear shift register.

0024As a variant, this module for generating the coefficients may be produced in the form of a non-linear shift register, or in the form of a finite state machine.

0025Thanks to these arrangements, a large number of coefficients can be generated using a small electronic memory.

0026According to particular characteristics, to calculate the <i>m</i> -tuple of values ​​(<i>y</i>_1,<i>y</i>_2,...,<i>y</i>_m) taken, for a <i>not</i> -tuple of variables (<i>x</i>_1,<i>x</i>_2,...,<i>x_not</i>) given by <i>m</i> polynomials of a system (Γ) in which these polynomials are all of global degree less than or equal to <i>D</i>, the generator comprises means for:<ul id="ul0001" list-style="dash"><li>choose a processing order for a chosen set of terms of the general polynomial to <i>not</i> degree variables <i>D</i>,</li><li>for the terms treated, calculate, respecting the said order, the monomial due to the variables, then, successively for the <i>m</i> polynomials, generate the coefficient of this term and multiply this coefficient by said monomial to obtain the value of said term.</li></ul>

0027Thanks to these provisions, each factor due to the variables is calculated only once instead of <i>m</i> time.

0028Correlatively, the invention relates to a method for generating a pseudo-random sequence of terms belonging to a finite field. <i>K</i> cardinal <i>q</i> ≥ 2 intended to be used in a cryptographic procedure, said method comprising the iterative calculation of a system (Γ) of <i>m</i> polynomials at <i>not</i>. variables belonging to a finite field<i>K</i>. This process for generating a pseudo-random sequence is remarkable in that the coefficients of the<i>m</i> polynomials are regenerated at each iteration.

0029According to particular characteristics, each of these <i>m</i> polynomials is of degree at most equal to two.

0030According to particular characteristics, to calculate the <i>m</i> -tuple of values ​​(<i>y</i>₁,<i>y</i>₂,...,<i>y_m</i>) taken, for a <i>not</i> -tuple of variables (<i>x</i>₁,<i>x</i>₂,...,<i>x_not</i>) given by <i>m</i> polynomials of a system (Γ) in which these polynomials are all of global degree less than or equal to <i>D</i>, it includes the following steps:<ul id="ul0002" list-style="dash"><li>we choose a processing order for a chosen set of terms of the general polynomial to <i>not</i> degree variables <i>D</i>,</li><li>for the treated terms, one calculates, by respecting this order, the monomial due to the variables, then, successively for the <i>m</i> polynomials, we generate the coefficient of this term and we multiply this coefficient by said monomial to obtain the value of said term.</li></ul>

0031The advantages offered by these methods are essentially the same as those offered by the correlative pseudo-random sequence generators succinctly described above.

0032The invention also relates to:<ul id="ul0003" list-style="dash"><li>an electronic circuit, and in particular a wired logic chip, comprising any one of the pseudo-random sequence generators succinctly described above,</li><li>a non-removable data storage means comprising computer program code instructions for the execution of the steps of any of the methods for generating a pseudo-random sequence succinctly described above,</li><li>a partially or completely removable data storage means, comprising computer program code instructions for the execution of the steps of any one of the methods for generating a pseudo-random sequence succinctly described above, and</li><li>a computer program containing instructions such that, when said program controls a programmable data processing device, said instructions cause said data processing device to use any of the methods for succinctly generating a pseudo-random sequence set out above.</li></ul>

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

0034Other aspects and advantages of the invention will appear on reading the detailed description below of particular embodiments, given by way of nonlimiting examples. The description refers to the accompanying drawings, in which:<ul id="ul0004" list-style="dash"><li>the <figref idref="f0001">figure 1</figref> is a block diagram illustrating an embodiment of the method for generating a pseudo-random sequence according to the invention, and</li><li>the <figref idref="f0002">figure 2</figref> is a block diagram illustrating an embodiment of the pseudo-random generator according to the invention.</li></ul>

0035As explained above, the security of the pseudo-random sequence generator according to the present invention (i.e. the impossibility for an "attacker" to calculate the (<i>i</i> + 1)^th term of the output sequence from <i>i</i> first terms) is based on the difficulty of the problem of solving <i>m</i> equations to <i>not</i> unknown on a finite body <i>K</i>.

0036According to one embodiment, these equations can all be chosen quadratic as in French application n ° <patcit id="pcit0005" dnum="FR0506041"><text>05 06041</text></patcit> (for the sake of simplicity of language, we use the expression of equations, respectively of polynomials, "quadratic", even in the case where some of these equations, respectively some of these polynomials, are linear - it being understood that at minus one equation, respectively at least one polynomial, of the system is effectively of degree two). This problem can be formulated precisely as follows:<ul id="ul0005" list-style="none"><li>given a system (Γ) of <i>m</i> quadratic equations to <i>not</i> unknown <i>x</i>₁ at <i>x_not</i> belonging to a finite body <i>K</i>, of shape <maths id="math0004"><math display="block"><mstyle displaystyle="true"><munder><mo>∑</mo><mrow><mi mathvariant="normal">l</mi><mo>≤</mo><mi>i</mi><mo>≤</mo><mi>j</mi><mo>≤</mo><mi>not</mi></mrow></munder><mo>⁢</mo><msubsup><mi>α</mi><mi>k</mi><mfenced><mi mathvariant="italic">ij</mi></mfenced></msubsup><mo>⁢</mo><msub><mi>x</mi><mi>i</mi></msub></mstyle><msub><mi>x</mi><mi>j</mi></msub><mo>+</mo><mstyle displaystyle="true"><munder><mo>∑</mo><mrow><mi mathvariant="normal">l</mi><mo>≤</mo><mi>j</mi><mo>≤</mo><mi>not</mi></mrow></munder><mo>⁢</mo><msubsup><mi>β</mi><mi>k</mi><mfenced><mi>j</mi></mfenced></msubsup></mstyle><msub><mi>x</mi><mi>j</mi></msub><mo>+</mo><msub><mi>γ</mi><mi>k</mi></msub><mo>=</mo><msub><mi>γ</mi><mi>k</mi></msub><mspace width="8em" /><mfenced><mn>1</mn><mo>≤</mo><mi>k</mi><mo>≤</mo><mi>m</mi></mfenced><mo>,</mo></math><img file="EP2005290B1_D0004.tif" /></maths>where the coefficients <maths id="math0005"><math display="inline"><msubsup><mi>α</mi><mi>k</mi><mfenced><mi mathvariant="italic">ij</mi></mfenced></msubsup><mo>,</mo><msubsup><mi>β</mi><mi>k</mi><mfenced><mi>j</mi></mfenced></msubsup></math><img file="EP2005290B1_D0005.tif" /></maths> and γ<i>_k</i> belong to <i>K</i> , and where the quantities <i>y_k</i> also belong to <i>K</i>,</li><li>find a solution <i>X =</i> (<i>x</i>₁,<i>x</i>₂,..,<i>x_not</i>).</li></ul>

0037We denote by "Γ" the function, described by the system of equations (Γ), which at a <i>not</i> -tuplet <i>X</i> = (x₁, x₂,...,<i>x_not</i>) of input values ​​associates the <i>m</i> -tuplet <i>Y</i> = (<i>y</i>_<i>1</i>,<i>y</i>₂<i>, ..., y_m</i>) of output values.

0038The pseudo-random generator iteratively calls one (or more) quadratic form (s) associating at least one variable <i>Y</i>^(<i>i</i>)<i>_k</i> (or <i>k</i> =1,2,...,<i>m)</i> at <i>not</i> variables <i>X</i>^(<i>i-</i>1)<i>_j</i> (or <i>j</i> =1,2,...,<i>not</i>). As explained above, the parameters<i>q, m</i> and <i>not</i> are preferably chosen so that:<ul id="ul0006" list-style="dash"><li>solving a system of <i>m</i> quadratic equations to <i>not</i> unknown on <i>K</i> can be considered difficult, which requires that the values ​​of <i>m</i> and <i>not</i> are sufficiently large, and that their orders of magnitude are sufficiently close to each other (we can for example take <i>q^not</i> and <i>q^m</i> both between 2⁸⁰ and 2⁴⁰⁰ ), and</li><li>calculations can be performed efficiently, which requires that the values ​​of <i>q, m</i> and <i>not</i> are small enough (we can for example take <i>q</i> less than a hundred, with <i>m</i> and <i>not</i> less than a few hundred).</li></ul>

0039In addition, in accordance with the invention, the coefficients of these quadratic forms are regenerated at each iteration (for example by recalculating them).

0040It is clear that the greater the number of zero coefficients, the faster these calculations will be; however, care should be taken to ensure that a sufficient number of coefficients of quadratic terms (designated by<maths id="math0006"><math display="inline"><msubsup><mi>α</mi><mi>k</mi><mfenced><mi mathvariant="italic">ij</mi></mfenced></msubsup></math><img file="EP2005290B1_D0006.tif" /></maths> above) are non-zero so that solving the system of equations is impossible in practice; in case, to gain speed of execution, it is allowed that certain equations (but not all obviously) are linear compared to all the variables, it is recommended to keep secret the mode of generation of the coefficients, in order to compensate for the fact that solving the system of equations is (in theory) made easier.

0041The correlative embodiment of the method for generating a pseudo-random sequence according to the invention is illustrated in the <figref idref="f0001"><b>figure 1</b></figref><b>.</b> In this embodiment, for each value of <i>i</i>, all components of the <i>m</i> -tuplet <i>Y</i>^(<i>i</i>) by applying quadratic forms with coefficients in <i>K</i> to the components of the <i>not</i> -tuplet <i>X</i>^(<i>i</i>-1)<i>.</i>

0042First, during an initialization step, a <i>not</i> -tuplet <i>X</i>⁽⁰⁾<i>.</i> Depending on the intended use of the generator, <i>X</i>⁽⁰⁾ may depend either on a public seed, or on a secret key, or on an initialization vector, or on a combination of several of these elements; an initialization vector is an additional parameter, generally non-secret, which allows the same secret key to be used several times to generate several distinct pseudo-random sequences.

0043Then iterative steps are implemented to produce, from the initial state <i>X</i>⁽⁰⁾ and according to the method described below, a pseudo-random sequence <i>Z</i>^(<i>i</i>) (or <i>i</i> =1,2_,...) made up of <i>t</i>- tuples of elements of <i>K,</i> where t is a constant between 1 and <i>m.</i> The total number of iterations could for example be between 1 and 2⁵⁰.

0044At iteration no.<i>i</i>, a current state <i>X</i>^(<i>i</i>-1) made up of a <i>not</i> - tuples of <i>K</i> is taken as input value to implement the following substeps:<ol id="ol0001"><li>1) a <i>m</i> -tuplet <i>Y</i>^(<i>i</i>) values ​​of <i>K</i> is deducted from <i>X</i>^(<i>i</i>) using the function Γ defined above, ie <i>Y</i>^(<i>i</i>) = Γ (<i>X</i>^<i>i</i>-1)),</li><li>2) an output value <i>Z</i>^(<i>i</i>) is obtained by applying to the couple (<i>X</i>^(<i>i</i>-1),<i>Y</i>^(<i>i</i>)) a selected output function S, ie <i>Z</i>^(<i>i</i>)<i>= S</i>(<i>X</i>^(<i>i-</i>1)<i>, Y</i>^(<i>i</i>))<i>,</i> and</li><li>3) a new current state <i>X</i>^(<i>i</i>), consisting of <i>not</i> -tuple of values ​​of <i>K</i>, is obtained by applying to the couple (<i>X</i>^(<i>i</i>-1)<i>, Y</i>^(<i>i</i>)) a feedback function <i>F</i> chosen, ie <i>X</i>(<i>i</i>) = <i>F (X</i>^(<i>i</i>-1)<i>, Y</i>^(<i>i</i>)<i>).</i></li></ol>

0045This process is illustrated on the <figref idref="f0001">figure 1</figref> sequentially (two successive iterations), but it could as well be illustrated in a looped-back manner. The important point to note here is that the successive stages of this process can be implemented by a single e same electronic circuit.

0046We will also refer to French application n ° <patcit id="pcit0006" dnum="FR0506041"><text>05 06041</text></patcit> for examples of possible choices for the feedback function <i>F</i> and for the output function <i>S</i> mentioned above. We will also refer to this request for examples of means to constitute, starting from at least the following<i>Z</i>^(<i>i</i>), various pseudo-random sequences of symbols (for example binary) at output.

0047The <figref idref="f0002"><b>figure 2</b></figref> schematically illustrates an embodiment of the pseudo-random sequence generator according to the invention. This generator includes the following modules:<ul id="ul0007" list-style="dash"><li>a memory (100) intended to contain the values ​​of the input variables of the system of polynomials to be calculated,</li><li>a memory (500) intended to contain, at the end of the calculation, the value taken by one or more of the polynomials to be calculated, and intended to serve simultaneously as a storage unit for the intermediate values,</li><li>a module (200) for generating (in a predetermined order) the values ​​of the various monomials which are involved in the polynomial system to be calculated, the module (200) for generating monomials being optionally provided with its own memory,</li><li>a module (300) for generating the sequence of coefficients describing the system of polynomials to be calculated, the module (300) being provided with its own memory, and</li><li>a combination module (400) intended for multiplying the coefficients and the values ​​of the monomials, so as to update the memory (500) containing the values ​​of the polynomials.</li></ul>

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

0049Note that for the proper functioning of the pseudo-random generator according to the invention, it is not at all necessary to apply the same function Γ to each iteration; in other words, nothing prohibits that the value of each coefficient of<i>m</i> polynomials can vary from one iteration to another, if that proves convenient. The present embodiment makes astute use of this observation.

0050According to a first variant, the module (300) for generating the coefficients is produced in the form of a linear shift register LFSR (initials of the English words, <i>"Linear Feedback Shift Register</i>").

0051An LFSR consists of a set of <i>l</i> memories α₁, α₂, ..., α₁<i>,</i> refreshed at each clock stroke by replacing the value contained in each memory α<i>_i</i> by the value contained in the memory α_<i>i</i>+1, except for the value contained in the memory α<i>_l</i> which is replaced by a given linear combination of the values ​​contained in various memories at the previous clock stroke.

0052The bits at the output of the linear shift registers are conventionally used as sequences of pseudo-random bits. According to the present invention, the data output from the LFSR is advantageously used not for directly generating the output values<i>Z</i>^(<i>i</i>), but to generate the coefficients of <i>m</i> polynomials. Indeed, an LFSR produces a pseudo-random sequence of length (2<i>^r</i> -1) from only <i>r</i> bits in memory and with an electronic circuit comprising a number of logic gates only of the order of <i>r.</i>

0053For example, in the case of a system of equations (Γ) comprising <i>m</i> = 80 multivariate polynomials in <i>not</i> = 80 variables on the binary body GF (2), the <i>m · N</i> ≈ 259200 coefficients of this system can be generated from a linear shift register <i>r</i> = 18 bits instead of the 259200 bits of a naive realization.

0054According to a second variant, the module (300) for generating the coefficients is produced in the form of a nonlinear shift register NLFSR (initials of the English words, <i>"Non-Linear Feedback Shift Register</i>"). This implies, compared to a linear offset, a very slight additional cost in terms of number of electronic gates, but allows to significantly improve the randomness of the sequence of terms produced by the output generator.

0055According to a third variant, the module (300) for generating the coefficients is produced in the form of a finite state machine comprising:<ul id="ul0008" list-style="dash"><li>a memory updated at each clock,</li><li>a circuit for updating this memory, and</li><li>a circuit for expanding the data recorded in this memory.</li></ul>

0056The term "expansion circuit" designates a circuit capable of generating a number <i>f</i> bits from <i>g</i> bits in memory, with <i>f> g</i>. For example, if<i>f</i> is a multiple of <i>h</i>, we can divide the set of <i>f</i> bits in subsets of <i>h</i> bits each and then pass each of these subsets of <i>h</i> bits through a series of different mixers, and finally concatenate the series of bits thus obtained.

0057In a finite state machine, all the memory values ​​are refreshed at each clock stroke (before expansion), while in a shift register, only one value in memory is refreshed at each clock stroke. A finite state machine therefore allows faster calculations than a shift register, but at the cost of a certain increase in the number of electronic gates.

0058All these various variants nevertheless make it possible to generate at each iteration the coefficients of the system of equations (Γ) quickly, and by means of a small number of electronic gates.

0059One can also envisage various embodiments for the module (200) for generating monomial values. To simplify the discussion, we will only consider here the calculation of quadratic terms (of the type<i>x_ix_j</i>, or <i>i</i> and <i>j</i> vary from 1 to <i>not</i>)<i>.</i>

0060The "naive" implementation consists in considering all the pairs of variables one after the other; the calculation then requires<i>not</i>² clock strokes.

0061But as a variant, we can calculate the monomials as follows: we place in memory two copies of the current sequence of values ​​of the variables (<i>x</i>₁<i>_,x</i>₂<i>, ..., x_not</i>). By calculating the terms "opposite", we first obtain the<i>not</i> squares <maths id="math0007"><math display="inline"><msubsup><mi>x</mi><mi>i</mi><mn>2</mn></msubsup><mn>.</mn></math><img file="EP2005290B1_D0007.tif" /></maths> Then, we apply a circular permutation of a position to one of the sequences of values ​​of the variables (<i>x</i>₁<i>_,x</i>₂<i>, ..., x_not</i>); by calculating again the terms "opposite", we obtain the<i>not</i> products <i>x</i>₁<i>x</i>₂, <i>x</i>₂<i>x</i>₃, ..., x<i>_notx</i>₁. We continue this process of calculating monomials<i>not</i> by <i>not</i> until we get the <i>not</i>² products. In the end, it only took (multiplication being commutative) that n / 2 clock ticks, but this device requires twice as much memory as in the "naive" implementation.

0062Finally, we can also gain speed, and save memory capacity, by combining the generation of coefficients in the module (300) with the generation of monomials in the module (200), so as to calculate each term of the same type " in parallel "for all polynomials, before moving on to the next term. Thus, in the case, for example, of a system of quadratic polynomials, we will calculate the corresponding monomial (respectively of the type<i>x_ix_j, x_j</i> or 1) due to the variables, then, successively for the <i>m</i> polynomials, we will generate the coefficient of this term (respectively of the type <maths id="math0008"><math display="inline"><msubsup><mi>α</mi><mi>k</mi><mfenced><mi mathvariant="italic">ij</mi></mfenced></msubsup><mo>,</mo><msubsup><mi>β</mi><mi>k</mi><mfenced><mi>j</mi></mfenced></msubsup></math><img file="EP2005290B1_D0008.tif" /></maths> or γ<i>_k</i>) and multiply this coefficient by said monomial to obtain the value of said term.