Method, system and device for generating group key

[0001] The invention relates to the field of network communication, in particular the method, system and device for generating a group key.

Background of the invention [0002] An ad hoc network is a self-organizing multi-hop network with a dynamically changing topology structure in which nodes are often displaced and have limited power, and the trust relationship and wireless transmission links between nodes are rather weak. For this reason, the design of the group key negotiation protocol in an ad hoc network is significantly different from the conventional solution. In an ad hoc network, to ensure secure communications, messages are typically encrypted and then sent. Because of the advantage in performance of a symmetrical cryptographic system, the complexity of message processing is significantly reduced by sharing the key in a group. Meanwhile, the ad hoc network is also a dynamic peer group and lacks the support of a permanent, trustworthy third party, so the session group key for message encryption must be established through negotiation by all group members to improve the security and reliability of the session group key. In addition, the group key negotiation protocol in the ad hoc network is required to take into account the dynamic properties of the network topology and implement key forward and backward security as well as efficient support for the nodes' joining and lowering mechanisms.

[0003] All existing group key negotiation solutions are based on the discrete algorithm problem in the finite body. There is a group key negotiating solution suitable for use in an ad hoc network in which n represents the number of group members; Ui represents the group member with the serial number i; U1 represents the selected organizer, which is temporary and can be any member. FIG. 1 is a block diagram of a group key negotiation solution in the prior art. With reference to Fig. 1, the group key negotiation solution includes:

101: System parameters are selected and system initialization is performed. Assuming that p and q are large prime numbers, Zp is a ring of integers modulo p, g is an element of the ring Zp, and q is the order of g, with q being the smallest possible integer satisfying the equation g^q = 1 mod q.

- 2 102: All members choose secret DH values, generate public values

DH based on secret DH values ​​and broadcast the generated public DH values ​​in the group. Member of the U group_AND randomly selects the secret DH value_AND e Z_q, generates the public value of DH g^ri based on the selected DH secret value and broadcasts the generated public g value^ri in a group where and takes values

1, 2, ...., n.

103: After receiving the public DH values ​​of other members, the organizer selects the secret exponent, generates an intermediate message based on the secret exponent and public DH values, and announces the indirect message in the group and in the meantime generates a group key.

The organizer U1 randomly selects the secret exponent ve Zq, generates an intermediate message M_t, M_AND = vg^r1ri based on the secret exponent, the public DH value of the organizer itself and the public values ​​of other members, respectively, and sends the generated message to Mi in the group, where i assumes values ​​1, 2, ..., n.

In particular, the organizer calculates the function F = f (g^r1, g^r2,, g^rn) based on the public DH value of each member and the public DH value of the organizer himself, where f represents the mapping from Zp to Zi, and then generates the group key K = g^fov based on the secret exponent v.

104: Upon receipt of an intermediate announcement by the organizer, each group member extracts a secret exponent and generates a group key based on the secret exponent and public value of each member.

[0004] After receiving Mi, all members of the group Ui decrypt the value of vi and calculate the function F = f (g^r1, g^r2,, g^rn), where f represents the mapping of Z_p to Z_and, and the value of v is subjected to mathematical operations, the result of which must be modulo p.

[0005] Through the above steps, group keys calculated by all members of group U_and are the same, that is, the group key is K = g^fov.

[0006] When a member joins or leaves a group, it is required to regenerate the group key based on all current group members after changing group members, the calculation being similar to the above process and will not be described again.

[0007] In an embodiment of the invention, the inventors find that the solution for negotiating a group key of an ad hoc network requires a large amount of computation and thus has low processing speed and high storage and bandwidth requirements.

[0008] Li, D .; Sampalli, S .: "An Efficient Group Key Establishment In Location-Aided mobile ad hoc Networks", ACM, 2005, pages 57-64 describes two scalable maximum fit (M2) algorithms for deploying tree-based binary group key agreements in MANET . In addition, the proposed technique is uncomplicated because it is based on the exchange of a key based on

- 3 Diffie-Hellman elliptic curve instead of the regular Diffie-Hellman algorithm and does not require third party support.

[0009] Document XP002667535 describes quotes from the publication Handbook of Applied Cryptography (Menezes, Vanstone, Oorschot, USA, 1997), and in particular the generation of a group key using the Diffie-Hellmann approach applied to at least three entities whose functionality forms a star structure.

Summary of the Invention [0010] To reduce the amount of computation and space used and to reduce the bandwidth requirements of a group key negotiation solution, the invention provides a method, system and devices for generating a group key. Technical solutions are described as follows.

[0011] In a first aspect of the invention, the method of generating a group key selects system parameters based on an elliptic curve, and the following steps are carried out in individual embodiments of the method.

[0012] The group members form a star structure and select an organizer from the group members.

[0013] Group members individually randomly select secret DH values ​​based on system parameters, individually generate public DH values ​​based on system parameters and selected secret DH values, and advertise public DH values ​​in the group.

[0014] After receiving the public DH values ​​of other group members, the organizer selects the secret exponent, calculates the DH value of the intermediate message based on the secret exponent, generates an intermediate message transferring the DH value of the intermediate message, broadcasts the intermediate message in the group and generates the group key based on the secret DH value selected by the organizer and public DH values ​​of other group members.

[0015] After receiving the intermediate message and the public DH value from the organizer, other group members calculate the secret DH value selected by the organizer based on the indirect message, verify the correctness of the calculated secret DH value chosen by the organizer based on the received public DH value of the organizer and generate a group key for based on the secret DH value chosen by the organizer and the public DH values ​​of other group members.

[0016] In a second object of the invention, the group key generation system comprises a communication device as an organizer and a communication device as members. The following functions are implemented in individual forms of implementation.

[0017] The communication device as an organizer is configured to select a secret DH value based on system parameters, generate a public DH value based on system parameters and a selected secret DH value, and broadcast

- 4 public DH values ​​in the group; and after receiving the public DH values ​​of other devices, the communication device as the organizer is also configured to select the secret exponent, calculate the DH value of the intermediate message based on the secret exponent, generate an intermediate message transferring the DH value of the intermediate message, broadcast the intermediate message in the group and generate the group key on based on the secret DH value selected and the public DH value of all devices in the group.

[0018] The communication device as members is configured to select secret DH values ​​based on system parameters, generate public DH values ​​based on system parameters and selected secret DH values, and broadcast public DH values; and after receiving the public DH value and the intermediate message broadcast by the communication device as the organizer, the communication device as members is also configured to calculate the secret DH value selected by the organizer based on the indirect message, verifying the correctness of the calculated secret DH value selected by the organizer, and then calculating the group key based on the secret DH value chosen by the organizer and the public DH value of all devices in the group.

[0019] Furthermore, in a third aspect of the invention, the communication device comprises a system parameter selection module, a public DH value generation and broadcast module, an intermediate message generation and broadcast module, and a group key generation organizer module. The following functions are implemented in the individual forms of implementation.

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

[0021] The public DH generating and broadcasting module is configured to select the secret DH value based on the system parameters selected by the system parameter selection module, generate the public DH value based on the system parameters and selected secret DH value, and broadcast the public DH value.

[0022] The intermediate message generation and broadcasting module is configured to select the secret exponent after receiving public DH values ​​broadcast by other communication devices, calculating the intermediate DH value based on the secret exponent, generating an intermediate message transferring the intermediate DH value based on the secret selected DH value by the module generating and disseminating the public DH value, and broadcasting an intermediate message.

[0023] The group key generation organizer module is configured to receive public DH values ​​broadcast by other communication devices, generate a group key based on the secret DH value selected by the module

- 5 generating and broadcasting public DH values ​​and public DH values ​​broadcast by other communication devices.

[0024] In a fourth object of the invention, the communication device comprises a system parameter selection module, a public DH value generation and broadcast module, and a group key generating member module. The following functions are implemented in individual forms of the device's implementation.

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

[0026] The public DH generation and broadcasting module is configured to select secret DH values ​​based on the system parameters selected by the system parameter selection module, generate public DH values ​​based on the system parameters and selected secret DH values, and broadcast public DH values.

[0027] The group key generating member module is configured to receive a public DH value and an intermediate message broadcast by another communication device, calculate the secret DH value selected by the organizer based on the indirect message, verifying the correctness of the calculated secret DH value selected by the organizer based on the public DH value broadcast by the communication device broadcasting the intermediate message and generating a group key based on the secret DH value chosen by the organizer and public DH values ​​broadcast by all other communication devices, except for the communication device that broadcasts an intermediate message.

[0028] Technical solutions of the invention are based on a cryptographic system based on elliptic curves, in which the organizer securely transmits the secret exponent to other group members through the DH value of an indirect message shared with other group members, and then all members negotiate, based on public key cryptographic technique based on an elliptic curve to get a group key. Compared to the state of the art, the advantages of the technical solution of the invention are high calculation speed, low space and bandwidth requirements, while maintaining the same security.

Brief description of the drawings [0029]

Fig. 1 is a block diagram of a method for generating a group key in the prior art;

Fig. 2 is a block diagram of a method for generating a group key according to embodiment 1 of the invention;

Fig. 3 is a schematic view of the star structure formed by group members according to embodiment 1 of the invention;

Fig. 4 is a schematic view of the star structure formed by group members when new members join the group according to embodiment 2 of the invention;

Fig. 5 is a block diagram of a method for generating a group key when new members join a group according to embodiment 2 of the invention;

Fig. 6 is a schematic view of the star structure formed by group members when the groups are joined according to embodiment 3 of the invention;

Fig. 7 is a block diagram of a method for generating a group key when the groups are combined according to embodiment 3 of the invention;

Fig. 8 shows a structural view of the group key generation system according to embodiment 6 of the invention;

Fig. 9 shows a structural view of a communication device according to embodiment 7 of the invention; and

Fig. 10 shows a structural view of another communication device according to embodiment 8 of the invention.

Detailed Description of Embodiments [0030] To make the objects, technical solutions and advantages of the invention clearer, the embodiments of the invention are described in detail below with reference to the accompanying drawings.

[0031] Embodiments of the invention provide a method, system and apparatus for generating a group key applicable in an ad hoc network. In particular, group members form a star structure and the member is selected to be the organizer responsible for securely transmitting the secret exponent to other group members through the indirect DH DH value shared with other group members, and then all members negotiate based on public key cryptographic based technology on the elliptic curve to get a group key. The DH value of the intermediate message is a parameter derived from the Diffie-Hellman key negotiation protocol (abbreviated as the DH key negotiation protocol) based on an elliptic curve.

[0032] Embodiments of the invention are based on a cryptographic system based on an elliptic curve. Elliptic curve cryptography (ECC) was introduced by Neal Koblitz and Victor Miller in 1985. The advantages of a cryptographic system based on an elliptic curve are high security, low computational load, short key length, high processing speed, low storage space, low bandwidth requirements and the like, so it has broad security application perspectives. Recently, a cryptographic system based on an elliptic curve has been accepted by standardization organizations such as

- 7 American National Institute of Standardization (ANSI), Institute of Electrical and Electronics Engineers (IEEE), International Organization for Standardization (ISO) and National Institute of Standardization and Technology (NIST) as a standard.

Embodiment 1 [0033] Fig. 2 is a block diagram of a method for generating a group key according to an embodiment of the invention. With reference to Fig. 2, the method includes:

201: Members of the U group₁, ..., U_n they form a star structure and the organizer is chosen.

According to an embodiment of the invention, n represents the number of members of the group and Ui represents the member of the group with serial number i (i = 1, 2, ..., n). The group member is selected as the organizer, and in this embodiment U1 is selected as the organizer. The organizer is not trusted but is temporary and can be played by any member. Fig. 3 is a schematic view of the star structure formed by group members.

202: System parameters are selected and system initialization is performed. The specific process is described as follows.

GF (p) is a finite field of the order expressed by the prime number p, and the elliptic curve EC: yx ax β (a, e ^ GF (p), 4a³27e +²(mod ph'0; ap is a large prime number over 190 bits) defined in the field. ECp (a, β) = {(x, y) ly²= x³+ ax + e (mod p)} OO (O is identity) creates an abelian group - an alternating group.

In a given ECC system, the PeEC point_p(α, β) is selected as the public base point, and the row P is a large prime number q (generally q> 120 bits). G = {O, P, 2P, ..., (q-1) P} is defined. From this it is known that G is a finite cyclic abelian group, and q is a cyclic period.

203: Member of the U group_and chooses the secret value of DH r_andeZ_q based on the system parameters, it generates the public value of DH X_and= (X_and, y_and) = R_andP based on the secret DH ri value and the public base point P, and announces the public DH value Xi = (xi, yi) = riP in the group where i takes the values ​​1, ..., n.

204: After receiving public DH Xi values ​​published by other members, the organizer of U₁ randomly chooses the secret exponent zZ_q (FROM_q is a ring of at least non-negative residues obtained after division of integers modulo q, aq is the prime number among system parameters, calculates the DH value of the intermediate message zP = (x, y), based on the Diffie-Hellman key negotiation protocol based on the elliptic curve, generates an intermediate message {c1, c2, ..., cn} = {r1x (mod p), r2zP, r3zP, ..., rnzP}, in which p is a prime number among system parameters, based on the received public DH values ​​of other members, the secret secret exponent z selected, secret DH value r1, and the x coordinate DH value of the intermediate message zP, broadcasts the intermediate message {c1, c2, ..., cn} = {r1x (mod p), r2zP, r3zP, ..., rnzP} in the group; generates a key

- 8 group K = r1 (r2P + r3P + ... + rnP) based on the secret DH r1 value chosen by the organizer himself and the public DH values ​​of other members.

It should be noted that in the embodiment the intermediate message may also be generated based on the received public DH values ​​of other members; chosen secret exponent z, secret value DH r1 and y coordinate of the intermediate DH message zP. The specified rule is similar to generating an intermediate message based on the received public DH values ​​of other members, the secret secret exponent z selected, secret value r1 and the x coordinate of the intermediate DH message zP, and will not be described again.

205: After receiving the intermediate message broadcast by the organizer U1, a member of the Ui group (and assumes values ​​in the range 2, 3, ..., n) extracts the DH value of the intermediate message from the intermediate message, whereby the DH value of the intermediate message zP is obtained in particular by calculating zP = (x, y) = ri^-1ci, and then, based on the DH value of the intermediate message zP = (x, y), the value x is obtained. Because c1 = r1x (mod p), r1 = c1x^-1 (mod p), the secret DH r1 value selected by the organizer is calculated.

206: After calculating the secret DH r1 value chosen by the organizer, a member of the group Ui (and assumes values ​​in the range 2, 3, ..., n) verifies whether the equation r1P = X1 is satisfied or not, and if it is is step 207; otherwise, step 203 is performed again. Verification of the equation r1P = X1 is to check whether the secret DH value chosen by the organizer is falsified or not.

207: Member of the group Ui (and assumes values ​​in the range 2, 3, ..., n) generates the group key K = r1 (r1P + r3P + ... + rnP) based on the secret DH value chosen by the organizer and the public DH values ​​of all other group members except the organizer.

[0034] Through the above process, the group keys calculated by all members of the group Ui are the same, that is, the group key is K = r1 (r2P + r3P + ... + rnP) and all members reserve the Xi values ​​received in the key negotiation stage .

Embodiment 2 [0035] In an embodiment, a method of generating a group key is provided by negotiating when a new member joins the group. The embodiment is based on embodiment 1. It is assumed that the group Σ = {υ₁, U₂, ..., U_n} performed basic negotiations of embodiment 1 and acquired the shared group key Kr₁(y₂pr₃P ... r, P^>). Now t members intend to join group Σ, and are respectively represented as Un + 1, Un + 2, ..., Un + t. The process of negotiating a new key requires that the newly added members and the U1 organizer participate. With reference to Fig. 4, U1, V2, ..., Un + t together form a star structure.

[0036] Fig. 5 is a flowchart of a method for generating a group key when new members join the group. With reference to Fig. 5, the method of generating a group key when new members join the group includes:

301: Organizer U₁ and a new member of the U_and choose secret DH values? . on the basis of system parameters, they generate public DH values: a, v, y, and a? -_;s based on secret DH values ​​and the public base point P, and proclaim the public DH values, 'ć =) λ_{; ι}··.^:; ι = in the group, where i takes the values ​​n + 1, ..., n + t.

302: After receiving public DH values, announced by new members, assuming that the secret exponent is J organizer U₁ calculates the DH value of an intermediate message:? ·, Ν, y based on the protocol

Diffie-Hellman negotiating the key based on the elliptic curve, generates an intermediate message

! .- l ¹ - ⁼ Li ··· '.-1- pi / enos / ącv DH value of the intermediate message, broadcasts the intermediate message

Cfr + 1 »»^cn + f5 = tel * Ρλ ^rn + l^sP> ^rn + 2^and 8^mp^e’ ^and generates a new group key Λ? j " ¹¹¹ "based on the secret DH value of_x chosen by the organizer and public values

DH new members.

In this embodiment, xK represents the coordinate of the K key shared by Σ = {υ₁, U₂, ..., U_n}, and all group members know that the U1 organizer chooses in advance the x coordinate or the y coordinate as z '. The organizer U1 chooses the coordinate x as z ', and assuming that z' = yK, the organizer U1 can choose the coordinate y as z '.

303: After receiving an intermediate message. . . , , '. . ? '. and announced by the organizer₁, new member of the U_and (ie {n + 1, ..., n + t}) extracts the DH value of the intermediate message from the intermediate message, with the DH value z'P of the intermediate message being specifically calculated as, and then based on the value of DH z'P = (x ', y'), the value of x 'is calculated. Because = 'Ś ?? · and? «Pj,? J = Cj /'. ' "¹ζ ?? ιϊ7 /), the secret DH value is calculated_x chosen by the organizer.

304: After calculating the secret DH value chosen by the organizer, a new U member_and (ie {n + 1, ..., n + t}) verifies whether the equation is satisfied or not, and if so, step 305 is performed; otherwise, step 301 is performed again. Checking equation =, 'ΐ) is to check whether the secret DH value chosen by the organizer has been violated or not.

- 10,305: New member of the U_and (ie {n + 1, ..., n + t}) generates a new group key K = rj (ΐ ^ + ιί * -t- itrtsf * Ί- Ί-based on the secret DH value chosen by the organizer and public DH values new members.

306: Other members of U₂, ..., U_n in group Σ get z '= x_K based on the previous value z, calculate and then obtain x 'based on the DH value z'P = (x', y) intermediate message. Because, - ς'χ, ν^-1 ; ?? ισς'ί?.? /, the secret value DH η chosen by the organizer is calculated. Then, based on the secret value of DH '_Ί chosen by the organizer and public DH values ​​of new members, each of the other U members₂, ..., U_n generates a new group key

<img file="PL2124381T3_D0001.tif" />

[0037] By means of the above process, after t members join group Σ, each member of group U_and ..., n + t}) calculates the new group key and the newly added members reserve the values ​​received in the key negotiation stage.

[0038] For example, it is assumed that the group Σ = {υι, ..., U₅} performed basic negotiations and obtained the shared key K = r1 (r2P + r3P + ... + r5P. Member G '= {U6} wants to join the group and shares a new key with the members in the group Według · According to the invention, the key negotiation process requires U1 contact with a newly joined member U6 so that all group members can calculate and get a new group key. In this example, after U1, U2, ..., U6 together form a star structure, the following specific steps are performed.

(1) The organizer U] selects the secret value DH £ Z- based on the system parameters and announces the message = (λ j = to U₆. AT₆ selects the secret value DH ΐ Z- based on the system parameters, and broadcasts the message Λ'ί = =; 'and? to U].

(2) After receipt of the public DH value as published by U₆, assuming that the secret exponent is z '= xK, the organizer U] calculates the DH value z'P = (x', y ') of the intermediate message, based on the Diffie-Hellman protocol of negotiating the key based on the elliptic curve, generates an intermediate message ( mo-ti)?), i *} transferring the DH value of the intermediate message, broadcasts the intermediate message = ί? jv ζ ?? ιί? £ ΐ in the group and generates the group key Λ '= based on the secret DH value of the year selected by the same the organizer and the public value of DH of the U6 member.

In the example, xK represents the x coordinate of the K key shared by Σ = {υι, u₂, ..., U5}.

(3) After receiving the intermediate message broadcast by the organizer U], U6 extracts the DH value of the intermediate message from the intermediate message in which

- the DH value z'P of the intermediate message is in particular obtained by calculating, and then x 'is obtained based on the DH value z'P = (x', y '). Because? J = γ^-andGiL $), the secret DH value selected by the Ui organizer is calculated.

(4) After calculating the secret DH value chosen by the organizer U₁, U₆ checks if the equation =, '&lt;_L is met or not, and if so, step (5) is performed; otherwise stage (1) is performed. The purpose of checking the equation is to verify whether the secret DH value chosen by the organizer has been violated or not.

(5) U₆ generates the group key A 'based on the secret DH value;

selected by the organizer U1 and the public value of DH U6.

(6) Other members of the U₂, ..., U₅ in group Σ get z '= x_K based on previous z values, calculate, get x 'based on the DH value z'P = (x', y ') intermediate message. Because Cj. =? · ΧΛ ',? J = i.'] /^_and i ??! ifi / A the secret DH value selected by the organizer U is calculated₁. Then based on the secret DH value:.

chosen by the organizer₁ and the public value of DH of a new U member₆, each of the other members of U₂, ..., U₅ generates a group key JT = rtfa P.

[0039] Through the above method, all members obtain the same group key

<img file="PL2124381T3_D0002.tif" />

Embodiment 3 [0040] In this embodiment, a method of generating a group key is provided when groups are combined. The embodiment is based on the embodiment

1. Connected are to be t groups, which are represented respectively as {Σι, Σ * ···, Σ} and each group Σ · has n_and members, that's Σ⁼{υα, U_i2, ..., U_ini} (ie {1, t}). Each group performed the basic negotiation of embodiment 1, respectively, and group members Σ share the group key K Here U₁₁ is chosen as the new organizer, Σ₁ is a large connecting group, and Σ2, ... Σι are small connecting groups. The negotiation process requires the participation of each U organizer_i1 each group Σ ·. With reference to Fig. 6, the groups together form a star structure, and with reference to Fig. 7, the key negotiation process is described as follows.

401: U₁₁ selects the secret value DH&gt;_π ΐ Z- based on the system parameters, generates the public DH value, '&lt;_at = H / n ¹ = ΐ'ιΐ ·⁵ on the basis of secret value and public base point P, and proclaims the public value of DH ⁱⁿ g^rup^e.

402: Assuming the secret DH value is the organizer of U_i1 for each small group connecting Σ2, ..., Σι generates the public value of DH A_;1 = (, y_;and,/_;and j = Y_;andAnd on

- 12 based on the secret value of r_;. and the public base point P, and broadcasts the public value of DH Λ_{; ι} = (,_RJIg_;andj =? '_;andA in the group, where i takes the values ​​2, ..., vol.

In the embodiment, xKi represents the x coordinate of the Ki key shared in Σ⁼{υη, U_i2, ..., U_ini} (ie {1, t}), and all group members know that the organizer Ui1 selects in advance the x coordinate or the y coordinate as z '. In the embodiment, the organizer Ui1 selects the coordinate x as z ', but it can also be assumed that z' = yKi, i.e. the organizer Ui1 selects the coordinate y as z '.

403: After the receipt of the public value of DH A_;and announced by U_i1, assuming that the secret exponent with '= xK1, U11 calculates the DH value with' P = (x ', y') of an intermediate message, based on the Diffie-Hellman protocol of negotiating a key based on an elliptic curve, generates an intermediate message {cpC₂, ..., ¾} = {γ ^ χ \ modphr ^ a F, r_sl2 P r ...._fl2 f} carrying the DH value of the intermediate message, broadcasts the intermediate message:: in group, and generates a new group key A '= u A ~ ż?_ANDA ~ ¹¹¹ ~ A and based on secret value

-1, chosen by U₁₁ and the public value of U_i1.

404: After receiving an intermediate message broadcast by U₁₁, U_i1 (ie {2, ..., t}) extracts the DH value of the intermediate message from the intermediate message, wherein the DH value of z'P of the intermediate message is in particular obtained by calculating and then, based on the DH value

ME = -ń. j.^:,! intermediate message, x 'is obtained. Because = 'il ·' Ru-X^;Hi ⁼ the secret DH g value, calculated by the organizer, is calculated.

405: After calculating the secret DH value, chosen by U₁₁, U_i1 (i ^ {2, ..., t}) verifies whether the equation is satisfied or not, and if it is, then step 406 is performed; otherwise, step 401 is performed again.

Checking the equation; · ^? = A ^ is to verify whether the secret DH value chosen by the organizer has been violated or not.

406: U, i (ie {2, generates the group key A r_at AND_;1A -? -¹¹¹ -_;andA j based on the secret DH * value chosen by U₁₁ and the public value of DH U_i1.

407: Other members of the small connecting group Σ (i ^ {2, ..., t}), except for the organizer, get z '= x_K1 based on the previous value z, calculate (ί Έ (1,2, ..., t}), and get z 'on the basis of the value DH z'P = {x', y) of the intermediate message. Because. "And⁼ 1χ. '\' Αζΐϊϊί Ar, '11 ^{= ;}and''' ^_and Χΐί?; Υ Ar, the secret DH g 'value calculated by the organizer is calculated. Then based on the secret value DH x ', chosen by U₁₁ and

- 13 public value of DH U_I1 each of the other members of the small connecting group Σ (and ^E{2, ..., t}) generates a new group key K = ri (viP + P + «-tf_tlP).

408: Based on xK1 obtained in advance, other group members in a large connecting group Σ₁, except for the organizer, calculate a¹ P = (x, y) = (ί - - «4Χ and get x 'based on the DH value z'P = {x', y ') intermediate message. Because ^ 1 =, 1 χλ, X^:, 'H ^{= ;}and ''? / !, the secret DH value selected by the organizer is calculated. Then based on the secret DH value chosen by U₁₁ and the public value of DH U_i1 each of the other members of the large connecting group Σ₁generates a new group key = (r_aiP + y₃₁ P + · -) - r ^ P).

[0041] Through the above method, t groups are combined into one group with U11 as the organizer and all members share the group key = ri (riP -ł- ri / * - (- "+ r_tl p).

Embodiment 4 [0042] In an embodiment, a method of generating a group key is provided when members leave the group. The embodiment is based on the embodiment

1. It is assumed that members in the group Σ = {υ₁, ..., U_n} they carried out the basic negotiation from the embodiment 1.k members Σ '= {υ_ί1, ..., U_jk} wants to leave the group, and the rest of the group Σ '' = {υ₁, ..., U_J1-1, Uji + and, ..., Uj_k+₁, ...., U_n} remain in the group. Other group members must calculate a new group key to prevent members who have left the group group key of the current group, and the following specific steps are performed.

[0043] First, after the group members grupy leave the organizer Σ₁ re-selects the secret DH value based on system parameters, and other members in G '' do not need to re-select the secret DH values.

[0044] Then the other members of the group Z "= {Ui, ..., Uji-i, Uji + i, ..., Ujk-i, Ujk + 1, ..., Un} again carry out the method of negotiating the group key with embodiment 1, generates a new intermediate message f ^{r 1 r 1 Γ} 'ΐ -

L^C1 »/ C / j-ił C / j + l * ···» j ~ {r [x \ modp), ... ^. ^ Ρ, τ ^ ζΡ, ..., ν ^ ζΡ, ν ^ ζΡ, ..., r_nzP}, and generate a new group key

K = i \ {r₂P Ψ · "+ η₁_₁Ρ-Ι-η_ι4ιΡ + r ^ _iP -t- łfo + iP -t- ”+ r_KP) to share.

[0045] If the organizer in the original group E has left the group, it is required to re-select the member as the organizer in group G '' and then to perform the above steps to generate a new group key = ^f1and (y₂P -t- ·· -1- Γ / j-iP -t- T)_{L + 1}P -1- r ^ -χΡ + r ^ P +&gt; «· + r_nP) to share.

Example of embodiment 5

[0046] As the group scale is still expanding, the design load and the organizer load increase dramatically. When the scale of the network increases too much, the performance of the organizer becomes a bottleneck of the protocol, so you need to properly modify the performance of the organizer to reduce the load on the organizer.

[0047] In an embodiment, a method of negotiating a group key for communication in a large-scale group is provided. The embodiment is based on embodiment 1. When the scale of the group members involved in the negotiation is very large, the group members grupy are divided into m subgroups, which are marked as Σ = {Σι, Σ₂, ..., Σιη} and all nodes form a star structure. Each subgroup Σι has n_andmembers who are marked as {U_i1, U_i2, ..., U_in}. n_and members can also form a star structure, and U_i1 becomes the organizer of the subgroup Σ.

[0048] Regarding the method of group division, the group can be divided based on a unique machine code corresponding to each node device (similar to the MAC address or Ethernet network card), and must be divided based on geographical locations. The following steps are performed.

[0049] First, n_and members of the subgroup Σ (i = 1, 2, ..., m) creates the star structure and performs basic negotiation from embodiment 1 to obtain the group key Ki = ri1 (ri2P + ri3P + ... + riniP).

[0050] Then the organizer U₁₁ subgroups Σ₁ is chosen as the organizer of the group Σ and the organizers are U_i1 grupι subgroups on behalf of each subgroup form together with U₁₁ star structure to re-perform the basic negotiation of the embodiment

1.

[0051] U₁₁ re-selects the secret DH value? -_at £ I-, generates the public DH, Y value₁₁⁼ · ί'Ίΐ.Ίΐ^{1 = !}ίί ^ based on the secret DH value and public base point P, and broadcasts the public value DH = (λH / n.¹ = ³ in a group.

[0052] U_i1 (ie {1, 2, ..., n}) participates in the calculations by taking the coordinate xx_Ki individual group key K_and, that's x_Ki, as a secret DH value, generates the public DH value ¹ based on the secret value of DH x_Ki and the public base point P, and broadcasts the public value of DH = ⁱⁿ g^rup^e.

[0053] U₁₁ takes the xx coordinate_K1 K key values₁ subgroup Σι, this is x_K1, as a new secret exponent with '= xK1, calculates the DH value with' P = (x ', y') of an intermediate message, based on the Diffie-Hellman key negotiation protocol based on an elliptic curve, generates an intermediate message: transmitting the DH message's indirectness , broadcasts an intermediate message ⁱⁿ gfupie ^and g^{energizes the key} gmpowy

- 15 g "= Ή P Ή ·· Ί- based on the secret DH value chosen by

AT₁₁ and the received public value of DH Λ / =) = Λ; . announced by U_i1.

[0054] After receiving the intermediate message broadcast by the organizer U11, Ui1 (ie {2, ..., m}) extracts the DH value of the intermediate message from the intermediate message in which the DH value z'P = (x ', y') of the message the intermediate is in particular obtained by calculating and then, based on the DH value z'P = (x ', y') of the intermediate message, x 'is obtained. Because fu = Yp^-and ve ry pi, secret DH values ​​selected by the organizer U11 are calculated. Based on · .. and the public value of Ui1 (ie {2, ..., m}), Ui1 generates a group key^K - ^rn^P + "* + ^xitmP) · [0055] At the same time, other members of Uj (ie [1, m], them [1, n]) in group Σ monitor the message sent to the appropriate group Σ get x_Ki by using the obtained key K_and subgroups Σί and calculate the secret DH / value by using an intermediate broadcast message to obtain a shared group key

<img file="PL2124381T3_D0003.tif" />

[0056] Finally, all members obtain the same group key

<img file="PL2124381T3_D0004.tif" />

[0057] Through the above method, the group Σ is divided into m subgroups = {Σ₁, ···&gt; Σ ™} to limit the organizer's workload in group Σ and all group members Σ share the group key

Embodiment 6 [0058] With reference to Fig. 8, a group key generation system is provided. The system includes a communication device as an organizer and a communication device as members.

[0059] The communication device as an organizer is configured to select a secret DH value based on system parameters, generate a public DH value based on system parameters and a selected secret DH value, and broadcast the public DH value in the group; and after receiving the public DH values ​​of other devices, the communication device as the organizer is also configured to select the secret exponent, calculate the DH value of the intermediate message based on the secret exponent, generate an intermediate message transferring the DH value of the temporary message, broadcast the temporary message in the group, and generate the group key on based on the secret DH value selected and the public DH value of all devices in the group.

[0060] The communication device as members is configured to select secret DH values ​​based on system parameters, generate public DH values ​​based on system parameters and selected secret DH values, and

- 16 broadcasting of public DH values; and after receiving the public D value and the intermediate message broadcast by the communication device as the organizer, the communication device as members is also configured to calculate the secret DH value selected by the organizer based on the indirect message, verify the correctness of the secret DH value, and then generate the group key based on the secret DH values ​​and public DH values ​​of all devices in the group.

[0061] When members join or leave a group, the communication device as the organizer and the communication device as members in the system are also configured to regenerate and broadcast public DH values. Embodiment 7 [0062] With reference to Fig. 9, a communication device is provided. The device includes a system parameter selection module, a DH value generation and broadcast module, an intermediate message generation and broadcast module, and a group key generation organizer module.

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

[0064] The public DH generating and broadcasting module is configured to select the secret DH value based on the system parameters selected by the system parameter selection module, generate the public DH value based on the system parameters and selected secret DH value, and broadcast the generated public DH value.

[0065] The intermediate message generation and broadcasting module is configured to select the secret exponent after receiving public DH values ​​broadcast by other communication devices, calculate the intermediate DH value based on the secret exponent, generate an intermediate message transferring the intermediate DH value based on the secret selected DH value by the module generating and disseminating the public DH value, and broadcasting an intermediate message.

[0066] The group key generation organizer module is configured to receive public DH values ​​broadcast by other communication devices, and generate a group key based on the secret DH value selected by the module for generating and broadcasting public DH values ​​and public DH values ​​broadcast by other communication devices.

[0067] To further improve the communication device when members join or leave the group, the communication device also includes a group key update module.

[0068] The group key update module is configured to instruct the public DH value generation and broadcast module to generate and broadcast a new public DH value when new members join or leave the group.

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

[0070] The group key update module instructs the public DH generation and broadcast module to choose a new secret DH value for the organizer and new members based on the system parameters selected by the system parameter selection module, to generate a new public DH value based on the system parameters and the new secret selected the value of DH, and spreading the new public value of DH.

[0071] The intermediate message generation and broadcasting module selects a new secret exponent after receiving the public DH values ​​of new members broadcast by other devices, calculates the new intermediate DH value based on the new secret exponent, generates a new intermediate message carrying the new intermediate message DH value based on the new secret DH value selected by the module for generating and broadcasting the public DH value, and broadcasting a new intermediate message.

[0072] The group key generation organizer module generates a new group key based on the new secret DH value selected by the module for generating and broadcasting the public DH value and received public DH values ​​of new members broadcast by other devices.

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

[0074] The group key update module instructs the public DH generation and broadcast module to choose a new secret DH value for the organizer based on the system parameters selected by the system parameter selection module, generate a new public DH value based on the system parameters and the selected new secret DH value, and spreading the new DH public value.

[0075] The intermediate message generation and broadcasting module selects the new secret exponent after receiving the public DH values ​​of the other members broadcast by other devices, calculates the new intermediate DH value based on the new secret exponent, generates a new intermediate message transferring the DH value of the intermediate message based on the new secret the DH value selected by the module for generating and broadcasting the public DH value, and broadcasting a new intermediate message.

[0076] The group key generation organizer module generates a new group key based on the new secret DH value selected by the module for generating and broadcasting the public DH value and received public DH values ​​of the other members broadcast by other devices.

Embodiment 8 [0077] Referring to Fig. 10, another communication device is provided. The device includes: a system parameter selection module, a DH value generation and publicity module, and a group key generation module.

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

[0079] The public DH generation and broadcasting module is configured to select secret DH values ​​based on system parameters selected by the system parameter selection module, generate public DH values ​​based on system parameters and selected secret DH values, and broadcast generated public DH values.

[0080] The group key generating member module is configured to receive public DH values ​​and an intermediate message broadcast by another communication device, calculate the secret DH value selected by the organizer based on the indirect message, verify the correctness of the secret DH value based on the public DH value broadcast by the communication device broadcasting an intermediate message, and generating a group key based on the secret DH value and public DH values ​​broadcast by other communication devices, with the exception of the communication device that broadcasts the intermediate message.

[0081] To further improve the communication device when members join or leave the group, the communication device also includes a group key update module.

[0082] The group key update module is configured to instruct the public DH value generation and broadcast module to generate and broadcast new public DH values ​​for newly joined members when new members join the group.

[0083] When new members join the group, the group key update module instructs the public DH generation and broadcast module to select new secret DH values ​​for new members based on the system parameters selected by the system parameter selection module, to generate new public DH values ​​for new members on based on the system parameters and selected new secret DH values, and the announcement of new public DH values ​​for new members. After receiving a new intermediate message, the group key generation module calculates the new secret DH value selected by the organizer based on the new intermediate message, verifies the correctness of the new secret DH value based on the received new public DH value of the organizer, and generates a new group key based on the new secret value DH and new public DH values ​​of new members broadcast by the module for generating and broadcasting public DH values.

[0084] When members leave the group, after receiving a new intermediate message, the group key generation module calculates the new secret DH value selected by the organizer based on the new intermediate message, verifies the correctness of the new secret DH value based on the received new public DH value of the organizer, and generates a new group key based on the new DH secret value and the new public values ​​of the other members broadcast by the public DH generation and broadcast module.

[0085] The above embodiments have the following advantages.

1) High security: the computational complexity of the discrete logarithmic curve problem is currently at exponential level, but the RSA public key cryptographic system is at sub-exponential level.

2) Low computational load and high processing speed: under the same computing resource conditions, a cryptographic system based on elliptic curves has a higher processing speed compared to RSA and the digital signature algorithm (DSA).

3) Little space: key length and parameters of a cryptographic system based on an elliptic curve are much shorter than in the case of RSA and DSA. The 160-bit Elliptic Curve Cipher (ECC) performs the same level of security as the 1024-bit RSA or DSA, and the 210-bit ECC performs the same level of security as the 2048-bit RSA or DSA, which means that the curve-based cryptographic system elliptical takes up much less space.

4) Small bandwidth requirements: for a given security level, ECC has a smaller parameter than RSA and DSA. For a higher level of security, the difference in ECC and RSA and DSA parameter sizes is more obvious. The smaller size parameter provides the advantages of high computing speed, short key and small key certificate, hence the signature length and cipher text length are also short.

[0086] In view of the above, ECC can realize high security at low load (throughput, computational load, storage space and power consumption) and with a small delay, which is particularly suitable when computing performance and throughput are rather limited, as is communication security in an ad hoc network environment. Compared to similar solutions, when implementing the same level of security, ECC has the advantages of high calculation speed, low storage space, low network bandwidth requirements and the like.

[0087] Embodiments of the invention support members joining and leaving the group. In particular, when members join the group, newly joined members and organizers are required to participate in the negotiation, and when members leave the group, the organizer is required to

- 20 re-chose a random number without re-selecting random numbers for the other members. In this way, embodiments of the invention have a high calculation speed, take up little space, and are flexible to use.

[0088] When used in a large-scale communication group, technical solutions of embodiments of the inventions can effectively reduce the computational load on the organizer, while the communication load increases slightly. At the same time, because the protocol is based on a cryptographic system based on an elliptic curve, it is possible to achieve greater protocol performance, including less message exchanges, less network bandwidth used, less space used by the key, and faster calculation speed.

[0089] Technical solutions of the above embodiments can be implemented in hardware and in software, and the software is stored on a readable data carrier, such as a floppy disk, hard disk, or computer optical disk.

[0090] The above descriptions are only preferred embodiments of the invention, but are not intended to limit the invention.

Prepared and verified

Grażyna Palka

Patent Attorney