Encryption system key distribution method and apparatus
Abstract
This record has no abstract on file.
Term
Term ended
Projected expiry passed 11 January 2003, 23.7 years ago.
- Priority
- Filed
- Published
- Projected expiry
- Today
17 claims: 17 independent, 0 dependent
- 1Claims 1. A key distribution method for communicating cipher keys between two terminals via a key distribution center, KDC, said method comprising 5 establishing between any one terminal and said key distribution center a terminal-unique cipher key, cooperating between said KDC and said one terminal on a subsequent connection between said KDC and said one terminal to establish a session key for use by said one 10 terminal in a subsequent secure transmission between said one terminal and a second terminal, and changing in response to said subsequent connection between said one terminal and said KDC said priorly established terminal-unique cipher key. 15 2. The invention set forth in claxm 1 wherein said session key is generated from the asymmetric exchange of information' between said one terminal and said KDC plus the subsequent exchange of information between said first and second terminals. 20 3. The invention set forth in claim 2 wherein said session key at said one terminal is random with respect to information at said KDC. 4. The invention set forth in claim 2 wherein said session key at said one terminal is underivable with 25 respect to any information at said KDC. ·♦· 5. A key distribution center for controlling the dissemination of session cipher keys between remotely located terminals, said center arranged for switched access to a plurality of said terminals, said center comprising 30 means for establishing communication cipher keys between said center and each said terminal having access thereto, each cipher key unique to each said terminal, means operative when one of said terminals 'gOREA^ OMH accesses said center for bidirectional asymmetrically 35 exchanging information with said accessed terminal using, as a foundation for said exchange, said priorly establish d communication cipher keys, and SUBSTITUTE SHEET Ά WO 83/04461 PCT/US83/00030 means responsive to said exchanged information for communicating to said terminal information allowing said terminal to establish a session cipher key for use with an identified other terminal also having access to said center. 6. The invention set forth in claim 5 wherein said key distribution center further comprising means for changing said established communication cipher keys as a result of said exchanged information. 7. The invention set forth in claim 5 wherein said cipher key establishing means uses information from a prior transmission from a particular terminal for establishing said cipher keys to said particular terminal. 8. The invention set forth in claim 5 wherein ···· said exchanged information includes information generated . · · · in part at said center for the random generation of said * ·· · ··· session key allowing said session key to be underivable with respect to any information at said center. i*··;· 9. λ key distribution center for controlling the!..... distribution of cipher control information among a number of terminals, said center comprising means for individually exchanging encoded information between any of said terminals, said exchange %*·’· for any particular terminal based partially upon a last ·· · information exchange between said particular terminal and said center, !..... · · means for identifying at least two terminals wherj=ja · encrypted session information is to be exchanged and for accepting from said identified terminals certain encryption··, control information, and ·..... · · means for modifying, according to a pre-established pattern, accepted information from said identified terminals and for communicating said modified information to the other of said terminals so as to allow each of said terminals to thereafter establish, independent of any information available at said center, a cipher key allowing said session information to be encrypted. SUBSTITUTE SHEET WO 83/04461 PCT/US83/00030 1/17 FIG. I KDC CONFIGURATION TERMINAL TERMINAL A B TERMINAL X OMH X WIPO WO 83/04461 PCT/US83/00030
- 22/17 ··· 0· FIG. 2 INITIAL SYSTEM SETUP « 0·· • ·· 0 · • · 0 · UREAcZ OMPI WO 83/04461 PCT/US83/00030
- 33/17 ··· ·· FIG. 3 TERMINAL A A .FROM FIG. <1 1 L J RE AT/\ OMPI λ WO 83/04461 PCT/l )883/00030
- 44/17 /76 4 TERMINAL A ·« ·9· WO 83/04461 PCT/US83/00030
- 55/17 FIG. 5 KDC WO 83/C4461 PCT/US83/00030
- 66/17 FIG. 6 BETWEEN CALLS IDLE STATE (FOR TERMINAL A) »··* ···· ···· • · · ·· · • · ···» e <* SEMI-PERM REGISTER TEMP REGISTER TERMINAL A ADDRESS FIG. 7 START OF SECURE CALL (A TO B) SETUP-GENERATION OF KDC-A LINK KEYS .jj FCT/US83/00030 WO 83/04461 ·· · · • · · · • ·· · • · · • · · • · · ·
- 77/17 FIG. 8 GENERATION OF B-A LINK KEYS FIG. 9 FIRST STEP IN UPDATE OF VERIFICATION INFORMATION ?CT/t)583/00030 WO 83/04461
- 88/17 FIG. /0 SECOND STEP IN UPDATE OF VERIFICATION INFORMATION SEMI-PERM REGISTER TEMP REGISTER F!6. // COMPUTATION OF A-KDC MESSAGE • · • · · • · ······
- 99 · ····· • · «. .· . WO 83/04461 PCT/US83/OOO30 -9/17 F/G. !2 IDLE STATE WHILE WAITING FOR RETURN MESSAGE FROM KDC • · · · • · · · • · · · • · · • · · • · « · • · β · ·φ SEMI-PERM REGISTER TEMP REGISTER TERMINAL A ADDRESS FIG. !3 DECRYPTION OF RETURN MESSAGE FROM KDC TERMINAL A WO 83/04461 PCT/US83/00030 9· · 9 9 «·«· 9 99 9 9 99 9 99 9 9 9 9 9 9 9 9 9 9 9 9 9 9
- 1010/17 FIG. 14 VERIFICATION CHECK I SEMI-PERM REGISTER TEMP REGISTER IF (ZERO) THEN CONTINUE ELSE WARN CUSTOMER OF SUSPECTED INTRUDER I TERMINAL A ADDRESS •99999 9 · FIG. !5 START OF KEY EXCHANGE WITH B CALCULATION OF DIFFIE-HELLMAN KEYS WO 83/04461 PCT/US83/00030 • « · · ' · ···· • ·· · • 9 · ®β β ···· • · • · · ·
- 1111/17 FIG. /6 IDLE WAIT STATE FOR RETURN MESSAGE FROM B SEMI-PERM REGISTER TEMP REGISTER I TERMINAL A ADDRESS TERMINAL A SEMI-PERM REGISTER F/G. 17 DECRYPTION OF MESSAGE FROM B AND CALCULATION OF SESSION TEMP REGISTER' ZERO WO 83/04461 PCT/US83/00030 ·'
- 1212/17 F/G. 18 KEY STORAGE DURING CALL SEMI-PERM REGISTER TEMP REGISTER F/G. /9 IDLE STATE FOLLOWING CALL COMPLETION • · ··· ·· «· • « • ·
- 1313/17 WO 83/04461 PCT/US83/00030 ·· · · ·« ·· <\··· • · · • Λ · • · · · • · • · ·· • · · ο β · • · FIG. 20 IDLE STATE BETWEEN CALLS FIG. 2! DECRYPTION OF MESSAGE FROM A WO 83/04461 PCT/US83/00030 '
- 1414/17 • ft · · • ·« e • ·· · ·· · ···· • · · · · · • · FIG. 22 FIRST STEP IN THE UPDATE OF VERIFICATION INFORMATION FIG. 23 SECOND -STEP’THE UPDATE OF VERIFICATION INFORMATION WO 83/04461 PCT/US83/00030
- 1515/17 • · · • · · · • · »· • ·· · • · · • · · • · · · • · • « · · FIG. 24 GENERATION OF NEW KDC-A LINK KEYS FIG. 25 GENERATION OF DIFFIE-HELLMAN ALGORITHM PARAMETERS PCT/US83/00030
- 1616/17 WO 83/04461 • et» ···· ···· • · · a » · • ·· « • « ···· 9«···· • * FIG. 26 INTERNAL EXCHANGE OF INFORMATION BETWEEN A & B'S REGISTERS • * >· « «I WO 83/04461 PCT/US83/00030
- 1717/17 • « > · • '· »W ··· · • e ♦ ·-· · ··· · • · ··«« · «····· • a ······ » · ·» ·· • · · • · • *· • · « • «4 fl ··<··· • · € · · FIG. 28 IDLE STATE BETWEEN CALLS
Independent claims17
146 paragraphs in 33 sections, as filed
Background of the Invention
This invention relates to the establishment and distribution of cipher keys in a cryptographic system.
Cryptographic systems are now gaining favor, both for voice as well as data transmission. In such systems it is typically necessary that the parties to a particular 10 transmission each have cryptographic keys to encrypt and decrypt the cipher transmissions. It follows that a compromise to a cryptographic key will in turn reduce the security of subsequent transmissions involving that key. This, great precautions must be taken to distribute the
-ryptographic keys among the system users. Such distribution, for example, using secure couriers to manually update the keys may be possible when the community of users is priorly known but becomes increasingly more difficult when either the number of parties is large or parties who seldom communicate with each other wish to do so. The responsibility for keeping the cryptographic key secure after distribution rests with each user and the longer the key remains effective the greater the risk of it becoming compromised.
Thus, from a practical point of view it is desirable to have the cryptographic key effective for a single session, requiring a new key for each new session. When couriers are used, however, this becomes costly and time consuming, especially when a party wishes to place many secure calls or have many secure sessions.
Attempts have been made to electronically distribute cryptographic keys between users from a key distribution center. One such example is shown in
Rosenblum Patent No. 4,182,933, issued January 8, 1980.
While such attempts have found some degree of success they all suffer from the problem that they are subject to . OMPI ϊ
SUBSTITUTE SHEET
WO 83/04^1
PCT/US83/00030
- 2 -compromise because they usually rely on the security of the transmission media between the key distribution center and the terminal for the distribution of session key information. Thus, an intruder need only compromise the key distribution channel to obtain subsequent session keys. Elaborate systems have sometimes been established to detect such a compromise, all of which are either costly or minimally effective.
Another problem with key distribution centers is that the center can derive the information used to decrypt the secure data exchange between users and thus could theoretically monitor the secure session transmission. Summary of the Invention
We have solved the above-identified problems by *·;· ···· arranging a key distribution center (KDC) which .·*·· • · · f communicates over a channel with the individual terminals.
. · ·
The channel, or data link, can be a dial-up telephone line,···’ »
a packet-switched data network, dedicated lines, or other communications channel types, over which secure ····;· communication is possible. The terminals operate in conjunction with the KDC to establish a session key for secure transmission between two or more terminals. The · · · · session key at a terminal is constructed from information ·. · ;
generated at that terminal in conjunction with information**.·.
• e · communicated from the KDC and ic known fully only to the terminals involved in the session and net to the KDC. ;···;·
Thus, when two terminals have established a session key, .!. they may securely communicate with each other for the duration of that session. J···;·
At the conclusions of the secure data exchange,!.....
• · the session keys should Le destroyed, and when either station wishes to establish additional secure communication either between themselves or to other stations, a new session key will be established in cooperation with the
KDC. .
Both the terminal-KDC channel and the KDCterminal channel, as mentioned above, are secure links in
SUBSTITUTE SHEET
<img file="AU1109483A_D0001.tif" />
<img file="AU1109483A_D0002.tif" />
PCT/US83/00030 that they are protected by cryptographic key information which is unique to each terminal and to the KDC on a onecall-only basis. Accordingly, whenever a connection is established between a terminal and the KDC, each has
<img file="AU1109483A_D0003.tif" />
information previously stored, referred to as terminalunique key information, and this priorly stored information is used to establish both new KDC-terminal link keys, referred to as call-setup key information, and new session key information. During the establishment of the session keys, the terminal and the KDC each modify their respective terminal-unique key information so that on a next call between the KDC and the same terminal, this new key information must be used in order to establish a secure communication path. The precise manner in which this happens will be discussed hereinafter. In this manner, an intruder on the key distribution between a terminal and the KDC must be adding and substituting information on the channel from the beginning and must stay on the channel throughout several calls.<sub>o</sub> since once the intruder leaves it is possible to detect, at least by hindsight, that a compromise has occurred. This is a result of the fact that the intruder is substituting random information that may be monitored.
One aspect of our system is that an intruder, in order to obtain useful information exchanged between two valid users of the system, must gain the terminal-unique information that is stored at the terminal, and he must also gain the terminal-unique information that is stored in the key distribution center for that specific terminal.
The intruder then, on the very next key exchange involving that terminal and the key oistributing center, must actively participate, i.e., substitute his own generated key information on that channel. Then the intruder must also substitute information on the channel between the two communicating terminals, and also must continue the above * substitutions on the channels for an indefinite period of time or risk detection.
SUBSTITUTE SHEET
<img file="AU1109483A_D0004.tif" />
PGT/USB3/00030 β
Vs.
Brief Description of the Drawing
These attributes of our invention, together with the operation and utilization of the invention in a specific embodiment, will be more fully apparent from the illustrative embodiment shown in conjunction with the drawing which:
FIG. 1 shows an overall system several terminals;
FIG. 2 shows an implementation establishment of information in both the terminal within a secure area;
FIGS. 3 and 4 show a flow chart detailing what within each terminal;
FIG. 5 shows a flow chart detailing what occurs the KDC;
FIGS. 6-19 show, establishment of key each terminal; and
FIGS. 21-28 show, establishment of key the KDC. In this system we have a variety of using a KDC and of the initial
KDC and the occurs within of the within of the in sequence, an information and implementation control data in sequence, an information and implementation control data • ·· e · · · • e w· ·····♦ within terminals
General Description shows a number of terminals, A, B and X, · each other und to KDC 10 via some transport public switched network). These terminals to set up a secure channel between ···
FIG connectable to network (e.g., should be able themselves in order to exchange secure information. In this process they must both communicate with the KDC. The.’””' transmission line 12 from terminal A is connected through ····.. link 16 to transmission line 13 to initiate a secure call to terminal B. Once the users decide to initiate a secure data exchange, each terminal sets up a transmission line, such as link 14 for terminal A, to the KDC.
An exchange of information will then occur from terminal A to the KDC and from terminal B to the KDC. Once the KDC has received both of these messages, it will
SUBSTITUTE SHEET
<img file="AU1109483A_D0005.tif" />
OMPI X
WO 83/04461
PCT/USB3/00030
- 5 formulate two distinct messages that will be sent respectively to terminal A via link 14 and to terminal B via link 15. These individual messages will contain .
session key information, as well as other pertinent information described below. This session key information has originated at terminal A and at terminal B and is exchanged through the KDC. Once the exchange has taken place between the two terminals and the KDC, link 14, which is the key distribution link between terminal A and the
KDC, is then taken down, and key distribution link 15 between the KDC and terminal B is taken down. Link 16, which is the session link between terminals A and B, is ·· ··· re-established. Further key information is exchanged based on the prior partial exchanges so as to derive independently at both terminals the session key, and finally using that session key information, data (i.e., digital data or digital voice) can be transmitted in secure fashion on data link 16.
Since further session information was derived between terminals A and B independent of the KDC, a malicious operator of the KDC cannot derive the key « information need to decrypt the secure messages sent ' between terminals A and B without actively substituting information on the session channel.
Also, at this point, as will be seen, contained within the messages that were sent between the KDC and the terminals was new terminal-unique key information to secure the next key distribution between the terminals and the KDC. This new information is independent of the previous information and therefore is unique to it.
Detailed Description
Turning now to FIG. 2 the initial setup between the terminal and the. KDC must be made in an authentic manner such that the information transported to the terminals from the KDC is not modified. One implementation is where the transport is made within a secured area, such as secured area 23. Since subsequent
SUBSTITUTE SHEET communications ____ ( <sup>OMPI</sup>
83/04461
PCT/US83/00030 between the KDC and each terminal depend upon the prior communication, it is important that at some period in time they both contain the proper information for start-up, and ideally this is done in the secured area so that there can be no breach of security.
On the initial system setup (based on the secured area implementation shown in FIG., 2) the terminals are brought within the secured area 23, and the KDC can generate terminal-unique key pairs for each terminal. The exact function of these key pairs will be described later. The KDC will generate a terminal-unique decryption key for . each terminal and the corresponding encryption key. This encryption key must be placed in the terminal-unique key storage for each terminal with the corresponding decryption*;* · · · · key stored in the terminal-unique key storage at the KDC .·;··, · · · under the address of that terminal. In addition, a random ....
· · number, Ua for terminal A, unique to each terminal is .*’** stored in the verification information storage at the KDC ·***;* also at the address of this terminal. This same random ;*··;· number must be loaded and stored in the verification information storage in the terminals and will be used for a verification check on the first call setup to the KDC.
FIGS. 3 and 4 are flow charts representing the *.
action that occurs within a terminal, for example, *..*.* terminal A.
FIG. 5 is a flow chart representing what actionS‘·’;· occur within the key distribution center. ···
The discussion which will follow is a discussion with respect to a time sequence between the terminal and ;***;· the KDC to illustrate both how terminal-unique keys are ···... updated, and how call-setup and session keys are distributed. This discussion will occur with respect to FIGS. 6 through 28. FIGS. 6 through 19 show the apparatus within the terminal and show on a step-by-step basis how the call-setup keys and the session keys are established. FIGS. 20 through 28 show the apparatus within the KDC, each figure showing a specific operational aspect of the __
SUBSTITUTE SHEET
PCT/US83/00030
WO 83/04461 establishment of the keys.
Turning now to FIG. 6, we will discuss the specific apparatus used in the terminals. The actual generation of the numbers will be discussed hereinafter.
Apparatus 72 is a random number generator which is a device or algorithm that produces bits (zeros and onas) that are equally likely to occur. This generation may be based upon a noisy .diode and any number of algorithms can be used to attain statistically independent output of 0's and l’s.
The more equally likely these random number generators are, i.e., the more random this function is, the higher the security level will be. The output of the random number generator is a serial stream of zeroes and ones where the correlation between one or a group of bits is zero. The bidirectional asymmetric key generator, apparatus 73, takes as input a random number from random number generator 72 and will compute an encryption key and the matching decryption key such that the encryption key cannot be derived from the decryption key and vice versa. The generation of these keys as an example could be done in
<img file="AU1109483A_D0006.tif" />
accordance with the RSA algorithm, as described by Rivest, Shamir, and Adleman in a paper entitled, A Method for Obtaining Digital Signatures and Public Key Crypto Systems, which publication is hereby incorporated by reference, which appeared in CACM, Vol. 21, No. 2, February, 1978, on pages 120-126.
Apparatus 74 implements a bidirectional asymmetric cryptographic algorithm (e.g., the RSA algorithm) that is, a cryptographic algorithm based on two 30 distinct keys where the encryption key cannot be derived from the decryption key and vice versa. Apparatus 74 has two inputs (I and K) and one output (0) . The input I is the bits to be encrypted or decrypted. The input K is the key, either encryption or decryption (the RSA algorithm 35 performs the same function regardless of encryption decryption). The output will be the inputted bits encrypted or decrypted with the supplied key. This
SUBSTITUTE SHEET
<img file="AU1109483A_D0007.tif" />
PCT/US83/00030
WO 83/04461 algorithm is also described in the aforementioned paper. Functionally, apparatus 75 is the embodiment of two functions f and g such that: given f(R, P) and P, one cannot determine R; g(Rl, f (R2, P), P) = g(R2, f(Rl, P) , P); and given f(Rl, P) , f(R2, P), and P one cannot determine Rl, R2, or g(Rl, f (R2, P), P) .
Apparatus 75 performs the above functions via, for example, the Diffie-Hellman algorithm, which is described in a paper by Diffie and Hellman entitled New Directions in Cryptography, published by the IEEE Transactions on Information Theory, Vol. IP-22, November, 1976, on pages 644-655, which is hereby incorporated by reference. The input to this algorithm is a base Y, a modulus Q and an exponent EXP. The output is Y raised to · the EXP power modulus the Q. The functions f and g are the..... same as discussed above in this example. * ’* <sup>x</sup> · · · a
The storage requirements are depicted by registers 71, 70 and 76. These are the semi-permanent register 71 which contains both the verification »····· information Va and the terminal-unique key information Eak used to encrypt messages to the KDC. Temporary register 70 can be in any state initially and is used during the interaction with the KDC on a secure call setup. The ·. ·*· address register permanently contains the address (i.e., a,··,·.
public piece of information that uniquely identifies A to the KDC) of the terminal (terminal A in this case) where is located. During a secure session (or call) setup, the address register will also contain the address of the terminal which is being called. The registers containing;···;· verification information and encryption and decryption • · information may vary in size depending upon the specific algorithm used but in this example should be on the order of 1,000 bits each. Information pertaining to the symmetric session key and the random number should be on the order of 100 bits, and the address information will be dependent upon a terminal numbering plan both unique and known to the KDC. For example, it could be the telephone
SUBSTITUTE SHEET
WO «3/04461
PCT/US83/00030
- 9 number of the specific terminal or it could be the serial number of the terminal.
Turning to FIG. 20, we will now discuss the working of the modules within the key distribution unit.
The address register at the KDC, register 200, performs the same function as the address register at the terminal. The RSA function.at the KDC, apparatus 210, performs the same function as the RSA function at the terminal, as previously described. The random number generator, apparatus 211, performs the same function as the random number generator at the terminal previously mentioned. The generator of the encryption and decryption keys apparatus 212 has the same function as described previously in the terminal. Apparatus 213 is a generator of the parameters used as inputs to the apparatus 75 described previously. For this particular example these parameters are the base and modulus for the Diffie-Hellman algorithm. It reguires as input the output of the random number generator, apparatus 211. The method of generation is described in the aforementioned paper by Diffie.
There is a semi-permanent storage at the KDC, registers 214 and 216, which shores verification . information Va and terminal-unique decryption key information Dak between calls. Semi-permanent registers 215 and 217 are used to store information during the call setup progress. These registers have the same functions as described previously for the terminal.
System Operation
The operation of the system will now be explained o beginning with FIG. 3. Initially the key management equipment in the terminal will be in the wait state until a request is received from the terminal controller processor to initiate a secure call. At this point, as discussed, there is stored in the terminal the terminal-unique encryption key that will be used to encrypt information that is sent to the KDC. Also stored is the verification information. These two pieces of information were stored
SUBSTITUTE SHEET
<img file="AU1109483A_D0008.tif" />
WO 83/04461
PCT/US83/00030 from the last call (or from the initial setup) that was made by this terminal. This in shown in FIG. 6 as Va and Eak.
Once a request is received to initiate a secure call, the address of the called party must be given to the key management equipment via the controller processor. This is seen in FIG. 3, box 31. At this point, there are generated new call-setup keys. This is shown in box 32 and in FIG. 7 as Eka and Dka. In box 33 there is shown the generation of partial session keys that will be used to encrypt data on the link from terminal B to terminal A. This is shown in FIG. 8 as Eba and Dba.
At this point, the verification information is updated using the keys that were just generated. The *’;· · · · · update function is specified as follows: .·;·· * · · «*» · ·
Vai' = f (Vai, El) and Va2' --= f (Va2, E2) *··’·’ *>····· • · where ' denotes updated and ValVa2 = Va. Va is the stored;···;· verification information and the E's are the just-generated encryption keys. The properties of f are as follows:
(1) for every V, El, E2: f(V, El) / f(V, E2) where
E1/E2; <*·*· (2) for every V21, V2, E: f(Vl, E) / f(V2, E) where .·*.·. V1/V2;
(3) given V and V' / f (V, E) it is difficult to J···;· determine E; and . ··· (4) in the case whe.e E is an asymmetric encryption key, D cannot be determined from Ε. J···;·
For this example, Va' = Val']Va2' where Va - Val|Va2, Vai·'··., is equal to Vai encrypted with Eka, and Va2' is equal to Va2 encrypted with Eba. This update process is depicted in FIG. 9. The first half of the verification information Vai is read from storage and provided as an input to algorithm. The key that is used to encrypt this information is the call-setup key, Eka, that was generated. This becomes Vai' and overwrites Vai
SUBSTITUTE SHEET the RSA
<img file="AU1109483A_D0009.tif" />
WO 83/04461
PCT/US83/00030
- 11 FIG. 10. Next, the second half of the verification information Va2 is encrypted using Eba just generated. The result Va2* overwrites Va2 in the storage register. This is shown in FIG. 3, box 34, and in summary, the updated verification information Va is the verification
<img file="AU1109483A_D0010.tif" />
• a* ·· · information stored from the previous call, or given to the terminal on the initial setup from the KDC, where half is encrypted using the encryption part o.f the partial session key generated on this call and the other half is encrypted 10 using the call-setup key for that call.
At this point, as shown in box 36, FIG. 3, and in
FIG. 11, the message can be formatted to the KDC. The contents of this message are the encryption parts of the two keys that were just generated. Both the partial session key to be established between terminal A and B,
Eba, and the new call-setup key Eka are encrypted using the terminal-unique encryption key Eak stored from the previous call from the KDC to the terminal or given to the terminal on the initial setup. At this point, the information that 20 can be destroyed from the terminal is the terminal-unique encryption key, Eak, stored at the terminal from the previous call, and both the call-setup encryption key, Eka, and the partial session encryption key, Eba, that were generated by the terminal. The encrypted message is then 25 appended to the address. A, of the originating terminal followed by the address, B, of the called terminal. This message is now sent to the KDC.
The terminal now will enter a wait state waiting for the information to be received from the KDC. This is depicted in box 37 of FIG. 3.
As shown in FIG. 5, the KDC will be in a wait state until a message is received from terminal A. This is shown in FIG. 5, box 50. Once the message is received, the
KDC reads the address information within the message into the address reqister which gives it the index of th?
decryption key that must be used to decrypt the message.
The KDC has in its storage from the previous call the
SUBSTITUTE SHEET ~ WIPO
WO 83/04461
PCT/US83/00030 matchir.. verification information for each terminal and the terminal-unique decryption key for each terminal. This is depicted in FIG. 20, boxes 214 and 216.
The message from terminal A is decrypted using the terminal-unique decryption key corresponding to that terminal, Dak. The keys, both the new call setup key Eka and the partial session key Eba (to be distributed to terminal Bk< is temporarily stored in the KDC memory as depicted in FIG. 21.
At this point, as shown in FIG. 22, the KDC can update its verification information in the exac.t same manner as the terminal. This is done by encrypting each half of the stored verification information Va with the received session key information Eba and the received caxl-setup key information Eka, shown in FIG. 23. This .·;··.
produces the update verification information Va. ....
' . ♦ ·
The key distribution center, as shown in FIG. 24/*** will now generate a bidirectional asymmetric i*··;· encryption/decryption key pair, Eak’, Dak'. The primes ;···;· denote updated information. Eak' will be distributed to terminal A to be used on the next call setup to the key distribution center. The decryption key Dak’ overwrites · · · ® the decryption key Dak that was stored from the previous *. * I call. · * · ··
Two other pieces of information are also generated at this time. These are the parameters that v;SlTj* be used by the terminals to create symmetric session keys?;· in this case they are the parameters of the Diffie-Hellman algorithm. One is the base Y and the other is the Σ**·;· modulus Q as previously described. Functionally, the ····;· amount of information that is generated at the KDC and sent to each terminal may vary depending upon the precise algorithm. This information is stored in temporary storage and will be used as part of the message sent back to both terminal A and terminal B. This generation process, is depicted in FIG. 25 and refers to the flow chart box 55, FIG. 5. By this point, as shown in FI7. 26, the KDC must
<img file="AU1109483A_D0011.tif" />
WO 83/04461
PCT/US83/00030
- 13 have received a message from terminal B in order to complete the call to terminal A. If not, the KDC process for terminal A must wait until the process for terminal B has reached this point. This is so it can give terminal A the partial session key information Eab generated at terminal B and also to be able to give terminal B the partial session key Eba generated at terminal A. Coordination between the processes must take place so that the same parameters generated by one process overwrites the 10 parameters generated by the other process. This insures that the parameters sent to the terminals for the purpose of generating symmetric session keys are the same.
Once the internal exchange is made between the A registers and the B registers to coordinate the information 15 inside the key distribution center, the messages can now be formatted for the terminals. This is shown in FIG. 27.
The message to terminal A will consist of the new terminal-unique key information Eak' that will be used on a subsequent call to the KDC. It will also consist of the partial session key information Eab which it received from terminal B. It will also consist of the verification information Va or a known reduction of Va in terms of the number of bits. It will also consist of the base Y and the modulus Q of the Diffie-Hellman algorithm. These five pieces of information will be encrypted using the callsetup key Eka received in the message from terminal A. The KDC destroys Eka, Eba, Eak’, Y, and Q corresponding to terminal A and destroys Ekb, Eab, Ebk', Y, and Q corresponding to terminal B. The KDC will then send this output message back to terminal A. An analogous encrypted message is sent from the KDC to terminal B. At this point the KDC is finished with its processing.
FIG. 28 shows the configuration of the KDC after the call to terminal A has been dropped. The KDC has updated verification information Va and updated terminalunique decrypt key information Dak' which will be used on a subsequent call between terminal A and the KDC.
SUBSTITUTE SHEET
<img file="AU1109483A_D0012.tif" />
WO 83/04461
PCT/US83/00030 terminal has been
FIG. 3, for terminal stored at
Referring back to the flow chart,
A, the key management equipment at the in a wait state while the KDC has been functioning. FIG. 12 shows the key information the terminal during this wait state. It is the verification Va information and both decrypt keys Dka and Dba corresponding to the previously generated enwryption keys.
updated
FIG. 13 shows how the information received from the KDC is used in accordance with the box 38, FIG. 3. The the call-setup decryption key Dka is used to decrypt message received from the KDC. The five values discussed) sent from the KDC are now used in the way. The first piece of information is the new distribution key Eak’ that is stored in the semi-permanent register 71 and will be used on a following call made ftem this terminal to the KDC. It i& the updated terminal- , ···*·· unique encryption key. The second piece of information is* · the partial session key Eab which was generated at B and ;···** sent through the KDC to terminal A. The third piece of information is the updated verification information Ya, which can now be compared with the verification information stored at terminal A information are the algorithm, the base stores in temporary
Referring . The fourth and parameters to the Y and the modulus (previously following • · · · • · · · • · · © • 9 9
C ·· > · · »· 9 * · • · · 9 fifth pieces of
Di f f ie-Hellm?.n
Q, which terminal ·· · • a • · · storage. to FIG. 4, box 40, at this point the . terminal will compare the verification information it received from the KDC and either the verification information which is presently stored or some known reduction of that verification information this matches, then the process will continue this does not match, an alarm could be given terminal controller processor of a potential threat on a previous call.
Assuming a success of the compared
FIG. 14.
• · « ft 9 • e
If as normal. If to thr intruder verification, the terminal can now take down the channel to the KDC and
OMPI
SUBSTITUTE SHEET
WO 83/04461
PCT/US83/00030
- 15 establish a channel to terminal B, if not already established. At this point, terminal A and terminal B can communicate data securely using the asymmetric session keys Eab and Eba. If a symmetric session key is needed, the following steps can be taken. The calculation of the message to be sent to terminal B is shown in FIG. 15. First, the base Y and modulus Q of the Diffie-Hellman algorithm are used along with a random number Ra generated by the random number generator 72. These inputs are given 10 to the Diffie-Hellman algorithm 75 and the output is then an input to the RSA function 73. The random number Ra is also stored in temporary storage. Eab is used as the key to the RSA function 73. At this point the session key information Eab received from terminal B and the base number Y may be destroyed. The output of the RSA algorithm is sent to terminal B.
Terminal A’ key management equipment will now enter a wait state shown in FIG. 4, box 44, waiting for a message to be turned from terminal B. The idle state is 20 depicted in F1J. 16 and in storage is the decrypt session key Dab which terminal A generated, the modulus Q of the
Diffie-Hellman algorithm generated by the KDC and the random Ra number that was generated by terminal A.
As shown in FIG. 17, upon receipt of the message from terminal B, terminal A will decrypt the message using its decryption key Dba stored from the initial generation of the partial session key. Dba can now be destroyed. The output of this will be fed into the Diffie-Hellman algorithm as the base. The exponent will be the random number Ra wnich was priorly generated and the modulus Q is also input into the algorithm. The output of the DiffieHellman algorithm will be symmetric session key information which will equal the session key information that terminal B has calculated. Q and Ra can now be destroyed.
At this point, terminals A and B have established symmetric session key information between themselves that / OMPI is not derivable by the KDC. This key information may be
SUBSTITUTE SHEET
PCT/US83/00030
WO 83/04461
I;
used in a symmetric key algorithm like the Data Encryption
Standard (DES) to encrypt data. What is stored now in the, terminal until the next request for a secure session (or call), as shown in FIG. 18, is the updated verification information Va and the terminal-unique key Eak* which it‘ received jfrom the KDC to be used to encrypt the next» message to the KDC. ’!
It should be noted that the actual generation of the desired data at the terminal and at the KDC is operative under control of a computer processor and is programmed in accordance with the flow charts shown in FIGS. '3-5 to perform the sequence of data transfers detailed herein. Such a processor, while not shown, can any one of several well-known microprocessors, such as for .... example, the Intel 8086 microprocessor, working in ·*·* · ♦ · ft , conjunction with the terminal and KDC apparatus shown and · *··’ · · · · .detailed herein above. *....·
It should also be noted that one skilled in the • ft art could use different encryption algorithms and different· * * ft ft · · · · • ft equipments to achieve the same results disclosed herein without departing from the spirit and scope of our invention.
• ft ·· ' • . · ft ft ft ft • ft ft • · ft
<img file="AU1109483A_D0013.tif" />
<img file="AU1109483A_D0014.tif" />
SUBSTITUTE SHEET
<img file="AU1109483A_D0015.tif" />
PCT/US83/00'^0
WO 83/04461
- 17 >
<
Contents33
29 members in 12 offices
Priority claims1
| Document | Office | Kind | Date |
|---|---|---|---|
| 38680582 | United States of America | A |
Members29
| Document | Office | Kind | |
|---|---|---|---|
| WO8304461A1 | World Intellectual Property Organization (WIPO) | A1 | |
| AU1109483AThis record | Australia | A | |
| IL71095A0 | Israel | A0 | |
| IL71095D0 | Israel | D0 | |
| JPS59501037A | Japan | A | |
| EP0111489A1 | European Patent Office (EPO) | A1 | |
| WO8403434A1 | World Intellectual Property Organization (WIPO) | A1 | |
| AU1376083A | Australia | A | |
| ZA841577B | South Africa | B | |
| KR840008295A | Republic of Korea | A | |
| EP0137774A1 | European Patent Office (EPO) | A1 | |
| JPS60500844A | Japan | A | |
| AU546156B2 | Australia | B2 | |
| IT8467201A1 | Italy | A1 | |
| CA1197588A | Canada | A | |
| US4563182A | United States of America | A | |
| US4578531A | United States of America | A | |
| EP0111489B1 | European Patent Office (EPO) | B1 | |
| DE3366798D1 | Germany | D1 | |
| IL71095A | Israel | A | |
| CA1233716A | Canada | A | |
| EP0137774B1 | European Patent Office (EPO) | B1 | |
| AT37483T | Austria | T | |
| ATE37483T1 | Austria | T1 | |
| DE3378103D1 | Germany | D1 | |
| IT1196687B | Italy | B | |
| IT1196687B | Italy | B | |
| IT8467201A0 | Italy | A0 | |
| JPH0448009B2 | Japan | B2 |
1 legal event, as the office reported them to INPADOC
Events
| Event | Code | |
|---|---|---|
| Patent ceased section 143(a) (annual fees not paid) or expiredExpiredMK14 | MK14 |
Numbers
- Application
- 1109483
Titles
- English
- ENCRYPTION SYSTEM KEY DISTRIBUTION METHOD AND APPARATUS
Classification
- CPC, 6
- H04L9/0841
- A61F7/12
- A61M31/00
- H04L9/083
- A61F2007/0028
- A61F2007/009
- IPC, 10
- H04K1 00
- A61F
- A61F5 00
- A61F7 00
- A61F7 02
- A61F7 12
- A61J
- H04L9 06
- H04L9 08
- H04L9 14