Source: http://www.google.com/patents/US8218773?dq=7,339,580
Timestamp: 2017-09-25 07:33:08
Document Index: 630706367

Matched Legal Cases: ['Application No. 60', 'Application No. 60', 'Application No. 60', 'art 3', 'art 3', 'art 3', 'Application No. 06704329', 'Application No. 06704329', 'Application No. 06704329', 'application No. 05742539', 'Application No. 05729970', 'Application No. 06704329', 'art 3', 'art 3', 'Application No. 2007']

Patent US8218773 - Systems and methods to securely generate shared keys - Google Patents
A method for secure bidirectional communication between two systems is described. A first key pair and a second key pair are generated, the latter including a second public key that is generated based upon a shared secret. First and second public keys are sent to a second system, and third and fourth...http://www.google.com/patents/US8218773?utm_source=gb-gplus-sharePatent US8218773 - Systems and methods to securely generate shared keys
Publication number US8218773 B2
Application number US 13/006,044
Also published as US7646872, US7894605, US8693695, US20050251680, US20100104102, US20110126013, US20120257746
Publication number 006044, 13006044, US 8218773 B2, US 8218773B2, US-B2-8218773, US8218773 B2, US8218773B2
Patent Citations (56), Non-Patent Citations (62), Referenced by (2), Classifications (22), Legal Events (4)
US 8218773 B2
This application is a continuation of U.S. patent application Ser. No. 12/651,630 that was filed on Jan. 4, 2010, and entitled “Systems and Methods to Securely Generate Shared Keys,” which is a continuation of U.S. patent application Ser. No. 11/118,236, now U.S. Pat. No. 7,646,872, that was filed on Apr. 29, 2005, and entitled “Systems and Methods to Securely Generate Shared Keys,” which claims the benefit of U.S. Provisional Application No. 60/566,790 filed on Apr. 30, 2004 and which is also a continuation-in-part of U.S. patent application Ser. No. 11/093,954 that was filed on Mar. 30, 2005, and entitled “Deploying and Provisioning Wireless Handheld Devices,” which claims the benefit of both of U.S. Provisional Application No. 60/559,646 filed Apr. 5, 2004 and U.S. Provisional Application No. 60/559,092 filed Apr. 2, 2004. All of these are hereby incorporated by reference in their entirety.
k=hash(k1∥k2)
where ∥ is a concatentation function.
“Received h A ”=h A=hash(k∥bytes of public key“A”)
where “received hA” came from the service offering, and ‘k’ is the local master key.
k=hash(k1∥k2).
h B=hash(k∥bytes of public key “B”).
Once the service provider has completed those calculations with (D) shown in FIG. 9, it returns a similar new public encryption key ‘Y’ (discussed further below) with a key confirmation value for verification by the user (E). This is shown as input (E) in FIG. 8. At this point the user is able to use the service provider's new key with the service provider's older long-term public key to create a master key following advanced SPEKE calculations, for example. By using both the existing ‘B’ and the new together to generate the key, the encryption method can provide implementation of perfect forward secrecy. Perfect forward secrecy can be achieved because neither the existing ‘B’ nor the new ‘Y’ are based on the original shared secret, and the existing ‘B’ is combined with the new ‘Y’ to create a new key not directly based on the previous key. Additionally, the existing ‘B’ key carries some of the authentication generated with the original shared secret. Only an authenticated service user, that originally possessed the shared secret, would have been able to have the private key ‘b’ saved to disk. This is seen more clearly in the exemplary re-key mathematical calculation to create a new master key ‘k’:
E(Fq)—an elliptic curve over Fq, such as the NIST (National Institute of Standards and Technology) approved 512 bit random elliptic curve over Fq, which curve has a cofactor of one (see Federal Information Processing Standards Publication, “Digital Signature Standard (DSS)”, Jan. 27, 2000, Appendix 6, located at http://csrc.nist.gov/publications/fips/fips186-2/fips186-2-change1.pdf);
where x is the integer representation of the x-coordinate of the elliptic curve point R, and f is the bit length of r (i.e., f=└log2 r┘+1).
In the last of the above-noted steps, SHA-512 refers to the 512 bit “secure hash algorithm” that is known to those of ordinary skill in the art, and “∥” is an agreed upon concatentation function (see Federal Information Processing Standards Publication 180-2, “Secure Hash Standard”, Aug. 1, 2002, located at http://csrc.nist.gov/publications/fips/fips180-2/fips180-2withchangenotice.pdf). Of course, other secure hash algorithms known in the art, such as those that utilize a different number of bits could also be used. The reference to (k, kconf) means the first half of the result (first 256 bits) from the SHA-512 calculation is the calculated master secret key k, and the second half of the result (second 256 bits) is a quantity kconf that will be used in calculating the host system's key confirmation value hB (or test string) as discussed below. The steps at which k1 and k2 are tested to check whether either of them is equal to 0, 1 or −1 is similar to the check made at step 314 of FIG. 6 discussed previously to test whether there is a possible attack being staged. If the condition is met, such that either or both of k1 and k2 are set to random numbers, the calculated master key k will not match the user's master key, and two-way secure communication based upon a shared master (secret) key will not occur. Of course, the process could simply be aborted at this stage if the condition is met.
In this calculation, HMAC-256 refers to the 256 bit “hashed message authentication code” algorithm known to those of ordinary skill in the art (see “HMAC: Keyed-Hashing for Message Authentication”, H. Krawczyk et al., Network Working Group Request for Comments: 2104, February 1997, 11 pages, accessible from the Internet at http://www.faqs.org/rfcs/rfc2104.html). Of course, other versions of a hashed message authentication code, such as those that use a different number of bits, could also be used. The quantity kconf (referred to previously) is a bit string provided as input to the HMAC-256 algorithm. Aux DataD is the first auxiliary data provided by the user 100 as described above. Aux DataB refers to second auxiliary data generated by the host system. The second auxiliary data can be essentially any data string such as a random data string, or it can be other useful data, such as device configuration information that can be used by the user in configuring one or more devices at the user's end. Its size is agreed upon in advance by the communicating parties and is the same size as the first auxiliary data. The symbol ‘∥’ is an agreed upon concatentation function. A, X, B, and Y are the first through fourth public keys, and ASCII1 is any predetermined ASCII code (e.g., for the letter “B”) programmed into the argument of the HMAC algorithm.
s B=(y+ Yb)mod r;
Z=s B(X+ XA);
In the above, X and Y are calculated from X and 1; respectively, using a known approach in the MQV protocol. Namely, to calculate X, the abscissa (x-coordinate) value of X is obtained (noting that X is an elliptic curve point having an x-coordinate value and a y-coordinate value), the leading half (left half) of the abscissa's bit values are dropped, and a leading “1” is inserted in place of the dropped bits. The calculation of Y from Y is done in the same manner. The first half of the bits of the result of the SHA calculation is the master key k, and the second half of the bits is the value of kconf, such as described previously. In this example, separate k1 and k2 values are not generated during re-keying, and a step analogous to step 466 is not carried out.
s A=(x+ Xa)mod r;
Z=s A(Y+ YB);
US6088798 Sep 26, 1997 Jul 11, 2000 Kabushiki Kaisha Toshiba Digital signature method using an elliptic curve, a digital signature system, and a program storage medium having the digital signature method stored therein
US6882958 Jun 28, 2001 Apr 19, 2005 National Instruments Corporation System and method for curve fitting using randomized techniques
US7680270 Oct 20, 2003 Mar 16, 2010 The Additional Director (Ipr), Defence Research & Development Organisation System for elliptic curve encryption using multiple points on an elliptic curve derived from scalar multiplication
US20040102242 May 15, 2003 May 27, 2004 Poelmann Boudewijn Johannes Maria Systems and methods for establishing a verifiable random number
US20050036609 Jul 25, 2003 Feb 17, 2005 Eisentraeger Anne Kirsten Squared weil and tate pairing techniques for use with elliptic curves
US20060129800 Dec 14, 2004 Jun 15, 2006 Microsoft Corporation Cryptographically processing data based on a cassels-tate pairing
US20060236384 Apr 16, 2003 Oct 19, 2006 Fredrik Lindholm Authentication method
US20080056499 Sep 14, 2007 Mar 6, 2008 Vanstone Scott A Split-key key- agreement protocol
US20090161876 Dec 21, 2007 Jun 25, 2009 Research In Motion Limited Methods and systems for secure channel initialization transaction security based on a low entropy shared secret
US20090164774 Dec 21, 2007 Jun 25, 2009 Research In Motion Limited Methods and systems for secure channel initialization
CA2381397A1 Aug 15, 2000 Feb 22, 2001 Alliedsignal Inc. Fuel cell having improved condensation and reaction product management capabilities
JP2003507761A Title not available
WO2001013218A1 Aug 16, 2000 Feb 22, 2001 Siemens Aktiengesellschaft Method for generating pseudo random numbers and method for electronic signatures
WO2005107141A1 May 2, 2005 Nov 10, 2005 Research In Motion Limited Systems and methods to securely generate shared keys
1 Advisory Action received in U.S. Appl. No. 11/336,814 on Nov. 4, 2010, 3 pages.
2 ANS X9.62-2005; "Public Key Cryptography for the Financial Services Industry-The Elliptic Curve Digital Signature Algorithm (ECDSA)"; Nov. 16, 2005; 163 pages.
3 ANS X9.62-2005; "Public Key Cryptography for the Financial Services Industry—The Elliptic Curve Digital Signature Algorithm (ECDSA)"; Nov. 16, 2005; 163 pages.
4 ANS X9.82; "Part 3-Draft"; Jun. 2004; 189 pages.
5 ANS X9.82; "Part 3—Draft"; Jun. 2004; 189 pages.
6 ANSI X9.82; "Part 3 for X9F1" Oct. 2003; 175 pages.
7 Ateniese, Giuseppe, et al., "New Multiparty Authentication Services and Key Agreement Protocols", IEEE Journal on selected areas in communications, Apr. 2000, vol. 18, No. 4.
8 Barker, Elaine and John Kelsey; "Recommendation for Random Number Generation Using Deterministic Random Bit Generators (Revised)"; NIST Special Publication 800-90; National Institute of Standards and Technology; Mar. 2007; 133 pages.
9 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.
10 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.
11 Boyd, Colin, et al., "Design and Analysis of Key Exchange Protocols via Secure Channel Identification", article, Nov. 28, 1994, 11, University of Manchester, Manchester.
12 Boyko, Victor, et al., "Provably Secure Password-Authenticated Key Exchange Using Deffie-Hellman", Advances of Cryptology-Eurocrypt 2000, International Conf. on the Theory and Application of Cryptographic Techniques, vol. 1807, May 14, 2000, pp. 156-171, Springer, Berlin Germany.
13 Boyko, Victor, et al., "Provably Secure Password-Authenticated Key Exchange Using Deffie-Hellman", Advances of Cryptology—Eurocrypt 2000, International Conf. on the Theory and Application of Cryptographic Techniques, vol. 1807, May 14, 2000, pp. 156-171, Springer, Berlin Germany.
14 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 .
15 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>.
16 Communication pursuant to Article 94(3) EPC issued in European Application No. 06704329.9 on Jul. 22, 2010; 4 pages.
17 Communication pursuant to Article 94(3) EPC issued in European Application No. 06704329.9 on Jun. 15, 2011; 4 pages.
18 Communication pursuant to Article 94(3) EPC issued in European Application No. 06704329.9 on Mar. 10, 2010; 4 pages.
19 Denning, et al., "Timestamps in Key Distribution Protocols", Communications of the Association for Computing Machinery, ACM, New York, NY, US, vol. 24, No. 8, Jan. 1, 1981, pp. 533-536, XP000907070, ISSN: 0001-0782.
20 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.
21 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.
22 European Search Report issued by the European Patent Office on Oct. 5, 2010 for European patent application No. 05742539.9.
23 European Search Report, issued May 18, 2007 for EP Application No. 05729970.
24 Extended European Search Report for EP Application 07124018 completed on Oct. 13, 2008.
25 Extended European Search Report for EP Application 07124019 completed on Jul. 9, 2008.
26 Extended European Search Report issued in European Application No. 06704329.9 on Nov. 12, 2009; 6 pages.
27 Freier, Alan O., et al., "The SSL Protocol Version 3.0", Transport Layer Security Working Group, Internet-Draft, downloaded on Mar. 12, 2008 from http://wp.netscape.com/eng/ss13/draft302.txt.
28 Gjoesteen, Kristian; "Comments on Dual-EC-DRBG/NIST SP 800-90, Draft Dec. 2005"; Mar. 16, 2006; 8 pages.
29 Goldreich, Oded; Foundations of Cryptography Basic Tools'; Cambridge University Press; 2001; pages.
30 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 .
31 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>.
32 International Preliminary Report on Patentability issued in International Application No. PCT/CA2006/000065on Aug. 2, 2007.
33 International Search Report and Written Opinion of the International Searching Authority issued in International Application No. PCT/CA2006/000065 on May 1, 2006; 11 pages.
34 International Search Report of Application No. PCT/CA2005/000466, date of mailing Jul. 20, 2005-11 pgs.
35 International Search Report of Application No. PCT/CA2005/000466, date of mailing Jul. 20, 2005—11 pgs.
36 International Search Report of Application No. PCT/CA2005/000676, date of mailing Aug. 22, 2005-15 pgs.
37 International Search Report of Application No. PCT/CA2005/000676, date of mailing Aug. 22, 2005—15 pgs.
38 Jablon, D, "The SPEKE Password-Based Key Agreement Methods", Phoenix Technologies, oCT. 22, 2003, downloaded on mAR. 12, 2008 from http://tools.ietf.org/html/draft-jablon-speke-02.
39 Jablon, DP, "Strong Password-Only Authenticated Key Exchange", Computer Communication Review, ACM SIGCOMM, New York, NY, vol. 26, No. 5, pp. 5-26 (Oct. 1996).
40 Johnson, Don B.; "X9.82 Part 3-Number Theoretic DRBGs"; NIST RNG Workshop; Jul. 20, 2004; retrieved from the internet .
41 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>.
42 Kaliski, Burton S., Jr.; "A Pseudo-Random Bit Generator Based on Elliptic Logarithms"; Advances in Cryptology; CRYPTO 1986; vol. 263; pp. 84-103.
43 Langford, Susan K., "Weaknesses in Some Threshold Cryptosystems", Aug. 18, 1996, San Jose, California.
44 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.
45 Luby, Michael; "Pseudorandomness and Cryptographic Applications"; Princeton University Press; 1996; pp. 70-74.
46 Menezes, A., et al., "Handbook of Applied Cryptography", 1997, CRC Press, pp. 570-572.
47 Menezes, A., et al., Handbook of Applied Cryptography, CRC Press, Chap. 10, pp. 385-424 (1996).
48 Office Action issued in U.S. Appl. No. 11/336,814 on Apr. 15, 2011; 31 pages.
49 Office Action issued in U.S. Appl. No. 11/336,814 on Aug. 23, 2010; 22 pages.
50 Office Action issued in U.S. Appl. No. 11/336,814 on Jun. 23, 2009; 10 pages.
51 Office Action received in Japanese Patent Application No. 2007-551522, issued Aug. 19, 2011, with English translation, 19 pages total.
52 Printout from wikipedia.org entitled "Diffie-Hellman Key Exchange", downloaded Mar. 12, 2008.
53 Printout from wikipedia.org entitled "Elliptic Curve Cryptography", downloaded Mar. 12, 2008.
54 Printout from wikipedia.org entitled "Legendre Symbol", downloaded Mar. 12, 2008.
55 Printout from wikipedia.org entitled "Shanks-Tonelli Algorithm", downloaded Mar. 12, 2008.
56 Printout from wikipedia.org entitled "Speke", downloaded Mar. 12, 2008.
57 S. Blake-Wilson et al, "Elliptic Curve Cryptography (ECC) Cipher Suites for Transport Layer Security (TLS)", May 2006.
58 Steiner, M., et al., Cliques: A New Approach to Group Key Agreement, May 1998, IEEE.
59 U.S. Appl. No. 11/962,181, filed Dec. 21, 2007.
60 U.S. Appl. No. 11/962,189, filed Dec. 21, 2007.
61 Van Oorschot, Paul C., et al., "Authentication and Authentication Key Exchanges", article, Mar. 6, 1992, 19, Kluwer Academic Publishers, Netherlands.
62 Zhang, Muxiang, "Analysis of the SPEKE Password-Authenticated Key Exchange Protocol", IEEE Communications Letters, IEEE Service Center, Jan. 1, 2004, pp. 63-65, vol. 8, No. 1, Piscataway, NJ US.
International Classification H04L9/30, H04L9/00, H04L29/06
Cooperative Classification H04L9/0844, H04L63/18, H04L9/3066, H04L2209/80, H04L9/002, H04L9/3215, H04L9/3226, H04L63/061, H04W12/06, H04W12/04, H04L63/083, H04L9/08, H04L9/0841
European Classification H04W12/04, H04L63/06A, H04L9/08, H04L9/32P, H04L9/30
Free format text: ASSIGNMENT OF ASSIGNORS INTEREST;ASSIGNORS:BROWN, MICHAEL K.;LITTLE, HERBERT A.;MACFARLANE, DAVID VICTOR;AND OTHERS;REEL/FRAME:025638/0399