Root key compromise recovery

Description: TECHNICAL FIELD [Detailed description of the invention]

Recovery when the root key is in jeopardy Background technology The present invention relates to common cryptography, especially the root key. Regarding recovery in case. Regarding cryptography, various algorithms called public key algorithms Has been developed. This algorithm is very useful for signing and authenticating electronic documents. It will be an effective means. Public key algorithms generally contain two keys called a public key and a private key. It is a thing. The private key is kept secret by the certifying authority It is being tubed. Public keys, on the other hand, are distributed to the public, as the name implies. Public key If you have, you can use it to encrypt your data, but this encryption Only the person who has the private key can decipher the converted data. Similarly, have a private key Encrypted data that can be decrypted only by those who have the public key using this Can also be created. Thus, both keys are for document encryption. An effective means, encrypted documents are not designated as the destination of the document. Can't read. If the private key is used for encryption, the result will be digitally signed. I may call it. The digital signature can only be created by someone who has the private key. It has a unique feature that can be done. Therefore, even if the private key is kept secret, Those who receive a document with a digital signature can verify the digital signature. , You can check the source of this document. Digital signature verification uses public key A data string was generated from the digital signature, and this data string was attached to the signature. It's done in a simple way, comparing it to a document. Document with the data string attached If the recipient is the same as the statement that this document is exactly signed by the certification authority It is a book and you can be confident that the contents of this signed document are reliable. Of course, in the above content, the private key is actually kept secret and only the certification body It is true only as long as it is a well-known fact that we know. secret As soon as you lose confidence that your key is confidential, you will receive a signed document However, this signature is not a signature by a person who has broken the trust of the private key, but a correct certification body. You will not be able to confirm that the signature is by. Widely reliable, higher than recognition agencies There is an authority (referred to as the central authority) For example, a certification authority that has lost the trust of the key chooses a new private key, which is covered by the guarantee of the central certification authority. You can distribute the attached alternative key. Those who received the replacement key are inside With the digital signature of the central certification body, the new public key corresponds to the new private key I can be sure that it is a thing. However, what if the trust of the central certification authority's private key is lost? I wonder. Also, if there is no widely trusted authority above the recognition body What to do Therefore, the public destroys the system because the alternative key is the correct key. Get an alternative key to ensure that it is not owned by the other person you are trying to The question of whether to distribute crabs effectively and efficiently is a very difficult problem to solve. Is. Disclosure of invention One embodiment of the present invention is a root key, which is a set of public and private keys. -This is a method to replace. The method of the present invention is a finger to replace the root key. Show, its replacement key, and the digital signature generated using the root key Procedures for electrically transmitting messages including, and outs that are not used for normal communication Issue the variable V derived from the message using the to-of-band channel It consists of the procedure to do. The keys that can be replaced are the first set of public and private keys mentioned. Is the public key of another public / private key pair that can be replaced with. The best form of the present invention has the following features. First of all, the method of this invention is The procedure for calculating the variable V by applying a one-way function to at least a part of the message Yes. In addition, the replacement key when generating the message and the replacement key for the message It has a procedure to concatenate with an identification name indicating that it is a delivery. message In the procedure to generate, the replacement key and (1) which root key to replace The serial number that identifies whether to perform the operation and (2) the expiration date of the replacement key The expiration date indicating the expiration date and (3) the expiration date when the replacement key becomes effective. Combine with the indicated validity period start date. Other embodiments of the present invention are also a set of public and private key private keys. This is a method to replace the root key. The method is the replacement key and root key. -Procedure to generate the first message, including instructions that it has been replaced, Lou The procedure for generating a digital signature from the first message using the key, the first message The procedure for combining a message and a digital signature to generate a second message, the second Using the out-of-band channel, the procedure for electrically sending the message of It consists of the procedure for issuing the variable V that can be obtained from the second message. Further, another embodiment of the present invention is a set of a public key and a private key of a private key. This is a method to respond to changes in the root key. The method is to replace the root key A message indicating that the message has been passed, using the replacement key and the root key. The procedure for electrically receiving a message containing the generated digital signature and the route. Steps to verify the digital signature of a message using the public key that corresponds to the key, and few Message by running the algorithm on a part of the message at least Obtain the variable V, which can be calculated from the data, using the out-of-channel. Generate variable B using an algorithm for the procedure and at least some part of the message And the procedure to compare B and V, and if B and V match, use the root key It consists of a procedure for replacing the corresponding public key with a replacement key. Also, other forms of the invention are times when the root key is in jeopardy. The news that the root key was in jeopardy and lost credibility An emergency message containing a digital signature generated using both the replacement key and the root key Match the procedure for sending the message electrically with the digital signature of the emergency message Procedures for using the public key of the root key that has lost trust due to, and few urgent messages Derived from an urgent message by running an algorithm at least in part V to get through the out-of-channel and urgent message The procedure to generate B by using the algorithm, the procedure to compare B and V, and B and V Consists of a procedure to replace the untrusted key with a replacement key if they match .. Also, other embodiments of the invention put the root key in jeopardy and trust. It is a device for recovery from a lost state. The device of the present invention is a digital professional An electric signal for emergency messages connected to a sesser and a digital processor Saves the communication interface received as and the public key corresponding to the root key Memory to keep and an input device to input V to the digital processor It consists of. Said V applies the algorithm to at least part of the urgent message Generated and obtained through the Out of Channel. The urgent message is Lou The key and confidence of the replacement, as well as showing that Tokey was in jeopardy and lost credibility. It contains a digital signature generated using an unreliable key. Digital process Sasser responds to root key to verify digital signature of emergency messages Apply the algorithm to the urgent message to generate B, using the public key Compare B and V, and if B and V match, replace the public key corresponding to the root key It is programmed to replace the key. Also, other embodiments of the present invention endanger the root key and lose credibility. Computer that records a computer program that recovers from a damaged state It is a readable recording medium. The recorded program is read by computer It has the following commands that can be taken. (1) Root key on the computer The key to replacement and the loss of trust, indicating that he was in jeopardy and lost trust Note the urgent message with the digital signature generated by the key Let the computer perform the process of pulling out from the computer, and (2) let the computer perform the emergency message digital. In order to verify the signature, use the public key corresponding to the root key, and (3) the above Have the computer apply the algorithm to the urgent message to generate B, (4 ) Have the computer compare B and V, (5) Have the computer equalize B and V If so, have the public key corresponding to the root key replaced with the replacement key. , The procedure. Recovery if the root key is at stake is a serious and unresolved issue. , Is a problem in public key cryptography. The present invention is for those who endanger the key. Includes more than 100 hexadecimal digits without risking being fooled The user can electrically press the key without the need to manually enter the entire key into the system. It has the advantage that it can be received by means. The present invention is a collation Using one-way functions to generate data, and outs already in use Only 15 to 20 by taking advantage of the presence of of-band channels You can safely replace the key simply by re-entering the number of hexadecimal digits in. Longer I The key can be received and registered by electrical means. To use out-of-band authentication methods in addition to urgent messages Therefore, the root key for authentication of the message and replacement is valid. You can get a strong conviction. According to the present invention, the root key is endangered by an intermediate entity (eg, a merchant). It is possible to notify that it has been done. Therefore, the merchant gives some electronic information with the customer. When sending, the public key of the central certification authority and the new one used for this communication You can attach an urgent message that includes a notification that it is a public key. This As such, central certification bodies rely on other entities to distribute emergency messages. Can be done. In addition, we are responsible for notifying all affected parties individually. You don't have to. Other advantages and features are the best forms and claims for carrying out the following inventions: It will be clarified by the description of the range of. A brief description of the drawing FIG. 1 is a diagram showing the format of an emergency message. Figure 2 shows the root key The execution process of the central certification body in the process of recovering from the endangered state It is a flowchart shown. Is Figure 3 endangering the root key? It is a flowchart which showed the execution process on the consumer side in the process of recovering from. Figure 4 shows a computer that provides recovery in the event that the root key is in jeopardy. -It is a block diagram of the system. The best mode for carrying out the invention Urgent message The present invention uses a commonly used in-band channel to replace new parts. An urgent message that contains a key and indicates that the key is no longer reliable And out-of-band different from in-band channels The other party uses the channel to check if the message is genuine. It consists of the procedure for issuing a verification code for. An in-band channel is a party It means a telecommunications path used between them to perform normal processing with each other. to this Is a computer phosphorus like the Internet, Wide Area Network (WAN) There are many other possibilities such as telephone lines, wireless communication, etc. Out of of A band channel is another communication path, in which a specific entity is another. Means a communication path that can communicate with an entity of. The out of -For channel communication, only one-way communication is performed from the central certification body. this is , Similar to the publication of newspapers. In this way, the Out of Band Channel What was received in this out-of-band communication was the central certification body. From a central certification body, not a message from someone else who pretends to be It has the characteristic of having high reliability regarding being a message of. FIG. 1 will be described. The urgent message 10 is the message identifier 12 and Serial number 14, replacement key 16, validity start date 18, validity period end It consists of an expiration date of 20 and a digital signature of 22. Message identifier 12 is a message Indicates that the message is an urgent message. Serial number 14 is optional , An identification code that identifies the root key at stake. Central certification body If you were using one or more private / public key pairs, you can identify this. You will need it. The key to be replaced 16 is the public key of the new public / private key pair, the previous one. As a replacement for the root key of the private / public key pair, which has lost trust. It was chosen. Data fields containing a validity period start date of 18 and a validity period end date of 20 are placed. Indicates the period during which the replaced key is valid. The validity period start date 18 is the central certification body As part of a program that keeps the system secure, public key-private key It is especially effective when you have a means to change a. Such a place If so, the central certification body will send an urgent message before the actual key change takes place. Do not change the key until the expiration date has passed by the key user. Is possible. And, of course, the expiration date of 20 is the expiration date of the key. Indicates the deadline. Because of this, the key user accidentally used the old emergency message. It won't happen. Finally, the digital signature attached to the message by the central certification body has lost credibility. Generated using the root key. Central certification body protocol FIG. 2 will be described. Central certification body believes root key trust has been lost If it is detected or if such a sign is detected, the central certification body will replace it with a new one. To select a public / private key pair and distribute the replacement key to users Create an urgent message (step 100). The above information, including the replacement key Create an emergency message by concatenating to generate a group of notification information. Furthermore, the above Create a digital signature for the set of notification information (step 102) and create the notification information. Create an emergency message with a digital signature attached to a group of reports (step 104) ). Central certification body uses lost credit root key to create digital signature .. The method of generating this signature can be any of several methods. Of which One method is simply a digital signature algorithm using the well-known root key. It is a method of adopting one of the rhythms. As another method, first of all, the above-mentioned method A group of intellectual information is expressed in a more compressed form using a one-way function, and the root key is further used. There is a method using a digital signature algorithm using. Of course, when using the latter method, the recipient of the emergency message authenticates it. The same one-way function must be used in the process. Therefore, the one-way function is Imagine a publicly available or well-known one-way function. Central certification body when a complete emergency message is generated with a digital signature attached Sends urgent messages to other users via in-band channel Send (step 106). In-band channels are generally business documents It is a communication path that is used for transmission and reception and is generally easy to use. The central certification body also generates and sends verification code V by this verification code. The recipient of the urgent message is sure that the urgent message is legitimate Melt. The verification code is an emergency message or part of an emergency message, while By generating a hash variable using a directed or one-way hash function Is generated (step 108). This one-way function generated a digital signature Or it may be the same as or different from the one-way function that is supposed to be generated. I. In either case, the central certification body has wide access to the one-way function f (x). I will do it. In reality, it is known that there is no perfect one-way function To. All functions that are currently considered one-way functions will eventually be Compu Calculate x1 from a given f (x1) using the capabilities or techniques of the data And would be quite possible. Therefore, the word one-way function knows f (x1). It doesn't have to be impossible to calculate x1 by, but it is very difficult to calculate It means that it is a function. In the aforementioned form, the hash function is the well-known SHA (Secure Hash). Algorithm). However, one-way functions have some standard hashes. It can be any of the functions (eg MD5, SHA, etc.). SHA and other articles As an explanation of the one-way hash function that was in question, one related to the cryptographic creation method See general literature. For example, Bruce Schneier Written by Applied Cryptography, John Wi Published by John Wiley & Sons, Inc. In addition, you can use some one-way functions or combine them. Needless to say, it is possible. In this technique, many one-way functions Known, but in general many are easy to calculate and therefore smart mosquitoes. It can also be equipped on the door. After generating Code-V for verification, the central certification body will call to ensure its authenticity. Issue de V. That is, by this method, the message is sent to the recipient. Guarantee that it is truly from a central certification body (step 110). Said person The law requires communication channels other than the channel that sent the emergency message. Including widespread distribution of V using (out of band channel) Get caught. Out of Band Channels by those who endanger the root key It is especially required that it is not hijacked or contaminated. Out of Band channels are well known (or computer applications) It was hard-coded in the monkey's report so that it could not be changed) To do. The key user using number 800 should call and match the hash variable. Can be done. Or a well-known and reliable publication, such as a national newspaper or magazine. It is published on a given page on a given day or period with variables for matching. Is done. The value generated by the key user by acting on the hash variable in the emergency message. Urgent mail by matching with hash variable V through the out of channel You can gain a high degree of confidence that the sage is legitimate. Why In order for the adversary to present a legitimate emergency message, out of channel You have to take over or collude with Le, but this is totally possible. Because there is no. The advantage of the above method is that emergency messages can be widely distributed. That is. Central certification bodies need replacement keys Many key users No need for immediate access to everything. In addition, the central certification body is urgent The first recipient of a message (eg a merchant or vendor) is another key user (eg a merchant or vendor) You can trust that you send an urgent message to your customer). for real , Merchants have an incentive to widely distribute emergency messages to customers. This is one Generally, the public key of a central certification body is exchanged in a commercial transaction between a customer and a merchant. This is because it is necessary to authenticate the information to be received. General user protocol FIG. 3 will be described. Is the key user sending an emergency message directly to the central certification authority? Receive by electrical means indirectly through or through other intermediaries (Step 2) 00). When you receive an urgent message and recognize that it is an urgent message, The user confirms the validity period start date and validity period end date included in the message. , Make sure the urgent message is up to date (step 202). Me If the sage is up to date, the user is part of the emergency message Digital Office Confirm the name (step 204). The user loses the reliability that he has been using so far The lost root key is used to perform the above processing by the public key algorithm. Central If the certification authority used multiple root keys, the serial number of the emergency message Examine the issue to see which of the multiple keys is appropriate. After confirming that the urgent message is up-to-date and legitimate, Au Obtain the matching variable V from a to-of-band source (step 206). Then use a one-way function on the appropriate part of the message or the entire message Generated variable B (step 208) and obtained it via the out-of-channel Compare V and B for matching (step 210). If B and V are equal, emergency mail The sage was sent by a central certification body and is the first route without approval -Provide confirmation that the key was not sent by the third party who obtained it. User For me, it's important to generate B and make sure it's a correct and valid value. It is important. Because with a lost key, the illicit executor takes control of the system. This is because a fraudster may send an urgent message. If the key user is certain that V and B are equal, then the old public key is urgently sent. Replace with the replacement key contained in the sage (step 212). This process If the test fails somewhere during execution, ignore the urgent message and source Continue to use the original public key that corresponds to the root key of. Naturally, V and B are one If it is confirmed not to do so, the root key has lost trust, but an urgent message Could be an attack on the system by someone who endangered the root key Very expensive. Signing an urgent message with an untrusted root key is, in fact, Clearly, it is an important step even if the tekey loses credibility. this Signatures serve as the front line of defense. It interrupts the normal operation of the system and is tense Issuing a rush message is guaranteed not to be possible for everyone There is. The signature is that the urgent message was issued only by one of the two publishers. It means that. That is, of a system with an authenticated root key A certification body or an entity that has endangered a certified root key Either. In this way, use emergency messages to destroy the system Greatly reduces the number of possible beings with. The procedure for handling urgent messages is on the user's computer on behalf of the user. It can be automatically executed by a device (for example, a PC computer) Is clear. FIG. 4 will be described. Computers are generally prog Communication link 40 with ramable digital processor 400 for emergency messages 3. Communication interface 402 (eg modem) to receive via telephone line, for example ). Further, the memory 404 including the main memory and the auxiliary memory, which is the user. Save the required public key and use the key that contains the emergency message processing program Pu It has a memory for storing the program. Processing program for the emergency message Is computer readable, such as computer disk 408 It shall be loaded from an external medium into the computer itself. Also out of -Input device 406 (for example, keyboard) for inputting the verification code extracted from the channel. It also has a display device (for example, a CRT display screen) that displays related information. The computer receives an emergency message via a communication link, which is an emergency message. It is programmed to recognize it as a sage. By this program The above-mentioned process is executed. Even if these processes are performed completely automatically, they are used. You may ask the user for management and input. In either case, the message is up to date First test of legitimacy (ie, with a key that the digital signature has lost trust It is natural to confirm that it has passed. So After that, the computer will enter the verification code to authenticate the new key. Notify. For example, in the dialog box on the screen, "In the New York Times. Please enter the number published on page x of Kajika Day "or A table such as "Call 800 and type the number read out" It may be indicated. In other words, the computer is a designated out-of-of -Input obtained by channel communication (that is, collation number or symbol string) To request. When the urgent message is confirmed by the verification code entered by the user, the compilation The user replaces the untrusted key in memory with a new replacement key. As an example, we used a PC, but there are many types of computer equipment, digiters. An electronic device that has a processor, such as a PDI, smart card, There are palmtop computers, more powerful workstations, etc. These are just a few examples. In addition, communication for transmitting information There are many possibilities in the medium. For example, telephone lines, cables, internet, guards Star communication, wireless communication, etc. In other words, the present invention is the type of device used. Rui is not limited in terms of the communication method adopted. .. And, of course, computer equipment executes the protocol. All the amount of memory required by the programs and data required for this, internal or external Have in one of. In addition, computer equipment includes other computer machines. Includes the equipment needed to communicate with the device (eg, a modem). In addition, There are many possibilities for communication media for transmitting information. For example, telephone line, ke Bull, Internet, satellite communication, wireless communication, etc. In other words, the present invention Regarding the type of device used or the communication method adopted It is not limited. Other examples are described in the claims below.