Cryptography – Key management
Reexamination Certificate
1998-06-25
2001-10-23
Hayes, Gail (Department: 2131)
Cryptography
Key management
C380S044000, C380S045000
Reexamination Certificate
active
06307940
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Field of the Invention
The preset invention relates to a communication network and a method thereof for realizing secrecy of data in the field of communication, in which the encryption key is changed each time communication is made, even if the other party with which communication is being made is the same party each time. More particularly, the preset invention relates to a cryptosystem for an open-algorithm common key block cipher, in which the encryption key for the block cipher is sequentially updated in order to improve safety, and to a method for updating the key for the cryptosystem.
2. Description of the Related Art
Open-algorithm common key block ciphers such as represented by the DES (Data Encryption Standard) and FEAL (Fast data Encipherment Algorithm) are defective in that the key can be analyzed in the event that a certain number or more of sets of cipher text encrypted by the key and plain text are output.
In order to deal with this defect, U.S. Pat. No. 5,600,720 (hereafter referred to as “Reference 1”) proposes a cryptosystem in which the key for block cipher is periodically updated by cryptographically secure pseudo-random numbers, in which, as shown in
FIG. 22
, the key is updated by cryptographically secure pseudo-random numbers before outputting the number of sets of cipher text and plain text needed to analyze the key so as to complicate the difficulty in analyzing the key, thereby improving the safety of the open-algorithm common key block cipher. It must be noted here that the term “cryptographically secure pseudo-random number” refers to a pseudo-random number which is indistinguishable from a true random number by a logic circuit of a polynomial order.
In other words, a cryptographically secure pseudo-random number sequence is a number sequence in which it is extremely difficult to predict a subsequent sequence from an output sequence. Such is discussed in detail in, e.g., A. C. Yao: “Theory and Applications of Trapdoor Functions” (Proceedings of the 23rd IEEE Symposium on Foundations of Computer Science, IEEE, pp. 80-91, 1982), (hereafter referred to as “Reference 2”), and M. Blum and S. Micali: “How to Generate Cryptographically Strong Sequences of Pseudo-Random Bits” (Proc. 22nd FOCS, IEEE, pp. 112-118, 1982), (hereafter referred to as “Reference 3”).
Known algorithms for generating such cryptographically secure pseudo-random numbers include such using square-type random numbers, RSA cipher, discreet logarithms, and inverse number cipher.
The cryptosystem shown in
FIG. 22
is comprised of a pseudo-random number generator
1
, a computing device
2
, and a block encrypting device
3
. The pseudo-random number generator
1
generates pseudo-random numbers following a cryptographically secure pseudo-random number algorithm. DES cipher or FEAL cipher is used as the block cipher for the algorithm for the block encrypting device
3
. The key stream necessary for periodical updating of the block cipher key is obtained by dividing the cryptographically secure pseudo-random number series output from the computing device
2
into bit-lengths of the block cipher key. The block cipher key is updated by means of sequentially using the key stream k
1
, k
2
, . . . , as the block cipher key. The block encrypting device
3
performs encrypting of the plain text block stream
5
(communication text: M
11
to M
1s
, M
21
to M
2s
, . . . , M
t1
to M
ts
) into the cipher block stream
6
(k
1
(M
11
)) to k
1
(M
1s
), k
2
(M
21
) to k
2
(M
2s
), . . . , k
t
(M
t1
) to k
t
(M
ts
)), and deciphering of the cipher text.
The pseudo-random number generator
1
which generates cryptographically secure pseudo-random numbers due to algorithms using square-type random numbers, RSA cipher, discreet logarithms, and inverse number cipher, is configured as shown in FIG.
23
. The operation thereof is as shown below:
(1) x
0
=K
AB
is input into the pseudo-random number generator
1
as the initial value 4.
(2) x
1
, x
2
, . . . , is generated by feedback calculation x
i+1
=f (x
i
) (i=0, 1, . . . ) in the first computing unit
101
.
(3) In the second computing unit
102
, calculation b
i+1
=g (x
i+1
) (i=0, 1, . . . ) is performed from the generated x
1
, x
2
, . . . , and the obtained b
1
, b
2
, . . . , b
m
is output as pseudo-random number
7
(CR
AB
).
In the above procedures, x
i+1
which is periodically updated by feedback calculation is referred to as an internal variable within the pseudo-random number generator
1
. Also, the procedures necessary to generate a pseudo-random number b
1
obtained at one time is referred to as one step.
Further, the computing device
2
converts the output CR
AB
obtained from the pseudo-random number generator
1
into the block cipher key stream k
1
, k
2
, . . . , k
t
. Each of the keys k
u
(u=1, 2, . . . , t) of the block cipher are bit streams of a certain length which is determined by the algorithm of the block cipher used, and are generated by the computing device
2
dividing the cryptographically secure pseudo-random number stream CR
AB
in the determined bit lengths.
In
FIG. 22
, M
uv
(u=1, 2, . . . , t:v=1, 2, . . . , s) represents plain text block
5
, k
u
(u=1, 2, . . . , t) represents the key stream
8
of the block cipher, k
u
(M
uv
) (u=1, 2, . . . , t:v=1, 2, . . . , s) represents the cipher text block stream
6
obtained by encrypting the plain text M
uv
with the encryption key k
u
. Here, the number s blocks from M
u1
to M
us
is encrypted using the same key k
u
. The plain text block
5
shown in
FIG. 22
is encrypted by a plurality of encrypting keys by means of sequentially using the aforementioned pseudo-random number stream as the block cipher key.
According to this cryptosystem, the number of plain text block encrypted by the same key is s, so analyzing of the key can be made difficult in the event that the number of sets of plain text blocks and cipher text blocks necessary for analysis of the key exceeds the number s.
In other words, the shorter the cycle for updating the block cipher key is, the further the number of pieces of plain text encrypted with the same key is reduced, thereby improving the safety thereof.
However, with the arrangement described in Reference 1, the aforementioned cryptographically secure pseudo-random number stream
7
(CR
AB
) is divided into bit lengths of the block cipher key and used sequentially as the block cipher key, so once a key is updated, updating to the next key cannot be made until pseudo-random numbers in bit lengths of the block cipher key are output anew from the pseudo-random number generator
1
.
Now, this will be quantitatively evaluated. The updating cycle of the block cipher key can be calculated as follows. In the event that cryptographically secure pseudo-random numbers generated at the speed of w
r
(bps) are used in a situation wherein, as shown in
FIG. 24
, the bit length of each block to be encrypted at one time is m
b
(bits), the bit length of the encryption key is m
k
(bits), and the encryption processing speed is w
e
(bps), the number of block encryption keys w
k
generated per second can be calculated as follows:
w
k
=w
r
/m
k
.
The number of blocks w
b
which can be encrypted per second is:
w
b
=w
e
/m
b
,
and accordingly, the number of blocks s encrypted with one encryption key is:
s=w
b
/w
k
.
The number of plain text blocks s encrypted with the same encryption key can be thus obtained.
For example, let us calculated what s will be under the following <Conditions 1>.
<Conditions 1>
(Block encryption)
Bit length of blocks encrypted at one time: 64 bits (m
b
=64)
Bit length of encryption key: 72 bits (m
k
=72)
Encryption processing speed: 128 Mbps (w
e
=128×10
6
) (generation of pseudo-random numbers)
Number of pseudo-random numbers b
i
output at one time: 9 bits
Processing time per step: 10
−3
seconds
Now, the processing time per step refers to the pro
Iwamura Keiichi
Yamamoto Takahisa
Canon Kabushiki Kaisha
Fitzpatrick ,Cella, Harper & Scinto
Hayes Gail
Seal James
LandOfFree
Communication network for encrypting/deciphering... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Communication network for encrypting/deciphering..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Communication network for encrypting/deciphering... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2565791