Elliptic curve random number generation

Abstract

An elliptic curve random number generator avoids escrow keys by choosing a point Q on the elliptic curve as verifiably random. An arbitrary string is chosen and a hash of that string computed. The hash is then converted to a field element of the desired field, the field element regarded as the x-coordinate of a point Q on the elliptic curve and the x-coordinate is tested for validity on the desired elliptic curve. If valid, the x-coordinate is decompressed to the point Q, wherein the choice of which is the two points is also derived from the hash value. Intentional use of escrow keys can provide for back up functionality. The relationship between P and Q is used as an escrow key and stored by for a security domain. The administrator logs the output of the generator to reconstruct the random number with the escrow key.

Claims

1. A method of operating an elliptic curve random number generator (ECRNG) including an arithmetic unit to perform elliptic curve operations to compute a random number for use in a cryptographic operation, said method performed by a hardware processor of a device including the ECRNG, and said method comprising the steps of: obtaining, at the device, a pair of inputs, wherein each input is representative of at least one coordinate of respective ones of a pair of elliptic curve points, and wherein one point of the pair of elliptic curve points is not a known multiple of the other point of the pair of elliptic curve points; providing, at the device, said pair of inputs as inputs to said arithmetic unit; performing, by said arithmetic unit, selected elliptic curve operations on said inputs to obtain an output, wherein said selected elliptic curve operations is performed independent of escrow keys separate from said pair of inputs to improve security of the cryptographic operation; utilizing said output as a random number in the cryptographic operation to generate, at the device, encrypted data; and transmitting, by the device, the encrypted data to a different device in a network.

2. The method of claim 1, wherein said at least one of said inputs is obtained from an output of a hash function.

3. The method of claim 2, wherein the other of said inputs is utilized as an input to said hash function.

4. The method of claim 1, wherein said random number generator has a secret value and said secret value is used to compute scalar multiples of said points represented by said inputs.

5. The method of claim 4, wherein one of said scalar multiples is used to derive said random number and the other of said scalar multiples is used to change said secret value for subsequent use.

6. The method of claim 2, wherein said output of said hash function is validated as a coordinate of a point on an elliptic curve prior to utilization as said input.

7. The method of claim 6, wherein another coordinate of said point is obtained from said one coordinate for inclusion as said one input.

8. The method of claim 7, wherein said other input is a representation of an elliptic curve point.

9. The method of claim 5, wherein said random number is derived from said one scalar multiple by selecting one coordinate of a point represented by said one scalar multiple and truncating said one coordinate to a bit string for use as said random number.

10. The method of claim 9, wherein said one coordinate is truncated in the order of one half the length of a representation of an elliptic curve point representation.

11. The method of claim 5, wherein said random number is derived from said one scalar multiple by selecting one coordinate of said point represented by said scalar multiple and hashing said one coordinate to provide a bit string for use as said random number.

12. The method of claim 1, wherein said at least one of said inputs is chosen to be of a canonical form.

13. The method of claim 1, wherein said output is passed through a one way function to obtain a bit string for use as a random number.

14. The method of claim 13, wherein said one way function is a hash function.

15. The method of claim 1, wherein obtaining one of the inputs includes obtaining a result of a hash function that is performed on said one input.

16. An elliptic curve random number generator (ECRNG) configured to perform elliptic curve operations to compute a random number for use in a cryptographic operation, the ECRNG comprising: one or more hardware processors configured to: generate, at the ECRNG, a pair of inputs, wherein each of said inputs is representative of at least one coordinate of respective ones of a pair of elliptic curve points, and wherein one point of the pair of elliptic curve points is not a known multiple of the other point of the pair of elliptic curve points; perform, at the ECRNG, selected elliptic curve operations on said inputs to obtain an output, said output representing a random number for use in the cryptographic operation to generate encrypted data, and said selected elliptic curve operations is performed independent of escrow keys separate from said pair of inputs to improve security of the cryptographic operation; and transmit the encrypted data to a different device in a network.

17. The elliptic curve random number generator of claim 16, wherein generate said inputs includes a one way function and at least one of said inputs is derived from an output of a one way function.

18. The elliptic curve random number generator of claim 17, wherein said one way function is a hash function.

19. The elliptic curve random number generator of claim 16, wherein one of said inputs is obtained from an output of a hash function, and the other of said inputs is provided as an input to said hash function.

Description

BRIEF DESCRIPTION OF THE DRAWINGS

(1) An embodiment of the invention will now be described by way of example only with reference to the appended drawings wherein:

(2) FIG. 1 is a schematic representation of a cryptographic random number generation scheme.

(3) FIG. 2 is a flow chart illustrating a selection process for choosing elliptic curve points.

(4) FIG. 3 is a block diagram, similar to FIG. 1 showing a further embodiment

(5) FIG. 4 is flow chart illustrating the process implemented by the apparatus of FIG. 3.

(6) FIG. 5 is a block diagram showing a further embodiment.

(7) FIG. 6 is a flow chart illustrating yet another embodiment of the process of FIG. 2.

(8) FIG. 7 is schematic representation of an administrated cryptographic random number generation scheme.

(9) FIG. 8 is a flow chart illustrating an escrow key selection process.

(10) FIG. 9 is a flow chart illustrating a method for securely utilizing an escrow key.

DETAILED DESCRIPTION OF THE INVENTION

(11) Referring therefore to FIG. 1, a cryptographic random number generator (ECRNG) 10 includes an arithmetic unit 12 for performing elliptic curve computations. The ECRNG also includes a secure register 14 to retain a state value s and has a pair of inputs 16, 18 to receive a pair of initialisation points P, Q. The points P, Q are elliptic curve points that are assumed to be known. An output 20 is provided for communication of the random integer to a cryptographic module 22. The initial contents of the register 14 are provided by a seed input S.

(12) This input 16 representing the point P is in a first embodiment, selected from a known value published as suitable for such use.

(13) The input 18 is obtained from the output of a one way function in the form of a hash function 24 typically a cryptographically secure hash function such as SHA1 or SHA2 that receives as inputs the point P. The function 24 operates upon an arbitrary bit string A to produce a hashed output 26. The output 26 is applied to arithmetic unit 12 for further processing to provide the input Q.

(14) In operation, the ECRNG receives a bit string as a seed, which is stored in the register 14. The seed is maintained secret and is selected to meet pre-established cryptographic criteria, such as randomness and Hamming weight, the criteria being chosen to suit the particular application.

(15) In order to ensure that d is not likely to be known (e.g. such that P=dQ, and ed=1 mod n); one or both of the inputs 16, 18 is chosen so as to be verifiably random. In the embodiment of FIG. 1, Q is chosen in a way that is verifiably random by deriving it from the output of a hash-function 24 (preferably one-way) whose input includes the point P. As shown in FIG. 2 an arbitrary string A is selected at step 202, a hash H of A is computed at step 204 with P and optionally S as inputs to a hash-based function F.sub.HO, and the hash H is then converted by the arithmetic unit 12 to a field element X of a desired field Fat step 206. P may be pre-computed or fixed, or may also be chosen to be a verifiably random chosen value. The field element X is regarded as the x-coordinate of Q (thus a compressed representation of Q). The x-coordinate is then tested for validity on the desired elliptic curve E at step 208, and whether or not X is valid, is determined at step 210. If valid, the x-coordinate provided by element X is decompressed to provide point Q at step 212. The choice of which of two possible values of the y co-ordinate is generally derived from the hash value.

(16) The points P and Q are applied at respective inputs 16, 18 and the arithmetic unit 12 computes the point sQ where s is the current value stored in the register 14. The arithmetic unit 12 converts the x-coordinate of the point (in this example point sQ) to an integer and truncates the value to obtain r=t(z(sQ)). The truncated value r is provided to the output 20.

(17) The arithmetic unit 12 similarly computes a value to update the register 14 by computing sP, where s is the value of the register 14, and converting the x-coordinate of the point sP to an integer u. The integer u is stored in the register to replace s for the next iteration. {ditto above}

(18) As noted above, the point P may also be verifiably random, but may also be an established or fixed value, Therefore, the embodiment of FIG. 1 may be applied or retrofitted to systems where certain base points (e.g. P) are already implemented in hardware. Typically, the base point P will be some already existing base point, such as those recommended in Federal Information Processing Standard (FIPS) 186-2. In such cases, P is not chosen to be verifiably random.

(19) In general, inclusion of the point P in the input to the hash function ensures that P was determined before Q is determined, by virtue of the one-way property of the hash function and since Q is derived from an already determined P. Because P was determined before Q, it is clearly understood that P could not have been chosen as a multiple of Q (e.g. where P=eQ), and therefore finding d is generally as hard as solving a random case of the discrete logarithm problem.

(20) Thus, having a seed value S provided and a hash-based function FO provided, a verifier can determine that Q=F(S,P), where P may or may not be verifiably random. Similarly, one could compute P=F(S,Q) with the same effect, though it is presumed that this is not necessary given that the value of P in the early drafts of X9.82 were identical to the base points specified in FIPS 186-2.

(21) The generation of Q from a bit string as outlined above may be performed externally of the ECRNG 10, or, preferably, internally using the arithmetic unit 12. Where both P and Q are required to be verifiably random, a second hash function 24 shown in ghosted outline in FIG. 1 is incorporated to generate the coordinate of point P from the bit string A. By providing a hash function for at least one of the inputs, a verifiably random input is obtained.

(22) It will also be noted that the output generated is derived from the x coordinate of the point sP. Accordingly, the inputs 16, 18 may be the x coordinates of P and Q and the corresponding values of sP and sQ obtained by using Montgomery multiplication techniques thereby obviating the need for recovery of the y coordinates.

(23) An alternative method for choosing Q is to choose Q in some canonical form, such that its bit representation contains some string that would be difficult to produce by generating Q=dP for some known d and P for example a representation of a name. It will be appreciated that intermediate forms between this method and the preferred method may also exist, where Q is partly canonical and partly derived verifiably at random. Such selection of Q, whether verifiably random, canonical, or some intermediate, can be called verifiable.

(24) Another alternative method for preventing a key escrow attack on the output of an ECRNG, shown in FIGS. 3 and 4 is to add a truncation function 28 to ECRNG 10 to truncate the ECRNG output to approximately half the length of a compressed elliptic curve point. Preferably, this operation is done in addition to the preferred method of FIGS. 1 and 2, however, it will be appreciated that it may be performed as a primary measure for preventing a key escrow attack. The benefit of truncation is that the list of R values associated with a single ECRNG output r is typically infeasible to search. For example, for a 160-bit elliptic curve group, the number of potential points R in the list is about 2.sup.80, and searching the list would be about as hard as solving the discrete logarithm problem. The cost of this method is that the ECRNG is made half as efficient, because the output length is effectively halved.

(25) Yet another alternative method shown in FIGS. 5 and 6 comprises filtering the output of the ECRNG through another one-way function F.sub.H2, identified as 34, such as a hash function to generate a new output. Again, preferably, this operation is performed in addition to the preferred method shown in FIG. 2, however may be performed as a primary measure to prevent key escrow attacks. The extra hash is relatively cheap compared to the elliptic curve operations performed in the arithmetic unit 12, and does not significantly diminish the security of the ECRNG.

(26) As discussed above, to effectively prevent the existence of escrow keys, a verifiably random Q should be accompanied with either a verifiably random P or a preestablished P. A pre-established P may be a point P that has been widely publicized and accepted to have been selected before the notion of the ECRNG 12, which consequently means that P could not have been chosen as P=eQ because Q was not created at the time when P was established.

(27) Whilst the above techniques ensure the security of the system using the ECRNG by closing the trap door, it is also possible to take advantage of the possible interdependence of P and Q, namely where P=eQ, through careful use of the existence of e.

(28) In such a scenario, the value e may be regarded as an escrow key. If P and Q are established in a security domain controlled by an administrator, and the entity who generates Q for the domain does so with knowledge of e (or indirectly via knowledge of d). The administrator will have an escrow key for every ECRNG that follows that standard.

(29) Escrow keys are known to have advantages in some contexts. They can provide a backup functionality. If a cryptographic key is lost, then data encrypted under that key is also lost. However, encryption keys are generally the output of random number generators. Therefore, if the ECRNG is used to generate the encryption key K, then it may be possible that the escrow key e can be used to recover the encryption key K. Escrow keys can provide other functionality, such as for use in a wiretap. In this case, trusted law enforcement agents may need to decrypt encrypted traffic of criminals, and to do this they may want to be able to use an escrow key to recover an encryption key.

(30) FIG. 7 shows a domain 40 having a number of ECRNG's 10 each associated with a respective member of the domain 40. The domain 40 communicates with other domains 40a, 40b, 40c through a network 42, such as the interne. Each ECRNG of a domain has a pair of identical inputs P,Q. The domain 40 includes an administrator 44 who maintains in a secure manner an escrow key e.

(31) The administrator 44 chooses the values of P and Q such that he knows an escrow key e such that Q=eP. Other members of the domain 40 use the values of P and Q, thereby giving the administrator 44 an escrow key e that works for all the members of the organization.

(32) This is most useful in its backup functionality for protecting against the loss of encryption keys. Escrow keys e could also be made member-specific so that each member has its own escrow e from points selected by the administrator 44.

(33) As generally denoted as numeral 400 in FIG. 8, the administrator initially selects a point P which will generally be chosen as the standard generator P for the desired elliptic curve 402. The administrator then selects a value d and the point Q will be determined as Q=dP 404, for some random integer d of appropriate size. The escrow key e is computed as e=d.sup.?1 mod n 406, where n is the order of the generator P and stored by the administrator.

(34) The secure use of such an escrow key 34e is generally denoted by numeral 500 and illustrated in FIG. 9. The administrator 44 is first instituted 502 and an escrow keys e would be chosen and stored 504 by the administrator 44

(35) In order for the escrow key to function with full effectiveness, the escrow administrator 44 needs direct access to an ECRNG output value r that was generated before the ECRNG output value k (i.e. 16) which is to be recovered. It is not sufficient to have indirect access to r via a one-way function or an encryption algorithm. A formalized way to achieve this is to have each member with an ECRNG 12 communicate with the administrator 44 as indicated at 46 in FIG. 7. and step 506 in FIG. 9. This may be most useful for encrypted file storage systems or encrypted email accounts. A more seamless method may be applied for cryptographic applications. For example, in the SSL and TLS protocols, which are used for securing web (HTTP) traffic, a client and server perform a handshake in which their first actions are to exchange random values sent in the clear.

(36) Many other protocols exchange such random values, often called nonces. If the escrow administrator observes these nonces, and keeps a log of them 508, then later it may be able to determine the necessary r value. This allows the administrator to determine the subsequent state of the ECRNG 12 of the client or server 510 (whoever is a member of the domain), and thereby recover the subsequent ECRNG 12 values. In particular, for the client who generally generates a random pre-master secret from which is derived the encryption key for the SSL or TLS session, the escrow key may allow recovery of the session key. Recovery of the session key allows recovery of the whole SSL or TLS session.

(37) If the session was logged, then it may be recovered. This does not compromise long-term private keys, just session keys obtained from the output of the ECRNG, which should alleviate any concern regarding general suspicions related to escrows.

(38) Whilst escrow keys are also known to have disadvantages in other contexts, their control within specific security domains may alleviate some of those concerns. For example, with digital signatures for non-repudiation, it is crucial that nobody but the signer has the signing key, otherwise the signer may legitimately argue the repudiation of signatures. The existence of escrow keys means the some other entity has access to the signing key, which enables signers to argue that the escrow key was used to obtain their signing key and subsequently generate their signatures. However, where the domain is limited to a particular organisation or part of an organisation it may be sufficient that the organisation cannot repudiate the signature. Lost signing keys do not imply lost data, unlike encryption keys, so there is little need to backup signing keys.

(39) Although the invention has been described with reference to certain specific embodiments, various modifications thereof will be apparent to those skilled in the art without departing from the spirit and scope of the invention as outlined in the claims appended hereto.