Cryptographic key distribution system

Description: TECHNICAL FIELD [Detailed description of the invention]

【0001】

[Industrial application field]

The present application relates to an encryption key distribution system in broadcast media such as satellite broadcasting or multicast on the Internet, and particularly to a method and system for minimizing the trouble for updating an encryption key by structuring the key in a tree structure. ..

【0002】

[Conventional technology]

In broadcasting media such as satellite broadcasting or multicast on the Internet, when authenticating users and encrypting data, the key must be distributed to the subscriber. When a new recipient joins, he can give him the key he is currently using, but when the recipient stops joining, he needs to update the data encryption key.

【0003】

For example, let S be a set of subscribers. S is assumed to be a viewer watching a particular pay program. Alternatively, it may be a set of employees waiting for confidential contact within the company, or a set of participants of a mailing list often used on the Internet may be S.

【0004】

Suppose S has n recipients. In Figure 1, Alice, Bob, and Carol are the elements of S. Publisher P encrypts content C and sends it out. In the Internet world, the IETF standards body has proposed RFC1421 as a draft standardization for mailing list encryption. It encrypts message M with a common session key K (K (M)), and then encrypts that K with n individual encryption keys D1 ... Dn (D1 (K), D2 (K)). ), ..., Dn (K)), which is sent out together with K (M) (see Fig. 2). The recipient decrypts the session key K with the corresponding decryption key (E1, E2, ..., En) and decrypts the message M with the resulting K. However, this method has a drawback that when the number of recipients n is large, the size of the key packet is much larger than that of the message. For example, if a 512-bit RSA key is used as the personal key, one Di (K) will be at least 64 bytes, and if n is 10,000, for example, a key packet of 640 KBytes must be sent per message.

【0005】

Figure 3 shows a case where a method (Join / Leave Model) in which a common session key K is distributed in advance using each recipient's personal key is considered. The personal key may be based on a general public key certificate or may be prepared for each application. The problem here is when there is a change in the set of recipients S. That is, when a new element is added to S, that is, when a new viewer joins, the user's identity can be authenticated using a personal key and K can be distributed, but the element of S is removed from S. In that case, it is difficult to update the key. For example, suppose Carol did not pay the viewing fee on the payment date and therefore tried to remove it from S. She has a K, so she can't keep using the same session key. Simply generate a new key K'and send it to the remaining n-1 recipients using their personal keys. In this case, if n is large, for example, if there are 100,000 viewers, 100,000 key distribution will occur every time one person leaves.

【0006】

Conventionally, the technology currently used for pay satellite communication is a secret algorithm method that is not compatible with each company's method, and since the ownership of the decoder is the ownership of the key, new viewers can be dynamically created. It cannot be joined or temporarily withdrawn. For example, the method used in pay-per-view relies on one-to-one communication by telephone for key delivery, and has problems such as requiring an uplink and not scaling.

【0007】

In addition, as a security for multicasting on the Internet, a method of distributing a group key from a router has been proposed. However, this method has a serious security problem that a reliable router must be installed in advance on the network. In addition, this method is security at the IP layer, and does not guarantee end-to-end security from the application.

【0008】

[Problems to be Solved by the Invention]

Therefore, an object to be solved by the present invention is to provide a method and a system for minimizing the trouble for updating the encryption key by structuring the encryption key into a tree structure. Yet another challenge is to provide cryptographic key distribution methods and systems that can publish standards to operate on known cryptographic techniques. Another issue is to provide an encryption key distribution method and system that can maintain the interoperability of each company, can dynamically join and leave the viewer without using an uplink, and can withdraw. Another issue is to provide an encryption key distribution method and system that can maintain the overall security no matter how many security problems there are during communication.

【0009】

[Means for solving problems]

In order to solve the above problem, first, a plurality of keys equal to or more than the number of recipients are generated, and the plurality of keys are arranged hierarchically in the form of a tree structure. Next, a plurality of recipients are associated with keys arranged hierarchically in the form of a tree structure, and individual encryption keys of the recipients are associated with the recipient in the tree structure from the root of the tree structure. Generated as a key string having a key leading to After the encryption key is generated in this way, the generated encryption key is distributed to the corresponding recipient. The tree structure has branches that are further derived from each branch that is derived from the root. In the method of the present invention, the number of branches derived from the method is not limited. That is, the number of branches derived from the root may be 2, and the number of branches derived from each branch may be 3. On the contrary, it may be constant like an n-advanced tree. In Figure 4 (in the case of a binary tree), K0 at the root of the tree is the session key. Content is encrypted with this session key. K0 is encrypted with K1 and K2, respectively, and delivered to the recipient. This is abbreviated as K1 (K0) and K2 (K0). Similarly, key K1 is encrypted and delivered with K3 and K4. The key distribution may be encrypted with each individual's public key. If it is secure, it is not necessary to encrypt it with each individual's public key and send it (for example, it may be handed over by a diskette). Further, as a distribution means, it may be distributed via the Internet or through satellite broadcasting. In addition, regardless of the essence of the present invention, it can be changed as appropriate. With this configuration, the time and effort required to update the encryption key can be minimized.

【0010】

BEST MODE FOR CARRYING OUT THE INVENTION

FIG. 6 shows a block diagram of the encryption key generation system of the present invention. First, block 610 generates more than one key, more than the number of recipients. Next, in block 620, multiple keys are arranged hierarchically in the form of a tree structure. Finally, in block 630, multiple recipients are associated with keys hierarchically arranged in a tree structure, and each recipient's encryption key corresponds to the recipient in the tree structure from the root of the tree structure. Generate as a key sequence with a key to the attached position.

【0011】

FIG. 7 shows a block diagram of the encryption key distribution system of the present invention. It is basically the same as the encryption key generation system, but first, block 710 generates multiple keys, which is more than the number of recipients. Next, in block 720, multiple keys are arranged hierarchically in the form of a tree structure. Next, in block 730, multiple recipients are associated with keys arranged hierarchically in the form of a tree structure, and each recipient's encryption key corresponds to the recipient in the tree structure from the root of the tree structure. Generate as a key sequence with a key to the attached position. Finally, in block 740, the generated encryption key is delivered to the corresponding recipient.

【0012】

[Example]

Hereinafter, examples of the present invention will be described with reference to the drawings. FIG. 8 shows an overview diagram showing an embodiment of the hardware configuration of the encryption key distribution system used in the present invention. In particular, it is a typical example of a system that distributes encryption keys via the Internet. System 100 includes a central processing unit (CPU) 1 and memory 4. The CPU 1 and the memory 4 are connected to the hard disk device 13 (or a storage medium drive device such as MO, CD-ROM23, or DVD) as an auxiliary storage device via the bus 2 via the IDE controller 25. Similarly, the CPU 1 and the memory 4 are connected to the hard disk device 30 (or a storage medium drive device such as MO28, CD-ROM23, DVD, etc.) as an auxiliary storage device via the bus 2 via the SCSI controller 27. The floppy disk device 20 is connected to the bus 2 via the floppy disk controller 19.

【0013】

A floppy disk is inserted into the floppy disk device 20, and the floppy disk or the like, the hard disk device 13 (or a storage medium such as MO, CD-ROM, or DVD), and the ROM 14 are used as a CPU or the like in cooperation with the operating system. The code or data of a computer program for giving instructions and carrying out the present invention can be recorded and executed by being loaded into memory 4. The code of this computer program can be compressed or divided into multiple pieces and recorded on multiple media.

【0014】

System 100 may further include user interface hardware, a pointing device (mouse, joystick, etc.) 7 or keyboard 6 for input, and a display 12 for presenting visual data to the user. .. It is also possible to connect a printer via the parallel port 16 and a modem via the serial port 15. This system 100 connects to a network (Internet) via a serial port 15 and a modem or a communication adapter 18 (Ethernet or Token Ring card), and transmits an encryption key or communicates with another computer or the like. Is possible. Further, a remote transmission / reception device can be connected to the serial port 15 or the parallel port 16 to transmit / receive data by infrared rays or radio waves (for example, transmission of an encryption key to a receiver).

【0015】

The speaker 23 receives the audio signal D / A (digital / analog conversion) converted by the audio controller 21 via the amplifier 22 and outputs it as audio. In addition, the audio controller 21 A / D (analog / digital) converts the audio information received from the microphone 24, and makes it possible to take the audio information outside the system into the system.

【0016】

As described above, the encryption key generation system and the encryption key distribution system of the present invention are various home appliances such as ordinary personal computers (PCs), workstations, notebook PCs, palm top PCs, network computers, and televisions with built-in computers. It can be easily understood that it can be carried out by a communication terminal having a communication function including a game machine having a communication function, a telephone, a fax, a mobile phone, a PHS, an electronic notebook, etc., or a combination thereof. However, these components are examples, and not all of them are essential components of the present invention.

【0017】

Figure 5 shows how to change the key. For example, suppose Alice pays a viewing fee and becomes a legitimate recipient. The server assigns key K7 to Alice, encrypts it with Alice's public key, and sends it. It also sends Alice a chain of keys that leads to the root session key, such as K3 encrypted with K7, that is, K7 (K3), then K3 (K1), K1 (K0). If the total number of recipients is n, then Alice's keychain is about the size of log (n). Here, consider the case where Carol withdraws from the set of viewers S for some reason. Carol has the keys K0, K1, K4 and K10 in her keychain. Therefore, in order to prevent Carol from accessing the content in the future, these keys must be reissued to invalidate Carol's key (the key with an X in Figure 5).

【0018】

Suppose K1 is reissued and becomes K1'. Then, Alice's K1 becomes invalid, so she needs to receive K3 (K1'), which is a new K1'encrypted with K3. Similarly, K0'needs to inform the recipient with two key distribution packets, K1'(K0') and K2 (K0'). This gives Alice the knowledge of K1'and K0', which in turn allows her to see the content encrypted with the new session key K0'. As described above, according to the hierarchical key structure of the present invention, when a withdrawal person comes out from a plurality of recipients, only the key related to the encryption key possessed by the withdrawal person is changed to correspond to the changed key. Since the changed encryption key can be encrypted with the key directly under the key and distributed only to the recipient, the time and effort for updating the encryption key can be minimized.

【0019】

Next, the key redelivery efficiency is as follows. For example, calculate the number of packets required to redistribute the key when Carol leaves. The key Carol had was log₂Since there are (n) keys, the number of newly generated keys is also log.₂(n) (Strictly speaking, log in the above method₂1 less than (n)). For each new key, the key must be encrypted with the keys of the two children and sent. Therefore, the number of key distribution packets required for key redelivery is 2 * log.₂(n). Generally, considering the case of r-advanced tree, the number p of key redelivery packets is p = r * log_r(n) = r * log (n) / log (r) Will be. When n is constant, r that minimizes p is r = e (e is the base of the natural logarithm), but since r is actually a natural number, r = 3 is optimal, and the number of packets. Is approximately 2.73 * log (n). Also, since the number of packets is theoretically the same in the case of r = 2 and in the case of r = 4, it would be practically advantageous to use the quaternary tree if the binary tree is used.

【0020】

For example, suppose n is broadcasting content to 1 million, or 1 million viewers. To remove one viewer, in the case of binary trees 2 * log₂(106), that is, 40 key redelivery packets may be broadcast. In the case of a cubic tree, 2.73 * log (106) = 37.7, so if DES is used as the key encryption method, one key can be sent with 64 bits + key ID, so the key ID is 32. In terms of bits, the payload of the key delivery packet is 96 bits (12 bytes), which is 38, and the total fits in 0.5 Kbytes.

【0021】

Next, the method of calculating a plurality of withdrawals at once is shown below. If k people withdraw at once, k * log_rThere is no need to generate (n) new keys. For example, K0 only needs to be updated once. Also, if it is known in advance that some people will leave at the same time (such as when watching with a contract by the end of the month), multiple viewers can be grouped into the same branch (group) as much as possible. Key renewal and redelivery in the event of a withdrawal can be reduced. That is, if a plurality of recipients are grouped in advance according to the attributes of the recipients, and the plurality of recipients are associated with the keys arranged hierarchically in the form of a tree structure according to the relationship between the groups, It is possible to generate and distribute keys very efficiently. In addition, as the attributes of the recipient, the contract years, subscription period, age, occupation, address, company, telephone number, and other personal information may be used. It can be changed as appropriate regardless of the essence of the present invention.

【0022】

[Effect of the invention]

According to the present invention, the standard can be published to operate on the known cryptographic technology, the interoperability of each company is maintained, and a specific viewer can be dynamically joined or withdrawn without using an uplink. It enables efficient distribution of encryption keys that can be performed. In addition, the overall security can be maintained no matter how many security problems there are during distribution.

【0023】

[Simple explanation of drawings]

[Figure 1]

It is a schematic diagram which broadcasts content by satellite broadcasting.

[Figure 2]

It is a figure which shows the outline of the standardization proposal of the encryption of the conventional mailing list.

[Fig. 3]

It gives an overview of the conventional Join / Leave Model.

[Fig. 4]

It is a figure which shows the example of the hierarchical structure of the key for the encryption key distribution of this invention.

[Fig. 5]

It is a figure which shows the example of changing the key by the withdrawal of a user of this invention.

[Fig. 6]

It is a block diagram of the encryption key generation system of this invention.

[Fig. 7]

It is a block diagram of the encryption key distribution system of this invention.

[Fig. 8]

It is a figure which shows one Example of the hardware composition of the encryption key distribution system of this invention.