Computing method for elliptic curve cryptography

• US 7,079,650 B1
• Filed: 07/07/2000
• Issued: 07/18/2006
• Est. Priority Date: 07/09/1999
• Status: Active Grant

• Current Assignee: Oberthur Card Systems, S.A. (Advent International Corporation)
• Original Assignee: Oberthur Card Systems, S.A. (Advent International Corporation)
• Inventors: Knudsen, Erik
• Primary Examiner(s): Barron, Jr., Gilberto
• Assistant Examiner(s): Simitoski, Michael J.
• Application Number:
  US09/786,756
• Time in Patent Office: 2,202 Days
• Field of Search: 380/28, 380/30, 380/282, 380/285, 380/44, 713/176, 708/492
• US Class Current: 380/30
• CPC Class Codes: G06F 7/725 over elliptic curves

Abstract

A fast cryptographic method between two entities exchanging data via a non-secure communication channel. The method, for example, forms a common key between two entities (A,B), each having a secret key (a,b) and using a public key (P) formed by a point of an elliptic curve (E), and includes at least multiplying the odd order point (P) by an integer by additions and halving operations.

Claims

1. A cryptographic method employed between two entities exchanging information via a non-secure communication channel, each of the two entities comprising a memory readable by a machine, tangibly embodying a program of instruction executable by the machine to perform the method, the method including a step of multiplying an odd order point of a non-supersingular elliptic curve by an integer, wherein, for exchanging information via the non-secure communication channel, the step of multiplying is performed by addition and halving operations of points of said elliptic curve, the halving of a point P is defined as the unique odd order point D such that [2]D=P,

$\left[\frac{1}{2}\right]$

P _

denotes the point D.

2. A method according to claim 1, where F_2n is a finite body of 2² elements, E(F_2n) is the sub-group of an elliptic curve E defined by:

E(F₂ⁿ)={(x,y)ε

F₂ⁿ×

F₂ⁿ|y²+xy=x³+α

x²+β

}∪

{O}α

, β

ε

F₂ⁿ, β

≠

0

and E[2^k] is the set of points P of said elliptic curve such that P added 2^k times to itself gives the neutral element O, where k is an integer greater than or equal to 1, wherein a point P=(x,y) of said elliptic curve gives by said halving the point

$\left[\frac{1}{2}\right]<br><br>P=\left(u_o,v_o\right)$

of said elliptic curve obtained by effecting the following operations;

(a) seek a first value λ

_o such that λ

_o²+λ

_o=α

+x;

(b) calculate a second value u_o² such that u_o²=x (λ

_o+1)+y;

(c) if k has the value 1, check if the equation;

λ

²+λ

=α

²+u²_o has solutions in F₂ⁿ;

(d) if the check in step (c) is yes, calculate said halving as follows;

u_o=√

{square root over (u₀²)},

v_o=u_o(u_o+λ

_o)

and

$\left[\frac{1}{2}\right]<br><br>P=\left(u_o,v_o\right);<br><br>$

(e) if not, add x to said second value u_o² and 1 to said first value λ

_o and calculate said halving as in step (d);

(f) if k is greater than 1, perform an iterative calculation as follows;

(i) seek a value λ

_i such that λ

_i²+λ

_i=α

+u<sub>i−

1</sub>; and

(ii) then calculate the value u²_i such that u²_i=u<sub>i−

1</sub>(λ

_i+λ

<sub>i−

1</sub>+u<sub>i−

1</sub>+1) by incrementing i from i=1 until the value u²<sub>k−

1</sub> is obtained;

(g) check whether the equation λ

²+λ

=α

²+u²<sub>k−

1</sub> has solutions in F₂ⁿ;

(h) if so, calculate said halving as follows;

u_o=√

{square root over (u₀²)},

v_o=u_o(u_o+λ

_o)

and

$\left[\frac{1}{2}\right]<br><br>P=\left(u_o,v_o\right);<br><br><br><br>a<br><br><br><br>n<br><br><br><br>d$

(i) if not, add x to the second value u_o² and 1 to said first value λ

_o and calculate said halving as in step (h).

3. A method according to claim 1, where F₂ⁿ is a finite body of 2ⁿ elements, E(F₂ⁿ) is the sub-group of an elliptic curve E defined by:

E(F₂ⁿ)={(x,y)ε

F₂ⁿ×

F₂ⁿ|y²+xy=x³+α

x²+β

}∪

{O}α

, β

ε

F₂ⁿ,β

≠

0

and E[2^k] is the set of points P of said elliptic curve such that P added 2^k times to itself gives the neutral element O, where k is an integer greater than or equal to 1, wherein a point P=(x,y) of said elliptic curve gives by said halving the point

$\left[\frac{1}{2}\right]<br><br>P=\left(u_o,{\mathrm{\lambda <br><br>}}_o\right)$

of said elliptic curve,

with λ

_o=u_o+v_o/u_o, obtained by effecting the following operations;

(a) seek a first value λ

_o such that λ

_o²+λ

_o=α

+x;

(b) calculate a second value u_o² such that;

u_o²=x (λ

_o+1)+y;

(c) if k has the value 1, check if the equation;

λ

²+λ

=α

²+u_o² has solutions in F₂ⁿ;

(d) if so, calculate said halving as follows;

u_o=√

{square root over (u₀²)},

and

$\left[\frac{1}{2}\right]<br><br>P=\left(u_o,{\mathrm{\lambda <br><br>}}_o\right);<br><br>$

(e) if not, add x to said second value u_o² and 1 to said first value λ

_o and calculate said halving as in step (d);

(f) if k is greater than 1, perform the following iterative calculation;

(i) seek a value λ

_i, such that λ

_i²+λ

_i=α

+u<sub>i−

1</sub>; and

(ii) then calculate the value u_i² such that u_i²=u<sub>i−

1</sub>(λ

_i+λ

<sub>i−

1</sub>+u<sub>i−

1</sub>+1) by incrementing i from i=1 until the value u²<sub>k−

1</sub> is obtained;

(g) check if the equation λ

²+λ

=α

²+u²<sub>k−

1</sub> has solutions in F_2n;

(h) if so, calculate said halving as follows;

u_o=√

{square root over (u₀²)}, and

$\left[\frac{1}{2}\right]<br><br>P=\left(u_o,{\mathrm{\lambda <br><br>}}_o\right);<br><br><br><br>a<br><br><br><br>n<br><br><br><br>d$

(i) if not, add x to said second value u_o² and 1 to said first value λ

_o to calculate said halving as in step (h).

4. A method according to claim 1, where F₂ⁿ is a finite body of 2ⁿ elements, E(F₂ⁿ) is the sub-group of an elliptic curve E defined by:

E(F₂ⁿ)={(x,y)ε

F₂ⁿ×

F₂ⁿ|y²+xy=x³+α

x²+β

}∪

{O}α

, β

ε

F₂ⁿ,β

≠

0

and E[2^k] is the set of points P of said elliptic curve such that P added 2^k times to itself gives the neutral element O, where k is an integer greater than or equal to 1, wherein a point P=(x,y) of said elliptic curve represented by (x,λ

_p) with λ

_p=x+y/x gives by said halving the point

$\left[\frac{1}{2}\right]<br><br>P=\left(u_o,v_o\right)$

of said elliptic curve obtained by effecting the following operations;

(a) seek a first value λ

₀ such that λ

_o²+λ

_o=α

+x;

(b) calculate a second value u_o² such that u_o²=x (λ

_oλ

+λ

_p+x+1);

(c) if k has the value 1, check if the equation;

λ

²+λ

=α

²+u_o² has solutions in F₂ⁿ;

(d) if so, calculate said halving as follows;

u_o=√

{square root over (₀²)},

v_o=u_o(u_o+λ

_o),

$a<br><br><br><br>n<br><br><br><br>d<br><br>\left[\frac{1}{2}\right]<br><br>P=\left(u_o,v_o\right);<br><br>$

(e) if not, add x to said second value u_o² and 1 to said first value λ

_o and calculate said halving as in step (d);

(f) if k is greater than 1, perform the following iterative calculation;

(i) seek a value λ

_i such that λ

_i²+λ

_i=α

+u<sub>i−

1</sub>; and

(ii) then calculate the value u_i² such that u_i²=u<sub>i−

1</sub> (λ

_i+λ

<sub>i−

1</sub>+u<sub>i−

1</sub>+1) incrementing i from i=1 until the value u²<sub>k−

1</sub> is obtained;

(g) check if the equation λ

²+λ

=α

²+u²<sub>k−

1</sub> has solutions in F₂ⁿ;

(h) if so, calculate said halving as follows;

u_o=√

{square root over (₀²)},

v_o=u_o(u_o+λ

_o),

$a<br><br><br><br>n<br><br><br><br>d<br><br>\left[\frac{1}{2}\right]<br><br>P=\left(u_o,v_o\right);<br><br><br><br>a<br><br><br><br>n<br><br><br><br>d$

(i) if not, add x to said second value u_o² and 1 to said first value λ

_o and calculate said halving as in step (h).

5. A method according to claim 1, where F₂ⁿ is a finite body of 2ⁿ elements, E(F₂ⁿ) is the sub-group of an elliptic curve E defined by:

E(F₂ⁿ)={(x,y)ε

F₂ⁿ×

F₂ⁿ|y²+xy=x³+α

x²+β

}∪

{O}α

, β

ε

F₂ⁿβ

≠

0

and E[2^k] is the set of points P of said elliptic curve such that P added 2^k times to itself gives the neutral element O, where k is an integer greater than or equal to 1, wherein a point P=(x,y) of said elliptic curve represented by (x,λ

_p) with λ

p=x+y/x gives by said halving the point

$\left[\frac{1}{2}\right]<br><br>P=\left(u_o,v_o\right)$

of said elliptic curve represented by

(u_o, λ

_o), with λ

_o=u_o+v_o/u_o obtained by effecting the following operations;

(a) seek for a first value λ

_o such that λ

_o²+λ

_o=α

+x;

(b) calculate a second value u_o² such that u_o²=x (λ

_o+λ

_p+x+1);

(c) if k has the value 1, check if the equation λ

²+λ

=α

²+u_o² has solutions in F₂ⁿ;

(d) if so, calculate said halving as follows;

u_o=√

{square root over (u₀²)},

$a<br><br><br><br>n<br><br><br><br>d<br><br>\left[\frac{1}{2}\right]<br><br>P=\left(u_o,{\mathrm{\lambda <br><br>}}_o\right);<br><br>$

(e) if not, add x to said second value u_o² and 1 to said first value λ

_o and calculate said halving as in step (d);

(f) if k is greater than 1, perform the following iterative calculation;

(i) seek a value λ

_i such that λ

_i²+λ

_i=α

+u<sub>i−

1</sub>; and

(ii) then calculate the value u_i² such that u_i²=u<sub>i−

1</sub>(λ

_i+λ

<sub>i−

1</sub>+u<sub>i−

1</sub>+1) incrementing i from i=1 until the value u²<sub>k−

1</sub> is obtained;

(g) check if the equation λ

²+λ

=α

²+u²<sub>k−

1</sub> has solutions in F₂ⁿ;

(h) if so, calculate said halving as follows;

u_o=√

{square root over (u₀²)},

$a<br><br><br><br>n<br><br><br><br>d<br><br>\left[\frac{1}{2}\right]<br><br>P=\left(u_o,{\mathrm{\lambda <br><br>}}_o\right);<br><br><br><br>a<br><br><br><br>n<br><br><br><br>d$

(i) if not, add x to said second value u_o² and 1 to said first value λ

_o and calculate said halving as in step (h).

6. A method according to claim 1, further comprising constructing a common key from two secret keys respectively belonging to the aforementioned two entities and a public key consisting of the point P of odd order r of a chosen non-supersingular elliptic curve E.

7. A method according to claim 6, wherein a and b are the secret keys of first and second entities, respectively, and:

(a) the first entity calculates the scalar multiplication [a]P and sends the result point to the second entity,

(b) the second entity calculates the scalar multiplication [b]P and sends the result point to the first entity,

(c) the two entities respectively calculate a common point (C)=(x,y) of said elliptic curve (E) by respectively effecting the scalar multiplications [a] ([b]P) and [b] ([a]P), both equal to [a.b]P, and

(d) the two entities choose as their common key the coordinate (x) of said common point (C) obtained by said scalar multiplication [a.b]P, at least one of the preceding scalar multiplications, and preferably all of them, being effected by means of predefined halvings.

8. A method according to claim 7, wherein scalar multiplication using halvings is obtained by the following operations:

(e) if said scalar of the multiplication is denoted S, choose m+1 values So . . . Smε

{0,1} to define S as follows;

$S=\underset{i=0}{\overset{m}{\sum <br><br>}}<br><br><br><br>{S_i<br><br>\left(\frac{r+1}{2}\right)}^i,$

r being the aforementioned odd order and m being the single integer between log₂(r)−

1 and log₂(r),

(f) calculate the scalar multiplication [S]P of a point P of said elliptic curve by the scalar S by applying an algorithm consisting of determining the series of points (Q_m+1, Q_m . . . , Q_i . . . , Q_o) of said elliptic curve E such that;

Q_m+1=O (neutral element), and

$Q_i=\left[S_i\right]<br><br>P+\left[\frac{1}{2}\right]<br><br>Q_i<br><br>+1<br><br><br><br>w<br><br><br><br>i<br><br><br><br>t<br><br><br><br>h<br><br><br><br>o\le <br><br>i\le <br><br>m,<br><br>a<br><br><br><br>n<br><br><br><br>d$

(g) calculate the last point Q_o of said series giving the result [S]P of said scalar multiplication.

9. A method according to claim 1, further comprising calculating a signature between two entities based on a pair of permanent keys belonging to one of the entities, one secret (a) and the other public (Q), by scalar multiplication of the secret key (a) by another public key consisting of the point (P) of odd order r of a chosen non-supersingular elliptic curve (E).

10. A method according to claim 9, further comprising the following operations:

(a) the first entity (A) holding said pair of permanent keys constructs a single-use pair of keys, one key (g) being chosen arbitrarily and the other key [g]P resulting from scalar multiplication of said arbitrarily chosen key (g) by the public point P of said elliptic curve, the coordinates of the key ([g]P) being denoted (x,y) with 2≦

g≦

r−

2,

(b) the first entity (A) converts the polynomial x of said single-use key [g]P=(x,y) into an integer i whose binary value is represented by the sequence of binary coefficients of said polynomial x,

(c) said first entity (A) calculates a signature (c,d) of the message (M) as follows;

c=i modulo r

d=g<sup>−

1</sup> (M+ac) modulo r,

(d) said first entity sends said message (M) and said signature (c, d) to said second entity;

upon receiving it;

(i) said second entity (B) checks if the elements of said signature (c,d) each belong to the range [1, r−

1],

(ii) if the check in step (i) is no, the second entity declares the signature invalid and stops;

(iii) if the check in step (i) is yes, said second entity (B) calculates three parameters;

h=d<sup>−

1</sup> modulo r,

h₁=Mh modulo r, and

h₂=ch modulo r,

(e) said second entity calculates a point T of said elliptic curve by summing the scalar multiplications of the points P and Q by the last two parameters cited;

T=[h₁]P+[h₂]Q, and

(i) if the resultant point T is the neutral element, said second entity declares the signature invalid and stops;

(ii) if the resultant point T is not the neutral element, considering the point T with coordinates x′ and

y′

;

T=(x′

,y′

),

(A) said second entity (B) converts the polynomial x′

of that point into an integer i′

whose binary value is represented by the sequence of binary coefficients or said polynomial x′

,

(B) said second entity (B) calculates c′

=i′

modulo r and,

(C) said second entity (B) checks if c′

=c, in which case said second entity (B) validates said signature, or if not, said second entity (B) invalidates said signature, at least one aforementioned scalar multiplication operation being effected by means of the predefined halvings.

11. A method according to claim 1, wherein said integer is decomposed as a set of values using powers of half said order, and said addition and halving operations are implemented dependent on said set of values.