Split-key key-agreement protocol

• US 6,934,392 B1
• Filed: 07/19/2000
• Issued: 08/23/2005
• Est. Priority Date: 07/19/1999
• Status: Expired due to Term

• Current Assignee: Malikie Innovations Limited (Key Patent Innovations Limited)
• Original Assignee: Certicom Corporation (Blackberry Limited)
• Inventors: Vanstone, Scott A.
• Primary Examiner(s): Barrón, Gilberto
• Assistant Examiner(s): Dinh, Minh
• Application Number:
  US09/619,633
• Time in Patent Office: 1,861 Days
• Field of Search: 713/163, 713/171, 380 28- 30, 380 44- 47, 380277-286
• US Class Current: 380/278
• CPC Class Codes: H04L 9/0844 with user authentication or key authentication, e.g. ElGamal, MTI, MQV-Menezes-Qu-Vanstone protocol or Diffie-Hellman protocols using implicitly-certified keys

Abstract

This invention relates to a method for generating a shared secret value between entities in a data communication system, one or more of the entities having a plurality of members for participation in the communication system, each member having a long term private key and a corresponding long term public key. The method comprises the steps of generating a short term private and a corresponding short term public key for each of the members; exchanging short term public keys of the members within an entity. For each member then computing an intra-entity shared key by mathematically combining the short term public keys of each the members computing an intra-entity public key by mathematically combining its short-term private key, the long term private key and the intra-entity shared key. Next, each entity combines intra-entity public keys to derive a group short-term S_i public key; each entity transmitting its intra-entity shared key and its group short term public key to the other entities; and each entity computing a common shared key K by combining its group short term public key (S_i), with the intra-entity shared key ({overscore (X)}_i), and a group short term public ({overscore (S)}_i) key received from the other entities.

Claims

1. A method for generating a shared secret value between entities (A, B) in a data communication system, one or more of said entities having a plurality of members (A_i, B_i) for participation in said communication system, each member having a long term private key and a corresponding long term public key said method comprising the steps of:

(a) generating an entity long term public key for each entity by combining the long term public keys of each members of the entity;

(b) generating a short term private and a corresponding short term public key for each of the members;

(c) making said short term public keys available to members within an entity;

(d) for each member;

i. computing an intra-entity shared key by mathematically combining said short term public keys of each said member;

ii. computing an intra-entity public key by mathematically combining its short-term private key, the long term private key and said intra-entity shared key;

(e) for each entity combining intra-entity public keys to derive a group short-term public key;

(f) each entity making its intra-entity shared key and its entity long term public key available to said other entities; and

(g) each entity computing a common shared key K by combining its group short term public key, with the intra-entity shared key, and an entity long term public key received from the other entity.

2. A method as defined in claim 1, said long term public key being derived from a generator point P and respective ones of said long term private keys.

3. A method as defined in claim 2, said step (a) including each member selecting a random integer x_i and multiplying said point P by a to obtain x_iP, the short term public key.

4. A method as defined in claim 3, said intra-entity-shared key being computed by summing said short term public keys.

5. A method as defined in claim 4, said intra-entity public key s_i being derived by computing s_i=x_i+a_if(Σ

x_iP), where f is a hash function.

6. A method as defined in claim 5, said group short tern public key being derived by computing Σ

s_i.

7. A method as defined in claim 1, said long term public keys being derived from a generator g and respective ones of said long term private keys.

8. A method as defined in claim 7, said step (a) including the step of each member selecting a random integer (x_ij) and exponentiating a function h(g) including said generator to a power g(x_ij) to obtain the short term public key X_y=h(g)^g(xij).

9. A method as defined in claim 8, said intra-entity shared key (X_i) being computed by each entity multiplying each or its short-term public keys X_ij together.

10. A method as defined in claim 1, including the step of exchanging the entity long term public key between entities.