Network device configured to derive a shared key

Abstract

A network device (110) is provided which is configured to determine a shared cryptographic key of key length (b) bits shared with a second network device (120) from a polynomial and an identity number of the second network device. A reduction algorithm is used to evaluate the polynomial in the identity number of the second network device and reduce module a public modulus and modulo a key modulus. The reduction algorithm comprises an iteration over the terms of the polynomial. In at least the iteration which iteration is associated with a particular term of the polynomial are comprised a first and second multiplication. The first multiplication is between the identity number and a least significant part of the coefficient of the particular term obtained from the representation of the polynomial, the least significant part of the coefficient being formed by the key length least significant bits of the coefficient of the particular term. The second multiplication is between a second multiplication between the identity number and a further part of the coefficient of the particular term obtained from the representation of the polynomial, the further part of the coefficient being formed by bits of the coefficient of the particular term different from the key length least significant bits, the further part and the least significant part together forming strictly fewer bits than in the coefficient of the particular term of the polynomial.

Claims

1. A first network device configured to determine a shared cryptographic key of a key length shared with a second network device from a polynomial and an identity number of the second network device, the polynomial having multiple terms, each term of the multiple terms being associated with a different degree and a coefficient, the first network device comprising: an electronic storage for storing local key material for the first network device, the local key material comprising a representation of the polynomial for use in evaluation of the polynomial by the first network device, wherein the first network device has limited available computational resources, a receiver for obtaining the identity number of the second network device, the second network device being different from the first network device, a processor configured to apply the polynomial to the identity number according to a reduction algorithm, and for deriving the shared key from the reduction algorithm, wherein the reduction algorithm comprises performing multiple iterations, wherein each iteration of the multiple iterations is performed over the multiple terms of the polynomial of which at least one iteration, associated with a particular term of the polynomial, comprises: a first multiplication between the identity number and a least significant part of a coefficient of the particular term obtained from the representation of the polynomial, the least significant part of the coefficient being formed by the key length of least significant bits of the coefficient of the particular term, and a second multiplication between the identity number and a further part of the coefficient of the particular term obtained from the representation of the polynomial, the further part of the coefficient being formed by bits of the coefficient of the particular term different from the key length least significant bits, the further part and the least significant part together forming strictly fewer bits than in the coefficient of the particular term of the polynomial, wherein the further part is a most significant part of the coefficient of the particular term, wherein a size of the further part increases with a degree of the particular term, such that the size of the further part increases where a influence of a reduction result increases, and the size of the further part decreases where the influence of the reduction result decreases, wherein as a result of the increasing and decreasing of the further part there is a reduction in computational resources utilized by the first network device.

2. The first network device as in claim 1, wherein a public modulus equals 2 to an exponent (2.sup.(a+2)b) plus an offset, wherein the exponent is a multiple of the key length, and wherein the absolute value of the offset is less than 2 to the power of the key length, each coefficient of the polynomial being less than the public modulus.

3. The first network device as in claim 1, wherein a key modulus equals 2 to the power of the key length, the identity number being less than the key modulus.

4. The first network device as in claim 1, wherein each iteration of the iterations over the terms of the polynomial is associated with a specific term of the terms of the polynomial, each iteration comprising: a first multiplication between the identity number and a least significant part of the coefficient of the specific term obtained from the representation of the polynomial, the least significant part of the coefficient being formed by the key length of the least significant bits of the coefficient of the specific term, and a second multiplication between the identity number and a further part of the coefficient of the specific term obtained from the representation of the polynomial, the further part of the coefficient being formed by bits of the coefficient of the specific term different from the key length least significant bits.

5. The first network device as in claim 4, wherein the further part of the coefficient of the specific term is a most significant part of the coefficient of the specific term, the most significant part of the coefficient being formed by a number of most significant bits of the coefficient of the specific term.

6. The first network device as in claim 4, wherein the number of bits in the further part is a multiple of the key length.

7. The first network device as in claim 4, wherein the number of bits in the further part decreases with decreasing degree of the specific term.

8. The first network device as in claim 7, wherein the number of bits in the further part is a multiple of the key length and wherein the multiple equals the degree of the specific term plus an error control number.

9. The first network device as in claim 8, wherein the error control number equals 1 or 2.

10. The first network device as in claim 1, wherein the coefficient of the polynomial is represented in pre-processed form, in the pre-processed form the least significant part and the further part of the coefficient of the particular term are represented in a single bit string adjacent to each other, the reduction algorithm comprising a single multiplication between the identity number and the single bit string for executing the first and second multiplication together.

11. A method for determining a shared cryptographic key of a key length shared between a first network device and a second network device from a polynomial and an identity number of the second network device, the polynomial having multiple terms, each term of the multiple terms being associated with a different degree and a coefficient, the method comprising: storing local key material in electronic form for the first network device, the local key material comprising a representation of a polynomial for use in evaluation of the polynomial by the first network device, wherein the first network device has limited available computational resources, obtaining an identity number of the second network device, the second network device being different from the first network device, applying the polynomial to the identity number according to a reduction algorithm, and deriving the shared key from the reduction algorithm, wherein the reduction algorithm comprises an iteration over the terms of the polynomial of which at least one iteration, associated with a particular term of the polynomial, comprises: a first multiplication between the identity number and a least significant part of a coefficient of the particular term obtained from the representation of the polynomial, the least significant part of the coefficient being formed by the key length of least significant bits of the coefficient of the particular term, and a second multiplication between the identity number and a further part of the coefficient of the particular term obtained from the representation of the polynomial, the further part of the coefficient being formed by bits of the coefficient of the particular term different from the key length least significant bits, the further part and the least significant part together forming strictly fewer bits than in the coefficient of the particular term of the polynomial, wherein the further part is a most significant part of the coefficient of the particular term, wherein a size of the further part increases with a degree of the particular term, such that the size of the further part increases where an influence of a reduction result increases, and the size of the further part decreases where the influence of the reduction result decreases, wherein as a result of the increasing and decreasing of the further part there is a reduction in computational resources utilized by the first network device.

12. A non-transitory computer-readable medium having one or more executable instructions stored thereon, which when executed by a processor, cause the processor to perform a method for determining a shared cryptographic key of a key length shared between a first network device and a second network device from a polynomial and an identity number of the second network device, the polynomial having multiple terms, each term of the multiple terms being associated with a different degree and a coefficient, the method comprising: storing local key material in electronic form for the first network device, the local key material comprising a representation of a polynomial for use in evaluation of the polynomial by the first network device, wherein the first network device has limited available computational resources, obtaining an identity number of the second network device, the second network device being different from the first network device, applying the polynomial to the identity number according to a reduction algorithm, and deriving the shared key from the reduction algorithm, wherein the reduction algorithm comprises an iteration over the terms of the polynomial of which at least one iteration, associated with a particular term of the polynomial, comprises: a first multiplication between the identity number and a least significant part of a coefficient of the particular term obtained from the representation of the polynomial, the least significant part of the coefficient being formed by the key length of least significant bits of the coefficient of the particular term, and a second multiplication between the identity number and a further part of the coefficient of the particular term obtained from the representation of the polynomial, the further part of the coefficient being formed by bits of the coefficient of the particular term different from the key length least significant bits, the further part and the least significant part together forming strictly fewer bits than in the coefficient of the particular term of the polynomial, wherein the further part is a most significant part of the coefficient of the particular term, wherein a size of the further part increases with a degree of the particular term, such that the size of the further part increases where an influence of a reduction result increases, and the size of the further part decreases where the influence of the reduction result decreases, wherein as a result of the increasing and decreasing of the further part there is a reduction in computational resources utilized by the first 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) FIGS. 1a and 1b are schematic block diagrams illustrating a communication network,

(3) FIG. 2 is a schematic flow chart illustrating generating a shared key,

(4) FIG. 3 is a schematic sequence diagram illustrating generating a shared key,

(5) FIGS. 4a-4f represent various reduction algorithms,

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

(7) 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.

DETAILED EMBODIMENTS

(8) 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.

(9) FIG. 1a is a schematic block diagram illustrating a communication network 100 during a set-up phase. FIG. 1a shows a network authority 160. FIG. 1a also shows multiple network devices; shown are first network device 110 and second network device 120.

(10) Network devices have a registration phase and a use phase. In the registration phase a participating network device is provided with an identity number and local key material. The local key material is provided by network authority 160.

(11) Network authority 160, may e.g. be implemented in the form of an electronic server, and may be directly connected with the device, e.g., during manufacture. Network authority 160 may provide the local key material later, say over the internet.

(12) During the use phase, two (or more) network devices may establish a shared key by requesting the public identity numbers of the other network devices and combining it with their local key material.

(13) The configuration application provides a full account how the network authority 160 may derive local key material. In an embodiment, the network authority performs a method comprising 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 comprising obtaining in electronic form an identity number (A) for the network device, 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.

(14) In other words, the network authority may start from a bivariate polynomial and convert it to a univariate polynomial by substituting the identity number of a network device. By choosing the reductions, and coefficients etc in certain ways the security of this process may be improved. In the end; for a particular network device a particular univariate polynomial is obtained, which is stored therein.

(15) In a further embodiment, 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.

(16) To generate a shared key from the univariate polynomial, the network device may do the following: obtaining an external identity number of another network device, sending local identity number to other network device, substituting the external identity number into the obfuscated univariate polynomial modulo the public modulus, and reducing modulo key modulus. The public modulus and key modulus are selected together in or before the registration phase and is the same for all participating network devices. The key modulus depends on the size of the desired key and is typically 2 to the power of the key length. Starting from the reduction result modulo the key modulus, a shared key may be derived. Deriving a key may involve a key derivation step, to spread and/or concentrate entropy among the bits of the key, say an application of a cryptographic hash.

(17) Unfortunately, due to the way the bivariate polynomial was chosen, it may happen that the shared key is not entirely the same. This may either be accepted; e.g. for ad-hoc networks it may not matter that some network devices are not capable of direct communication, similarly, for low-cost or low-security applications a certain failure rate may be acceptable. The chances of having equal keys may be increased by using a key equalizing procedure. Several reduction algorithms will be described which often or always give the same result. Indeed, given the fact that determining the shared key may fail in a small percentage of cases, it is particularly advantageous that algorithms may now be used which do not always give the exact same result but do so with high probability.

(18) It is noted that the network authority may use a multivariate polynomial, having more variables than 2 (bivariate), say 3 or 4 or even more. In this case multiple network nodes need to contribute its identity number for deriving a shared key. It is noted that the network authority may use a non-symmetric polynomial, in this case network device are divided among multiple groups, a shared key may only be derived if at least one member of each group is contributes his identity number.

(19) For example, the network authority may generate a set of keying material for a device A of the form: KM.sup.A (X)=.sub.iKM.sub.i.sup.Ax.sup.i comprising coefficients KM.sub.i.sup.A with i=0, . . . , . A can generate a common key with another device B with identifier by doing the following: K.sub.AB<<KM.sup.A(X)|.sub.x=>.sub.N>.sub.2.sub.b=.sub.iKM.sub.i.sup.A.sup.i>.sub.N>.sub.2.sub.b where N=2.sup.(a+2)b1. This evaluation of the polynomial needs to be implemented efficiently on a small embedded processor. See in particular page 17-25 of the configuring application for examples on how to select parameters, root key material and local key material.

(20) An efficient polynomial evaluation method is the so-called Homer's method, however it turns out that this method may still be optimized much further. The polynomial evaluation is performed with coefficients over large numbers of size greater than 128 bits. Therefore the evaluation of the common key K.sub.AB needs to be done without requiring too much memory for intermediate storage of big numbers. Additionally the polynomial is evaluated over modulo N and should be implemented without performing any costly divisions. The present invention provides optimizations for implementing the polynomial evaluation on an embedded micro-processor with minimal memory (flash and RAM) and still perform it fast.

(21) A particular fine choice for N is close to 2.sup.(a+2)b. The size of N in terms of the degree of the polynomial and the key length, helps in protecting the system against attacks. Because N is close to a power of 2, modular operation may expressed as an addition, and possible a multiplication with the small offset (if it is not 1 or 1). Some optimization are independent of N, say moving the highest and lowest degree iterations out of the loop, words for each N.

(22) FIG. 1b is a schematic block diagram illustrating a communication network 100 comprising multiple network devices; shown are first network device 110 and second network device 120. We will illustrate first network device 110. Second network device 120 may be the same, or work along the same principles.

(23) Network device 110 comprises a transceiver 130 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 120. Possibly, transceiver 130 is also used to receive the local key material, say from network authority 160 or other trusted third party. Through the transceiver 130 the identity number of another network device is received; in the figure of the second network device 120.

(24) The transceiver is a combination of a sender and a receiver, note that only the receiver is needed to derive the shared key locally. If it is needed that the shared key is derived at the first and second device more or less at the same time, then a sender may be conveniently used to send the identity number.

(25) Network device 110 comprises a local key material storage 144. Local key material storage 144 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 storage 144 may also be configured to obtain the local key material from e.g. the network authority 160, e.g., via transceiver 130. Local key material storage 144 is configured to provide the polynomial manipulation device with the needed parameters. The local key material stored by local key material storage 144 comprises a representation of the polynomial for later evaluation by the first network device. For example, a representation of the polynomial may be a list of the coefficient of the polynomial, for example, sorted by degree. However, the representation of the polynomial may be optimized in various ways; it turns out that some parts of the coefficients have very little impact on the end result. The determination of the shared key is optimized by leaving out those calculations which are unlikely to have a large impact on the final result. Not only the computation may be optimized in this way, also the storage of the representation may be optimized by not storing those parts of a coefficient which are not used.

(26) Network device 110 comprises a polynomial manipulation device 142 configured to apply the polynomial to the external identity number according to a reduction algorithm to obtain a reduction result. The reduction algorithm is configured such that it gives a reduction result that corresponds to, i.e., approximates, the result that would have been obtained when: 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. The reduction result corresponds in that it approximates the result of the other algorithm.

(27) Often the reduction result will be equal to result of substituting the identity number of the second network device into the polynomial corresponding to the local key material, and performing two reductions on the result: modulo the public modulus and then modulo a key modulus. Unfortunately, sometimes the two may differ. If they do differ, the difference is often limited to one or a few least significant bits. It is preferred that two values differ in less than 1% of cases, less preferably in less than 10%.

(28) It is noted that using obfuscated polynomials or polynomials derived from two private moduli, have the property that the reduction result obtained on different devices may also differ in rare cases (cf. the configuration application). For this reason it is not considered a large additional burden that in some rare additional cases further differences are introduced in the reduction result, since the system will already be equipped to deal with this fact, e.g., key equalization or other solutions.

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

(30) Network device 110 comprises an optional key equalizer 148. 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.

(31) Network device 110 comprises a cryptographic element 150 configured to use the shared key for a cryptographic application. For example, cryptographic element 150 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 150 may decrypt or verify the authenticity of a message received from the second network device.

(32) Typically, the device 110 and 120 each comprise a microprocessor (not shown) which executes appropriate software stored at the device 110 and 120, e.g. the software may have been downloaded and stored in a corresponding memory, e.g. RAM or non-volatile memory such as Flash memory (neither shown).

(33) FIG. 2 is a schematic flow chart illustrating a method of generating a shared key 200. The method comprises obtaining 210 an external identity number of another network device, sending 220 the local identity number to the other network device, executing 230 a reduction algorithm on the polynomial and the received identity number, deriving 250 a shared key, sending 260 a key confirmation message to the other network device, determining 270 if the key is confirmed, and a cryptographic application 280. If the key is not confirmed in step 270 then the method continues in step 250 with deriving a new key. For example, step 250 may remove one additional least significant bit each time the key is not confirmed.

(34) For the reduction algorithm there are various choices, as explained using FIGS. 4a-4f The execution of a reduction algorithm may be done by a polynomial manipulation device. This may be done on a microprocessor with software according to the algorithm explained below.

(35) Steps 250, 260, and 270 together form a key equalization protocol. For example, in step 260 a nonce and encryption of the nonce under the shared key derived in step 250 may be sent to the second device. In step 260 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.

(36) 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 210 and 220 may be executed, at least partially, in parallel. Moreover, a given step may not have finished completely before a next step is started.

(37) FIG. 3 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 310, network device A sends its identity number to device B. In step 320 device B, send its identity number and a key confirmation message for the shared key (K1) it derived based on identity number A and its local key material. In step 330, 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 330 device A sends a new key confirmation message. In this fashion A and B exchange key confirmation messages 340 until they arrive at the same key in step 350. In step 350 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 360 it sends a confirmation thereof, this may be an authenticated message or a key confirmation message, etc. In step 370 device A sends a message M1 which is encrypted (say using AES) and/or authenticated (say using HMAC) using the now equal shared key.

(38) 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

(39) TABLE-US-00001 Set I=L Set continue=TRUE Set Length = bI 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 = bI }

(40) 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.

(41) There are other ways to arrive at a same key for both devices, e.g., as described in the configuring application.

(42) Throughout FIGS. 4a-4f the following conventions are used: The network device executing the reducing result is the first network device, the network device contributing its identity number is the second network device; b denotes the key length, a denotes the degree of the polynomial (sometimes written in the text as a), KM.sub.,j denotes the coefficient corresponding to the term of degree j of the polynomial corresponding to the first network device, is the identify number of the first network device, the identity number of the second network device, N is the public modulus. The notation ( . . . ).sub.c denotes a modulo reduction of the number in brackets modulo c. The notation >>c denotes a shift right over c bits, i.e., division by 2.sup.c, rounded downwards to the next integer.

(43) The words input, output, for, end for, return are standard in the field of computer algorithms.

(44) The advantageous public modulus N=2.sup.(a+2)b1 is used in the examples. This particular modulus allows a particular fast and elegant reduction. The algorithms may be adopted for different moduli, notably when the public modulus equals 2 to an exponent (2.sup.(a+2)b) minus a (positive) offset, wherein the exponent is a multiple of the key length, and wherein the absolute value of the offset is less than 2 to the power of the key length. When the offset is not 1 but larger, say 3, the most significant part is added offset times to the least significant part instead once. If the offset is added instead of subtracted, the most significant part is added to least significant part.

(45) As an example, one could take a=2 and b=128. For higher security, larger values may be used, say =4 or 6.

(46) FIG. 4a illustrates in the form of so-called pseudo code how a reduction result may be obtained.

(47) Line 3 and 5 show an iteration over the terms of the polynomial given by coefficients KM.sub.,j. In each iteration an intermediate value key is multiplied with a new coefficient. This implementation of the evaluation of the key <<.sub.iKM.sub.i.sup.A.sup.i>.sub.N>.sub.2.sub.b uses the so-called Homer's method.

(48) The algorithm of FIG. 4b is similar to that of 4a but takes advantage of the particular form of the modulus used. The step temp key+KM.sub.j.sub.N is optimized by using the fact the N is of the special form N=2.sup.(a+2)b1. Therefore if we denote R=key then R can be divided into two parts R=R.sub.1.Math.2.sup.(a+2)bR.sub.0 where R.sub.0 is the 2.sup.(a+2)b least significant bits (lsb) of R and R.sub.1 are the remaining MSB of R. Given this, we can calculate R.sub.N=R.sub.1.Math.2.sup.(a+2)bR.sub.0.sub.N=R.sub.1+R.sub.0 since 2.sup.(a+2)b.sub.N=1. To be exact: it is R.sub.0+R.sub.1.sub.N which equals R.sub.0+R.sub.1 if it is not too big, i.e., less than N. To be more exact, one could reduce modulo N once more, and doing so gives an approximation. However, R.sub.1 is very small compared to N so the chance that introducing errors by not doing the second reduction is small. Instead, one could also do a modulo N reduction (with the same trick) after step 7 and only then apply step 8.

(49) A similar optimization would be obtained if N=2.sup.(a+2)boffset. In which offset is small compared to N, say larger than 0 but smaller than the key modulus (2.sup.b).

(50) FIG. 4c avoids unnecessary computations. The performance of the reduction algorithm of FIGS. 4a and 4b can be improved by not performing intermediate computations which have no or rarely an effect in the final result. In FIG. 4c, advantage is taken of the fact that the first and last iterations require fewer computations. In this design, also mod N reductions are eliminated using the following expression R.sub.j=key+KM.sub.j thus R.sub.j.sub.N=R.sub.j,12.sup.(a+2)b+R.sub.j,0.sub.NR.sub.j,1+R.sub.j,0 whose implementation requires fewer computations than the previous one.

(51) This optimization, uses the fact that 2.sup.b1 and KM.sub.j2.sup.(a+2)b1. The operation keykey+KM.sub.j.sub.N can be performed efficiently since (key+KM)2.sup.(a+3)b2.sup.b<2.sup.(a+3)b1.

(52) Therefore key can be represented as key=R.sub.1.Math.2.sup.(a+2)b+R.sub.0 where R.sub.12.sup.b1. Then reduction by N is simple addition as before but always with b bits.

(53) The algorithms of FIGS. 4a, 4b and 4c do not have the feature that the identity number is used in first and second multiplication by a further and least significant part of a coefficient, which together form a smaller part than the full coefficient, i.e., some part of the polynomial is not used. Reduction algorithms 4a-4c are included for comparison with the algorithms 4d-4f

(54) FIG. 4d reduces data storage requirements. Not all the bits of the polynomial coefficients are required when generating the key. This algorithm needs to store only those bits which will be used. This approach also leads to a reduction in the number of computations required. The notation MSB, denotes the c most significant words. The notation LSB.sub.c denotes the c least significant words. Words are key length (b) bits wide.

(55) FIG. 4d shows in lines 3 and 10 an iteration over the terms of the polynomial KM.sub.. In this particular embodiment, each iteration is associated with a particular term of the polynomial; the iterations are associated in order with degrees 1 to 1. The iterations corresponding to degree and 0 are performed outside the loop.

(56) Line 5 shows a first multiplication between the identity number () and a least significant part of the coefficient of the particular term obtained from the representation of the polynomial. The least significant part of the coefficient being formed by the key length least significant bits of the coefficient of the particular term,

(57) Line 4 shows a second multiplication between the identity number and a further part of the coefficient of the particular term obtained from the representation of the polynomial, the further part of the coefficient being formed by bits of the coefficient of the particular term different from the key length least significant bits.

(58) Note that for most iterations the further part and the least significant part together form strictly fewer bits than in the coefficient of the particular term of the polynomial; in fact they have fewer words than the coefficient of the particular term of the polynomial. The coefficients that are not used need not be stored either.

(59) Note that in each iteration the least significant part is exactly one word of key length bits. The number of bits in the further part is however decreasing in the loop, i.e., decreasing with the degree.

(60) The number of words in the further part is the degree (j) plus an error control number (red). The error control number is here chosen to be 1. The error control number determines the likelihood that the result of the reduction algorithm is exactly the same as the result of the algorithm of FIG. 4a. To decrease the probability of getting unequal results between the first and second network device the error control number may be increased, say to 2. Larger values are possible, however the probability reduces exponentially with the error control number.

(61) This algorithm makes further use of the fact that not all parts of the multiplied KM.sub.j contribute to the final result of the key. Some parts have very minimal effect (due to carries) but these errors can be corrected during the generation of a shared key as explained in FIGS. 2 and 3.

(62) FIG. 4e as the algorithm of FIG. 4d also tries to reduce the data storage requirements. Although this design has to store some additional bits which the algorithm of FIG. 4d does not require, it is advantageous because fewer intermediate computations are required so implementation will be faster.

(63) In Line 4 a further part is obtained, and in line 5 a second multiplication is shown. In line 6 a first multiplication is performed with a least significant part which has been introduced in key in the previous iteration. In line 5 a second multiplication is performed.

(64) The optimization of FIG. 4d needed to track the amount of bits being used from KM.sub.j in each iteration and requires additional pointer management. The algorithm of FIG. 4e reduces the need for managing the memory. This optimization is more efficient in memory and in the number of clock cycles.

(65) FIG. 4f illustrates a further reduction algorithm which requires a pre-computation step on the coefficients. It has both low data storage requirements, and is faster than the algorithm of FIG. 4e. A keying material share is generated as follows
K(x)=.sub.i=0.sup.KM.sub.i2.sup.b.sub.Nx.sup.i=.sub.i=0.sup.KM.sub.ix.sup.i
thus each KM.sub.i has a special form which makes this approach faster because the instructions to select the MSB and LSB can be skipped. Then, a network device wishing to generate a key with a second network device may compute the key as:

(66) $K_{,{}^{}}={.Math.\frac{{\mathrm{KM}}_i^{}\left({}^{}\right)}{2^b}.Math.}_{2^b}$

(67) This transformation has the effect that the least significant part and the further part of a coefficient of a particular term KM.sub.i are represented in a single bit string adjacent to each other in KM.sub.i Usually, the least significant part and the most significant part are separated from each other by a number of intermediate words, as the degree is lower this intermediate part is larger. Because of the transformation, the first and second multiplication may be performed in a single step.

(68) The coefficients used in FIG. 4f have been transformed in this fashion. As a result, the multiplication in line 3 performs the first and second multiplication together. Note that the transformation preferably is done by the TTP and the network device stores these transformed coefficients in the local key material storage.

(69) The table below gives an indication of the comparative advantages of the latter reduction algorithms. The algorithms were implemented in flash and used RAM for dynamic memory. Execution time is measured in CPU cycles. The configuration used to run the tests was: =6, b=32 and a 32-bit CPU (the ARM Cortex-M3). Algorithms of FIGS. 4a and 4b are comparatively worse than the examples given below.

(70) TABLE-US-00002 Reduction Algorithm Flash Size Ram Size Execution time FIG. 4c 828 36 2521 FIG. 4d 892 36 2043 FIG. 4e 828 36 1742 FIG. 4f 716 36 1283

(71) FIG. 5 again illustrates in the form of a flow chart a method for determine a shared cryptographic key of key length (b) bits shared with a second network device from a polynomial and an identity number of the second network device, the polynomial having multiple terms, each term being associated with a different degree and a coefficient.

(72) In step 510, local key material is stored in electronic form for the first network device, the local key material comprising a representation of a polynomial for later evaluation by the first network device. In step 520, an identity number of the second network device is obtained, the second network device being different from the first network device. In step 530, the polynomial is applied to the identity number according to a reduction algorithm to obtain a reduction result. In step 540, the shared key is deriving from the reduction result, say by a key derivation algorithm such as KDF. Additionally, a key equalizing algorithm may be performed. Step 530 includes a reduction algorithm; this is illustrated by a dashed arrow to steps 522, 524 and 526.

(73) In step 522, an iteration over the terms of the polynomial is started, at least one iteration is associated with a particular term of the polynomial. In step 524, a first multiplication is performed between the identity number and a least significant part of the coefficient of the particular term obtained from the representation of the polynomial, the least significant part of the coefficient being formed by the key length least significant bits of the coefficient of the particular term.

(74) In step 526, a second multiplication is performed between the identity number and a further part of the coefficient of the particular term obtained from the representation of the polynomial, the further part of the coefficient being formed by bits of the coefficient of the particular term different from the key length least significant bits, the further part and the least significant part together forming strictly fewer bits than in the coefficient of the particular term of the polynomial.

(75) 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 524 and 526 may be executed, together by creating a number in which the further and least significant parts are adjacent. Moreover, a given step may not have finished completely before a next step is started.

(76) A method according to the invention may be executed using software, which comprises instructions for causing a processor system to perform method 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.

(77) 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.

(78) 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.

(79) 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.

LIST OF REFERENCE NUMERALS IN FIGS. 1a, 1b AND 2

(80) 100 a communication network 110 a first network device 120 a second network device 130 a transceiver 142 a polynomial manipulation device 144 a local key material storage 146 a key derivation device 148 a key equalizer 150 a cryptographic element 160 a network authority 210 obtaining external identity number of another network device 220 sending local identity number to other network device 230 executing reduction algorithm 250 deriving a shared key 260 sending a key confirmation message to the other network device 270 Key confirmed? 275 no 280 Cryptographic application