Key sharing device and system for configuration thereof

Abstract

A method of configuring a network device for key sharing and a method for a first network device to determine a shared key are provided. The method of configuring uses a private modulus (p.sub.1) a public modulus (N), and a bivariate polynomial (f.sub.1) having integer coefficients, the binary representation of the public modulus and the binary representation of the private modulus are the same in at least key length (b) consecutive bits. Local key material for a network device is generated by substituting an identity number into the bivariate polynomial and reducing modulo the private modulus the result of the substitution to obtain a univariate polynomial. Security may be increased by adding (440) one or more obfuscating numbers to coefficients of the univariate polynomial to obtain an obfuscated univariate polynomial. In a use phase, the network device determines a shared cryptographic key, by substituting (530) the identity number of another network device into the univariate polynomial and reducing modulo the public modulus and reducing modulo a key modulus.

Claims

1. A method of configuring a network device for key sharing, the method comprising the steps of: obtaining in electronic form a private modulus (p.sub.1), a public modulus (N), and a bivariate polynomial (f.sub.1) having integer coefficients, the binary representation of the public modulus and the binary representation of the private modulus are the same in at least key length (b) consecutive bits; generating local key material for the network device, the generating step comprising obtaining in electronic form an identity number (A) for the network device, and determining using a polynomial manipulation device a univariate polynomial from the bivariate polynomial by substituting the identity number into the bivariate polynomial, reducing modulo the private modulus the result of the substitution; and electronically storing the generated local key material at the network device, and storing the public modulus in the network device.

2. The method as claimed in claim 1, wherein the step of generating local key material for the network device comprises: generating an obfuscating number and adding, using a polynomial manipulation device, the obfuscating number to a coefficient of the univariate polynomial to obtain an obfuscated univariate polynomial, the generated local key material comprising the obfuscated univariate polynomial.

3. The method as claimed in claim 1, wherein the bivariate polynomial (f.sub.1) is a symmetric polynomial.

4. The method as claimed claim 1, wherein the least significant key length (b) bits of the binary representation of the public modulus are the same as the least significant key length (b) bits of the private modulus.

5. The method as claimed in claim 1, wherein the method further comprises the steps of: generating the private modulus (p.sub.1) using an electronic random number generator, and/or generating the bivariate polynomial using an electronic random number generator by generating one or more random coefficients for the bivariate polynomial.

6. The method as claimed in claim 1, wherein the public modulus satisfies 2.sup.(a+2)b−1≦N, wherein N represents the public modulus, a represents the degree of the bivariate polynomial and b represents the key length.

7. The method as claimed in claim 1, wherein said method further comprises the steps of: obtaining in electronic form multiple private moduli (p.sub.i), and multiple bivariate polynomials (f.sub.i) having coefficients modulo p.sub.i, such that there is a set of key length (b) consecutive positions in which the binary representation of the public modulus agrees with the binary representation of all private moduli; and determining the univariate polynomial comprises substituting the identity number into each one of the multiple bivariate polynomials (f.sub.i), reducing modulo a private modulus of the multiple private moduli corresponding to the one symmetric bivariate polynomial, and adding the multiple results of the multiple reductions.

8. The method as claimed in claim 1, wherein the obfuscating number is generated such that
ε.sub.A,i|<2.sup.(a+1−i)b wherein ε.sub.A,i denotes the obfuscating number, i denotes the degree of the monomial corresponding to the coefficient, a represents the degree of the bivariate polynomial and b represents the key length.

9. A method for a first network device, configured by the method of configuring a network device for key sharing as claimed in claim 1, to determine a shared key, the key being a cryptographic key, the method comprising the steps of: obtaining local key material for the first network device in electronic form, the local key material comprising a, optionally obfuscated, univariate polynomial; obtaining an identity number for a second network device, the second network device being different from the first network device; substituting the identity number of the second network device into the, optionally obfuscated, univariate polynomial; reducing the result of the substituting modulo the public modulus and reducing modulo a key modulus; and deriving the shared key from the result of the reduction modulo the key modulus.

10. The method as claimed in claim 9, wherein said method further comprises the step of: determining if the first network device and the second network device have derived the same shared key, and if not deriving a further shared key from the result of the reduction modulo the key modulus.

11. The method as claimed in claim 9, wherein said method further comprises the step of: dividing the result of the substituting modulo the public modulus by a zero bit string divisor which is a power of two, the zero bit string divisor being larger than 1.

12. A system for configuring a network device for key sharing, the system comprising: a key material obtainer for obtaining in electronic form a private modulus (p.sub.1), a public modulus (N), and a symmetric bivariate polynomial (f.sub.1) having integer coefficients, the binary representation of the public modulus and the binary representation of the private modulus are the same in at least key length (b) consecutive bits; and a generator for generating local key material for the network device, said generator comprising: a network device manager for obtaining in electronic form an identity number (A) for the network device and for electronically storing the generated local key material at the network device, and storing the public modulus in the network device; and a polynomial manipulation device for determining a univariate polynomial from the bivariate polynomial by substituting the identity number into the bivariate polynomial, reducing modulo the private modulus the result of the substitution.

13. A first network device configured to determine a shared key as claimed in claim 1, the key being a cryptographic key, the first network device comprising: a local key material obtainer for obtaining local key material for the first network device in electronic form, the local key material comprising a, optionally obfuscated, univariate polynomial; a receiver for obtaining an identity number for a second network device, the second network device being different from the first network device; a polynomial manipulation device for substituting the identity number of the second network device into the, optionally obfuscated, univariate polynomial and reducing the result of the substituting modulo the public modulus followed by and reducing modulo a key modulus; and a key derivation device for deriving the shared key from the result of the reduction modulo the key modulus.

14. A non-transitory computer-readable medium encoded with a computer program comprising computer program code means for causing a computer, when running the computer program, to configure a network device for key sharing by performing the steps of: obtaining in electronic form a private modulus (p.sub.1), a public modulus (N), and a bivariate polynomial (f.sub.1) having integer coefficients, the binary representation of the public modulus and the binary representation of the private modulus are the same in at least key length (b) consecutive bits; generating local key material for the network device, the generating step comprising obtaining in electronic form an identity number (A) for the network device, and determining using a polynomial manipulation device a univariate polynomial from the bivariate polynomial by substituting the identity number into the bivariate polynomial, reducing modulo the private modulus the result of the substitution; and electronically storing the generated local key material at the network device, and storing the public modulus in the network device.

Description

BRIEF DESCRIPTION OF THE DRAWINGS

(1) These and other aspects of the invention are apparent from and will be elucidated with reference to the embodiments described hereinafter. In the drawings,

(2) FIG. 1 is a schematic block diagram illustrating a root key material generator,

(3) FIG. 2 is a schematic block diagram illustrating a local key material generator,

(4) FIG. 3 is a schematic block diagram illustrating a communication network,

(5) FIG. 4 is a schematic flow chart illustrating generating local key material,

(6) FIG. 5 is a schematic flow chart illustrating generating a shared key,

(7) FIG. 6 is a schematic sequence diagram illustrating generating a shared key.

(8) It should be noted that items which have the same reference numbers in different Figures, have the same structural features and the same functions, or are the same signals. Where the function and/or structure of such an item has been explained, there is no necessity for repeated explanation thereof in the detailed description.

LIST OF REFERENCE NUMERALS

(9) 100 a root key material obtainer 110 a public modulus element 112 a polynomial degree element 114 a key length element 116 a number of polynomials element 122 a private modulus manager 124 a symmetric bivariate polynomial manager 200 a local key material generator 210 a public material element 220 a private material element 240 a polynomial manipulation device 250 a network device manager 260 an obfuscating number generator 300 a communication network 310 a first network device 320 a second network device 330 a transceiver 342 a polynomial manipulation device 344 a local key material obtainer 346 a key derivation device 348 a key equalizer 350 a cryptographic element

DETAILED EMBODIMENTS

(10) While this invention is susceptible of embodiment in many different forms, there is shown in the drawings and will herein be described in detail one or more specific embodiments, with the understanding that the present disclosure is to be considered as exemplary of the principles of the invention and not intended to limit the invention to the specific embodiments shown and described.

(11) Below an embodiment of the key sharing method is described. The method has a set-up phase and a use phase. The set-up phase may include initiation steps and registration steps. The initiation steps do not involve the network devices.

(12) The initiation steps select system parameters. The initiation steps may be performed by the trusted third party (TTP). However, the system parameters may however also be regarded as given as inputs. In that case the trusted third party need not generate them, and the initiation steps may be skipped. For example, the trusted third party may receive the system parameters from a device manufacturer. The device manufacturer may have performed the initiation steps to obtain the system parameters. For convenience of exposition we will refer to the trusted third party as performing the initiation steps, bearing in mind that this is not necessary.

(13) Initiation Steps

(14) The desired key length for the key that will be shared between devices in the use phase is selected; this key length is referred to as ‘b’. A typical value for a low security application may be 64 or 80. A typical value for a consumer level security may be 128. Highly secret applications may prefer 256 or even higher values.

(15) The desired degree is selected; the degree controls the degree of certain polynomials. The degree will be referred to as ‘a’, it is at least 1. A practical choice for a is 2. A more secure application may use a higher value of a, say 3 or 4, or even higher. For a simple application also a=1 is possible. The case a=1 is related to the so called ‘hidden number problem’; higher “a” values are related to the extended hidden number problem confirming that these cases are hard to break.

(16) The number of polynomials is selected. The number of polynomials will be referred to as ‘m’. A practical choice for m is 2. A more secure application may use a higher value of m, say 3 or 4, or even higher. Note that a low-complexity application, say for resource bounded devices may use m=1.

(17) Higher values of security parameters a and m increase the complexity of the system and accordingly increase its intractability. More complicated systems are harder to analyze and thus more resistant to cryptanalysis.

(18) In an embodiment, a public modulus N is selected satisfying 2.sup.(a+2)b−1≦N and most preferably also N≦2.sup.(a+2)b−1. The bounds are not strictly necessary; the system could also use a smaller/larger value of N, although that is not considered the best option.

(19) Often the key length, degree and number of polynomials will be pre-determined, e.g., by a system designer, and provided to the trusted party as inputs. As a practical choice one may take N=2.sup.(a+2)b−1. For example if a=1,b=64 then N may be N=2.sup.192−1. For example if a=2, b=128 then N may be N=2.sup.512−1. Choosing for N the upper or lower bound of the above interval has the advantage of easy computation. To increase complexity one may choose a random number within the range for N.

(20) A number of m private moduli p.sub.1, p.sub.2, . . . , p.sub.m, are selected. Moduli are positive integers. During the registration steps each device will be associated with an identity number. Each selected private modulus is larger than the largest identity number used. For example, one may bound identity numbers by requiring that they are less or equal to 2.sup.b−1, and that the selected private moduli are larger than 2.sup.b−1. Each selected number satisfies the following relationship p.sub.j=N+γ.sub.j.Math.2.sup.b. Wherein the γ.sub.j are integers such that |γ.sub.j|<2.sup.b. One practical way of selecting numbers that satisfy this requirement is to choose a set of m random integers γ.sub.j such that −2.sup.b+1≦γ.sub.j≦2.sup.b−1 and compute the selected private moduli from the relationship p.sub.j=N+γ.sub.j.Math.2.sup.b. Having |γ.sub.j| a bit larger may be allowed, however, a problem may occur in that the modular operation goes too far so that shared keys might not be equal.

(21) For m>1, the system is more complicated, and thus more secure, since modulo operation for different moduli are combined even though such operations are not compatible in the usual mathematical sense. For this reason it is advantageous to choose the selected private moduli as pair wise distinct.

(22) A number of m symmetric bivariate polynomials f.sub.1, f.sub.2, . . . , f.sub.m of degrees a.sub.j are generated. All degrees satisfy a.sub.j≦a, most preferably a=MAX{a.sub.1, . . . , a.sub.m}. A practical choice is to take each polynomial of degree a. A bivariate polynomial is a polynomial in two variables. A symmetric polynomial f satisfies f(x,y)=f(y,x). Each polynomial f.sub.j is evaluated in the finite ring formed by the integers modulo p.sub.j, obtained by computing modulo p.sub.j. The integers modulo p.sub.j form a finite ring with p.sub.j elements. In an embodiment the polynomial f.sub.j is represented with coefficients from 0 up to p.sub.j−1. The bivariate polynomials may be selected at random, e.g., by selecting random coefficients within these bounds. Note that some or all of the bivariate polynomials may be generated asymmetrically, which leads to a system with two groups. We will assume for simplicity that the all selected polynomials are symmetric.

(23) The security of the key sharing depends on these bivariate polynomials as they are the root keying material of the system; so preferably strong measures are taken to protect them, e.g., control procedures, tamper-resistant devices, and the like. Preferably the selected integers p.sub.1, p.sub.2, . . . , p.sub.m are also kept secret, including the value γ.sub.j corresponding to p.sub.j, though this is less critical. We will refer to the bivariate polynomials also in the following form: for j=1, 2, . . . , m, we write f.sub.j(x,y)=Σ.sub.i=0.sup.af.sub.i,j(x)y.sup.i.

(24) The above embodiment can be varied in a number of ways. The restrictions on the public and private moduli may be chosen in a variety of ways, such that obfuscation of the univariate polynomial is possible, yet that the shared keys obtained at network devices remain sufficiently close to each other sufficiently often. As explained, what is sufficient will depend on the application, the required security level and the computing resources available at the network devices. The above embodiment combines positive integers such that the modular operations which are carried out when generating the polynomials shares are combined in a non-linear manner when they are added over the integers creating a non-linear structure for the local key material stored on a network device. The above choice for N and p.sub.j has the property that: (i) the size of N is fixed for all network devices and linked to a; (ii) the non-linear effect appears on the most significant bits of the coefficients forming the key material stored on the device. Because of that specific form the shared key may be generated by reducing module 2.sup.b after the reduction modulo N.

(25) These design concepts can be applied in a more general way to improve on aspects (i) and (ii) as mentioned in the last paragraph. Below different, general constructions, are given to choose the public and private moduli. To address the first point (i), this structure for N and p.sub.j fits a more general expression where we write p.sub.j=2.sup.X+γ.sub.j2.sup.Y.sup.j−1 such that for each j, Y.sub.j+bα.sub.j=X and |γ.sub.j|<2.sup.b. This expression allows for a more variable form p.sub.j while ensuring a maximum effect when introducing non-linear effects. Note that one can also make, Y.sub.j+bα.sub.j≈X where the difference between the left and right-hand side is a fraction of the key length.

(26) To address the second point, the above form for N and p.sub.j fits an even more general expression in which p.sub.j=β2.sup.X+γ.sub.j2.sup.Y.sup.j+ζ.sub.j2.sup.Z.sup.j. By setting, e.g., ζ.sub.j=−1,β=1, and Z.sub.j=0 ∀j we obtain the previous expression in which the different γ.sub.j values introduce a non-linear effect in the most significant bits of the coefficients of the key material stored on a network device. In this case, the constant public modulus (N) is N=2.sup.X−1, while the private variable part used in the generation of different positive integers involved in the modular operations is γ.sub.j2.sup.Y.sup.j. Alternatively, we can set γ.sub.j=1,β=1,Z.sub.j=0, Y.sub.j=(α.sub.j+1)b,X=(α.sub.j+2)b ∀j while ζ.sub.j are different for different j such that |ζ.sub.j|<2.sup.b. In this case, the differences in ζ.sub.j allow introducing a non-linear effect in the least significant bits of the coefficients of the local key material stored on a node. The construction of the public part in this case is also different and equal to N=β.sub.j2.sup.X.sup.j+γ.sub.j2.sup.Y.sup.j=2.sup.X+2.sup.b(α.sup.j.sup.+1) i.e., the parts that remain constant. Note in this case the non-linear effect is in the lowest part, and because of the condition for maximum mixing effect mentioned before, then the difference between Y.sub.j−Z.sub.j−log.sub.2(ζ.sub.j) must be α.sub.jb. In a similar way, other constructions can be defined following the same concept.

(27) Registration Steps

(28) In the registration step each network device is assigned keying material (KM). A network device is associated with an identity number. The identity number may be assigned on demand, e.g. by the TTP, or may already be stored in the device, e.g., stored in the device at manufacture, etc.

(29) The TTP generates a set of keying material for a device A as follows:
KM.sup.A(X)=Σ.sub.j=1.sup.m<f.sub.j(x,A)>.sub.p.sub.j+2.sup.bΣ.sub.i=0.sup.aε.sub.A,iX.sup.i=Σ.sub.iC.sub.i.sup.Ax.sup.i

(30) Wherein KM.sup.A(X) is the keying material of a device with identity number A; X is a formal variable. Note that the keying material is non-linear. The notation < . . . >.sub.p.sub.j denotes reducing modulo p.sub.j each coefficient of the polynomial between the brackets. The notation ‘ε.sub.A,i’ denotes a random integer, which is an example of an obfuscating number, such that |ε.sub.A,i|<2.sup.(a+1−i)b. Note that any one of the random integers may be positive or negative. The random numbers ε are generated again for each device. The term Σ.sub.i=0.sup.aε.sub.A,iX.sup.i thus represents a polynomial in X of degree a, of which the coefficient length is shorter with increasing degree. Alternatively, a more general, but more complicated condition is that Σ.sub.i=0.sup.a|ε.sub.A,i|.Math.2.sup.b+i is small, e.g., <2a. Note that the step of adding obfuscation is optional and may be omitted, but is preferred to obtain a higher security level. We will assume that obfuscation is used.

(31) All other additions may either use the natural integer arithmetic, or (preferably) they use addition modulo N. So the evaluation of the univariate polynomials Σ.sub.j=1.sup.m<f.sub.j(x,A)>.sub.p.sub.j is each individually done modulo a smaller modulus p.sub.j but the summation of these reduced univariate polynomials themselves is preferably done modulo N. Also adding the obfuscating polynomial 2.sup.bΣ.sub.i=0.sup.aε.sub.A,iX.sup.i may be done using natural integer arithmetic or, preferably, modulo N. The keying material comprises the coefficients C.sub.i.sup.A with i=0, . . . , a. The keying material may be presented as a polynomial as above. In practice, the keying material may be stored as a list, e.g., an array, of the integers C.sub.i.sup.A. The device A also receives the numbers N and b. Manipulation of polynomials may be implemented, e.g., as manipulation of arrays containing the coefficients, e.g., listing all coefficient in a predetermined order. Note that polynomials may be implemented, in other data structures, e.g., as an associative array (aka a ‘map’) comprising a collection of (degree, coefficient) pairs, preferably such that each coefficient appears at most once in the collection. The coefficients C.sub.i.sup.A that are provided to the device are preferably in the range 0, 1, . . . N−1.

(32) In case, that the more general construction for N and the integer numbers p.sub.j is used, the obfuscating polynomial needs to be adapted so that the random numbers E affect different parts of the coefficients. For instance, if the non-linear effect is introduced in the least significant bits of the coefficients of the key material stored on the network devices, then the random numbers should only affect the highest part of the coefficients and a variable number of bits in the lowest part of the coefficients. This is a direct extension of the method described above and other extensions are feasible.

(33) Use Phase

(34) Once two devices A and B have an identity number and received their keying material from the TTP, they may use their keying material to obtain a shared key. Device A may perform the following steps to obtain his shared key. First, device A obtains the identity number B of device B, then A generates the shared key by computing the following:
K.sub.AB=<<KM.sup.A(x)|.sub.x=B>.sub.N>.sub.2.sub.b=<<Σ.sub.iC.sub.i.sup.AB.sup.i>.sub.N>.sub.2.sub.b

(35) That is, A evaluates his keying material, seen as an integer polynomial, for the value B; the result of evaluating the keying material is an integer. Next device A reduces the result of the evaluation first modulo the public modulus N and then modulo the key modulus 2.sup.b. The result will be referred to as A's shared key, it is an integer in the range of 0 up to 2.sup.b−1. For its part, device B can generate B′ shared key by evaluating its keyed material for identity A and reducing the result modulo N and then modulo 2.sup.b.

(36) In line with the above description, if a more general expression of N and the positive integers p.sub.j is used, then the method to obtain the b-bits key needs a small adaptation. In particular, if the non-linear effect is introduced in the lowest bits of the coefficients of the key material stored on the network devices while the second term in the expression of N is Y.sub.j, then the key is generated as follows:

(37) $K_{AB} = < \frac{< {KM}^{A} (x) |_{x = B} >_{N}}{2^{Y_{j}}} >_{2^{b}}$

(38) Because the bivariate polynomials in the root key material are symmetric A's shared key and B's shared key are often, though not necessarily always, equal. The particular requirements on the integers p.sub.1, p.sub.2, . . . , p.sub.m, and on the (optional) random numbers ε are such that the keys are often equal and almost always close to each other modulo two to the power the key length. If A and B have obtained the same shared key, then they may use it as a symmetric key which is shared between A and B; for example, it may be used for a variety of cryptographic applications, for example, they may exchange one or more messages encrypted and/or or authenticated using the shared key. Preferably, a key derivation algorithm is applied to the shared key for further protection of the master key, e.g., a hash function may be applied.

(39) If A and B have not obtained the same shared key, then it is almost certain that these keys are close to each other, by removing a number of the least significant bits of the keys, the generated keys can almost always be made the same. A and B may verify if their shared keys are equal by performing a key confirmation, for example, A may send to B a message containing the pair (m, E(m)), wherein m is a message, say a fixed string or a random number, and E(m) is the encryption using A's shared key.

(40) By decrypting E(m) using B's shared key, B may verify if the keys are equal. If so, B may respond to A informing him of the situation.

(41) If the keys are not equal, A and B may engage in a key equalization protocol. For example, they may make use of the fact that the two keys are arithmetically close to each other. For example, network device A and B may iteratively remove a least significant bit and send a key confirmation message until the keys are equal. After obtaining equal keys, A and B may perform a key derivation algorithm to regain keys of a usual key length.

(42) The selected m private moduli, p.sub.1, p.sub.2, . . . , p.sub.m, are preferably pair wise relatively prime. If these numbers are pair wise relatively prime the lack of compatibility between the modulo operations is increased. Obtaining pair wise relatively prime numbers may be obtained by selecting the integers in order, testing for each new integer if all pairs of different numbers are still relatively prime, if not the just selected number is removed from the set. This procedure continues until all m numbers are selected.

(43) The complexity increases even further by requiring that the selected m private moduli, p.sub.1, p.sub.2, . . . , p.sub.m, are distinct prime numbers. In that case each prime number may be required to have the form p.sub.j=N+γ.sub.j.Math.2.sup.b. Wherein the γ.sub.j are integers such that |γ.sub.j|<2.sup.b. Experiments have confirmed that these primes are easily available. For example, one may repeatedly select a random γ.sub.j and test the resulting p.sub.j until a prime is found. The same applies if a more general expression, as described above, is applied. Indeed it follows from the prime number theorem for arithmetic progressions that as long as a is of about the same order of magnitude as b, in particular for a<b, such primes are abundant. In particular, for any combination of key length in the group 64, 128, 196, 256 and degree in the group 2, 3, we confirmed by experiment that many prime numbers of this form could be generated using the above algorithm within practical time limits. When using prime numbers each polynomial f.sub.j is thus taken in the finite field with p.sub.j elements.

(44) Many variants are possible to choose the various parameters used during the registration and use phase. For example, in a simplified embodiment, the private moduli are smaller than the public modulus and satisfy the relationship p.sub.j=N−β.sub.j.Math.2.sup.b. Wherein the β.sub.j are positive integers such that β.sub.j<2.sup.b. One practical way of selecting numbers that satisfy this requirement is to choose a set of m random positive integers β.sub.j such that β.sub.j<2.sup.b and compute the selected private moduli from the relationship p.sub.j=N−β.sub.j.Math.2.sup.b.

(45) As noted, the difference between Y.sub.j−Z.sub.j−log.sub.2(ζ.sub.j) may be α.sub.jb. In a similar way, other constructions can be defined following the same concept. In particular, we can write p.sub.j=β2.sup.X+γ.sub.j2.sup.Y.sup.j+δ2.sup.W+ζ.sub.j2.sup.Z.sup.j for the private moduli and N=β2.sup.X+δ2.sup.W for the public modulus. A particular instantiation of this construction is p.sub.j=2.sup.2(a+1)b+γ.sub.j2.sup.(a+1)b2.sup.ab+ζ.sub.j and N=2.sup.2(a+1)b+2.sup.ab. In this case, the absolute value of terms γ.sub.j and β.sub.j is smaller than 2.sup.b and are in charge of creating a non-linear effect on the MSB and LSB of the coefficients of the local stored key material on a device. Note that since the device identifiers are around b-bits long, γ.sub.j (β.sub.j) affects the MSB (LSB) of the coefficients of the polynomial share evaluated in the ring of integers modulo p.sub.j. Afterwards during the generation of the local key material for a device the coefficients of the polynomial shares in different rings are added over the integers so that the origin of the contributions is concealed.

(46) The key may be generated as follows:

(47) $K_{AB} = < \frac{< {KM}^{A} (x) |_{x = B} >_{N}}{2^{Y_{j}}} >_{2^{b}},$
but if the even more general expression of p.sub.j and N is used that allows introducing a non-linear effect on both MSB and LSB, then the division after the reduction modulo N is by 2 to the power of W, where 2.sup.W is the highest integer power of 2 of which N is an integer multiple. Other constructions of N and p.sub.j may require a division by another power of two. Because the bivariate polynomials in the root key material are symmetric A's shared key and B's shared key are often, though not necessarily always, equal.

(48) Key Confirmation.

(49) It may be desirable for one of A and B to send a key confirmation message to the other party. A so-called key confirmation message (KC) enables the recipient of the key confirmation message to verify that he has computed the same key as the sender of the key confirmation message. In particular in a key sharing scheme for which it is known that the key established by both parties may differ, a key confirmation message may be used both as a confirmation that both have established the same key, and if not, to determine an equal shared key. For example, in general a MAC (message authentication code) based on the established key can serve as the confirmation message, e.g. an HMAC based on SHA2 or SHA3, or a CMAC based on AES, and the like. Also a cryptographically strong hash function may be used, e.g., a hash of the established key may be used as the key confirmation message. The hash may be computed over the key itself. The MAC can be computed over data which is known by B or included in the key confirmation message, e.g. a nonce, etc.

(50) However, general cryptographically strong key confirmation messages require some resources, possibly more resources than a key sharing algorithm according to the above principles. The key sharing schemes given above allow for simpler functions that require much less computation resources than general purpose key confirmation schemes.

(51) Devices A and B compute keys K.sub.A(B) and K.sub.B(A). It can be shown, by following the mathematical relations, that there exists an integer Δ, depending on the design parameters, such that:
K.sub.A(B)ε{<K.sub.B(A)+j>.sub.2.sub.b|−Δ≦j≦Δ},

(52) Again <x>.sub.m denotes the integer between 0 and m−1 such that x−<x>.sub.m is a multiple of m. Define a function as follows: h(x)=<x>.sub.2.sub.r where r is a pre-determined integer such that 2.sup.r≧2Δ+1. Compared to the general embodiment, there is no need that the devices compute possibly complicated hash functions; the disadvantage is that some information on the key that is being used is sent over an observable communication channel. It is usually preferred that a key confirmation message leaks no, or a negligible amount, of information on the key for which it is computed. This disadvantage can be countered by dividing the established key by 2.sup.r, after a key has been found that is the same for both A and B. More generally in a second embodiment, h(x)=<x>.sub.v where v≧2Δ+1 is such that either 2.sup.b is a multiple of v or <2.sup.b>.sub.v≧2Δ+1. In both cases, h(K.sub.A(B)) may be used by A as a key confirmation message.

(53) Apart from sending a key confirmation message, one may decrease the difference between K.sub.A(B) and K.sub.B(A) by dividing both keys by a power of 2. K.sub.A(B) and K.sub.B(A) are b-bit keys, then removing the l least significant bits of the b-bit generated keys so that a b−l bit-key, which corresponds to the b−l most significant bits of the key generated, is used to secure the communication. If b is relatively big (let's say, 100) and l is also big (let's say, 50), the probability of the b−l most significant bits to be equal is very high, i.e. about

(54) $1 - \frac{2 Δ}{2^{b - l}} .$
This approach does not require the exchange of any information, l bits of the original generated key are removed, and the resulting key can be used for the communication. However, this has a drawback because the key size is reduced, potentially in a considerable manner to make sure that all the devices in a network will share a common b−l bit key with very high probability.

(55) Note that removing least significant bits may be combined with a key confirmation message. For example, after removing l bits, a key confirmation message is computed and sent to the other party. This approach has the advantage that, even if the removal of least significant bits was not sufficient to establish a common key, it will make it easier to find such a common key.

(56) In a different approach the problem of potentially different keys being established by parties A and B is the following: The central authority has all the information to compute beforehand if any two devices may derive different keys. For example, the central authority may start with single identifier A and keying material computed for A. Devices are added to a pool of device iteratively. When a new device B′ is to be added to the system, the TTP computes keying material for B′. The TTP, verifies for each combination of B′ and the devices already in the pool if they would arrive at the same common key. For example, the TTP may verify that they find the same key directly. The TTP may also verify that B′ and any other device will arrive at a common key be engaging in a suitable key agreement protocol to repair a possible different key; e.g., by dividing by a power of 2 and/or by sending one or more key confirmation messages. In view of the foregoing probabilistic approach, it is very likely that a random choice for B′ makes {A,B′} valid for all A if the number of devices A is relatively small.

(57) If it turns out that B′ will not arrive at a common key with some of the devices already in the pool, the TTP assigns a new identifier to B′ or computes new keying material, but with different random choices. Although checking this condition represents quite an overhead, this is possible for relatively small networks (let's say ˜0(10.sup.4) or 0(10.sup.5) devices).

(58) A related approach can also be applied in groups of devices. In particular, in some settings not all devices might require to talk to each other, e.g., if devices are static and are deployed in groups (e.g., in a building). In this case, the verification performed by the TTP when a new device B′ is added is limited to checking for the devices belonging to the group to which B′ will be added. For instance, the TTP can verify whether all devices in a given group generate a key if the l LSB of the key are removed. Note that this method also allows for the design of more advanced hierarchical schemes such that all devices belong to the main group at a first level, devices are divided into a number of groups at a second level, devices in a group at a second level are further divided into a number of subgroups. In such a hierarchical organization, the TTP might verify whether all devices in a given group at level w generate a common key after the removal of l.sub.w bits. In such a system, groups at a deeper level might require the removal of a lesser number of bits, while groups at high levels might require the removal of more bits to ensure the generation of common keys.

(59) The TTP may perform these checks whenever a new device is added, but it may also pro-actively create a pool of device identifiers and keying material such that each pair of identifiers from this pool gives a valid common key.

(60) For example, the TTP may limit to pairs of valid devices {A,B}, where a pair is valid if:

(61) $.Math. \frac{K_{B} (A)}{2^{l}} .Math. = .Math. \frac{K_{A} (B)}{2^{l}} .Math.$
where l refers to l bits corresponding to the l Least Significant Bits of K.sub.A(B) and K.sub.B(A). This condition, in general, shows a way of verifying that the keys that actually will be used are equal. Another condition is that a new B is admitted if and only if for all A, the l least significant bits of K.sub.A(B) and K.sub.B(A) correspond to a number in [Δ,2.sup.l−1−Δ].

(62) FIG. 1 is a schematic block diagram illustrating a root key material generator 100. A key material obtainer is configured to provide input data, except an identity number, needed by a local key material generator for generating local key material. A key generator is an example of a key material obtainer. Instead of generating all or part of the input data, some parameters can also be obtained by the root key material generator by receiving them; for example the key obtainer may comprise an electronic receiver for receiving input data, e.g., a public and private modulus. A key material obtainer obtains all the needed parameters except the identity numbers from an external source. In an embodiment a,b, m are predetermined, e.g., received and the public modulus and the private moduli and corresponding symmetric bivariate polynomials are generated. In an embodiment also the public modulus is pre-determined, e.g., received.

(63) Root key generator 100 comprises a polynomial degree element 112, a key length element 114 and a number of polynomials element 116 configured to provide the polynomial degree, the key length and the number of polynomials, i.e., a,b and m respectively. Although these elements may be generated, e.g., depending on circumstances, typically these parameters are chosen by a system designer. For example, the elements may be designed as non-volatile memories, or as receivers for receiving the element values, or as volatile memories connected to a receiver, etc. A suitable choice includes a=2, b=128, m=2. Any one of the numbers may be increased or decreased to obtain a more or less secure system.

(64) Root key generator 100 comprises a public modulus element 110 configured to provide the public modulus N. The public modulus may or may not be chosen by a system designer. For example, the public modulus may be set a convenient number allowing fast reduction (close or equal to a power two). The public modulus is chosen within a range determined by the elements 112 and 114.

(65) Root key generator 100 comprises a private modulus manager 122 configured to provide the private modulus p, or multiple private moduli p.sub.1, . . . , p.sub.m. For example, they are chosen at random within the appropriate bounds.

(66) Root key generator 100 comprises a symmetric bivariate polynomial manager 124 configured to provide the symmetric bivariate polynomial f, or multiple symmetric bivariate polynomial, f.sub.1, . . . , f.sub.m. Each symmetric bivariate polynomial is chosen with coefficients random modulo the corresponding private modulus, i.e. the private modulus having the same index. The coefficients may be chosen within the range 0 to p−1, and may be chosen at random.

(67) The private moduli may be chosen by adding or subtracting a multiple of two to the power of the key length to the public modulus. This will result in private moduli such that the difference with the public modulus ends in a series of consecutive zeros. One may also choose a public modulus and one or more private moduli such that a series of key length consecutive zeros occurs not at the end but another position, say position ‘s’, counting from the least significant bit.

(68) FIG. 2 is a schematic block diagram illustrating a local key material generator 200. Key material generator 100 and local key material generator 200 together form a system for configuring a network device for key sharing.

(69) Local key material generator 200 comprises a polynomial manipulation device 240. Local key material generator 200 comprises a public material element 210 for providing the public parameters a,N to the polynomial manipulation device 240. Local key material generator 200 comprises a private material element 220 for providing the private parameters p.sub.i,f.sub.i and m to the polynomial manipulation device 240. Elements 210 and 220 may be implemented by the corresponding elements of key material generator 100; these elements may also be memories or busses to connect to key material generator 100.

(70) Local key material generator 200 comprises an obfuscating number generator 260 for providing an obfuscating number ‘ε.sub.A,i’ to the polynomial manipulation device 240. The obfuscated number may be a random number, e.g. generated with the random number generator. The obfuscating number generator 260 may generate multiple obfuscating numbers for multiple coefficients of the univariate polynomial. In an embodiment an obfuscating number is determined for each coefficient of the univariate polynomial.

(71) Local key material generator 200 comprises a network device manager 250 configured to receive an identity number for which local key material must be generated, e.g., from a network device, and is configured to send the local key material to the network device corresponding to the identity number. Instead of receiving an identity number, it may also be generated, e.g., as a random, serial or nonce number. In the latter case the identity number is sent along with the local key material to the network device.

(72) The polynomial manipulation device 240 obtains, possibly multiple, univariate polynomials by substituting the identity number from manager 250 into each one of the bivariate polynomials and reducing each modulo the corresponding private modulus. The resulting multiple reduced univariate polynomials are added, coefficient wise, with natural arithmetic addition. Also added are the one or more obfuscating numbers. Preferably, the result is reduced, again coefficient wise, modulo the public modulus; the coefficients of the latter may be represented in the range 0 to N−1.

(73) The obfuscated univariate polynomial is part of the local key material corresponding to the identity number. If needed, the public modulus, degree and the key length are also sent to the network device.

(74) FIG. 3 is a schematic block diagram illustrating a communication network 300 comprising multiple network devices; shown are a first network device 310 and a second network device 320. We will illustrate first network device 310. Second network device 320 may be the same, or work along same principles.

(75) Network device 310 comprises a transceiver 330 combining a sender and a receiver for sending and receiving messages in electronic, e.g., digital, format, in wired or wireless from and to second network device 320. Possibly, transceiver 330 is also used to receive the local key material from the network authority 200. Through the transceiver 330 the identity number of another network device is received; in the figure of the second network device 320.

(76) Network device 310 comprises a local key material obtainer 344. The local key material obtainer 344 may be implemented as local memory, e.g., non-volatile memory such as flash memory for storing the local key material. The local key material obtainer 344 may also be configured to obtain the local key material from generator 200, e.g., via transceiver 330. Local key material obtainer 344 is configured to provide the polynomial manipulation device with the needed parameters.

(77) Network device 310 comprises a polynomial manipulation device 342 configured to substituting the identity number of the second network device into the obfuscated univariate polynomial, and to perform two reductions on the result: First reducing the result of the substituting modulo the public modulus and second reducing modulo a key modulus. Note that even if multiple private moduli were used, only one public modulus would be needed. Note that for some combinations of N and private modulus, a division by a 2 power is required before the result is reduced module a key modulus.

(78) Network device 310 comprises a key derivation device 346 for deriving the shared key from the result of the reduction modulo the key modulus. For example, key derivation device 346 may remove one or more least significant bits. Key derivation device 346 may also apply a key derivation function. It is also possible to use the result of the second reduction without further processing.

(79) Network device 310 comprises an optional key equalizer 348. Note that it may happen that the shared key derived in the first network device is not equal to the key derived in the second network device (based on the identity number of the first network device). If this is considered undesirable, a key equalization protocol may be followed.

(80) Network device 310 comprises a cryptographic element 350 configured to use the shared key for a cryptographic application. For example, cryptographic element 350 may encrypt or authenticate a message of the first network device with the shared key before sending it to the second network device, say a status message. For example, cryptographic element 350 may decrypt or verify the authenticity of a message received from the second network device.

(81) Typically, a system for configuring a network device for key sharing 200, and a first network device configured to determine a shared key 310, each comprise a microprocessor (not shown) which executes appropriate software stored at the respective devices, e.g., which software may have been downloaded and stored in a corresponding memory, e.g. RAM (not shown).

(82) An interesting embodiment is obtained for a=1, especially in combination with higher values of m, say higher than 1, 2 or higher, 4 or higher. The required polynomial manipulation reduces to a single multiplication and reduction, giving an especially simple implementation. However, even for this simple case recovering the original bivariate polynomials is not straightforward, and becomes increasingly complicated with higher values of m. Although no viable attack is known even for a=1, the linear structure may be a starting point for future analysis, so one may want to restrict to a >1, for this reason.

(83) FIG. 4 is a schematic flow chart illustrating a method of generating local key material 400. The method comprises obtaining 410 a public and private modulus, and a symmetric bivariate polynomial, obtaining 420 an identity number of a network device, substituting 430 the identity number into the bivariate polynomial modulo the private modulus, adding 440 an obfuscating number to a coefficient, and storing 450 the obfuscated univariate polynomial at the network device

(84) FIG. 5 is a schematic flow chart illustrating a method of generating a shared key 500. The method comprises obtaining 510 external identity number of another network device, sending 520 local identity number to other network device, substituting 530 external identity number into the obfuscated univariate polynomial modulo the public modulus, reducing 540 modulo key modulus, deriving 550 a shared key, sending 560 a key confirmation message to the other network device, determining 570 if the key is confirmed 570, and a cryptographic application 580. If the key is not confirmed in step 570 then the method continues in step 550 with deriving a new key. For example, step 550 may remove one additional least significant bit each time the key is not confirmed.

(85) Steps 550, 560, and 570 together form a key equalization protocol. For example, in step 560 a nonce and encryption of the nonce under the shared key derived in step 550 may be sent to the second device. In step 560 a message is received from the second device. The received message may simply say that the received key confirmation message showed that the keys are not equal. The received message may also contain a key confirmation message. In the latter case, the first network device verifies the key confirmation message and establishes if the keys are equal. If not a new key is derived, for example, by deleting a least significant bit.

(86) Many different ways of executing the method are possible, as will be apparent to a person skilled in the art. For example, the order of the steps can be varied or some steps may be executed in parallel. Moreover, in between steps other method steps may be inserted. The inserted steps may represent refinements of the method such as described herein, or may be unrelated to the method. For example, steps 410 and 420, or 510 and 520, may be executed, at least partially, in parallel. Moreover, a given step may not have finished completely before a next step is started.

(87) A method according to the invention may be executed using software, which comprises instructions for causing a processor system to perform method 400 or 500. Software may only include those steps taken by a particular sub-entity of the system. The software may be stored in a suitable storage medium, such as a hard disk, a floppy, a memory etc. The software may be sent as a signal along a wire, or wireless, or using a data network, e.g., the Internet. The software may be made available for download and/or for remote usage on a server.

(88) FIG. 6 shows in schematic form a possible sequence of message between two network devices, device A and B, while they are generating a shared key. Time runs downward. In step 610, network device A sends his identity number to device B. In step 620 device B, send his identity number and a key confirmation message for the shared key (K1) it derived based on identity number A and his local key material. In step 630, device A found that they did not generated the same key. Device A has deleted one least significant bit (say integer divide by 2) to obtain key K2. In step 630 device A sends a new key confirmation message. In this fashion A and B exchange key confirmation messages 640 until they arrive at the same key in step 650. In step 650 device A sends a key confirmation message to device B. Device B was able to verify that they had arrived at the same key. In step 660 it sends a confirmation thereof, this may be an authenticated message or a key confirmation message, etc. In step 670 device A sends a message M1 which is encrypted (say using AES) and/or authenticated (say using HMAC) using the now equal shared key.

(89) The algorithm below gives a possible implementation of this approach, i.e., a protocol for mutual key agreement & session key derivation run by Device A and Device B

(90) TABLE-US-00001 Set I=L Set continue=TRUE Set Length = b−I Generate a b-bit key K While(continue AND (Length>MINIMUM_LENGTH)){ K = K>>I Perform Mutual authentication handshake with B based on K If handshake successful, then{ continue=FALSE }else{ Length = b−I }

(91) The protocol removes a number of bits of the bit string generated with a key sharing algorithm, such as described herein, and performs an authentication handshake, e.g., challenge-response. The authentication handshake may comprise a key confirmation message. If it is not successful, a few additional bits are removed, and so on until the handshake is successfully performed or the key got too short. The protocol can be modified in a number of ways, e.g., by removing a variable number of bits depending on the iteration or requiring always a fixed number of steps so that an eavesdropper observing the execution of the protocol does not gain any information about the length of the shared common key between A and B. This approach has the advantage that it makes sure that the shared keys are as long as possible; however, it has the potential disadvantage that it requires a number of exchanges for the agreement on the common key. On the other hand, for most applications this will not be a big problem because for most pairs of devices the keys will be equal or differ only in few bits and only a device pairs will arrive at keys with a relatively high number of different least significant bits. This follows from the properties of the keys generated.

(92) There are other ways to arrive at a same key for both devices. Again we assume that devices A and B compute keys K.sub.A(B) and K.sub.B(A). The protocols below apply for any key sharing scheme for which there exists an integer A, depending on the design parameters, such that:
K.sub.A(B)ε{<K.sub.B(A)+j>.sub.2.sub.b|−Δ≦j≦Δ}.

(93) For example, the key sharing schemes describe herein have this property. The generated keys are represented as b-bits integers. So keys can be considered as elements from the set {0, 1, 2, . . . , 2.sup.b−1}. For example, if Δ=2, and K.sub.B(A)=1, then K.sub.A(B) is in {1, 2, 3, 0, 2.sup.b−1} (note that <1−2>.sub.2.sub.b=2.sup.b−1). For properly chosen system design parameters, Δ is relatively small. The invention assures that the same key is generated always because a failure to generate a common key can be recovered from.

(94) According to this method, Device A sends to device B a function value h(K.sub.A(B)). Here h is a suitable hash function, e.g. a cryptographic hash function. Device B computes h(i) for all i in {<K.sub.B(A)+j>.sub.2.sub.b|−Δ≦j≦Δ} and uses, for future communications, the integer i for which h(i) matches the received value of h(K.sub.A(B)). If Δ is too large, devices A and B may first divide their keys by a power of 2 to reduce the size of Δ.

(95) It will be appreciated that the invention also extends to computer programs, particularly computer programs on or in a carrier, adapted for putting the invention into practice. The program may be in the form of source code, object code, a code intermediate source and object code such as partially compiled form, or in any other form suitable for use in the implementation of the method according to the invention. An embodiment relating to a computer program product comprises computer executable instructions corresponding to each of the processing steps of at least one of the methods set forth. These instructions may be subdivided into subroutines and/or be stored in one or more files that may be linked statically or dynamically. Another embodiment relating to a computer program product comprises computer executable instructions corresponding to each of the means of at least one of the systems and/or products set forth.

(96) It should be noted that the above-mentioned embodiments illustrate rather than limit the invention, and that those skilled in the art will be able to design many alternative embodiments. In the claims, any reference signs placed between parentheses shall not be construed as limiting the claim. Use of the verb “comprise” and its conjugations does not exclude the presence of elements or steps other than those stated in a claim. The article “a” or “an” preceding an element does not exclude the presence of a plurality of such elements. The invention may be implemented by means of hardware comprising several distinct elements, and by means of a suitably programmed computer. In the device claim enumerating several means, several of these means may be embodied by one and the same item of hardware. The mere fact that certain measures are recited in mutually different dependent claims does not indicate that a combination of these measures cannot be used to advantage.

Key sharing device and system for configuration thereof

Assignee

Inventors

Cpc classification

Classification Explorer

H04L9/0838

ELECTRICITY

Classification Explorer

H04W12/041

ELECTRICITY

Classification Explorer

Y04S40/20

GENERAL TAGGING OF NEW TECHNOLOGICAL DEVELOPMENTS; GENERAL TAGGING OF CROSS-SECTIONAL TECHNOLOGIES SPANNING OVER SEVERAL SECTIONS OF THE IPC; TECHNICAL SUBJECTS COVERED BY FORMER USPC CROSS-REFERENCE ART COLLECTIONS [XRACs] AND DIGESTS

Classification Explorer

H04L9/0866

ELECTRICITY

Classification Explorer

H04W12/0431

ELECTRICITY

Classification Explorer

H04L9/3093

ELECTRICITY

Classification Explorer

H04L9/0869

ELECTRICITY

Classification Explorer

H04W12/0433

ELECTRICITY

Classification Explorer

H04L63/061

ELECTRICITY

Classification Explorer

H04W12/122

ELECTRICITY

International classification

Classification Explorer

H04L9/00

ELECTRICITY

Classification Explorer

H04W12/04

ELECTRICITY

Classification Explorer

H04L29/06

ELECTRICITY

Classification Explorer

H04L9/30

ELECTRICITY

Classification Explorer

H04W12/12

ELECTRICITY

Classification Explorer

H04L9/08

ELECTRICITY

Abstract

Claims

Description