Accelerating elliptic curve point multiplication through batched inversions

• US 7,702,105 B1
• Filed: 04/23/2004
• Issued: 04/20/2010
• Est. Priority Date: 04/23/2004
• Status: Active Grant

• Current Assignee: Oracle America, Inc. (Oracle Corporation)
• Original Assignee: Oracle America, Inc. (Oracle Corporation)
• Inventors: Gura, Nils, Eberle, Hans, Fung, Stephen C., Stebila, Douglas
• Primary Examiner(s): Zand; Kambiz
• Assistant Examiner(s): RAHIM, MONJUR
• Application Number:
  US10/830,661
• Time in Patent Office: 2,188 Days
• Field of Search: 380/255, 713/154
• US Class Current: 380/255
• CPC Class Codes: G06F 7/725 over elliptic curves
• CPC Class Codes: G06F 7/726 Inversion; Reciprocal calculation; Division of elements of a finite field

Abstract

Executing multiple elliptic curve cryptography (ECC) point multiplications in parallel and using batched inversions allows shared computations between independent ECC operations. The point multiplications may be computed over prime integer fields or over binary polynomial fields. The batched inversion may be shared between point additions and point doublings, between point additions, or between point doublings. The batched inversions are applicable to point multiplications using projective or using affine coordinate systems.

Claims

1. A method, comprising:

computing a batched inversion to produce a batched inversion result for use in elliptic curve cryptography (ECC) point multiplication; and

sharing the batched inversion result among multiple independent elliptic curve cryptography (ECC) point multiplications belonging to different secure transactions;

wherein said computing and said sharing are performed by a device configured to support a public-key cryptography application.

2. The method as recited in claim 1, further comprising processing, by at least two threads, multiple point multiplications, the two threads synchronizing to share the batched inversion result and otherwise processing the multiple point multiplications independently.

3. The method as recited in claim 1, further comprising:

receiving at a request queue ECC point multiplication requests from at least two threads;

processing the requests in the request queue using a third thread using the batched inversion result; and

returning results to respective threads.

5. The method as recited in claim 1, further comprising computing the point multiplications using affine coordinates.

6. The method as recited in claim 1, wherein the point multiplications are computed over a binary polynomial field.

7. The method as recited in claim 1, wherein the batched inversion result is shared between at least one point addition and at least one point doubling.

8. The method as recited in claim 1, wherein the batched inversion result is shared between point additions.

9. The method as recited in claim 1, wherein the batched inversion result is shared between point doublings.

10. The method as recited in claim 1, wherein the inversion is shared between precomputations belonging to the multiple independent elliptic curve cryptography (ECC) point multiplications.

4. The method as recited in 1, further comprising executing multiple independent point multiplications in parallel.

11. A computer-implemented method, comprising:

receiving multiple independent elliptic curve cryptography (ECC) point multiplications;

combining inversions from the multiple independent ECC point multiplications into one inversion and multiple multiplications; and

performing the one inversion and the multiple multiplications to produce a respective result for each of the independent ECC point multiplications.

12. A computer readable storage medium storing program instructions computer-executable to implement:

processing a plurality of independent elliptic curve cryptography (ECC) point multiplications; and

returning results of said processing;

wherein said processing comprises using a same batched inversion result in each of the plurality of independent ECC point multiplications.

13. The storage medium as recited in claim 12, wherein said processing comprises at least two threads processing multiple point multiplications, the two threads synchronizing to share the batched inversion result and otherwise each thread processing the multiple point multiplications independently.

14. A computer system, comprising;

means to receive multiple independent elliptic curve cryptography (ECC) point multiplications;

means to combine inversions from the independent ECC point multiplications into one inversion and multiple multiplications; and

means to perform the one inversion and the multiplications to reduce a respective result for each of the independent ECC point multiplications.

15. A computer system, comprising at least one inversion circuit, wherein the computer system is configured to perform:

computing a batched inversion to produce a batched inversion result for use in elliptic curve cryptography (ECC) point multiplication; and

sharing the batched inversion result among multiple independent elliptic curve cryptography (ECC) point multiplications belong to different secure transactions; and

wherein the computer system is configured to support a public-key cryptography application.

17. The computer system as recited in claim 15, wherein the cryptographic hardware accelerator includes a single inversion circuit for multiple multiplier circuits and multiple adder circuits, the single inversion circuit performing batched inversions for point multiplications being performed in the multiplier and adder circuits.

18. The computer system as recited in claim 15, wherein at least two threads process the multiple independent ECC point multiplications, and wherein the two threads share inversions.

19. The computer system as recited in claim 15, further comprising:

a request queue receiving ECC point multiplication requests from at least two threads; and

a third thread processing the requests using batched inversions and returning the results to respective threads.

20. The computer system as recited in claim 15, wherein the inversion is shared between precomputations belonging to the multiple independent elliptic curve cryptography (ECC) point multiplications.

16. The computer system as recited in 15, further comprising a cryptographic hardware accelerator configured to perform the batched inversion.

21. An apparatus, comprising:

means for processing a plurality of independent elliptic curve cryptography (ECC) point multiplication, wherein said processing comprises using a same batched inversion result in each of the plurality of independent ECC point multiplications; and

means for returning results of said processing.