Methods for improving unpredictability of output of pseudo-random number generators

Abstract

A method for performing computations in a mathematical system which exhibits a positive Lyapunov exponent, or exhibits chaotic behavior, comprises varying a parameter of the system. When employed in cryptography, such as, e.g., in a pseudo-random number generator of a stream-cipher algorithm, in a block-cipher system or a HASH/MAC system, unpredictability may be improved. In a similar system, a computational method comprises multiplying two numbers and manipulating at least one of the most significant bits of the number resulting from the multiplication to produce an output. A number derived from a division of two numbers may be used for deriving an output. In a system for generating a sequence of numbers, an array of counters is updated at each computational step, whereby a carry value is added to each counter. Fixed-point arithmetic may be employed. A method of determining an identification value and for concurrently encrypting and/or decrypting a set of data is disclosed.

1 . A method for repeatedly performing computations in a mathematical system which exhibits a positive Lyapunov exponent, comprising varying at least one parameter of the mathematical system after a certain number of computations.  
     
     
         2 . A method according to  claim 1 , wherein at least one variable of the mathematical system is expressed as a fixed-point number.  
     
     
         3 . A method according to  claim 2 , further comprising the steps of: 
 expressing the mathematical system in discrete terms,    performing said computations in such a way that the computations include the at least one variable expressed as a fixed-point number,    obtaining, from said computations, a resulting number, the resulting number representing at least one of: 
 a. at least a part of a solution to the mathematical system, and  
 b. a number usable in further computations involved in the numerical solution of the mathematical system.  
   
     
     
         4 . A method according to  claim 1 , wherein the mathematical system comprises at least one non-linear map.  
     
     
         5 . A method according to  claim 1 , wherein said at least one parameter is repeatedly varied at predetermined intervals in said computations.  
     
     
         6 . A method according to  claim 1 , wherein said computations involve performing iterations in the mathematical system.  
     
     
         7 . A method according to  claim 1 , wherein said at least one parameter is represented by a counter which varies independently of the mathematical system.  
     
     
         8 . A method according to  claim 7 , wherein the counter is increased at each iteration in the mathematical system.  
     
     
         9 . A method according to  claim 7 , wherein a maximum value is defined for the counter, the method comprising resetting the counter to a minimum value once the counter has reached said maximum value, whereby the counter varies with a certain period.  
     
     
         10 . A method according to  claim 7 , wherein a set of counters is employed, the set comprising multiple counters.  
     
     
         11 . A method according to  claim 10 , wherein the variation of a first one of said counters is dependent from the variation of a second one of said counters in such a way that the period of the first counter is different from the period of the second counter.  
     
     
         12 . A method according to  claim 10 , wherein the variation of each individual one of said counters is dependent from the variation of at least another one of said counters so as to obtain a period of the counters which is longer than the period which would have existed if each individual counter would not have been dependent from the variation of another counter.  
     
     
         13 . A method according to  claim 1 , wherein the one or more counters is/are increased linearly.  
     
     
         14 . A method for generating pseudo-random numbers comprising performing mathematical operations by a method according to  claim 1 .  
     
     
         15 . A method for generating an identification value comprising performing mathematical operations by a method according to  claim 1 .  
     
     
         16 . A method for encrypting and/or decrypting data comprising performing mathematical operations by a method according to  claim 1 .  
     
     
         17 . A method according to  claim 15 , wherein encrypting and/or decrypting comprises generating pseudo-random numbers by a method according to  claim 14 .  
     
     
         18 . A method for manipulating a first set of data in a cryptographic system, the first set of data comprising a first and a second number of a first and a second bit size A and B, respectively, the method comprising: 
 multiplying the first and the second number to obtain a third number of a third bit size A+B, the third number consisting of P most significant and Q least significant bits, wherein A+B=P+Q, and wherein Q is equal to the largest of the first bit size A and the second bit size B, Q=max(A,B),    manipulating the third number to obtain a fourth number which is a function of at least one of the P most significant bits of the third number,    using the fourth number for deriving an output of the cryptographic system.    
     
     
         19 . A method according to  claim 18 , wherein the first number is equal to the second number.  
     
     
         20 . A method according to  claim 18 , wherein at least one of the first and second number represents at least one state variable of a mathematical system, and wherein the state variable is updated as a function of the fourth number.  
     
     
         21 . A method according to  claim 20 , wherein the state variable is updated as a function of a permutation of the fourth number.  
     
     
         22 . A method according to  claim 21 , wherein the permutation comprises a bitwise rotation of the bits of the fourth number.  
     
     
         23 . A method according to  claim 18 , wherein: 
 the step of multiplying is performed multiple times, each multiplication being performed on a number which represents or is a function of one of a plurality of state variables, the step of multiplying thereby resulting in a plurality of third numbers, and wherein    the step of manipulating results in an array comprising a plurality of fourth numbers, and wherein    at least one state variable is updated as a function of at least two of the fourth numbers.    
     
     
         24 . A method according to  claim 18 , wherein at least one of the first and second number is a state value X i  to which there is added a variable parameter value.  
     
     
         25 . A method according to  claim 24 , wherein the parameter value is a counter C i .  
     
     
         26 . A method according to  claim 25 , wherein the step of multiplying comprises squaring (X i +C i ), wherein X i  denotes a state variable or an array of state variables, and wherein C i  denotes the counter or an array of counters.  
     
     
         27 . A method according to  claim 24 , wherein said at least one parameter is repeatedly varied at predetermined intervals in said computations.  
     
     
         28 . A method acccording to  claim 18 , wherein a counter C i  is added to the fourth number or to a number which is a function of the fourth number to result in an updated state variable X i+1 .  
     
     
         29 . A method according to  claim 18 , wherein the step of multiplying comprises calculating x k , x denoting the first number, k denoting an exponent.  
     
     
         30 . A method according to  claim 29 , wherein k is an integer number.  
     
     
         31 . A method according to  claim 18 , wherein the step of manipulating comprises at least one logical operation which is performed on a bit of the most significant bits and a bit of the least significant bits of the third number.  
     
     
         32 . A method according to  claim 31 , wherein the logical operation comprises at least one XOR operation.  
     
     
         33 . A method according to  claim 32 , wherein P=Q, and wherein the at least one XOR operation comprises P XOR operations to result in a result of bit size P, each XOR operation being performed on one bit of the most significant bits of the third number and one bit of the least significant bits of the third number.  
     
     
         34 . A method according to  claim 18 , wherein the step of manipulating comprises at least one arithmetic operation which is performed on at least one bit of the most significant bits and at least one bit of the least significant bits.  
     
     
         35 . A method according to  claim 18 , wherein the step of multiplying comprises a plurality of multiplication functions resulting in a plurality of numbers of bit size A+B, and wherein the step of manipulating comprises combining at least one of the bits of a first one of the plurality of numbers with at least one of the bits of a second one of the plurality of numbers.  
     
     
         36 . A method according to  claim 35 , wherein the plurality of multiplication functions comprises at least one squaring operation, and wherein the step of manipulating comprises combining at least one of the P most significant bits of a first one of the plurality of numbers with at least one of the Q least significant bits of a second one of the plurality of numbers.  
     
     
         37 . A method according to  claim 18 , wherein the step of multiplying is performed in a mathematical system in which at least one state variable is being iterated.  
     
     
         38 . A method according to  claim 18 , wherein the step of multiplying is performed in an iterative system of at least two state variables.  
     
     
         39 . A method according to  claim 38 , wherein, in each computational sequence, values assigned to each of the at least two state variables is updated as a function of at least one value of the same and/or another state variable.  
     
     
         40 . A method according to  claim 18 , wherein the fourth number is used for generating or updating a pseudo-random number as the output of the cryptographic system.  
     
     
         41 . A method according to  claim 18 , wherein at least one of the first and second number is derived from a second set of data to be encrypted or decrypted, and wherein the fourth number is used to generate an encrypted or decrypted representation of the second set of data.  
     
     
         42 . A method according to  claim 18 , wherein at least one of the first and second number is derived from a second set of data, and wherein the fourth number is used for generating an identification value identifying the second set of data.  
     
     
         43 . A method according to  claim 18 , wherein at least one of the first and second number is derived from a cryptographic key.  
     
     
         44 . A method for manipulating a first set of data in a cryptographic system, the first set of data comprising a first and a second number, the method comprising: 
 dividing the first number by the second number to obtain a quotient and a remainder,    combining, by means of a mathematical operation, the quotient and the remainder to obtain a resulting number,    using the resulting number for deriving an output of the cryptographic system.    
     
     
         45 . A method for generating a periodic sequence of numbers in a cryptographic system in which computational steps are repeatedly performed, the method comprising updating, in each computational step i, an array of counters, the counters being updated by a logical and/or by an arithmetic function, whereby, at each computational step, a carry value is added to each counter in the array, wherein the carry added to the first counter in the array, c 0 , is obtained from at least one of: 
 a selected computation of a value of the array of counters,    a value which is a function of a counter value at a previous computational step.    
     
     
         46 . A method for generating a periodic sequence of numbers in a cryptographic system in which computational steps are repeatedly performed, the method comprising updating, in each computational step i, an array C i  of counters c j,i , the counters being updated as:  
         c   0,i+1   =c   0,i   +a   0   +d   i   modN   0 ,  c   j,i+1   =c   j,i   +a   j   +b   j−1,i+1   modN   j  for j>0,  
       where: 
 c j,i+1  is a value assigned to position j of array C at step i+1, j=0 . . . n−1, n denoting a dimension of the array C,  
 c j,i  is a value assigned to position j of array C at step i, j=0 . . . n−1,  
 a j  is a value assigned to position j of an array A, j=0 . . . n−1,  
 for j>0: b j−1,i+1  is a carry value resulting from the computation of c j−1,i+1,    
 N j  is a constant, j=0 . . . n−1,  
 for i=0: d i =d 0  is an initial value,  
 for i>0 d i  is a carry value obtained from a selected computation of a value of the array of counters C i  and/or a function of C i .  
 
     
     
         47 . A method according to  claim 46 , wherein each value a/j is a constant.  
     
     
         48 . A method according to  claim 46 , wherein n=1, so that: 
 the array C contains a single value c 0,i ,    the array A contains a single value a 0 .    
     
     
         49 . A method according to  claim 46 , wherein, for i>0, d i  is a carry value resulting from the computation of c j−1,i .  
     
     
         50 . A method according to  claim 46 , wherein d i  is a carry value resulting from the computation of c j−1,i+1 .  
     
     
         51 . A method according to  claim 46 , wherein the computational steps which are performed in the cryptographic system comprise an iterative procedure in which an array of state variables, X, is repeatedly iterated so that at least one value assigned to a position in the array of state variable X at computational step i+1 is a function of: 
 at least one value assigned to a position in the array of state variables X at computational step i, and    at least one value assigned to a position of the array of counters C at computational step i.    
     
     
         52 . A method according to  claim 51 , wherein the array of state variables X contains a single variable.  
     
     
         53 . A method according to  claim 51 , wherein the array of state variables X at computational step i+1 is a function of X i +C i , X i+1 =f(X i +C i ).  
     
     
         54 . A method according to  claim 46 , wherein the product of N 0 ·N 1 · . . . ·N n−1 −1 and a concatenated value of A are mutually prime.  
     
     
         55 . A method for generating an output of a cryptographic system in which computational steps are performed as an iterative procedure wherein an array of state variables, X, is repeatedly iterated so that at least one value assigned to a position in the array of state variables X at iteration step i+1 is a function of: 
 at least one value assigned to a position in the array of state variables X at iteration i, and    at least one value assigned to a position of an array of counters C at iteration i,    the array of counters being updated in each iteration as:      c   0,i+1   =c   0,i   +a   0   +d   i   modN   0 ,  c   j,i+1   =c   j,i   +a   j   +b   j−1,i+1   modN   j  for j>0,    where:    c j,i+1  is a value assigned to position j of array C at step i+1, j=0 . . . n−1, n denoting a dimension of the array C,    c j,i  is a value assigned to position j of array C at step i, j=0 . . . n−1,    a j  is a value assigned to position j of an array A, j=0 . . . n−1,    for j>0: b j−1,i+1  is a carry value resulting from the computation of c j−1,i+1,      N j  is a constant, j=0 . . . n−1,    for i=0: d i =d 0  is an initial value,    for i>0 d i  is a carry value obtained from a selected computation of a value of the array of counters C i  and/or a function of C i ,    each iteration comprising:    multiplying a first number of a first bit size A and a second number of a second bit size B to obtain a third number of a third bit size A+B, at least one of the first and second number being equal to or a function of at least one value assigned to a position of the array of state variables X at iteration i, the third number consisting of P most significant and Q least significant bits, wherein A+B=P+Q, and wherein Q is equal to the largest of the first bit size A and the second bit size B, Q=max(A,B),    manipulating the third number to obtain a fourth number which is a function of at least one of the P most significant bits of the third number,    using the fourth number for deriving the output of the cryptographic system and/or for assigning new values to positions of the array of state variables X.    
     
     
         56 . A method of determining an identification value for identifying a set of data and for concurrently encrypting and/or decrypting the set of data, the method comprising performing numerical computations in a mathematical system exhibiting a positive Lyapunov exponent.  
     
     
         57 . A method according to  claim 56 , further comprising the steps of: 
 expressing the mathematical system in discrete terms,    expressing at least one variable of the mathematical system as a fixed-point number,    performing said computations in such a way that the computations include the at least one variable expressed as a fixed-point number,    obtaining, from said computations, a resulting number, the resulting number representing at least one of: 
 a. at least a part of a solution to the mathematical system, and  
 b. a number usable in further computations involved in the numerical solution of the mathematical system.  
   
     
     
         58 . A method according to  claim 56 , the method further comprising repeatedly performing mathematical computations as iterations in the mathematical system, whereby various parts of the set of data or modifications thereof may be used as input to the computations.  
     
     
         59 . A method according to  claim 56 , the method further comprising: 
 repeatedly performing mathematical computations as iterations in the mathematical system, whereby various parts of the set of data or modifications thereof may be used as input to the computations, following each computation or a certain number of computations: 
 extracting a resulting number from the computations, the resulting number representing at least one of: 
 a. at least a part of a solution to the mathematical system, and  
 b. a number usable in further computations involved in the numerical solution of the mathematical system,  
 
 determining an updated value for the identification value based on the resulting number, whereby various parts of the set of data or modifications thereof may be used as input in the step of determining,  
 encrypting and/or decrypting a certain portion of the set of data based on the resulting number,  
 whereby as many iterations are performed as required for encrypting and/or decrypting the entire set of data.  
   
     
     
         60 . A method according to  claim 56 , further comprising: 
 expressing the mathematical system in discrete terms,    expressing at least one variable of the mathematical system as a fixed-point number,    performing said computations in such a way that the computations include the at least one variable expressed as a fixed-point number.    
     
     
         61 . A method according to  claim 56 , wherein the identification value is further modified following encryption and/or decryption of the entire set of data.