Method and a device for generating a pseudorandom string
The invention relates to a method of generating a pseudorandom string of terms belonging to a finite body K of cardinal q≧2 intended to be used in a cryptography procedure, said method comprising the iterative calculation of a system (Γ) of m polynomials with n variables belonging to the finite body K. According to the invention, the coefficients of these m polynomials are regenerated at each iteration. The invention also relates to pseudorandom string generator intended to implement this method.
1. A pseudorandom string generator comprising:
an electronic circuit that generates a pseudorandom string of terms belonging to a finite body K intended to be used in a cryptography procedure, said generator including circuitry for iteratively calculating a system of m polynomials with n variables belonging to a finite body K, wherein the coefficients of said m polynomials are deterministically regenerated on each iteration without using a stored coefficient from a previous iteration based on an original seed that is shorter than the coefficients of said m polynomials.
2. A pseudorandom string generator according to claim 1 , wherein each of said polynomials forming the system is at most of second degree.
3. A pseudorandom string generator according to claim 1 , further including a coefficient generator module in the form of a linear shift register.
4. A pseudorandom string generator according to claim 1 , further including a coefficient generator module in the form of a non-linear shift register.
5. A pseudorandom string generator according to claim 1 , further including a coefficient generator module in the form of a finite state machine.
6. A pseudorandom string generator comprising:
an electronic circuit that generates a pseudorandom string of terms belonging to a finite body K intended to be used in a cryptography procedure, said generator including circuitry for iteratively calculating a system of m polynomials with n variables belonging to a finite body K, based on an original seed that is shorter than the coefficients of said m polynomials for each iteration;
wherein,
to calculate an m-tuple of values taken, for a given n-tuple of variables, by the m polynomials of a system in which the polynomials are all of global degree less than or equal to D,
the generator includes circuitry for:
choosing a processing order for a given set of terms of a general polynomial with n variables of degree D;
for the processed terms, calculating, in the same order, a mononomial for the variables and then, successively for the m polynomials, generating the coefficient of that term and multiplying that coefficient by said mononomial to obtain the value of said term.
7. A pseudorandom string generator according to claim 1 , wherein the electronic circuit comprises a hard-wired logic chip.
8. A method of generating a pseudorandom string of terms belonging to a finite body K of cardinal q≧2 intended to be used in a cryptography procedure, said method comprising:
iteratively calculating, using an electronic circuit, a system of m polynomials with n variables belonging to the finite body K; and
deterministically regenerating, from an initial state ,using the electronic circuit, the coefficients of said m polynomials on each iteration without using a stored coefficient from a previous iteration based on an original seed that is shorter than the coefficients of said m polynomials.
9. A method according to claim 8 wherein each of said polynomials forming the system is at most of second degree.
10. A method of generating a pseudorandom string of terms belonging to a finite body K intended to be used in a cryptography procedure, said method comprising:
iteratively calculating, using an electronic circuit, a system of m polynomials with n variables belonging to the finite body K; and
regenerating, using the electronic circuit, the coefficients of said m polynomials on each iteration based on an original seed that is shorter than the coefficients of said m polynomials;
wherein, to calculate an m-tuple of values taken, for a given n-tuple of variables, by the m polynomials of a system in which the polynomials are all of global degree less than or equal to D, the method includes the following steps:
choosing a processing order for a given set of terms of a general polynomial with n variables of degree D;
for the processed terms, calculating, in the same order, a mononomial for the variables and then, successively for the m polynomials, generating the coefficient of that term and multiplying that coefficient by said mononomial to obtain the value of said term.
11. Non-transitory, non-removable data storage media including computer program code instructions for executing the steps of a method according to claim 8 .
12. Non-transitory, partly or totally removable data storage media including computer program code instructions for executing the steps of a method according to claim 8 .
13. A non-transitory data storage device having stored thereon a computer program containing instructions such that, when said program controls a programmable data processing device, said instructions cause said data processing device to execute a method according to claim 8 .
14. An electronic circuit adapted to generate iteratively a sequence of elements from a finite field K, said elements being coefficients of terms in an expression of polynomials in a number of variables defined over K, thereby allowing an iterative computation of said polynomials from the number of variables, wherein each iteration deterministically regenerates the coefficients without using a stored coefficient from a previous iteration based on an original seed that is shorter than the coefficients of said polynomials.