Cryptography – Key management – Having particular key generator
Reexamination Certificate
1998-10-29
2001-08-21
Peeso, Thomas R. (Department: 2132)
Cryptography
Key management
Having particular key generator
C380S044000, C380S278000, C380S264000, C380S223000
Reexamination Certificate
active
06278780
ABSTRACT:
BACKGROUND OF THE INVENTION
The present invention relates to a method of and an apparatus for generating internal crypto-keys which are used as initial values to be set in feedback registers of an pseudo-random-sequence generator for generating pseudo-random-numbers to be XORed (added according to eXclusive OR logic) onto a data sequence recorded in a recording medium or to be transmitted in a communication system, for preventing a third party from tapping the data sequence without permission.
Cryptography called secret-key-cryptography can be classified into two types, cryptography called block ciphers and cryptography called stream ciphers. In the former cryptography, data of a fixed length, 64 bits, for example, called the plain text is transformed into a data block called the cipher text according to a certain transformation algorithm. On the other hand, a sequence of pseudo-random-numbers called the key-stream is XORed onto a data stream called the plain text stream to be converted into a cipher-stream.
As a method of generating a pseudo-random-sequence which is cryptographically secure, there is known a method making use of a one-way function such as a public-key-cryptograph function. Here, the one-way function means a function f(x) which can be easily calculated from a variable x, but it is hardly possible to estimate the variable x from an output of the function f(x).
FIG. 5
is a block diagram illustrating a configuration example of a conventional pseudo-random-sequence generator which generates the cryptographically secure pseudo-random-sequence.
Referring to
FIG. 5
, an external key-data of n-bits is supplied to a first input terminal
405
. A one-way function circuit
101
outputs an n-bit conversion result by processing n-bit output of a selector
201
with a certain one-way function (such as a public key function) according to a certain conversion parameter (such as a public key) supplied to a second input terminal
104
. The LSB (Least Significant Bit) of the conversion result is output from an output terminal
508
as a bit of the pseudo-random-sequence.
With each clock pulse CLK supplied from a clock terminal
210
, a register
202
outputs registered n-bit data to the selector
201
and newly registers the n-bit conversion result of the one-way function circuit
101
.
Only when the clock pulse CLK is supplied for the first to the register
202
, a selection signal SEL supplied to the selector
210
through a selection terminal
211
is set at logic ‘0’ for controling the selector
201
to output the external key-data supplied from the first input terminal
405
to the one-way function circuit
101
, and afterwards the selection signal SEL is turned to logic ‘1’ so that the selector is controlled to select the output of the register
202
to be fed-back to the one-way function circuit
101
.
Thus, the pseudo-random-sequence is output bit-by-bit from the output terminal
508
in synchronization with the clock pulse CLK.
The pseudo-random-sequence generator of
FIG. 5
is known to be cryptographically secure. However, calculation of the one-way function takes comparatively long time.
Therefore, a pseudo-random-sequence generator consisting of combination of several linear feedback-sift-registers or nonlinear feedback-shift-registers is generally used for generating the key-stream of the stream cipher, when a high speed is required, having such configuration as illustrated in a block diagram of FIG.
6
.
In the pseudo-random-sequence generator of
FIG. 6
, there are comprised linear feedback-sift-registers or nonlinear feedback-shift-registers (hereinafter generically called the feedback-shift-registers) S
1
to S
n
. To each of the feedback-shift-registers, working as a sub-generator, an internal key K
1
to K
n
is set initially. At each clock, each of the feedback-shift-resisters is shifted by one bit outputting its LSB to a combination function F, and its MSB (Most Significant Bit) is generated according to a certain feedback function from its registered bit sequence. The combination function F generates a key-stream bit by bit according to a certain combination function from outputs of the feedback-shift-registers S
1
to S
n.
However, the key-stream generated making use of feedback-shift-registers, such as illustrated in
FIG. 6
, may sometimes be broken by a deciphering method called correlation attacks. So, various kinds of devices has been studied, whereof some examples are described in “Applied Cryptography, Second Edition: Protocols, Algorithms, and Source Code in C,” by Bruce Schneier, published by John Wiley & Sons, Inc., 1996, and as to the correlation attacks, there is an explanation in “Correlation-Immunity of Nonlinear Combining Functions for Cryptographic Applications” by T. Siegenthaler, IEEE Transactions on Information Theory, Vol. IT-30, No. 5, 1984, for example. However, description of details of the pseudo-random-sequence generator itself or the correlation attacks is omitted, here.
In any way, to be sufficiently robust against cryptographic analysis such as the correlation attacks, sufficient numbers of sufficiently long-bit feedback-shift-registers should be used for generating the key-stream, which requires numbers of internal keys to be set to the feedback-shift-registors as their initial values.
On the other hand, bit-length of a secret crypto-key is usually limited practically, such as 64 bits, for example. Therefore, it is important for the pseudo-random-sequence generator consisting of feedback-shift-registers how to securely generate numbers of internal keys to be set thereto, from a secret-key given from external (hereinafter called the external key).
As above mentioned, one or some internal keys may be estimated by the correlation attacks. Hence, when the internal keys are generated from a single external key without sufficient care, all the internal keys may be easily estimated based on the broken internal keys.
Cryptographically secure internal keys may be obtained making use of a one-way function in the same way with generating the pseudo-random-sequence itself, by the pseudo-random-sequence generator of
FIG. 5
, for example. However, a demerit of obtaining the internal keys by way of the one-way function lies in that it takes too long time even for generating the internal keys once at the beginning of a cipher-stream. Because, the pseudo-random-sequence generator cannot but generate the pseudo-random-numbers bit by bit. Therefore, n×m clocks should be needed for generating n sets of internal keys of m bits, for example, and the clock frequency cannot be made high because of comparatively long calculation time of the one-way function.
SUMMARY OF THE INVENTION
Therefore, a primary object of the present invention is to provide method of and an apparatus for generating internal crypto-keys to be set initially in the feedback-shift-registers of a pseudo-random-sequence generator of the stream cipher system, with sufficient security and sufficiently high speed as well.
In order to achieve the object, a method according to the invention of generating internal crypto-keys from an external key comprises:
a step of outputting m sets of first conversion results, each i-th of the m sets of first conversion results being obtained by processing an (i−1)-th of the m sets of first conversion results with a first non-linear function and first of the m sets of first conversion results being obtained by processing a first part of the external key with the first nonlinear function, m being a positive integer more than one, i being a positive integer more than one and not more than m, and the first nonlinear function being a function wherein a variable giving a value of the function is difficult to be estimated from the value of the function;
a step of outputting m sets of second conversion results, each i-th of the m sets of second conversion results being obtained by processing an (i−1)-th of the m sets of first conversion results with a second nonlinear function and first of the m sets of second conversion results being o
Jack Todd
NEC Corporation
Peeso Thomas R.
Young & Thompson
LandOfFree
Method of and an apparatus for generating internal crypto-keys does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Method of and an apparatus for generating internal crypto-keys, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method of and an apparatus for generating internal crypto-keys will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2485629