Source: https://patents.justia.com/patent/10243734
Timestamp: 2019-06-19 16:48:01
Document Index: 210079695

Matched Legal Cases: ['Application No. 60', 'art 3', 'art 3', 'art 3', 'Application No. 06704329', 'Application No. 2', 'Application No. 2', 'Application No. 06704329', 'Application No. 06704329', 'Application No. 06704329', 'Application No. 2007', 'Application No. 2007', 'Application No. 2007', 'Application No. 2007', 'Application No. 2011', 'Application No. 2011']

US Patent for Elliptic curve random number generation Patent (Patent # 10,243,734 issued March 26, 2019) - Justia Patents Search
Justia Patents Particular Algorithmic Function EncodingUS Patent for Elliptic curve random number generation Patent (Patent # 10,243,734)
Dec 18, 2014 - Certicom Corp.
This application is a continuation of and claims priority from U.S. patent application Ser. No. 13/770,533, filed on Feb. 29, 2013, which is a continuation of and claims priority from U.S. patent application Ser. No. 11/336,814, filed on Jan. 23, 2006 and issued as U.S. Pat. No. 8,396,213 on Mar. 12, 2013, which is hereby incorporated by reference and which claims priority from U.S. Provisional Patent Application No. 60/644,982 filed on Jan. 21, 2005.
The elliptic curve E includes the points (x, y) and one further point, namely the point O at infinity. The elliptic curve E also has a group structure, which means that the two points P and Q on the curve can be added to form a third point P+Q. The point O is the identity of the group, meaning P+O=O+P=P, for all points P. Addition is associative, so that P+(Q+R)=(P+Q)+R, and commutative, so that P+Q=Q+R, for all points P, Q and R. Each point P has a negative point −P, such that P+(−P)=O. When the curve equation is the Weierstrass equation of the form y2=x3+ax+b, the negative of P=(x, y) is determined easily as −P=(x, −y). The formula for adding points P and Q in terms of their coordinates is only moderately complicated involving just a handful of field operations.
The ECRNG has a state, which may be considered to be an integer s. The state s is updated every time the ECRNG produces an output. The updated state is computed as u=z(sP), where zO is a function that converts an elliptic curve point to an integer. Generally, z consists of taking the x-coordinate of the point, and then converting the resulting field element to an integer. Thus u will typically be an integer derived from the x-coordinate of the point s.
The output of the ECRNG is computed as follows: r=t(z(sQ)), where is a truncation function. Generally the truncation function removes the leftmost bits of its input. In the ECRNG, the number of bits truncated depends on the choice of elliptic curve, and typically may be in the range of 6 to 19 bits.
Although P and Q are known, it is believed that the output r is random and cannot be predicted. Therefore successive values will have no relationship that can be exploited to obtain private keys and break the cryptographic functions. The applicant has recognised that anybody who knows an integer d such that Q=dP, can deduce an integer e such that ed=1 mod n, where n is the order of G, and thereby have an integer e such that P=eQ, Suppose U=sP and R=sQ, which are the precursors to the updated state and the ECRNG output. With the integer e, one can compute U from R as U=eR, Therefore, the output r=t(z(R)), and possible values of R can be determined from r. The truncation function means that the truncated bits of R would have to be guessed. The z function means that only the x-coordinate is available, so that decompression would have to be applied to obtain the full point R. In the case of the ECRNG, there would be somewhere between about 26=64 and 219 (i.e. about half a million) possible points R which correspond to r, with the exact number depending on the curve and the specific value of r.
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 FHO, 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.
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.
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.
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.
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 280, 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.
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.
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.
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
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.
6044388 March 28, 2000 DeBellis
6088798 July 11, 2000 Shimbo
6122375 September 19, 2000 Takaragi
6263081 July 17, 2001 Miyaji et al.
6285761 September 4, 2001 Patel
6307935 October 23, 2001 Crandall
6424712 July 23, 2002 Vanstone et al.
6466668 October 15, 2002 Miyazaki
6480605 November 12, 2002 Uchiyama
6687721 February 3, 2004 Wells
6714648 March 30, 2004 Miyazaki et al.
6738478 May 18, 2004 Vanstone et al.
6990201 January 24, 2006 Coron
7000110 February 14, 2006 Terao
7013047 March 14, 2006 Schmidt et al.
7062043 June 13, 2006 Solinas
7062044 June 13, 2006 Solinas
7092979 August 15, 2006 Shim
7124443 October 17, 2006 Ishibashi
7162033 January 9, 2007 Coron et al.
7171000 January 30, 2007 Toh et al.
7197527 March 27, 2007 Naslund et al.
7218735 May 15, 2007 Coron et al.
7221758 May 22, 2007 Cramer et al.
7308096 December 11, 2007 Okeya
7308588 December 11, 2007 Nishizawa
7327845 February 5, 2008 Orr
7353395 April 1, 2008 Gentry
7388957 June 17, 2008 Ono
7418099 August 26, 2008 Vanstone et al.
7480795 January 20, 2009 Vanstone
7542568 June 2, 2009 Ohmori et al.
7599491 October 6, 2009 Lambert
7613917 November 3, 2009 Chojnacki
7639799 December 29, 2009 Lauter et al.
7650507 January 19, 2010 Crandall et al.
7680270 March 16, 2010 Srungaram
7680272 March 16, 2010 Yoon
7853013 December 14, 2010 Vasyltsov
7907726 March 15, 2011 Lauter et al.
7936874 May 3, 2011 Futa
7961874 June 14, 2011 Ibrahim
8074266 December 6, 2011 Yoneda
8411855 April 2, 2013 Robinson et al.
8428252 April 23, 2013 Makepeace et al.
8559625 October 15, 2013 Douguet et al.
8619977 December 31, 2013 Douguet et al.
20020044649 April 18, 2002 Gallant et al.
20030156714 August 21, 2003 Okeya
20040005053 January 8, 2004 Koshiba
20040102242 May 27, 2004 Poelmann et al.
20040247115 December 9, 2004 Ono
20050036609 February 17, 2005 Eisentraeger et al.
20060129800 June 15, 2006 Lauter et al.
20060165231 July 27, 2006 Srungaram
20060285682 December 21, 2006 Sarangarajan et al.
20070121933 May 31, 2007 Futa et al.
20080056499 March 6, 2008 Vanstone
2381397 February 2001 CA
2001-222220 August 2001 JP
2003-507761 February 2003 JP
2005-500740 January 2005 JP
2001/13218 February 2001 WO
2001/35573 May 2001 WO
ANS X9.62/2005; “Public Key Cryptography for the Financial Services Industry—The Elliptic Curve Digital Signature Algorithm (ECDSA)”; Nov. 16, 2005; 163 pages.
ANSI X9.82; “Part 3 for X9F1” Oct. 2003; 175 pages.
ANS X9.82; “Part 3—Draft”; Jun. 2004; 189 pages.
Barker, Elaine and John Kelsey; “Recommendation for Random Number Generation Using Deterministic Random Bit Generators”; NIST Special Publication 800-90; National Institute of Standards and Technology; Dec. 2005; 130 pages.
Barker, Elaine and John Kelsey; “Recommendation for Random No. Generation Using Deterministic Random Bit Generators (Revised)”; NIST Special Publication 800-90; National Institute of Standards and Technology; Mar. 2007; 133 pages.
Blum, Manuel and Silvio Micali; “How to Generate Cryptographically Strong Sequences of Pseudo-Random Bits”; SIAM Journal on Computing; vol. 13, No. 4; Nov. 1984; pp. 850-864.
Brown, Daniel R.L.; “Conjecture Security of the ANSI-NIST Elliptic Curve RNG”; Cryptology ePrint Archive; Report 2006/117; Mar. 29, 2006; 14 pages. Retrieved from the internet <http://eprint.iacr.org>.
El Mahassni, Edwin and Igor Shparlinksi; “On the Uniformity of Distribution of Congruential Generators over Elliptic Curves”; Sequences and Their Applications: Proceedings of SETA '01; 2002' pp. 257-264.
Gjoesteen, Kristian; “Comments on Dual-EC-DRBG/NIST SP 800-90, Draft Dec. 2005”; Mar. 16, 2006; 8 pages.
Guerel, Nicolas; “Extracting Bits from Coordinates of a Point of an Elliptic Curve”; Cryptology ePrint Archive; Report 2005/324; 2005; 9 pages. Retrieved from the internet <http://eprint.iacr.org>.
Johnson, Don B.; “X9.82 Part 3—Number Theoretic DRBGs”; NIST RNG Workshop; Jul. 20, 2004; retrieved from the internet <http://csrc.nist.gov/groups/ST/tooklit/documents/rng/NumberTheoreticDRBG.pdf>.
Kaliski, Burton S., Jr.; “A Pseudo-Random Bit Generator Based on Elliptic Logarithms”; Advances in Cryptology; CRYPTO 1986; vol. 263; pp. 84-103.
Lee, K. et al.; “Elliptic Curve Random Number Generation”; Electrical and Electronic Technology 2001; Proceedings of IEEE Region 10 International Conference; Aug. 19-22, 2001; pp. 239-241.
Lichota, Dr. RW; “Verifying the Correctness of Cryptographic Protocols Using ‘Convince’” IEEE; Dec. 13, 1996; pp. 119-122.
Luby, Michael; “Pseudorandomness and Cryptographic Applications”; Princeton University Press; 1996; pp. 70-74.
Satoh, A.; “Scalable Dual-Field Elliptical Curve Cryptographic Processor”; IEEE, vol. 52; Apr. 2003; pp. 452-456.
Office Action issued in U.S. Appl. No. 11/336,814 dated Jun. 23, 2009; 10 pages.
Office Action issued in U.S. Appl. No. 11/336,814 dated Aug. 23, 2010; 22 pages.
Office Action issued in U.S. Appl. No. 11/336,814 dated Apr. 15, 2011; 31 pages.
Office Action issued in U.S. Appl. No. 11/336,814 dated Mar. 22, 2012; 9 pages.
Notice of Allowance issued in U.S. Appl. No. 11/336,814 dated Jul. 3, 2012; 8 pages.
Notice of Allowance issued in U.S. Appl. No. 11/336,814 dated Nov. 8, 2012.
Office Action issued in U.S. Appl. No. 13/770,533 dated Apr. 16, 2014; 11 pages.
Extended European Search Report issued in European Application No. 06704329.9 dated Nov. 12, 2009; 6 pages.
Official Action issued in Canadian Application No. 2,594,670 dated Aug. 9, 2012; 4 pages.
Notice of Allowance issued in Canadian Application No. 2,594,670 dated Mar. 21, 2014; 1 page.
Communication pursuant to Article 94(3) EPC issued in European Application No. 06704329.9 dated Mar. 10, 2010; 4 pages.
Communication pursuant to Article 94(3) EPC issued in European Application No. 06704329.9 dated Jul. 22, 2010; 4 pages.
Communication pursuant to Article 94(3) EPC issued in European Application No. 06704329.9 dated Jun. 15, 2011; 4 pages.
Office Action issued in Japanese Application No. 2007-551522 dated Aug. 26, 2011; 18 pages.
Office Action issued in Japanese Application No. 2007-551522 dated Jan. 18, 2012; 8 pages.
Notice of Final Rejection issued in Japanese Application No. 2007-551522 dated May 30, 2012; 7 pages.
Notice of Allowance issued in Japanese Application No. 2007-551522 dated Oct. 31, 2012; 3 pages.
Office Action issued in Japanese Application No. 2011-259363 dated Jan. 31, 2013; 12 pages.
Office Action issued in Japanese Application No. 2011-259363 dated Jun. 7, 2013; 13 pages.
International Search Report and Written Opinion of the International Searching Authority issued in International Application No. PCT/CA2006/000065 dated May 1, 2006; 11 pages.
International Preliminary Report on Patentability issued in International Application No. PCT/CA2006/000065 dated Aug. 2, 2007.
Patent Publication Number: 20150156019
Inventors: Daniel Richard L. Brown (Mississauga), Scott Alexander Vanstone (Campbellville)
Application Number: 14/575,844
International Classification: H04L 9/08 (20060101); G06F 7/58 (20060101); H04L 9/30 (20060101); H04L 9/06 (20060101); G06F 7/72 (20060101);