X-ONLY GENERIC MAPPING FUNCTION FOR PACE PROTOCOL

Abstract

A method of calculating the x-coordinate(x.sub.M) of a point mapping in an elliptic curve Diffie-Hellman key exchange protocol (EC-DHKF), wherein the point mapping is defined as sG+H, where sG is a point (x.sub.S,y.sub.S) on an elliptic curve and H is a point (x.sub.H,y.sub.H) on the elliptic curve, including: computing V=y.sub.S.sup.2 based upon the elliptic curve and x.sub.S; computing W=y.sub.H.sup.2 based upon the elliptic curve and x.sub.H; computing U=sqrt(W.Math.V) mod p, where p is a large prime number; choosing U=U or U=pU such that U based upon a characteristic agreed upon by the parties to the EC-DHKF; computing x based upon V, W, U, x.sub.S, x.sub.H, and p.

Claims

1. A method of calculating the x-coordinate(x.sub.M) of a point mapping in an elliptic curve Diffie-Hellman key exchange protocol (EC-DHKF), wherein the point mapping is defined as sG+H, where sG is a point (x.sub.S,y.sub.S) on an elliptic curve and H is a point (x.sub.H,y.sub.H) on the elliptic curve, comprising: computing V=y.sub.s.sup.2 based upon the elliptic curve and x.sub.S; computing W=y.sub.H.sup.2 based upon the elliptic curve and x.sub.H; computing U=sqrt(W.Math.V) mod p, where p is a large prime number; choosing U=U or U=pU such that U based upon a characteristic agreed upon by the parties to the EC-DHKF; computing x.sub.M based upon V, W, U, x.sub.S, x.sub.H, and p.

2. The method of claim 1, wherein the elliptic curve is a Montgomery curve of the form y.sup.2=x.sup.3+Ax.sup.2+x mod p.

3. The method of claim 2, wherein V=x.sub.S.sup.3+A*x.sub.S.sup.2+X.sub.S mod p.

4. The method of claim 3, wherein W=x.sub.H.sup.3+A*x.sub.H.sup.2+x.sub.H mod p.

5. The method of claim 1, wherein x.sub.M=((V+W2U)/(x.sub.Sx.sub.H).sup.2)Ax.sub.Sx.sub.H mod p.

6. The method of claim 1, wherein the elliptic curve is a Weierstra curve of the form y.sup.2=x.sup.3+Ax+B mod p.

7. The method of claim 6, wherein V=x.sub.S.sup.3+A*x.sub.S+B mod p.

8. The method of claim 7, wherein W=x.sub.H.sup.3+A*x.sub.H+B mod p.

9. The method of claim 6, wherein x.sub.M=((V+W2U)/(x.sub.Sx.sub.H).sup.2)x.sub.Sx.sub.H mod p.

10. The method of claim 1, wherein the elliptic curve is an Edwards curve of the form y.sup.2+x.sup.2=c.sup.2(1+dx.sup.2 y.sup.2) where c and d are scalars.

11. The method of claim 1, wherein the elliptic curve is a twisted Edwards curve of the form ax.sup.2+y.sup.2=1+dx.sup.2 y.sup.2 where a and d are scalars.

12. The method of claim 1, wherein the characteristic agreed upon by the parties includes one of: whether the least significant bit of U or pU is zero; whether the least significant bit of U or pU is one; which of U or pU when written as a positive integer is closer to zero; which of U or pU when written as a positive integer is further from zero; and which of U or pU is a quadratic residue.

13. A non-transitory machine-readable storage medium encoded with instructions for calculating the x-coordinate(x.sub.M) of a point mapping in an elliptic curve Diffie-Hellman key exchange protocol (EC-DHKF), wherein the point mapping is defined as sG+H, where sG is a point (x.sub.S,y.sub.S) on an elliptic curve and H is a point (x.sub.H,y.sub.H) on the elliptic curve, comprising: instructions for computing V=y.sub.S.sup.2 based upon the elliptic curve and x.sub.S; instructions for computing W=y.sub.H.sup.2 based upon the elliptic curve and x.sub.H; instructions for computing U=sqrt(W.Math.V) mod p, where p is a large prime number; instructions for choosing U=U or U=pU such that U based upon a characteristic agreed upon by the parties to the EC-DHKF; instructions for computing x based upon V, W, U, x.sub.S, x.sub.H, and p.

14. The non-transitory machine-readable storage medium of claim 13, wherein the elliptic curve is a Montgomery curve of the form y.sup.2=x.sup.3+Ax.sup.2+x mod p.

15. The non-transitory machine-readable storage medium of claim 14, wherein V=x.sub.S.sup.3+A*x.sub.S.sup.2+x.sub.S mod p.

16. The non-transitory machine-readable storage medium of claim 15, wherein W=x.sub.H.sup.3+A*x.sub.H.sup.2+x.sub.H mod p.

17. The non-transitory machine-readable storage medium of claim 13, wherein x.sub.M=((V+W2U)/(x.sub.Sx.sub.H).sup.2)Ax.sub.Sx.sub.H mod p.

18. The non-transitory machine-readable storage medium of claim 13, wherein the elliptic curve is a Weierstra curve of the form y.sup.2=x.sup.3+Ax+B mod p.

19. The non-transitory machine-readable storage medium of claim 18, wherein V=x.sub.S.sup.3+A*x.sub.S+B mod p.

20. The non-transitory machine-readable storage medium of claim 19, wherein W=x.sub.H.sup.3+A*x.sub.H+B mod p.

21. The non-transitory machine-readable storage medium of claim 18, wherein x.sub.M=((V+W2U)/(x.sub.Sx.sub.H).sup.2)x.sub.Sx.sub.H mod p.

22. The non-transitory machine-readable storage medium of claim 1, wherein the elliptic curve is an Edwards curve of the form y.sup.2+x.sup.2=c.sup.2(1+dx.sup.2 y.sup.2) where c and d are scalars.

23. The non-transitory machine-readable storage medium of claim 1, wherein the elliptic curve is a twisted Edwards curve of the form ax.sup.2+y.sup.2=1+dx.sup.2 y.sup.2 where a and d are scalars.

24. The non-transitory machine-readable storage medium of claim 1, wherein the characteristic agreed upon by the parties includes one of: whether the least significant bit of U or pU is zero; whether the least significant bit of U or pU is one; which of U or pU when written as a positive integer is closer to zero; which of U or pU when written as a positive integer is further from zero; and which of U or pU is a quadratic residue.

Description

BRIEF DESCRIPTION OF THE DRAWINGS

[0022] In order to better understand various exemplary embodiments, reference is made to the accompanying drawings, wherein:

[0023] FIG. 1 illustrates the PACE protocol using elliptic curve cryptography (ECC).

[0024] To facilitate understanding, identical reference numerals have been used to designate elements having substantially the same or similar structure and/or substantially the same or similar function.

DETAILED DESCRIPTION

[0025] The description and drawings illustrate the principles of the invention. It will thus be appreciated that those skilled in the art will be able to devise various arrangements that, although not explicitly described or shown herein, embody the principles of the invention and are included within its scope. Furthermore, all examples recited herein are principally intended expressly to be for pedagogical purposes to aid the reader in understanding the principles of the invention and the concepts contributed by the inventor(s) to furthering the art, and are to be construed as being without limitation to such specifically recited examples and conditions. Additionally, the term, or, as used herein, refers to a non-exclusive or (i e , and/or), unless otherwise indicated (e.g., or else or or in the alternative). Also, the various embodiments described herein are not necessarily mutually exclusive, as some embodiments can be combined with one or more other embodiments to form new embodiments.

[0026] Embodiments are described below that include a mapping function that may be used with the PACE that performs only the x-coordinate computations for the Diffie-Hellmann operations in the ECC-based implementation of the PACE protocol. Although embodiments described herein use a Montgomery curve, the embodiments may be applied to other implementations of the PACE protocol using other curves. Also, the embodiments described herein may be used for x-coordinate only computations for other types of elliptic curve based exchange protocols.

[0027] Because the core of the generic mapping is the calculation of G.sub.map=sG+H, a point addition operation is required that would normally require knowledge of the y-coordinates of the points being added. However, many systems are designed/specified to perform EC-DHKF using x-coordinates only, and frequently exploit various implementation optimizations in doing so. These optimizations reduce the computational requirements to perform the EC-DHKF. This raises the question of whether a generic mapping may be implemented efficiently when using such systems.

[0028] Embodiments are disclosed below that show how to create an agreed x-coordinate out of a mapping function that may be used as the basis of the second EC-DHKF using Gmap as the basepoint, and which is computed on x-only inputs from the scalar multiplication sG and the x-coordinate agreement scheme resulting in point H.

[0029] Accordingly, H is the point (x.sub.H, y.sub.H), and S=sG is the point (x.sub.S, y.sub.S). It is important to note that y.sub.H and y.sub.S are not unambiguously known, and only x.sub.H and x.sub.S are supplied as inputs to the map function, the desired output being an agreed value for x.sub.MAP.

[0030] Knowing H and S only up to the uncertainty results in two possible x-coordinates that may be produced for a sum point. As a result, an unambiguous choice may be made by an agreed-upon convention.

[0031] With the x-coordinates of S and H, the two possible results for the x-coordinates of a sum point are the values for the x-coordinate of S+H, S+(H), (S)+H, or (S)+(H). These correspond to the x-coordinates corresponding to (S+H) and (SH).

[0032] Because either of these results could have validly arisen from a full generic mapping function, from a security point of view it does not matter whether the x-coordinate of S+H or SH is used as the basepoint-x for the second EC-DHKF, but it is important that there is a convention which both sides agree on when the protocol executes.

[0033] Accordingly, a generic map-to-x-coordinate function may be defined using Montgomery curve y.sup.2=x.sup.3+Ax.sup.2+x mod p as follows. If (x.sub.S, y.sub.S) and (x.sub.H, y.sub.H) are coordinates of S and H respectively, then the x-coordinates of the possible map points are given by the equation:

x=((y.sub.Sy.sub.H).sup.2/(x.sub.Sx.sub.H).sup.2)Ax.sub.Sx.sub.H mod p, (1)

where A is from the curve equation y.sup.2=x.sup.3+Ax.sup.2+x (e.g., on Dan Bernstein's Curve-25519, A=486662).

[0034] Because the purpose of this mapping function is to accommodate the situation where y.sub.S and y.sub.H are not known unambiguously and because they may have been computed using an optimized x-only Diffie-Hellmann function, the ambiguity that may arise in the selection of either the x-coordinate of S+H or SH needs to be resolved.

[0035] In order to resolve which x-coordinate to choose, expand (y.sub.Sy.sub.H).sup.2=y.sub.S.sup.22 y.sub.S*y.sub.H+y.sub.H.sup.2 and substitute for y.sub.S.sup.2 and y.sub.H.sup.2 using the curve equation, leaving only the term 2 y.sub.S*y.sub.H to deal with; a value for this term may be derived with a single square root operation in the field because,

y.sub.S*y.sub.H=sqrt(y.sub.S.sup.2*y.sub.H.sup.2)=sqrt((x.sub.S.sup.3+A*x.sub.S.sup.2+x.sub.S)*(x.sub.H.sup.3+A*x.sub.H.sup.2+x.sub.H))

where the computation of a square root depends on the exact congruence of the prime p defining the underlying field. The simplest cases for such a computation are:

[0036] when p=3 mod 4, sqrt(z) mod p is computable as z.sup.(p+1)/4 mod p since, if z is a quadratic residue mod p, then z.sup.(p1)/2=1 mod p, and z.sup.(p+1)/2=z mod p and since p+1 is divisible by 4 it follows that z.sup.(p+1)/4 mod p=sqrt(z); and

[0037] when p=1 mod 4 and p=5 mod 8, sqrt(z) is computable using Atkin's square root algorithm, which is a constant-time computation using with one exponentiation and four modular multiplications; this case covers the commonly used Curve22519 specified by Dan Bernstein.

[0038] Other cases require a troublesome probabilistic algorithms for finding square roots in Galois field, and these approaches are troublesome because they have the potential to leak timing information about the value of the calculated square root (e.g., recall that confidentiality of the ephemeral basepoint used in the second exchange phase is a key security objective of the PACE protocol).

[0039] Having computed one square root

sqrt((x.sub.S.sup.3+A*x.sub.S.sup.2+x.sub.S)*(x.sub.H.sup.3+A*x.sub.H.sup.2+x.sub.H)) mod p

then the other is trivially known to be

psqrt((x.sub.S.sup.3+A*x.sub.S.sup.2+x.sub.S)*(x.sub.H.sup.3+A*x.sub.H.sup.2+x.sub.H)) mod p

and it should be clear that, because p is odd, these two roots have differing values for their least significant bit when reduced mod p.

[0040] Now a convention may be defined as to which square root to use. It might be that someone really computed y-coordinates y.sub.S and y.sub.H instead deriving the product y.sub.S*y.sub.H, in which case they need to be told to compute equation (1) with a given convention for the product y.sub.S*y.sub.H e.g. choose y.sub.S*y.sub.H or (py.sub.S*y.sub.H), for example, such that the least significant bit of the result mod p is zero.

[0041] The effect of such a sign change in equation (1) would be to change (y.sub.Sy.sub.H).sup.2 into (y.sub.S+y.sub.H).sup.2, which is how two x-coordinates can arise from the original equation defining the sum of points as a result of changing the sign of either point's y-coordinate.

[0042] Accordingly, the steps of the map function computation are as follows: [0043] 1. Compute V=x.sub.S.sup.3+A*x.sub.S.sup.2+x.sub.S mod p (i.e., calculating y.sub.S.sup.2); [0044] 2. Compute W=x.sub.H.sup.3+A*x.sub.H.sup.2+x.sub.H mod p (i.e., calculating y.sub.H.sup.2); [0045] 3. Compute U=sqrt(W*V) mod p using an algorithm which depends on the values of p mod 4 and p mod 8 (i.e., calculating y.sub.S*y.sub.H); [0046] 4. Choose U=U or pU such that U has its least significant bit set to zero (i.e., choosing the positive or negative root); and [0047] 5. Compute x.sub.M=((V+W2U)/(x.sub.Sx.sub.H).sup.2)Ax.sub.Sx.sub.H mod p.
The result of this map-to-x function is an agreed x-coordinate x.sub.M of either S+H or SH, which can then be used as the basis for the second x-only Diffie-Hellmann exchange. Alternatively, in step 4 above, U may be selected such that its least significant bit is set to one. Other agreed upon characteristics may be used as well to determine whether to choose U as U or pU. Such agreed upon characteristics should be agreed upon by the two parties using the PACE protocol. Other conventions may be used as well. For example, the value closes to or furthest from zero when the value is written as a positive integer may be chosen by agreement. Also, the square root that is the quadratic residue may be chosen. This only works when 1 is a quadratic non-residue mod p, i.e., when p=3 mod 4, because p=4k+3=>(p1)/2=2k+1 so (1)((p1)/2)=1 is the Legendre symbol of 1. However, this convention has an implementation advantage when p=3 mod 4, because if v=w.sup.2 mod p is computed using sqrt(v) by v.sup.((p+1)/4), the root automatically results, which is a quadratic residue.

[0048] An example will now be provided using the short WeierstraB curve y.sup.2=x.sup.3+Ax+B mod p. On the short Weierstra curve the addition law results in a slightly different equation for the x-coordinate of the sum of two points S and H thus

x=((y.sub.Sy.sub.H).sup.2/(x.sub.Sx.sub.H).sup.2)x.sub.Sx.sub.H mod p. (2)

The only difference being the absence of the constant term in (1); otherwise, the mapping function computation can proceed along exactly the same lines as in the Montgomery curve case.

[0049] Accordingly, the steps of the map function computation when using a short WeierstraB form curve may be defined as follows: [0050] 1. Compute V=x.sub.S.sup.3+A*x.sub.S+B mod p; [0051] 2. Compute W=x.sub.H.sup.3+A*x.sub.H+B mod p; [0052] 3. Compute U=sqrt(W*V) mod p using an algorithm which depends on the values of p mod 4 and p mod 8; [0053] 4. Choose U=U or pU such that U has its least significant bit set to zero; and [0054] 5. Compute x.sub.M=((V+W2U)/(x.sub.Sx.sub.H).sup.2)x.sub.Sx.sub.H mod p.

[0055] Again, the result of this map-to-x function is an agreed x-coordinate x.sub.M of either S+H or SH, which can then be used as the basis for the second x-only Diffie-Hellmann exchange. Alternatively, in step 4 above, U may be selected such that its least significant bit is set to one. Other agreed upon characteristics may be used as well to determine whether to choose U as U or pU. Such agreed upon characteristics should be agreed upon by the two parties using the PACE protocol as described above.

[0056] A mapping function has been described that allows the PACE protocol with generic/CAM mapping to be used in an x-only EC-Diffie-Hellmann context, using either Montgomery curves or short WeierstraB form curves. In both cases the mapping function requires one square root computation, an inversion, and a small number of modular multiplication, addition, and subtraction operations; with a suitable implementation of the inversion, constant-time execution of the mapping function is possible. Such implementation may reduce the computation required for the PACE protocol in an EC-Diffie-Hellmann context.

[0057] Other elliptic curves may be used as well. For example, an Edwards curve of the form y.sup.2+x.sup.2=c.sup.2(1+dx.sup.2 y.sup.2) where c and d are scalars may be used. Also, a twisted Edwards curve of the form ax.sup.2+y.sup.2=1+dx.sup.2 y.sup.2 where a and d are scalars may be used. These curves may be used in a manner similar to the Montgomery curve and short Weierstra curves described above using only a single coordinate.

[0058] A method according to the embodiments of the invention may be implemented on a computer as a computer implemented method. Executable code for a method according to the invention may be stored on a computer program medium. Examples of computer program media include memory devices, optical storage devices, integrated circuits, servers, online software, etc. Accordingly, key delivery systems described herein may include a computer implementing a computer program. Such system, may also include other hardware elements including storage, network interface for transmission of data with external systems as well as among elements of the key delivery systems.

[0059] In an embodiment of the invention, the computer program may include computer program code adapted to perform all the steps of a method according to the invention when the computer program is run on a computer. Preferably, the computer program is embodied on a non-transitory computer readable medium.

[0060] Any combination of specific software running on a processor to implement the embodiments of the invention, constitute a specific dedicated machine.

[0061] As used herein, the term non-transitory machine-readable storage medium will be understood to exclude a transitory propagation signal but to include all forms of volatile and non-volatile memory. Further, as used herein, the term processor will be understood to encompass a variety of devices such as microprocessors, field-programmable gate arrays (FPGAs), application-specific integrated circuits (ASICs), and other similar processing devices. When software is implemented on the processor, the combination becomes a single specific machine.

[0062] It should be appreciated by those skilled in the art that any block diagrams herein represent conceptual views of illustrative circuitry embodying the principles of the invention.

[0063] Although the various exemplary embodiments have been described in detail with particular reference to certain exemplary aspects thereof, it should be understood that the invention is capable of other embodiments and its details are capable of modifications in various obvious respects. As is readily apparent to those skilled in the art, variations and modifications can be effected while remaining within the spirit and scope of the invention. Accordingly, the foregoing disclosure, description, and figures are for illustrative purposes only and do not in any way limit the invention, which is defined only by the claims.