# US 2017/0359176 A1 · Cryptography on an elliptical curve

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

- Number: US 2017/0359176 A1
- Document ID: US20170359176A1
- Status: Published application
- Kind: A1
- Application number: 15/671,064
- Filed: 2017-08-07
- Published: 2017-12-14
- Earliest claimed: 2009-06-16
- Assignees: Morpho
- Applicants: Morpho
- Inventors: Thomas Icart; Jean-Sebastien Coron
- Web page: https://patentgrep.com/patent/US20170359176A1

## CPC

- H04L 9/30: Public key, i.e. encryption algorithm being computationally infeasible to invert or user's encryption keys not requiring secrecy
- H04L 9/005: {for timing attacks}
- H04L 9/3066: {involving algebraic varieties, e.g. elliptic or hyper-elliptic curves}
- G06F 7/725: {over elliptic curves}
- H04L 9/002: {Countermeasures against attacks on cryptographic mechanisms (network architectures or network communication protocols for protection against malicious traffic H04L63/1441)}
- 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 cryptographic calculation includes obtaining a point P(X,Y) from a parameter t on an elliptical curve Y2=f(X); and from polynomials X1(t), X2(t), X3(t) and U(t) satisfying: f(X1(t))·f(X2(t))·f(X3(t))=U(t)2 in Fq, with q=3 mod 4. Firstly a value of the parameter t is obtained. Next, the point P is determined by: (i) calculating X1=X1(t), X2=X2(t), X3=X3(t) and U=U(t); (ii) if the term f(X1)·f(X2) is a square, then testing whether the term f(X3) is a square in Fq and if so calculating the square root of f(X3) in order to obtain the point P(X3); (iii) otherwise, testing whether the term f(X1) is a square and, if so, calculating the square root of f(X1) in order to obtain the point P(X1); (iv) otherwise, calculating the square root of f(X2) in order to obtain the point P(X2). This point P is useful in a cryptographic application.

## Claims

### Claim 1

An electronic component configured to execute a cryptographic calculation and to obtain a point P(X,Y) from at least one parameter t, on an elliptical curve that satisfies the equation: Y2=f(X) and from polynomials X1(t), X2(t), X3(t) and U(t) satisfying the following Skalba equality: f(X1(t))·f(X2(t))·f(X3(t))=U(t)2 in a finite field Fq, regardless of the parameter t, q satisfying the equation q=3 mod 4, wherein said electronic component is configured to:
obtain a value of the parameter t; and
determine the point P by:
(i) calculating X1=X1(t), X2=X2(t), X3=X3(t) and U=U(t)
(ii) if the term f(X1)·f(X2) is a squared term in the finite field Fq then testing whether the term f(X3) is a squared term in the finite field Fq and calculating the square root of the term f(X3), the point P having X3 as abscissa and the square root of the term f(X3) as ordinate;
(iii) otherwise, testing whether the term f(X1) is a squared term in the finite field Fq and in this case, calculating the square root of the term f(X1), the point P having X1 as abscissa and the square root of the term f(X1) as ordinate;
(iv) otherwise, calculating the square root of the term f(X2), the point P having X2 as abscissa and the square root of the term f(X2) as ordinate;
wherein said electronic component is further configured to use said point P in a cryptographic application selected from the group consisting of encryption or hashing or signature or authentication or identification,
wherein the cryptographic calculation is an application of authentication or identification by a checking entity, and
wherein obtaining the value of the parameter t further comprises:
/a/ generating a random value;
/b/ obtaining an encrypted value by encrypting said random value based on an encryption function using an encryption key determined from a password or identifier corresponding to the parameter; and
/c/ transmitting the encrypted value to the checking entity.

### Claim 2 (depends on 1)

The electronic component according to claim 1, wherein in order to determine the point P said electronic component is further configured to:
calculate R1 such that:
R
1
=
(
f

(
X
1
)
·
f

(
X
2
)
)
q
+
1
4
if R12 is equal to f(X1)·f(X2), then decide whether the term f(X1)·f(X2) is a squared term in the field Fq; and
test whether the term f(X1) is a squared term in the finite field Fq by:
calculating R2′ such that:
R
2
′
=
f

(
X
1
)
q
-
1
-
q
+
1
4
calculating R3′ such that:
R3′=R2′2
calculating R4′ such that:
R4′=R3′·ƒ(X1)
if R4′ is not equal to 1, obtain the square roof of the term f(X2) from the following equation:
√{square root over (ƒ(X2))}=R1·R2′.

### Claim 3 (depends on 1)

The electronic component according to claim 1, wherein the polynomials that satisfy Skalba's equality are expressed in Jacobian coordinates according to which the point P(X,Y) is written P(X′,Y′,Z) such that:
X′=X·Z2 and
Y′=Y·Z3
wherein the function f is written ƒz(X′) and satisfies:
ƒz(X′)=X′3+a·X′·Z4+b·Z6
with the elliptical curve satisfying the equation:
Y′2=ƒz(X′)
in which the polynomials that satisfy Skalba's equality expressed in Jacobian coordinates are X′1(t), X′2(t), X′3(t), Z(t) and U′(t) and satisfy Skalba's equality in Jacobian coordinates:
U′(t)2=ƒZ(t)(X′1(t))·ƒZ(t)(X′2(t))·fZ(t)(X′3(t))
and in which Z(t) is determined in such a way that operations of inversion are transformed into operations of multiplication.

### Claim 4 (depends on 1)

The electronic component according to claim 1, wherein the polynomials that satisfy Skalba's equality are such that it is possible to set a value of X3(t) for any possible t, such that f(X3(t)) is never a squared term in Fq, and
wherein when determining the point P, the term f(X1)·f(X2) is not a squared term in the finite field Fq,
wherein determining the point P further comprises testing whether the term f(X1) is a squared term in the finite field Fq by:
calculating R2′ such that:
R
2
′
=
f

(
X
1
)
q
-
1
-
q
+
1
4
calculating R3′ such that:
R3′=R2′2; and
calculating R4′ such that:
R4′=R3′·ƒ(X1)
wherein, if R4′ is not equal to 1, determining the point P further comprises obtaining the square root of the term f(X2) according to the following equation:
√{square root over (ƒ(X2))}=R1·R2′
R
1
=
(
f

(
X
1
)
·
f

(
X
2
)
)
q
+
1
4
where
in which R1 is obtained beforehand from the following equation:
R
1
=
(
f

(
X
)
·
f

(
X
2
)
)
q
+
1
4
=
U
·
f

(
u
)
q
-
1
-
q
+
1
4
.

### Claim 5 (depends on 4)

The electronic component according to claim 4, wherein the polynomials that satisfy Skalba's equality are expressed in Jacobian coordinates according to which the point P(X,Y) is written P(X′,Y′,Z) such that:
X′=X·Z2 and
Y′=Y·Z3
where the function f is written ƒz(x′) and satisfies:
ƒz(X′)=X′3+a·X′·Z4+b·Z6
with the elliptical curve satisfying the equation:
Y′2=ƒz(X′)
in which the polynomials that satisfy Skalba's equality expressed in Jacobian coordinates are X′1(t), X′2(t), Z(t) and U′(t) and satisfy Skalba's equality in Jacobian coordinates:
U′(t)2=ƒZ(t)(X′1(t))·ƒZ(t)(X′2(t))·ƒ(X3(t))
and in which Z(t) is determined in such a way that operations of inversion are transformed into operations of multiplication.

### Claim 6 (depends on 1)

The electronic component according to claim 1, wherein obtaining the value of the parameter t comprises obtaining the value of the parameter t as a function of a password or an identifier.
