Key distribution method

A key distribution method and system for distributing a key over an insecure communication channel between first and second systems. Both first and second systems generate respective random numbers, calculate key distribution codes based on that random number, public information and information secret to the respective systems, and transmits the distribution codes to the other system. The same key is generated by both systems based on public information, the locally generated random number and the received key distribution codes. Alternatively, the systems may exclude the secret information from the key distribution codes but generate and transmit identification codes based on the secret information, public information and the locally generated random numbers. The received key distribution and identification codes are subjected to a known transformation and compared to known identification of the transmitting system.

BACKGROUND OF THE INVENTION 
The invention relates to a method of distributing a key for enciphering an 
unenciphered or plaintext message and for deciphering the enciphered 
message. 
A public key distribution method used in a public key cryptosystem as a 
well-known key distribution method is disclosed in a paper entitled "New 
Directions in Cryptography" by W. Diffie and M. E. Hellman, published in 
the IEEE Transactions on Information Theory, Vol. IT-22, No. 6, pp. 644 to 
654, November issue, 1976. The key distribution method disclosed in the 
paper memorizes public information for each of conversers. In the system, 
before a converser A sends an enciphered message to a converser B, the 
converser A prepares an enciphering key (which represents a number 
obtained by calculating Y.sub.B.sbsp.A.sbsp.X (mod p)) generated from 
public information Y.sub.B of the converser B and secret information 
X.sub.A which is kept secret by the converser A. The number p is a large 
prime number of about 256 bits in binary representation, which is publicly 
known. a (mod b) means a remainder of division of the number a by the 
number b. The converser B also prepares the key wk in accordance to 
Y.sub.A.sbsp.B.sbsp.X (mod p) in a similar manner. Y.sub.A and Y.sub.B are 
selected so as to be equal to .alpha..sbsp.A.sbsp.X (mod p) and 
.alpha..sbsp.B.sbsp.X (mod p), respectively. As a result, 
Y.sub.B.sbsp.A.sbsp.X (mod p) becomes equal to Y.sub.A.sbsp.B.sbsp.X (mod 
p). It is known that even if Y.sub.A, .alpha. and p are known, it is 
infeasible for anybody except the converser A to obtain X.sub.A which 
satisfies Y.sub.A =.alpha..sbsp.A.sbsp.X (mod p). 
The prior art key distribution system of the type described, however, has 
disadvantages in that since the system needs a large amount of public 
information corresponding to respective conversers, the amount of the 
public information increases as the number of conversers increases. 
Further, strict control of such information becomes necessary to prevent 
the information from being with tampered. 
SUMMARY OF THE INVENTION 
An object of the invention is, therefore, to provide a key distribution 
method free from the above-mentioned disadvantages of the prior art 
system. 
According to an aspect of the invention, there is provided a method which 
comprises the following steps: generating a first random number in a first 
system; generating first key distribution information in the first system 
by applying a predetermined first transformation to the first random 
number on the basis of first secret information known only by the first 
system; transmitting the first key distribution information to a second 
system via a communication channel; receiving the first key distribution 
information in the second system; generating a second random number in the 
second system; generating second key distribution information by applying 
the predetermined first transformation to the second random number on the 
basis of second secret information known only by the second system; 
transmitting the second key distribution information to the first system 
via the channel; receiving the second key distribution information in the 
first system; and generating an enciphering key in the first system by 
applying a predetermined second transformation to the second key 
distribution information on the basis of the first random number and 
identification information of the second system which is not secret. 
According to another aspect of the invention, there is provided a method 
which comprises the following steps: generating a first random number in 
the first system; generating first key distribution information by 
applying a predetermined first transformation to the first random number 
on the basis of public information in the first system and generating 
first identification information by applying a predetermined second 
transformation to the first random number on the basis of first secret 
information known only by the first system; transmitting the first key 
distribution information and the first identification information to a 
second system via a communication channel; receiving the first key 
distribution information and the first identification information in the 
second system; examining whether or not the result obtained by applying a 
predetermined third transformation to the first key distribution 
information on the basis of the first identification information satisfies 
a first predetermined condition, and, if it does not satisfy, suspending 
key distribution processing; generating a second random number if said 
condition is satisfied in the preceding step; generating second key 
distribution information by applying the predetermined first 
transformation to the second random number on the basis of the public 
information, and generating second identification information by applying 
the predetermined second transformation to the second random number on the 
basis of second secret information known only by the second system; 
transmitting the second key distribution information and the second 
identification information to the first system via the communication 
channel; and examining whether or not the result obtained by applying a 
third predetermined transformation to the second key distribution 
information on the basis of the second identification information in the 
first system satisfies a predetermined second condition, and if the result 
does not satisfy the second condition, suspending the key distribution 
processing, or if it satisfies the second condition, generating an 
enciphering key by applying a fourth predetermined transformation to the 
first random number on the basis of the second key distribution 
information.

PREFERRED EMBODIMENTS 
Referring now to FIG. 1, a first embodiment of the invention comprises a 
first system 101, a second system 102 and an insecure communication 
channel 103 such as a telephone line which transmits communication signals 
between the systems 101 and 102. It is assumed herein that the systems 101 
and 102 are used by users or conversers A and B, respectively. The user A 
has or knows a secret integer number S.sub.A and public integer numbers e, 
c, .alpha. and n which are not necessarily secret while the user B has or 
knows a secret integer number S.sub.B and the public integer numbers. 
These integer numbers are designated and distributed in advance by a 
reliable person or organization. The method to designate the integer 
numbers will be described later. 
An operation of the embodiment will next be described on a case in which 
the user A starts communication. The system 101 of the user A generates a 
random number .gamma. (Step A1 in FIG. 1) and sends a first key 
distribution code X.sub.A representative of a number obtained by computing 
S.sub.A .multidot..alpha..sup..gamma. (mod n) (Step A2) to the system 102 
of the user B (step A3). Next, when the system 102 receives the code 
X.sub.A (Step B1), it generates a random number t (Step B2), calculates 
(X.sub.A.sup.e /ID.sub.A).sup.t (mod n) (Step B5), and keeps the resulting 
number as a enciphering key wk for enciphering a message into storage 
means (not shown). The identification code ID.sub.A represents herein a 
number obtained by considering as a numeric value a code obtained by 
encoding the address, the name and so on of the user A. The encoding is, 
for instance, performed on the basis of the American National Standard 
Code for Information Interchange. Then, the system 102 transmits to the 
system 101 of the user A a second key distribution code X.sub.B 
representative of a number obtained by calculating S.sub.B 
.multidot..alpha..sup.t (mod n) (Steps B3 and B4). 
The system 101, on the other hand, receives the code X.sub.B (Step A4), 
calculates (X.sub.B.sup.e /ID.sub.B).sup..gamma. (mod n) (Step A5), and 
keeps the resulting number as the key wk for enciphering a message. The 
identification code ID.sub.B represents the numbers obtained by 
considering as a numeric value a code obtained by encoding the name, 
address, and so on of the user B. 
Subsequently, communication between the users A and B will be conducted by 
transmitting messages enciphered with the enciphering key wk via the 
channel 103. 
The integer numbers S.sub.A, S.sub.B, e, c, .alpha. and n are determined as 
follows. n is assumed to be a product of two sufficiently large prime 
numbers p and q. For instance, p and q may be 2.sup.256 or so. e and c are 
prime numbers which are equal to or less than n, while .alpha. is a 
positive integer number which is equal to or less than n. Further, d is 
defined as an integer number which satisfies e.d (mod 
(p-1).multidot.(q-1))=1. S.sub.A and S.sub.B are defined as numbers 
obtainable from ID.sub.A.sup.d (mod n) and ID.sub.B.sup.d (mod n), 
respectively. 
If S.sub.A, S.sub.B, e, c, .alpha., and n are defined as above, ID.sub.A 
and ID.sub.B become equal to S.sub.A.sup.e (mod n) and S.sub.b.sup.e (mod 
n), respectively. This can be proved from a paper entitled "A Method for 
Obtaining Digital Signatures and Publick-Key Cryptosystems" by R. L. 
Rivest et al., published in the Communication of the ACM, Vol. 21, No. 2, 
pp. 120 to 126. Since the key obtained by (X.sub.B.sup.e /ID.sub.B).sup.r 
(mod n) on the side of the user A becomes equal to .alpha..sup.ert (mod n) 
and the key obtained by (X.sub.A.sup.e /ID.sub.A).sup.t (mod n) on the 
side of the user B becomes equal to .alpha..sup.ert (mod n), they can 
prepare the same enciphering key. Even if a third party tries to assume 
the identity of the user A, he cannot prepare the key wk since he cannot 
find out z which meets ID.sub.A =Z.sup.e (mod n). 
Referring now to FIG. 2, a second embodiment of the invention comprises a 
first system 201, a second system 202 and an insecure communication 
channel 203. It is assumed herein that the systems 201 and 202 are used by 
users A and B, respectively. The user A has or knows a secret integer 
number S.sub.A and public integer numbers e, c, .alpha. and n, which are 
not necessarily secret while the user B has or knows a secret integer 
number S.sub.B and the public integer numbers. These integer numbers are 
designated and distributed by a reliable person or organization in 
advance. The method to designate the integer numbers will be described 
later. 
An operation of the embodiment will next be described on a case where the 
user A starts communication. The system 201 of the user A generates a 
random number .gamma. (Step AA1 in FIG. 2) and determines a first key 
distribution code X.sub.A representative of a number obtained by computing 
.alpha..sup.e.r (mod n) as well as a first identification code Y.sub.A 
indicative of a number obtained by computing 
S.sub.A.multidot..alpha..sup.c.r. (mod n) (Step AA2). The system 201 then 
transmits a first pair of X.sub.A and Y.sub.A to the system 202 of the 
user B (Step AA3). Thereafter, the system 202 receives the first pair 
(X.sub.A, Y.sub.A) (Step BB1), calculates Y.sub.A.sup.e /X.sub.A.sup.c 
(mod n), and examines whether or not the number obtained by the 
calculation is identical to the number indicated by an identification code 
ID.sub.A obtained by the address, the name and so on of the user A in a 
similar manner to in the first embodiment (Step BB2). If they are not 
identical to each other, the system suspends processing of the key 
distribution (Step BB7). On the other hand, if they are identical to each 
other, the system 202 generates a random number t (Step BB3) and 
determines a second key distribution code X.sub.B representative of a 
number obtained by calculating .alpha..sup.e.t (mod n) and a second 
identification code Y.sub.B obtained by calculating 
S.sub.B.multidot..alpha..sup.c.t (mod n) (Step BB4). The system 202 then 
transmits a second pair of X.sub.B and Y.sub.B to the system 201 of the 
user A (Step BB5). The system 202 calculates X.sub.A.sup.t (mod n) and 
keeps the number thus obtained as a enciphering key wk (Step BB6). 
The system 201, on the other hand, receives the second pair (X.sub.B, 
Y.sub.B) (Step AA4), calculates Y.sub.B.sup.e /X.sub.B.sup.c (mod n), and 
examines whether or not the number thus obtained is identical to the 
number indicated by an identification code ID.sub.B obtained by the 
address, the name and so on of the user B in a similar manner to in the 
first embodiment (Step AA5). If they are not identical to each other, the 
system suspends the key distribution processing (Step AA7). If they are 
identical to each other, the system 201 calculates X.sub.B.sup.r (mod n), 
and stores the number thus obtained as a enciphering key wk (Step AA6). 
Although the codes ID.sub.A and ID.sub.B are widely known, they may be 
informed by the user A to the user B. 
The integer numbers S.sub.A, S.sub.B, e, c, .alpha. and n are determined in 
the same manner as in the first embodiment. As a result, ID.sub.A and 
ID.sub.B becomes equal to Y.sub.A.sup.e /X.sub.A.sup.c (mod n) 
(=S.sub.A.sup.e.multidot..alpha..sup.erc /.alpha..sup.erc (mod n)) and 
Y.sub.B.sup.e /X.sub.B.sup.c (mod n) 
(=S.sub.B.sup.e.multidot..alpha..sup.etc /.alpha..sup.etc (mod n)), 
respectively. If we presuppose that the above-mentioned reliable person or 
organization who prepared S.sub.A and S.sub.B do not act illegally, since 
S.sub.A is possessed only by the user A while S.sub.B is possessed only by 
the user B, the first pair (x.sub.A, y.sub.A) which satisfies 
y.sub.A.sup.e /x.sub.A.sup.c (mod n)=ID.sub.A can be prepared only by the 
user A while the second pair (x.sub.B, y.sub.B) which satisfies 
y.sub.B.sup.e /x.sub.B.sup.c (mod n)=ID.sub.B can be prepared only by the 
user B. It is impossible to find out a number x which satisfies x.sup.f 
(mod n)=ID.sub.B on the basis of f, b and n since finding out X is 
equivalent to breaking the RSA public key cryptogram system disclosed in 
the above-mentioned article in the Communication of the ACM. It is 
described in the above-referenced article in IEEE Transactions on 
Information Theory that the key wk cannot be calculated from the codes 
x.sub.A or x.sub.B and n. The key distribution may be implemented 
similarly by making the integer number C variable and sending it from a 
user to another. 
An example of the systems 101, 102, 201 and 202 to be used in the first and 
second embodiments will next be described referring to FIG. 3. 
Referring now to FIG. 3, a system comprises a terminal unit (TMU) 301 such 
as a personal computer equipped with communication processing functions, a 
read only memory unit (ROM) 302, a random access memory unit (RAM) 303, a 
random number generator (RNG) 304, a signal processor (SP) 306, and a 
common bus 305 which interconnects the TMU 301, the ROM 302, the RAM 303, 
the RNG 304 and the SP 306. 
The RNG 304 may be a key source 25 disclosed in U.S. Pat. No. 4,200,700. 
The SP 306 may be a processor available from CYLINK Corporation under the 
trade name CY 1024 KEY MANAGEMENT PROCESSOR. 
The RNG 304 generates random numbers r or t by a command given from the SP 
306. The ROM 407 stores the public integer numbers e, c, .alpha., n and 
the secret integer number S.sub.A (if the ROM 407 is used in the system 
101 or 201) or the secret integer number S.sub.B (if the ROM 407 is used 
in the system 102 or 202). The numbers S.sub.A and S.sub.B may be stored 
in the RAM 303 from the TMU 301 everytime users communicates. According to 
a program stored in the ROM 407, the SP 306 executes the above-mentioned 
steps A2, A5, AA2, AA5, AA6 and AA7 (if the SP 306 is used in the system 
101 or 201), or the steps B3, B5, BB2, BB4, BB6 and BB7 (if the SP 306 is 
used in the system 102 or 202). The RAM 303 is used to temporarily store 
calculation results in these steps. 
Each of the systems 101, 102, 201 and 202 may be a data processing unit 
such as a general purpose computer and an IC (integrated circuit) card. 
As described in detail hereinabove, this invention enables users to 
effectively implement key distribution simply with a secret piece of 
information and several public pieces of information. 
While this invention has thus been described in conjunction with the 
preferred embodiments thereof, it will now readily be possible for those 
skilled in the art to put this invention into practice in various other 
manners.