Cryptography – Key management – Having particular key generator
Reexamination Certificate
2001-04-19
2004-06-22
Sheikh, Ayaz (Department: 2131)
Cryptography
Key management
Having particular key generator
C380S047000, C380S265000
Reexamination Certificate
active
06754345
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Field of the Invention
The present invention relates to a pseudorandom number generation circuit using a linear feedback shift register (referred to as LFSR hereinafter) and a data communication system employing the circuit, and more particularly to a pseudorandom number generation circuit which gives an irregularity to the cycle of the random numbers and a data communication system employing the circuit.
2. Description of the Related Art
Heretofore, cryptographic algorithms using random numbers have been utilized in data communication systems in view of security. As random numbers used in cryptographic algorithms, pseudorandom numbers that can be generated easily by means of software are used more frequently than intrinsic random numbers owing to the ease in handling and the simplicity in processing.
As for pseudorandom number generation circuit for generating pseudorandom numbers, circuits using an LFSR are well known. An LFSR comprises a plurality of registers connected in series and an exclusive OR circuit. The output signals of two specified registers among the plurality of registers are supplied to the input node of the exclusive OR circuit, and the output signal of the exclusive OR circuit is fed back to the leading register. Moreover, a shift clock is supplied in common to all of these registers. With this constitution, it is possible to obtain pseudorandom number sequences with relatively long cycle.
For example, the cycle of pseudorandom number sequences generated by an LFSR consisting of n registers is equal to that of maximum length linearly recurring sequences (called M-sequences) of n-th degree, which is 2
n
−1. It should be noted that what is defined as a cycle here is not what is representing a time, but ration it is what is representing the number of ways (or length) in which the generated pseudorandom numbers can be regarded as being different kinds. In other words, an identical set of pseudorandom numbers will be generated repeatedly for every cycle.
In
FIG. 8
is shown a block diagram of a conventional pseudoradom number generation circuit
50
employing an LFSR having 7 stages of registers. The pseudorandom number generation circuit
50
has a configuration in which the output of a second stage register
50
-
2
and the output of a final stage register
50
-
7
, out of 7 registers
50
-
1
to
50
-
7
connected in series, are connected to the input node of an exclusive OR circuit
52
, and the output node of the exclusive OR circuit
52
is fed back to a leading register
50
-
1
. A shift clock SCK is supplied in common to all registers
50
-
1
to
50
-
7
, and the LFSR is driven in response to the SCK. The outputs B
1
to B
7
of respective registers are taken out as forming a pseudorandom number.
Since bit strings of an M-sequence are generated in the case of a pseudorandom number generation circuit employing an LFSR, an LFSR consisting of 7 stages of registers generates 127 (namely, 2
7
−1) ways of pseudorandom numbers.
However, when the random number sequences generated by the pseudorandom number generation circuit
50
are used as seeds, namely, as cipher keys, for a cipher circuit, there is a possibility that a cipher text is decoded relatively easily. For example, in a stream type cryptography, a stream cryptogram is generated by taking exclusive OR of binary sequences of a plain text and binary pseudorandom number sequences generated by a pseudorandom number generation circuit. However, when the pseudorandom number sequences or the pseudorandom number sequence generation logic are deciphered, it is easy to reproduce a plain text from a cipher text obtained. As a result, the circuit no longer functions as an enciphering circuit.
It is therefore an important function required of a pseudorandom number generation circuit to be able to efficiently generate unpredictable pseudorandom number sequences for which attempts to decode a cipher text enciphered by an enciphering circuit will hardly meet with success. The simplest method to generate pseudorandom number sequences which will not readily lend itself to an easy data analysis is to increase the degree n (number of registers) of the M-sequences. Since, however, it is merely for enlarging the cycle of the pseudorandom number sequences, it cannot be considered to be an essential solution to the problem. Accordingly, in order to generate pseudorandom number sequences which are difficult to be analyzed by using the present method, it is necessary to employ an extremely large number of registers which leads to an increase in the circuit scale.
A pseudorandom number generation circuit which generates pseudorandom number sequences using small number of registers is disclosed in Publication of Japanese Patent publication No. Hei 5-327427. However, the pseudorandom number sequences generated by this circuit have merely an apparently long cycle, and the measure against an easy decoding essentially remains intact unresolved.
SUMMARY OF THE INVENTION
It is therefore an object of the present invention to provide a pseudorandom number generation circuit which can generate pseudorandom number sequences which are essentially difficult to decode.
It is another object of this invention to provide a data communication system which employs pseudorandom number generation circuits generating pseudorandom number sequences which are essentially difficult to decode.
The pseudorandom number generation circuit according to this invention is equipped with a selection signal generation circuit which generates a selection signal, a clock generation circuit generates a plurality of clock signals having different frequencies each other, a selection circuit which selects one of the clock signals in response to the selection signal, a first shift register circuit including a plurality of first register circuits connected in series which carries out shift operation in response to the selected clock signal selected by said selection circuit, a first exclusive OR circuit receiving output signals of two of the plurality of first register circuits, means for supplying an output signal of the first exclusive OR circuit to a first stage of the first shift register circuit, and means for extract contents of at least a part of the first register circuits.
In addition, the data communication system according to this invention is equipped with a first and a second cipher keys generation circuits which generate a first and a second cipher keys, respectively, an enciphering circuit which enciphers original data to enciphered data based on the first cipher key, and a deciphering circuit which deciphers the enciphered data to deciphered data based on the second cipher key, the first cipher key generation circuit including a first pseudorandom number generation circuit generating a first pseudorandom number, a first clock generator generating a first clock signal based on the first pseudorandom number, a second pseudorandom number generation circuit generating a second pseudorandom number in response to the first clock signal, and means for supplying the second pseudorandom number to the enciphering circuit as the first cipher key, the second cipher key generation circuit including a third pseudorandom number generation circuit generating a third pseudorandom number, a second clock generator generating a second clock signal based on the third pseudorandom number, a fourth pseudorandom number generation circuit generating a fourth pseudorandom number in response to the second clock signal, and means for supplying the fourth pseudorandom number to the deciphering circuit as the second cipher key.
REFERENCES:
patent: 3790768 (1974-02-01), Chevalier et al.
patent: 4553251 (1985-11-01), Hartmann
patent: 5592424 (1997-01-01), Maeno
patent: 0 095 272 (1983-11-01), None
patent: 0095272 (1983-11-01), None
patent: 0 580 870 (1994-02-01), None
patent: 0619659 (1994-10-01), None
patent: 0 619 659 (1994-10-01), None
patent: 5-327427 (1993-12-01), None
M.J.B. Robshaw, Stream ciphers, Jul. 25, 1995, RSA Laboratories Te
Ishimoto Junichi
Tanaka Masanori
NEC Electronics Corporation
Sheikh Ayaz
Song Hosuk
Sughrue & Mion, PLLC
LandOfFree
Pseudorandom number generation circuit and data... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Pseudorandom number generation circuit and data..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Pseudorandom number generation circuit and data... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3333304