SECURED PERFORMANCE OF AN ELLIPTIC CURVE CRYPTOGRAPHIC PROCESS

Abstract

A method for performing an elliptic curve cryptographic process to generate output data based on input data, the elliptic curve cryptographic process based on an elliptic curve over a finite field, wherein the generation of the output data comprises generating, based on a predetermined point V of the elliptic curve and a positive R-bit integer k, a first point of the elliptic curve that is based, at least in part, on the point kV of the elliptic curve, wherein k=Σ.sub.r=0.sup.R−1 2.sup.rb.sub.r and, for each r=0,1, . . . , R−1, b.sub.r is the bit value of k at bit position r of k, wherein the method comprises: storing, according to a partition of the R bit positions for k into T groups of bit positions P.sub.t (t=0, 1, . . . , T−1), a corresponding lookup table L.sub.t having, for each of the 2.sup.|P.sup.t.sup.|possible options for assigning to the |P.sub.t| bit positions s ∈ P.sub.t a respective bit value x.sub.s, a corresponding point of the elliptic curve that is based, at least in part, on the point (Σ.sub.s∈P.sub.t2.sup.sx.sub.s)V of the elliptic curve; obtaining k; and determining the first point as Σ.sub.t=0.sup.T−1l.sub.t, where l.sub.t is the point of the elliptic curve that corresponds, in lookup table L.sub.t, to the option for assigning to the |P.sub.t| bit positions s ∈ P.sub.t the corresponding bit value b.sub.s.

Claims

1. A method for performing an elliptic curve cryptographic process to generate output data based on input data, the elliptic curve cryptographic process based on an elliptic curve over a finite field, wherein the generation of the output data comprises generating, based on a predetermined point V of the elliptic curve and a positive R-bit integer k, a first point of the elliptic curve that is based, at least in part, on the point kV of the elliptic curve, wherein k=Σ.sub.r=0.sup.R−1 2.sup.rb.sub.r and, for each r=0,1, . . . , R−1, b.sub.r is the bit value of k at bit position r of k, wherein the method comprises: storing, according to a partition of the R bit positions for k into T groups of bit positions P.sub.t (t=0,1, . . . , T−1), a corresponding lookup table L.sub.t having, for each of the 2.sup.|P.sup.t.sup.| possible options for assigning to the |P.sub.t| bit positions s ∈P.sub.t a respective bit value x.sub.s, a corresponding point of the elliptic curve that is based, at least in part, on the point (Σ.sub.s∈P.sub.t 2.sup.sx.sub.s)V of the elliptic curve; obtaining k; and determining the first point as Σ.sub.t=0.sup.T−1 l.sub.t, where l.sub.t is the point of the elliptic curve that corresponds, in lookup table L.sub.t, to the option for assigning to the |P.sub.t| bit positions s ∈ P.sub.t the corresponding bit value b.sub.s.

2. The method of claim 1, wherein the first point of the elliptic curve is the point kV and wherein for each lookup table L.sub.t (t=0,1, . . . , T−1) and for each of the 2.sup.|P.sup.t.sup.| possible options for assigning to the |P.sub.t| bit positions s ∈ P.sub.t a respective bit value x.sub.s, the corresponding point of the elliptic curve stored in the lookup table L.sub.t is the point (Σ.sub.s∈P.sub.t 2.sup.sx.sub.s)V of the elliptic curve.

3. The method of claim 1, wherein the first point of the elliptic curve is the point (kμ)V, wherein μ is a predetermined non-negative integer, wherein for each lookup table L.sub.t (t=0,1, . . . , T−1) and for each of the 2.sup.|P.sup.t.sup.| possible options for assigning to the |P.sub.t| bit positions s ∈ P.sub.t a respective bit value x.sub.s, the corresponding point of the elliptic curve stored in the lookup table L.sub.t is the point (μ Σ.sub.s∈P.sub.t 2.sup.sx.sub.s)V of the elliptic curve.

4. The method of claim 1, wherein the first point of the elliptic curve is the point (k+μ)V, wherein μ is a predetermined non-negative R-bit integer, wherein μ=Σ.sub.r=0.sup.R−1 2.sup.r{circumflex over (b)}.sub.r and, for each r=0,1, . . . , R−1, {circumflex over (b)}.sub.r is the bit value of μ at bit position r of μ, wherein for each lookup table L.sub.t (t=0,1, . . . , T−1) and for each of the 2.sup.|P.sup.t.sup.| possible options for assigning to the |P.sub.t| bit positions s ∈ P.sub.t a respective bit value x.sub.s, the corresponding point of the elliptic curve stored in the lookup table L.sub.t is the point (Σ.sub.s∈P.sub.t 2.sup.sx.sub.s)V+(Σ.sub.s∈P.sub.t 2.sup.s{circumflex over (b)}.sub.s)V of the elliptic curve.

5. The method of claim 1, wherein the first point of the elliptic curve is the point k(V+M), wherein M is a predetermined point of the elliptic curve, wherein for each lookup table L.sub.t (t=0,1, . . . , T−1) and for each of the 2.sup.|P.sup.t.sup.| possible options for assigning to the |P.sub.t| bit positions s ∈ P.sub.t a respective bit value x.sub.s, the corresponding point of the elliptic curve stored in the lookup table L.sub.t is the point (Σ.sub.s∈P.sub.t 2.sup.sx.sub.s)V+(Σ.sub.s∈P.sub.t 2.sup.sx.sub.s)M of the elliptic curve.

6. The method of claim 1, wherein the first point of the elliptic curve is the point kV+M, wherein M is a predetermined point of the elliptic curve, wherein for each lookup table L.sub.t (t=0,1, . . . , T−1) and for each of the 2.sup.|P.sup.t.sup.| possible options for assigning to the |P.sub.t| bit positions s ∈ P.sub.t a respective bit value x.sub.s, the corresponding point of the elliptic curve stored in the lookup table L.sub.t is the point (Σ.sub.s∈P.sub.t 2.sup.sx.sub.s)V+M of the elliptic curve.

7. The method of claim 1, wherein the first point of the elliptic curve is the point kμV+M, wherein M is a predetermined point of the elliptic curve and μ is a predetermined non-negative integer, wherein for each lookup table L.sub.t (t=0,1, . . . , T−1) and for each of the 2.sup.|P.sup.t.sup.| possible options for assigning to the |P.sub.t| bit positions s ∈ P.sub.t a respective bit value x.sub.s, the corresponding point of the elliptic curve stored in the lookup table L.sub.t is the point (μΣ.sub.s∈P.sub.t 2.sup.sx.sub.s)V+M of the elliptic curve.

8. The method of claim 3, wherein μ is a secret maintained by a third party.

9. The method of claim 5, wherein M is a secret maintained by a third party.

10. The method of claim 1, wherein all of the T groups of bit positions P.sub.t (t=0,1, . . . , T−1) have the same number of bit positions.

11. The method of claim 10, wherein all of the T groups of bit positions P.sub.t (t=0,1, . . . , T−1) have 4 bit positions.

12. The method of claim 1, wherein, for each of the T groups of bit positions P.sub.t (t=0,1, . . . , T−1), the bit positions of P.sub.t are consecutive.

13. The method of claim 1, wherein the cryptographic process comprises one or more of: elliptic curve encryption; elliptic curve decryption; elliptic curve shared secret establishment; elliptic curve digital signature generation; elliptic curve digital signature verification.

14. (canceled)

15. (canceled)

16. The method of claim 4, wherein μ is a secret maintained by a third party.

17. The method of claim 7, wherein at least one of M and μ is a secret maintained by a third party.

18. The method of claim 6, wherein M is a secret maintained by a third party.

19. A system comprising one or more processors, the one or more processors arranged to carry out a method for performing an elliptic curve cryptographic process to generate output data based on input data, the elliptic curve cryptographic process based on an elliptic curve over a finite field, wherein the generation of the output data comprises generating, based on a predetermined point V of the elliptic curve and a positive R-bit integer k, a first point of the elliptic curve that is based, at least in part, on the point kV of the elliptic curve, wherein k=Σ.sub.r=0.sup.R−1 2.sup.rb.sub.r and, for each r=0,1, . . . , R−1, b.sub.r is the bit value of k at bit position r of k, wherein the method comprises: storing, according to a partition of the R bit positions for k into T groups of bit positions P.sub.t (t=0,1, . . . , T−1), a corresponding lookup table L.sub.t having, for each of the 2.sup.|P.sup.t.sup.51 possible options for assigning to the |P.sub.t| bit positions s ∈ P.sub.t a respective bit value x.sub.s, a corresponding point of the elliptic curve that is based, at least in part, on the point (Σ.sub.s∈P.sub.t 2.sup.sx.sub.s)V of the elliptic curve; obtaining k; and determining the first point as E.sub.t=0.sup.T−1 l.sub.t, where l.sub.t is the point of the elliptic curve that corresponds, in lookup table L.sub.t, to the option for assigning to the |P.sub.t| bit positions s ∈ P.sub.t the corresponding bit value b.sub.s.

Description

BRIEF DESCRIPTION OF THE DRAWINGS

[0056] Embodiments of the invention will now be described, by way of example only, with reference to the accompanying drawings, in which:

[0057] FIG. 1 schematically illustrates an example of a computer system; and

[0058] FIG. 2 is flow diagram illustrating a method for performing an elliptic curve cryptographic process.

DETAILED DESCRIPTION OF EMBODIMENTS OF THE INVENTION

[0059] In the description that follows and in the figures, certain embodiments of the invention are described. However, it will be appreciated that the invention is not limited to the embodiments that are described and that some embodiments may not include all of the features that are described below. It will be evident, however, that various modifications and changes may be made herein without departing from the broader spirit and scope of the invention as set forth in the appended claims.

1—System Overview

[0060] FIG. 1 schematically illustrates an example of a computer system 100. The system 100 comprises a computer 102. The computer 102 comprises: a storage medium 104, a memory 106, a processor 108, an interface 110, a user output interface 112, a user input interface 114 and a network interface 116, which may be linked together over one or more communication buses 118.

[0061] The storage medium 104 may be any form of non-volatile data storage device such as one or more of a hard disk drive, a magnetic disc, a solid-state-storage device, an optical disc, a ROM, etc. The storage medium 104 may store an operating system for the processor 108 to execute in order for the computer 102 to function. The storage medium 104 may also store one or more computer programs (or software or instructions or code).

[0062] The memory 106 may be any random access memory (storage unit or volatile storage medium) suitable for storing data and/or computer programs (or software or instructions or code).

[0063] The processor 108 may be any data processing unit suitable for executing one or more computer programs (such as those stored on the storage medium 104 and/or in the memory 106), some of which may be computer programs according to embodiments of the invention or computer programs that, when executed by the processor 108, cause the processor 108 to carry out a method according to an embodiment of the invention and configure the system 100 to be a system according to an embodiment of the invention. The processor 108 may comprise a single data processing unit or multiple data processing units operating in parallel, separately or in cooperation with each other. The processor 108, in carrying out data processing operations for embodiments of the invention, may store data to and/or read data from the storage medium 104 and/or the memory 106.

[0064] The interface 110 may be any unit for providing an interface to a device 122 external to, or removable from, the computer 102. The device 122 may be a data storage device, for example, one or more of an optical disc, a magnetic disc, a solid-state-storage device, etc. The device 122 may have processing capabilities—for example, the device may be a smart card. The interface 110 may therefore access data from, or provide data to, or interface with, the device 122 in accordance with one or more commands that it receives from the processor 108.

[0065] The user input interface 114 is arranged to receive input from a user, or operator, of the system 100. The user may provide this input via one or more input devices of the system 100, such as a mouse (or other pointing device) 126 and/or a keyboard 124, that are connected to, or in communication with, the user input interface 114. However, it will be appreciated that the user may provide input to the computer 102 via one or more additional or alternative input devices (such as a touch screen). The computer 102 may store the input received from the input devices via the user input interface 114 in the memory 106 for the processor 108 to subsequently access and process, or may pass it straight to the processor 108, so that the processor 108 can respond to the user input accordingly.

[0066] The user output interface 112 is arranged to provide a graphical/visual and/or audio output to a user, or operator, of the system 100. As such, the processor 108 may be arranged to instruct the user output interface 112 to form an image/video signal representing a desired graphical output, and to provide this signal to a monitor (or screen or display unit) 120 of the system 100 that is connected to the user output interface 112. Additionally or alternatively, the processor 108 may be arranged to instruct the user output interface 112 to form an audio signal representing a desired audio output, and to provide this signal to one or more speakers 121 of the system 100 that is connected to the user output interface 112.

[0067] Finally, the network interface 116 provides functionality for the computer 102 to download data from and/or upload data to one or more data communication networks.

[0068] It will be appreciated that the architecture of the system 100 illustrated in FIG. 1 and described above is merely exemplary and that other computer systems 100 with different architectures (for example with fewer components than shown in FIG. 1 or with additional and/or alternative components than shown in FIG. 1) may be used in embodiments of the invention. As examples, the computer system 100 could comprise one or more of: a personal computer; a server computer; a mobile telephone; a tablet; a laptop; a television set; a set top box; a games console; other mobile devices or consumer electronics devices; etc. Additionally, it is possible that some components of the computer system 100 are not located in the computer 102 and are, instead, part of a computer network connected to the computer 102 via the network interface 116. Additionally or alternatively, the computer system 100 may comprise multiple computers 102, e.g. in a network of computers such as a cloud system of computing resources.

2—Elliptic Curve Cryptographic Processes With Masked Curve Points

[0069] Elliptic curve cryptographic processes (such as the examples set out earlier) may involve performing elliptic curve scalar multiplication, namely: given an elliptic curve point V and a non-negative integer k, calculation of the elliptic curve point kV. The point V could, for example, be the generator point G or a public key Q. When implementing the cryptographic process (e.g. as part of a software implementation), it is possible to do so in a masked way. The masking could take a variety of forms, e.g. (a) using the point {circumflex over (V)}=μV instead of the point V for some positive integer μ (which may be kept secret) to thereby calculate k{circumflex over (V)}=kμV; (b) calculating the point {circumflex over (V)}=(k+μ)V instead of the point kV for some positive integer μ (which may be kept secret); (c) calculating the point {circumflex over (V)}=kV+M or {circumflex over (V)}=k(V+M) instead of the point kV for some elliptic curve point M≠; (d) some combination of the above; etc.

EXAMPLE 1—CONTINUED

Elliptic Curve Shared Secret Establishment

[0070] Continuing the example of elliptic curve shared secret establishment set out earlier, this may be implemented/adapted in a variety of ways, as set out below: [0071] Implementation using the point {circumflex over (V)}=μV instead of the point V for some positive integer μ [0072] Alice's implementation uses an obfuscated version of d.sub.A, namely {circumflex over (d)}.sub.A, instead of d.sub.A, where d.sub.A=μ{circumflex over (d)}.sub.A. Here, μ is a positive integer kept secret by a third party (e.g. the third party may have been involved in the initial generation of the private key d.sub.A, and may have generated (and kept secret) the value μ and may have provided {circumflex over (d)}.sub.A and not d.sub.A to Alice). Thus, Alice's implementation is more secure, as it does not store or reveal the actual private key d.sub.A. [0073] When Bob wants to send his public key Q.sub.B to Alice, Bob passes Q.sub.B to the third party, and the third party provides (or identifies) an obfuscated version of Q.sub.B, namely the point {circumflex over (Q)}.sub.B=μQ.sub.B, to Alice, or the third party enables Alice to implement the function f (x)=xμQ.sub.B (e.g. by providing code to implement this function or, as set out in more detail later, by providing a suitable set of lookup tables). [0074] Alice can then calculate {circumflex over (d)}.sub.A{circumflex over (Q)}.sub.B={circumflex over (d)}.sub.AμQ.sub.B=f ({circumflex over (d)}.sub.A)=d.sub.AQ.sub.B. [0075] Bob can calculate d.sub.BQ.sub.A to yield the same result (i.e. d.sub.AQ.sub.B) as Alice. This could be based directly on d.sub.B and Q.sub.A or, in an analogous way as for Alice, using an obfuscated version of d.sub.B (which may be based on a different value for μ) and a correspondingly obfuscated version of Q.sub.A. [0076] Implementation using calculation of the point {circumflex over (V)}=(k+μ)V instead of the point kV for some positive integer μ [0077] Alice's implementation uses an obfuscated version of d.sub.A, namely {circumflex over (d)}.sub.A, instead of d.sub.A, where d.sub.A=μ+{circumflex over (d)}.sub.A. Here, μ is a positive integer kept secret by a third party (e.g. the third party may have been involved in the initial generation of the private key d.sub.A, and may have generated (and kept secret) the value μ and may have provided {circumflex over (d)}.sub.A and not d.sub.A to Alice). Thus, Alice's implementation is more secure, as it does not store or reveal the actual private key d.sub.A. [0078] When Bob wants to send his public key Q.sub.B to Alice, Bob passes Q.sub.B to the third party, and the third party enables Alice to implement the function f (x)=(x+μ) Q.sub.B (e.g. by providing code to implement this function or, as set out in more detail later, by providing a suitable set of lookup tables). [0079] Alice can then calculate f ({circumflex over (d)}.sub.A)=({circumflex over (d)}.sub.A+μ)Q.sub.B=d.sub.AQ.sub.B. [0080] Bob can calculate d.sub.BQ.sub.A to yield the same result (i.e. d.sub.AQ.sub.B) as Alice. This could be based directly on d.sub.B and Q.sub.A or, in an analogous way as for Alice, using an obfuscated version of d.sub.B (which may be based on a different value for μ) and a correspondingly obfuscated version of Q.sub.A. [0081] Implementation using calculation of the point {circumflex over (V)}=kV+M instead of the point kV for some elliptic curve point M≠ [0082] Alice's implementation uses an obfuscated version of d.sub.A, namely {circumflex over (d)}.sub.A, instead of d.sub.A, where d.sub.A=μ{circumflex over (d)}.sub.A. Here, μ is a positive integer kept secret by a third party (e.g. the third party may have been involved in the initial generation of the private key d.sub.A, and may have generated (and kept secret) the value μ and may have provided {circumflex over (d)}.sub.A and not d.sub.A to Alice). Thus, Alice's implementation is more secure, as it does not store or reveal the actual private key d.sub.A. [0083] When Bob wants to send his public key Q.sub.B to Alice, Bob passes Q.sub.B to the third party, and the third party enables Alice to implement the function f (x)=xμQ.sub.B+M (e.g. by providing code to implement this function or, as set out in more detail later, by providing a suitable set of lookup tables). [0084] Alice can then calculate f ({circumflex over (d)}.sub.A)={circumflex over (d)}.sub.AμQ.sub.B+M=d.sub.AQ.sub.B+M. [0085] Bob can calculate d.sub.BQ.sub.A+M to yield the same result (i.e. d.sub.AQ.sub.B+M) as Alice. This could be based directly on d.sub.B and Q.sub.A or, in an analogous way as for Alice, using an obfuscated version of d.sub.B (which may be based on a different value for μ) and a correspondingly obfuscated version of Q.sub.A.

EXAMPLE 2—CONTINUED

Elliptic Curve Encryption And Decryption

[0086] Continuing the example of elliptic curve encryption and decryption set out earlier, this may be implemented/adapted in a variety of ways, as set out below: [0087] Implementation using the point {circumflex over (V)}=μV instead of the point V for some positive integer μ [0088] Bob's implementation uses an obfuscated version of d.sub.B, namely {circumflex over (d)}.sub.B, instead of d.sub.B, where d.sub.B=μ{circumflex over (d)}.sub.B. Here, μ is a positive integer kept secret by a third party (e.g. the third party may have been involved in the initial generation of the private key d.sub.B, and may have generated (and kept secret) the value μ and may have provided {circumflex over (d)}.sub.B and not d.sub.B to Bob). Thus, Bob's implementation is more secure, as it does not store or reveal the actual private key d.sub.B. [0089] When Bob wants to send his public key Q.sub.B to Alice, Bob passes Q.sub.B to the third party, and the third party provides (or identifies) Q.sub.B to Alice along with an obfuscated version of G, namely the point Ĝ=μG, to Alice, or the third party enables Alice to implement the function f (x)=xμG (e.g. by providing code to implement this function or, as set out in more detail later, by providing a suitable set of lookup tables). Alternatively, the third party may already have provided (or identified) Bob with Ĝ (or the code or tables for the function f), so that Bob can provide these directly to Alice instead of using the third party for this provision to Alice. [0090] Encryption step (1) then becomes Alice generating a random integer r ∈ [1,n−1] and calculating Ŵ=rĜ=f (r)=rμG . Alice sends Ŵ to Bob instead of W at encryption step (5). [0091] Decryption step (1) then becomes Bob generating s=p.sub.x where P=(p.sub.x, p.sub.y)={circumflex over (d)}.sub.BŴ (noting that {circumflex over (d)}.sub.BŴ={circumflex over (d)}.sub.BrμG=d.sub.BrG=rQ.sub.B as desired). [0092] Implementation using the point V=μV instead of the point V for some positive integer μ [0093] Bob's implementation uses an obfuscated version of d.sub.B, namely {circumflex over (d)}.sub.B, instead of d.sub.B, where {circumflex over (d)}.sub.B=μd.sub.B. Here, μ is a positive integer kept secret by a third party (e.g. the third party may have been involved in the initial generation of the private key d.sub.B, and may have generated (and kept secret) the value μ and may have provided {circumflex over (d)}.sub.B and not d.sub.B to Bob). Thus, Bob's implementation is more secure, as it does not store or reveal the actual private key d.sub.B. [0094] When Bob wants to send his public key Q.sub.B to Alice, Bob passes Q.sub.B to the third party, and the third party provides (or identifies) an obfuscated version of Q.sub.B, namely the point {circumflex over (Q)}.sub.B=μQ.sub.B, to Alice, or the third party enables Alice to implement the function f(x)=xμQ .sub.B (e.g. by providing code to implement this function or, as set out in more detail later, by providing a suitable set of lookup tables). Alternatively, the third party may already have provided (or identified) Bob with {circumflex over (Q)}.sub.B (or the code or tables for the function f), so that Bob can provide these directly to Alice instead of using the third party for this provision to Alice. [0095] Encryption step (2) then involves Alice generating {circumflex over (P)}=r{circumflex over (Q)}.sub.B=f (r), with {circumflex over (P)} being used subsequently instead of P. [0096] Decryption step (1) then becomes Bob generating s=p.sub.x where P=(p.sub.x, p.sub.y)={circumflex over (d)}.sub.BW (noting that {circumflex over (d)}.sub.BW=μd.sub.BrG=rμQ.sub.B=r{circumflex over (Q)}.sub.B=f (r)={circumflex over (P)} as desired). [0097] Of course, this could be combined with the previous masked implementation of elliptic curve encryption and decryption.

EXAMPLE 3—CONTINUED

Elliptic Curve Digital Signatures

[0098] Continuing the example of elliptic curve digital signatures set out earlier, this may be implemented/adapted in a variety of ways, as set out below: [0099] Implementation using the point {circumflex over (V)}=μV instead of the point V for some positive integer μ [0100] Alice's implementation uses an obfuscated version of d.sub.A, namely {circumflex over (d)}.sub.A, instead of d.sub.A, where {circumflex over (d)}.sub.A=μd.sub.A. Here, μ is a positive integer kept secret by a third party (e.g. the third party may have been involved in the initial generation of the private key d.sub.A, and may have generated (and kept secret) the value μ and may have provided {circumflex over (d)}.sub.A and not d.sub.A to Alice). Thus, Alice's implementation is more secure, as it does not store or reveal the actual private key d.sub.A. [0101] When Alice wants to send her public key Q.sub.A to Bob, Alice passes Q.sub.A to the third party, and the third party provides (or identifies) an obfuscated version of Q.sub.A, namely the point {circumflex over (Q)}.sub.A=μQ.sub.A, to Bob, or the third party enables Bob to implement the function f(x)=xμQ.sub.A (e.g. by providing code to implement this function or, as set out in more detail later, by providing a suitable set of lookup tables). Alternatively, the third party may already have provided (or identified) Alice with {circumflex over (Q)}.sub.A (or the code or tables for the function f), so that Alice can provide these directly to Bob instead of using the third party for this provision to Bob. [0102] Signature step (6) then becomes [0103] Calculate s=k.sup.−1 (z+r{circumflex over (d)}.sub.A) mod n. If s=0 then 0 return to (3). [0104] Verification step (1) then becomes checking the validity of {circumflex over (Q)}.sub.A. [0105] Verification step (5) then becomes [0106] Calculate the point of the elliptic curve (x.sub.1, y.sub.1)=u.sub.1G+u.sub.2{circumflex over (Q)}.sub.A. [0107] Here, we note that:

[00001]$\begin{array}{c}{u}_{1}G+u_2{\hat{Q}}_A=u_{1}G+u_2\mu Q_A\\ =u_{1}G+u_2\mu d_{A}G\\ =u_{1}G+u_2{\hat{d}}_{A}G\\ =\left({\mathrm{zs}}^{-1}+{\mathrm{rs}}^{-1}{\hat{d}}_A\right)G\\ =\left(z+r{\hat{d}}_A\right)s^{-1}G\\ =\left(z+r{\hat{d}}_A\right){\left(k^{-1}\left(z+r{\hat{d}}_A\right)\right)}^{-1}G\\ =kG\\ =\left(x_1,y_1\right)\end{array}$ [0108] as desired.

3—Secured Elliptic Curve Multiplication

[0109] Set out below is a method for performing secured elliptic curve scalar multiplication, namely: given an elliptic curve point V and a non-negative integer k, secured calculation of the elliptic curve point kV. The elliptic curve point V could, for example, be the generator point G that forms part of the domain parameters for the elliptic curve cryptographic process, but this is merely one example for the elliptic curve point V.

[0110] The integer k has (or may be represented by) R bits. Thus, there are R bit positions in the binary representation of k. In the following, the bit positions shall be positions 0,1, . . . , R−1, where bit position 0 is the position of the least significant bit and bit position R−1 is the position of the most significant bit. It will, however, be appreciated that this is not essential and that the equations/formulae set out below could be adapted to other bit position numbering accordingly. The values of k's bits are b.sub.r (r=0,1, . . . , R−1) where b.sub.r=0 or 1 and b.sub.r is the value for bit position r, so that k=Σ.sub.r=0.sup.R−1 2.sup.rb.sub.r.

[0111] These R bit positions for k may be partitioned (or split or divided) into T groups (or sets) of bit positions P.sub.t (t=0,1, . . . , T−1), for an integer T>1. Each group P.sub.t (t=0,1, . . . , T−1) has |P.sub.t| bit positions respectively, namely p.sub.t,s (s=0,1, . . . , |P.sub.t|−1), i.e. P.sub.t={p.sub.t,0, p.sub.t,1, . . . , p.sub.t,|P.sub.t.sub.|−1}. The T groups of bit positions P.sub.t (t=0,1, . . . , T−1) are non-overlapping groups of bit positions that, together, span the full set of R bit positions for k, i.e. P.sub.t.sub.1 ∩ P.sub.t.sub.2∅ if t.sub.1≠t.sub.2, and ∩.sub.t=0, . . . , T−1 P.sub.t={0,1, . . . , R−1}. Thus Σ.sub.t=0.sup.T−1|P.sub.t|=R.

[0112] Notably, k=Σ.sub.r=0.sup.R−12.sup.rb.sub.r=Σ.sub.t=0.sup.T−1 Σ.sub.s∈P.sub.t 2.sup.sb.sub.s so that kV=(Σ.sub.r=0.sup.R−1 2.sup.wb.sub.w)V=(Σ.sub.t=0.sup.T−1 Σ.sub.s∈P.sub.t 2.sup.sb.sub.s)V=Σ.sub.t=0.sup.T−1 ((Σ.sub.s∈P.sub.t 2.sup.sb.sub.s)V).

[0113] Now, as each group P.sub.t (t=0,1, . . . , T−1) has |P.sub.t| bit positions, there are 2.sup.|P.sup.t.sup.| possible options for assigning a respective bit value x.sub.s (where x.sub.s=0 or 1) to the |P.sub.t| bit positions p.sub.s ∈ P.sub.t. Defining Y(V, {x.sub.s: s ∈ P.sub.t})=(Σ.sub.s∈P.sub.t 2.sup.ss.sub.s)V, then for each group P.sub.t (t=0,1, . . . , T−1), a corresponding lookup table L.sub.t may be constructed, where L.sub.t has, for each of the 2.sup.|P.sup.t.sup.| possible options for assigning to the |P.sub.t| bit positions s ∈ P.sub.t a respective bit value x.sub.s, the corresponding elliptic curve point Y(V, {x.sub.s: s ∈ P.sub.t}). For example, if P.sub.t={4,5,10}, then Y(V, {x.sub.4, x.sub.5, x.sub.10})=(2.sup.4x.sub.4+2.sup.5x.sub.5+2.sup.10x.sub.10)V, and there are 8 points Y(V, {x.sub.4, x.sub.5, x.sub.10}) stored in the lookup table L.sub.t corresponding to the 8 possible options for assigning bit values to the triple of bits x.sub.4, x.sub.5, x.sub.10.

[0114] Hence, given any particular option for assigning to the |P.sub.t| bit positions p.sub.s ∈ P.sub.t respective bit value x.sub.s (where x.sub.s=0 or 1), the lookup table L.sub.t may be used to lookup (or obtain or identify) the corresponding elliptic curve point Y(V, {x.sub.s: s ∈ P.sub.t}). For example, the lookup table L.sub.t may be indexed so that, for an input represented by a value with |P.sub.t|-bit binary representation

[00002]$x_{p_{t,.Math.P_t.Math.-1}}{x}_{p_{t,.Math.P_t.Math.-2}}.Math.x_{p_{t,1}}{x}_{p_{t,0}},$

the lookup table L.sub.t maps that input value to the elliptic curve point Y(V, {x.sub.s: s ∈ P.sub.t}). Alternatively, the lookup table L.sub.t may be indexed so that, for an input value of E.sub.s∈P.sub.t 2.sup.sx.sub.s, the lookup table L.sub.t maps that input value to the elliptic curve point Y(V,{x.sub.s:s ∈ P.sub.t}). It will be appreciated that the lookup table L.sub.t may be indexed or configured in other ways too.

[0115] Based on the above, the elliptic curve point kV may then be determined as kV=Σ.sub.t=0.sup.T−1Y (V, {b.sub.s:s ∈ P.sub.t}), i.e. as Σ.sub.t=0.sup.T−1 l.sub.t, where l.sub.t is the point of the elliptic curve that corresponds, in lookup table L.sub.t, to the option for assigning to the |P.sub.t| bit positions s ∈ P.sub.t the corresponding bit value b.sub.s.

[0116] For example, suppose R=256, T=64 and, for t=0,1, . . . , 63, P.sub.t={4t+3,4t+2,4t+1,4t}, i.e. for t=0,1, . . . , 63 and s=0,1,2,3, p.sub.t,s=4t+s. In this example, k's binary representation may be viewed as a concatenation of 64 4-bit blocks, each of those blocks representing a 4-bit value k.sub.t ∈ {0,1,2, . . . , 15} (for t=0,1, . . . ,63), so that k=k.sub.632.sup.252+k.sub.622.sup.248+ . . . +k.sub.12.sup.4+k.sub.02.sup.0. The lookup table L.sub.t (t=0,1, . . . , 63) may then be generated (or configured) to map the 16 possible values for k.sub.t to the respective points 2.sup.4tk.sub.tV. Then kV=Σ.sub.t=0.sup.T−1 l.sub.t, where l.sub.t is the point of the elliptic curve that corresponds, in lookup table L.sub.t, to k.sub.t, i.e. the option for assigning to the |P.sub.t| bit positions s ∈ P.sub.t the corresponding bit value b.sub.s.

[0117] It will be appreciated that, whilst the above example partitions the bit positions into equal size groups of bit positions (i.e. each group having 4 bit positions), that this is not necessary. Some embodiments may impose a minimum and/or a maximum size to each group of bit positions.

[0118] Likewise, it will be appreciated that, whilst the above example partitions the bit positions into groups of consecutive bit positions, that this is also not necessary, i.e. the bit positions in a group need not be consecutive.

[0119] In some embodiments, the partition may be randomly determined when the lookup tables L.sub.t (t=0,1, . . . , T−1) are generated (subject, potentially, to minimum and/or maximum thresholds for the size of each partition P.sub.t).

[0120] In some embodiments, there may be a minimum threshold for the number T of groups of bit positions, with the groups (and possibly the sizes of the groups) being determined accordingly so as to meet (at least) this minimum threshold for the number T.

[0121] As discussed in section 2 above, in some embodiments, it may be desirable to actually calculate the point (kμ)V for some predetermined non-negative integer μ which is to remain a secret. In this case, Y(V, {x.sub.s: s ∈ P.sub.t}) may be defined differently as Y(V, {x.sub.s: s ∈ P.sub.t})=(μ Σ.sub.s∈P.sub.t 2.sup.sx.sub.s)V . The lookup tables L.sub.t (t=0,1, . . . , T−1) may then be generated according to this alternative definition of Y(V, {x.sub.s: s ∈ P.sub.t}).

[0122] As discussed in section 2 above, in some embodiments, it may be desirable to actually calculate the point (k+μ)V for some predetermined non-negative R-bit integer μ which is to remain a secret. The values of μ's bits are {acute over (b)}.sub.r (r=0,1, . . . , R−1) where {acute over (b)}.sub.r=0 or 1 and {acute over (b)}.sub.r is the value for bit position r, so that μ=Σ.sub.r=0.sup.R−1 2.sup.r{acute over (b)}.sub.r. In this case, Y(V, {x.sub.s: s ∈ P.sub.t}) may be defined differently as Y (V, {x.sub.s: s ∈ P.sub.t})=(Σ.sub.s∈P.sub.t 2.sup.sx.sub.s)V+(Σ.sub.s∈P.sub.t 2{acute over (b)}.sub.s)V. The lookup tables L.sub.t (t=0,1, . . . , T−1) may then be generated according to this alternative definition of Y (V, {x.sub.s: s ∈ P.sub.t}).

[0123] As discussed in section 2 above, in some embodiments, it may be desirable to actually calculate the point k (V+M) for some predetermined elliptic curve point M which is to remain a secret. In this case, Y (V, {x.sub.s: s ∈ P.sub.t}) may be defined differently as Y(V,{x.sub.s:s ∈ P.sub.t})=(Σ.sub.s∈P.sub.t 2.sup.sx.sub.s)V+(Σ.sub.s∈P.sub.t 2.sup.s x.sub.s)M . The lookup tables L.sub.t (t=0,1, . . . , T−1) may then be generated according to this alternative definition of Y (V, {x.sub.s: s ∈ P.sub.t}).

[0124] As discussed in section 2 above, in some embodiments, it may be desirable to actually calculate the point kμV+M for some predetermined elliptic curve point M and some predetermined non-negative integer μ which are to remain secret. In this case, Y(V , {x.sub.s: s ∈ P.sub.t}) may be defined differently as Y (V, {x.sub.s: s ∈ P.sub.t})=(μ Σ.sub.s∈P.sub.t 2.sup.ss.sub.s)V+M. The lookup tables L.sub.t (t=0,1, . . . , T−1) may then be generated according to this alternative definition of Y (V, {x.sub.s: s ∈ P.sub.t}).

[0125] Based on the above, FIG. 2 is flow diagram illustrating a method 200 for performing an elliptic curve cryptographic process 220. The method 200 may be performed, for example, by the computer system 100 of FIG. 1 (e.g. by execution of a computer program by the processor 108). The elliptic curve cryptographic process 220 may, for example, be any of the above-discussed elliptic curve cryptographic processes, such as shared secret establishment, encryption, decryption, digital signature generation and digital signature verification, although it will be appreciated that the elliptic curve cryptographic process 220 could be any other the elliptic curve cryptographic process and/or may be a different algorithm/protocol than the specific examples set out above for shared secret establishment, encryption, decryption, digital signature generation and digital signature verification.

[0126] In general, the elliptic curve cryptographic process 220 generates output data based on input data. The elliptic curve cryptographic process 220 is based on an elliptic curve over a finite field (as has been discussed above). The generation of the output data comprises (amongst other operations/calculations) generating, based on a predetermined point V of the elliptic curve and a positive R-bit integer k, a first point of the elliptic curve that is based, at least in part, on the point kV of the elliptic curve. In some embodiments, the first point may be the point kV. In other embodiments, the first point may be related to, or based on, the point kV, such as: the point (kμ)V for some predetermined non-negative integer μ; the point (k+μ)V for some predetermined non-negative R-bit integer μ; the point k(V+M) for some predetermined elliptic curve point M; the point kμV+M for some predetermined elliptic curve point M; some combination of two or more of these; etc.

[0127] For example: [0128] (a) If the elliptic curve cryptographic process 220 is the example of shared secret establishment discussed above (i.e. Example 1), as performed by Alice, then (i) the input data may comprise Bob's public key Q.sub.B; (ii) the output data may comprise p.sub.x, where (p.sub.x, p.sub.y)=d.sub.AQ.sub.B; and (iii) generation of the output data involves using/determining the point d.sub.AQ.sub.B based on the point Q.sub.B and the positive integer d.sub.A. [0129] (b) If the elliptic curve cryptographic process 220 is the example of encryption discussed above (i.e. Example 2), as performed by Alice, then (i) the input data may comprise the message m and Bob's public key Q.sub.B; (ii) the output data may comprise the point W and the encrypted message c=E(m, k.sub.E); and (iii) generation of the output data involves using/determining the point W=rG based on the point G and the positive integer r and/or using/determining the point P=r Q.sub.B based on the point Q.sub.B and the positive integer r. [0130] (c) If the elliptic curve cryptographic process 220 is the example of digital signature generation discussed above (i.e. Example 3), as performed by Alice, then (i) the input data may comprise the message m; (ii) the output data may comprise the signature (r, s); and (iii) generation of the output data involves using/determining the point kG based on the point G and the positive integer k. [0131] (d) If the elliptic curve cryptographic process 220 is the example of digital signature verification discussed above (i.e. Example 3), as performed by Bob, then (i) the input data may comprise the signature (r, s), the message m, and Alice's public key Q.sub.A; (ii) the output data may comprise an indication of whether or not the signature (r, s) is valid, i.e. whether the signature (r, s) corresponds to the message m and Alice's public key Q.sub.A; and (iii) generation of the output data involves using/determining the point nQ.sub.A based on the point Q.sub.A and the positive integer n and/or using/determining the point u.sub.1G based on the point G and the positive integer u.sub.1 and/or using/determining the point u.sub.2Q.sub.A based on the point Q.sub.A and the positive integer u.sub.2.

[0132] The above applies likewise to the modified versions of these cryptographic processes that use masked curved points and/or masked private keys, as has been discussed above.

[0133] At a step 202, the method 200 comprises storing, based on (or according to) the partition of the R bit positions for k into the T groups of bit positions P.sub.t (t=0,1, . . . , T−1) having |P.sub.t| bit positions respectively (namely p.sub.t,s (s=0,1, . . . , |P.sub.t|−1) for each group P.sub.t (t=0,1, . . . , T−1)), the corresponding lookup table L.sub.t. As discussed above L.sub.t has, for each of the 2.sup.|P.sup.t.sup.| possible options for assigning respective bit value x.sub.s to the |P.sub.t| bit positions p.sub.t,s of P.sub.t=0,1, . . . , |P.sub.t|−1 and x.sub.s=0 or 1) the corresponding point of the elliptic curve (Σ.sub.s∈P.sub.t 2.sup.sx.sub.s)V.

[0134] In some embodiments, the step 202 involves the computer system 100 generating the lookup tables L.sub.t (t=0,1, . . . , T−1) and then storing those generated tables. For example, if the point V is to be the generator point G for the elliptic curve (as for examples (b), (c) and (d) above), then the computer system 100 may generate the lookup tables L.sub.t (t=0,1, . . . , T−1) once the computer system 100 knows which elliptic curve and generator 0 point G to use (e.g. as established by the domain parameters). As another example, if the point V is to be the public key Q.sub.A for Alice or Q.sub.B for Bob (as for examples (a), (b) and (e) above), then the computer system 100 may generate the lookup tables L.sub.t (t=0,1, . . . , T−1) once the computer system 100 knows which elliptic curve to use (e.g. as established by the domain parameters) as well as that public key. As mentioned, the generation of the lookup tables L.sub.t (t=0,1, . . . , T−1) may also comprise determining the partition to use for the R bit positions for k (e.g. as a randomly generated partition); alternatively, the partition may be predetermined.

[0135] In other embodiments, the step 202 may involve the computer system 100 receiving the lookup tables L.sub.t (t=0,1, . . . , T−1) and then storing those received lookup tables. For example, Alice or Bob may generate the lookup tables based on the point V being their respective public key Q.sub.A or Q.sub.B and then provide the generated lookup tables to the computer system 100 so that the computer system 100 can use those tables (and therefore the public key) as part of the cryptographic process. In some embodiments, the generation of the lookup tables L.sub.t (t=0,1, . . . , T−1) may be performed by a third party, different from the entity (or entities) involved in, or ultimately performing, some or all of the cryptographic process—e.g. as in the modified versions of the cryptographic processes that use masked curved points and/or masked private keys, as has been discussed above.

[0136] It will be appreciated that other mechanisms for generating and/or storing the lookup tables L.sub.t (t=0,1, . . . , T−1) could be used.

[0137] At a step 204, the method 200 comprises obtaining the input data for the elliptic curve cryptographic process 220. Given the variety of elliptic curve cryptographic processes 220 (e.g. the examples (a)-(e) set out above), it will be appreciated the input data may be obtained in a variety of ways and may be intended for a variety of purposes.

[0138] At a step 206, the method 200 comprises obtaining (or calculating or generating) the positive integer k. As discussed above, the R bits of k have respective values b.sub.r (r=0,1, . . . , R−1) so that k=Σ.sub.r=0.sup.R−1 2.sup.rb.sub.r. Given the variety of elliptic curve cryptographic processes 220 (e.g. the examples (a)-(d) set out above), it will be appreciated k may be obtained in a variety of ways and may be intended for a variety of purposes.

[0139] At a step 208, the method 200 comprises using the lookup tables L.sub.t (t=0,1, . . . , T−1) as has been described above to generate the first point (e.g. kV in some embodiments) as Σ.sub.t=0.sup.T−1 l.sub.t, where l.sub.t is the point of the elliptic curve that corresponds, in lookup table L.sub.t, to the option for assigning bit value b.sub.p.sub.t,s to bit position p.sub.t,s (for each s=0,1, . . . , |P.sub.t|−1), i.e. where l.sub.t is the point of the elliptic curve that corresponds, in lookup table L.sub.t, to the option for assigning to the |P.sub.t| bit positions s ∈ P.sub.t the corresponding bit value b.sub.s.

[0140] At a step 210, the method 200 comprises using the generated first point to generate the output data for the elliptic curve cryptographic processes 220. Given the variety of elliptic curve cryptographic processes 220 (e.g. the examples (a)-(e) set out above), it will be appreciated the output data may be generated in a variety of ways.

[0141] Finally, at a step 212, the method 202 may comprise using and/or providing the generate output data, depending on the intended purpose of the output data, e.g. Alice and Bob using their shared secret to establish a shared secret key in example (a) above; Alice providing the point W and the encrypted message c=E(m,k.sub.E) to Bob in example (b) above; Alice providing the signature (r,s) to Bob in example (c) above; and Bob determining whether or not to trust the signed message based on the verification result in example (d) above.

[0142] Use of the above-described method to perform elliptic curve scalar multiplication via lookup tables provides several technical advantages, including: [0143] Generating the first point (e.g. kV in some embodiments) as Σ.sub.t=0.sup.T−1 l.sub.t involves performing T lookups (one from each lookup table L.sub.t (t=0,1, . . . , T−1)) and T−1 elliptic curve point additions using those looked-up points. This means that performance of elliptic curve scalar multiplication via lookup tables (which forms the basis of many white-box implementations of cryptographic processes) can be achieved in a memory efficient manner, especially when the field F is a large field (e.g. GF(2.sup.256) or larger). For example, if F is GF(2.sup.256) and if one were to use the previous example in which R=256, T=64 and, for t=0,1, . . . , 63, P.sub.t={4t+3,4t+2,4t+1,4t}, then each lookup table has 16 lookup values/points, each of which is a pair (x,y) where x, y ∈ GF(2.sup.256), so that each lookup value/point can be represented by 512 bits. Thus, each lookup table may use 16×512=8,192 bits, so that in total, the set of T lookup tables (L.sub.t (t=0,1, . . . , T−1)) may use just 64×8,192=524,288 bits, i.e. 64 KB. [0144] As generating the first point (e.g. kV in some embodiments) as Σ.sub.t=0.sup.T−1 l.sub.t involves performing T lookups (one from each lookup table L.sub.t (t=0,1, . . . , T−1)) and T−1 elliptic curve point additions using those looked-up points, regardless of the value of k, the elliptic curve scalar multiplication can be performed both quickly and in substantially constant time (independent of k), thereby making timing attacks more difficult for attackers. [0145] Use of the lookup tables L.sub.t (t=0,1, . . . , T−1)) inherently hides/embeds the underlying elliptic curve point V so that it is difficult for an attacker to identify the underlying elliptic curve point V. Even if security of the cryptographic process itself does not rely on secrecy of the underlying elliptic curve point V (e.g. if the point V is the generator point G or a public key), use of the lookup tables to implement the underlying elliptic curve point V helps add an extra later of security that makes it more difficult for an attacker. For example, Alice and Bob may need to undertake shared secret establishment, with Alice being in charge of the process—Alice could send Bob a set of lookup tables so as to perform elliptic curve scalar multiplication based on underlying point G (so that Bob can generate a private and public key pair without knowing the point G) and/or a set of lookup tables so as to perform elliptic curve scalar multiplication based on underlying point Q.sub.A (so that Bob can use Alice's public key Q.sub.A without knowing the point Q.sub.A). [0146] Moreover, as discussed above, use of the lookup tables L.sub.t (t=0,1, . . . , T−1)) can be used to hide/embed/use further secret data, e.g. calculating the point (kμ)V for some predetermined non-negative integer μ which is to remain a secret; calculating the point (k+μ)V for some predetermined non-negative R-bit integer μ which is to remain a secret; calculating the point kV+M or k(V+M) or kμV+M for some predetermined elliptic curve point M and predetermined non-negative integer μ which is/are to remain a secret. In this way, further security may be achieved for the implementation of the elliptic curve cryptographic process, since the attacker is not able to leverage the data available in the absence of knowledge of the secret data. Additionally, as discussed above, this enables implementations that do not store an entity's actual private key but, instead, store or use an obfuscated version of the private key.

4—Modifications

[0147] It will be appreciated that the methods described have been shown as individual steps carried out in a specific order. However, the skilled person will appreciate that these steps may be combined or carried out in a different order whilst still achieving the desired result.

[0148] It will be appreciated that embodiments of the invention may be implemented using a variety of different information processing systems. In particular, although the figures and the discussion thereof provide an exemplary computing system and methods, these are presented merely to provide a useful reference in discussing various aspects of the invention. Embodiments of the invention may be carried out on any suitable data processing device, such as a personal computer, laptop, personal digital assistant, mobile telephone, set top box, television, server computer, etc. Of course, the description of the systems and methods has been simplified for purposes of discussion, and they are just one of many different types of system and method that may be used for embodiments of the invention. It will be appreciated that the boundaries between logic blocks are merely illustrative and that alternative embodiments may merge logic blocks or elements, or may impose an alternate decomposition of functionality upon various logic blocks or elements.

[0149] It will be appreciated that the above-mentioned functionality may be implemented as one or more corresponding modules as hardware and/or software. For example, the above-mentioned functionality may be implemented as one or more software components for execution by a processor of the system. Alternatively, the above-mentioned functionality may be implemented as hardware, such as on one or more field-programmable-gate-arrays (FPGAs), and/or one or more application-specific-integrated-circuits (ASICs), and/or one or more digital-signal-processors (DSPs), and/or one or more graphical processing units (CPUs), and/or other hardware arrangements. Method steps implemented in flowcharts contained herein, or as described above, may each be implemented by corresponding respective modules; multiple method steps implemented in flowcharts contained herein, or as described above, may be implemented together by a single module.

[0150] It will be appreciated that, insofar as embodiments of the invention are implemented by a computer program, then one or more storage media and/or one or more transmission media storing or carrying the computer program form aspects of the invention. The computer program may have one or more program instructions, or program code, which, when executed by one or more processors (or one or more computers), carries out an embodiment of the invention. The term “program” as used herein, may be a sequence of instructions designed for execution on a computer system, and may include a subroutine, a function, a procedure, a module, an object method, an object implementation, an executable application, an applet, a servlet, source code, object code, byte code, a shared library, a dynamic linked library, and/or other sequences of instructions designed for execution on a computer system. The storage medium may be a magnetic disc (such as a hard drive or a floppy disc), an optical disc (such as a CD-ROM, a DVD-ROM or a BluRay disc), or a memory (such as a ROM, a RAM, EEPROM, EPROM, Flash memory or a portable/removable memory device), etc. The transmission medium may be a communications signal, a data broadcast, a communications link between two or more computers, etc.