Method and apparatus for performing elliptic curve arithmetic

• US 20040010689A1
• Filed: 05/05/2003
• Published: 01/15/2004
• Est. Priority Date: 05/03/2002
• Status: Active Grant

• Current Assignee: Blackberry Limited
• Original Assignee: Certicom Corporation (Blackberry Limited)
• Inventors: Vanstone, Scott A., Brown, Daniel R.
• Granted Patent: US 7,418,099 B2
• Time in Patent Office: Days
• US Class Current: 713/171
• CPC Class Codes: G06F 7/725 over elliptic curves
• CPC Class Codes: H04L 9/002 Countermeasures against attacks on cryptographic mechanisms network architectures or network communication protocols for protection against malicious traffic H04L63/1441
• CPC Class Codes: H04L 9/0894 Escrow, recovery or storing of secret information, e.g. secret key escrow or cryptographic key storage
• CPC Class Codes: H04L 9/3066 involving algebraic varieties, e.g. elliptic or hyper-elliptic curves

Abstract

A method of performing a cryptographic operation on a point in an elliptic curve cryptosystem using an elliptic carve. The method comprises the steps of obtaining information that uniquely identifies the elliptic curve and performing computations on the point to obtain the result of the cryptographic operation. The computations use the information. The computations produce an incorrect result if the point is not on the elliptic curve.

Claims

1. A method of performing a cryptographic operation on a point in an elliptic curve cryptosystem using an elliptic curve, said method comprising the steps of:

c) obtaining information that uniquely identifies said elliptic curve; and

d) performing computations on said point to obtain the result of said cryptographic operation, said computations using said information;

whereby said computations produce an incorrect result if said point is not on said elliptic curve.

2. A method according to claim 1, wherein said cryptographic operation is used to recover a message from a cryptographically encoded message, said encoded message being encoded using a shared key derived from an elliptic curve public key, said information including a pair of values which uniquely identify the elliptic curve, and said computations including computing said shared key from said public key, and using each of said pair of values in the computation, said method further comprising decrypting said encrypted message using said shared key, and the computation of said shared key being correct only for said elliptic curve.

3. A method according to claim 2 wherein said pair of values are a pair of coefficients a, b.

4. A method according to claim 3, wherein said computation of said shared secret key uses said coefficient b in at least one but not all double operations.

5. A method according to claim 2 wherein said cryptographic encoding is encryption.

6. method according to claim 2 wherein said cryptographic encoding is authentication.

7. A method according to claim 1, wherein said cryptographic operation is computing a point multiple from a key K and a point G in an elliptic curve cryptosystem using an elliptic curve having coefficients a, b, and said computations include performing double operations and performing add operations, and at least one but not all of said double operations uses said coefficient b, thereby producing an incorrect result if said point is not on said elliptic curve.

11. A cryptographic unit according to claim 3, wherein said computation of said shared secret key uses said coefficient b in at least one but not all double operations.

8. A cryptographic unit for performing a cryptographic operation on a point in an elliptic curve cryptosystem using an elliptic curve, said unit comprising:

a) storage for information that uniquely identifies said elliptic curve; and

b) a cryptographic module operably coupled to said storage to perform computations on said point to obtain the result of said cryptographic operation, said computations using said information;

whereby said computations produce an incorrect result if said point is not on said elliptic curve.

9. A cryptographic unit according to claim 8, wherein said cryptographic operation is used to recover a message from a cryptographically encoded message, said encoded message being encoded using a shared key derived from an elliptic curve public key, said information including a pair of values which uniquely identify the elliptic curve, and said computations including computing said shared key from said public key, and using each of said pair of values in the computation, said unit further comprising a decrypter to decrypt said encrypted message using said shared key, and the computation of said shared key being correct only for said elliptic curve.

10. A cryptographic unit according to claim 9 wherein said pair of values are a pair of coefficients a, b.

12. A cryptographic unit according to claim 9 wherein said cryptographic encoding is encryption.

13. A cryptographic unit according to claim 9 wherein said cryptographic encoding is authentication.

14. A cryptographic unit according to claim 8, wherein said cryptographic operation is computing a point multiple from a key K and a point G in an elliptic curve cryptosystem using an elliptic curve having coefficients a, b, and said computations include performing double operations and performing add operations, and at least one but not all of said double operations uses said coefficient b, thereby producing an incorrect result if said point is not on said elliptic curve.

15. A computer readable storage medium containing processor instructions for performing a cryptographic operation on a point in an elliptic curve cryptosystem using an elliptic curve, said medium including instructions to:

c) obtain information that uniquely identifies said elliptic curve; and

d) perform computations on said point to obtain the result of said cryptographic operation, said computations using said information;

whereby said computations produce an incorrect result if said point is not on said elliptic curve.

16. A computer readable storage medium according to claim 15, wherein said cryptographic operation is used to recover a message from a cryptographically encoded message, said encoded message being encoded using a shared key derived from an elliptic curve public key, said information including a pair of values which uniquely identify the elliptic curve, and said computations including computing said shared key from said public key, and using each of said pair of values in the computation, said medium further comprising instructions to decrypt said encrypted message using said shared key, and the computation of said shared key being correct only for said elliptic curve.

17. A computer readable storage medium according to claim 16 wherein said pair of values arc a pair of coefficients a, b.

18. A computer readable storage medium according to claim 17, wherein said computation of said shared secret key uses said coefficient b in at least one but not all double operations.

19. A computer readable storage medium according to claim 16 wherein said cryptographic encoding is encryption.

20. A computer readable storage medium according to claim 16 wherein said cryptographic encoding is authentication.

21. A computer readable storage medium according to claim 15, wherein said cryptographic operation is computing a point multiple from a key K and a point G in an elliptic curve cryptosystem using an elliptic curve having coefficients a, b, and said computations include performing double operations and performing add operations, and at least one but not all of said double operations uses said coefficient b, thereby producing an incorrect result if said point is not on said elliptic curve.