# US 8,280,059 B2 · Method, system and device for generating group key

> Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt

- Number: US 8,280,059 B2
- Document ID: US8280059B2
- Status: Granted
- Kind: B2
- Application number: 12/603,920
- Filed: 2009-10-22
- Published: 2010-02-18
- Granted: 2012-10-02
- Earliest claimed: 2007-06-08
- Assignees: Huawei Technologies Co., Ltd.
- Inventors: Chunxiang Xu; Huan Zhong; Ya Liu
- Web page: https://patentgrep.com/patent/US8280059B2

## CPC

- H04L 9/0841: {involving Diffie-Hellman or related key agreement protocols}
- H04L 9/0833: {involving conference or group key (network architectures or network communication protocols for key management in group communication in a packet data network H04L63/065)}
- H04L: TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION (arrangements common to telegraphic and telephonic communication H04M)

## Abstract

A method for generating a group key are provided in the field of network communications. The method includes the following steps: Group members select DH secret values and generate DH public values. An organizer generates an intermediate message and broadcasts a DH public value and the intermediate message. The group members generate a group key according to a DH secret value selected by the organizer and DH public values of the other group members except the organizer. A system for generating a group key and communication devices are also disclosed in the present invention.

## Claims

### Claim 1

A method for generating a group key, wherein system parameters are selected based on an elliptic curve, the method comprising:
forming, by group members, a star-shaped structure, and selecting an organizer from the group members;
randomly selecting, by the group members, DH secret values according to the system parameters individually, generating DH public values individually according to the system parameters and the selected DH secret values, and broadcasting the DH public values in the group;
selecting, by the organizer, a secret exponent after receiving the DH public values of the other group members, computing an intermediate message DH value according to the secret exponent, generating an intermediate message carrying the intermediate message DH value, broadcasting the intermediate message in the group, and generating a group key according to the DH secret value selected by the organizer and the DH public values of the other group members; and
computing, by the other group members, the DH secret value selected by the organizer according to the intermediate message after receiving the intermediate message and the DH public value of the organizer, verifying the computed DH secret value selected by the organizer to be correct according to the received DH public value of the organizer, and generating a group key according to the DH secret value selected by the organizer and the DH public values of the other group members;
wherein the computing the intermediate message DH value according to the secret exponent further comprises:
computing the intermediate message DH value zP according to the secret exponent z, wherein the secret exponent z is a random number selected from a collection Zq of minimum non-negative residues obtained after integers are modulo q, q is a prime number among the system parameters, and P is a public base point in the system parameters;
wherein the generating the intermediate message carrying the intermediate message DH value further comprises:
extracting an x-coordinate x of the intermediate message DH value zP on the elliptic curve, and computing an organizer component r1x(mod p) of the intermediate message according to the DH secret value r1 selected by the organizer, wherein p is a prime number among the system parameters;
computing the other member components r2zP, r3zP, . . . rnzP of the intermediate message according to the secret exponent z and the DH public values Xi=riP broadcasted by the other group members except the organizer, wherein i=2, . . . , n, and n is the number of the group members; and
generating the intermediate message {c1, c2, . . . , cn}={r1x(mod p), r2zP, r3zP, . . . , rnzP} according to the organizer component of the intermediate message and the other member components of the intermediate message;
or
extracting a y-coordinate y of the intermediate message DH value zP on the elliptic curve, and computing an organizer component r1y(mod p) of the intermediate message according to the DH secret value r1 selected by the organizer, wherein p is a prime number among the system parameters;
computing the other member components r2zP, r3zP, rnzP of the intermediate message according to the secret exponent z and the DH public values Xi=riP broadcasted by the other group members except the organizer, wherein i=2, . . . , n, and n is the number of the group members; and
generating the intermediate message {c1, c2, . . . , cn}={r1y(mod p), r2zP, r3zP, . . . , rnzP} according to the organizer component of the intermediate message and the other member components of the intermediate message.

### Claim 2 (depends on 1)

The method according to claim 1, wherein the computing the DH secret value selected by the organizer according to the intermediate message further comprises:
computing the intermediate message DH value zP according to the intermediate message {c1, c2, . . . , cn}={r1x(mod p), r2zP, r3zP, . . . , rnzP} and the selected DH secret value ri, extracting the x-coordinate x of the intermediate message DH value zP on the elliptic curve, and computing the DH secret value r1=c1x−1(mod p) selected by the organizer; or
computing the intermediate message DH value zP according to the intermediate message {c1, c2, . . . , cn}={r1y(modp), r2zP, r3zP, . . . , rnzP} and the selected DH secret value ri, extracting the y-coordinate y of the intermediate message DH value zP on the elliptic curve, and computing the DH secret value r1=c1y−1(mod p) selected by the organizer.

### Claim 3

A method for generating a group key, wherein system parameters are selected based on an elliptic curve, the method comprising:
forming, by group members, a star-shaped structure, and selecting an organizer from the group members;
randomly selecting, by the group members, DH secret values according to the system parameters individually, generating DH public values individually according to the system parameters and the selected DH secret values, and broadcasting the DH public values in the group;
selecting, by the organizer, a secret exponent after receiving the DH public values of the other group members, computing an intermediate message DH value according to the secret exponent, generating an intermediate message carrying the intermediate message DH value, broadcasting the intermediate message in the group, and generating a group key according to the DH secret value selected by the organizer and the DH public values of the other group members; and
computing, by the other group members, the DH secret value selected by the organizer according to the intermediate message after receiving the intermediate message and the DH public value of the organizer, verifying the computed DH secret value selected by the organizer to be correct according to the received DH public value of the organizer, and generating a group key according to the DH secret value selected by the organizer and the DH public values of the other group members;
wherein when new members join the group, the method further comprises:
forming, by the new members and the group members, a new star-shaped structure;
randomly selecting, by the organizer and the new members, new DH secret values according to the system parameters individually, generating new DH public values individually according to the system parameters and the selected new DH secret values, and broadcasting the new DH public values in the group;
taking, by the organizer, an x-coordinate or y-coordinate of the group key as a new secret exponent after receiving the new DH public values, computing a new intermediate message DH value according to the new secret exponent, generating a new intermediate message carrying the new intermediate message DH value, broadcasting the new intermediate message in the group, and generating a new group key according to the new DH secret value selected by the organizer and the new DH public values of the new members; and
receiving, by the other group members except the organizer, the new intermediate message of the organizer, the new DH public value of the organizer, and the new DH public values of the new members, computing the new DH secret value selected by the organizer according to the new intermediate message, verifying the new computed DH secret value selected by the organizer to be correct according to the received new DH public value of the organizer, and generating a new group key according to the new DH secret value selected by the organizer and the new DH public values of the new group members.

### Claim 4 (depends on 3)

The method according to claim 3, wherein the generating the new intermediate message carrying the new intermediate message DH value further comprises:
extracting an x-coordinate x′ of the new intermediate message DH value z′P on the elliptic curve, and computing an organizer component r′1x′(mod p) of the new intermediate message according to the new DH secret value r′1 selected by the organizer, wherein p is a prime number among the system parameters, z′=xK, xK is an x-coordinate of the group key, and P is a public base point in the system parameters;
computing new member components r′n+1z′P, r′n+2z′P, . . . , r′n+1z′P of the new intermediate message according to the secret exponent z′ and the DH public values X′i=r′iP broadcasted by the new members, wherein i=n+1, . . . , n+t, n is the number of the group members before the new members join the group, and t is the number of the new members; and
generating the new intermediate message
{c′1, c′n+1, . . . , c′n+1}={r′1x′(mod p), r′n+1z′P, r′n+2z′P, . . . , r′n+1z′P} according to the organizer component of the new intermediate message and the new member components of the new intermediate message;
or
extracting a y-coordinate y′ of the new intermediate message DH value z′P on the elliptic curve, and computing an organizer component r′1y′(mod p) of the new intermediate message according to the new DH secret value r′1 selected by the organizer, wherein p is a prime number among the system parameters, z′=yK, yK is a y-coordinate of the group key, and P is a public base point in the system parameters;
computing new member components r′n+1z′P, r′n+2z′P, . . . , r′n+1z′P of the new intermediate message according to the secret exponent z′ and the DH public values X′i=r′iP broadcasted by the new members, wherein i=n+1, . . . n+t, n is the number of the group members before the new members join the group, and t is the number of the new members; and
generating the new intermediate message
{c′1, c′n+1, . . . , c′n+t}={r′1y′(mod p), r′n+1 z′P, r′n+2z′P, . . . , r′n+1z′P} according to the organizer component of the new intermediate message and the new member components of the new intermediate message.

### Claim 5 (depends on 3)

The method according to claim 3, wherein the generating the new group key according to the new DH secret value selected by the organizer and the new DH public values of the new members further comprises:
generating the group key K′=r′1(r′n+1P+r′n+2P+ . . . r′n+tP) according to the DH public values X′i=r′iP of the new members and the new DH secret value r1′ selected by the organizer, wherein i=n+1, . . . , n+t, n is the number of the group members before the new members join the group, t is the number of the new members, and P is the public base point in the system parameters.

### Claim 6

A method for generating a group key, wherein system parameters are selected based on an elliptic curve, the method comprising:
forming, by group members, a star-shaped structure, and selecting an organizer from the group members;
randomly selecting, by the group members, DH secret values according to the system parameters individually, generating DH public values individually according to the system parameters and the selected DH secret values, and broadcasting the DH public values in the group;
selecting, by the organizer, a secret exponent after receiving the DH public values of the other group members, computing an intermediate message DH value according to the secret exponent, generating an intermediate message carrying the intermediate message DH value, broadcasting the intermediate message in the group, and generating a group key according to the DH secret value selected by the organizer and the DH public values of the other group members; and
computing, by the other group members, the DH secret value selected by the organizer according to the intermediate message after receiving the intermediate message and the DH public value of the organizer, verifying the computed DH secret value selected by the organizer to be correct according to the received DH public value of the organizer, and generating a group key according to the DH secret value selected by the organizer and the DH public values of the other group members;
wherein when members leave the group, the method further comprises:
selecting, by the organizer, a new DH secret value according to the system parameters, generating a new DH public value according to the system parameters and the selected new DH secret value, and broadcasting the new DH public value in the group;
selecting, by the organizer, a new secret exponent, computing a new intermediate message DH value according to the new secret exponent, generating a new intermediate message carrying the new intermediate message DH value, broadcasting the new intermediate message in the group, and generating a new group key according to the new DH secret value selected by the organizer and DH public values of the remaining group members except the organizer; and
computing, by the remaining group members except the organizer, the new DH secret value selected by the organizer according to the new intermediate message after receiving the new intermediate message and the new DH public value of the organizer, verifying the new DH secret value to be correct according to the received new DH public value of the organizer, and generating a new group key according to the new DH secret value and the DH public values of the remaining group members except the organizer.

### Claim 7 (depends on 6)

The method according to claim 6, wherein the generating the new intermediate message carrying the new intermediate message DH value further comprises:
extracting an x-coordinate x′ of the new intermediate message DH value z′P on the elliptic curve, and computing an organizer component r′1x′(mod p) of the new intermediate message according to the new DH secret value r′1 selected by the organizer, wherein p is a prime number among the system parameters;
computing remaining-member components
r′2z′P, . . . , r′jt−1z′P, r′jt+1z′P, . . . , r′jk−1z′P, r′jk+1z′P, . . . , r′nz′P of the new intermediate message according to the secret exponent z and the DH public values X′i=r′iP broadcasted by the remaining group members except the organizer, wherein i=2, . . . , j1−1, j1+1, . . . , jk−1, jk+1, . . . n, and k is the number of the members that leave the group; and
generating the new intermediate message
{c′1, . . . , c′j1−1, c′j1+1, . . . , c′jk−1, c′jk+1, . . . , c′n}={r′1x′(mod p), . . . r′j1−1z′P, r′j1+1z′P, . . . , r′jk−1z′P, r′jk+1z′P, . . . , r′nz′P} according to the organizer component of the new intermediate message and the remaining-member components of the new intermediate message;
or
extracting a y-coordinate y′ of the new intermediate message DH value z′P on the elliptic curve, and computing an organizer component r′1y′(mod p) of the new intermediate message according to the new DH secret value r′1 selected by the organizer, wherein p is a prime number among the system parameters;
computing remaining-member components
r′2z′P, . . . , r′j1−1z′P, r′j1+1z′P, . . . , r′jk−1z′P, r′jk+1z′P, . . . , r′nz′P of the new intermediate message according to the secret exponent z′ and the DH public values X′i=r′iP broadcasted by the remaining group members except the organizer, wherein i=2, . . . , j1−1, j1+1, . . . , jk−1, jk+1, . . . n, and k is the number of the members that leave the group; and
generating the new intermediate message
{c′1, . . . , c′j1−1, c′j1+1, . . . , c′jk−1, c′jk+1, . . . , c′n}={r′1y′(mod p), . . . , r′jt−1z′P, r′j1+1z′P, . . . , r′kk−1z′P, r′jk+1z′P, . . . , r′nz′P} according to the organizer component of the new intermediate message and the remaining-member components of the new intermediate message.
