Digital signature generating/verifying method and system using public key encryption

• US 6,341,349 B1
• Filed: 10/30/1997
• Issued: 01/22/2002
• Est. Priority Date: 10/31/1996
• Status: Expired due to Fees

• Current Assignee: Hitachi, Ltd.
• Original Assignee: Hitachi, Ltd.
• Inventors: Takaragi, Kazuo, Kurumatani, Hiroyuki
• Primary Examiner(s): Peeso, Thomas R.
• Application Number:
  US08/961,557
• Time in Patent Office: 1,545 Days
• Field of Search: 380/30, 380/28, 380/25, 713/176
• US Class Current: 713/168
• CPC Class Codes: G06F 7/725 over elliptic curves
• CPC Class Codes: H04L 9/3013 involving the discrete logarithm problem, e.g. ElGamal or Diffie-Hellman systems
• 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 digital signature generating/verifying method using a public key encryption scheme which ensures high security, reduction in length of the digital signature and independency of the length of the digital signature on that the order of a base point. In generating a digital signature, a first hash value (e) satisfying a condition that e=H(M) is determined for a given message (M) by using a hash function (H), a numerical value (x) is obtained from translation of a random number, a hash value (r) satisfying a condition that r=h(x) is determined by using a hash function (h) whose output value is shorter than that of the first hash function (H), and the digital signature is generated by using the hash values (e) and (r) as determined. For verification of an inputted digital signature, the hash value (e) satisfying the condition that e=H(M) is determined, and for a numerical value (x) obtained from arithmetic operation of a public key (Q), a base point (P) and the inputted digital signature (r, s), a hash value (r′) satisfying a condition that r′=h(x) on the basis of the hash value (re), the digital signature (r, s), the base point (P) and the public key (Q) by using a hash function (h) whose output value is shorter than that of the first hash function (H). The hash value (r′) is then compared with a tally (r) of the inputted digital signature to thereby verify the inputted digital signature.

Claims

1. A digital signature generating method for generating a digital signature authenticating electronically a signature affixed to a given message, M, by resorting to a public key encryption scheme, comprising the steps of:

determining for said message, M, a first hash value, e, satisfying a condition that e=H(M) by using a first hash function, H;

determining for a numerical value, x, obtained from translation of a random number and independent of said message, a second hash value, r, satisfying a condition that r=h(x) by using a second hash function, h, whose output value is shorter than that of said first hash function, H, said second hash value being independent of said message; and

arithmetically determining and outputting said digital signature by using said first hash value, e, and said second hash value, r, as determined.

2. A digital signature generating method according to claim 1,

wherein for generating a digital signature (r₁, s₁) for a given message, M₁, said method comprises the steps of:

determining a hash value, e₁, satisfying a condition that e₁=H(M₁) by using said first hash function, H;

generating a random number, k₁;

determining an element, R₁, by multiplying an element, P, of an abelian group by said random number, k₁;

determining a first numerical value, r₁, satisfying a condition that r₁=h(R₁) by using the second hash function, h, whose output value is shorter than the output value of the first hash function, H;

determining a second numerical value, s₁, satisfying a condition that s₁=k₁+d₁(e₁+r₁) (mod n) by using the order, n, of said element, P, of said abelian group and a private key, d₁; and

outputting a set of said determined numerical values (r₁, s₁) as a digital signature.

3. A digital signature generating method according to claim 2,

wherein said element, P, of said abelian group corresponds to a point, P, on an elliptic curve.

4. A digital signature verifying method for verifying a digital signature authenticating electronically a signature affixed to a given message, M, by resorting to a public key encryption scheme, comprising the steps of:

determining for said message, M, a first hash value, e, satisfying a condition that e=H(M) by using a first hash function, H;

determining a second hash value, r′

, from a numerical value, x, said numerical value, x, being obtained from arithmetic operation of an inputted digital signature (r, s), a public key, Q, and an element, P, and which has been selected independently, said second hash value, r′

, satisfying a condition that r′

=h(x) from said first hash value, e, said digital signature (r, s), said element, P, and said public key, Q, by using a second hash function, h, whose output value is shorter than that of said first hash function, H, said second hash valve being independent of said message; and

comparing said second hash value, r′

, with a tally, r, of said inputted digital signature to thereby obtain a result of verification of said inputted digital signature.

5. A digital signature verifying method according to claim 4,

wherein for verifying a digital signature (r₁, s₁ ) of a given message, M₁, said method comprises the steps of:

determining a hash value, e₁, satisfying a condition that e₁=H(M₁);

inputting a public key, Q₁, generated previously so as to satisfy a condition Q₁=d₁P, where d₁ represents a private key, said public key, Q₁, having been registered;

determining arithmetically a point, R₁, of an abelian group, said point, R₁, being given by R₁=s₁P−

(e₁+r₁) Q₁;

determining a hash value, r₁′

, satisfying a condition that r₁′

=h(R₁);

outputting a data indicating that said digital signature is authenticated, when said hash value, r₁′

, coincides with said tally, r, of said digital signature; and

outputting a data indicating that said digital signature is not authenticated unless said hash value, r₁′

, coincides with said tally, r₁, of said digital signature.

6. A digital signature verifying method according to claim 5,

wherein said abelian group includes an elliptic curve.

7. A digital signature generating method for generating a multiple digital signature authenticating electronically signatures affixed to messages and/or comments, M_i, as created and/or added sequentially by N users i (where i=1, . . . , N) by using a public key encryption scheme, comprising the steps of:

(a) determining for a given one of said messages, M_i, a first hash value, e_i, satisfying a condition that e_i=H(M_i) by using a first hash function, H;

(b) determining for a numerical value, x_i, obtained from translation of a random number and independent of said message a second hash value, r_i, satisfying a condition that r_i=h(x_i) by using a second hash function, h, whose output value is shorter than that of said first hash function, H, wherein the value r_i is part of data configuring a digital signature, said second hash valve being independent of said message;

(c) executing said steps (a) and (b) for each of said users i (where i=1, . . . , N); and

(d) determining arithmetically said multiple digital signatures on the basis of the hash values (e_i and r_i) determined in said step (c).

8. A multiple digital signature generating method according to claim 7,

wherein for generating said multiple digital signature by user i (i≧ 2), said method comprises the steps of;

inputting a set of numeric values (x<sub>i−

1</sub>, y<sub>i−

1</sub>) obtained from translation of random numbers;

computing a hash value e_i=H(M_i);

generating a random number k_i;

computing a point k_iP=(x, y);

computing a point (x_i, y_i)=(x<sub>i−

1</sub>, y<sub>i−

1</sub>)+(x, y);

computing a hash value r_i=h(x_i);

determining by using a private key, d_i, a tally, s_i, satisfying a condition given by the following expression;

$s_i=s_{i-1}+k_i+d_i<br><br>\left(e_i+\underset{k=i}{\overset{i}{\sum <br><br>}}<br><br>\text{\hspace{1em}<br><br>}<br><br>r_k\right)<br><br>\text{\hspace{1em}<br><br>}<br><br>\left(\mathrm{mod}<br><br>\text{\hspace{1em}<br><br>}<br><br>n\right);<br><br>$

 

and

outputting a set of numerical values (r₁, . . . , r_i, s_i) as said multiple digital signature, wherein the value s_i is part of data configuring a digital signature.

9. A multiple digital signature verifying method according to claim 7,

wherein for generating a multiple digital signature by users i (i≧

2), said method comprises the steps of;

inputting (i−

1) messages and/or comments (M₁, . . . M<sub>i−

1</sub>) and (i−

1)-tuple digital signature (r_i, . . . , r<sub>i−

1</sub>, s<sub>i−

1</sub>) issued by an immediately preceding user (i−

1);

repeating computation of hash values e_k=H(M_k), where k represents 1 to (i−

1);

inputting repetitionally public keys Q_k generated so as to satisfy a condition that Q_k=d_kP, where k represents 1 to (i−

1);

computing an element (R<sub>i−

1</sub>) of an abelian group in accordance with $\left(R_{i-1}\right)=S_{i-1}<br><br>P-\underset{k=1}{\overset{i-1}{\sum <br><br>}}<br><br>\text{\hspace{1em}<br><br>}<br><br>{\left(e_k+\underset{M=1}{\overset{k}{\sum <br><br>}}<br><br>\text{\hspace{1em}<br><br>}<br><br>r_m\right)}_{Q^k};<br><br>$

 

computing a hash value (r′

<sub>i−

1</sub>=h(R<sub>i−

1</sub>);

issuing data indicating “

authenticated”

when said hash value, r<sub>i−

1</sub>′

, coincides with a tally, r<sub>i−

1</sub>, of said (i−

1)-tuple digital signature; and

issuing data indicating “

not-authenticated”

unless said hash value, r<sub>i−

1</sub>′

, coincides with said tally, r<sub>i−

1</sub>.

10. A digital signature verifying method according to claim 9,

wherein said abelian group includes an elliptic curve.

11. A digital signature verifying method for verifying a multiple digital signature authenticating electronically signatures affixed to messages and/or comments, M_i, as created and/or added sequentially by N users i (where i=1, . . . , N) by resorting to a public key encryption scheme, comprising the steps of:

(a) determining for the inputted message, M_i, a first hash value, e_i, satisfying a condition that e_i=H(M_i) by using a first hash function, H;

(b) determining for a numerical value, x_i, obtained by arithmetic operation of an inputted multiple digital signature (r_i, s_i), a public key, Q, and an element, P, and independent of said message, a second hash value, r_i′

, satisfying a condition that r_i′

=h(x_i) on the basis of said first hash value, e_i, said digital signature (r_i, s_i), said element, P, and said public key, Q, by using a second hash function, h, whose output value is shorter than that of said first hash function, H, said second hash value being independent of said message;

(c) executing said steps (a) and (b) for each of said users i (where i represents integers “

1”

to “

N”

inclusive, respectively); and

(d) comparing each of said hash values, r_i′

, determined in said step (c) with each of said tallies, r, of said inputted multiple digital signature to thereby obtain results of verification of said inputted digital signature.

12. A digital signature generating system for generating a digital signature authenticating electronically a signature affixed to a given message, M, by resorting to a public key encryption scheme, comprising:

processing means for determining for said message, M, a first hash value, e, satisfying a condition that e=H(M) by using a first hash function, H;

processing means for determining for a numerical value, x, obtained from translation of a random number and independent of said message, a second hash value, r, satisfying a condition that r=h(x) by using a second hash function, h, whose output value is shorter than that of said first hash function, H, said second hash value being independent of said message; and

arithmetic/output means for arithmetically determining and outputting said digital signature by using said first hash value, e, and said second hash value, r, as determined.

13. A digital signature generating system according to claim 12,

wherein for generating a digital signature (r₁, s₁) for a given message, M₁, said system comprises:

means for determining a hash value, e₁, satisfying a condition that e₁=H(M₁) by using the first hash function, H;

means for generating a random number, k₁;

means for determining an element, R₁, by multiplying an element P, of the abelian group by said random number, k₁;

means for determining a first numerical value, r₁, satisfying a condition that r₁=h(R₁) by using the second hash function, h, whose output value is shorter than that of said first hash function, H;

means for determining a second numerical value, s₁, satisfying a condition that s₁=k₁+d₁(e₁+r₁) (mod n) by using order, n₁, of said element, P, of the abelian group and a private key, d₁; and

means for outputting a set of said determined numerical values (r₁, s₁) as a digital signature.

14. A digital signature verifying system according to claim 13,

wherein said abelian group corresponds to an elliptic curve.

15. A digital signature verifying system for verifying a digital signature authenticating electronically a signature affixed to a given message, M, by resorting to a public key encryption scheme, comprising:

first arithmetic means for determining for said given message, M, a first hash value, e, satisfying a condition that e=H(M) by using a first hash function, H;

second arithmetic means coupled to said first arithmetic means for determining for a numerical value, x, obtained from arithmetic operation of an inputted digital signature (r, s), a public key, Q, and a base point, P, and independent of said message, a second hash value, r′

, satisfying a condition that r′

=h(x) from said first hash value, e, said digital signature (r, s), said base point, P, and said public key, Q, by using a second hash function, h, whose output value is shorter than that of said first hash function, H, said second hash value being independent of said message; and

verification result output means coupled to said first and second arithmetic means for comparing said hash value, r′

, with a tally, r, of said inputted digital signature to thereby obtain a result of verification of said inputted digital signature.

16. A digital signature verifying system according to claim 15,

wherein for verifying a digital signature (r₁, s₁) of a given message, M₁, said system comprises:

means for determining a hash value, e₁, satisfying a condition that e₁=H(M₁);

means for inputting a public key, Q₁, generated previously so as to satisfy a condition Q₁,=d₁P, where d₁ represents a private key, said public key, Q₁, having been registered;

means for determining arithmetically an element, R₁, of an abelian group, said element, R₁, being given by R₁=s₁P−

(e₁+r₁)Q₁;

means for determining a hash value, r₁′

, satisfying a condition that r₁′

=h(R₁);

means for outputting a data indicating that said digital signature is authenticated, when said hash value, r₁′

, coincides with a tally, r₁, of said digital signature; and

means for outputting a data indicating that said digital signature is not authenticated, unless said hash value, r₁′

, coincides with said tally, r₁, of said digital signature.

17. A digital signature verifying system according to claim 16,

wherein said abelian group includes an elliptic curve.

18. A digital signature generating system for generating a multiple digital signature authenticating electronically signatures affixed to message and/or comments, M_i, as created and/or added sequentially by N users'"'"' units i (where i=1, . . . , N) by using a public key encryption scheme, comprising:

first processing means for determining for a given one of said messages, M_i, a first hash value, e_i, satisfying a condition that e=H(M₁) by using a first hash function, H;

second processing means for determining for a numerical value, x_i, obtained from translation of a random number and independent of said message a second hash value, r_i, satisfying a condition that r_i=h(x_i) by using a second hash function, h, whose output value is shorter than that of said first hash function, H, said second hash value being independent of said message;

third processing means for executing the processings of said first and second processing means for each of said users'"'"' units i (where i=1, . . . , N); and

arithmetic/output means for determining arithmetically said multiple digital signature on the basis of said hash values (e_i and r_i) determined by said third processing means.

19. A multiple digital signature generating system according to claim 18,

wherein for generating said multiple digital signature, each of said users'"'"' units i (i≧ 2) includes;

means for inputting said set of numerical values (x<sub>i−

1</sub>, y<sub>i−

1</sub>) obtained from the translation of random numbers;

means for computing a hash value given by e₁=H(M_i);

means for generating a random number k_i;

means for computing a point given by k₁P=(x, y);

means for computing a point given by (x₁, y₁)=(x<sub>i−

1</sub>, y<sub>i−

1</sub>)+(x, y);

means for computing a hash value given by r₁=h(x_i);

means for determining a numerical value, s, by using a private key, d_i, said numerical value, s_i, satisfying a condition given by $s_i=s_{i-1}+k_i+d_i<br><br>\left(e_i+\underset{k=i}{\overset{i}{\sum <br><br>}}<br><br>\text{\hspace{1em}<br><br>}<br><br>r_k\right)<br><br>\text{\hspace{1em}<br><br>}<br><br>\left(\mathrm{mod}<br><br>\text{\hspace{1em}<br><br>}<br><br>n\right);<br><br>$

 

and

means for outputting a set of determined numerical values (r₁, . . . , r_i, s_i) as the digital signature.

20. A digital signature verifying system for verifying a multiple digital signature authenticating electronically signatures affixed to messages and/or comments, M_i, as created and/or added sequentially by N users'"'"'s unit i (where i=1, . . . , N) by resorting to a public key encryption scheme, comprising:

first arithmetic means for determining for the inputted message, M_i, a first hash value, e_i, satisfying a condition that e_i=H(M_i) by using a first hash function, H;

second arithmetic means for determining for a numerical value, x_i, obtained by arithmetic operation of the inputted multiple digital signature (r_i, s_i), a public key, Q, and a base point, P, and independent of said message, a second hash value, r_i′

, satisfying a condition that r_i′

=h(x_i) on the basis of said first hash value, e_i, said digital signature (r_i, s_i), said base point, P, and said public key, Q, by using a second hash function, h, whose output value is shorter than that of said first hash function, H, said second hash value being independent of said message;

processing means for executing repetitionally the arithmetic operation of said first and second arithmetic means for each of said users'"'"'s units i (where i represents integers “

1”

to “

N”

inclusive, respectively); and

verifying means for comparing each of said hash values, r_i, determined by said processing means with each of said tallies, r, of said inputted multiple digital signature to thereby obtain results of verification of said inputted digital signature.

21. A multiple signature verifying system according to claim 20,

wherein for authenticating a multiple digital signature by users'"'"' units i (i≧ 2), each of said users'"'"' units includes;

means for inputting (i−

1) messages and/or comments (M₁, . . . , M<sub>i−

1</sub>) and (i−

1)-tuple digital signature (r₁, . . . , r<sub>i−

1</sub>, s<sub>i−

1</sub>) issued by an immediately preceding user'"'"'s units (i−

1);

means for repeating computation of hash values e_k=H(M_k), where k represents 1 to (i−

1);

means for inputting repetitionally public keys Q_k generated so as to satisfy a condition that Q_k=d_kP, where k represents 1 to (i−

1);

means for computing an element, R<sub>i−

1</sub>, of an abelian group in accordance with $\left(R_{i-1}\right)=S_{i-1}<br><br>P-\underset{k=1}{\overset{i-1}{\sum <br><br>}}<br><br>\text{\hspace{1em}<br><br>}<br><br>{\left(e_k+\underset{M=1}{\overset{k}{\sum <br><br>}}<br><br>\text{\hspace{1em}<br><br>}<br><br>r_m\right)}_{Q^k};<br><br>$

means for computing hash values r<sub>i−

1</sub>′

=h(R<sub>i−

1</sub>);

means for issuing data indicating that said multiple digital signature is authenticated

when said hash value, r<sub>i−

1</sub>′

, coincides with a tally, r<sub>i−

1</sub>, of said (i−

1)-tuple digital signature, and issuing data indicating that said multiple digital signature is not-authenticated unless said hash value, r<sub>i−

1</sub>′

, coincides with said tally, r<sub>i−

1</sub>.

22. A digital signature verifying system according to claim 21,

wherein said abelian group includes an elliptic curve.

23. A computer-readable recording medium for storing a program which is composed of instructions executed by a computer and which is for carrying out a method for generating a digital signature authenticating electronically a signature affixed to a given message, M, by resorting to a public key encryption scheme, said digital signature generating method comprising the steps of:

determining for said message, M, a first hash value, e, satisfying a condition that e=H(M) by using a first hash function, H;

determining for a numerical value, x, obtained from translation of a random number and independent of said message a second hash value, r, satisfying a condition that r=h(x) by using a second hash function, h, whose output value is shorter than that of said first hash function, H, said second hash value being independent of said message; and

arithmetically determining and outputting said digital signature by using said first hash value, e, and said second hash value, r, as determined.

24. A computer-readable recording medium for storing a program which is composed of instructions executed by a computer and which is for carrying out a method for verifying a digital signature authenticating electronically a signature affixed to a given message, M, by resorting to a public key encryption scheme, said digital signature generating method comprising the steps of:

determining for said message, M, a first hash value, e, satisfying a condition that e=H(M) by using a first hash function, H;

determining for a numerical value, x, obtained from arithmetic operation of an inputted digital signature (r, s), a public key, Q, and a base point, P, and independent of said message, a second hash value, r′

, satisfying a condition that r′

=h(x) on the basis of said first hash value, e, said digital signature(r, s), said base point, P, and said public key, Q, by using a second hash function, h, whose output value is shorter than that of said first hash function, H, said second hash value being independent of said message; and

comparing said hash value, r′

, with a tally, r, of said inputted digital signature to thereby obtain a result of verification of said inputted digital signature.

25. A method of generating and verifying a digital signature using a public key encryption scheme in a system in which a digital signature is generated by a given one computer and transmitted via a network to another computer to be verified thereby,

for generating a digital signature (r₁, s₁) for a given message, M₁, by said given one computer, said method comprises:

determining a hash value, e₁, satisfying a condition that e₁=H(M₁) by using a first hash function, H;

generating a random number, k₁;

determining a point, R₁, by multiplying an element, P, of an abelian group by said random number, k₁;

determining a first numerical value, r₁, satisfying a condition that r₁=h(R₁) and being determined independent of said message by using a second hash function, h, whose output value is shorter than that of said first hash function, H, said first numerical value being independent of said message;

determining a second numerical value, s₁ , satisfying a condition that s₁=k₁+d₁(e₁+r₁) (mod n) on the basis of the order, n, of said element, P, of said abelian group and a private key, d₁; and

sending a set of said determined numerical values (r₁, s₁) as a digital signature to said another computer via said network; and

for verifying said digital signature (r₁, s₁) by said another computer, said method comprises;

fetching said digital signature (r₁, s₁) sent from said given one computer, said element, P, a public key, Q, and order, n, from a public file;

determining a hash value, e₁, satisfying a condition that e₁=H(M₁);

inputting a public key, Q₁, generated previously so as to satisfy a condition Q₁=d₁P, where d₁ represents a private key;

determining arithmetically a point, R₁, of an abelian group, said point, R₁, being given by R₁=s₁P−

(e₁+r₁)Q₁;

determining a hash value, r₁′

, satisfying a condition that r₁′

=h(R₁);

outputting a data indicating that said digital signature is authenticated, when said hash value, r₁′

, coincides with a tally, r, of said digital signature; and

outputting data indicating that said digital signature is not authenticated unless said hash value, r₁′

, coincides with said tally, r₁, of said digital signature.