Method of elliptic curve cryptographic digital signature generation and verification using reduced base tau expansion in non-adjacent form

• US 6,243,467 B1
• Filed: 07/23/1998
• Issued: 06/05/2001
• Est. Priority Date: 07/23/1998
• Status: Expired due to Fees

• Current Assignee: Government of The United States of America As Represented By The National Security Agency
• Original Assignee: The United States of America As Represented By The Director National Security Agency
• Inventors: Solinas, Jerome A., Reiter, Robert W.
• Primary Examiner(s): Barron, Jr., Gilberto
• Assistant Examiner(s): LEANING, JEFFREY S
• Application Number:
  US09/120,740
• Time in Patent Office: 1,048 Days
• Field of Search: 380/30, 713/176, 713/170, 713/180
• US Class Current: 380/30
• CPC Class Codes: G06F 7/725 over elliptic curves
• CPC Class Codes: H04L 9/3066 involving algebraic varieties, e.g. elliptic or hyper-elliptic curves
• CPC Class Codes: H04L 9/3247 involving digital signatures

Abstract

A method of generating and verifying a digital signature by selecting an elliptic curve; selecting a point G; generating x and M; reducing x; generating a base tau expansion, in non-adjacent form, of the reduced x; multiplying G by the expansion; computing h=Hash(M); generating k; reducing k; generating a base tau expansion, in non-adjacent form, of the reduced k; multiplying G by the expansion of k to form K=(K_x,K_y); computing R=(K_x mod q); returning to the step of generating k if R=0, otherwise computing S=(k{circumflex over ( )}−1)(h+xR); returning to the step of generating k if S=0, otherwise transmitting y, q, M, R, and S; receiving y, q, M, R, and S; proceeding with the next step if 0<R<q and 0<S<q, otherwise not verifying the digital signature and stopping; forming h=Hash(M); computing f=((S{circumflex over ( )}−1) mod q), b=(hf mod q), and t=(Rf mod q); reducing b and t; generating a base tau expansion, in non-adjacent form, of the reduced b; multiplies G by the result of the last step to form a point B; reduces t; generates a base tau expansion, in non-adjacent form, of the reduced b and t; multiplying G by the expansion of t; computing V=B+T, where V=(V_x,V_y); computing v=(V_x mod q); and verifying the digital signature if v=R, otherwise not verifying the digital signature.

Claims

1. A method of generating a digital signature for transmission to a recipient, comprising the steps of:

a) selecting an elliptic curve, where the elliptic curve is of the form y²+xy=x³+a(x{circumflex over ( )}2)+1, where “

a”

is a member of a field F₂, where the elliptic curve is defined over a field F₂m, and where m is an integer;

b) selecting a point G on the elliptic curve as a base point, where the point G is of order q, and where q is an integer;

c) generating a private signature key x and a message M;

d) reducing x by mod (τ

^m−

1) in the form of w+zt;

e) generating a base tau expansion, in non-adjacent form, of the result of step (d);

f) multiplying G by the result of step (e) to form a point y on the elliptic curve;

g) computing h=Hash(M), where “

Hash”

is a secure one-way hash function;

h) generating a private integer k;

i) reducing k by mod (τ

^m−

1) in the form of w+zt;

j) generating a base tau expansion, in non-adjacent form, of the result of step (i);

k) multiplying G by the result of step (j) to form a point K on the elliptic curve, where K=(K_x,K_y);

l) computing R=(K_x mod q);

m) returning to step (h) if R=0, otherwise proceeding to the next step;

n) computing S=(k{circumflex over ( )}−

1)(h+xR);

o) returning to step (h) if S=0, otherwise proceeding to the next step; and

p) transmitting y, q, M, R, and S to the recipient, where the pair (R,S) is the digital signature for the message M.

2. The method of claim 1, wherein said step of reducing x by mod (τ

^m−

1) in the form of w+zτ

is comprised of the steps of;

a) setting L₀=0;

b) setting L₁=1;

c) setting i=2;

d) setting L_i=(−

1)<sup>1−

a</sup>L<sub>i−

1</sub>−

2L<sub>i−

2</sub>;

e) determining whether or not i=m;

f) incrementing i by one and returning to step (d) for further processing if i≠

m in step (e); and

g) setting j₁=−

2L<sub>i−

1</sub>−

1, setting j₂=L_i, and returning j₁ and j₂ if i=m in step (e).

3. The method of claim 2, further comprising the steps of:

a) setting n=(j₁{circumflex over ( )}2)+(−

1)<sup>1−

a</sup>j₁j₂+2(j₂{circumflex over ( )}2);

b) setting c=└

(j₁x+(−

1)<sup>1−

a</sup>j₂x)/n┘

, where “

└

┘

”

denotes a function of returning the largest integer not larger than the value contained therein;

c) setting d=└

−

j₂x/n┘

;

d) setting w=x−

j₁c+2j₂d;

e) setting z=−

j₂c−

j₁d−

(−

1)<sup>1−

a</sup>j₂d; and

f) returning, w and z.

4. The method of claim 1, wherein said step of generating a base tau expansion, in non-adjacent form, of the result of step (d) is comprised of the steps of:

a) setting i=0;

b) setting x_i=0 if w is even, otherwise setting x_i=1−

z[((w−

1+2z)/2) mod 2];

c) setting w=w−

x_i;

d) setting temp=w;

e) setting (−

1)<sup>1−

a</sup>(temp/2)+z;

f) setting z=(−

temp)/2; and

g) incrementing i by one and returning to step (b) if both w and z are not equal to zero, otherwise returning (x_i, x<sub>i−

1</sub>, . . . ,x₀) as the base tau expansion, in non-adjacent form, of the modular reduced private signature key x.

5. The method of claim 1, wherein said step of multiplying G by the result of step (e) is comprised of the steps of:

a) computing y=x_iG;

b) decrementing i by one;

c) setting y=ty;

d) setting y=y+G if x_i=1;

e) setting y=y−

G if x_i=−

1; and

f) returning to step (b) for further processing if i=0, otherwise returning y as the product of G and the base tau expansion, in non-adjacent form, of the modular reduced private signature key x.

6. The method of claim 1, wherein said step of reducing k by mod (τ

^m−

1) in the form of w+zτ

comprised of the steps of;

a) setting L₀=0;

b) setting L₁=1;

c) setting i=2;

d) setting L_i=(−

1)<sup>1−

a</sup>L<sub>i−

1</sub>−

2L<sub>i−

2</sub>;

e) determining whether or not i=m;

f) incrementing i by one and returning to step (d) for further processing if i≠

m in step (e); and

g) setting j₁=−

2L<sub>i−

1</sub>−

1, setting j₂=L_i, and returning j₁ and j₂ if i=m in step (e).

7. The method of claim 6, further comprising the steps of:

a) setting n=(j₁{circumflex over ( )}2)+(−

1)<sup>1−

a</sup>₁j₂+2(j₂{circumflex over ( )}2);

b) setting c=└

(j₁x+(−

1)<sup>1−

a</sup>j₂x)/n┘

, where “

└

┘

”

denotes a function of returning the largest integer not larger than the value contained therein;

c) setting d=└

−

j₂x/n┘

;

d) setting w=x−

j₁c+2j₂d;

e) setting z=−

j₂c−

j₁d−

(−

1)<sup>1−

a</sup>j₂d; and

f) returning w and z.

8. The method of claim 1, wherein said step of generating a base tau expansion, in non-adjacent form, of the result of step (i) is comprised of the steps of:

a) setting i=0;

b) setting k_i=0 if w is even, otherwise setting k_i=1−

z[((w−

1+2z)/2) mod 2];

c) setting w=w−

k_i;

d) setting temp=w;

e) setting w=(−

1)<sup>1−

a</sup>(temp/2)+z;

f) setting z=(−

temp)/2; and

g) incrementing i by one and returning to step (b) if both w and z are not equal to zero, otherwise returning (k_i, k<sub>i−

1</sub>, . . . ,k₀) as the base tau expansion, in non-adjacent form, of the modular reduced private integer k.

9. The method of claim 1, wherein said step of multiplying G by the result of step (j) is comprised of the steps of:

a) computing K=k_iG;

b) decrementing i by one;

c) setting K=tK;

d) setting K=K+G if k_i=1;

e) setting K=K−

G if k_i=−

1; and

f) returning to step (b) for further processing if i=0, otherwise returning K as the product of G and the base tau expansion, in non-adjacent form, of the modular reduced private integer k.

10. The method of claim 3, wherein said step of generating a base tau expansion in non-adjacent form, of the result of step (d) is comprised of the steps of:

a) setting i=0;

b) setting x_i=0 if w is even, otherwise setting x_i=1−

z[((w−

1+2z)/2) mod 2];

c) setting w=w−

x_i;

d) setting temp=w;

e) setting w=(−

1)<sup>1−

a</sup>(temp/2)+z;

f) setting z=(−

temp)/2; and

g) incrementing i by one and returning to step (b) if both w and z are not equal to zero, otherwise returning (x_i, x<sub>i−

1</sub>, . . . ,x₀) as the base tau expansion, in non-adjacent form, of the modular reduced private signature key x.

11. The method of claim 10, wherein said step of multiplying G by the result of step (e) is comprised of the steps of:

a) computing y=x_iG;

b) decrementing i by one;

c) setting y=ty;

d) setting y=y+G if x_i=1;

e) setting y=y−

G if x_i=−

1; and

f) returning to step (b) for further processing if i=0 otherwise returning y as the product of G and the base tau expansion, in non-adjacent form, of the modular reduced private signature key x.

12. The method of claim 11, wherein said step of reducing k by mod (τ

^m−

1) in the form of w+zτ

is comprised of the steps of;

a) setting L₀=0;

b) setting L₁=1;

c) setting i=2;

d) setting L_i=(−

1)<sup>1−

a</sup>L<sub>i−

1</sub>−

2L<sub>i−

2</sub>;

e) determining whether or not i=m;

f) incrementing i by one and returning to step (d) for further processing if i≠

m in step (e); and

g) setting j₁=−

2L<sub>i−

1</sub>−

1, setting j₂=L_i, and returning j₁ and j₂ if i=m in step (e).

13. The method of claim 12, further comprising the steps of:

a) setting n=(j₁{circumflex over ( )}2)+(−

1)<sup>1−

a</sup>j₁j₂+2(j₂{circumflex over ( )}2);

b) setting c=└

(j₁x+(−

1)<sup>1−

a</sup>j₂x)/n┘

, where “

└

┘

”

denotes a function of returning the largest integer not larger than the value contained therein;

c) setting d=└

−

j₂x/n┘

;

d) setting w=x−

j₁c+2j₂d;

e) setting z=−

j₂c−

j₁d−

(−

1)<sup>1−

a</sup>j₂d; and

f) returning w and z.

14. The method of claim 13, wherein said step of generating a base tau expansion, in non-adjacent form, of the result of step (i) is comprised of the steps of:

a) setting i=0;

b) setting k_i=0 if w is even, otherwise setting k_i=1−

z[((w−

1+2z)/2) mod 2];

c) setting w=w−

k_i;

d) setting temp=w;

e) setting w=(−

1)<sup>1−

a</sup>(temp/2)+z;

f) setting z=(−

temp)/2; and

g) incrementing, i by one and returning to step (b) if both w and z are not equal to zero, otherwise returning (k_i, k<sub>i−

1</sub>, . . . ,k₀) as the base tau expansion, in non-adjacent form, of the modular reduced private integer k.

15. The method of claim 14, wherein said step of multiplying G by the result of step (j) is comprised of the steps of:

a) computing K=k_iG;

b) decrementing i by one;

c) setting K=tK;

d) setting K=K+G if k_i=1;

e) setting K=K−

G if k_i=−

1; and

f) returning to step (b) for further processing if i=0, otherwise returning K as the product of G and the base tau expansion, in non-adjacent form, of the modular reduced private integer k.

16. A method of verifying a digital signature (R,S) for a message M, comprising the steps of:

a) receiving parameters y, q, M, R, and S;

b) proceeding with the next step if 0<

R<

q and 0<

S<

q, otherwise determining that the digital signature is not verified and stopping;

c) forming h=Hash(M), where “

Hash”

is a secure one-way hash function that is identical to a hash function used to generate S;

d) computing f=((S{circumflex over ( )}−

1) mod q);

e) computing b=(hf mod q) and t=(Rf mod q);

f) reducing b by mod (τ

^m−

1) in the form of w+zt;

g) generating a base tau expansion, in non-adjacent form, of the result of step (f);

h) multiplying G by the result of step (g) to form a point B on an elliptic curve used to generate y, R, and S;

i) reducing t by mod (τ

^m−

1) in the form of w+zt;

j) generating a base tau expansion, in non-adjacent form, of the result of step (i);

k) multiplying G by the result of step (j) to form a point T on the elliptic curve,

l) computing V=B+T, where V=(V_x,V_y);

m) computing v=(V_x mod q); and

n) verifying the digital signature if v=R, otherwise not verifying the digital signature.

17. The method of claim 16, wherein said step of reducing b by mod (τ

^m−

1) in the form of w+zτ

is comprised of the steps of;

a) setting L₀=0;

b) setting L₁=1;

c) setting i=2;

d) setting L_i=(−

1)<sup>1−

a</sup>L<sub>i−

1</sub>−

2L<sub>i−

2</sub>;

e) determining whether or not i=m;

f) incrementing i by one and returning to step (d) for further processing if i≠

m in step (e); and

g) setting j₁=−

2L<sub>i−

1</sub>−

1, setting j₂=L_i, and returning j₁ and j₂ if i=m in step (e).

18. The method of claim 17, further comprising the steps of:

a) setting n=(j₁{circumflex over ( )}2)+(−

1)<sup>1−

a</sup>j₁j₂+2(j₂{circumflex over ( )}2);

b) setting c=└

(j₁b+(−

1)<sup>1−

a</sup>j₂b)/n┘

, where “

└

┘

”

denotes a function of returning the largest integer not larger than the value contained therein;

c) setting d=└

−

j₂b/n┘

;

d) setting w=b−

j₁c+2j₂d;

e) setting z=−

j₂c−

j₁d−

(−

1)<sup>1−

a</sup>j₂d; and

f) returning w and z.

19. The method of claim 16, wherein said step of generating a base tau expansion, in non-adjacent form, of the result of step (f) is comprised of the steps of:

a) setting i=0;

b) setting b_i=0 if w is even, otherwise setting b_i=1−

z[((w−

1+2z)/2) mod 2];

c) setting w=w−

b_i;

d) setting temp=w;

e) setting w=(−

1)<sup>1−

a</sup>(temp/2)+z;

f) setting z=(−

temp)/2; and

g) incrementing i by one and returning to step (b) if both w and z are not equal to zero, otherwise returning (b_i, b_i, b<sub>i−

1</sub>, . . . ,b₀) as the base tau expansion, in non-adjacent form, of the modular reduced b.

20. The method of claim 16, wherein said step of multiplying G by the result of step (g) is comprised of the steps of:

a) computing B=b_iG;

b) decrementing i by one;

c) setting B=tB;

d) setting B=B+G if b_i=1;

e) setting B=B−

G if b_i=−

1; and

f) returning to step (b) for further processing if i=0, otherwise returning B as the product of G and the base tau expansion, in non-adjacent form, of the modular reduced b.

21. The method of claim 16, wherein said step of reducing t by mod (τ

^m−

1) in the form of w+zτ

is comprised of the steps of;

a) setting L₀=0;

b) setting L₁=1;

c) setting i=2;

d) setting L_i=(−

1)<sup>1−

a</sup>L<sub>i−

1</sub>−

2L<sub>i−

2</sub>;

e) determining whether or not i=m;

f) incrementing i by one and returning to step (d) for further processing if i≠

m in step (e); and

g) setting j₁=−

2L<sub>i−

1</sub>−

1, setting j₂=L_i, and returning j₁ and j₂ if i=m in step (e).

22. The method of claim 21, further comprising the steps of:

a) setting n=(j₁{circumflex over ( )}2)+(−

1)<sup>1−

a</sup>j₁j₂+2(j₂{circumflex over ( )}2);

b) setting c=└

(jt+(−

1)<sup>1−

a</sup>j₂t)/n┘

, where “

└

┘

”

denotes a function of returning the largest integer not larger than the value contained therein;

c) setting d=└

−

j₂t/n┘

;

d) setting w=t−

j₁c+2j₂d;

e) setting z=−

j₂c−

j₁d−

(−

1)<sup>1−

a</sup>j₂d; and

f) returning w and z.

23. The method of claim 16, wherein said step of generating a base tau expansion, in non-adjacent form, of the result of step (i) is comprised of the steps of:

a) setting i=0;

b) setting t_i=0 if w is even, otherwise setting t_i=1−

z[((w−

1+2z)/2) mod 2];

c) setting w=w−

t_i;

d) setting temp=w;

e) setting w=(−

1)<sup>1−

a</sup>(temp/2)+z;

f) setting z=(−

temp)/2; and

g) incrementing i by one and returning to step (b) if both w and z are not equal to zero, otherwise returning (t_i, t<sub>i−

1</sub>, . . . ,t₀) as the base tau expansion, in non-adjacent form, of the modular reduced t.

24. The method of claim 16, wherein said step of multiplying G by the result of step (j) is comprised of the steps of:

a) computing T=t_iG;

b) decrementing i by one;

c) setting T=tT;

d) setting T=T+G if t_i=1;

e) setting T=T−

G if t_i=−

1; and

f) returning to step (b) for further processing if i=0, otherwise returning T as the product of G and the base tau expansion, in non-adjacent form, of the modular reduced t.

25. The method of claim 18, wherein said step of generating a base tau expansion, in non-adjacent form, of the result of step (f) is comprised of the steps of:

a) setting i=0;

b) setting b_i=0 if w is even, otherwise setting b_i=1−

z[((w−

1+2z)/2) mod 2];

c) setting w=w−

b_i;

d) setting temp=w;

e) setting w=(−

1)<sup>1−

a</sup>(temp/2)+z;

f) setting z=(−

temp)/2; and

g) incrementing i by one and returning to step (b) if both w and z are not equal to zero, otherwise returning (b_i, b<sub>i−

1</sub>, . . . ,b₀) as the base tau expansion, in non-adjacent form, of the modular reduced b.

26. The method of claim 25, wherein said step of multiplying G by the result of step (g) is comprised of the steps of:

a) computing B=b_iG;

b) decrementing i by one;

c) setting B=tB;

d) setting B=B+G if b_i=1,

e) setting B=B−

G if b_i−

1; and

f) returning to step (b) for further processing if i=0, otherwise returning B as the product of G and the base tau expansion, in non-adjacent form of the modular reduced b.

27. The method of claim 26, wherein said step of reducing t by mod (τ

^m−

1) in the form of w+zτ

is comprised of the steps of;

a) setting L₀=0;

b) setting L₁=1;

c) setting i=2;

d) setting L_i=(−

1)<sup>1−

a</sup>L<sub>i−

1</sub>−

2L<sub>i−

2</sub>;

e) determining whether or not i=m;

f) incrementing i by one and returning to step (d) for further processing if i≠

m in step (e); and

g) setting j₁=−

2L<sub>i−

1</sub>−

1, setting j₂=L_i, and returning j₁ and j₂ if i=m in step (e).

28. The method of claim 27, further comprising the steps of:

a) setting n=(j{circumflex over ( )}2)+(−

1)<sup>1−

a</sup>j₁j₂+2(j₂{circumflex over ( )}2);

b) setting c=└

(j₁t+(−

1)<sup>1−

a</sup>j₂t)/n┘

, where “

└

┘

”

denotes a function of returning the largest integer not larger than the value contained therein;

c) setting d=└

−

j₂t/n┘

;

d) setting w=t−

j₁c+2j₂d;

e) setting z=−

j₂c−

j₁d d−

(−

1)<sup>1−

a</sup>j₂d; and

f) returning w and z.

29. The method of claim 28, wherein said step of generating a base tau expansion in non-adjacent form, of the result of step (i) is comprised of the steps of:

a) setting, i=0;

b) setting t_i=0 if w is even, otherwise setting t_i=1−

z[((w−

1+2z)/2) mod 2];

c) setting w=w−

t_i;

d) setting temp=w;

e) setting w=(−

1)<sup>1−

a</sup>(temp/2)+z;

f) setting z=(−

temp)/2; and

g) incrementing i by one and returning to step (b) if both w and z are not equal to zero, otherwise returning (t_i, t<sub>i−

1</sub>, . . . ,t₀) as the base tau expansion, in non-adjacent form, of the modular reduced t.

30. The method of claim 29, wherein said step of multiplying G by the result of step (j) is comprised of the steps of:

a) computing T=t_iG;

b) decrementing i by one;

c) setting T=tT;

d) setting T=T+G if t_i=1;

e) setting T=T−

G if t_i=−

1; and

f) returning to step (b) for further processing if i=0, otherwise returning T as the product of G and the base tau expansion, in non-adjacent form, of the modular reduced t.