Elliptic curve encryption systems

• US 6,141,420 A
• Filed: 01/29/1997
• Issued: 10/31/2000
• Est. Priority Date: 07/29/1994
• Status: Expired due to Term

• Current Assignee: Certicom Corporation (Blackberry Limited)
• Original Assignee: Certicom Corporation (Blackberry Limited)
• Inventors: Vanstone, Scott A., Mullin, Ronald C., Agnew, Gordon B.
• Primary Examiner(s): GREGORY, BERNARR E
• Application Number:
  US08/790,987
• Time in Patent Office: 1,371 Days
• Field of Search: 380/28, 380/30, 380/44, 380/46, 380/49, 380/50, 380/9, 708/200, 708/491, 708/492
• US Class Current: 380/30
• 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
• CPC Class Codes: H04L 2209/125 Parallelization or pipelining, e.g. for accelerating processing of cryptographic operations
• CPC Class Codes: H04L 9/3066 involving algebraic varieties, e.g. elliptic or hyper-elliptic curves

Abstract

An elliptic curve encryption system represents coordinates of a point on the curve as a vector of binary digits in a normal basis representation in F₂.spsb.m. A key is generated from multiple additions of one or more points in a finite field. Inverses of values are computed using a finite field multiplier and successive exponentiations. A key is represented as the coordinates of a point on the curve and key transfer may be accomplished with the transmission of only one coordinate and identifying information of the second. An encryption protocol using one of the coordinates and a further function of that coordinate is also described.

Claims

1. In a data encryption system in which the data is combined with an encryption key to produce ciphertext, a method of generating a key comprising the steps of

a) selecting an elliptic curve of the form y² +xy=x³ +ax² +b lying in the finite field GF2^m, said field being selected to have elements A².spsp.i (o≦

i≦

m) that constitute a normal basis,

b) representing the coordinates of a point on said curve as a set of vectors, each vector representing a coordinate of said point and having m binary digits, each of which represents the coefficient of A².spsp.i in the normal basis representation of said vector,

c) computing from addition of at least two sets of vectors an additional set of vectors to represent the coordinates of further point on said curve, and

d) utilising said additional set of vectors to derive a key for encrypting data.

2. A method according to claim 1 wherein addition of sets of vectors involves at lest one squaring operation.

3. A method according to claim 2 wherein said squaring operation is performed on at least one of said vectors of one of said sets representing a point.

4. A method according to claim 3 wherein said squaring operation is performed on combinations of vectors from a plurality of said sets representing respective points.

5. A method according to claim 3 wherein each of said vectors is represented as m binary digits and squaring thereof is performed by a cyclic shift of said m binary digits.

6. A method according to claim 5 wherein said m binary digits are stored in respective cells of a shift register and squaring thereof is performed by a cyclic shift of said m bits in said register.

7. A method according to claim 1 wherein addition of sets of vectors involves the computation of at least one inverse of a vector.

8. A method according to claim 7 wherein said inversion utilises multiple squaring operations.

9. A method according to claim 8 wherein squaring operations are performed by a cyclic shift of binary digits.

10. A method according to claim 7 wherein computation of said inverse includes an exponentiation of the square of the vector to provide a value γ

of the form

space="preserve" listing-type="equation">γ

=β

.sup.1+2+2.spsp.2 .sup.. . . 2.spsp.g-1

where β

is the square of the vector and g is a factor of m-1.

11. A method according to claim 10 wherein successive terms of said exponentiation are obtained by successive cyclic shifts of the vector.

12. A method according to claim 11 wherein the value of the γ

is accumulated after each cyclic shift by multiplication of the shifted term with the previously accumulated value of γ

.

13. A method according to claim 10 wherein m binary digits representing β

are stored in each of a pair of shift registers, one of said pair of registers being cyclically shifted and said pair of registers being multiplied to provide an intermediate value of γ

.

14. A method according to claim 13 wherein said one of said pair of registers is further cyclically shifted to provide a further successive term of said expansion and said further successive term multiplied with said intermediate value to provide a further intermediate value of γ

.

15. A method according to claim 14 wherein said cyclic shifting and multiplication is performed g-2 times to complete said exponentiation of β

and provide a value of γ

.

16. A method according to claim 10 where computation of said inverse includes a further exponentiation of γ

of the form

space="preserve" listing-type="equation">γ

.sup.1+2.spsp.g.sup.+2.spsp.2g .sup.. . . 2.spsp.(h-i)g

where h is a factor of m-1 such that gh=m-1.

17. A method according to claim 16 wherein successive terms said further exponentiation are obtained by successive cyclic shifts of the m binary digits representing γ

.

18. A method according to claim 17 wherein the value of said inverse is accumulated after each cyclic shift by multiplication of the shifted term with the previously accumulated value of γ

.

19. A method according to claim 16 wherein m binary digits representing γ

are stored in each of a pair of shift registers, one of said pair of registers being cyclically shifted and said pair of registers being multiplied together to provide an intermediate value of said inverse.

20. A method according to claim 19 wherein said one of said pair of registers is further cyclically shifted to provide a further successive term of said expansion which is then multiplied with said intermediate value of said inverse to provide a further intermediate value thereof.

21. A method according to claim 20 wherein said cyclic shifting and multiplication is performed (h-1)g-1 times to complete exponentiation of γ

.

22. A method according to claim 11 wherein said further point on said curve is an integer multiple d of said point P and said value dP is computed by successively doubling multiples of P to provide terms 2ⁱ P from t=o to t=m, and computing ##EQU16## where λ

is the coefficient of the binary representation of d.

23. A method according to claim 22 wherein doubling of multiples of p is obtained by computing ##EQU17## and ##EQU18## where x₁ y₁ are the coordinates of the point 2^i-1 and x₃ y₃ are the coordinates of the point 2ⁱ p.

24. A method according to claim 23 wherein computation of the term x₁² is obtained by a cyclic shift of binary digits representing x₁ in a normal basis.

25. A method according to claim 24 wherein computation of the inverse of x₁² is computed by an exponentiation of x₁² to provide a value γ

of the form

space="preserve" listing-type="equation">β

.sup.1+2+2.sup.2 . . . 2.sup.g-1

where β

=x₁² and g is a factor of m-1.

26. A method according to claim 25 wherein successive terms of said exponentiation are obtained by successive cyclic shifts of the binary digits representing x₁² in a normal basis.

27. A method according to claim 26 wherein computation of the inverse of x₁² includes a further exponentiation of γ

of the form

space="preserve" listing-type="equation">γ

Σ

1+2.sup.g +2.sup.2g . . . 2.sup.(h-i)g

where h is a factor of m-1 such that gh=m-1.

28. A method according to claim 27 wherein successive terms said further exponentiation are obtained by successive cyclic shifts of the m binary digits representing γ

.

29. A method of transferring the coordinates of a point on an algebraic curve defined by a function of two variables between a pair of correspondents connected by a data communications link comprising the steps of forwarding from one correspondent to another a coordinate of said point, providing at said other correspondent parameters of said algebraic curve, and computing at said other correspondent said other coordinate from said one coordinate and said algebraic curve.

30. A method according to claim 29 including the step of forwarding with said one coordinate identifying information of said other coordinate and utilising said identifying information and a discriminating function to determine the appropriate value of said other coordinate.

31. A method according to claim 30 wherein said identifying information is a digital bit of said other coordinate that identifies the appropriate value of said other coordinate.

32. A method according to claim 30 wherein said algebraic curve is an elliptic curve of the form y² +xy=x³ +ax² +b and said other coordinate is determined by solving a quadratic equation to provide two possible values of said other coordinate, said identifying information indicating the appropriate one of said values.

33. A method according to claim 32 wherein said identifying information is a digital bit of said other coordinate that identifies the appropriate value of said other coordinate.

34. A method according to claim 30 wherein said algebraic curve is defined over the field Zp and said identifying information indicates the Legendre symbol of the appropriate value.

35. A method according to claim 30 wherein said curve is defined over the field zp and the elements thereof subdivided into a pair of subsets, one of which contains one possible value and the other of which contains the other possible value, said indicating information identifying the subset containing the appropriate value.

36. A method according to claim 29 wherein said algebraic curve is an elliptic curve of the form y² +xy=x³ +ax+b defined over a finite field F₂^m.

37. A method according to claim 36 including the step of forwarding with said one coordinate identifying information of said other coordinate and utilising said identifying information and a discriminating function to determine the appropriate value of said other coordinate.

38. A method according to claim 37 wherein said field GF2^m has field elements A².spsp.i that constitute a normal basis.

39. A method according to claim 38 wherein said other coordinate is determined by solving a quadratic equation to provide two possible values of said other coordinate, said identifying information indicating the appropriate one of said values.

40. A method according to claim 38 wherein said quadratic equation is solved by summing terms of the form c from g=0 to g=m-1 where ##EQU19## and x₀ is said one coordinate.

41. A method according to claim 40 wherein terms of the form c are obtained by g fold cyclic shifts of the normal basis representation of c.

42. A method of encrypting a message m using a public key cryptographic system and having a private key formed from a bit string representative of a coordinate (x, y) of a point p on an elliptic curve, said method comprising the steps of representing said message m as a pair of message bit strings m₁ m₂ of length corresponding to the bit strings representing the coordinates x,y, and combining said message bit strings with an enciphering bit string derived from at least one of said coordinates to generate a ciphertext c of said message.

43. A method according to claim 42 wherein said enciphering bit strings are derived from each of said coordinates to produce ciphertext c.

44. A method according to claim 42 wherein said message bit strings are combined with enciphering bit strings derived from one of said coordinates and a function thereof to produce said ciphertext.

45. A method according to claim 43 wherein said enciphering bit string is derived from said coordinate x and the cube x³ thereof.

46. A method according to claim 42 wherein field elements z are derived from at least one of said coordinates and modify the combination of said message bit strings and said enciphering bit string.

47. A method according to claim 46 wherein said ciphertext c is of the form (c₁ c₂) where

c₁ =z₁ (m₁ ⊕

f₁ (x₀)) and

c₂ +z₂ (m₁ ⊕

f₂ (x₀));

f₁ (x₀)f₂ (x) are respective first and second values derived from the coordinate x and z₁ and z₂ are respective field elements derived from the coordinate x.

48. A method according to claim 47 wherein f₂ (x) is said second coordinate y.

49. A method according to claim 47 wherein f₂ (x) is the cube of the value of the coordinate x.

50. A method according to claim 47 wherein said field elements z are formed by concatenating part of each of said values f₁ (x), f₂ (x).

51. A method according to claim 50 wherein f₂ (x) is derived from the cube of the value of the coordinate x.

52. A method according to claim 47 wherein