Secure messaging systems

Description: TECHNICAL FIELD [Detailed description of the invention]

[Technical field of invention] The present invention relates to a highly secure communication system. [Previous technology and its problems] Communication networks to which a significant number of terminals, such as personal computers, are connected are well known. Such systems very often use insecure communication media, such as payphone systems, for passive jamming (eavesdropping) and active jamming (message interception and extraction, message partial modification, and). Susceptible to inserting false messages). It is known to use cryptography to overcome these problems. However, while the principles of cryptography are clear, there are fairly practical problems associated with designing a system with a significant number of terminals. The present invention, in more detail, relates to key management. In a system with several terminals, a basic choice must be made between making a more or less permanent connection between all terminals and making a connection only between the terminals that need the connection. In the former case, the control rights may be distributed, or a special control terminal, i.e. a key distribution center (Key distribution). It may be placed in the center (hereinafter referred to as KDC). In the latter, control must be placed in the key distribution center, so two unconnected terminals can have a secure medium through which they can make connections. Such a KDC system is known, and in this system, when one terminal (first terminal) wants to communicate securely with another terminal (second terminal), the first terminal is second to KDC. Request to set up a link with your device. The passage between the two terminals and the KDC is itself secure due to cryptographic protection under the key shared by each terminal and the KDC. Such a key can be called a control data key. This is because these keys are related to the control function of the communication between the terminal and the KDC and the transfer information (data) from the KDC to the terminal. "Data" is a key used by terminals when communicating with each other. In this known system, the terminal requires the KDC for a key called a session key that links with the other terminal each time it wants to talk to the other terminal. The advantage of this system is that each terminal only needs to maintain the keys needed for the current communication session with the other terminal. The KDC must provide a pair of session keys (one in each direction) to the two terminals for this link each time a link or session is requested. The two terminals communicate with each other during the session without further KDC intervention. [Purpose of Invention] An object of the present invention is to provide a communication system that performs key management with higher security than the above-mentioned prior art. [Outline of Invention] According to one embodiment of the invention, it consists of at least three terminals and a key distribution center (KDC), each of which is between a single terminal and the KDC when requested by the first terminal. Key information for communication between the first terminal and the second terminal specified by the first terminal under the encryption by the shared key transfer key. A communication system is provided. In this communication system, the key means thus given is used as a key transport key by the two terminals described above, exchanging the data transport key used by these two terminals to pass data. To do. Preferably, the key information is one of the keys that encrypts the message from the first terminal to the second terminal and the other of the key that encrypts the message from the second terminal to the first terminal. It consists of two keys. As a result, the link between the two terminals is virtually permanent. Once this is set, the KDC only has to update the key information, which only needs to be done occasionally. The keys used to transport data (user messages) between the two links have usage counters associated with them, and each terminal presses these keys when its usage reaches a given value. It has a means to update. The new key is transported between the two terminals by the key transport key. (The data transport key may be updated at different times for the two directions along the link, depending on the number of messages in each direction.) Therefore, the workload on the KDC is substantially reduced. Of course, key transport keys have a hierarchy, with higher hierarchy keys being used to transport lower hierarchy keys and lower hierarchy keys being used to transport data keys. You will understand. Therefore, the top key of the hierarchy transports the data key, but this transport hierarchy is done indirectly by using the lower keys. Preferably, the system also gives the KDC a message to terminate the link from one of the two terminals, the terminal sending the message erases the key associated with the link from itself, and the KDC sends the message to the other terminal. Send it to clear the key associated with that link from there. The present invention is also preferably updated with a usage counting means for counting the number of times each data transport key has been used and a means for updating such a key when the number of times of use reaches a predetermined value. It provides means for transporting the key to a terminal at the other end of the associated link. It is also desirable to use the same technique for key transport keys when using such a key hierarchy. The present invention also provides means for terminating the link with a terminal. This means is provided for each terminal with a means for erasing the key related to the link in the terminal, and when a request for link termination comes to the terminal, the erasing means in the terminal is activated and the link termination message is sent to the KDC. The KDC has the means to record the message and send the link termination message to another terminal on the link to activate the erasing means of that other terminal. The user may want to temporarily switch from one UA to another. This user will then want to temporarily use the new UA to read messages sent to the user's regular UA. Therefore, in the present invention, it is possible to preferably request the user from the terminal (UA1) to the KDC for a terminal change key (journey key) that specifies which other terminal (UA2) the user wants to use. I am trying to do it. Upon receiving this request, KDC issues a key for changing the terminal used to the user, sets the UA that the user is visiting in response to the key for changing the terminal used, and sets the key for changing the terminal used as the UA.₂It is sent to (encrypted), where it is stored in the key register for changing the terminal used together with the address code of UA1. The user also sets his own UA (UA1) to store all the received messages, encrypts them under the key for changing the terminal used, and sends them to UA2 for calling from UA2. respond. In UA2, the user decrypts his message using the key for changing the terminal to be used later. Failures occur from time to time in both systems. In the system of the present invention, the UA is not prepared to recover from a failure. This is because it creates a backup facility for cryptography and encryption keys, which compromises the security of the system. However, the KDC is ready to recover from the failure. This is because the KDC is in a safer environment and it is easier to take safety measures to minimize the safety risks of having such a backup. According to the present invention, the KDC preferably keeps a record of all the messages it sends and receives, in the order in which they acted, and the state of the KDC is periodically stored as a backup. If the KDC fails, the KDC is first backed up to a pre-stored state, and a record of all messages that have occurred since the previous state was replayed and given to the KDC. Also, since all messages related to key generation and transmission are repeated, a new key is sent to each UA to replace the previously sent but lost KDC. This puts the KDC in its correct current state and the system as a whole in a consistent state. The system cannot be completely recovered just by playing the stored message. This is because the key that occurred after the system backup state was stored is lost. Therefore, during playback of the recording, all messages related to key generation and transmission are repeated, replacing the key that was sent earlier by sending a new key to the UA but lost by the KDC. Changing the key can result in the loss of some messages, which can be handled by the equipment that handles the lost messages. [Examples of the invention] The communication system according to the embodiment of the present invention will be described with reference to the drawings. The explanation will be divided into the following parts. General configuration of the system General system behavior-key hierarchy Message structure and UA structure Chain between UA and KDC Calls between each UA System message error recovery Local message storage UA changes Recording KDC messages It should be noted that other features of the invention are described and claimed in the two co-pending patent applications filed at the same time as the present application. General configuration of the system With reference to FIG. 1, the system consists of multiple terminals 10, 10A, 10B, etc., all connected to a common communication medium 11, and a KDC 12 responsible for key control and distribution. .. There is also a non-electronic physical key distribution path 13, which allows the keys to be distributed from the KDC 12 to the terminal 10. Each terminal 10 is composed of a conventional terminal device such as the personal computer PC 14 and the disk memory 15 shown in the figure, and a security module 16 which is various encryption keys. Since the KDC 12 consists of a safety module 17, a computing unit 18, and a plurality of storage means 19, the risk of data loss can be ignored. Safety modules 16 and 17 are protected against external interference, as shown by the double box. The safety module 16 is also shown to have a bidirectional data path to the PC 14 with signals supplied by the control line from the PC 14 for control purposes. This latter route is used to transmit the data from the PC 14 to the security module 16 for encryption, and to transmit the encryption of the data from the other module to the PC 14 after being explained in the security module 16. This route is also used to transfer data from PC14 and back to the same PC14 for locally secured (ie encrypted) files in the terminal and to decrypt when the data is accessed again. .. The safety module 16 is also shown to be directly connected to the communication medium 11. In practice, some form of interface with the communication medium 11 is required. This can also be done with safety module 16, but in practice it is convenient to do this with PC14. Of course, the part of the PC related to this is logically different from the part that exchanges unencrypted data with the security module. (Also, of course, the PC communicates directly with the normal medium 11 to send and receive unsafe messages.) Safety modules 16 and 17 are constructed using known techniques. Therefore, each module is like a data storage means that stores encryption keys and other information that must be kept secret, quantity calculations for data encryption, decryption and checking, and other processing required within the module. It is provided with processing means for performing various operations and control means for controlling necessary operations. Each module is also equipped with batteries so that safety information such as keys is not lost in the unlikely event of a temporary local power outage. The module also detects physical attacks on the module, and in the event of such an attack, all information stored in the module is useful from the module when the enemy opens the module and connects it to a personal component. It provides a means of destroying stored information, such as keys, by overwriting random data to counterattack the possibility of trying to extract the information. Many of the module's components, such as various registers, counters, and storage devices described below, preferably define or provide functionality for the microprocessor, RAM, and the memory location used for these components. It is realized by the storage program. (However, it is convenient to configure some components, such as random number generators and encryption / decryption units, with special purpose hardware for a variety of reasons.) Programs are at least partially PROM or similar. Since it is stored in the thing, at least a part of the program cannot be changed once it is written. Therefore, the program cannot modify the storage key or other safety information so that it can be read from the module. It is assumed that the system is open to attacks from outsiders 20 attempting to eavesdrop on communication medium 11. Such an outsider 20 intercepts the message, intercepts the message, retrieves it, modifies the real message, and attempts to insert a fake message. The communication medium 11 is dispersed and is not under the independent control of any user such as the terminal 10 or 10A. For example, the communication medium 11 may include a part of a public telephone system such as a telephone network or a packet switching system with store and forward means. Therefore, the activity of outsider 20 is not inherently detectable. In addition to the possibility of such an attack by an outsider, the communication medium 11 loses the message, adds various delays to the message so that the order is changed, and duplicates the message (echo). It is considered to be inherently vulnerable to obstacles such as media. In addition to the potential for interception and physical attacks on the safety module described above, outsiders attempt to access the module and enter the system while a legitimate user is away. Various techniques can be used to combat this. The security module can be configured to have password control so that a legitimate user can enter the password and the module will thus only respond to that password. A time lock can be used if the user knows the length of his absence. The internal battery of the module ensures that the time lock operates continuously. A password can also be generated by the module and sent to a floppy disk that can be physically removed and retained by a legitimate user. Of course, slightly different protection technologies can be used for the user terminal safety module and the KDC safety module. This is because the KDC seems to be less vulnerable to an attack than the user terminal, but on the other hand, if the attack on the KDC is successful, the damage will be much greater than that of the user terminal. General system behavior-key hierarchy The operation of this system is controlled by KDC12 at two levels. First, each UA is assigned a unique User Master Key (UMK) by the KDC. This UMK is taken into the UA along the non-electronic key distribution path 13. For example, it is installed in the UA (in safety module 16) by a member of the staff who operates the KDC. This key is then used to establish and confirm the message between the UA and the KDC. Second, if a UA wants to talk to another UA, it must use the KDC to set up a secure channel between the two UAs. The UA requesting the link notifies the KDC and the KDC sets the link accordingly, but then rarely participates in the use of the link (when the LMK needs an update). There is also a third level of system operation, which concerns the secure storage of information in a single UA. This behavior has nothing to do with KDC. Table 1 shows the physical location of the keys, their hierarchy, and the abbreviations used. Each message is encrypted with a separate message key generated just for that message, no matter what level of hierarchy is associated with that message, so the message key should be hierarchical. Is not shown. In fact, each message is encrypted using a pair of keys. One key, called the base key, is the key taken from the hierarchy and the other is the message key for the message.<img file="JP2730902B2_D0001.tif" /><img file="JP2730902B2_D0002.tif" /> If an outsider can accumulate enough messages encoded with the same key, he can extremely break the system and get the key back. So for this reason you change the key at appropriate time intervals, and therefore even if an outsider manages to get the key, as a result of such a key update, it will eventually be useless to him. To do. However, it is difficult to change these because UMKs are physically dispersed. Therefore, it uses a hierarchical system of keys, in which each key is repeatedly changed before the keys above it are changed hierarchically. The upper key can be used to convey information about changing the lower key. Therefore, the KDC will only be involved in key changes related to the physical transport of the key (new UMK) at relatively rare time intervals, and such updates will not be significantly annoying. Message structure and UA structure Various UAs and KDCs communicate with each other by messages. All of these messages have almost the same structure, but there are changes, as shown below. One of the basic classifications of messages is to divide them into system messages and user messages. The former is generated by the system and operated by the system without the user's knowledge, while the latter is generated in response to the user and contains data assembled by the user. System messages are generally fairly short and come in several different formats. User messages vary greatly in length, but are effectively in only one form. As you can see, several system messages can sometimes be combined into a single packet. First, the message between the UA and the KDC, especially such the first, about the general structure of the message, and the hardware needed to generate it in the first UA and to respond to similar messages received by the UA. I will explain it here with reference to the message of. Other system messages are treated in much the same way, but there are minor differences, for example, at the relevant key level. The system starts when the UMK (user master key) is distributed and installed in all UAs (user equipment), but there are no other keys and no communication key. With reference to FIG. 2, it has various elements to be explained, and the general control function for these elements is performed by the control circuit 30. The UMK to the UA is physically transported by the key transport unit 31, which is temporarily connected to the UA's safety module 16 to move the UMK to the UMK register 32. The usage counter 40 holds a count of the number of times the UMK has been used in association with the UMK register 32. This counter, like all other usage counters, increments each time a key is used, is initially set to 0 (when the system first boots), and the associated key is updated (ie new). Set to 0 for each (replaced by key). UMKs are relatively permanent, but can be updated after full use by physically transporting new UMKs from the KDC. Therefore, a UMK key number register 40A is provided, which is initially set to 0 and increments each time a new UMK is installed. (Instead, the UMK key number register 40A can be set from the key transport unit 31 each time a new UMK is installed and the KDC generates a new value.) As soon as the UMK is installed in the UA, a control data key CDK is generated and stored in the UA's CDK register 34. The associated usage counter 33 and CDK key number register 33A are also set here. The key is generated from the random signal generator 36. Random signal generators utilize random signal sources such as thermal noise generators or radioactive decay counters to ensure that the keys are random. CDK thus generated, appropriate system message by di, is immediately sent to the KDC. In practice, such a random signal generator generates bits at a relatively slow rate and therefore has a register (not shown) for the next key (typically 64-bit). .. This register replenishment begins as soon as its contents are retrieved for a new key, so the next random key is immediately available. This random signal generator therefore has a plaintext (ie, unencrypted) key and is therefore housed in a security module. Considering the message in more detail, the UA has a message assembly register with several partitions, where the message (including the current one) is assembled. The MB area of message assembly register 37 is the message body or data part, and is used to store the "meaning" or "data" (if any) of the message. The message assembly register 37 has two parts on the far left, the source partition SC and the destination partition DN. The source partition SC stores the invariant source code that represents this UA, and the destination partition contains the code that indicates the destination required to send to it. The next partition MT is the message type area described below. The next partition KN is the key number and message identifier partition described below. The next partition is the MK partition, which is used to hold the message key MK for the message. Next to the MB partition is the Message Authentication code. It is followed by a Code) partition MAC, preceded by a PMAC (formerly MAC) partition, which may be ignored for the time being (or considered to be clogged with zeros). The message type format storage area 38 holds a set of message type formats for system messages, such as a message to the KDC that a CDK is being sent, from which the appropriate message type is selected. Is sent to the message body partition MB in register 37. For system messages to the KDC, this storage also holds the KDC destination code. Of course, for messages (users or systems) to other UAs, the destination code of the receiving UA must be generated. Since most of the communication with other UAs is started by the user, the destination code of the receiving UA is decided by the user. This code is used not only by user messages to that UA, but of course by system messages to that UA. Of course, you can use a traditional table lookup system that gets the destination code from the destination mnemonic. Further, the routing or addressing of the message through the communication medium 11 is usually processed by the interface unit 43 described below. As noted above, each message is encrypted with two keys: the base key and the message key that arise from the key hierarchy. The key number partition KN of the message assembly register 37 contains a combination key number for a message that identifies the basic key used for the message and also serves as a message number that uniquely identifies the message. This message number is obtained by concatenating the key number of the key down the hierarchy to the basic key and also concatenating the usage count of the basic key. Each key register has an associated key number storage, namely 40A for UMK for UMK register 32 and 33A for CDK for CDK register 34. Therefore, if the basic key is UMK, the contents of the UMK key number register 40A and the usage counter 40 are used, and if the basic key is CDK, the contents of the CMK key number register 40A, the CDK key number register 33A, and the usage counter 33 are used. To use. Each key number is incremented by 1 each time the associated key changes. Therefore, for a given message type, the message numbers are strictly in ascending order. This is because the key number of each key usually goes up, and when such a number goes down by being reset to 0, it is the result of an increase in the higher number. The branching of the relevant hierarchy and the distance down the hierarchy can be seen from the message type. For example, for the message type "CDK is being sent to KDC" considered here, the key hierarchy inevitably contains only UMK. It should be noted that the key number of a key is similar to the usage count of the key immediately above it in the hierarchy, but the two are not necessarily the same. This is because in some situations the higher key in the hierarchy can be used, so its usage count increases without changing the key directly below it in the hierarchy. To avoid such problems, keep the usage count and key number separate throughout the system. (This also means that the message numbers are not necessarily contiguous.) (This system relies to some extent on the content of the MT, which indicates the message type in clear text. This can, of course, be modified by including the content of the MT as part of what is encrypted. In this case, the message. The length of the identifier (ie, the key number), or its equivalent, the level of the key in the hierarchy must be indicated separately.) Generally, the body of each message is encrypted using the message's unique key, the message key MK. This message key is generated by the UA using the random signal generator RND36 and sent to the message key register MK39. It is assumed that the cryptosystem used is one that uses the same key for encryption and decryption, such as the DES / DEA standard or the like. (Although it is possible to use a system that uses different keys for encryption and decryption, such as a "public key" system, it stores both keys in the key pair and is also for encryption and decryption. The appropriate one must be used.) The encryption technology used is CBC (Cipher Block Chaining), which requires an initialization vector IV and an abbreviation key. (This is described, for example, in the operating mode of ANSI standard X3.106-1983 DEA.) The initialization vector IV is initially created by encrypting the message key MK under the base key. The message encryption key is then obtained by encrypting the IV again under the base key. Since the message key MK is sent in clear text and the receiver has a copy of the base key, the message encrypts the message key under the base key to get the initialization vector and gets the decryption key again. This allows decoding at the other end. The IV and decryption keys are then used to decrypt the message. Using a different MK for each message means that the messages will be encrypted under different keys even if they are repeated in much the same way (for example, the same user message will be sent a second time, probably only at different times). This means that outsiders cannot get much help from repetition in trying to break the code. Once the message is encrypted, the contents of the MT, KN, MK, PMAC, and MB parts of message assembly register 39 are sent to the message authentication code calculation unit 42, where the MAC value is calculated and this value is calculated. It is sent back to the MAC partition of message assembly register 37. In this way the MAC value is included as part of the message. MAC is calculated by an encryption-like process (MAC encryption) using CBC technology. The final block obtained from this process forms the MAC. "MAC encryption" is done using the key and the initialization vector (IV). The key ("MAC encryption key") is obtained as a fixed function of the base key used to encrypt the message, with IV being 0. Source code and destination code do not need to be authenticated. Because if either changes somehow, the unit that actually receives the message (UA or KDC) authenticates the message because it is not using a qualified key when trying to authenticate by MAC check. Because it cannot be done. The encryption / decryption unit 41 and the message authentication code calculation unit 42 must be inside the security module because the key must be received in clear text. Similarly, the UMK register 32 has the key in clear text, so it must also be inside the safety module. It is possible to store other keys outside the module, encrypt them under UMK, and decrypt them inside the module when needed, but it is much better to store all the keys in plaintext in registers inside the module. It is convenient for. The message assembly register 3.7 is, of course, also inside the module to ensure that the encrypted and authenticated message is not compromised. Each message sent and received passes through an interface unit 43 that performs the low-level protocol processing required to combine with the communication medium 11. In particular, interface unit 43 can be a mailbox dedicated to the transmission of encrypted messages, or two such mailboxes, one for system messages and one for user messages. it can. This allows yet another mailbox to be used for unencrypted messages, which are sent and received in clear text (eg, from terminals that do not form part of a secure communication system). As noted above, this interface unit is conveniently implemented by PC14 (Fig. 1). Considering the receiving circuit this time, the message assembly register 37 is used to receive the incoming message received from the communication medium 11 via the interface unit 43. The message number KN of this message is checked to check that the corresponding base key is available. The MAC of the message is then checked by the message authentication code generator unit 42 using the base key identified by the message identifier KN as the "MAC encryption" key. The resulting MAC is compared by the comparator 44 to the MAC (in the MAC partition) of the message. If the calculated value of MAC matches the MAC of the message, the message is judged to be genuine. If they do not match, the message is discarded because there is an error in either (possibly as a result of transmission noise) or it has been tampered with. Consistent with the modified message, as outsider 20 attempts to modify the message, but he cannot correct the MAC of the message protected by calculating with a key unknown to the outsider. You won't be able to change the MAC of the message you have to do. The message number KN of the message is then examined to check that the message was previously received but not a repeat. You can check if the message number is reasonable and related to the previously received message. (We will discuss in detail later how to prepare for lost messages, duplicate messages, and messages that are out of order.) If the message passes the KN and MAC tests, the message is decrypted (assuming the message body part MB is not empty). Therefore, the message key of the MK partition is encrypted using the encryption / decryption unit 41 under the base key (identified by the message number) to obtain IV, which is again encrypted under the base key. Get the decryption key. (The decryption IV and decryption key are the same as the encryption IV and encryption key.) The IV and decryption key are sent directly to the encryption / decryption unit 41 and used to decrypt the contents of the MB partition. (Some system messages, such as some approval messages, do not have a "body"; their MB interval is empty). So the content of the MB section is some kind of system message, which is processed by the control circuit 30. Assuming that this message is received from the KDC, the message may have a CDK key. If so, the received key is sent to CDK1 register 46 or CDK2 register 47. There is a pair of receive CDK registers because messages using the old CDK may be received even after the new CDK is received, even if the CDK of the KDC changes. There are two receive CDK number registers, which are also fed with the corresponding CDK numbers (again from the MB partition) so that the appropriate CDK can be identified when a CDK-encrypted message is received. It is dangerous to assume that it is never necessary to store more than one previous CDK, as the CDK can only be changed by sending a significant number of fixed messages that are encrypted under it. is not it. (If you need a discarded CDK, there will be something else fundamentally wrong.) Link between UA and KDC The system starts with UMKs (user master keys) installed in all UAs (user devices) but no other keys and no communication links. As soon as the UMK is installed in the UA, a link must be installed between the UA and the KDC. To begin this, generate a control data key CDK and store it in the UA's CDK register 34 and encrypt the system message under the UMK (using its unique message key MK in register 39). Configure and send to KDC. The KDC thus knows that the UA has installed the UMK and that the CDK has been installed at both ends of the link between the UA and the KDC, so that the CDK can be used for future communications from the UA to the KDC. The KDC sends an approval message back to the UA to acknowledge that it has received the CDK. In addition, the KDC generates its own CDK for this UA in the same way, encrypts it under the UMK, and sends it to the UA. The UA receives this message and decrypts it to get a CDK from the KDC. In this way, a link is installed between the UA and the KDC using a pair of CDKs, one in each direction. Both ends of the link use the CDK generated to encrypt future messages and the CDK received from the other end to decrypt future messages received from the other end of the link. This use of a pair of keys for two directions in which a message can be sent is also done in the case of a link between UAs. The approval that the KDC has received a message with a CDK from the UA does not have to be a separate separate message, but can instead be included as part of the message that the KDC sends the CDK to the UA. The message is now approved by the UA. Therefore, the exchange of CDKs is done with three messages. That is, the approval of the CDK from the UA to the KDC, the approval of the reception by the CDK from the KDC to the UA, and the approval from the UA to the KDC. Thus, the link between the UA and the KDC is bidirectional with a separate CDK in each direction. Once a link is set up between the UA and the KDC in this way, almost all future messages between the two units will use the CDK as the base key. When the use of the CDK exceeds a predetermined limit, a new CDK is created and transmitted under the encryption by the UMK as described above. Since the message flow between the UA and KDC is relatively low, this two-level (UMK and CDK) hierarchy is sufficient for a system that rarely requires UMK changes for the time being. .. In fact, the use of UMK also depends on some communication between UAs when a new LMK is needed, as will be seen below. The message between the UA and the KDC is generally only needed when a user (UA) wants to set up or break a link with another user (UA), which (sees the link as being virtually persistent). It happens rarely (because it has been done) and only when updating the LMK. In general, the number of messages (whether user or system) flowing in two directions along a link does not have to be the same. Therefore, subsequent individual updates of the new CDK will only update one of the linked CDKs. Such an update sends a new CDK in one direction and an approval message for it in the opposite direction. If desired, the KDC can be programmed to set up all the links needed when the system is first launched. To do this, store a significant number of system messages in each UA's key transport unit 31 (Figure 2). These system messages do not require encryption (because this message is shipped with the UMK and its security is as physical as the security of the UMK). If this were not done, these system messages would have to be sent between the KDC and each UA when the system was first put into operation. This significantly reduces the initial number of system messages about KDC. The structure of KDC is the same as that of UA, and is shown in the form of blocks in Fig. 3. A control unit 50 (corresponding to the UA control unit 30 shown in FIG. 2) and one message assembly processing circuit 51 are provided, and the message assembly processing circuit 51 has a message assembly register 52 (message assembly register). Corresponds to 37). The encryption / decryption unit, message authentication code calculation unit, and related circuits of the MAC comparator are considered here as part of the message assembly processing circuit 51 and are not shown separately. The KDC has a separate set of key registers and usage counters for each UA. Here, the key used by the KDC for sending (ie corresponding to registers 32, 34, and 39, and associated usage counters and key number registers), and the key used by the UA to send a message to the KDC (ie). Each collection of registers 46 and 47 and related registers 48 and 49) is shown in blocks 53, 54, 55, .... Blocks 53, 54, 55, ... Are multiplexed with respect to the message assembly processing circuit 51 by a multiplexer 60 controlled by the selector circuit 61. Depending on the contents of the selector circuit 61, blocks 53, 54, 55 ... Select the appropriate one from ... to get the key to process the incoming message and prepare the message to send. When the message is received in this way, the selector circuit 61 contains the contents of the SC partition of the message assembly register 52. This partition contains the source code of the incoming message, thus identifying which UA the message came from. If the response message must be sent back to the UA that sent the incoming message, the contents of the selector are unchanged so that the appropriate one of blocks 53, 54, 55 ... It remains selected for preparation. However, if the message must be sent to another UA, the contents of the selector circuit 61 must, of course, be changed accordingly. This happens, for example, during the installation of the link. The message requesting the establishment of a link from UA1 to KDC contains a code for UA2 in its MB partition, and this code must be forwarded to selector circuit 61 to send the appropriate message to UA2. It doesn't become. The two codes are used alternately by the selector circuit 61 in this case as messages are sent and received from them to and from UA1 and UA2. The appropriate one of them remains selected for the preparation of the response message. However, if the message must be sent to another UA, the contents of the selector circuit 61 must, of course, be changed accordingly. This happens, for example, during the installation of the link. The message requesting the establishment of a link from UA1 to KDC contains a code for UA2 in its MB partition, and this code must be forwarded to selector circuit 61 to send the appropriate message to UA2. It doesn't become. The two codes are used alternately by the selector circuit 61 in this case as messages are sent and received from them to and from UA1 and UA2. The appropriate one of them remains selected for the preparation of the response message. However, if the message must be sent to another UA, the contents of the selector circuit 61 must, of course, be changed accordingly. This happens, for example, during the installation of the link. The message requesting the establishment of a link from UA1 to KDC contains a code for UA2 in its MB partition, and this code must be forwarded to selector circuit 61 to send the appropriate message to UA2. It doesn't become. The two codes are used alternately by the selector circuit 61 in this case as messages are sent and received from them to and from UA1 and UA2. Communication between UAs A link must be set up between the UA pairs to be able to communicate. Each such link is set by the UA requesting the KDC to set a link between itself and another designated UA. The KDC does not exceed the limit on the number of links that any UA that will be included in a link can have with other UAs, and the UA at the "receive" end of the requested link is the link. If you do not refuse acceptance, set up the requested link. Once the links are assembled, the UAs at both ends are symmetrical in that they are in the same position. Both can be sent to others or the decision to break the link can be made. The process of setting a link is summarized in Table II A. In this table, the UA requesting the link is called UA1, and the UA with whom UA1 wants to have the link is called UA2. Table II A UA1 KDC: UA1 requests KDC to link with UA2. UA2 KDC: KDC sends send LMK and receive LMK to UA2. UA2 KDC: UA2 confirms reception. UA1 KDC: KDC sends the key to UA1. More specifically, when a user of UA1 wants to link with another UA, UA2, specified by the user of UA1, UA1 sends a system message to the KDC. This system message is encrypted using the UA1's CDK key, which is the key that UA1 uses for system messages to the KDC (excluding system messages related to CDK updates, of course). The message type indicates that UA1 is requesting to set up a link, and the message body contains the code for UA2. Upon receiving this message, the KDC creates a pair of random LMKs and sends the message to UA2. The message type of the message asks UA2 if it wants to accept a link with UA1, and the message body has UA1 and two LMK codes. All of these are encrypted using the CDK used to send messages from the KDC to the UA2 as the base key. When the UA2 receives this message, the user must make a decision whether to accept the link. If the link is accepted, the message will be sent from UA2 to KDC. This message indicates acceptance of the link and also contains the UA1 code (the UA1 code is included here to distinguish it from other UA-related configuration messages). This message is also encrypted using the CDK used to send the message from the UA2 to the KDC as the base key. When the KDC receives this message, it sends the message to UA1 to indicate acceptance of the link by UA2, and the UA2 code encrypted using the CDK used to send the message from KDC to UA1 as the base key. And incorporate two LMKs. As a result, the two UAs, UA1 and UA2, now share a set of LMKs that can be used to communicate directly with each other. There are certain situations in which a link cannot be established. As a practical matter, the UA has limited capacity to maintain such links. Therefore, if UA1 already has the maximum number of possible links, it will refuse to try to set other links. The user has the option to cut the remaining links and create capacity for the UA to accept the new links. Also, UA2 may already have the maximum number of links possible. It then returns a system message to KDC to indicate this, and KDC in turn sends a system message to UA1 to indicate that the requested link has been rejected. (If desired, UA2 can be configured to indicate to that user that UA1 is requesting a link, and that user will break the existing link to create capacity to accept the requested link with UA1. In addition, as noted above, if the UA2 has such capability, the user will be asked if it should accept the requested link, and if the user refuses, the UA2 will again. Send a system message to the KDC to indicate this. When such a system message is sent to the KDC, the KDC sends a corresponding message to the UA1 indicating what happened, and the user of the UA1 knows that the requested link has been rejected. (In a safety system, when a user's request is rejected, the reason for the rejection is usually not given.) Fig. 4 shows the configuration of the UA more roughly than that shown in Fig. 2. The message assembly processing circuit is shown in block 75 and includes a message assembly register 37, an encryption / decryption unit 41, and a message authentication code calculation unit 42. There are several blocks of key registers and related circuits. Block 70 contains the various key registers shown in Figure 2 and their associated counters, all related to communication with the KDC. Blocks 71, 72, ... have similar key registers and counters, but each block is associated with communication with a separate UA. Therefore, each of these blocks has a UA address code register (register 73) that identifies which UA is associated with that block. These registers contain the addresses of the other UAs when the user of the UA requests and is authorized to link to the other UA, and when the other UA requests and is authorized to link to the other UA. The code is put in. Blocks 70, 71, 72, ... Are selected by the multiplexer 74. For block 70 for KDC, the selection is directly controlled by the SC partition of message assembly register 37 or control circuit 30. In the case of other blocks, the selection is determined by comparing the address code in the SC partition of message assembly register 37 (corresponding to the incoming message) with the contents of various registers 73. In the case of selection of outgoing messages, the selection is determined by the user (actually, it is done indirectly using a table stored in PC14 that stores the user-defined UA identifier for that address code. ). Blocks 71, 72, ... do not contain UMK registers, and the UA, of course, has only one UMK for sending and receiving that is in block 70 and forms the highest level of all layers of the key. You will find that it exists. Each of these blocks has two transmit keys LMK and LDK, and two keys at each level of the receive key (in this case, LDK1 and LDK2). Low-level key LDKs change relatively rarely (for example, once every 50 messages), so it is unnecessary to save anything other than the current and previous versions, and high-level keys. Even if it is rare, it changes, so you have to save the current version as well as the previous version and deal with it when it changes. Once the link is set, user messages can be sent from UA1 to UA2 and vice versa. The link obviously has to be set up in response to a request from one UA, but once it's set up, it's symmetric. To send a user message, the process is almost the same as sending a system message. However, the message body partition MB in message assembly register 37 is only limited in length. The selector switch 76 is in the connection path from the MB partition of the message assembly register 37 to the encryption / decryption unit 41, and for the user message, the body of the message is a continuous 64-bit block. As a result, it is sent from the PC 14 to the encryption / decryption unit 41 instead of from the register part, and the encrypted message is sent back to the PC 14 block by block (PC 14 operates as the interface unit 43 in this respect). The MAC of the message is then calculated and sent to the MAC partition of message assembly register 37. The length of the message is indicated, for example, by the length value contained as part of the MT partition or as the first part of the message body. Since the message authentication code calculation unit 42 can be configured to act as a cipher at the same time, the contents on the left side of the MB partition in the message assembly register 37 are the message authentication code before the encryption of the message body starts. Give to compute unit 42, then block by block as the message body emerges from unit 41. This allows the last MAC to be available immediately after the last encryption block in the message body. However, since the MAC calculation involves the same process as the actual encryption, it is actually desirable to use the encryption / decryption unit 41 (hence the message authentication code calculation unit 42 is physically). It does not exist as a unit that is clearly separated from unit 41, but of course its logical function is clearly separated). Of course, in this case, the MAC cannot be calculated in parallel with the encryption and must be calculated after the encryption. When a user message is received, a special user message confirming receipt is automatically generated and returned to the source UA if requested by the sender. Such a request is indicated by the appropriate message type MT. Since the communication medium 11 is not sufficiently reliable, it is necessary to prepare for the possibility of message loss by the communication medium 11, the reversal of the order of the two messages, and the duplication of messages. These facilities are different for user messages and system messages. The equipment for user messages will be described here. Of course, the loss of a message cannot be detected until subsequent messages are received. These facilities mainly consist of two receive LDK registers LDK1 and a pair of bit registers (bitmaps) 77 and 78 associated with LDK2. Each block 71, 72, ... has its own set of these registers. The set for block 71 is shown in Figure 4A. The length of registers 77 and 78, expressed in bits, is equal to the count when the LDK key counter of the corresponding source UA is reset to zero. For each user message received, the bit corresponding to the source UA's LDK usage count (which is part of the message number KN) is set. If the bit corresponding to the received message is already set, it indicates that the message has already been received. Therefore, the version received this time is a duplicate and will be discarded by the system. If no user message is received, no system operation will normally occur. In fact, the system does not allow the lost user message to be identified because the message numbers are not necessarily contiguous. Therefore, an unset bit that is younger than the set bit may mean that the user message has not yet been received, but that the user message with that number does not exist. .. The system can modify the missing user message so that it can be identified when the next message is received. This can be done, for example, by giving the user message a strictly contiguous number along with the previously described message number, or by including the message number of the predecessor user message in each user message. However, even if this is done, it is desirable to leave the user with the right to decide what to do if it finds that the message has not been received. For example, the apparently lost message may not be gone, but simply delayed and still present in the middle of the system. The user can choose to either leave the situation as it is or later send his user message to another UA user requesting the resend of the lost message. Such a resend will occur as the transmission of an entirely new user message as far as the system is concerned. It is the sender's duty to include instructions that the new message is a repeat of the previously sent but lost message. As described above, when the user message is received, the confirmation message is sent. The confirmation message is automatically generated by the system as a special type of user message. Therefore, the UA may keep a record of such messages sent and this record may be configured to be updated when a confirmation of receipt is returned. To achieve this, for example, use a bitmap in which bits are set only for messages that indicate that the message type is auto-verification, or keep a record of the message numbers for such messages. You can do it. When this is done, the user can determine which of the user's user messages that need to be confirmed have not yet been confirmed and resend them as the user deems appropriate. Can be done. Mochiro. The lack of confirmation does not necessarily mean that the original message has not reached the intended destination. It may simply mean that the confirmation message for it has not reached the intended destination. Therefore, as a ritual issue and, as a good practice, it is desirable to indicate to the user that when a message is sent that is the correct repeat, it is a resend of the previous message. It will be appreciated that the initial setup of the link can be done by a sequence of various possible messages between the two UAs and KDCs. Two examples of such a sequence are shown in Tables II B and II C. Table II B UA1 KDC: UA1 requests KDC to link with UA2. UA2 KDC: Asks UA2 if KDC accepts the link with UA1. UA2 KDC: UA2 confirms and agrees. UA1 and UA2 KDC: KDC sends the receive key to UA1 and UA2. UA1 and UA2 KDC: UA1 and UA2 confirm reception. UA1 and UA2 KDC: KDC sends the send key to UA1 and UA2. Table II C UA1 KDC: UA1 requests KDC to link with UA2. UA1 and UA2 KDC: KDC sends the receive key to UA1 and UA2. UA1 and UA2 KDC: UA1 and UA2 confirm the reception, and UA2 accepts it. UA1 and UA2 KDC: KDC sends the send key to UA1 and UA2. These sequences are more complex than the sequences in Table II A in that, at some stage, two messages are sent from the KDC at the same time and the two messages are sent back to the KDC more or less at the same time. Also, since the sequence in Table II B consists of 6 stages instead of 4 stages, the sequence in Table II C is preferable to the sequence in Table II B. In these two sequences, the process will apoport at the third message stage if UA2 refuses to accept the proposed link. If this happens, UA2 sends a reject message to KDC as a third message, and KDC sends a "link reject" message to UA1 as a fourth and final message. Note that for the last two sequences, each UA receives its receive key before the other UA receives its send key. This means that the UA cannot send a message to another UA until it has the key needed to receive the message. For the sequence in Table II A, UA1 cannot send a message until UA2 receives the send key of UA1, but UA2 receives the send key and UA1 receives the send key of UA2 (as the receive key of UA1). Since it gets its send key before, UA2 can send a message to UA1 before UA1 has the necessary key to decrypt it. This situation can only occur when the link is first set up. Therefore, it is likely that the UA1 requesting the link will want to send a message first. However, it is possible that UA2 will try to send a message before UA1 receives the decryption key. As a result, the message will be rejected by UA1 who knows from the message number that it does not have the key needed to decrypt the message. One option here is simply to reject the message so that it is effectively lost. If the message is a system message, the action described below is taken. If it is a user message, this is processed as described above, and this transmission is probably left to the user's own resources to find out that the message is not received. Alternatively, the UA can be configured to store such messages and wait for the key to decrypt them. After the link is established, if you are confident that the user does not need to communicate with the UA at the other end of the link anymore, or if you want to install another link but this UA wants to accommodate the maximum number of links. This UA may want to terminate this link if it already has and therefore can only terminate the current link and make room for a new link. To achieve this, UA1 removes all information about the link from itself and sends a link termination system message to the KDC. The KDC records this and sends a system message to UA2 instructing it to remove all information about this link from UA2. The KDC records a link deletion as an error if the deletion is for a link that does not exist. (Such an "error" can occur naturally if both ends of the link request the end of the link at the same time, because the KDC before the other message reaches the KDC of the other message. Because it reaches and terminates the link.) System message error recovery As noted above, messages can be "lost" for a variety of reasons, and can be duplicated (either by the habit of communication medium 11 or by being intentionally reproduced by an outsider). There is. For user messages, we have described how to handle such situations. Let me explain how to handle such a situation with respect to system messages. In the case of system messages, it is imperative that nothing be lost and processed in the correct order. For each UA link (ie a persistent link with the KDC and each link with another UA), all system messages sent on that link (apart from just confirmation) are stored. These are removed from storage in two situations: That is, when confirmation messages for them are received, or when they become redundant. Each time a new system message is sent, a new packet is prepared and all system messages in storage are placed in this packet in the correct order with the new system message at the end of the packet. In this way, every time a new system message occurs, all unconfirmed and non-redundant old system messages are prepended to it, and all messages (that is, the old message plus this new message) are sent as packets. Therefore, the receiver receives a new combination of all unconfirmed system messages in the correct order each time a new system message occurs. Therefore, since all unconfirmed and non-redundant messages are arranged in the correct order before any message in the packet, the receiver inevitably processes the system messages in the correct order. Of course, the receiver may have received an earlier packet containing some of these system messages by that time, and that system message may have already been processed. The receiver keeps a record (by message number) of the last message processed for each link, so duplicate messages, especially all such messages in the packet just received. Ignore everything, including. As soon as a new packet arrives, the receiver begins responding to the messages contained in that packet. The confirmation message may be just a confirmation message that is nothing more than confirming the receipt of the message, or it may be a normal system message that carries some information. The latter is issued in response to an incoming system message, so implicitly check its predecessor message. System messages become redundant when their effect is canceled by a later one. For example, a message requesting that a link be set is canceled by a subsequent message requesting that the link be broken. Strictly speaking, duplicate messages are not completely ignored. If a duplicate message is detected, a mere confirmation is sent back to the sender, but no further processing is added to this message. This is because normal message confirmation may have been lost in the system. If the sender had previously received confirmation of the message, the message would not have been resent. So if the duplicate message confirmation is not sent, the sender will continue to send it repeatedly. However, if the sender receives a confirmation of the message, all messages with a message number greater than or equal to the message number of the confirmation message can be safely deleted from the retransmission storage device. This is because the message can be received, processed, and confirmed by the receiver only if all preceding messages have been properly received. This ensures that all system messages are processed in the correct order, and the automatic retransmission of each new message delays the last message by resending the earlier message. Is guaranteed to be absent. Another option is to resend the message. If a sufficiently long time has passed without generating a new message and receiving confirmation after sending the message packet, the packet of the current message stored in the storage device 95 is automatically retransmitted. By constructing such packets, the message is always sent in exactly the same form. However, the message is re-encrypted under the current base key. The entire package can be sent as a unit or as a single message. However, it is desirable to send it in a form that can be processed as the individual messages in it are decrypted. That way, if the message is interrupted or damaged, only part of it is lost and the receiver can stay halfway up to the latest state. This means that package authentication can happen here, but the packets are still protected from jamming and trick outsiders into responding to fake messages. It means that it must be designed so that it cannot be done. The packet format begins with the usual "header" information at the left end of the message assembly register (SC, DN, MT, KN, and MK partitions). The contents of the MT partition contain indicator bits that indicate that the message is a packet of two or more messages. The message number in the KN partition is the message number of the current message (this message is at the end of the packet). The first message in the packet is the stored message. Therefore, no source code or destination code is required for all stored messages contained in the packet, and no special MK is required. Therefore it is assembled as an abbreviated message from its message type (with an indicator bit if this is not the last in a series of stored messages), message number KN, and message body MB (if any). It is composed. It also has a PMAC partition, which is blank (for a single message). The MAC of the packet assembled in this way is calculated and put into the MAC partition. The next partition of the packet, in turn, takes in and assembles the next stored message, or the current message if all stored messages have already been put in. Therefore, the MAC that was just calculated for the message before the packet is put in the PMAC (previous MAC) part, this PMAC value is encrypted, and the new calculated for the message that is taken in the current part of the packet. Enter the field covered by the MAC. This process continues until the current message forms the final part of the packet. The MB partition of the current message does not include the MT partition and KN partition. Because these are already in the packet header. ) It is clear that this packet structure allows packets to be disassembled, decrypted, and processed message by message. Moreover, both individual messages and their sequences are authenticated by the MAC sequence strand. Each MAC checks the integrity of the message that precedes it, and each message has the MAC of the previous message in it, so any sequence changes (message reordering, deletion, or repetition) As soon as a message that deviates from the sequence arrives, the MAC will not pass the check. The receiver responds individually to the individual messages in the packet. However, none of the response messages (other than just confirmation messages) are sent immediately and are placed in message storage, and only when the incoming packets are completely processed are these response messages become single packets. Sent (along with old unconfirmed messages). (If this is not done, these responses will have to be iteratively sent out as a series of longer packets.) As mentioned above, the length of a packet is implied by connecting the messages in a chain and inserting a bit in the MT of each message to indicate whether there are any messages that follow. This, of course, allows the receiver to distinguish between the retransmitted message with the MT and KN in the MB body and the current message (the last message in the packet) with the MT and KN in the packet header. it can. An alternative technique is to put the packet length value (number of messages) in the header, for example as part of the MT or KN partition. This method of resending all unconfirmed system messages each time a new system message occurs results in very few unnecessary retransmissions. Retransmission can only be justified if the message was received correctly but the original UA has not yet received the confirmation, or if the confirmation is lost. Is. An alternative is to keep a record of the message number of the last message received by the recipient and resend the lost message if it is found that the new message does not have a message number in the paired order of that number. Is to send a request for. However, this technique requires the use of strictly contiguous message numbers, and causes the delay of two message transmissions (request and response) before the receiver can process the current message. If the "recovery" message gets lost, it will be even more delayed. It should also be noted that system messages are relatively short, so the cost of resending all unacknowledged messages in a single packet is unlikely to be expensive. This is in contrast to the case of user messages. This is because the length of the user message is very variable and can be very long. Since packets have a considerable and variable length (compared to a single user message), the packets are prepared for retransmission in roughly the same way as user messages, and contiguous blocks The messages sent to the encryption / decryption unit, encrypted and authenticated are stored in the PC 14 acting as the interface unit 43 as they are generated. The devices involved in these operations are shown in FIGS. 3, 4, and 5. The terminal (UA or KDC) has its own system message storage block for each link from that terminal. That is, there are blocks 85, 86, 87 ...... (Fig. 3) for links to all terminals UA1, UA2, UA3, ... in the KDC, and each UA terminal also has blocks 85, 86, 87 ... Has blocks 90, 91, 92, ... (Fig. 4) with respect to terminals UA-1, UA-II, ... that are linked to the link to KDC. These blocks are, of course, connected to the message assembly processing circuit 51 or 75 via a multiplexer 60 or 74. Figure 5 shows the main components of block 85. The other blocks are virtually the same. There is a storage device 95 that stores unconfirmed system messages, which behaves somewhat like a FIFO (first in, first out) storage device, but with non-destructive reads. System messages are sent from top to this storage 95 and steadily move down until they are deleted. The message number KN corresponding to the message in the storage device 95 is stored in the partition 96. Register 97 stores the message number PXKN of the last confirmed message, and if this changes, the message in storage 95 goes up to the message that has a message number in partition 96 that matches the message number PXKN. Will be deleted. When new system messages are being prepared, all old messages still in storage 95 are read upwards, i.e. the oldest ones first, non-destructively. The new message then enters the top of storage 95 (and all messages already in storage 95 are pushed down). In fact, there are two classes of system messages, depending on the level of the base key in the key hierarchy, which have different sequence message number KNs. Therefore, since the storage device 95 and the register 97 are duplicated, the messages of the two classes are stored separately, and the block 85 is composed of two compartments A and B for the two classes. All messages with higher base keys (ie, higher base keys) precede lower base key messages in the packet. This means that messages cannot be sent in exactly the same sequence as they originally occurred. However, the only effect is that some new keys may arrive slightly faster than they would otherwise. Block 85 also has a timer TMR98 used to measure the time elapsed since the system message was last sent, and is still confirmed when the time of this timer 98 exceeds a preset limit. Trigger a resend of a system message that is not. This timer 98 is reset to 0 each time a packet is sent. Blocks 90, 91, 92, ... of each UA are in a safety module to keep the list of messages waiting to be retransmitted safe from possible outsiders. However, in KDC, the corresponding blocks 85, 86, 87, ... are not in the safety module, but in the support storage for various reasons. Since the KDC has links to all UAs, the number of messages stored is likely to be much higher than that of the UA. Loss of stored messages (eg due to the failure of a compute unit computer) 18 means that the KDC has backup and restore procedures (as described below), and the KDC is less attacked by outsiders than the UA. As it seems, it is not as serious as the corresponding loss at the UA. This KDC information stored in assistive storage is protected against accidental or deliberate alterations by the local message storage techniques described below. Local message storage There are situations where it is desirable to be able to securely store messages in the UA. Therefore, the user may want to securely store the received user message either because he or she is not there when the user message is received or because he or she wants to keep the message. Users may also want to securely store materials such as their own user messages in the UA. The system provides both of these facilities. When the received message is stored in the UA, it is stored in the support storage device such as the disk memory 15 in the form when it is received, that is, in the undeciphered form. This means that even if an outsider can access the stored message, he / she cannot obtain more knowledge than he / she could obtain by intercepting the message on the communication medium 11, especially communication. It means that there is nothing to be gained by comparing the message as it appears on the medium 11 with the message stored in the support storage device. However, the user must, of course, be able to decrypt the message later on his own. Therefore, the message comes with an LDK that encrypts it. This LDK must be in its own encrypted form, as there is no situation in which the key can be allowed to exist in clear text outside the security module. So it is encrypted and stored under the LMK above it in the key hierarchy. That LMK also accompanies the message, again encrypted, encrypted under the LMK at the top of the hierarchy. Since the LMK itself is at the top of the hierarchy, it cannot be encrypted and cannot be stored in clear text as part of the message. Instead, add this identification number when the message is stored. It is important that the key should not appear in two different forms. Each key (apart from UMK) was received encrypted under the base key (the key above it) and the message key. The key is stored in clear text (ie, after being decrypted) in blocks 70, 71, 72, ... of the safety module. Each key is therefore stored in these blocks in encrypted form when it is received, along with the MK used for that encryption. Once the key is attached to the message, the stored encrypted form and associated MK are used to form the appendage. The UA is equipped with a UMK history storage device, UMKH105 (Fig. 4), which stores current and past UMKs along with their serial numbers (identification numbers). When a new UMK enters KDC block 70, it also enters UMKH history storage 105. To generate a series of attachments to a message, each level of key is now encrypted in the message assembly processing circuit 75 under its higher key, and finally the current UMK serial number. Taken from UMK key number register 40A (Figure 2) in block 70. (Since the capacity of the UMK history storage device 105 is finite, when it is full, the old UMK of the past is taken out from it, encrypted under the more recent UMK, and stored in the disk memory 15. .) To recover the stored messages, send the accessories one by one to the circuit in Figure 4. In this case, the first is the UMK serial number used to obtain the appropriate LMK from the UMK history storage 105, and the second appendix is the message assembly to decrypt under the UMK to obtain the LMK. It is sent to processing circuit 75, and the last appendage is also sent to message assembly processing circuit 75 to decrypt under this LMK to get the LDK, then the message itself is embedded in the LDK and the message. It is sent to the message assembly processing circuit 75 to decrypt it under the existing MK and obtain the body of the message. Virtually the same technique is used to securely store locally generated messages. The secure storage key block SSK 107 is similar to blocks 70, 71, 72, ... but has a set of key registers for the local key hierarchy PMK, PSMK, and PDK. .. (The secure storage key block 106 is shown smaller than a similar block because it has only the key corresponding to the "send" key. Obviously, there is no need to store the key corresponding to the "receive" key. ) To store the message, encrypt the message in the usual way with the message key KM and the current PDK. As a result, the message contains the PDK encrypted under PSMK, the PSMK encrypted under PMK, the PMK encrypted under the current UMK, and the serial number of the current UMK. Is added for. The message can be recovered by decrypting it in much the same way as it would for a message received from another UA and stored securely. The system also authenticates locally stored messages, whether received from other UAs or originated locally. The purpose of such authentication is to protect locally stored messages from interference by outsiders who, of course, are not safety modules 16 but can access storage devices such as PC 14 and disk memory 15 (Figure 1). It is to be. Such outsiders may delete the message, modify the message, or attempt to insert the message. A storage device such as a disk memory 15 (or an internal storage device of a PC 14) contains various messages 111 (FIG. 6) of various lengths and arranged at various locations throughout the storage device. (Of course, individual messages can be placed in a non-contiguous series of pages in the usual way without affecting the principles described here.) There is a directory 112 associated with these messages. This directory 112 lists the identification title of each message and the location of the message in disk memory 15 in partition 113. When the message enters the disk memory 15, the corresponding MAC is calculated by the message authentication code calculation unit 42 using the basic key in which the message itself is encrypted. This MAC is stored in partition 114 of directory 112 in association with the title and location of the message stored in partition 113. In addition, the entire list of MACs in directory 112 is treated as special messages, and global MACs or super MACs are calculated for these MACs. This global MAC is stored in the global MAC register 115 installed inside the safety module 16. If you want to check the individual integrity of the stored files listed in directory 112, calculate that MAC and compare it to the MAC stored in directory 112. Since these MACs are calculated using the encryption key, even if an outsider tries to modify the file, the correct MAC for the modified file cannot be created. Therefore, the MAC in directory 112 authenticates its individual files. If the entire set of files must be checked for integrity, the global MAC of the directory's MAC is calculated and stored in the global MAC register 115 by the MAC comparator 44 (Figure 2) in safety module 16. Compare with the global MAC. If an outsider changes something in directory 112, for example by deleting entries, reordering entries, or inserting entries, the global MAC will change. And since the global MAC is stored in safety module 16 and is inaccessible to outsiders, outsiders cannot change it, and the global MAC in the altered directory is in the global MAC register. It will not match the global MAC stored in 115. (Since all MACs are calculated using keys, outsiders cannot calculate the global MAC of modified files, but if they had access to the global MAC, they would have previously The entire file and global MAC can be exchanged depending on the version of). Of course, it will be understood that the MAC of each file can be stored as part of the stored file. In this case, the directory 112 is used to calculate the global MAC, and each MAC stored in the message is searched for. Also, if the directory 112 is large enough, it can be divided into partitions so that the partition MAC is calculated for each partition from the MAC of the message identified in that partition and the global MAC is calculated from the partition MAC. .. Partition MACs can be stored in clear text. In this case, these partition MACs can be modified by an outsider, but such partition MACs do not match well with the MAC calculated from the messages associated with that partition, or the global MAC is stored in the global MAC register 115. It will not match well with the global MAC that is being used. The directory 112 can of course be installed in the disk memory 15. Instead of storing the global MAC in the register of safety module 16, it can be stored outside of safety module 16. However, this runs the risk of not being able to replace all of the stored information without being detected by previous versions. If the user wants to change the stored message, for example by modifying the message, adding a new message, or deleting the message, the directory is calculated by calculating the MAC of the granted or added message. It must be stored in 112, or the MAC of messages deleted from directory 112 and the new global MAC must be calculated and stored in the global MAC register 115. It only calculates a new MAC (which is required for internal authentication of the message) and a new global MAC from the message MAC. The MAC of unaltered messages is immutable and no processing is required for these messages. UA changes A user may want to temporarily or permanently change a UA from his own UA, UA1, to another UA, UA2. If you want to change it temporarily, you want to be able to temporarily use the new UA to read messages directed to your regular UA. Also, if you want to change it permanently, users want to transfer everything from their old UA to the new UA. The treatment of these two cases is different. In the former case, the user requests the KDC to specify which other terminal he / she wants to use and a key for changing the terminal to be used (journey key). Upon receiving this, the KDC issues a key for changing the terminal used to the user, sets the UA that the user visits and responds to the key for changing the terminal used, and the key for changing the terminal used (UMK and CDK key hierarchy of UM2). (Encrypted under) is sent to UA2, where it is stored in the key register 107 for changing the terminal used together with the address code of UA1. The user also sets up his own UA to store all received messages and send them to UA2 to respond to calls from UA2. This message is transferred by UA1 decrypting the message, encrypting it again under the terminal change key (along with the usual random MK), and then sending the modified message to UA2. In UA2, the user uses his terminal change key to decrypt the message. Care must be taken when using this technique, as the same message may be encrypted and sent under different keys, and the travel key cannot be updated after a given use. In the latter case, the user's UMK must be physically transported to the UA2 and installed there. (In fact, all previous UMKs can be installed in the same way to forward securely stored messages.) Then establish a link with the KDC as described above and then with other UAs. Establish a link for. All keys already stored in UA2 will, of course, be destroyed before the new user's UMK is installed, and all keys in UA1 will be destroyed as well. All keys securely stored in UA1 are sent to UA2 unencrypted, that is, in the form of an encrypted message storage plus an appendix up to the UMK serial number, so new. It can be decrypted in UA2 under the installed UMK. Recording KDC messages In UA, there is no backup system for the keys, that is, for the contents of the safety module. This is because providing a key that can be used outside the safety module is a serious weakness. Failures that occur in the UA can only be recovered by restarting the UA. The KDC maintains a complete set of UMKs for each UA and can send and install the appropriate set through the key distribution path 13 so that all stored messages can be read safely. So the UA must be reconfigured to be able to read the stored messages safely. The UA must then reestablish the link with the KDC first and then with the other UAs it wants to connect to. (Many parts of this operation, as in the case of the initial configuration of the UA link, can be done by a set of stored messages transmitted from the KDC through the key distribution path 13.) All messages directed to it have been lost and cannot be retrieved. A user who has lost his message is responsible for deciding whether to resend the message when the failed UA recovers and the link is reestablished. The equipment that handles KDC failures is different. KDC keeps a record or log of all the messages it sends and receives, in the order in which it was processed. This log is retained in the support storage means 19. In addition, the state of the KDC is periodically stored in the storage means 19. In the event of a KDC failure, the operator must back up the KDC to its previously stored state, recovering from storage means 19. Next, the log of all messages generated after that time is played back to the KDC. This brings the KDC to its correct current state. However, all the keys that KDC generated and sent out during that time have been lost. Therefore, during log playback, the messages related to key generation and sending are repeated, so a new key is sent to the UA to replace the previously sent but lost in the KDC. In this way, the entire system is restored to a consistent state. [Effect of the invention] As described in detail above, according to the present invention, an extremely secure communication system can be obtained by adopting a hierarchical structure of keys.

[Simple explanation of drawings]

FIG. 1 is a diagram for explaining the overall configuration of an embodiment of the present invention, FIG. 2 is a diagram for explaining the configuration of a main part of the terminal in FIG. 1, and FIG. 3 is FIG. A diagram for explaining the configuration of the main part of the KDC inside, Fig. 4 is a diagram for explaining the configuration of other main parts of the terminal in Fig. 1, and Fig. 4A is a partial configuration of Fig. 4. FIG. 5 is a diagram for explaining the retransmission operation in the KDC in FIG. 3, and FIG. 6 is a diagram for explaining the configuration of other main parts of the terminal in FIG. 1. 10,10A, 10B: Terminal 11: Communication medium 12: KDC 13: Key distribution route 14,14A: PC 15,15A: Disk memory 16,16A,17: Safety module 18: Computational unit 19: Memories 20: Outsider 30: Control circuit 31: Key transport unit 32: UMK register 33,40: Use counter 33A: CDK key number register 34: CDK register 36: Random signal generator 37: Message assembly register 38: Message type format storage 39: MK register 40A: UMK key number register 41: Encryption / decryption unit 42: Message authentication code calculation unit 43: Interface unit 44: Comparator 46: CDK1 register 47: CDK2 register 48,49: CDK number register 50: Control unit 51: Message assembly processing circuit 52: Message assembly register 60: Multiplexer 61: Selector circuit 73: Register 74: Multiplexer 75: Message assembly processing circuit 76: Selector switch 77,78: Bit register 95: Storage device 97: Register 98: Timer 105: UMK history storage device 106: Safe storage key block 107: Key register for changing the terminal used 111: Message 112: Directory 115: Global MAC register