Method, system and device for generating group key

FIELD OF THE INVENTION

0001The present invention relates to the field of network communications, and more particularly to a method, a system, and a device for generating a group key.

BACKGROUND OF THE INVENTION

0002An Ad Hoc network is a multi-hop self-organizing network with a dynamically changing topological structure, in which nodes are frequently moved and power-limited, and a trust relationship and wireless transmission links among the nodes are rather poor. Thus, the design of a group key negotiation protocol in the Ad Hoc network is significantly different from the conventional solution. In the Ad Hoc network, in order to ensure the communication security, messages are generally encrypted and then transmitted. Due to the advantage of a symmetric cryptosystem in efficiency, the complexity of message processing is reduced greatly by sharing a key in the group. Meanwhile, the Ad hoc network is also a dynamic peer group, and it lacks the support of a fixed trustable third party, so that a group session key for encrypting the messages needs to be established through the negotiation of all group members, so as to improve the security and reliability of the group session key. Furthermore, the group key negotiation protocol in the Ad Hoc network is required to take the dynamic topology characteristics of the network into consideration, and to realize the forward security and backward security of the key and efficiently support the joining and leaving motions of nodes.

0003All the existing group key negotiation solutions are based on the discrete logarithm problem in the finite field. There is a group key negotiation solution applicable to the Ad Hoc network, in which <i>n</i> represents the number of group members; <i>U_i</i> represents a group member with a serial number of <i>i</i>; <i>U</i>₁ represents a selected organizer, and the organizer is temporary and may be played by any member. <figref idref="f0001">FIG. 1</figref> is a flow chart of a method of a group key negotiation solution in the prior art. Referring to <figref idref="f0001">FIG. 1</figref>, the group key negotiation solution includes: <ul id="ul0001" list-style="none"><li>101: System parameters are selected, and a system initialization is performed. Supposed that <i>p</i> and <i>q</i> are large prime numbers, <i>Z_p</i> is a collection formed by the integer modulo <i>p</i>, g is an element in <i>Z_p,</i> and an order of g is q, in which q is the minimum positive integer that satisfies an equation <i>g^q</i> ≡ 1 mod <i>q</i>.</li><li>102: All members select DH secret values, generate DH public values according to the DH secret values, and broadcast the generated DH public values in the group. The group member <i>U_i</i> randomly selects a DH secret value <i>r_i</i> ∈ <i>Z_q</i>, generates a DH public value <i>g^{r<sub2>i</sub2>}</i> according to the selected DH secret value, and broadcasts the generated DH public value <i>g^{r<sub2>i</sub2>}</i> in the group, in which i goes through 1, 2, ..., <i>n</i>.</li><li>103: After receiving the DH public values of the other members, an organizer selects a secret exponent, generates an intermediate message according to the secret exponent and the DH public values, and broadcasts the intermediate message in the group, and meanwhile generates a group key. The organizer <i>U</i>₁ randomly selects a secret exponent <i>v</i> ∈ <i>Z_q</i>, generates an intermediate message <i>M_i</i>, <i>M_i = v·g^{r<sub2>1</sub2>r<sub2>i</sub2>}</i> according to the secret exponent, a DH public value of the organizer itself, and the DH public values of the other members respectively, and broadcasts the generated message <i>M_i</i> in the group, in which <i>i</i> goes through 1, 2, ..., <i>n</i>. Specifically, the organizer computes a function <i>F</i> = <i>f</i>(<i>g^{r<sub2>1</sub2>}</i>, <i>g</i>^{<i>r</i><sub2>2</sub2>}<i>,....,g^{r<sub2>n</sub2>}</i>) according to the DH public value of each member and the DH public value of the organizer itself, in which <i>f</i> represents a mapping from <i>Z_p</i> to <i>Z_q,</i> and then generates a group key <i>K</i> = <i>g^Fov</i> according to the secret exponent <i>v</i>.</li><li>104: After receiving the intermediate message broadcasted by the organizer, each group member extracts the secret exponent and generates a group key according to the secret exponent and the DH public value of each member.</li></ul>

0004After receiving <i>M_i</i>, all the group members <i>U_i</i> decrypt the <i>v</i> value, and compute the function <i>F</i> = <i>f</i> (<i>g</i>^{<i>r</i><sub2>1</sub2>}<i>,g</i>^{<i>r</i><sub2>2</sub2>}<i>,...,g^{r<sub2>n</sub2>}</i>)<i>,</i> in which <i>f</i> represents a mapping from <i>Z_p</i> to <i>Z_q</i>. Then, the group members <i>U_i</i> compute a group key <i>K</i> = <i>g^{F<sub2>ov</sub2>}</i> , in which the symbol o represents that <i>F</i> and <i>v</i> are mathematically operated and a result thereof needs to be modulo <i>p</i>.

0005Through the above steps, the group keys computed by all the group members <i>U_i</i> are the same, that is, the group key <i>K</i> = <i>g^Fov</i>.

0006When a member joins or leaves the group, it is required to re-generate a group key according to all the current group members after the change of group members, in which the computation is similar to the above process, and will not be repeated herein.

0007In the implementation of the present invention, the inventors find that the group key negotiation solution of the Ad Hoc network requires a large amount of computation, and thus has a low processing speed, a large storage space and a high bandwidth requirement.

0008<nplcit id="ncit0001" npl-type="b"><text>Li, D.; Sampalli, S.: "An Efficient Group Key Establishment In Location-Aided mobile ad hoc Networks", ACM, 2005, pages 57-64</text></nplcit> describes two scalable maximum matching algorithms (M2) to deploy binary tree-based group key agreements in MANETs. Furthermore, the proposed technique is lightweight since it uses the Elliptic Curve Diffie-Hellman key exchange in place of the regular Diffie-Hellman and also does not require third-paity's support.

0009Document XP002667535 discloses citations from the <nplcit id="ncit0002" npl-type="b"><text>Handbook of Applied Cryptography (Menezes, Vanstone, Oorschot, USA, 1997</text></nplcit>) and in particular the generation of a group key via Diffe Hellmann approach applied to three or more parties, which functionally form a star-shaped structure.

SUMMARY OF THE INVENTION

0010In order to reduce the amount of computation and the occupied storage space, and lower the bandwidth requirement of the group key negotiation solution, the present invention provides a method, a system, and devices for generating a group key. The technical solutions are described as follows.

0011As a first aspect of the invention the method for generating a group key selects system parameters based on an elliptic curve, and in respective implementation forms of the method the following steps are carried out.

0012Group members form a star-shaped structure and select an organizer from the group members.

0013The group members individually select DH secret values randomly according to the system parameters, individually generate DH public values according to the system parameters and the selected DH secret values, and broadcast the DH public values in the group.

0014After receiving the DH public values of the other group members, the organizer selects a secret exponent, computes an intermediate message DH value according to the secret exponent, generates an intermediate message carrying the intermediate message DH value, broadcasts the intermediate message in the group, and generates a group key according to the DH secret value selected by the organizer and the DH public values of the other group members.

0015After receiving the intermediate message and a DH public value of the organizer, the other group members compute the DH secret value selected by the organizer according to the intermediate message, verify the computed DH secret value selected by the organizer to be correct according to the received DH public value of the organizer, and generate a group key according to the DH secret value selected by the organizer and the DH public values of the other group members.

0016As a second aspect of the invention the system for generating a group key includes a communication device as an organizer and a communication device as members. In respective implementation forms the following features are realized.

0017The communication device as the organizer is configured to select a DH secret value according to system parameters, generate a DH public value according to the system parameters and the selected DH secret value, and broadcast the DH public value in the group; and after receiving DH public values of the other devices, the communication device as the organizer is further configured to select a secret exponent, compute an intermediate message DH value according to the secret exponent, generate an intermediate message carrying the intermediate message DH value, broadcast the intermediate message in the group, and generate a group key according to the selected DH secret value and DH public values of all devices in the group.

0018The communication device as the members is configured to select DH secret values according to system parameters, generate DH public values according to the system parameters and the selected DH secret values, and broadcast the DH public values; and after receiving the DH public value and the intermediate message broadcasted by the communication device as the organizer, the communication device as the members is further configured to compute the DH secret value selected by the organizer according to the intermediate message, verify the computed DH secret value selected by the organizer to be correct, and then generate a group key according to the DH secret value selected by the organizer and the DH public values of all the devices in the group.

0019Furthermore, as a third aspect of the invention the communication device includes a system parameter selecting module, a DH public value generating and broadcasting module, an intermediate message generating and broadcasting module, and an organizer group key generating module. In respective implementation forms of the device the following features are realized.

0020The system parameter selecting module is configured to select system parameters based on an elliptic curve.

0021The DH public value generating and broadcasting module is configured to select a DH secret value according to the system parameters selected by the system parameter selecting module, generate a DH public value according to the system parameters and the selected DH secret value, and broadcast the DH public value.

0022The intermediate message generating and broadcasting module is configured to select a secret exponent after receiving DH public values broadcasted by other communication devices, compute an intermediate message DH value according to the secret exponent, generate an intermediate message carrying the intermediate message DH value according to the DH secret value selected by the DH public value generating and broadcasting module, and broadcast the intermediate message.

0023The organizer group key generating module is configured to receive the DH public values broadcasted by other communication devices, and generate a group key according to the DH secret value selected by the DH public value generating and broadcasting module and the DH public values broadcasted by other communication devices.

0024As a fourth aspect of the invention the communication device includes a system parameter selecting module, a DH public value generating and broadcasting module, and a member group key generating module. In respective implementation forms of the device the following features are realized.

0025The system parameter selecting module is configured to select system parameters based on an elliptic curve.

0026The DH public value generating and broadcasting module is configured to select DH secret values according to the system parameters selected by the system parameter selecting module, generate DH public values according to the system parameters and the selected DH secret values, and broadcast the DH public values.

0027The member group key generating module is configured to receive a DH public value and an intermediate message broadcasted by another communication device, compute a DH secret value selected by an organizer according to the intermediate message, verify the computed DH secret value selected by the organizer to be correct according to the DH public value broadcasted by the communication device that broadcasts the intermediate message, and generate a group key according to the DH secret value selected by the organizer and DH public values broadcasted by all the other communication devices except the communication device that broadcasts the intermediate message.

0028The technical solutions of the present invention are based on an elliptic curve cryptography system, in which an organizer safely transmits a secret exponent to the other group members via an intermediate message DH value shared with the other group members, and then all the members negotiate based on the public key cryptographic technique on an elliptic curve to obtain a group key. Compared with the prior art, the technical solutions of the present invention have advantages of a high computation speed, small storage space, and low network bandwidth requirement, while maintaining the same security.

BRIEF DESCRIPTION OF THE DRAWINGS

0029<ul id="ul0002" list-style="none"><li><figref idref="f0001">FIG. 1</figref> is a flow chart of a method for generating a group key in the prior art;</li><li><figref idref="f0002">FIG. 2</figref> is a flow chart of a method for generating a group key according to Embodiment 1 of the present invention;</li><li><figref idref="f0003">FIG. 3</figref> is a schematic view of a star-shaped structure formed by group members according to Embodiment 1 of the present invention;</li><li><figref idref="f0003">FIG. 4</figref> is a schematic view of a star-shaped structure formed by group members when new members join the group according to Embodiment 2 of the present invention;</li><li><figref idref="f0004">FIG. 5</figref> is a flow chart of a method for generating a group key when new members join the group according to Embodiment 2 of the present invention;</li><li><figref idref="f0005">FIG. 6</figref> is a schematic view of a star-shaped structure formed by group members when groups are combined according to Embodiment 3 of the present invention;</li><li><figref idref="f0006">FIG. 7</figref> is a flow chart of a method for generating a group key when groups are combined according to Embodiment 3 of the present invention;</li><li><figref idref="f0007">FIG. 8</figref> is a structural view of a system for generating a group key according to Embodiment 6 of the present invention;</li><li><figref idref="f0007">FIG. 9</figref> is a structural view of a communication device according to Embodiment 7 of the present invention; and</li><li><figref idref="f0008">FIG. 10</figref> is a structural view of another communication device according to Embodiment 8 of the present invention.</li></ul>

DETAILED DESCRIPTION OF THE EMBODIMENT

0030In order to make the objects, technical solutions, and advantages of the present invention more comprehensible, embodiments of the present invention are further described in detail as follows with reference to the accompanying drawings.

0031The embodiments of the present invention provide a method, a system, and a device for generating a group key, which are applicable to an Ad Hoc network. Specifically, group members form a star-shaped structure, and a member is selected to be an organizer, who is responsible for safely transmitting a secret exponent to the other group members via an intermediate message DH value shared with the other group members, and then all the members negotiate based on the public key cryptographic technique on an elliptic curve to obtain a group key. The intermediate message DH value is a parameter obtained based on a Diffie-Hellman key negotiation protocol (briefly referred to as a DH key negotiation protocol) on the elliptic curve.

0032The embodiments of the present invention are based on an elliptic curve cryptography system. Elliptic curve cryptography (ECC) was set forth by Neal Koblitz and Victor Miller in the year of 1985. The elliptic curve cryptography system has advantages of a high security, low computation load, short key length, high processing speed, small occupied storage space, low bandwidth requirement and so on, thus has a wide application prospect in the field of security. Recently, the elliptic curve cryptography system has been accepted as a standard by standardization organizations, such as American National Standard Institute (ANSI), Institute of Electrical and Electronics Engineers (IEEE), International Standardization Organization (ISO), and National Institute of Standards and Technology (NIST).

Embodiment 1

0033<figref idref="f0002">FIG. 2</figref> is a flow chart of a method for generating a group key according to an embodiment of the present invention. Referring to <figref idref="f0002">FIG. 2</figref>, the method includes: <ul id="ul0003" list-style="none"><li>201: Group members <i>U</i>₁, ..., <i>U_n</i> form a star-shaped structure, and an organizer is selected. According to the embodiment of the present invention, <i>n</i> represents the number of group members, and <i>U_i</i> represents a group member with a serial number <i>i</i> (<i>i</i>=1, 2, ..., <i>n</i>). A group member is selected as an organizer, and in this embodiment <i>U</i>₁ is selected as the organizer. The organizer is not trusty, but is temporary, which can be played by any member. <figref idref="f0003">FIG. 3</figref> is a schematic view of a star-shaped structure formed by group members.</li><li>202: System parameters are selected, and a system initialization is performed. The specific process is described as follows. <i>GF</i>(<i>p</i>) is a finite field with an order as a prime number <i>p</i>, and an elliptic curve <i>EC</i>: <i>y²</i>=<i>x³</i>+<i>ax</i>+<i>β</i> (<i>a,β</i>∈<i>GF</i>(<i>p</i>), <i>4a³+27β²</i>(mod <i>p</i>)≠0; and <i>p</i> is a large prime number of above 190 bits) is defined in the field. <i>ECp(a, β</i>) <i>=</i>{(<i>x</i>,<i>y</i>)|<i>y</i>²=<i>x</i>³+<i>ax</i>+<i>β</i> (mod <i>p</i>)} ∪ <i>O</i> (<i>O</i> is the identity) forms an Abel group - commutative group. As for a given ECC system, a point <i>P</i>∈<i>EC_p</i>(<i>α,β</i>) is selected as a public base point, and the order of <i>P</i> is a large prime number <i>q</i> (generally, <i>q</i>≥120 bits). It is defined <i>G</i> = {<i>O</i>, <i>P, 2P,</i> ..., (<i>q</i>-1)<i>P</i>}. Thus, it can be known that <i>G</i> is a finite cyclic Abel group, and <i>q</i> is a cyclic period.</li><li>203: A group member <i>U_i</i> selects a DH secret value <i>r_i</i>∈<i>Z_q</i> according to the system parameters, generates a DH public value <i>X_i</i> = (<i>x_i, y_i</i>)= <i>r_iP</i> according to the DH secret value <i>r_i</i> and the public base point <i>P</i>, and broadcasts the DH public value <i>X_i</i> = (<i>x_i, y_i</i>)= <i>r_iP</i> in the group, in which <i>i</i> goes through 1, ..., <i>n.</i></li><li>204: After receiving DH public values <i>X_i</i> broadcasted by the other members, the organizer <i>U</i>₁ randomly selects a secret exponent <i>z</i>∈<i>Z_q</i> (<i>Z_q</i> is a collection of minimum non-negative residues obtained after integers are modulo <i>q</i>, and <i>q</i> is a prime number among the system parameters), computes an intermediate message DH value <i>zP</i>=(<i>x</i>, <i>y</i>) based on the Diffie-Hellman key negotiation protocol on the Elliptic-Curve, generates an intermediate message {<i>c</i>₁, <i>c</i>₂, ..., <i>c_n</i>}={<i>r</i>₁x(mod <i>p</i>), <i>r</i>₂<i>zP, r</i>₃<i>zP,</i> ..., <i>r_nzP</i>}<i>,</i> in which <i>p</i> is a prime number among the system parameters, according to the received DH public values of the other members, the selected secret exponent z, the DH secret value <i>r</i>₁, and the x-coordinate of the intermediate message DH value <i>zP</i>, broadcasts the intermediate message {<i>c</i>₁, <i>c</i>₂<i>,</i> ..., <i>c_n</i>} ={<i>r</i>₁<i>x</i>(mod <i>p</i>), <i>r₂zP, r₃zP, ..., r_nzP</i>} in the group; generates a group key <i>K</i>=<i>r₁(r₂P</i>+<i>r₃P</i>+... +<i>r_nP</i>) according to the DH secret value <i>r</i>₁ selected by the organizer itself and the DH public values of the other members. It should be noted that, in this embodiment, the intermediate message may also be generated according to the received DH public values of the other members; the selected secret exponent <i>z</i>, the DH secret value <i>r</i>₁, and the y-coordinate of the intermediate message DH value <i>zP</i>. The specific principle is similar to that of generating the intermediate message according to the received DH public values of the other members, the selected secret exponent <i>z</i>, the DH secret value <i>r</i>₁, and the x-coordinate of the intermediate message DH value <i>zP</i>, and will not be repeated herein.</li><li>205: After receiving the intermediate message broadcasted by the organizer <i>U</i>₁, the group member <i>U_i</i>(<i>i</i> goes through 2, 3, ..., <i>n</i>) extracts the intermediate message DH value in the intermediate message, in which the intermediate message DH value <i>zP</i> is specifically obtained by computing <i>zP</i>= (<i>x</i>,<i>y</i>) = <i>r_i^-1c_i,</i> and then, according to the intermediate message DH value <i>zP</i>=(<i>x, y</i>), the x is obtained. As <i>c₁=r₁x</i>(<i>mod p</i>), <i>r</i>₁ = <i>c</i>₁<i>x</i>^-1 (mod <i>p</i>)<i>,</i> so that the DH secret value <i>r</i>₁ selected by the organizer is computed.</li><li>206: After computing the DH secret value <i>r</i>₁ selected by the organizer, the group member <i>U_i</i> (<i>i</i> goes through 2, 3, ..., <i>n</i>) verifies whether an equation <i>r</i>₁<i>P</i>=<i>X</i>₁ is satisfied or not, and if yes, 207 is executed; otherwise, 203 is re-executed. The verification of the equation <i>r</i>₁<i>P</i>=<i>X</i>₁ aims at verifying whether the DH secret value selected by the organizer is tampered or not.</li><li>207: The group member <i>U_i</i> (<i>i</i> goes through 2, 3, ..., <i>n</i>) generates a group key <i>K</i>=<i>r</i>₁(<i>r</i>₁<i>P</i>+<i>r</i>₃<i>P</i>+... +<i>r_nP</i>) according to the DH secret value selected by the organizer and the DH public values of all the other group members except the organizer.</li></ul>

0034Through the above process, the group keys computed by all the group members <i>U_i</i> are the same, that is, the group key <i>K</i>=<i>r</i>₁(<i>r</i>₂<i>P</i>+<i>r</i>₃<i>P</i>+<i>...</i>+<i>r_nP</i>), and all the members reserve the <i>X_i</i> values received in the key negotiation stage.

Embodiment 2

0035In this embodiment, a method for generating a group key through negotiation when new members join the group is provided. This embodiment is based on Embodiment 1. It is assumed that the group Σ={<i>U</i>₁<i>, U</i>₂, <i>..., U_n</i>} has executed the basic negotiation of Embodiment 1 and has obtained the shared group key <i>K</i>=<i>r</i>₁(<i>r</i>₂<i>P</i>+<i>r</i>₃<i>P</i>+... +<i>r_nP</i>)<i>.</i> Now, <i>t</i> members are intended to join the group Σ, which are respectively represented as <i>U</i>_<i>n</i>+1,<i>U</i>_<i>n+</i>2<i>,</i> ..., U_n+<i>t</i>. The negotiation process about a new key requires the newly-added <i>t</i> members and the organizer <i>U</i>₁ to participate in. Referring to <figref idref="f0003">FIG 4</figref>, <i>U</i>₁, <i>V₂, ..., U_n+t</i> together form a star-shaped structure.

0036<figref idref="f0004">FIG. 5</figref> is a flow chart of a method for generating a group key when new members join the group. Referring to <figref idref="f0004">FIG. 5</figref>, the method for generating a group key when new members join the group includes: <ul id="ul0004" list-style="none"><li>301: The organizer <i>U</i>₁ and new member <i>U_i</i> select DH secret values r^'_i according to the system parameters, generate DH public values <maths id="math0001"><math display="inline"><msubsup><mi>X</mi><mi>i</mi><mi>ʹ</mi></msubsup><mo>=</mo><mfenced><msubsup><mi>x</mi><mi>i</mi><mi>ʹ</mi></msubsup><msubsup><mi>y</mi><mi>i</mi><mi>ʹ</mi></msubsup></mfenced><mo>=</mo><msubsup><mi>r</mi><mi>i</mi><mi>ʹ</mi></msubsup><mo>⁢</mo><mi>P</mi></math><img file="EP2124381B1_D0001.tif" /></maths> according to the DH secret values <maths id="math0002"><math display="inline"><msubsup><mi>r</mi><mi>i</mi><mi>ʹ</mi></msubsup></math><img file="EP2124381B1_D0002.tif" /></maths> and the public base point <i>P</i>, and broadcast the DH public values <maths id="math0003"><math display="inline"><msubsup><mi>X</mi><mi>i</mi><mi>ʹ</mi></msubsup><mo>=</mo><mfenced><msubsup><mi>x</mi><mi>i</mi><mi>ʹ</mi></msubsup><msubsup><mi>y</mi><mi>i</mi><mi>ʹ</mi></msubsup></mfenced><mo>=</mo><msubsup><mi>r</mi><mi>i</mi><mi>ʹ</mi></msubsup><mo>⁢</mo><mi>P</mi></math><img file="EP2124381B1_D0003.tif" /></maths> in the group, in which <i>i</i> goes through <i>n</i>+1, ..., <i>n</i>+<i>t.</i></li><li>302: After receiving the DH public values <maths id="math0004"><math display="inline"><msubsup><mi>X</mi><mi>i</mi><mi>ʹ</mi></msubsup></math><img file="EP2124381B1_D0004.tif" /></maths> broadcasted by the new members, supposed that a secret exponent z' = <i>x_K</i>, the organizer <i>U</i>₁ computes an intermediate message DH value <i>z'P</i> = (<i>x', y'</i>) based on Diffie-Hellman key negotiation protocol on the Elliptic-Curve, generates an intermediate message <maths id="math0005"><math display="inline"><mfenced open="{" close="}"><msubsup><mi>c</mi><mn>1</mn><mi>ʹ</mi></msubsup><msubsup><mi>c</mi><mrow><mi>n</mi><mo>+</mo><mn>1</mn></mrow><mi>ʹ</mi></msubsup><mo>⋯</mo><msubsup><mi>c</mi><mrow><mi>n</mi><mo>+</mo><mi>t</mi></mrow><mi>ʹ</mi></msubsup></mfenced><mo>=</mo><mfenced open="{" close="}"><msubsup><mi>r</mi><mn>1</mn><mi>ʹ</mi></msubsup><mo>⁢</mo><mi mathvariant="italic">xʹ</mi><mfenced><mi>mod</mi><mspace width="1em" /><mi>p</mi></mfenced><mo>,</mo><msubsup><mi>r</mi><mrow><mi>n</mi><mo>+</mo><mn>1</mn></mrow><mi>ʹ</mi></msubsup><mo>⁢</mo><mi mathvariant="italic">zʹP</mi><mo>,</mo><msubsup><mi>r</mi><mrow><mi>n</mi><mo>+</mo><mn>2</mn></mrow><mi>ʹ</mi></msubsup><mo>⁢</mo><mi mathvariant="italic">zʹP</mi><mo>,</mo><mo>⋯</mo><mo>,</mo><msubsup><mi>r</mi><mrow><mi>n</mi><mo>+</mo><mi>t</mi></mrow><mi>ʹ</mi></msubsup><mo>⁢</mo><mi mathvariant="italic">zʹP</mi></mfenced></math><img file="EP2124381B1_D0005.tif" /></maths> carrying the intermediate message DH value broadcasts the intermediate message <maths id="math0006"><math display="inline"><mfenced open="{" close="}"><msubsup><mi>c</mi><mn>1</mn><mi>ʹ</mi></msubsup><msubsup><mi>c</mi><mrow><mi>n</mi><mo>+</mo><mn>1</mn></mrow><mi>ʹ</mi></msubsup><mo>⋯</mo><msubsup><mi>c</mi><mrow><mi>n</mi><mo>+</mo><mi>t</mi></mrow><mi>ʹ</mi></msubsup></mfenced><mo>=</mo><mfenced open="{" close="}"><msubsup><mi>r</mi><mn>1</mn><mi>ʹ</mi></msubsup><mo>⁢</mo><mi mathvariant="italic">xʹ</mi><mfenced><mi>mod</mi><mspace width="1em" /><mi>p</mi></mfenced><mo>,</mo><msubsup><mi>r</mi><mrow><mi>n</mi><mo>+</mo><mn>1</mn></mrow><mi>ʹ</mi></msubsup><mo>⁢</mo><mi mathvariant="italic">zʹP</mi><mo>,</mo><msubsup><mi>r</mi><mrow><mi>n</mi><mo>+</mo><mn>2</mn></mrow><mi>ʹ</mi></msubsup><mo>⁢</mo><mi mathvariant="italic">zʹP</mi><mo>,</mo><mo>⋯</mo><mo>,</mo><msubsup><mi>r</mi><mrow><mi>n</mi><mo>+</mo><mi>t</mi></mrow><mi>ʹ</mi></msubsup><mo>⁢</mo><mi mathvariant="italic">zʹP</mi></mfenced></math><img file="EP2124381B1_D0006.tif" /></maths> in the group, and generates a new group key <maths id="math0007"><math display="inline"><mi mathvariant="italic">Kʹ</mi><mo>=</mo><msubsup><mi>r</mi><mn>1</mn><mi>ʹ</mi></msubsup><mo>⁢</mo><mfenced><msubsup><mi>r</mi><mrow><mi>n</mi><mo>+</mo><mn>1</mn></mrow><mi>ʹ</mi></msubsup><mo>⁢</mo><mi mathvariant="italic">P</mi><mo mathvariant="italic">+</mo><msubsup><mi>r</mi><mrow><mi>n</mi><mo>+</mo><mn>2</mn></mrow><mi>ʹ</mi></msubsup><mo>⁢</mo><mi mathvariant="italic">P</mi><mo>,</mo><mo>⋯</mo><mo>,</mo><msubsup><mi>r</mi><mrow><mi>n</mi><mo>+</mo><mi>t</mi></mrow><mi>ʹ</mi></msubsup><mo>⁢</mo><mi mathvariant="italic">P</mi></mfenced></math><img file="EP2124381B1_D0007.tif" /></maths> according to the DH secret value <maths id="math0008"><math display="inline"><msubsup><mi>r</mi><mn>1</mn><mi>ʹ</mi></msubsup></math><img file="EP2124381B1_D0008.tif" /></maths> selected by the organizer itself and the DH public values of the new members. In this embodiment, <i>x_K</i> represents an x-coordinate of the key <i>K</i> shared by Σ= {<i>U</i>₁, <i>U</i>₂, ..., <i>U_n</i>}, and all the group members know that the organizer <i>U</i>₁ selects the x-coordinate or the y-coordinate as <i>z'</i> in advance. The organizer <i>U</i>₁ selects the x-coordinate as <i>z'</i> , and may also supposed that <i>z</i>' = <i>y_K,</i> that is, the organizer <i>U</i>₁ selects the y-coordinate as <i>z</i>'.</li><li>303: After receiving the intermediate message <maths id="math0009"><math display="inline"><mfenced open="{" close="}"><msubsup><mi>c</mi><mn>1</mn><mi>ʹ</mi></msubsup><msubsup><mi>c</mi><mrow><mi>n</mi><mo>+</mo><mn>1</mn></mrow><mi>ʹ</mi></msubsup><mo>⋯</mo><msubsup><mi>c</mi><mrow><mi>n</mi><mo>+</mo><mi>t</mi></mrow><mi>ʹ</mi></msubsup></mfenced><mo>=</mo><mfenced open="{" close="}"><msubsup><mi>r</mi><mn>1</mn><mi>ʹ</mi></msubsup><mo>⁢</mo><mi mathvariant="italic">xʹ</mi><mfenced><mi>mod</mi><mspace width="1em" /><mi>p</mi></mfenced><mo>,</mo><msubsup><mi>r</mi><mrow><mi>n</mi><mo>+</mo><mn>1</mn></mrow><mi>ʹ</mi></msubsup><mo>⁢</mo><mi mathvariant="italic">zʹP</mi><mo>,</mo><msubsup><mi>r</mi><mrow><mi>n</mi><mo>+</mo><mn>2</mn></mrow><mi>ʹ</mi></msubsup><mo>⁢</mo><mi mathvariant="italic">zʹP</mi><mo>,</mo><mo>⋯</mo><mo>,</mo><msubsup><mi>r</mi><mrow><mi>n</mi><mo>+</mo><mi>t</mi></mrow><mi>ʹ</mi></msubsup><mo>⁢</mo><mi mathvariant="italic">zʹP</mi></mfenced></math><img file="EP2124381B1_D0009.tif" /></maths> broadcasted by the organizer <i>U</i>₁, the new member <i>U_i</i> (<i>i</i>∈{<i>n</i>+1, ..., <i>n</i>+<i>t</i>}) extracts the intermediate message DH value in the intermediate message, in which the intermediate message DH value <i>z'P</i> is specifically obtained by computing <maths id="math0010"><math display="inline"><mi mathvariant="italic">zʹP</mi><mo>=</mo><mfenced><mi mathvariant="italic">xʹ</mi><mi mathvariant="italic">yʹ</mi></mfenced><mo>=</mo><msubsup><mi>r</mi><mi>i</mi><mrow><mi>ʹ</mi><mo>-</mo><mn>1</mn></mrow></msubsup><mo>⁢</mo><msubsup><mi>c</mi><mi>i</mi><mi>ʹ</mi></msubsup><mo>,</mo></math><img file="EP2124381B1_D0010.tif" /></maths> and then, according to the intermediate message DH value <i>z'P</i> = (<i>x', y'</i>) , the <i>x'</i> is obtained. As <maths id="math0011"><math display="inline"><msubsup><mi>c</mi><mn>1</mn><mi>ʹ</mi></msubsup><mo>=</mo><msubsup><mi>r</mi><mn>1</mn><mi>ʹ</mi></msubsup><mo>⁢</mo><mi mathvariant="italic">xʹ</mi><mfenced><mi>mod</mi><mspace width="1em" /><mi>p</mi></mfenced><mo>,</mo></math><img file="EP2124381B1_D0011.tif" /></maths><maths id="math0012"><math display="inline"><msubsup><mi>r</mi><mn>1</mn><mi>ʹ</mi></msubsup><mo>=</mo><msubsup><mi>c</mi><mn>1</mn><mi>ʹ</mi></msubsup><mo>⁢</mo><msup><mi mathvariant="italic">xʹ</mi><mrow><mo>-</mo><mn>1</mn></mrow></msup><mfenced><mi>mod</mi><mspace width="1em" /><mi>p</mi></mfenced><mo>,</mo></math><img file="EP2124381B1_D0012.tif" /></maths> so that the DH secret value <maths id="math0013"><math display="inline"><msubsup><mi>r</mi><mn>1</mn><mi>ʹ</mi></msubsup></math><img file="EP2124381B1_D0013.tif" /></maths> selected by the organizer is computed.</li><li>304: After computing the DH secret value <maths id="math0014"><math display="inline"><msubsup><mi>r</mi><mn>1</mn><mi>ʹ</mi></msubsup></math><img file="EP2124381B1_D0014.tif" /></maths> selected by the organizer, the new member <i>U_i</i> (<i>i</i>∈{<i>n</i>+1, ..., <i>n</i>+<i>t</i>}) verifies whether the equation <maths id="math0015"><math display="inline"><msubsup><mi>r</mi><mn>1</mn><mi>ʹ</mi></msubsup><mo>⁢</mo><mi>P</mi><mo>=</mo><msubsup><mi>X</mi><mn>1</mn><mi>ʹ</mi></msubsup></math><img file="EP2124381B1_D0015.tif" /></maths> is satisfied or not, and if yes, 305 is executed; otherwise, 301 is re-executed. The verification of the equation <maths id="math0016"><math display="inline"><msubsup><mi>r</mi><mn>1</mn><mi>ʹ</mi></msubsup><mo>⁢</mo><mi>P</mi><mo>=</mo><msubsup><mi>X</mi><mn>1</mn><mi>ʹ</mi></msubsup></math><img file="EP2124381B1_D0016.tif" /></maths> aims at verifying whether the DH secret value selected by the organizer is tampered or not.</li><li>305: The new member <i>U_i</i> (<i>i ∈</i>{<i>n</i>+1, ..., <i>n</i>+<i>t</i>}) generates a new group key <maths id="math0017"><math display="inline"><mi mathvariant="italic">Kʹ</mi><mo>=</mo><msubsup><mi>r</mi><mn>1</mn><mi>ʹ</mi></msubsup><mo>⁢</mo><mfenced><msubsup><mi>r</mi><mrow><mi>n</mi><mo>+</mo><mn>1</mn></mrow><mi>ʹ</mi></msubsup><mo>⁢</mo><mi mathvariant="italic">P</mi><mo mathvariant="italic">+</mo><msubsup><mi>r</mi><mrow><mi>n</mi><mo>+</mo><mn>2</mn></mrow><mi>ʹ</mi></msubsup><mo>⁢</mo><mi mathvariant="italic">P</mi><mo>+</mo><mo>⋯</mo><msubsup><mi>r</mi><mrow><mi>n</mi><mo>+</mo><mi>t</mi></mrow><mi>ʹ</mi></msubsup><mo>⁢</mo><mi mathvariant="italic">P</mi></mfenced></math><img file="EP2124381B1_D0017.tif" /></maths> according to the DH secret value selected by the organizer and the DH public values of the new members.</li><li>306: The other members <i>U</i>₂, ..., <i>U_n</i> in the group Σ obtain <i>z'</i> = <i>x_K</i> according to the previous z value, compute <maths id="math0018"><math display="inline"><mi mathvariant="italic">zʹP</mi><mo>=</mo><mfenced><mi mathvariant="italic">xʹ</mi><mi mathvariant="italic">yʹ</mi></mfenced><mo>=</mo><msubsup><mi>r</mi><mi>i</mi><mrow><mi>ʹ</mi><mo>-</mo><mn>1</mn></mrow></msubsup><mo>⁢</mo><msubsup><mi>c</mi><mi>i</mi><mi>ʹ</mi></msubsup><mspace width="1em" /><mfenced><mi>i</mi><mo>∈</mo><mfenced open="{" close="}"><mn mathvariant="italic">2</mn><mo>…</mo><mi>n</mi></mfenced></mfenced><mo>,</mo></math><img file="EP2124381B1_D0018.tif" /></maths> and then get the x' according to the intermediate message DH value <i>z'P</i> = (<i>x', y'</i>). As <maths id="math0019"><math display="inline"><msubsup><mi>c</mi><mn>1</mn><mi>ʹ</mi></msubsup><mo>=</mo><msubsup><mi>c</mi><mn>1</mn><mi>ʹ</mi></msubsup><mo>⁢</mo><mi mathvariant="italic">xʹ</mi><mfenced><mi>mod</mi><mspace width="1em" /><mi>p</mi></mfenced><mo>,</mo></math><img file="EP2124381B1_D0019.tif" /></maths><maths id="math0020"><math display="inline"><msubsup><mi>r</mi><mn>1</mn><mi>ʹ</mi></msubsup><mo>=</mo><msubsup><mi>c</mi><mn>1</mn><mi>ʹ</mi></msubsup><mo>⁢</mo><msup><mi mathvariant="italic">xʹ</mi><mrow><mo>-</mo><mn>1</mn></mrow></msup><mfenced><mi>mod</mi><mspace width="1em" /><mi>p</mi></mfenced><mo>,</mo></math><img file="EP2124381B1_D0020.tif" /></maths> so that the DH secret value <maths id="math0021"><math display="inline"><msubsup><mi>r</mi><mn>1</mn><mi>ʹ</mi></msubsup></math><img file="EP2124381B1_D0021.tif" /></maths> selected by the organizer is computed. Then, according to the DH secret value <maths id="math0022"><math display="inline"><msubsup><mi>r</mi><mn>1</mn><mi>ʹ</mi></msubsup></math><img file="EP2124381B1_D0022.tif" /></maths> selected by the organizer and the DH public values of the new members, each of the other members <i>U</i>₂, <i>..., U_n</i> generates a new group key <maths id="math0023"><math display="inline"><mi mathvariant="italic">Kʹ</mi><mo>=</mo><msubsup><mi>r</mi><mn>1</mn><mi>ʹ</mi></msubsup><mo>⁢</mo><mfenced><msubsup><mi>r</mi><mrow><mi>n</mi><mo>+</mo><mn>1</mn></mrow><mi>ʹ</mi></msubsup><mo>⁢</mo><mi mathvariant="italic">P</mi><mo mathvariant="italic">+</mo><msubsup><mi>r</mi><mrow><mi>n</mi><mo>+</mo><mn>2</mn></mrow><mi>ʹ</mi></msubsup><mo>⁢</mo><mi mathvariant="italic">P</mi><mo>+</mo><mo>⋯</mo><msubsup><mi>r</mi><mrow><mi>n</mi><mo>+</mo><mi>t</mi></mrow><mi>ʹ</mi></msubsup><mo>⁢</mo><mi mathvariant="italic">P</mi></mfenced><mn>.</mn></math><img file="EP2124381B1_D0023.tif" /></maths></li></ul>

0037Through the above process, after the <i>t</i> members have joined the group Σ, each group member <i>U_i</i> (<i>i</i> ∈{1, ..., <i>n</i>+<i>t</i>}) computes a new group key <maths id="math0024"><math display="inline"><mi mathvariant="italic">Kʹ</mi><mo>=</mo><msubsup><mi>r</mi><mn>1</mn><mi>ʹ</mi></msubsup><mo>⁢</mo><mfenced><msubsup><mi>r</mi><mrow><mi>n</mi><mo>+</mo><mn>1</mn></mrow><mi>ʹ</mi></msubsup><mo>⁢</mo><mi mathvariant="italic">P</mi><mo mathvariant="italic">+</mo><msubsup><mi>r</mi><mrow><mi>n</mi><mo>+</mo><mn>2</mn></mrow><mi>ʹ</mi></msubsup><mo>⁢</mo><mi mathvariant="italic">P</mi><mo>+</mo><mo>⋯</mo><msubsup><mi>r</mi><mrow><mi>n</mi><mo>+</mo><mi>t</mi></mrow><mi>ʹ</mi></msubsup><mo>⁢</mo><mi mathvariant="italic">P</mi></mfenced><mo>,</mo></math><img file="EP2124381B1_D0024.tif" /></maths> and the newly-added <i>t</i> members reserve the <maths id="math0025"><math display="inline"><msubsup><mi>X</mi><mi>i</mi><mi>ʹ</mi></msubsup></math><img file="EP2124381B1_D0025.tif" /></maths> values received in the key negotiation stage.

0038For example, it is assumed that a group Σ = {<i>U</i>₁, ..., <i>U</i>₅} has executed the basic negotiation, and has obtained the shared key <i>K</i>=<i>r</i>₁(<i>r</i>₂<i>P</i>+<i>r</i>₃<i>P</i>+...+<i>r₅P</i>). A member <i>G'</i>={<i>U₆</i>} needs to join the group and shares a new key with members in the group Σ. According to the method in this embodiment, the key negotiation process requires <i>U</i>₁ to interact with the newly joined member <i>U</i>₆, such that all the group members are enabled to compute and obtain the new group key. In this example, after <i>U</i>₁, <i>U</i>₂, ..., <i>U</i>₆ together form a star-shaped structure, the following specific steps are executed. <ol id="ol0001"><li>(1) The organizer <i>U</i>₁ selects the DH secret value <maths id="math0026"><math display="inline"><msubsup><mi>r</mi><mn>1</mn><mi>ʹ</mi></msubsup><mo>∈</mo><msub><mi>Z</mi><mi>q</mi></msub></math><img file="EP2124381B1_D0026.tif" /></maths> according to the system parameters, and broadcasts the message <maths id="math0027"><math display="inline"><msubsup><mi>X</mi><mn>1</mn><mi>ʹ</mi></msubsup><mo>=</mo><mfenced><msubsup><mi>x</mi><mn>1</mn><mi>ʹ</mi></msubsup><msubsup><mi>y</mi><mn>1</mn><mi>ʹ</mi></msubsup></mfenced><mo>=</mo><msubsup><mi>r</mi><mn>1</mn><mi>ʹ</mi></msubsup><mo>⁢</mo><mi>P</mi></math><img file="EP2124381B1_D0027.tif" /></maths> to <i>U</i>₆. <i>U</i>₆ selects a DH secret value <maths id="math0028"><math display="inline"><msubsup><mi>r</mi><mn>6</mn><mi>ʹ</mi></msubsup><mo>∈</mo><msub><mi>Z</mi><mi>q</mi></msub></math><img file="EP2124381B1_D0028.tif" /></maths> according to the system parameters, and broadcasts a message <maths id="math0029"><math display="inline"><msubsup><mi>X</mi><mn>6</mn><mi>ʹ</mi></msubsup><mo>=</mo><mfenced><msubsup><mi>x</mi><mn>6</mn><mi>ʹ</mi></msubsup><msubsup><mi>y</mi><mn>6</mn><mi>ʹ</mi></msubsup></mfenced><mo>=</mo><msubsup><mi>r</mi><mn>6</mn><mi>ʹ</mi></msubsup><mo>⁢</mo><mi>P</mi></math><img file="EP2124381B1_D0029.tif" /></maths> to <i>U</i>₁.</li><li>(2) After receiving the DH public value <maths id="math0030"><math display="inline"><msubsup><mi>X</mi><mn>6</mn><mi>ʹ</mi></msubsup></math><img file="EP2124381B1_D0030.tif" /></maths> broadcasted by <i>U</i>₆, supposed that secret exponent <i>z</i>' = <i>x_K</i>, the organizer <i>U</i>₁ computes the intermediate message DH value <i>z'P</i> = (<i>x',y'</i>) based on Diffie-Hellman key negotiation protocol on the Elliptic-Curve, generates an intermediate message <maths id="math0031"><math display="inline"><mfenced open="{" close="}"><msubsup><mi>c</mi><mn>1</mn><mi>ʹ</mi></msubsup><msubsup><mi>c</mi><mn>6</mn><mi>ʹ</mi></msubsup></mfenced><mo>=</mo><mfenced open="{" close="}"><msubsup><mi>r</mi><mn>1</mn><mi>ʹ</mi></msubsup><mo>⁢</mo><mi mathvariant="italic">xʹ</mi><mfenced><mi>mod</mi><mspace width="1em" /><mi>p</mi></mfenced><mo>,</mo><msubsup><mi>r</mi><mn>6</mn><mi>ʹ</mi></msubsup><mo>⁢</mo><mi mathvariant="italic">zʹP</mi></mfenced></math><img file="EP2124381B1_D0031.tif" /></maths> carrying the intermediate message DH value, broadcasts the intermediate message <maths id="math0032"><math display="inline"><mfenced open="{" close="}"><msubsup><mi>c</mi><mn>1</mn><mi>ʹ</mi></msubsup><msubsup><mi>c</mi><mn>6</mn><mi>ʹ</mi></msubsup></mfenced><mo>=</mo><mfenced open="{" close="}"><msubsup><mi>r</mi><mn>1</mn><mi>ʹ</mi></msubsup><mo>⁢</mo><mi mathvariant="italic">xʹ</mi><mfenced><mi>mod</mi><mspace width="1em" /><mi>p</mi></mfenced><mo>,</mo><msubsup><mi>r</mi><mn>6</mn><mi>ʹ</mi></msubsup><mo>⁢</mo><mi mathvariant="italic">zʹP</mi></mfenced></math><img file="EP2124381B1_D0032.tif" /></maths> in the group, and generates a group key <maths id="math0033"><math display="inline"><mi mathvariant="italic">Kʹ</mi><mo>=</mo><msubsup><mi>r</mi><mn>1</mn><mi>ʹ</mi></msubsup><mo>⁢</mo><msubsup><mi>r</mi><mn>6</mn><mi>ʹ</mi></msubsup><mo>⁢</mo><mi>P</mi></math><img file="EP2124381B1_D0033.tif" /></maths> according to the DH secret value <maths id="math0034"><math display="inline"><msubsup><mi>r</mi><mn>1</mn><mi>ʹ</mi></msubsup></math><img file="EP2124381B1_D0034.tif" /></maths> selected by the organizer itself and the DH public value of <i>U</i>₆. In the example, <i>x_K</i> represents an x-coordinate of the key <i>K</i> shared by Σ={<i>U</i>₁, <i>U</i>₂, ..., <i>U</i>₅}.</li><li>(3) After receiving the intermediate message broadcasted by the organizer <i>U</i>₁<i>, U₆</i> extracts the intermediate message DH value in the intermediate message, in which the intermediate message DH value <i>z'P</i> is specifically obtained by computing <maths id="math0035"><math display="inline"><mi mathvariant="italic">zʹP</mi><mo>=</mo><mfenced><mi mathvariant="italic">xʹ</mi><mi mathvariant="italic">yʹ</mi></mfenced><mo>=</mo><msubsup><mi>r</mi><mn>6</mn><mrow><mi>ʹ</mi><mo>-</mo><mn>1</mn></mrow></msubsup><mo>⁢</mo><msubsup><mi>c</mi><mn>6</mn><mi>ʹ</mi></msubsup><mo>,</mo></math><img file="EP2124381B1_D0035.tif" /></maths> and then, according to the intermediate message DH value <i>z'P</i> = (<i>x',y'</i>), the <i>x</i>' is obtained. As <maths id="math0036"><math display="inline"><msubsup><mi>c</mi><mn>1</mn><mi>ʹ</mi></msubsup><mo>=</mo><msubsup><mi>r</mi><mn>1</mn><mi>ʹ</mi></msubsup><mo>⁢</mo><mi mathvariant="italic">xʹ</mi><mfenced><mi>mod</mi><mspace width="1em" /><mi>p</mi></mfenced><mo>,</mo></math><img file="EP2124381B1_D0036.tif" /></maths><maths id="math0037"><math display="inline"><msubsup><mi>r</mi><mn>1</mn><mi>ʹ</mi></msubsup><mo>=</mo><msubsup><mi>c</mi><mn>1</mn><mi>ʹ</mi></msubsup><mo>⁢</mo><msup><mi mathvariant="italic">xʹ</mi><mrow><mo>-</mo><mn>1</mn></mrow></msup><mfenced><mi>mod</mi><mspace width="1em" /><mi>p</mi></mfenced><mo>,</mo></math><img file="EP2124381B1_D0037.tif" /></maths>the DH secret value <maths id="math0038"><math display="inline"><msubsup><mi>r</mi><mn>1</mn><mi>ʹ</mi></msubsup></math><img file="EP2124381B1_D0038.tif" /></maths> selected by the organizer <i>U</i>₁ is computed.</li><li>(4) After computing the DH secret value <maths id="math0039"><math display="inline"><msubsup><mi>r</mi><mn>1</mn><mi>ʹ</mi></msubsup></math><img file="EP2124381B1_D0039.tif" /></maths> selected by the organizer <i>U</i>₁, <i>U₆</i> verifies whether the equation <maths id="math0040"><math display="inline"><msubsup><mi>r</mi><mn>1</mn><mi>ʹ</mi></msubsup><mo>⁢</mo><mi>P</mi><mo>=</mo><msubsup><mi>X</mi><mn>1</mn><mi>ʹ</mi></msubsup></math><img file="EP2124381B1_D0040.tif" /></maths> is satisfied or not, and if yes, (5) is executed; otherwise, (1) is re-executed. The verification of the equation <maths id="math0041"><math display="inline"><msubsup><mi>r</mi><mn>1</mn><mi>ʹ</mi></msubsup><mo>⁢</mo><mi>P</mi><mo>=</mo><msubsup><mi>X</mi><mn>1</mn><mi>ʹ</mi></msubsup></math><img file="EP2124381B1_D0041.tif" /></maths> aims at verifying whether the DH secret value selected by the organizer is tampered or not.</li><li><i>(5) U₆</i> generates a group key <maths id="math0042"><math display="inline"><mi mathvariant="italic">Kʹ</mi><mo>=</mo><msubsup><mi>r</mi><mn>1</mn><mi>ʹ</mi></msubsup><mo>⁢</mo><msubsup><mi>r</mi><mn>6</mn><mi>ʹ</mi></msubsup><mo>⁢</mo><mi>P</mi></math><img file="EP2124381B1_D0042.tif" /></maths> according to the DH secret value <maths id="math0043"><math display="inline"><msubsup><mi>r</mi><mn>1</mn><mi>ʹ</mi></msubsup></math><img file="EP2124381B1_D0043.tif" /></maths> selected by the organizer <i>U</i>₁ and the DH public value of <i>U₆</i>.</li><li>(6) The other members <i>U</i>₂, ..., <i>U</i>₅ in the group Σ obtain z'= <i>x_K</i> according to the previous z value, compute <maths id="math0044"><math display="inline"><mi mathvariant="italic">zʹP</mi><mo>=</mo><mfenced><mi mathvariant="italic">xʹ</mi><mi mathvariant="italic">yʹ</mi></mfenced><mo>=</mo><msubsup><mi>r</mi><mi>i</mi><mrow><mi>ʹ</mi><mo>-</mo><mn>1</mn></mrow></msubsup><mo>⁢</mo><msubsup><mi>c</mi><mi>i</mi><mi>ʹ</mi></msubsup><mspace width="1em" /><mfenced><mi>i</mi><mo>∈</mo><mfenced open="{" close="}"><mn mathvariant="normal">2</mn><mo>…</mo><mn>5</mn></mfenced></mfenced><mo>,</mo></math><img file="EP2124381B1_D0044.tif" /></maths> and obtain the <i>x'</i> according to the intermediate message DH value <i>z'P</i> = (<i>x', y</i>'). As <maths id="math0045"><math display="inline"><msubsup><mi>c</mi><mn>1</mn><mi>ʹ</mi></msubsup><mo>=</mo><msubsup><mi>r</mi><mn>1</mn><mi>ʹ</mi></msubsup><mo>⁢</mo><mi mathvariant="italic">xʹ</mi><mfenced><mi>mod</mi><mspace width="1em" /><mi>p</mi></mfenced><mo>,</mo></math><img file="EP2124381B1_D0045.tif" /></maths><maths id="math0046"><math display="inline"><msubsup><mi>r</mi><mn>1</mn><mi>ʹ</mi></msubsup><mo>=</mo><msubsup><mi>c</mi><mn>1</mn><mi>ʹ</mi></msubsup><mo>⁢</mo><msup><mi mathvariant="italic">xʹ</mi><mrow><mo>-</mo><mn>1</mn></mrow></msup><mfenced><mi>mod</mi><mspace width="1em" /><mi>p</mi></mfenced><mo>,</mo></math><img file="EP2124381B1_D0046.tif" /></maths> so that the DH secret value <maths id="math0047"><math display="inline"><msubsup><mi>r</mi><mn>1</mn><mi>ʹ</mi></msubsup></math><img file="EP2124381B1_D0047.tif" /></maths> selected by the organizer <i>U</i>₁ is computed. Then, according to the DH secret value <maths id="math0048"><math display="inline"><msubsup><mi>r</mi><mn>1</mn><mi>ʹ</mi></msubsup></math><img file="EP2124381B1_D0048.tif" /></maths> selected by the organizer <i>U</i>₁ and the DH public value of the new member U<i>₆</i>, each of the other members <i>U</i>₂, ..., <i>U</i>₅ generates a group key <maths id="math0049"><math display="inline"><mi mathvariant="italic">Kʹ</mi><mo>=</mo><msubsup><mi>r</mi><mn>1</mn><mi>ʹ</mi></msubsup><mo>⁢</mo><msubsup><mi>r</mi><mn>6</mn><mi>ʹ</mi></msubsup><mo>⁢</mo><mi>P</mi><mn>.</mn></math><img file="EP2124381B1_D0049.tif" /></maths></li></ol>

0039Through the above method, all the members obtain the same group key <maths id="math0050"><math display="inline"><mi mathvariant="italic">Kʹ</mi><mo>=</mo><msubsup><mi>r</mi><mn>1</mn><mi>ʹ</mi></msubsup><mo>⁢</mo><msubsup><mi>r</mi><mn>6</mn><mi>ʹ</mi></msubsup><mo>⁢</mo><mi>P</mi><mn>.</mn></math><img file="EP2124381B1_D0050.tif" /></maths>

Embodiment 3

0040In this embodiment, a method for generating a group key through negotiation when groups are combined is provided. This embodiment is based on Embodiment 1. <i>t</i> groups need to be combined, which are represented as {Σ₁, Σ₂, ..., Σ_t} respectively, and each group Σ<i>_i</i> has <i>n_i</i> members, i.e., Σ<i>_i</i>= {<i>U</i>_<i>i</i>1, <i>U</i>_<i>i</i>2, ..., <i>U_{in<sub2>i</sub2>}</i>} (<i>i</i>∈{1, <i>t</i>}). Each group has executed the basic negotiation in Embodiment 1 respectively, and the members in the group Σ<i>_i</i> share a group key <i>K_i</i>. Herein, <i>U</i>₁₁ is selected as a new organizer, Σ₁ is a major combining group, and Σ₂, ..., Σ<i>_t</i> are minor combining groups. The negotiation process requires the organizer <i>U</i>_<i>i</i>1 of each group Σ<i>_i</i> to participate in. Referring to <figref idref="f0005">FIG. 6</figref>, the groups to be combined form a star-shaped structure together, and referring to <figref idref="f0006">FIG. 7</figref>, the key negotiation process is described as follows. <ul id="ul0005" list-style="none"><li>401: <i>U</i>₁₁ selects a DH secret value <maths id="math0051"><math display="inline"><msubsup><mi>r</mi><mn>11</mn><mi>ʹ</mi></msubsup><mo>∈</mo><msub><mi>Z</mi><mi>q</mi></msub></math><img file="EP2124381B1_D0051.tif" /></maths> according to system parameters, generates a DH public value <maths id="math0052"><math display="inline"><msubsup><mi>X</mi><mn>11</mn><mi>ʹ</mi></msubsup><mo>=</mo><mfenced><msubsup><mi>x</mi><mn>11</mn><mi>ʹ</mi></msubsup><msubsup><mi>y</mi><mn>11</mn><mi>ʹ</mi></msubsup></mfenced><mo>=</mo><msubsup><mi>r</mi><mn>11</mn><mi>ʹ</mi></msubsup><mo>⁢</mo><mi>P</mi></math><img file="EP2124381B1_D0052.tif" /></maths> according to the DH secret value <maths id="math0053"><math display="inline"><msubsup><mi>r</mi><mn>11</mn><mi>ʹ</mi></msubsup></math><img file="EP2124381B1_D0053.tif" /></maths> and a public base point <i>P</i>, and broadcasts the DH public value <maths id="math0054"><math display="inline"><msubsup><mi>X</mi><mn>11</mn><mi>ʹ</mi></msubsup><mo>=</mo><mfenced><msubsup><mi>x</mi><mn>11</mn><mi>ʹ</mi></msubsup><msubsup><mi>y</mi><mn>11</mn><mi>ʹ</mi></msubsup></mfenced><mo>=</mo><msubsup><mi>r</mi><mn>11</mn><mi>ʹ</mi></msubsup><mo>⁢</mo><mi>P</mi></math><img file="EP2124381B1_D0054.tif" /></maths> in the group.</li><li>402: Supposed that a DH secret value <maths id="math0055"><math display="inline"><msubsup><mi>r</mi><mrow><mi>i</mi><mo>⁢</mo><mn>1</mn></mrow><mi>ʹ</mi></msubsup><mo>=</mo><msub><mi>x</mi><msub><mi>K</mi><mi>i</mi></msub></msub><mo>,</mo></math><img file="EP2124381B1_D0055.tif" /></maths> the organizer <i>U</i>_<i>i</i>1 of each of the minor combining groups Σ₂, ..., Σ<i>_t</i> generates a DH public value <maths id="math0056"><math display="inline"><msubsup><mi>X</mi><mrow><mi>i</mi><mo>⁢</mo><mn>1</mn></mrow><mi>ʹ</mi></msubsup><mo>=</mo><mfenced><msubsup><mi>x</mi><mrow><mi>i</mi><mo>⁢</mo><mn>1</mn></mrow><mi>ʹ</mi></msubsup><msubsup><mi>y</mi><mrow><mi>i</mi><mo>⁢</mo><mn>1</mn></mrow><mi>ʹ</mi></msubsup></mfenced><mo>=</mo><msubsup><mi>r</mi><mrow><mi>i</mi><mo>⁢</mo><mn>1</mn></mrow><mi>ʹ</mi></msubsup><mo>⁢</mo><mi>P</mi></math><img file="EP2124381B1_D0056.tif" /></maths> according to the DH secret value <maths id="math0057"><math display="inline"><msubsup><mi>r</mi><mrow><mi>i</mi><mo>⁢</mo><mn>1</mn></mrow><mi>ʹ</mi></msubsup></math><img file="EP2124381B1_D0057.tif" /></maths> and the public base point <i>P</i>, and broadcasts the DH public value <maths id="math0058"><math display="inline"><msubsup><mi>X</mi><mrow><mi>i</mi><mo>⁢</mo><mn>1</mn></mrow><mi>ʹ</mi></msubsup><mo>=</mo><mfenced><msubsup><mi>x</mi><mrow><mi>i</mi><mo>⁢</mo><mn>1</mn></mrow><mi>ʹ</mi></msubsup><msubsup><mi>y</mi><mrow><mi>i</mi><mo>⁢</mo><mn>1</mn></mrow><mi>ʹ</mi></msubsup></mfenced><mo>=</mo><msubsup><mi>r</mi><mrow><mi>i</mi><mo>⁢</mo><mn>1</mn></mrow><mi>ʹ</mi></msubsup><mo>⁢</mo><mi>P</mi></math><img file="EP2124381B1_D0058.tif" /></maths> in the group, in which <i>i</i> goes through 2, ..., <i>t</i>. In the embodiment, <i>x_Ki</i> represents an x-coordinate of the key <i>K_i</i> shared in the Σ<i>_i</i>= {<i>U</i>_<i>i</i>1, <i>U</i>_<i>i</i>2<i>, ... , U_{in<sub2>i</sub2>}</i>} (<i>i</i>∈{1, <i>t</i>}), and all the group members know that the organizer <i>U</i>_<i>i</i>1 selects the x-coordinate or the y-coordinate as <i>z</i>' in advance. In this embodiment, the organizer <i>U</i>_<i>i</i>1 selects the x-coordinate as <i>z</i>', and may also supposed that <i>z'</i> = <i>y_{K<sub2>i</sub2>}</i>, that is, it organizer <i>U</i>_<i>i</i>1 selects the y-coordinate as <i>z'</i>.</li><li>403: After receiving the DH public value <maths id="math0059"><math display="inline"><msubsup><mi>X</mi><mrow><mi>i</mi><mo>⁢</mo><mn>1</mn></mrow><mi>ʹ</mi></msubsup></math><img file="EP2124381B1_D0059.tif" /></maths> broadcasted by <i>U</i>_<i>i</i>1, supposed that a secret exponent <i>z'</i> = <i>x</i>_{<i>K</i><sub2>1</sub2>}, <i>U</i>₁₁ computes an intermediate message DH value <i>z'P</i> = (<i>x'</i>, <i>y'</i>) based on Diffie-Hellman key negotiation protocol on the Elliptic-Curve, generates an intermediate message <maths id="math0060"><math display="inline"><mfenced open="{" close="}"><msubsup><mi>c</mi><mn>1</mn><mi>ʹ</mi></msubsup><msubsup><mi>c</mi><mn>2</mn><mi>ʹ</mi></msubsup><mo>⋯</mo><msubsup><mi>c</mi><mi>t</mi><mi>ʹ</mi></msubsup></mfenced><mo>=</mo><mfenced open="{" close="}"><msubsup><mi>r</mi><mn>11</mn><mi>ʹ</mi></msubsup><mo>⁢</mo><mi mathvariant="italic">xʹ</mi><mfenced><mi>mod</mi><mspace width="1em" /><mi>p</mi></mfenced><mo>,</mo><msubsup><mi>r</mi><mn>21</mn><mi>ʹ</mi></msubsup><mo>⁢</mo><mi mathvariant="italic">zʹP</mi><mo>,</mo><msubsup><mi>r</mi><mn>31</mn><mi>ʹ</mi></msubsup><mo>⁢</mo><mi mathvariant="italic">zʹP</mi><mo>,</mo><mo>⋯</mo><mo>,</mo><msubsup><mi>r</mi><mrow><mi>t</mi><mo>⁢</mo><mn>1</mn></mrow><mi>ʹ</mi></msubsup><mo>⁢</mo><mi mathvariant="italic">zʹP</mi></mfenced></math><img file="EP2124381B1_D0060.tif" /></maths> carrying the intermediate message DH value, broadcasts the intermediate message <maths id="math0061"><math display="inline"><mfenced open="{" close="}"><msubsup><mi>c</mi><mn>1</mn><mi>ʹ</mi></msubsup><msubsup><mi>c</mi><mn>2</mn><mi>ʹ</mi></msubsup><mo>⋯</mo><msubsup><mi>c</mi><mi>t</mi><mi>ʹ</mi></msubsup></mfenced><mo>=</mo><mfenced open="{" close="}"><msubsup><mi>r</mi><mn>11</mn><mi>ʹ</mi></msubsup><mo>⁢</mo><mi mathvariant="italic">xʹ</mi><mfenced><mi>mod</mi><mspace width="1em" /><mi>p</mi></mfenced><mo>,</mo><msubsup><mi>r</mi><mn>21</mn><mi>ʹ</mi></msubsup><mo>⁢</mo><mi mathvariant="italic">zʹP</mi><mo>,</mo><msubsup><mi>r</mi><mn>31</mn><mi>ʹ</mi></msubsup><mo>⁢</mo><mi mathvariant="italic">zʹP</mi><mo>,</mo><mo>⋯</mo><mo>,</mo><msubsup><mi>r</mi><mrow><mi>t</mi><mo>⁢</mo><mn>1</mn></mrow><mi>ʹ</mi></msubsup><mo>⁢</mo><mi mathvariant="italic">zʹP</mi></mfenced></math><img file="EP2124381B1_D0061.tif" /></maths> in the group, and generates a new group key <maths id="math0062"><math display="inline"><mi mathvariant="italic">Kʹ</mi><mo>=</mo><msubsup><mi>r</mi><mn>11</mn><mi>ʹ</mi></msubsup><mo>⁢</mo><mfenced><msubsup><mi>r</mi><mn>21</mn><mi>ʹ</mi></msubsup><mo>⁢</mo><mi mathvariant="italic">P</mi><mo mathvariant="italic">+</mo><msubsup><mi>r</mi><mn>31</mn><mi>ʹ</mi></msubsup><mo>⁢</mo><mi mathvariant="italic">P</mi><mo>+</mo><mo>⋯</mo><mo>+</mo><msubsup><mi>r</mi><mrow><mi>t</mi><mo>⁢</mo><mn>1</mn></mrow><mi>ʹ</mi></msubsup><mo>⁢</mo><mi mathvariant="italic">P</mi></mfenced></math><img file="EP2124381B1_D0062.tif" /></maths> according to the DH secret value <maths id="math0063"><math display="inline"><msubsup><mi>r</mi><mn>11</mn><mi>ʹ</mi></msubsup></math><img file="EP2124381B1_D0063.tif" /></maths> selected by <i>U</i>₁₁ itself and the DH public value of <i>U</i>_<i>i</i>1.</li><li>404: After receiving the intermediate message broadcasted by <i>U</i>₁₁, <i>U</i>_<i>i</i>1 (<i>i</i>∈{2, ... , <i>t</i>}) extracts the intermediate message DH value in the intermediate message, in which the intermediate message DH value <i>z'P</i> is specifically obtained by computing <maths id="math0064"><math display="inline"><mi mathvariant="italic">zʹP</mi><mo>=</mo><mfenced><mi mathvariant="italic">xʹ</mi><mi mathvariant="italic">yʹ</mi></mfenced><mo>=</mo><msubsup><mi>r</mi><mrow><mi>i</mi><mo>⁢</mo><mn>1</mn></mrow><mrow><mi>ʹ</mi><mo>-</mo><mn>1</mn></mrow></msubsup><mo>⁢</mo><msubsup><mi>c</mi><mi>i</mi><mi>ʹ</mi></msubsup><mo>,</mo></math><img file="EP2124381B1_D0064.tif" /></maths> and then, according to the intermediate message DH value <maths id="math0065"><math display="inline"><mi mathvariant="italic">zʹP</mi><mo>=</mo><mfenced><mi mathvariant="italic">xʹ</mi><mi mathvariant="italic">yʹ</mi></mfenced><mo>,</mo></math><img file="EP2124381B1_D0065.tif" /></maths> the <i>x</i>' is obtained. As <maths id="math0066"><math display="inline"><msubsup><mi>c</mi><mn>1</mn><mi>ʹ</mi></msubsup><mo>=</mo><msubsup><mi>r</mi><mn>11</mn><mi>ʹ</mi></msubsup><mo>⁢</mo><mi mathvariant="italic">xʹ</mi><mfenced><mi>mod</mi><mspace width="1em" /><mi>p</mi></mfenced><mo>,</mo></math><img file="EP2124381B1_D0066.tif" /></maths><maths id="math0067"><math display="inline"><msubsup><mi>r</mi><mn>11</mn><mi>ʹ</mi></msubsup><mo>=</mo><msubsup><mi>r</mi><mn>1</mn><mi>ʹ</mi></msubsup><mo>⁢</mo><msup><mi mathvariant="italic">xʹ</mi><mrow><mo>-</mo><mn>1</mn></mrow></msup><mfenced><mi>mod</mi><mspace width="1em" /><mi>p</mi></mfenced><mo>,</mo></math><img file="EP2124381B1_D0067.tif" /></maths> so that the DH secret value <maths id="math0068"><math display="inline"><msubsup><mi>r</mi><mn>11</mn><mi>ʹ</mi></msubsup></math><img file="EP2124381B1_D0068.tif" /></maths> selected by the organizer is computed.</li><li>405: After computing the DH secret value <maths id="math0069"><math display="inline"><msubsup><mi>r</mi><mn>11</mn><mi>ʹ</mi></msubsup></math><img file="EP2124381B1_D0069.tif" /></maths> selected by <i>U</i>₁₁, <i>U</i>_<i>i</i>1 (<i>i</i>∈{2, ..., <i>t</i>}) verifies whether an equation <maths id="math0070"><math display="inline"><msubsup><mi>r</mi><mn>11</mn><mi>ʹ</mi></msubsup><mo>⁢</mo><mi>P</mi><mo>=</mo><msubsup><mi>X</mi><mn>11</mn><mi>ʹ</mi></msubsup></math><img file="EP2124381B1_D0070.tif" /></maths> is satisfied or not, and if yes, 406 is executed; otherwise, 401 is re-executed. The verification of the equation <maths id="math0071"><math display="inline"><msubsup><mi>r</mi><mn>11</mn><mi>ʹ</mi></msubsup><mo>⁢</mo><mi>P</mi><mo>=</mo><msubsup><mi>X</mi><mn>11</mn><mi>ʹ</mi></msubsup></math><img file="EP2124381B1_D0071.tif" /></maths> aims at verifying whether the DH secret value selected by <i>U</i>₁₁ is tampered or not.</li><li>406: <i>U</i>_<i>i</i>1 (<i>i</i> ∈ {<i>2,</i> ..., <i>t</i>}) generates a group key <maths id="math0072"><math display="inline"><mi mathvariant="italic">Kʹ</mi><mo>=</mo><msubsup><mi>r</mi><mn>11</mn><mi>ʹ</mi></msubsup><mo>⁢</mo><mfenced><msubsup><mi>r</mi><mn>21</mn><mi>ʹ</mi></msubsup><mo>⁢</mo><mi mathvariant="italic">P</mi><mo mathvariant="italic">+</mo><msubsup><mi>r</mi><mn>31</mn><mi>ʹ</mi></msubsup><mo>⁢</mo><mi mathvariant="italic">P</mi><mo>+</mo><mo>⋯</mo><mo>+</mo><msubsup><mi>r</mi><mrow><mi>t</mi><mo>⁢</mo><mn>1</mn></mrow><mi>ʹ</mi></msubsup><mo>⁢</mo><mi mathvariant="italic">P</mi></mfenced></math><img file="EP2124381B1_D0072.tif" /></maths> according to the DH secret value <maths id="math0073"><math display="inline"><msubsup><mi>r</mi><mn>11</mn><mi>ʹ</mi></msubsup></math><img file="EP2124381B1_D0073.tif" /></maths> selected by <i>U</i>₁₁ and the DH public value of <i>U</i>_<i>i</i>1.</li><li>407: The other members in the minor combining group Σ<i>_i</i>(<i>i</i>∈{2, ..., <i>t</i>}) except the organizers obtain <i>z</i>' = <i>x</i>_{<i>K</i><sub2>1</sub2>} according to the previous z value, compute <maths id="math0074"><math display="inline"><mi mathvariant="italic">zʹP</mi><mo>=</mo><mfenced><mi mathvariant="italic">xʹ</mi><mi mathvariant="italic">yʹ</mi></mfenced><mo>=</mo><msubsup><mi>r</mi><mrow><mi>i</mi><mo>⁢</mo><mn>1</mn></mrow><mrow><mi>ʹ</mi><mo>-</mo><mn>1</mn></mrow></msubsup><mo>⁢</mo><msubsup><mi>c</mi><mi>i</mi><mi>ʹ</mi></msubsup><mspace width="1em" /><mfenced><mi>i</mi><mo>∈</mo><mfenced open="{" close="}"><mn mathvariant="normal">1</mn><mn mathvariant="normal">2</mn><mo>…</mo><mi>t</mi></mfenced></mfenced><mo>,</mo></math><img file="EP2124381B1_D0074.tif" /></maths> and obtain the <i>x'</i> according to the intermediate message DH value <i>z'P</i> = (<i>x', y'</i>). As <maths id="math0075"><math display="inline"><msubsup><mi>c</mi><mn>1</mn><mi>ʹ</mi></msubsup><mo>=</mo><msubsup><mi>r</mi><mn>11</mn><mi>ʹ</mi></msubsup><mo>⁢</mo><mi mathvariant="italic">xʹ</mi><mfenced><mi>mod</mi><mspace width="1em" /><mi>p</mi></mfenced><mo>,</mo></math><img file="EP2124381B1_D0075.tif" /></maths><maths id="math0076"><math display="inline"><msubsup><mi>r</mi><mn>11</mn><mi>ʹ</mi></msubsup><mo>=</mo><msubsup><mi>r</mi><mn>1</mn><mi>ʹ</mi></msubsup><mo>⁢</mo><msup><mi mathvariant="italic">xʹ</mi><mrow><mo>-</mo><mn>1</mn></mrow></msup><mfenced><mi>mod</mi><mspace width="1em" /><mi>p</mi></mfenced><mo>,</mo></math><img file="EP2124381B1_D0076.tif" /></maths> so that the DH secret value <maths id="math0077"><math display="inline"><msubsup><mi>r</mi><mn>11</mn><mi>ʹ</mi></msubsup></math><img file="EP2124381B1_D0077.tif" /></maths> selected by the organizer is computed. Then, according to the DH secret value <maths id="math0078"><math display="inline"><msubsup><mi>r</mi><mn>11</mn><mi>ʹ</mi></msubsup></math><img file="EP2124381B1_D0078.tif" /></maths> selected by <i>U</i>₁₁ and the DH public value of <i>U</i>_<i>i</i>1, each of the other members in the minor combining group Σ<i>_i</i> (<i>i</i>∈{2, ..., <i>t</i>}) generates a new group key <maths id="math0079"><math display="inline"><mi mathvariant="italic">Kʹ</mi><mo>=</mo><msubsup><mi>r</mi><mn>11</mn><mi>ʹ</mi></msubsup><mo>⁢</mo><mfenced><msubsup><mi>r</mi><mn>21</mn><mi>ʹ</mi></msubsup><mo>⁢</mo><mi mathvariant="italic">P</mi><mo mathvariant="italic">+</mo><msubsup><mi>r</mi><mn>31</mn><mi>ʹ</mi></msubsup><mo>⁢</mo><mi mathvariant="italic">P</mi><mo>+</mo><mo>⋯</mo><msubsup><mi>r</mi><mrow><mi>t</mi><mo>⁢</mo><mn>1</mn></mrow><mi>ʹ</mi></msubsup><mo>⁢</mo><mi mathvariant="italic">P</mi></mfenced><mn>.</mn></math><img file="EP2124381B1_D0079.tif" /></maths></li><li>408: According to the <i>x</i>_{<i>K</i><sub2>1</sub2>} obtained in advance, the other members in the major combining group Σ<i>₁</i> except the organizer compute <maths id="math0080"><math display="inline"><mi mathvariant="italic">zʹP</mi><mo>=</mo><mfenced><mi mathvariant="italic">xʹ</mi><mi mathvariant="italic">yʹ</mi></mfenced><mo>=</mo><msubsup><mi>r</mi><mrow><mi>i</mi><mo>⁢</mo><mn>1</mn></mrow><mrow><mi>ʹ</mi><mo>-</mo><mn>1</mn></mrow></msubsup><mo>⁢</mo><msubsup><mi>c</mi><mi>i</mi><mi>ʹ</mi></msubsup><mspace width="1em" /><mfenced><mi>i</mi><mo>∈</mo><mfenced open="{" close="}"><mn mathvariant="normal">1</mn><mn mathvariant="normal">2</mn><mo>…</mo><mi>t</mi></mfenced></mfenced><mo>,</mo></math><img file="EP2124381B1_D0080.tif" /></maths> and then obtain the corresponding <i>x'</i> according to the intermediate message DH value <maths id="math0081"><math display="inline"><mi mathvariant="italic">zʹP</mi><mo>=</mo><mfenced><mi mathvariant="italic">xʹ</mi><mi mathvariant="italic">yʹ</mi></mfenced><mn>.</mn></math><img file="EP2124381B1_D0081.tif" /></maths> As <maths id="math0082"><math display="inline"><msubsup><mi>c</mi><mn>1</mn><mi>ʹ</mi></msubsup><mo>=</mo><msubsup><mi>r</mi><mn>11</mn><mi>ʹ</mi></msubsup><mo>⁢</mo><mi mathvariant="italic">xʹ</mi><mfenced><mi>mod</mi><mspace width="1em" /><mi>p</mi></mfenced><mo>,</mo></math><img file="EP2124381B1_D0082.tif" /></maths><maths id="math0083"><math display="inline"><msubsup><mi>r</mi><mn>11</mn><mi>ʹ</mi></msubsup><mo>=</mo><msubsup><mi>r</mi><mn>1</mn><mi>ʹ</mi></msubsup><mo>⁢</mo><msup><mi mathvariant="italic">xʹ</mi><mrow><mo>-</mo><mn>1</mn></mrow></msup><mfenced><mi>mod</mi><mspace width="1em" /><mi>p</mi></mfenced><mo>,</mo></math><img file="EP2124381B1_D0083.tif" /></maths>so that the DH secret value <maths id="math0084"><math display="inline"><msubsup><mi>r</mi><mn>11</mn><mi>ʹ</mi></msubsup></math><img file="EP2124381B1_D0084.tif" /></maths> selected by the organizer is obtained. Then, according to the DH secret value <maths id="math0085"><math display="inline"><msubsup><mi>r</mi><mn>11</mn><mi>ʹ</mi></msubsup></math><img file="EP2124381B1_D0085.tif" /></maths> selected by <i>U</i>₁₁ and the DH public value of <i>U</i>_<i>i</i>1, each of the other members in the major combining group Σ<i>_l</i> generates a new group key <maths id="math0086"><math display="inline"><mi mathvariant="italic">Kʹ</mi><mo>=</mo><msubsup><mi>r</mi><mn>11</mn><mi>ʹ</mi></msubsup><mo>⁢</mo><mfenced><msubsup><mi>r</mi><mn>21</mn><mi>ʹ</mi></msubsup><mo>⁢</mo><mi mathvariant="italic">P</mi><mo mathvariant="italic">+</mo><msubsup><mi>r</mi><mn>31</mn><mi>ʹ</mi></msubsup><mo>⁢</mo><mi mathvariant="italic">P</mi><mo>+</mo><mo>⋯</mo><msubsup><mi>r</mi><mrow><mi>t</mi><mo>⁢</mo><mn>1</mn></mrow><mi>ʹ</mi></msubsup><mo>⁢</mo><mi mathvariant="italic">P</mi></mfenced><mn>.</mn></math><img file="EP2124381B1_D0086.tif" /></maths></li></ul>

0041Through the above method, <i>t</i> groups are combined into one group with <i>U</i>₁₁ as the organizer, and all the members share the group key <maths id="math0087"><math display="inline"><mi mathvariant="italic">Kʹ</mi><mo>=</mo><msubsup><mi>r</mi><mn>11</mn><mi>ʹ</mi></msubsup><mo>⁢</mo><mfenced><msubsup><mi>r</mi><mn>21</mn><mi>ʹ</mi></msubsup><mo>⁢</mo><mi mathvariant="italic">P</mi><mo mathvariant="italic">+</mo><msubsup><mi>r</mi><mn>31</mn><mi>ʹ</mi></msubsup><mo>⁢</mo><mi mathvariant="italic">P</mi><mo>+</mo><mo>⋯</mo><msubsup><mi>r</mi><mrow><mi>t</mi><mo>⁢</mo><mn>1</mn></mrow><mi>ʹ</mi></msubsup><mo>⁢</mo><mi mathvariant="italic">P</mi></mfenced><mn>.</mn></math><img file="EP2124381B1_D0087.tif" /></maths>

Embodiment 4

0042In this embodiment, a method for generating a group key when members leave the group is provided. This embodiment is based on Embodiment 1. It is assumed that the members in the group Σ = {<i>U</i>₁,..., <i>U_n</i>} has executed the basic negotiation of Embodiment 1. <i>k</i> members Σ'={<i>U</i>_{<i>j</i><sub2>1</sub2>,}...,<i>U_{j<sub2>k</sub2>}</i>} need to leave the group and the other group members Σ"= {<i>U</i>₁, ...<i>U</i>_{<i>j</i><sub2>1</sub2>-1}, <i>U</i>_{<i>j</i><sub2>1</sub2>+1},...,<i>U</i>_{<i>j_k</i>+1},...,<i>U_n</i>} remain in the group. The remaining group members are required to compute a new group key to prevent the members who have left the group from obtaining the group key of the current group, and the following specific steps are performed.

0043First, after <i>k</i> members leave the group Σ, the organizer <i>U</i>₁ re-selects the DH secret value <maths id="math0088"><math display="inline"><msubsup><mi>r</mi><mn>1</mn><mi>ʹ</mi></msubsup><mo>,</mo></math><img file="EP2124381B1_D0088.tif" /></maths><i>z</i>' ∈ <i>Z_q</i> according to the system parameters, and the other members in <i>G</i>" do not need to re-select the DH secret values.

0044Next, the other group members Σ" = {<i>U</i>₁,···,<i>U</i>_{<i>j</i><sub2>1</sub2><i>-</i>1},<i>U</i>_{<i>j</i><sub2>1</sub2>+1},···,<i>U</i>_{<i>j_k</i>-1},<i>U</i>_{<i>j_k</i>+1},···,<i>U_n</i>} perform the group key negotiation method in Embodiment 1 once again, generate a new intermediate message <maths id="math0089"><math display="inline"><mfenced open="{" close="}"><msubsup><mi>c</mi><mn>1</mn><mi>ʹ</mi></msubsup><mo>⋯</mo><msubsup><mi>c</mi><mrow><msub><mi>j</mi><mn>1</mn></msub><mo>-</mo><mn>1</mn></mrow><mi>ʹ</mi></msubsup><msubsup><mi>c</mi><mrow><msub><mi>j</mi><mn>1</mn></msub><mo>+</mo><mn>1</mn></mrow><mi>ʹ</mi></msubsup><mo>…</mo><msubsup><mi>c</mi><mrow><msub><mi>j</mi><mi>k</mi></msub><mo>-</mo><mn>1</mn></mrow><mi>ʹ</mi></msubsup><msubsup><mi>c</mi><mrow><msub><mi>j</mi><mi>k</mi></msub><mo>+</mo><mn>1</mn></mrow><mi>ʹ</mi></msubsup><mo>⋯</mo><msubsup><mi>c</mi><mi>n</mi><mi>ʹ</mi></msubsup></mfenced><mo>=</mo><mrow><mo>{</mo></mrow><msubsup><mi>r</mi><mn>1</mn><mi>ʹ</mi></msubsup><mo>⁢</mo><mi mathvariant="italic">xʹ</mi><mfenced><mi>mod</mi><mspace width="1em" /><mi>p</mi></mfenced><mo>,</mo></math><img file="EP2124381B1_D0089.tif" /></maths><maths id="math0090"><math display="inline"><mo>⋯</mo><mo>,</mo><msubsup><mi>r</mi><mrow><msub><mi>j</mi><mn>1</mn></msub><mo>-</mo><mn>1</mn></mrow><mi>ʹ</mi></msubsup><mo>⁢</mo><mi mathvariant="italic">zʹP</mi><mo>,</mo><msubsup><mi>r</mi><mrow><msub><mi>j</mi><mn>1</mn></msub><mo>+</mo><mn>1</mn></mrow><mi>ʹ</mi></msubsup><mo>⁢</mo><mi mathvariant="italic">zʹP</mi><mo>,</mo><mo>…</mo><mo>,</mo><msubsup><mi>r</mi><mrow><msub><mi>j</mi><mi>k</mi></msub><mo>-</mo><mn>1</mn></mrow><mi>ʹ</mi></msubsup><mo>⁢</mo><mi mathvariant="italic">zʹP</mi><mo>,</mo><msubsup><mi>r</mi><mrow><msub><mi>j</mi><mi>k</mi></msub><mo>+</mo><mn>1</mn></mrow><mi>ʹ</mi></msubsup><mo>⁢</mo><mi mathvariant="italic">zʹP</mi><mo>,</mo><mo>⋯</mo><mo>,</mo><msubsup><mi>r</mi><mi>n</mi><mi>ʹ</mi></msubsup><mo>⁢</mo><mi mathvariant="italic">zʹP</mi><mrow><mo>}</mo></mrow></math><img file="EP2124381B1_D0090.tif" /></maths> and generate a new group key <maths id="math0091"><math display="inline"><mi mathvariant="italic">Kʹ</mi><mo>=</mo><msubsup><mi>r</mi><mn>1</mn><mi>ʹ</mi></msubsup><mo>⁢</mo><mfenced><msub><mi>r</mi><mn>2</mn></msub><mo>⁢</mo><mi>P</mi><mo>+</mo><mo>⋯</mo><mo>+</mo><msub><mi>r</mi><mrow><msub><mi>j</mi><mn>1</mn></msub><mo>-</mo><mn>1</mn></mrow></msub><mo>⁢</mo><mi>P</mi><mo>+</mo><msub><mi>r</mi><mrow><msub><mi>j</mi><mn>1</mn></msub><mo>+</mo><mn>1</mn></mrow></msub><mo>⁢</mo><mi>P</mi><mo>+</mo><msub><mi>r</mi><mrow><msub><mi>j</mi><mi>k</mi></msub><mo>-</mo><mn>1</mn></mrow></msub><mo>⁢</mo><mi>P</mi><mo>+</mo><msub><mi>r</mi><mrow><msub><mi>j</mi><mi>k</mi></msub><mo>+</mo><mn>1</mn></mrow></msub><mo>+</mo><mo>⋯</mo><mo>+</mo><msub><mi>r</mi><mi>n</mi></msub><mo>⁢</mo><mi>P</mi></mfenced></math><img file="EP2124381B1_D0091.tif" /></maths> for sharing.

0045If the organizer in the original group E has left the group, it is required to re-select a member to be the organizer in the group <i>G</i>", and then execute the above steps to generate anewgroupkey <maths id="math0092"><math display="inline"><mi mathvariant="italic">Kʹ</mi><mo>=</mo><msubsup><mi>r</mi><mn>1</mn><mi>ʹ</mi></msubsup><mo>⁢</mo><mfenced><msub><mi>r</mi><mn>2</mn></msub><mo>⁢</mo><mi>P</mi><mo>+</mo><mo>⋯</mo><mo>+</mo><msub><mi>r</mi><mrow><msub><mi>j</mi><mn>1</mn></msub><mo>-</mo><mn>1</mn></mrow></msub><mo>⁢</mo><mi>P</mi><mo>+</mo><msub><mi>r</mi><mrow><msub><mi>j</mi><mn>1</mn></msub><mo>+</mo><mn>1</mn></mrow></msub><mo>⁢</mo><mi>P</mi><mo>+</mo><msub><mi>r</mi><mrow><msub><mi>j</mi><mi>k</mi></msub><mo>-</mo><mn>1</mn></mrow></msub><mo>⁢</mo><mi>P</mi><mo>+</mo><msub><mi>r</mi><mrow><msub><mi>j</mi><mi>k</mi></msub><mo>+</mo><mn>1</mn></mrow></msub><mo>+</mo><mo>⋯</mo><mo>+</mo><msub><mi>r</mi><mi>n</mi></msub><mo>⁢</mo><mi>P</mi></mfenced></math><img file="EP2124381B1_D0092.tif" /></maths> for sharing.

Embodiment 5

0046As the scale of the group is continuously expanded, the computation load and the communication load of the organizer are increased rapidly. When the scale of the network is increased to an extent, the performance of the organizer becomes a bottleneck of the protocol, so that it needs to modify the performance of the organizer appropriately, so as to reduce the load of the organizer.

0047In this embodiment, a group key negotiation method in communication of a large-scale group is provided. This embodiment is based on Embodiment 1. When the scale of group members who participate in the negotiation is very large, the members in a group Σ are divided into <i>m</i> sub-groups, which are remarked as Σ={Σ₁, Σ₂, ..., Σ<i>_m</i>}, and all the nodes form a star-shaped structure. Each sub-group Σ<i>_i</i> has <i>n_i</i> members, which are remarked as {<i>U</i>_<i>i</i>1, <i>U</i>_<i>i</i>2, ..., <i>U_{in<sub2>i</sub2>}</i>}<i>.</i> The <i>n_i</i> members may also form a star-shaped structure, and <i>U</i>_<i>i</i>1 becomes an organizer of the sub-group Σ<i>_i</i>.

0048As for a group dividing method, the group may be divided according to a unique machine code corresponding to each node device (similar to a MAC address of an Ethernet network card), and may also be divided according to geographical locations. The following steps are performed.

0049First, <i>n_i</i> members in the sub-group Σ<i>_i</i> (<i>i</i>=1,2,..., <i>m</i>) form a star-shaped structure, and perform the basic negotiation in Embodiment 1, so as to obtain a group key <i>K_i</i> = <i>r</i>_<i>i</i>1<i>(r</i>_<i>i</i>2<i>P</i>+<i>r</i>_<i>i</i>3<i>P+...r_{in<sub2>i</sub2>} P</i>).

0050Next, the organizer <i>U</i>₁₁ of the sub-group Σ₁ is selected as an organizer of the group Σ, and the organizers <i>U</i>_<i>i</i>1 of the sub-groups Σ_i, on behalf of each sub-group, form a star-shaped structure together with <i>U</i>₁₁, so as to perform the basic negotiation of Embodiment 1 once again.

0051<i>U</i>₁₁ re-selects a DH secret value <maths id="math0093"><math display="inline"><msubsup><mi>r</mi><mn>11</mn><mi>ʹ</mi></msubsup><mo>∈</mo><msub><mi>Z</mi><mi>q</mi></msub><mo>,</mo></math><img file="EP2124381B1_D0093.tif" /></maths> generates a DH public value <maths id="math0094"><math display="inline"><msubsup><mi>X</mi><mn>11</mn><mi>ʹ</mi></msubsup><mo>=</mo><mfenced><msubsup><mi>x</mi><mn>11</mn><mi>ʹ</mi></msubsup><msubsup><mi>y</mi><mn>11</mn><mi>ʹ</mi></msubsup></mfenced><mo>=</mo><msubsup><mi>r</mi><mn>11</mn><mi>ʹ</mi></msubsup><mo>⁢</mo><mi>P</mi></math><img file="EP2124381B1_D0094.tif" /></maths> according to the DH secret value <maths id="math0095"><math display="inline"><msubsup><mi>r</mi><mn>11</mn><mi>ʹ</mi></msubsup></math><img file="EP2124381B1_D0095.tif" /></maths> and the public base point <i>P</i>, and broadcasts the DH public value <maths id="math0096"><math display="inline"><msubsup><mi>X</mi><mn>11</mn><mi>ʹ</mi></msubsup><mo>=</mo><mfenced><msubsup><mi>x</mi><mn>11</mn><mi>ʹ</mi></msubsup><msubsup><mi>y</mi><mn>11</mn><mi>ʹ</mi></msubsup></mfenced><mo>=</mo><msubsup><mi>r</mi><mn>11</mn><mi>ʹ</mi></msubsup><mo>⁢</mo><mi>P</mi></math><img file="EP2124381B1_D0096.tif" /></maths> in the group.

0052<i>U</i>_<i>i</i>1 (<i>i</i>∈1, 2, ..., <i>n</i>}) participates in the computation by taking the x-coordinate <i>x_{K<sub2>i</sub2>}</i> of the individual group key <i>K_i</i>, that is <i>x</i>_{<i>K</i><sub2>i</sub2>}, as a DH secret value, generates a DH public value <maths id="math0097"><math display="inline"><msubsup><mi>X</mi><mrow><mi>i</mi><mo>⁢</mo><mn>1</mn></mrow><mi>ʹ</mi></msubsup><mo>=</mo><mfenced><msubsup><mi>x</mi><mrow><mi>i</mi><mo>⁢</mo><mn>1</mn></mrow><mi>ʹ</mi></msubsup><msubsup><mi>y</mi><mrow><mi>i</mi><mo>⁢</mo><mn>1</mn></mrow><mi>ʹ</mi></msubsup></mfenced><mo>=</mo><msub><mi>x</mi><msub><mi>K</mi><mi>i</mi></msub></msub><mo>⁢</mo><mi>P</mi></math><img file="EP2124381B1_D0097.tif" /></maths> according to the DH secret value <i>x_{K<sub2>i</sub2>}</i> and the public base point <i>P</i>, and broadcasts the DH public value <maths id="math0098"><math display="inline"><msubsup><mi>X</mi><mrow><mi>i</mi><mo>⁢</mo><mn>1</mn></mrow><mi>ʹ</mi></msubsup><mo>=</mo><mfenced><msubsup><mi>x</mi><mrow><mi>i</mi><mo>⁢</mo><mn>1</mn></mrow><mi>ʹ</mi></msubsup><msubsup><mi>y</mi><mrow><mi>i</mi><mo>⁢</mo><mn>1</mn></mrow><mi>ʹ</mi></msubsup></mfenced><mo>=</mo><msub><mi>x</mi><msub><mi>K</mi><mi>i</mi></msub></msub><mo>⁢</mo><mi>P</mi></math><img file="EP2124381B1_D0098.tif" /></maths> in the group.

0053<i>U</i>₁₁ takes the x-coordinate <i>x</i>_{<i>K</i><sub2>1</sub2>} of the key value <i>K</i>₁ of the sub-group Σ₁, that is <i>x</i>_{<i>K</i><sub2>1</sub2>}, as a new secret exponent <i>z</i>' = <i>x</i>_{<i>K</i><sub2>1</sub2>}, computes an intermediate message DH value <i>z'P</i> = (<i>x'</i>,<i>y'</i>) based on the Diffie-Hellman key negotiation protocol on the Elliptic-Curve, generates an intermediate message <maths id="math0099"><math display="inline"><mfenced open="{" close="}"><msubsup><mi>c</mi><mn>1</mn><mi>ʹ</mi></msubsup><msubsup><mi>c</mi><mn>2</mn><mi>ʹ</mi></msubsup><mo>⋯</mo><msubsup><mi>c</mi><mi>t</mi><mi>ʹ</mi></msubsup></mfenced><mo>=</mo><mfenced open="{" close="}"><msubsup><mi>r</mi><mn>11</mn><mi>ʹ</mi></msubsup><mo>⁢</mo><mi mathvariant="italic">xʹ</mi><mfenced><mi>mod</mi><mspace width="1em" /><mi>p</mi></mfenced><mo>,</mo><msub><mi>x</mi><msub><mi>K</mi><mn>2</mn></msub></msub><mo>⁢</mo><mi>P</mi><mo>,</mo><msub><mi>x</mi><msub><mi>K</mi><mn>3</mn></msub></msub><mo>⁢</mo><mi>P</mi><mo>,</mo><mo>⋯</mo><mo>,</mo><msub><mi>x</mi><msub><mi>K</mi><mi>m</mi></msub></msub><mo>⁢</mo><mi>P</mi></mfenced></math><img file="EP2124381B1_D0099.tif" /></maths> carrying the intermediate message DH value, broadcasts the intermediate message <maths id="math0100"><math display="inline"><mfenced open="{" close="}"><msubsup><mi>c</mi><mn>1</mn><mi>ʹ</mi></msubsup><msubsup><mi>c</mi><mn>2</mn><mi>ʹ</mi></msubsup><mo>⋯</mo><msubsup><mi>c</mi><mi>t</mi><mi>ʹ</mi></msubsup></mfenced><mo>=</mo><mfenced open="{" close="}"><msubsup><mi>r</mi><mn>11</mn><mi>ʹ</mi></msubsup><mo>⁢</mo><mi mathvariant="italic">xʹ</mi><mfenced><mi>mod</mi><mspace width="1em" /><mi>p</mi></mfenced><mo>,</mo><msub><mi>x</mi><msub><mi>K</mi><mn>2</mn></msub></msub><mo>⁢</mo><mi>P</mi><mo>,</mo><msub><mi>x</mi><msub><mi>K</mi><mn>3</mn></msub></msub><mo>⁢</mo><mi>P</mi><mo>,</mo><mo>⋯</mo><mo>,</mo><msub><mi>x</mi><msub><mi>K</mi><mi>m</mi></msub></msub><mo>⁢</mo><mi>P</mi></mfenced></math><img file="EP2124381B1_D0100.tif" /></maths> in the group, and generates a group key <maths id="math0101"><math display="inline"><mi>K</mi><mo>=</mo><msubsup><mi>r</mi><mn>11</mn><mi>ʹ</mi></msubsup><mo>⁢</mo><mfenced><msub><mi>x</mi><msub><mi>K</mi><mn>2</mn></msub></msub><mo>⁢</mo><mi>P</mi><mo>+</mo><msub><mi>x</mi><msub><mi>K</mi><mn>3</mn></msub></msub><mo>⁢</mo><mi>P</mi><mo>+</mo><mo>⋯</mo><mo>+</mo><msub><mi>x</mi><msub><mi>K</mi><mi>m</mi></msub></msub><mo>⁢</mo><mi>P</mi></mfenced></math><img file="EP2124381B1_D0101.tif" /></maths> according to the DH secret value <maths id="math0102"><math display="inline"><msubsup><mi>r</mi><mn>11</mn><mi>ʹ</mi></msubsup></math><img file="EP2124381B1_D0102.tif" /></maths> selected by <i>U</i>₁₁ itself and the received DH public value <maths id="math0103"><math display="inline"><msubsup><mi>X</mi><mrow><mi>i</mi><mo>⁢</mo><mn>1</mn></mrow><mi>ʹ</mi></msubsup><mo>=</mo><mfenced><msubsup><mi>x</mi><mrow><mi>i</mi><mo>⁢</mo><mn>1</mn></mrow><mi>ʹ</mi></msubsup><msubsup><mi>y</mi><mrow><mi>i</mi><mo>⁢</mo><mn>1</mn></mrow><mi>ʹ</mi></msubsup></mfenced><mo>=</mo><msub><mi>x</mi><msub><mi>K</mi><mi>i</mi></msub></msub><mo>⁢</mo><mi>P</mi></math><img file="EP2124381B1_D0103.tif" /></maths> broadcasted by <i>U</i>_<i>i</i>1.

0054After receiving the intermediate message broadcasted by the organizer <i>U</i>₁₁, <i>U</i>_<i>i</i>1 (<i>i</i>∈{2, ..., <i>m</i>}) extracts the intermediate message DH value in the intermediate message, in which the intermediate message DH value <i>z'P</i> = (<i>x'</i>,<i>y'</i>) is specifically obtained by computing <maths id="math0104"><math display="inline"><mi mathvariant="italic">zʹP</mi><mo>=</mo><mfenced><mi mathvariant="italic">xʹ</mi><mi mathvariant="italic">yʹ</mi></mfenced><mo>=</mo><msubsup><mi>x</mi><msub><mi>K</mi><mi>i</mi></msub><mrow><mo>-</mo><mn>1</mn></mrow></msubsup><mo>⁢</mo><msubsup><mi>c</mi><mi>i</mi><mi>ʹ</mi></msubsup><mo>,</mo></math><img file="EP2124381B1_D0104.tif" /></maths> and then, according to the intermediate message DH value <i>z'P</i> = (<i>x'</i>, <i>y'</i>), the <i>x</i>' is obtained. As <maths id="math0105"><math display="inline"><msubsup><mi>c</mi><mn>1</mn><mi>ʹ</mi></msubsup><mo>=</mo><msubsup><mi>r</mi><mn>11</mn><mi>ʹ</mi></msubsup><mo>⁢</mo><mi mathvariant="italic">xʹ</mi><mfenced><mi>mod</mi><mspace width="1em" /><mi>p</mi></mfenced><mo>,</mo></math><img file="EP2124381B1_D0105.tif" /></maths><maths id="math0106"><math display="inline"><msubsup><mi>r</mi><mn>11</mn><mi>ʹ</mi></msubsup><mo>=</mo><msubsup><mi>c</mi><mn>1</mn><mi>ʹ</mi></msubsup><mo>⁢</mo><msup><mi mathvariant="italic">xʹ</mi><mrow><mo>-</mo><mn>1</mn></mrow></msup><mfenced><mi>mod</mi><mspace width="1em" /><mi>p</mi></mfenced><mo>,</mo></math><img file="EP2124381B1_D0106.tif" /></maths> so that the DH secret values selected by the organizer <i>U</i>₁₁ is obtained. According to <maths id="math0107"><math display="inline"><msubsup><mi>r</mi><mn>11</mn><mi>ʹ</mi></msubsup></math><img file="EP2124381B1_D0107.tif" /></maths> and the DH public value of <i>U</i>_i1 (<i>i</i>∈{2, ..., <i>m</i>})<i>, U</i>_<i>i</i>1 generates a group key <maths id="math0108"><math display="inline"><mi>K</mi><mo>=</mo><msubsup><mi>r</mi><mn>11</mn><mi>ʹ</mi></msubsup><mo>⁢</mo><mfenced><msub><mi>x</mi><msub><mi>K</mi><mn>2</mn></msub></msub><mo>⁢</mo><mi>P</mi><mo>+</mo><msub><mi>x</mi><msub><mi>K</mi><mn>3</mn></msub></msub><mo>⁢</mo><mi>P</mi><mo>+</mo><mo>⋯</mo><mo>+</mo><msub><mi>x</mi><msub><mi>K</mi><mi>m</mi></msub></msub><mo>⁢</mo><mi>P</mi></mfenced><mn>.</mn></math><img file="EP2124381B1_D0108.tif" /></maths>

0055Simultaneously, the other members <i>U_ij</i> (<i>i</i>∈[1,<i>m</i>], <i>j</i>∈[1,<i>n_i</i>]) in the group Σ monitor the message sent to the corresponding group Σ<i>_i</i>, obtain <i>x_{K<sub2>i</sub2>}</i> by using the obtained key <i>K_i</i> of the sub-group Σ<i>_i</i>, and compute the DH secret value <maths id="math0109"><math display="inline"><msubsup><mi>r</mi><mn>11</mn><mi>ʹ</mi></msubsup></math><img file="EP2124381B1_D0109.tif" /></maths> by using the broadcasted intermediate message, so as to obtain the sharing group key <maths id="math0110"><math display="inline"><mi>K</mi><mo>=</mo><msubsup><mi>r</mi><mn>11</mn><mi>ʹ</mi></msubsup><mo>⁢</mo><mfenced><msub><mi>x</mi><msub><mi>K</mi><mn>2</mn></msub></msub><mo>⁢</mo><mi>P</mi><mo>+</mo><msub><mi>x</mi><msub><mi>K</mi><mn>3</mn></msub></msub><mo>⁢</mo><mi>P</mi><mo>+</mo><mo>⋯</mo><mo>+</mo><msub><mi>x</mi><msub><mi>K</mi><mi>m</mi></msub></msub><mo>⁢</mo><mi>P</mi></mfenced><mn>.</mn></math><img file="EP2124381B1_D0110.tif" /></maths>

0056Finally, all the members obtain the same group key <maths id="math0111"><math display="inline"><mi>K</mi><mo>=</mo><msubsup><mi>r</mi><mn>11</mn><mi>ʹ</mi></msubsup><mo>⁢</mo><mfenced><msub><mi>x</mi><msub><mi>K</mi><mn>2</mn></msub></msub><mo>⁢</mo><mi>P</mi><mo>+</mo><msub><mi>x</mi><msub><mi>K</mi><mn>3</mn></msub></msub><mo>⁢</mo><mi>P</mi><mo>+</mo><mo>⋯</mo><mo>+</mo><msub><mi>x</mi><msub><mi>K</mi><mi>m</mi></msub></msub><mo>⁢</mo><mi>P</mi></mfenced><mn>.</mn></math><img file="EP2124381B1_D0111.tif" /></maths>

0057Through the above method, the group Σ is divided into <i>m</i> sub-groups = {Σ_1, Σ₂, ..., Σ<i>_m</i>} to reduce the load of the organizer in the group Σ, and all the members in the group Σ share the group key <maths id="math0112"><math display="inline"><mi>K</mi><mo>=</mo><msubsup><mi>r</mi><mn>11</mn><mi>ʹ</mi></msubsup><mo>⁢</mo><mfenced><msub><mi>x</mi><msub><mi>K</mi><mn>2</mn></msub></msub><mo>⁢</mo><mi>P</mi><mo>+</mo><msub><mi>x</mi><msub><mi>K</mi><mn>3</mn></msub></msub><mo>⁢</mo><mi>P</mi><mo>+</mo><mo>⋯</mo><mo>+</mo><msub><mi>x</mi><msub><mi>K</mi><mi>m</mi></msub></msub><mo>⁢</mo><mi>P</mi></mfenced><mn>.</mn></math><img file="EP2124381B1_D0112.tif" /></maths>

Embodiment 6

0058Referring to <figref idref="f0007">FIG. 8</figref>, a system for generating a group key is provided. The system includes a communication device as an organizer and a communication device as members.

0059The communication device as the organizer is configured to select a DH secret value according to system parameters, generate a DH public value according to the system parameters and the selected DH secret value, and broadcast the DH public value in the group; and after receiving DH public values of other devices, the communication device as the organizer is further configured to select a secret exponent, compute an intermediate message DH value according to the secret exponent, generate an intermediate message carrying the intermediate message DH value, broadcast the intermediate message in the group, and generate a group key according to the selected DH secret value and the DH public values of all the devices in the group.

0060The communication device as the members is configured to select DH secret values according to the system parameters, generate DH public values according to the system parameters and the selected DH secret values, and broadcast the DH public values; and after receiving the DH public value and the intermediate message broadcasted by the communication device as the organizer, the communication device as the members is further configured to compute the DH secret value selected by the organizer according to the intermediate message, verify the DH secret value to be correct, and then generate a group key according to the DH secret value and the DH public values of all the devices in the group.

0061When members join or leave the group, the communication device as the organizer and the communication device as the members in the system are further configured to re-generate and broadcast new DH public values.

Embodiment 7

0062Referring to <figref idref="f0007">FIG. 9</figref>, a communication device is provided. The device includes: a system parameter selecting module, a DH public value generating and broadcasting module, an intermediate message generating and broadcasting module, and an organizer group key generating module.

0063The system parameter selecting module is configured to select system parameters based on an elliptic curve.

0064The DH public value generating and broadcasting module is configured to select a DH secret value according to the system parameters selected by the system parameter selecting module, generate a DH public value according to the system parameters and the selected DH secret value, and broadcast the generated DH public value.

0065The intermediate message generating and broadcasting module is configured to select a secret exponent after receiving DH public values broadcasted by other communication devices, compute an intermediate message DH value according to the secret exponent, generate an intermediate message carrying the intermediate message DH value according to the DH secret value selected by the DH public value generating and broadcasting module, and broadcast the intermediate message.

0066The organizer group key generating module is configured to receive the DH public values broadcasted by other communication devices, and generate a group key according to the DH secret value selected by the DH public value generating and broadcasting module and the DH public values broadcasted by other communication devices.

0067In order to further improve the communication device, when members join or leave the group, the communication device further includes a group key updating module.

0068The group key updating module is configured to instruct the DH public value generating and broadcasting module to generate and broadcast a new DH public value when new members join or leave the group.

0069When new members join the group, the process of generating a new group key is described as follows.

0070The group key updating module instructs the DH public value generating and broadcasting module to select a new DH secret value for the organizer and the new members according to the system parameters selected by the system parameter selecting module, to generate a new DH public value according to the system parameters and the selected new DH secret value, and to broadcast the new DH public value.

0071The intermediate message generating and broadcasting module selects a new secret exponent after receiving DH public values of the new members broadcasted by other devices, computes a new intermediate message DH value according to the new secret exponent, generates a new intermediate message carrying the new intermediate message DH value according to the new DH secret value selected by the DH public value generating and broadcasting module, and broadcasts the new intermediate message.

0072The organizer group key generating module generates a new group key according to the new DH secret value selected by the DH public value generating and broadcasting module and the received DH public values of the new members broadcasted by other devices.

0073When members leave the group, the process of generating a new group key is described as follows.

0074The group key updating module instructs the DH public value generating and broadcasting module to select a new DH secret value for the organizer according to the system parameters selected by the system parameter selecting module, to generate a new DH public value according to the system parameters and the selected new DH secret value, and to broadcast the new DH public value.

0075The intermediate message generating and broadcasting module selects a new secret exponent after receiving DH public values of the remaining members broadcasted by other devices, computes a new intermediate message DH value according to the new secret exponent, generates a new intermediate message carrying the new intermediate message DH value according to the new DH secret value selected by the DH public value generating and broadcasting module, and broadcasts the new intermediate message.

0076The organizer group key generating module generates a new group key according to the new DH secret value selected by the DH public value generating and broadcasting module and the received DH public values of the remaining members broadcasted by other devices.

Embodiment 8

0077Referring to <figref idref="f0008">FIG. 10</figref>, another communication device is provided. The device includes: a system parameter selecting module, a DH public value generating and broadcasting module, and a member group key generating module.

0078The system parameter selecting module is configured to select system parameters based on an elliptic curve.

0079The DH public value generating and broadcasting module is configured to select DH secret values according to the system parameters selected by the system parameter selecting module, generate DH public values according to the system parameters and the selected DH secret values, and broadcast the generated DH public values.

0080The member group key generating module is configured to receive DH public values and an intermediate message broadcasted by another communication device, compute a DH secret value selected by an organizer according to the intermediate message, verify the DH secret value to be correct according to the DH public value broadcasted by the communication device that broadcasts the intermediate message, and generate a group key according to the DH secret value and DH public values broadcasted by the other communication devices except the communication device that broadcasts the intermediate message.

0081In order to further improve the communication device, when members join or leave the group, the communication device further includes a group key updating module.

0082The group key updating module is configured to instruct the DH public value generating and broadcasting module to generate and broadcast new DH public values for newly joined members when new members join the group.

0083When new members join the group, the group key updating module instruct the DH public value generating and broadcasting module to select new DH secret values for the new members according to the system parameters selected by the system parameter selecting module, to generate new DH public values of the new members according to the system parameters and the selected new DH secret values, and to broadcast the new DH public values of the new members. After receiving the new intermediate message, the member group key generating module computes a new DH secret value selected by an organizer according to the new intermediate message, verifies the new DH secret value to be correct according to the received new DH public value of the organizer, and generates a new group key according to the new DH secret value and the new DH public values of the new members broadcasted by the DH public value generating and broadcasting module.

0084When members leave the group, after receiving a new intermediate message, the member group key generating module computes a new DH secret value selected by the organizer according to the new intermediate message, verifies the new DH secret value to be correct according to the received new DH public value of the organizer, and generates a new group key according to the new DH secret value and new DH public values of the remaining members broadcasted by the DH public value generating and broadcasting module.

0085The above embodiments have the following advantages. <ol id="ol0002"><li>1) High security: The computation complexity of the elliptic curve discrete logarithm problem is at the exponential level currently, but the RSA public key cryptosystem is at the sub-exponential level.</li><li>2) Low computation load and high processing speed: Under the same computation resource condition, the elliptic curve cryptography system has a higher processing speed as compared with the RSA and the digital signature algorithm (DSA).</li><li>3) Small storage space: The key length and system parameters of the elliptic curve cryptography system are much shorter than that of the RSA and DSA. The 160-bit elliptic curve cipher (ECC) realizes the same security level as the 1024-bit RSA or DSA, and the 210-bit ECC realizes the same security level as the 2048-bit RSA or DSA, which means that the elliptic curve cryptography system occupies a much smaller storage space.</li><li>4) Low bandwidth requirement: For a given security level, the ECC has a smaller parameter than the RSA and DSA. For a higher security level, the difference in the sizes of the parameters of the ECC and the RSA and DSA is more obvious. The parameter in a smaller size brings advantages of a high computation speed, a short key, and a small key certificate, and thus the signature length and cipher text length are also short.</li></ol>

0086In view of the above, the ECC can realize a high security with a small overhead (such as, bandwidth, computation load, storage space, and power consumption) and a small delay, which is especially suitable for the situation when the computation capability and bandwidth are rather limited, such as the security communication in an Ad Hoc network environment. Compared with similar solutions, when realizing the same security level, the ECC has the advantages of a high computation speed, a small storage space, a low network bandwidth requirement, and the like.

0087The embodiments of the present invention support the joining and leaving motions of the members. Specifically, when members join the group, the newly joined members and the organizer are required to participate in the negotiation, and when members leave the group, the organizer is required to re-select a random number, without re-selecting random numbers for the remaining members. Thus, the embodiments of the present invention have a high computation speed, occupy a small storage space, and are flexible in usage.

0088When being applied in a large-scale group communication, the technical solutions of the embodiments of the present invention can effectively reduce the computation load of the organizer while slightly increasing the communication load. Meanwhile, as the protocol is based on the elliptic curve cryptography system, the higher protocol operation efficiency can be achieved, including less message exchanges, lower occupied network bandwidth, smaller key storage space, and higher computation speed.

0089The technical solutions of the above embodiments can be implemented through hardware and software, and the software is stored in a readable storage medium, such as a floppy disk, a hard disk, or an optical disk of a computer.

0090The above descriptions are merely preferred embodiments of the present invention, but not intended to limit the present invention.