Back to results
US 2006/0039558 A1Published application
Pseudo-random number generation method and pseudo-random number generator
OwnerMasakatu Morii, Yoshiaki Shiraishiinventors
Life of this patent
Estimating the term…
Abstract
A bit string obtained by sampling, every the number s, bits of a bit string whose output sequence is M sequence, when the bit number per one cycle of the M sequence is prime to the derived value, constitutes M sequence of a linear feedback shift register having other construction. Further, the linear feedback shift register can be determined from bits corresponding to at least two cycles by Berlekamp-Massay algorithm, whereby the linear feedback shift register 11 can be easily and dynamically reconstructed based on the initial state value.
Claims20
A method for generating pseudo-random numbers comprising:
- a first step for setting up an initial state value of a linear feedback shift register including n plurality of shift resistors and capable of outputting a bit string having bit number of (2ˆn)-1 per one cycle;
- a second step for finding a derived value prime to the bit number per one cycle of the linear feedback shift register based on the initial state value by means of a predetermined operation processing;
- a third step for multiplying the derived value by a value obtained by multiplying the bit number per one cycle by two or more to calculate a bit number to be outputted from the linear feedback shift register;
- a fourth step for outputting a bit string corresponding to the calculated bit number based on the initial state value from the linear feedback shift register;
- a fifth step for taking out a bit from the output bit string to generate a new bit string;
- a sixth step for reconstructing the linear feedback shift register such that the new bit string can be outputted from the resistor;
- and
- a seventh step for generating pseudo-random numbers based on the initial state value from the reconstructed linear feedback shift register.
5 more elements
A pseudo-random number generator comprising:
- a linear feedback shift register having n shift resistors and capable of outputting a bit string having bit number of (2ˆn)-1 per one cycle;
- means for setting up an initial state value of the linear feedback shift register based on a secret key;
- means for determining a derived value prime to the bit number per one cycle of the linear feedback shift register based on the initial state value by means of a predetermined operation processing;
- means for multiplying the derived value by a value obtained by multiplying the bit number corresponding to one cycle by two or more to calculate a bit numbers to be outputted from the first linear feedback shift register;
- means for outputting a bit string corresponding to the bit number calculated by the above means based on the initial state value from the linear feedback shift register;
- means for taking out a bit from the output bit string every the number of the derived value to generate a new bit string;
- means for reconstructing the linear feedback shift register such that the new bit string can be outputted from the resistor;
- and
- means for generating pseudo-random numbers based on the initial state value from the reconstructed linear feedback shift register.
6 more elements
A pseudo-random number generator comprising:
- a part for outputting a selectively used random number bit string having a predetermined bit number based on a secret key;
- a part for outputting an amplified random number bit string having bits of a larger bit number than the selectively used random number bit string based on the selectively used random number bit string outputted from the part for outputting a selectively used random number bit string;
- and
- a part for nonlinearly converting the amplified random number bit string outputted from the part for outputting an amplified random number bit string to output pseudo-random numbers;
- said part for outputting a selectively used random number bit string comprising:
- a linear feedback shift register having n shift resistors and capable of outputting a bit string having bit number of (2ˆn)-1 per one cycle,
- means for setting up an initial state value of the linear feedback shift register based on a secret key,
- means for determining a derived value prime to the bit number per one cycle of the linear feedback shift register based on the initial state value by means of a predetermined operation processing,
- means for multiplying the derived value by a value obtained by multiplying the bit number corresponding to one cycle by two or more to calculate a bit numbers to be outputted from the linear feedback shift register,
- means for outputting a bit string corresponding to the bit number calculated by the above means based on the initial state value from the linear feedback shift register.
- means for taking out a bit from the output bit string outputted from the above means every the number of the derived value to generate a new bit string,
- means for reconstructing the linear feedback shift register such that the new bit string can be outputted from the resistor, and
- means for outputting selectively used pseudo-random numbers based on the initial state value using the reconstructed linear feedback shift register reconstructed by the above means;
- said part for outputting an amplified random number bit string comprising:
- a random number table in which a plurality of amplified random bit strings having larger bit number than that of the selectively used random number bit string is stored, and
- means capable of selecting a corresponding amplified random number bit string from the plurality of amplified random number bit strings within the random number table by referring to the random number table using the selectively used random number bit string outputted from the means for outputting selectively used random number bit string;
- and
- said part for nonlinearly converting the amplified random number bit string comprising means for nonlinearly converting the amplified random number bit string selected by the means for selecting the amplified random number bit string by a nonlinear function to output pseudo-random numbers.
15 more elements
A program to be executed by a computer for generating pseudo-random numbers comprising:
- a part for outputting a selectively used random number bit string having a predetermined bit number based on a secret key;
- a part for outputting an amplified random number bit string having bits of a larger bit number than the selectively used random number bit string based on the selectively used random number bit string outputted from the part for outputting a selectively used random number bit string;
- and
- a part for nonlinearly converting the amplified random number bit string outputted from the part for outputting an amplified random number bit string to output pseudo-random numbers;
- said part for outputting a selectively used random number bit string comprising:
- a linear feedback shift register having n shift resistors and capable of outputting a bit string having bit number of (2ˆn)-1 per one cycle.
- means for setting up an initial state value of the linear feedback shift register based on a secret key,
- means for determining a derived value prime to the bit number per one cycle of the linear feedback shift register based on the initial state value by means of a predetermined operation processing,
- means for multiplying the derived value by a value obtained by multiplying the bit number corresponding to one cycle by two or more to calculate a bit numbers to be outputted from the linear feedback shift register,
- means for outputting a bit string corresponding to the bit number calculated by the above means based on the initial state value from the linear feedback shift register,
- means for taking out a bit from the output bit string outputted from the above means every the number of the derived value to generate a new bit string,
- means reconstructing of the linear feedback shift register such that the new bit string can be outputted from the resistor, and
- means for outputting selectively used pseudo-random numbers based on the initial state value using the reconstructed linear feedback shift register reconstructed by the above means,
- said part for outputting an amplified random number bit string comprising:
- a random number table in which a plurality of amplified random bit strings having larger bit number than that of the selectively used random number bit string is stored, and
- means capable of selecting a corresponding amplified random number bit string from the plurality of amplified random number bit strings within the random number table by referring to the random number table using the selectively used random number bit string outputted from the means for outputting selectively used random number bit string;
- and
- said part for nonlinearly conversing the amplified random number bit string comprising means for nonlinearly conversing the amplified random number bit string selected by the means for selecting the amplified random number bit string by a nonlinear function to output pseudo-random numbers.
15 more elements
Dependencies are inferred from the claim text.