JP2001268070A - Key escrow method - Google Patents

Abstract

PROBLEM TO BE SOLVED: To provide a key escrow system that can prevent escape of escrow at a low cost, allow a criminal investigation agency to intercept communication quickly as required and prevent limitless interception. SOLUTION: A control station 2 decides a group configuration in response to a request from a terminal 5, prepares one idle terminal 8 with respect to one group, and stores it. A base station 3 allows group terminals including the idle terminal 8 to generate a group key by the BD method. When the criminal investigation agency 6 intercepts communication, the control station 2 rents the idle terminal 8 to the criminal investigation agency 6. When the interception permission period is finished, the control station 2 excludes the idle terminal 8 and delivers a new group key to the group memberships. Even when the group configuration is dynamically subject to change, the communication of the group in which the criminal investigation object terminal is included can surely be intercepted only for the permitted period.

Description

DETAILED DESCRIPTION OF THE INVENTION

[0001]

BACKGROUND OF THE INVENTION 1. Field of the Invention The present invention relates to a key escrow system, and more particularly, to a key escrow system in which an investigating organization intercepts group cryptographic communication using a dummy terminal.

[0002]

2. Description of the Related Art One of the conventional key escrow systems is a clipper chip system which has been used when the US government intercepts for criminal investigation purposes. This is called a first key escrow method. FIG. 2 shows a configuration of the clipper chip system. The phone conversation is encrypted using a tamper-resistant clipper chip that has been implemented in a telephone or the like in advance. The key information used for the encryption at that time is recorded in a kind of header called LEAF (Law Enforcement Access Field). The contents of LEAF are
80-bit session key Ks, 32-bit device i device unique key Kui, and 16-bit checksum Check total 1
This is key information consisting of 28 bits.

[0003] The device unique key of the clipper chip used by the user is divided and deposited in advance by two key depositing institutions 1 and 2. This key is kept secret, but if it is deemed necessary for law enforcement to break the code, the investigating authority obtains the permission of the court and gives the key depositary authority Delivery can be requested.

First, session key information is restored and extracted from the LEAF decoder using the key Kr. Next, at step, the investigating agency sends the retrieved device identifier Di to the two key storage agencies. , The key storage institutions 1 and 2 respectively send the Kui ¹ and Kui from Di.
Search for ² and find Kui ¹ and Kui ² respectively. , And send it to the investigating agency. Next, in step (i), Kui ¹ and Kui ² obtained from both organizations are combined to restore the session key Ks. This decrypts the intercepted ciphertext.

[0005] As a second conventional key escrow system,
There is an ID-based key distribution system using an ID-based encryption system. This method uses only the ID information (address, date of birth, e-mail address, etc.) of the communication partner and shares the encryption key without referring to the public file. As one of the methods, there is an "encryption key sharing method and an apparatus for the same" disclosed in JP-A-63-36634.
FIG. 3 shows a schematic configuration of this system.

First, the center generates an algorithm G for the center and keeps it secret. ID information of users A, B, C,... In the network is assumed to be y _A , y _B , y _C. The center uses the user's secret algorithms X _A , X _B , X
_{C a, X A = G (y A} ), X B = G (y B), as _{X C = G (y C)} , generated using an algorithm and ID information of the center. X _A is only A, X _B, as only the referred B, generates a secret algorithm for each user a dedicated and distributes to the appropriate users. After such preparation, the user inputs the ID information of the other party with whom the user wants to communicate to his / her own secret algorithm on the transmitting side to obtain a common key. Each user keeps a secret algorithm from the center secret.

[0007] The second key escrow system is an application of this ID-based encryption system. If the investigating institution accesses the center and creates a shared key to be intercepted, the eavesdropping becomes possible. In this ID-based key distribution system, all information of key generation is stored in the center, and any combination of encrypted communication shared keys can be synthesized.

On the other hand, there is the following technology relating to group communication. In a cryptographic communication system consisting of a plurality of mobile terminals capable of broadcasting from a base station, when performing group cryptographic communication between specific terminals, only the terminals constituting the group need to have the group cryptographic key set in advance. It must be delivered secretly. In a conventional cryptographic communication system, an individual encryption key is used to deliver a group encryption key,
From the beginning, the method of storing the group key in the terminal was adopted. However, such a method of distributing a group encryption key has a problem that it is difficult to update the group key when the group members are changed.

Several methods have been proposed to avoid such difficulties. A conventional group key distribution method for updating a group encryption key will be described below. As an encryption key sharing scheme for a group of three or more parties, there is a Burmester-Desmedt method (hereinafter referred to as a BD method) (M. Burmester, Y. Desme).
dt “A secure and efficient conference key distribu
tion system ”EUROCRYPT'94 May 1994.)

[0010] The base station transmits a prime number p and an integer α as public information.
(2 ≦ α ≦ p−1) is generated and made public. Each member M _{i of the} group (i = 1 to n; n is the number of members) generates a random number R _i and keeps it secret, calculates Z _i = α ^Ri mod p, and calculates the value of Z _i . To each member. Each member M _i is, on the basis of the _{Z i + 1, Z i-} 1 that has been _{sent, X i = (Z i +} 1 / Z i-1) Ri modp ( However, Z ₀ = Z _n,
Z _{n + 1} = Z ₁ ) and distribute the value of X _i to each member.

[0011] each member M _i is, as a common key _{K n, K n = Z i} -1 nRi · X i n-1 · X i + 1 (n-2) ··· X n (i-1) ·
X ₁ ^(i-2) ... X _i-2 modp = α ^{(Ri-1) nRi} · (Z _{i + 1} / Z _i-1 ) ^{Ri (n-1)} · (Z _{i + 2} /
Z _i ) ^{Ri + 1 (n-2)} ... (Z ₁ / Z _n-1 ) ^{Rn (i-1)} · (Z ₂ /
^{_{Z n) R1 (i-2}} ) ··· (Z i - 1 / Z i-3) Ri-2 modp = α ^ {(nR i R i-1) + (n-1) R i (R i ₊₁ -R _i-1 ) + (n
−2) R _{i + 1} (R _{i + 2} −R _i ) +... + (I−1) R _n (R ₁ −
R _n−1 ) + (i−2) R ₁ (R ₂ −R _n ) +... R _i−2 (R _i−1 −
R _i-3 )} modp = α ＾ {R _i-1 R _i + R _i R _{i + 1} + R _{i + 1} R _{i + 2} +... + R _n
Calculate the _{R 1 + R 1 R 2 +} ··· + R i-2 R i-1} modp = α ^ {R 1 R 2 + R 2 R 3 + ··· + R n R 1} modp, the common key K get _n .

Now, the group is defined as M ₁ ,..., M _i ,.
A method of obtaining a new key when the number of members is newly increased when the number of members is M _n is as follows. Member M trying to join the group
_{n + 1} generates a random number R _{n + 1} , calculates Zn _{+ 1} = α ^{Rn + 1} modp, and delivers Zn _{+ 1} .

The member M ₁ calculates X ₁ = (Z ₂ / Z _{n + 1} ) ^R1 modp and delivers X ₁ to each member. Member M _n
Calculates X _n = (Z _{n + 1} / Z _n-1 ) ^Rn modp and delivers X _n to each member. Member M
_{For n + 1} , X _{n + 1} = (Z ₁ / Z _n ) ^{Rn + 1} modp is calculated, and X _{n + 1} is delivered.

[0014] each member M _i is _{K n + 1 = Z i-} 1 (n + 1) Ri · X i n · X i + 1 (n-1) ··· X n + 1
^(i-1) · X ₁ ^(i-2) ··· X _i−2 modp = α ＾ {R ₁ R ₂ + R ₂ R ₃ +... + R _n R _{n + 1} + R _{n + 1} R ₁ }
Calculate modp to obtain the key Kn _{+ 1} .

When the number of members decreases, for example,
If M _{n + 1} departs from the state described when increasing,
When notifies each member that M _{n + 1} is missing, member M ₁ is use Z _n in place of Z _{n + 1,} to calculate the _{X 1 = (Z 2 / Z} n) R1 modp, X Deliver ₁ . Also, the member M _n is Z
Using Z ₁ instead of _{n + 1} , calculate X _n = (Z ₁ / Z _n-1 ) ^Rn modp and deliver X _n . Each member M _i is represented by K _n = Z _i−1 ^nRi · X _i ⁽ⁿ⁻¹⁾ · X _{i + 1} ⁽ⁿ⁻²⁾ ... X _n ^{(i−1)
_{· X 1 (i-2)}} ··· X i-2 modp = α ^ by calculating _{{R 1 R 2 + R 2} R 3 + ··· + R n R 1} modp obtain the common key K _n.

As described above, when the number of members increases or decreases, the members before and after the member to increase or decrease newly calculate Z using the Z of the members before and after, and distribute this to each member by broadcasting. I do.

[0017]

However, in the first conventional key escrow system, after obtaining permission, key information is taken out from LEAF, and two organizations are requested to combine the keys to take out the session key. There was a problem that it took time. Generally, it is limited to two hours or less in order to substantially effectively intercept, but it is difficult to satisfy the condition. In addition, there is a problem in that it is expensive because it depends on tamper-resistant hardware. In addition, there is a problem that by attaching a fake LEAF, eavesdropping can be avoided.

In the second conventional escrow system,
There was a problem that confidential information was concentrated in the center too, and strict management was required for confidentiality. Further, there is a problem that it is not known whether the key reproduced by the investigating agency for a period of interception is destroyed after the investigation is performed. That is, communications are intercepted by unrestricted investigative agencies,
Privacy may be violated.

The present invention solves the above-mentioned conventional problems, and in a key escrow system, it is possible to prevent a deposit from escaping at low cost, to enable quick interception when necessary, and to prevent unrestricted interception by a search agency. The purpose is to:

[0020]

Means for Solving the Problems To solve the above problems,
In the present invention, the management station, the control station, the base station, and the
Of a mobile cryptographic communication system
-Escrow management station manages group configuration information
Means to control the control station, and
To add dummy users to groups
And means for assigning dummy users to idle terminals
And instructions to instruct the terminal to generate a group key via the base station
Steps, means for storing idle terminals, and requests from law enforcement agencies
Means to provide idle terminals according to
After the elapse of the new group to eliminate idle terminals
Means for causing a terminal to generate a key,
Means to relay control of group communication and public information
Generate and publish a prime number p and an integer α (2 ≦ α ≦ p−1)
Each terminal M_i(i = 1 to n; n is the member
Number), a random number R_iMeans for generating and keeping secrets, Z_i
= Α^Ri means for calculating modp and delivering it to other terminals,
Z sent from the terminal of_{i + 1}And Z_i-1From X_i= (Z
_{i + 1}/ Z_i-1)^Ri modp (however, Z₀= Z_n, Z_{n + 1}=
Z₁Means for calculating and delivering to another terminal;_i-1 ^nRi
・ X_i ^n-1・ X_{i + 1} ^(n-2)... X_n ^(i-1)・ X ₁ ^(i-2)...
X_i-2 Calculate modp and use common key K_nMeans for obtaining
The configuration was adopted.

With this configuration, it is possible to prevent the escape from the deposit at low cost, and to prevent unrestricted interception by the investigating agency. The investigating agency can quickly and reliably intercept the communication of the group including the terminal to be searched, when necessary, no matter how the group configuration changes dynamically.

[0022]

Embodiments of the present invention will be described below in detail with reference to FIG.

(Embodiment) In an embodiment of the present invention, an idle terminal is assigned to each communication group and stored by a control station. When an investigating agency intercepts a communication, the idle terminal is permitted to use the idle terminal. It is a key escrow system that intercepts only for a certain period.

FIG. 1 is a functional block diagram of a key escrow system according to an embodiment of the present invention. In FIG. 1, a management station 1 is an organization that manages a subscriber database and billing information. The control station 2 is an organization that manages the groups and stores the entrusted encryption keys.
The management station 1 may be included in the control station 2. Base station 3
Is a radio station that supervises terminal communication. The wireless network 4 is a wireless communication path capable of broadcasting. Terminal 5
(T1 to T8) are a plurality of mobile radio stations forming a group. The investigation agency 6 is a public investigation organization such as the police. Court 7 is a court that issues a warrant for intercept permission.

The operation of the key escrow system according to the embodiment of the present invention configured as described above will be described. When each terminal forms a group and performs group communication,
The group communicates by sharing the group key. Even when the terminals communicate one-to-one, a group including two terminals is formed. That is, all terminal-to-terminal communication is group communication. It is possible for one terminal to join a plurality of groups.

As shown in FIG. 1, when the terminals T2, T3, T4 want to form a group, any one of the terminals forming the group (for example, the terminal 2) notifies the base station 3 of the group members. .

The control station 2 having received the request for group formation via the base station 3 makes an inquiry to the management station 1 and determines group members so that only allowed members form a group. For example, if a stolen terminal enters a member and forms a group, there is a risk that a third party could eavesdrop on it, and this is to prevent such a situation. When forming a group, the control station 2 puts a dummy user into the group and assigns the dummy user to the idle terminal Ti. That is, four terminals are assigned to the group formation request of the three terminals T2, T3, and T4 shown in FIG.
In order for terminals forming a group to share a group key, four group configuration terminal numbers are sent back to the base station 3.

The base station 3, based on a command from the control station 2,
The four terminals generate the group key KG1 of the group # 1. A group key is generated using a conventional BD method. Since the generated group key KG1 is also held in the idle terminal Ti, the control station 2 stores the idle terminal Ti, which means that the group key has been deposited.
In this way, the terminals T2, T3, and T4 form the group # 1 and perform group encryption communication. Group # 2
Similarly, when the terminals T5, T6, and T7 form the group 2, the control station 2 assigns the dummy user to the idle terminal Tj and generates the group encryption key KG2 for the four terminals T5, T6, T7, and Tj. Let it. When a plurality of groups are formed at the same time, one idle terminal is provided for each group. When the terminal generates the group key, the group key is also generated in the idle terminal without fail, so that the escape from the deposit can be prevented.

The investigating institution 6 uses the deposited group key.
The following describes the procedure for interception. The investigating agency 6 applies for permission to the court 7 when it becomes necessary to intercept the communication. If the application is legal, the court 7 issues an intercept permission warrant specifying the intercept permission period. The investigating agency 6 with the permission of the court 7 offers to intercept the communication of the investigation target terminal T4 of the control station 2 group # 1. If the control station 2 determines that the request is valid, it lends the terminal Ti to the investigating agency 6. The investigating agency 6 intercepts communication using the group encryption key as a member of the group # 1.

After the elapse of the intercept permission period, the control station 2 removes the idle terminal and forms a new group. Except for the idle terminal Ti, another idle terminal Tk is inserted and the terminal T
The base station 3 is instructed to form a new group # 1 with 2, T3, T4, and Tk. By performing the group communication with the new group key, unrestricted interception of the investigating agency 6 is prevented.

Next, a method for generating a group key in the terminal 5 according to an instruction from the base station 3 will be specifically described. Base station 3
Is a prime number p and an integer α (2 ≦ α ≦ p−1) as public information
Generate and publish.

Each member M _{i of the} group (i = 1 to n; n
Generates the random number R _i and keeps it secret, calculates Z _i = α ^Ri modp, and delivers the value of Z _i to each member. Each member M _i is, on the basis of the _{Z i + 1, Z i-} 1 that has been _{sent, X i = (Z i +} 1 / Z i-1) Ri modp ( However, Z ₀ = Z _n,
Z _{n + 1} = Z ₁ ) and distribute the value of X _i to each member.

[0033] each member M _i is, as a common key _{K n, K n = Z i} -1 nRi · X i n-1 · X i + 1 (n-2) ··· X n (i-1) ·
X ₁ ^(i-2) ... X _i-2 modp = α ^{(Ri-1) nRi} · (Z _{i + 1} / Z _i-1 ) ^{Ri (n-1)} · (Z _{i + 2} /
Z _i ) ^{Ri + 1 (n-2)} ... (Z ₁ / Z _n-1 ) ^{Rn (i-1)} · (Z ₂ /
^{_{Z n) R1 (i-2}} ) ··· (Z i-1 / Z i-3) Ri-2 modp = α ^ {(nR i R i-1) + (n-1) R i (R i ₊₁ -R _i-1 ) + (n
−2) R _{i + 1} (R _{i + 2} −R _i ) +... + (I−1) R _n (R ₁ −
R _n−1 ) + (i−2) R ₁ (R ₂ −R _n ) +... R _i−2 (R _i−1 −
R _i-3 )} modp = α ＾ {R _i-1 R _i + R _i R _{i + 1} + R _{i + 1} R _{i + 2} +... + R _n
Calculate the _{R 1 + R 1 R 2 +} ··· + R i-2 R i-1} modp = α ^ {R 1 R 2 + R 2 R 3 + ··· + R n R 1} modp, the common key K get _n .

Even when the number of members of the group increases or decreases, a new group key is generated by the method described in the related art. Even if the configuration of the group is dynamically changed, the group key is generated in the idle terminal 8 of the investigating agency 6 that has joined the group, so that it is possible to constantly intercept the communication. After the eavesdropping permission period has elapsed, the control station 2 immediately removes the idle terminal 8 of the investigating organization 6 from the group and generates a new group key to prevent the eavesdropping of the communication, so that privacy is violated. Can be reliably prevented.

As described above, in the embodiment of the present invention,
The key escrow method uses a configuration in which idle terminals belong to each communication group and are stored by the control station, and when an investigating agency intercepts communications, the idle terminals are used to intercept only for the permitted period. This allows for costly quick interception when needed and prevents unrestricted interception by law enforcement agencies.

[0036]

As is apparent from the above description, the present invention
Now, the key escrow method is defined as the management station, control station, and base station.
Mobile cryptographic communication system consisting of
Group configuration in Stem's key escrow system management office
A means for managing information is provided, and the control station responds to terminal requests.
And then assign a dummy user to the group
Additional means and assigning dummy users to idle terminals
Means to generate the group key to the terminal via the base station.
Instructing means, storing idle terminals, and investigating
Means for providing idle terminals at the request of the institution;
After the eligibility period has passed, remove idle terminals
Means for causing a terminal to generate a new group key.
Means for relay control of group communication between terminals,
Generate a prime number p and an integer α (2 ≦ α ≦ p−1) as information
Each terminal M _i(i = 1 to n; n is
The number of members)_iHands to generate and keep secret
Step and Z_i= Α^Ri Calculate modp and deliver to other terminals
Means and Z sent from another terminal_{i + 1}And Z_i-1From
X_i= (Z_{i + 1}/ Z_i-1)^Ri modp (however, Z₀= Z_n,
Z_{n + 1}= Z₁Means for calculating and delivering to another terminal;
_i-1 ^nRi・ X_i ^n-1・ X_{i + 1} ^(n-2)... X_n ^(i-1)・ X₁ ^(i-2)
... X_i-2 Calculate modp and use common key K_nMeans to obtain
Equipped to prevent escaping at low cost.
No matter how the composition changes dynamically, investigating agencies
Will send communication from the group containing the
As well as unrestricted access by investigative agencies.
The effect that interception can be prevented is obtained.

[Brief description of the drawings]

FIG. 1 is a functional block diagram of a key escrow system according to an embodiment of the present invention;

FIG. 2 is a functional block diagram of a conventional key escrow system using a clipper chip,

FIG. 3 is a functional block diagram of a conventional key escrow system using ID-based key distribution.

[Explanation of symbols]

 REFERENCE SIGNS LIST 1 management station 2 control station 3 base station 4 wireless network 5 terminal T1 to T8 6 investigating agency 7 court 8 idle terminal

Continuation of the front page (72) Inventor Daisuke Ishii 3-20-8 Shin-Yokohama, Kohoku-ku, Yokohama-shi, Kanagawa 8 F-Term in Advanced Mobile Communication Security Technology Research Institute (reference) 5J104 AA16 EA12 JA03 NA00 NA02 PA01 5K067 AA30 BB01 BB21 CC10 CC13 DD29 EE02 EE10 EE16 EE32 FF04 HH36

Claims (1)

[Claims] In a key escrow system of a mobile cryptographic communication system capable of broadcasting comprising a management station, a control station, a base station, and a plurality of terminals, the management station includes means for managing group configuration information, The control station, a means for determining a group configuration according to the request of the terminal, adding a dummy user to the group, allocating a dummy user to an idle terminal, and generating a group key for the terminal via the base station. Means for instructing, means for storing the idle terminal, means for providing the idle terminal in response to a request from an investigating agency, and excluding the idle terminal after the eavesdropping permission period has elapsed to replace the terminal with a new group key. Means for relay control of group communication between the terminals, a prime number p and an integer α (2 ≦ 2) as public information. ≦ p-1) produced and means to expose the said respective terminal M _{i (i} = 1~n; a n is the number of members), and means for holding the secret to generate a random number R _i, Z
means for calculating _i = α ^Ri modp and delivering it to another terminal;
From Z _{i + 1} and Z _i-1 sent from other terminals, X _i =
(Z _{i + 1} / Z _i-1 ) ^Ri modp (where Z ₀ = Z _n , Z _{n + 1}
= Calculates the Z ₁₎ and means for delivering to other terminals, Z _{i-1
^{nRi · X i n -1 · X}} i + 1 (n-2) ··· X n (i-1) · X 1 (i-2) ·
· Key escrow method to calculate the X _i-2 modp characterized by comprising a means for obtaining a common key K _n.