JPS6329743B2 - - Google Patents

Description

[Detailed Description of the Invention] The present invention is based on the RSA method (Rivest, Shamir and
Adelman's method), a cryptographic master key that determines the existence of a convenient master key that can be commonly used for each individual cryptographic key from that individual cryptographic key, and automatically generates a master key if it exists. This relates to a generating device.

When providing various services using data communication systems and data processing systems, handling of highly confidential and important data has become an issue.
Various cryptographic key management methods have been proposed. By the way, the concept of a normal "master key" used in conventional cryptographic key management methods is a concept under management methods that always require a "master key" when using an individual key, so to speak, security is The aim was to strengthen the Specifically, the individual keys for each encryption machine are once encrypted with one "master key" and distributed, and when each individual key is used, the individual key must first be decrypted with that "master key." then use it. This "master key" is a so-called "master key for individual key encryption." On the other hand, a master key that can be used directly and commonly as a substitute for individual keys in a physical lock system is called a "true master key."
The present invention relates to this "true master key."

The above-mentioned concept of a "true master key" is not found in conventional cryptographic key management methods, and a method for synthesizing it through specific analysis has not been clarified.
In the following, the "true master key" will be simply referred to as the master key. In addition, as a specific cryptographic system for generating master keys, it is considered the most promising among public key cryptosystems (methods in which the encryption key and decryption key are different) that can be signed and keys can be easily distributed. RSA
Subject to law.

Already proposed RSA method (Rivest, Shamir
and Adelman “A method for observing
Digital Signature and Public−Key
Cryptosystems” CACM Vol.21, No.2, Feb.
The cryptographic principle based on individual keys (1978) is as follows.

m individual keys (encryption individual key K _ei , decryption individual key K _di , (1im)) are obtained independently by the following procedure.

(i) Select two arbitrary different large prime numbers p _i and q _i and calculate n _i =p _i ·q _i .

(ii) (P _i −1) (q _i −1) (hereinafter abbreviated as (n _i ))
Select any integer k _di that is coprime to .

(iii) Calculate the inverse element K _ei of the multiplication of K _di modulo (n _i ). That is, K _ei is obtained by solving K _ei ·K _di ≡1 (mod(n _i )).

Then, the encryption key is a pair of (K _ei , n _i ),
The corresponding decryption key is the pair (K _di , n _i ).
K _ei and n _i are made public and K _di is kept secret.

Algorithm E for encrypting plaintext P into ciphertext C
Then, algorithm D for decrypting ciphertext C into plaintext P is expressed as C=E(P)=P ^Kei (mod n _i ) P=D(C)=C ^Kdi (mod n _i ).

The present invention develops a conventional cryptographic system consisting only of individual keys, generates a master key that can be commonly applied to multiple individual keys, reduces the storage capacity for storing all the individual keys, and enables the master key holder to However, the present invention aims to provide a cryptographic master key generation device that enables flexible and efficient cryptographic key management so that it can be used in emergencies and for daily convenience without having to own each individual key. be.

Hereinafter, the present invention will be explained separately into a method for checking the existence condition of a master key and a specific method for deriving it when the master key exists. Note that the master key is for m sets of individual keys.

First, the method for checking existence conditions will be explained.
Here, the encryption individual key is K _ei (i=1, 2,...,
m), the decryption individual key is K _di (i=1, 2,..., m)
Let K _eM be the encryption master key, and K _dM be the decryption master key. Encryption and decryption functions are isomorphic in the sense that they raise a certain number (plaintext or ciphertext) to a power modulo n _i , and the existence conditions for the master key of the encryption key and decryption key can be found independently and similarly. .
In the following, for simplicity, the subscripts e and d of K _di and K _ei and K _eM and K _dM are omitted, and they are expressed as K _i and K _M , respectively.
P and C are represented by M.

The condition for the existence of a master key is that M ^KM ≡M ^Ki (mod n _i ) (1) holds for all i from 1 to m and all integers M from 0 to n _i -1. That's true. If we consider equation (1) separately for the case where M is disjoint with p _i and the case where M is disjoint with q _i , the necessary and sufficient condition for equation (1) to hold is K _M =K _i +l _i E _i (i=1,...,m) (2) E _i =LCM {(p _i −1), (q _i −1)} (3) It is derived that. Here, LCM {(p _i −
1), (q _i −1)} represents the least common multiple of (p _i −1) and (q _i −1), and l _i is an integer.

To make the conditions more specific, the condition for the existence of a master key is that the following equation holds true for all combinations of integers i and j between 1 and m.

K _j −K _i = a _ij × g _ij g _ij = GCD (E _i , E _j ) (4) Here, GCD (E _i , E _j ) represents the greatest common divisor of E _i and E _j , and a _ij is an integer.

Next, given an individual key K _i that satisfies the master key existence conditions shown above, the master key K _M
We will explain the specific method of finding. The master key for the first to i-th (1im) individual keys is expressed as K _M,i . Naturally, K _M,n = K _M and K _M,1 = K ₁ .

From the existence condition, for example, regarding K _M,2 , K _M,2 = K ₁ + ₁ E ₁ K _M,2 = K ₂ + l ₂ E ₂ is satisfied. Therefore, by eliminating K _M,2 , we get ₁ E ₁ −l ₂ E ₂ =K ₂ −K ₁ (5), and solving this two-dimensional linear equation, ₁ ,
Find l ₂ . Therefore, K _M,2 is found. next
Regarding K _M,3 , solve K _M,3 = K _M,2 + ₂ LCM (E ₁ , E ₂ ) K _M,3 = K ₃ + l ₃ E ₃ (6) to find ₂ and l ₃ . Therefore, K _M,3 is found. If K _M,i is found in the same way one after another, generally for K _n,i (i=2,...,m), K _M,i = K _M,i-1 +l _i-1・L _{i- 1} K _M,i =K _i +l _i E _i (7) holds true. However, L _i = LCM (E ₁ , E ₂ ,...,
E _i ) (i=1,..., m-1).

Therefore, equation (7) becomes _i-1・l _i-1 −l _i E _i =K _i −K _M,i-1 , and by solving this two-dimensional linear indeterminate equation, _i-1 ,
Find l _i . From the obtained l _i , K _M,i can be found. When i is increased, K _M,n (=K _M ) is finally found.

Next, an embodiment of the apparatus of the present invention having the above-mentioned master key existence condition checking and master key generation functions will be described.

FIG. 1 is a block diagram of an embodiment of a cryptographic master key generation device according to the present invention. In FIG. 1, the individual key K _i is connected to the data reading circuit 11 from the line 10.
When m sets of basic constants p _i and q _i are input, according to the instructions of the program in the program storage memory 16,
A computing unit 15 consisting of an adder 12, a multiplier 13, and a divider 14 is used to check the existence of a master key and derive the master key, and the data storage memory 1
While intermediate variables are stored in 7, the result is outputted by the data writing circuit 18.

Details of the main parts of FIG. 1 are shown in FIG. 2. In FIG. 2, when the individual key K _i is input from line 26,
The data is stored in the data storage memory 17 as it is. line 2
When p _i and q _i are input from 1, the least common multiple derivation program in the program storage memory 16 is started, E _i of equation (3) is calculated using the arithmetic unit 15, and it is stored in the data storage memory 17. do. When the storage of m sets of K _i and E _i is completed, the greatest common divisor derivation program in the program storage memory 16 is activated, g _ij in equation (4) is calculated using the data E _i and the arithmetic unit 15, and the data The data is stored in the storage memory 17. Next, data K _i and adder 1
2 to find K _i −K _j and store data in data storage memory 1.
Store in 7. K _i −K _j is divided by g _ij by the divider 14 and the remainder is output to the line 27 . Comparator 28
It is determined whether the remainder is 0 or not, and if it is not 0, a signal is sent through the line 29 and a message is outputted through the data writing circuit 18 saying that "the master key does not exist."

If all m remainders are 0, a master key exists, and the process moves to the master key generation stage. First, the least common multiple derivation program in the program storage memory 16 is started from the data E ₁ , E ₂ , ..., E _i , L _i is calculated using the arithmetic unit 15, and the data is stored in the data storage memory 1.
Store in 7. Next, the program for solving the two-dimensional linear indefinite equation in the program storage memory 16 is started, and the data E _i , L _i-1 , K _M,i-1 , K _i (i=2,..., m
-1) and computing unit 15 to find l _i in equation (7), further using computing unit 15 to find K _M,i , and store it in data storage memory 17 . The overall master key K _M (=K _Mn ) is finally obtained by sequentially executing the above two-dimensional linear indeterminate equation from i to m. This K _M is output using the data write circuit 18.

As explained above, the cryptographic master key generation device of the present invention has the following advantages.

(1) For cryptographic systems in which the existence of a master key was previously unknown, it is possible to specifically clarify the existence conditions and automatically check whether each individual key meets the existence conditions.

(2) If the master key existence conditions are met, the master key can be automatically generated from the individual keys.

(3) The key storage capacity is small.

(4) In an emergency, the master key holder can perform key input operations quickly without using each individual key.

(5) Even if an individual key is lost or destroyed, it can be replaced by the master key, improving reliability.

[Brief explanation of the drawing]

FIG. 1 is a block diagram of an embodiment of a cryptographic master key generation device according to the present invention, and FIG. 2 is a detailed diagram of the main part of FIG. 1. 11... Data reading circuit, 12... Adder, 13... Multiplier, 14... Divider, 15...
Arithmetic unit, 16...Program storage memory, 17...
...Data storage memory, 18...Data write circuit, 28...Comparator.

Claims (1)

[Claims] 1 means for inputting a plurality of different individual encryption keys, means for determining whether or not the plurality of different individual encryption keys satisfy the existence condition of a master key that can commonly be substituted for the plurality of different individual encryption keys; A cryptographic master key generation device comprising means for generating a master key that can be commonly applied to the plurality of individual cryptographic keys when an existence condition is satisfied.