KR100642745B1 - ID-based key exchange method and apparatus - Google Patents

Abstract

An ID-based key exchange method and apparatus are disclosed. The key exchange method comprises the steps of (a) the client passing the ID _u , X and Y to the server; (b) the server receiving the IDs _u , X and Y to authenticate the client, and if authenticated, generate the z and t _v to the client and generate a session key (sk); (c) the client receives z, t _v from the server and authenticates the server, and if the client is authenticated as a valid server, generating a session key identical to the session key of the server.

According to the present invention, an efficient ID-based authenticated key exchange can be achieved between two users (servers and clients) having different computing powers. It is especially suitable for mobile devices with low power by reducing the amount of computation on the client side.

Description

ID-based key exchange method and apparatus {ID-based Key Agreement Method and Apparatus}

1 is a block diagram showing the configuration of an ID-based key exchange device according to the present invention.

2 is a block diagram illustrating a detailed configuration of the generation unit 100 of X & Y.

3 is a block diagram illustrating a detailed configuration of the server authenticator 120.

4 is a block diagram illustrating a detailed configuration of the z & t _v generator 130.

5 is a block diagram illustrating a detailed configuration of the client authenticator 160.

6 is a flowchart illustrating an ID-based key exchange method according to the present invention.

TECHNICAL FIELD The present invention relates to key exchange, and in particular, to a method and apparatus for ID-based key exchange.

In many modern collaborations and distributed environments, authenticated key exchange is one of the most important issues. The key exchange protocol is intended for secret communication with users who own a distributed key. And a key exchange protocol that provides mutual authentication for any intended users to this key exchange protocol is called an authenticated key exchange (AKA) protocol. Among various authentication schemes, a typical certificate-based public key infrastructure (PKI) requires a certificate issued by a trust authority for the public key of the other party to be authenticated.

ID-based systems, on the other hand, only need to know a public identity (ID) consisting of plain public information such as the user's e-mail address. Therefore, ID-based authentication system provides more efficient and simple authentication method than certificate-based PKI.

Recently, as the wireless environment develops rapidly, an appropriate key exchange protocol is required. In particular, the formation of a secure channel in an unbalanced computing environment such as a server and a low power mobile is essential for secure communication. Unfortunately, most ID-based AKA protocols are not suitable for resource constrained applications, such as low power mobile devices, due to the complexity of computational speed and computational complexity.

SUMMARY OF THE INVENTION The present invention provides a method and apparatus for ID-based key exchange that can be used for low power mobile devices due to a small amount of calculation on the client side, and enables multiple clients to form a secure channel around a single server. It is.

In order to solve the above technical problem, an ID-based key exchange method according to the present invention includes a generator of a gap DiffieHellman group whose number is a prime q, a master secret key of a key generation center (KGC), and s and P. The product of P _pub (= sP), the pairing operation value of P (g (= e (P, P)), the IDs _u and ID _v of the client and server, and the secrets of the client and server When the keys are S _u and S _v , respectively, (a) the client forwards the ID _u , X and Y to the server; (b) the server receiving the IDs _u , X and Y to authenticate the client, and if authenticated, generate the z and t _v to be delivered to the client and generate a session key (sk); (c) the client receives z, t _v from the server and authenticates the server, and if the client is authenticated as a valid server, generating a session key identical to the session key of the server. Generating X and Y in step (a) comprises selecting an arbitrary value a from multiplication group Zq ^* having a degree q; Generating a hash function value _{q v (= H (ID V} )) of the ID _V and generating a Q _v (= P _pub + q _v P) combined for the P _pub and q _v P, and the g a exponentiation a taking step of generating a t _u (= g ^a) and generating a hash function value of the _{t u h (= h 1 (} t u)); And comprises the step of generating the X (= aQ _V) by calculating a product of the a and Q _v and generates a Y (= (a + h) S U) is multiplied by S _U to the sum of the a and h .

Client authentication of the (b) step, produce a hash function value of the _{ID U q u (= H (} ID U)) , and the combined the P _pub the product of q _u and P (q _u P) Q _U Generate (= P _pub + q _u P), generate t _u (= e (X, S _V )) by pairing X and S _V received from the client, and pair Y and Q _U received from the client. Producing c (= e (Y, Q _U )); A step of generating a hash function value of the _{t u h (= H 1 (} t u), generating the t _u and g of h exponentiation (g ^h) the product of a value (t _u g ^h); and wherein c = and if t _u g ^h is satisfied, authenticating to a valid client, wherein t _v in step (b) is generated by the server randomly selecting from the multiplication group Zq ^* , where the rank is q, and (b) The generation of z and the session key (sk) of step is that if the client is authenticated as a valid client, z = H ₂ (t _u , t _v , X, Y, ID _u , ID _v ), sk = H ₃ (t _u , t _v , X, Y, ID _u , and ID _v ) The server authentication in step (c) is performed by ID _U , ID _V , client generated t _u , X, Y and the server. t _v a hash function, the value of z; that _{'(= H 2 (t u} , t v, to produce the _{X, Y, ID u, ID} v) , and the z' are z and match (z '= z) And checking the session key in step (c). If you are authenticated as a valid server, then sk = H ₃ (t _u , t _v , X, Y, ID _u , ID _v ).

In the client authentication of step (b), if e (Y, Q _U ) is not equal to t _u g ^h , it is preferable to transmit a client authentication failure message to the client. In the server authentication of step (c), if z and z 'are not the same value, it is preferable to transmit a server authentication failure message to the server.

In order to solve the above technical problem, an ID-based key exchange device according to the present invention includes a generator of an addition group G1 having a rank of q, a master secret key of a key generation center KGC, and s. The product of P is Ppub (= sP), the pairing operation value of P is g (= e (P, P)), the IDs _u and ID _v of the client and server, respectively An X & Y generation unit installed in the client and the server when the keys are S _u and S _v , respectively, and generate X and Y values; A client transmitter installed on a client side and transmitting the ID _u , X and Y to a server; A client authentication unit installed in the client and receiving z and t _v from the server to authenticate the server; A client session key generation unit generating a session key identical to the session key of the server when authenticated with a valid server; A server authentication unit installed in a server and receiving the ID _u , X and Y to authenticate a client; Z & t _v generation unit, installed on the _server and generating z and t _v if the client is authenticated as a valid client; A server transmitter for transmitting the z and t _v to a client; And a server session key generator that is installed in the server and generates a session key sk when the client is authenticated as a valid client.

The generation unit of X & Y includes: a selection unit for selecting an arbitrary value a from multiplication group Zq ^* having a rank q; Generating a hash function value _{q v (= H (ID V} )) of the ID _V, and the combined the P _pub and q _v P generate Qv (= P _pub + q _v P), and the g to a exponentiation taking t _u (= g ^a) generating and parameter value generator generating a hash function value of the _{t u h (= h 1 (} t u)) a; An X generator for generating X (= aQ _V ) by calculating a product of a and Q _v ; And a Y generator that generates Y (= (a + h) S _U ) by multiplying S _U by the sum of a and h.

The client authentication unit has a hash function of ID _U , ID _V , client generated t _u , X, Y, and t _v received from the server, z '(= H ₂ (t _u , t _v , X, Y, Z 'generation unit for generating ID _U and ID _V ) and z' authentication unit for authenticating the server by checking whether z 'matches z (z' = z). If the server is authenticated as a valid server, the hash function values of t _u , t _v , X, Y, ID _u , and ID _v (sk = H ₃ (t _u , t _v , X, Y, ID _u , ID _v )) to generate the server authentication unit generates a hash functional value of the _{ID U q u (= H (} ID U)) , and the product of the Ppub q _u and P (q _u P) and the combined Q _U (= Ppub + q _u P), pairing operation of X and S _V received from the client to generate t _u (= e (X, S _V )), and pairing operation of Y and Q _U received from the client to c (= to produce a hash function value of the _{t u h (= h 1 (} t u)); e (Y, Q U)) c generator for generating , Wherein t _u and g of h exponentiation (g ^h) the product of a value (t _u g ^h) t _u g ^h and generates a; Compare and the c and the t _u g ^h if the value is the same valid It includes a c authentication unit for authenticating with the client.

The z & t _v generation unit includes: a t _v selection unit for selecting at random a t _v from a multiplication group Zq ^* having a rank q; And if the client is authenticated as a valid _{client, t u, t v, X} , Y, ID u, ID v hash function value of _{z (= H 2 (t u} , t v, X, Y, ID u, ID v Z generation unit generating)). The server session key generation unit hashes t _u , t _v , X, Y, ID _u , and ID _v when the client is authenticated as a valid client. Sk (= H ₃ (t _u , t _v , X, Y , ID _u , ID _v )).

If e (Y, Q _U ) is not equal to t _u g ^h in the client authentication unit, it is preferable to transmit a client authentication failure message to the client. If z and z 'are not the same value, the server authentication unit preferably transmits a server authentication failure message to the server.

A computer readable recording medium having recorded thereon a program for executing the invention described above is provided.

Hereinafter, a method and apparatus for ID-based key exchange according to the present invention will be described in detail with reference to the accompanying drawings.

First, Bilinear Maps and cryptographic assumptions are explained. In the present invention, let G ₁ be an addition operation group having a decimal number q and G _{2 be} a multiplication operation group having the same rank q. And P is the constructor of G ₁ . In this case, it is assumed that the discrete logarithm problem (DLP) in G ₁ and G ₂ is difficult. The function e: G ₁ x G _1- > G ₂ , which satisfies the following conditions, is called an admissible bilinear map.

Bilinear: e (aP, bP) = e (P, P) ^{ab for} all P, Q ∈ G ₁ and a, b ∈ Zq ^*

Non-degenerate: P ∈ G ₁ satisfying e (P, P) ≠ ₁ Is present.

Computable: There is an efficient algorithm that can calculate e (P, P) for all P, Q ∈ G ₁ .

Computational Diffie - Hellman ( CDH ) problem : The CDH problem is to calculate abP given P, aP, and bP where a, b ∈ Zq ^* .

Inverse Computational Diffie - Hellman ( ICDH ) problem : The ICDH problem is to calculate a ^-1 P given P, aP, which is a∈ Zq ^* .

Modified Inverse Computational Diffie-Hellman (mICDH) problem: The mICDH problem is to calculate (a + b) ^-1 P given a, b ∈ Zq ^* , b, P, aP and (a + b) P.

Bilinear Diffie - Hellman ( BDH ) problem : The BDH problem is to calculate e (P, P) ^abc given P, aP, bP and cP, where a, b, c∈Zq ^* .

를 계산하는 문제이다. Bilinear Inverse Diffie - Hellman ( BIDH ) problem : The BIDH problem is given by P, aP, bP where a, b, c∈Zq ^*

It is a matter of calculating.

를 계산하는 문제이다. Modified Bilinear Inverse Diffie - Hellman ( mBIDH ) problem : The mBIDH problem is given by b, P, aP and cP where a, b, c∈Zq ^*

It is a matter of calculating.

It is easy to see that the CDH, ICDH, and mICDH problems are polynomial time equivalents.

Theorem 1. BDH, BIDH and mBIDH problems are polynomial time equivalents.

(Proof) BDH and BIDH problems are polynomial time equivalents. Therefore, we only prove that BIDH and mBIDH are polynomial time equivalents.

를 출력하면 mBIDH 역시 같은 값을 출력한다.[BIDH ⇒ mBIDH] If b, P, aP and cP are given to mBIDH, calculate a'P = aP + bP and enter P, a'P, cP into BIDH. BIDH

If you print, mBIDH will output the same value.

를 출력하면 BIDH 역시 같은 값을 출력한다.[mBIDH ⇒ BIDH] Given P, aP and cP to BIDH, calculate a'P = aP-bP and enter b, P, a'P and cP into mBIDH. mBIDH

Outputs the same value.

Assume that CDH, BDH and BIDH problems are difficult. This means that no algorithm exists to calculate CDH, BDH and BIDH problems with meaningful probabilities in polynomial time. The GDH parameter generator that satisfies the gap Diffie-Hellman (GDH) assumption can be configured as Weil / Tate pairing on an elliptic curve.

In order to demonstrate the safety of the present invention, the problems of Collusion Attack Algorithm with k traitor (k-CAA) and modified BIDH with k values (k-mBIDH) are defined. In fact, k-mBIDH is a bilinear form of the k-CAA problem.

Definition 1. The k-CAA problem is to calculate (s + h) ^-1 P for h ∈ Zq ^* given by

를 계산하는 문제이다. Definition 2. The k-mBIDH problem is given by

It is a matter of calculating.

.

.

A more general advantage for Algorithm A is defined as

Next, the security of the ID-based key exchange method and apparatus according to the present invention will be analyzed.

We describe the method and apparatus for ID-based authenticated key exchange between mobile client U and server V using authenticryption technique, and prove the security in random Oracle model. The key exchange method applied to this invention is called ID-AKA.

1. ID-based authenticated key exchange protocol

First we create two groups G ₁ , G ₂ and bilinear map e using the GDH generator. It is assumed that the mICDH problem in G ₁ is difficult. The ID-AKA method of the present invention uses a key generation authority (KGC), which is a trust authority that generates a secret key corresponding to a given public identifier, and the security of the generated secret key is based on the difficulty of the mICDH problem.

Setup is as follows.

그리고

를 선택한다. 여기서 t 는 보안상수(security parameter)이며, k는 세션키의 비트 길이이다. 그 다음에 KGC는 마스터 비밀키인 s를 비밀로 하고 공개 시스템 파라미터

를 공개한다.KGC selects the constructor P of s ∈ Zq ^* and G ₁ and calculates P _pub = sP. Also cryptographic one-way hash function

And

Select. Where t is the security parameter and k is the bit length of the session key. KGC then keeps the master secret key s secret and public system parameters

To the public.

Extract is done as follows.

를 계산하여 비밀키

를 계산한 후 (g, S_U)를 안전한 채널로 U에게 전송한다. 동일한 방법으로, 확인자가 ID_v인 서버 V도

를 계산한 후, 비밀키

와 g=e(P,P) 를 계산하여 안전한 채널로 V에게 전송한다. When the client U whose resolver is ID _u wants to obtain a secret key, KGC

Calculate the secret key

Calculate and transmit (g, S _U ) to _U on a secure channel. In the same way, even the _server whose resolver is ID _v

Calculate, Secret Key

Calculate and g = e (P, P) and send it to V on a secure channel.

1 is a block diagram illustrating a configuration of an ID-based key exchange device according to the present invention. The X & Y generation unit 100, the client transmission unit 110, the client authentication unit 160, and the client session key generation unit 170 are shown in FIG. ), The server authentication unit 120, the z & t _v generation unit 130, the server transmission unit 140 and the server session key generation unit 150.

First, the constructor of the gap DiffieHellman group having a prime q, for example, the addition group G ₁ having a prime q, is P, the master secret key of the Key Generation Center (KGC) s, and the product of s and P is Ppub. (= sP), g pairing operation value of P (= e (P, P)), ID _u and ID _{v of} client and server, respectively, and secret key of client and server received from key generation center, respectively. _u and S _v .

The X & Y generator 100 is installed in the client and generates an X value and a Y value. 2 is a block diagram showing the detailed configuration of the generation unit 100 of the X & Y, a selection unit 200, parameter generation unit 220, X generation unit 240 and Y generation unit 260 It is made, including. The a selector 200 selects a random value a from the multiplication group Zq ^* having the above order q. The parameter generator 220 generates a hash function value q _v (= H (ID _V )) of the ID _V , and adds the P _pub and q _v P to Q _v (= P _pub + q _v P). the generation, and by taking a exponentiation of g generate the _u t (= g ^a) and generating a hash function value of the _{t u h (= H 1 (} t u)). The X generator 240 generates X (= aQ _V ) by calculating the product of a and Q _v . The Y generator 260 generates Y (= (a + h) S _U ) by multiplying S _U by the sum of a and h.

The client transmitter 110 is installed on the client side, and transmits the ID _u , X and Y to the server.

The client authentication unit 160 is installed on the client and authenticates the server by receiving z and t _v from the server. 5 is a block diagram illustrating a detailed configuration of the client authenticator 160, and includes a z ′ generation unit 500 and a z authenticator 550. The z 'generation unit 500 is a ID of _U , ID _V , t _u generated by the client, X, Y, a hash function of the tv received from the server z' (= H ₂ (tu, tv, X, Y , ID _U , ID _V )). The z authenticator 550 authenticates the server by checking whether z 'matches z (z' = z).

The client session key generation unit 170 generates the same session key as that of the server if the server is authenticated as a valid server. More specifically, the client session key generation unit 170, if the server is authenticated as a valid server, the hash function value of t _u , t _v , X, Y, ID _u , ID _v (sk = H ₃ ( t _u , t _v , X, Y, ID _u , ID _v ))

Server authentication unit 120 is installed on the server, and receives the ID _u , X and Y to authenticate the client. 3 is a block diagram illustrating a detailed configuration of the server authenticator 120, and includes a c generator 300, a t _u g ^h generator 320, and a c authenticator 340.

The c generator 300 generates a hash functional value of the ID _U q _u (= H (ID _U)), and the product of the Ppub q _u and P (q _u P) and the combined Q _U (= Ppub + q _u P), pairing operation of X and S _V received from the client to generate t _u (= e (X, S _V )), and pairing operation of Y and Q _U received from the client to c ( = e (Y, Q _U )). The t _u g ^h generation unit 320 is the t _u of the hash function value h (= H ₁ (t _u)) for generating said t _u and g of h exponentiation (g ^h), the multiplied value (t _u g ^h ). The c authentication unit 340 compares c and t _u g ^h and authenticates a valid client if the values are the same.

The z & t _v generator 130 is installed in the server, and generates z and t _v if the client is authenticated as a valid client. 4 is a block diagram illustrating a detailed configuration of the z & t _v generation unit 130, and includes a t _v selection unit 400 and a z generation unit 450. The t _v selection unit 400 selects a random t _v from the multiplication group Zq ^* number of q above the server. The z generating unit 450, if the client is authenticated as a valid client, the hash function value z (= H ₂ (t _u , t _v , X,) of t _u , t _v , X, Y, ID _u , and ID _v Y, ID _u , ID _v )).

The server transmitter 140 transmits the z and t _v to the client.

The server session key generation unit 150 is installed in the server, and generates a session key sk when the client is authenticated as a valid client. That is, when the client is authenticated as a valid client, the server session key generation unit 150 hashes t _u , t _v , X, Y, ID _u , and ID _v sk (= H ₃ (t _u , t _v , X, Y, ID _u , ID _v ))

를 계산하고 난수 a∈Zq^* 를 선택하여 t_u=g^a와 Qv = Ppub + q_vP를 계산한다. 그 다음으로 U는

그리고

를 계산하여

를 V에게 전송한다.Meanwhile, an ID-based key exchange method according to the present invention in which the client U and the server V generate a session key will be described. 6 is a flowchart illustrating an ID-based key exchange method according to the present invention. Referring to Figure 6, the client U is

Compute t _u = g ^a and Qv = Ppub + q _v P by selecting the random number a∈Zq ^* . Then U is

And

By calculating

Is sent to V.

를 계산한 후, z와 t_v를 U에게 전송한다. 결국 서버 V는 세션키로

를 계산한다. Server V calculates q _u = H (ID _u ) and Q _U = P _pub + q _u P, and then receives the message t _u = g ^a and c = e (X, Sv) and its private key S Calculate using _v We also determine that c = t _u g ^h by calculating h = H ₁ (t _u ). If the expression does not hold, V outputs a failure, and if the expression holds, select the random number t _v ∈ Zq ^* to send an authentication message.

Then compute z and t _v to U. Eventually, Server V is the session key

Calculate

을 t_u와 t_v를 이용하여 계산한 후, z=z'임을 확인한다. 만약 식이 성립하지 않으면 U는 실패를 출력하고, 식이 성립하면 세션키

를 계산한다.Client u

Is calculated using t _u and t _v , and it is confirmed that z = z '. If the expression does not hold, U prints a failure, and if the expression holds, the session key

Calculate

In the above protocol, client U can calculate t _u and Y in advance. Then on-line U needs to calculate only one point addition and two scalar multiplications. In addition, since the hash function H is a general hash function rather than a large computational Map-To-Point operation, the calculation amount is very small.

This will be described in more detail as follows. First, the constructor of the gap DiffieHellman group having a prime number q, for example, the addition group G1 having a prime q, is P, the master secret key of the key generation center (KGC) is s, and the product of s and P is P _pub ( = sP), the P of the pairing computation value of g (= e (P, P )), the ID of the client and server each ID _u and ID _v, the private key of the client and the server received from the key generation center, each S _u And S _v .

(a) The client passes the ID _u , X and Y to the server. Here, the generation of X and Y is performed as follows. Selects a random value a from multiplication group Zq ^* whose rank is q. Then generating a hash function value _{q v (= H (ID V} )) of the ID _V, and the combined the P _pub and q _v P generate Qv (= P _pub + q _v P), and the g by taking a a power generation of t _u (g = ^a), and generates a hash functional value of the _{t u h (= H 1 (} t u)). And then it generates a Y (= (a + h) S U) generate the X (= aQ _V) by calculating a product of the Q and _v, and _U is multiplied by S to the sum of the a and h.

(b) The server receives the IDs _u , X and Y to authenticate the client, and if authenticated, generates a z and t _v to be delivered to the client and generates a session key sk. Here, the client authentication is performed as follows. Hash function value of the _{ID U q u (= H (} ID U)) generated, and the product of the P _pub q _u and _{P (q u P) Q U} (= P pub + q u P) combined with the a Generate t _u (= e (X, S _V )) by pairing the X and S _V received from the client, and c (= e (Y, Q) by pairing the Y and Q _U received from the client. _U )) Then to produce the hash function value of _{t u h (= H 1 (} t u)), and generates a value (t _u g ^h) multiplied by the exponential h ^(h g) of the t _u and g. Then, if c = t _u g ^h is satisfied, a valid client is authenticated. And t _v is generated by the server arbitrarily selecting from the multiplication group Zq ^* of order q. The generation of z and the session key sk is such that if the client is authenticated as a valid client, z = H ₂ (t _u , t _v , X, Y, ID _u , ID _v ), sk = H ₃ (t _u , t _v , X, Y, ID _u , ID _v ).

(c) The client receives z and t _v from the server and authenticates the server. If the client authenticates as a valid server, the client generates the same session key as the session key of the server. Here, the server authentication is performed as follows. First, ID _U , ID _V , a hash function of t _u , X, Y generated by the client, and t _v received from the server z '(= H ₂ (t _u , t _v , X, Y, ID _U , ID _V ), then check that z 'matches z (z' = z) The session key sk is sk = H ₃ (t if the server is authenticated as a valid server). _u , t _v , X, Y, ID _u , ID _v ).

The present invention provides half omnidirectional safety. If the server's private key is leaked, the attacker can calculate all the session keys from the transmitted message, but if the client's private key is leaked, the attacker using it will not get any information about the previous session keys. In general, mobile clients are low power devices, which makes them more vulnerable to attack than servers. Therefore, the provision of omnidirectional security at the client is more effective than the server.

Analysis of the safety of the present invention is as follows. Forger is an attacker forging a client's message in ID-AKA for security analysis. First, it shows that forgery of the client's transmission message from ID _u and ID _v is impossible.

그리고 q_E 개의 H, H₁, 전송 그리고 추출질의를 한다고 하자. 만약

라 하면 러닝 타임이

인 k-CAA문제를 계산하는 공격자 B가 존재한다. Theorem Theorem 1. Assume that the hash functions H and H ₁ are random Oracles, and Forger A is a forger with ID _u and ID _v and a probability of success with running times t ₀ and ε ₀ . A is each

And q _E H, H ₁ , transmission and extraction query. if

Speaking of running time

There is an attacker B who computes the k-CAA problem.

인 k-CAA 문제의 입력값

이 주어진다. B의 목적은 임의의 q₀에 대하여

를 계산하는 것이다. B는 A를 이용하기 위해 A의 공격 환경을 시뮬레이션해 준다. 먼저 B는 GDH 파라미터

를 생성하고 Ppub=sP와 g=e(P,P)를 계산하여 시스템 파라미터

를 A에게 입력한다.(Proof) First to B

For k-CAA problems

Is given. The purpose of B is for any q ₀

Will be calculated. B simulates A's attack environment to use A. B is the GDH parameter

Create a system parameter by calculating Ppub = sP and g = e (P, P)

Enter to A.

Without loss of generality, assume that for a given ID, A only performs H, H ₁ , transmission, and extract query once, and performs a query before transmission and extract. To avoid conflicts and to ensure consistent responses to queries, B maintains lists L _H and L _H1 . These lists are initially empty. B responds to A's query as follows:

H -question. When A is when the H- query to the ID _i, if _i = ID If ID is _V B is other than transmitting the q _0, that is, add the <ID _i, q _i> L _H in the list and sends the q _i do.

H ₁ -question. When A has H ₁ -queried for m, B sends a random number h and adds it to the list L _H1 .

) 질의를 했을 때, 만약 ID_i = ID_U이면 B는 난수 a와 h를 선택하여 X=a(sP+q₀P)와 Y=hP를 계산한 후, ID_u(X,Y)를 A에게 전송한다. 그 외의 경우 B는 목록 L_H에서 <ID_i, q_i>를 찾은 후, 난수 a와 h를 선택하고 X=a(sP+q₀P)와 Y=(a+h)(q_i+s)^-1P를 계산하여 ID_u(X,Y)를 A에게 전송한다. 만약 A의 전송 질의가 ID_i=ID_u이면 B는 정당한 Y값을 생성할 수 없기 때문에 임의의 Y값을 전송하게 된다. 그러나 A는 서버의 비밀키 S_v를 알지 못하기 때문에 전송받은 (X,Y)에 대한 정당성을 확인할 수 없다. 따라서 전송 질의에 대한 B의 시뮬레이션은 타당하다. Transport-query. A is sent (

In the query, if ID _i = ID _U, B selects random numbers a and h, calculates X = a (sP + q ₀ P) and Y = hP, and sets ID _u (X, Y) to A. Send to. Otherwise, B finds <ID _i , q _i > from list L _H , selects random numbers a and h, and X = a (sP + q ₀ P) and Y = (a + h) (q _i + s ) ^-1 P is calculated and ID _u (X, Y) is sent to A. If A's transmission query is ID _i = ID _u, B will not be able to generate a valid Y value. However, since A does not know the server's secret key S _v , it cannot verify the validity of the received (X, Y). Therefore, the simulation of B for the transmission query is valid.

에 대한 추출 질의를 했을 때, B는 목록 L_H에서 <ID_i, q_i>를 찾은 후, (s+q_i)^-1P를 전송한다. Extract-Query. A

When B extracts the query, B finds <ID _i , q _i > in the list L _H , and sends (s + q _i ) ^-1 P.

와

을 출력하게 된다. 그러면 B는

를 계산한 후 이를 k-CAA 문제의 결과로 출력한다.Finally, A prints a new legitimate message ID _u (X, Y). B simulates the same using H ₁ and a different hash function H ' ₁ , like forking lemma, so A pairs two different legitimate messages where A is h ≠ h'

Wow

Will print B is then

Calculate and output it as the result of the k-CAA problem.

에 유계하게 된다.The probability that B correctly guesses h and h 'is 1 / q ² _H1 and the total running time t ₁ is equal to the running time required for the forking lemma.

Will be bound to

Theorem 2. Suppose that the hash function used in the proposed ID-AKA is called random Oracle, and that ID-AKA attacker A is given with ID _U and ID _V and running time t. ID-AKA is then a secure AKA protocol that provides half omnidirectional safety based on the difficulty of the k-mBIDH problem. In other words,

는 공격자 A가 생성하는 전송, 손상 그리고 해쉬 Hi 질의의 개수를 나타낸다.Where Adv ^Forge (t) is the maximum benefit of any Forger with t running time,

Represents the number of transmission, corruption, and hash Hi queries generated by attacker A.

(Proof) Let A be an active attacker attacking ID-AKA. A can then attempt to attack in two cases. The first is forgery of authentication messages. In other words, try the most attack as a client. The second is to attack by eavesdropping without forging or tampering with the transmitted message. An attacker forging a server's outgoing message, that is, an attack impersonating the server, must eventually forge a value of z, which cannot succeed without knowing the client's secret value t _u . However, forgery of z-values is impossible due to the unidirectionality of the hash function H ₂ . Therefore, attacker A's attack is limited to the above two cases.

가 된다. 보조정리 1.에 의하여 확률 Pr_A[Forge]은 무시할 만한 값이다.First, if A attempts to attack in the first case, A can be used to construct a Forger F that forges a legitimate message pair ID _V (X, Y). This can be easily configured by correctly generating all the public and private keys necessary for the system and then simulating A's queries. If Forger is an event in which A creates a new legitimate message pair, the probability that F will succeed

Becomes By auxiliary theorem 1. The probability Pr _A [Forge] is a negligible value.

를 질의해야만 한다. 따라서 A는 비밀 정보인 t_u를 계산해야만 한다. 그러므로 A를 이용하여 k-mBIDH 문제를 계산하는 공격자 B를 다음과 같이 구성할 수 있다. 먼저 B에게

인 k- mBIDH 문제의 입력값

이 주어진다. B의 목적은

를 계산하는 것이다. B는 A를 이용하기 위해 A의 공격 환경을 시뮬레이션 해 준다. 먼저 B는 GDH 파라미터 <e,G₁,G₂>를 생성하고 Ppub=sP와 g=e(P,P)를 계산하여 시스템 파라미터

를 A에게 입력한다. A의 이점을 활용하기 위해 B는 임의의

를 선택한다.

는 A가

번째 세션에 테스트 질의를 하는 것을 추측하기 위한 값이다.Next, consider when A attempts to attack in the second case. A hash is the Oracle H ₃ to obtain the information from the session key sk

You must query Therefore, A must calculate the secret information t _u . Therefore, attacker B, which computes k-mBIDH problem using A, can be constructed as follows. To B first

K- mBIDH Problem Input

Is given. The purpose of B

Will be calculated. B simulates A's attack environment to use A. First, B generates the GDH parameters <e, G ₁ , G ₂ > and calculates the system parameters by calculating Ppub = sP and g = e (P, P).

Enter to A. To take advantage of A, B is random

Select.

Has a

The value to guess the test query in the first session.

Without loss of generality, suppose A queries the same message only once, and performs an H query before transmission and extraction. To avoid conflicts and to ensure consistent responses to queries, B maintains lists L _H , L _H1, and L _H2 . These lists are initially empty. B responds to A's query as follows:

H -question. When A makes an H-query against ID _i , if ID _i = ID _v, B sends q ₀ , otherwise adds <ID _i , q _i > to list L _H and sends q _i do.

H ₁ -question. If A has a H ₁ -query for message m equal to (m, h) recorded in the list L _H1 , then B sends h. Otherwise, B sends a random number h and adds (m, h) to L _H1 .

는 목록에서

를 찾아서 z를 A에게 전송한다.H ₂ -question. When A asks H _2-

In the list

Find and send z to A.

H ₃ -question. If A queries H ₃ -for message m, B sends a random number to A.

Transport-query. The transfer query considers two transfer queries from client to server and from server to client. The query from the client to the server is called S, and the query from the server to the client is called C.

질의를 했을 때, 만약 이 질의가

번째 세션에 대한 요청이면, B는 난수

을 선택하고, X=tP와 Y=

P를 계산한 후, ID_V (X,Y)를 A에게 전송한다. 그 외의 경우 B는 목록 L_H에서

를 찾은 후, 난수

와 h를 선택하고

그리고

를 계산하여 t_u와 h는 목록 L_H1에 추가하고 ID_V(X,Y)를 에게 전송한다.A send

When you make a query, if this query

If the request is for the first session, B is a random number

, Select X = tP and Y =

After calculating P, ID _V (X, Y) is sent to A. Otherwise B is in list L _H

After finding, random number

And h

And

T _u and h are added to the list L _H1 and the ID _V (X, Y) is sent to.

질의를 했을 때, B는 난수 z와 t_v를 선택하고 이를 A에게 전송한 후

를 목록 L_H2에 추가한다.A send

When querying, B chooses a random number z and t _v and sends it to A.

To the list L _H2 .

를 A에게 전송한다. Run-inquiry. When A makes a run (U, V) query, B uses a simulation of the transfer query to

Is sent to A.

에 대한 추출 질의를 했을 때, B는 목록L_H에서

를 찾은 후,

를 전송한다. Extract-Query. A

When an extract query is made for, B is from list L _H

After finding

Send it.

를 찾은 후,

를 전송한다. Damage-quality. When A makes a damage query for ID _V , B is in list L _H

After finding

Send it.

Outflow-question. When A makes a leak query, B sends a random number to A.

번째 세션에 대한 질의이면 B는 실패를 출력하고, 그 외의 경우에는 임의의 비트 b를 선택한다. 만약 b=1이면 세션키를 아니면 난수를 A에게 전송한다. Test-question. When A makes a test query, if that query

If the query is for the first session, B outputs a failure; otherwise, selects a random bit b. If b = 1, the session key is sent or A is sent to A.

를 정확히 추측한 사건과 A가 비밀 값

를 해쉬 오라클에 질의한 사건에 의존한다. 위의 시뮬레이션에서 B가

를 정확히 추측할 확률은

이고, A의 이점이

이라면 A가 비밀 값 t_u를 H₁ 해쉬 오라클에 질의할 확률은

이 된다. 따라서 B가

를 정확히 추측하였다면 t_u는

의 확률로 목록 L_H1에 존재하게 된다. 그러므로 B는 k-mBIDH 문제를 적어도 확률

로 계산할 수 있게 된다. 결국 증명의 처음부분에서 언급한 두 번째 사건에 대한 A의 이점은 최대

만큼의 이점을 가지게 된다. 마침내 우리는 위의 증명의 결과로 아래와 같은 식을 얻을 수 있다.B's probability of success is

The exact guess and A's secret value

Depends on the event that queried the hash Oracle. In the above simulation, B

The probability of guessing exactly

And the advantage of A is

If the probability that A will query the private value t to _u H ₁ hash Oracle

Becomes So B is

If _u correctly guess t _u is

Has a probability of being in the list L _H1 . Therefore B is at least a probability of k-mBIDH problem

Can be calculated as After all, the benefit of A for the second case mentioned at the beginning of the

You will have as many advantages. Finally, we can obtain the following equation as a result of the above proof.

The present invention can be embodied as code that can be read by a computer (including all devices having an information processing function) in a computer-readable recording medium. The computer-readable recording medium includes all kinds of recording devices in which data that can be read by a computer system is stored. Examples of computer-readable recording devices include ROM, RAM, CD-ROM, magnetic tape, floppy disks, optical data storage devices, and the like.

Although the present invention has been described with reference to the embodiments shown in the drawings, this is merely exemplary, and it will be understood by those skilled in the art that various modifications and equivalent other embodiments are possible. Therefore, the true technical protection scope of the present invention will be defined by the technical spirit of the appended claims.

The ID-based key exchange method and apparatus according to the present invention enables efficient ID-based authenticated key exchange between two users (servers and clients) having different computing power. It is especially suitable for mobile devices with low power by reducing the amount of computation on the client side. The safety of the present invention is based on the difficulty of k-CAA and k-mBIDH problems in the random Oracle model.

ID-based systems using bilinear maps require complex computations, such as Weil / Tate pairing operations and Map-To-Point operations, which convert ID numbers into points on an elliptic curve. . Therefore, even though much research has been conducted to reduce such complex operations, especially pairing operations, the ID-based key exchange schemes proposed by the existing ID-based key exchange schemes are still very low compared to scalar products. Not suitable for use with the device. Most ID-based AKAs are based on a wired network environment capable of performing heavy computations on the client side.

ID-based AKA according to the present invention also uses a bilinear map. However, it has the following features. First, we didn't use complex pairing and Map-To-Point operations on the client side. Second, using offline precomputation, on-line clients only need to perform two scalar products and one addition on an elliptic curve.

The present invention takes advantage of the concept of authenticity, where only key exchange and designated verifiers (servers) can verify and decrypt a given message.

The present invention provides a half forward secrecy where the previous session key is exposed when the server's fixed secret key is exposed, but the previous session key is secure even when the client's fixed private key is exposed. In addition, key exchange between users in different domain areas, i.e., a client, can establish a secure channel with itself and with servers in other domain areas. Moreover, the protocol according to the present invention can be extended to an ID-based authenticated group key exchange where multiple clients can form a secure channel around a single server.

Claims (9)

The generator of the gap DiffieHellman group whose prime is q is P, the master secret key of the Key Generation Center (KGC) is s, the product of s and P is P _pub (= sP), and the pairing operation of P is g (= e when La (P, P)), the client and the server ID of each ID _u and ID _v, the secret key of the client and the server receives from the key generation center each S _u and S _v, (a) the client passing the IDs _u , X and Y to the server; (b) the server receiving the IDs _u , X and Y to authenticate the client, and if authenticated, generate the z and t _v to be delivered to the client and generate a session key (sk); (c) the client receives z, t _v from the server and authenticates the server, and if the client is authenticated as a valid server, generating a session key identical to the session key of the server, Generation of X and Y in step (a) Selecting an arbitrary value a from the multiplication group Zq ^* whose rank is q; Generating a hash function value _{q v (= H (ID V} )) of the ID _V and generating a Q _v (= P _pub + q _v P) combined for the P _pub and q _v P, and the g a exponentiation a taking step of generating a t _u (= g ^a) and generating a hash function value of the _{t u h (= H 1 (} t u)); And Be made by generating a X (= aQ _V) by calculating a product of the a and Q _v and generates a Y (= (a + h) S U) is multiplied by S _U to the sum of the a and h , Client authentication of step (b) Hash function value of the _{ID U q u (= H (} ID U)) generated, and the product of the P _pub q _u and _{P (q U P) Q U} (= P pub + q U P) combined with the a Generate tu (= e (X, S _V )) by pairing the X and S _V received from the client, and c (= e (Y, Q _U) by pairing the Y and Q _U received from the client. Generating)); A step of generating a hash function value of the _{t u h (= H 1 (} t u)), generating a value (t _u g ^h) multiplied by the exponential h ^(h g) of the t and _u g; And If c = t _u g ^h is satisfied, including a step of authenticating to a valid client, T _v in step (b) is generated by the server randomly selecting from the multiplication group Zq ^* of order q, Generation of the z and session key (sk) in step (b), z = H ₂ (t _u , t _v , X, Y, ID _u , ID _v ), sk if the client is authenticated as a valid client = H ₃ (t _u , t _v , X, Y, ID _u , ID _v ), The server authentication of step (c), ID _u , ID _V , the client generated t _u , X, Y, t _v received from the server hash function z '(= H ₂ (tu, tv, X, Y, ID _U , ID _V ) Generating; and And checking whether z 'matches z (z' = z), The generation of the session key sk of step (c) is performed by sk = H ₃ (t _u , t _v , X, Y, ID _u , ID _v ) if the server is authenticated as a valid server. Based key exchange method. The method of claim 1, The constructor P of the gap DiffieHellman group whose number is prime q ID-based key exchange method, characterized in that the generator of the addition group (G1) of the number q. The method of claim 1, And (e) in the client authentication of step (b), if an e (Y, Q _U )) value is not equal to t _u g ^h , a client authentication failure message is sent to the client. The method of claim 1, In the server authentication of step (c), if z and z 'are not the same value, a server authentication failure message is transmitted to the server. The generator of the addition group (G1) of the order q is P, the master secret key of the key generation center (KGC) is s, the product of s and P is Ppub (= sP), and the pairing operation value of P is g when La (P, P)), the client and the server ID of each ID _u and ID _v, the secret key of the client and the server receives from the key generation center each S _u and S _v, An X & Y generator installed in the client and generating an X value and a Y value; A client transmitter installed on a client side and transmitting the ID _u , X and Y to a server; A client authentication unit installed in the client and receiving z and t _v from the server to authenticate the server; A client session key generation unit generating a session key identical to the session key of the server when authenticated with a valid server; A server authentication unit installed in a server and receiving the ID _u , X and Y to authenticate a client; Z & t _v generation unit, installed on the _server and generating z and t _v if the client is authenticated as a valid client; A server transmitter for transmitting the z and t _v to a client; And It is installed on the server, characterized in that it comprises a server session key generator for generating a session key (sk) if the client is authenticated as a valid client, The generation unit of the X & Y A selection unit for selecting an arbitrary value a from the multiplication group Zq ^* having a rank q; Generating a hash function value _{q v (= H (ID V} )) of the ID _V, and the combined the P _pub and q _v P generate Qv (= P _pub + q _v P), and the g to a exponentiation taking t _u (= g ^a) generating and parameter value generator generating a hash function value of the _{t u h (= H 1 (} t u)) a; An X generator for generating X (= aQ _V ) by calculating a product of a and Q _v ; And Is made by multiplying the S _U to the sum of the a and h Y (= (a + h ) S U) includes a generation unit configured to generate Y, The client authentication unit, ID _U , ID _V , hash generated by the client generated t _u , X, Y, and t _v from the server z '(= H ₂ (t _u , t _v , X, Y, ID _U , ID _V Z 'generator to generate and A z 'authentication unit for authenticating a server by checking whether z' matches z (z '= z); The client session key generator If the server is authenticated as a valid server, the hash function value of t _u , t _v , X, Y, ID _u , ID _v (sk = H ₃ (t _u , t _v , X, Y, ID _u , ID _v ) ), Server authentication unit Generating a hash function value of the _{ID U q u (= H (} ID U)) , and generates the product of the Ppub q _u and _{P (q u P) Q U} (= Ppub + q u P) were combined and and , Tu (= e (X, S _V )) is generated by pairing the X and S _V received from the client, and c (= e (Y, Q _U )) by pairing the Y and Q _U received from the client. C generating unit for generating a; Generating a hash function value of the _{t u h (= H 1 (} t u)), t u g h generator for generating the product of the h exponentiation (g ^h) in the t _u and the g value (t _u g ^h) part; And Comparing the c and t _u g ^h and if the value is the same comprises a c authentication unit for authenticating as a valid client, The z & t _v generation unit, A t _v selection unit for the _server to randomly select t _v from the multiplication group Zq ^* having a rank q; And And if the client certificate as a valid _{client, t u, t v, X} , Y, ID u, ID v hash function value of _{z (= H 2 (t u} , t v, X, Y, ID u, ID v) Z generating unit for generating), The server session key generation unit If the client is authenticated as a valid client, hashing t _u , t _v , X, Y, ID _u , and ID _v sk (= H ₃ (t _u , t _v , X, Y, ID _u , ID _v) ID) based key exchange device. The method of claim 5, The constructor P of the gap DiffieHellman group whose number is prime q ID-based key exchange device, characterized in that the generator of the addition group (G1) of the number q. The method of claim 5, And, if e (Y, Q _U )) is not equal to t _u g ^h in the client authentication unit, sends a client authentication failure message to the client. The method of claim 5, And the server authentication unit transmits a server authentication failure message to the server when z and z 'are not equal to each other. A computer-readable recording medium having recorded thereon a program for executing the invention according to claim 1 on a computer.

Images