# US 10,484,173 B2 · X-only generic mapping function for PACE protocol

> Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt

- Number: US 10,484,173 B2
- Document ID: US10484173B2
- Status: Granted
- Kind: B2
- Application number: 15/397,462
- Filed: 2017-01-03
- Published: 2018-07-05
- Granted: 2019-11-19
- Earliest claimed: 2017-01-03
- Assignees: NXP B.V.
- Applicants: NXP B.V.
- Inventors: Bruce Murray
- Web page: https://patentgrep.com/patent/US10484173B2

## CPC

- H04L 9/3013: {involving the discrete logarithm problem, e.g. ElGamal or Diffie-Hellman systems}
- G06F 7/725: {over elliptic curves}
- H04L 9/0841: {involving Diffie-Hellman or related key agreement protocols}
- H04L 9/0844: {with user authentication or key authentication, e.g. ElGamal, MTI, MQV-Menezes-Qu-Vanstone protocol or Diffie-Hellman protocols using implicitly-certified keys}
- H04L 9/14: using a plurality of keys or algorithms
- H04L 9/3066: {involving algebraic varieties, e.g. elliptic or hyper-elliptic curves}
- H04L: TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION (arrangements common to telegraphic and telephonic communication H04M)
- G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N)

## Abstract

A method of calculating the x-coordinate(xM) 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 (xS,yS) on an elliptic curve and H is a point (xH,yH) on the elliptic curve, including: computing V=yS2 based upon the elliptic curve and xS; computing W=yH2 based upon the elliptic curve and xH; computing U=sqrt(W·V)mod p, where p is a large prime number; choosing U′=U or U′=p−U such that U′ based upon a characteristic agreed upon by the parties to the EC-DHKF; computing xM based upon V, W, U′, xS, xH, and p.

## Claims

### Claim 1

A method of calculating an x-coordinate (xM) of a point mapping in an elliptic curve Diffie-Hellman key exchange protocol (EC-DHKE) between two parties, wherein the point mapping is defined as sG+H, where sG is a point (xs,ys) on an elliptic curve and H is a point (xH,yH) on the elliptic curve, comprising:
computing V=ys2 based upon the elliptic curve and xs;
computing W=yH2 based upon the elliptic curve and xH;
computing U=sqrt(W·V) mod p, where p is a large prime number, wherein sqrt stands for square root;
choosing U′=U or U′=p−U such that U′ is based upon a characteristic agreed upon by the parties to the EC-DHKE;
computing xM based upon V, W, U′, xs, xH, and p, wherein the method allows elliptic curve Diffie-Hellmann key exchange for an x-coordinate only implementation in order to establish a connection between the two parties.

### Claim 2 (depends on 1)

The method of claim 1, wherein the elliptic curve is a Montgomery curve of the form y2=x3+Ax2+x mod p.

### Claim 3 (depends on 2)

The method of claim 2, wherein V=xS3+A*xS2+xS mod p.

### Claim 4 (depends on 3)

The method of claim 3, wherein W=xH3+A*xH2+xH mod p.

### Claim 5 (depends on 1)

The method of claim 1, wherein xM=((V+W−2U′)/(xS−xH)2)−A−xS−xH mod p.

### Claim 6 (depends on 1)

The method of claim 1, wherein the elliptic curve is a Weierstraß curve of the form y2=x3+Ax+B mod p.

### Claim 7 (depends on 6)

The method of claim 6, wherein V=xS3+A*xS+B mod p.

### Claim 8 (depends on 7)

The method of claim 7, wherein W=xH3+A*xH+B mod p.

### Claim 9 (depends on 6)

The method of claim 6, wherein xM=((V+W−2U′)/(xS−xH)2)−xS−xH mod p.

### Claim 10 (depends on 1)

The method of claim 1, wherein the elliptic curve is an Edwards curve of the form y2+x2=c2(1+dx2 y2) where c and d are scalars.

### Claim 11 (depends on 1)

The method of claim 1, wherein the elliptic curve is a twisted Edwards curve of the form ax2+y2=1+dx2 y2 where a and d are scalars.

### Claim 12 (depends on 1)

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

### Claim 13

A non-transitory machine-readable storage medium encoded with instructions for calculating an x-coordinate (xM) of a point mapping in an elliptic curve Diffie-Hellman key exchange protocol (EC-DHKE) between two parties, wherein the point mapping is defined as sG+H, where sG is a point (xs,ys) on an elliptic curve and H is a point (xH,yH) on the elliptic curve, comprising:
instructions for computing V=ys2 based upon the elliptic curve and xs;
instructions for computing W=yH2 based upon the elliptic curve and xH;
instructions for computing U=sqrt(W·V) mod p, where p is a large prime number, wherein sqrt stands for square root;
instructions for choosing U′=U or U′=p−U such that U′ is based upon a characteristic agreed upon by the parties to the EC-DHKE;
instructions for computing xM based upon V, W, U′, xs, xH, and p, wherein executing the instructions allows elliptic curve Diffie-Hellmann key exchange for an x-coordinate only implementation in order to establish a connection between the two parties.

### Claim 14 (depends on 13)

The non-transitory machine-readable storage medium of claim 13, wherein the elliptic curve is a Montgomery curve of the form y2=x3+Ax2+x mod p.

### Claim 15 (depends on 14)

The non-transitory machine-readable storage medium of claim 14, wherein V=xS3+A*xS2+xS mod p.

### Claim 16 (depends on 15)

The non-transitory machine-readable storage medium of claim 15, wherein W=xH3+A*xH2+xH mod p.

### Claim 17 (depends on 13)

The non-transitory machine-readable storage medium of claim 13, wherein xM=((V+W−2U′)/(xS−xH)2)−A−xS−xH mod p.

### Claim 18 (depends on 13)

The non-transitory machine-readable storage medium of claim 13, wherein the elliptic curve is a Weierstraß curve of the form y2=x3+Ax+B mod p.

### Claim 19 (depends on 18)

The non-transitory machine-readable storage medium of claim 18, wherein V=xS3+A*xS+B mod p.

### Claim 20 (depends on 19)

The non-transitory machine-readable storage medium of claim 19, wherein W=xH3+A*xH+B mod p.

### Claim 21 (depends on 18)

The non-transitory machine-readable storage medium of claim 18, wherein xM=((V+W−2U′)/(xS−xH)2)−xS−xH mod p.

### Claim 22 (depends on 13)

The non-transitory machine-readable storage medium of claim 13, wherein the elliptic curve is an Edwards curve of the form y2+x2=c2(1+dx2 y2) where c and d are scalars.

### Claim 23 (depends on 13)

The non-transitory machine-readable storage medium of claim 13, wherein the elliptic curve is a twisted Edwards curve of the form ax2+y2=1+dx2 y2 where a and d are scalars.

### Claim 24 (depends on 13)

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