Digital signature generating/verifying method and system using public key encryption
First Claim
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.
1 Assignment
0 Petitions
Accused Products
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.
-
Citations
25 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. - View Dependent Claims (2, 3)
wherein for generating a digital signature (r1, s1) for a given message, M1, said method comprises the steps of: determining a hash value, e1, satisfying a condition that e1=H(M1) by using said first hash function, H;
generating a random number, k1;
determining an element, R1, by multiplying an element, P, of an abelian group by said random number, k1;
determining a first numerical value, r1, satisfying a condition that r1=h(R1) 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, s1, satisfying a condition that s1=k1+d1(e1+r1) (mod n) by using the order, n, of said element, P, of said abelian group and a private key, d1; and
outputting a set of said determined numerical values (r1, s1) 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.- View Dependent Claims (5, 6)
wherein for verifying a digital signature (r1, s1 ) of a given message, M1, said method comprises the steps of: determining a hash value, e1, satisfying a condition that e1=H(M1);
inputting a public key, Q1, generated previously so as to satisfy a condition Q1=d1P, where d1 represents a private key, said public key, Q1, having been registered;
determining arithmetically a point, R1, of an abelian group, said point, R1, being given by R1=s1P−
(e1+r1) Q1;
determining a hash value, r1′
, satisfying a condition that r1′
=h(R1);
outputting a data indicating that said digital signature is authenticated, when said hash value, r1′
, 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, r1′
, coincides with said tally, r1, 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, Mi, 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, Mi, a first hash value, ei, satisfying a condition that ei=H(Mi) by using a first hash function, H;
(b) determining for a numerical value, xi, obtained from translation of a random number and independent of said message a second hash value, ri, satisfying a condition that ri=h(xi) by using a second hash function, h, whose output value is shorter than that of said first hash function, H, wherein the value ri 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 (ei and ri) determined in said step (c). - View Dependent Claims (8, 9, 10)
wherein for generating said multiple digital signature by user i (i≧ - 2), said method comprises the steps of;
inputting a set of numeric values (xi−
1, yi−
1) obtained from translation of random numbers;
computing a hash value ei=H(Mi);
generating a random number ki;
computing a point kiP=(x, y);
computing a point (xi, yi)=(xi−
1, yi−
1)+(x, y);
computing a hash value ri=h(xi);
determining by using a private key, di, a tally, si, satisfying a condition given by the following expression;
andoutputting a set of numerical values (r1, . . . , ri, si) as said multiple digital signature, wherein the value si 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 (M1, . . . Mi−
1) and (i−
1)-tuple digital signature (ri, . . . , ri−
1, si−
1) issued by an immediately preceding user (i−
1);
repeating computation of hash values ek=H(Mk), where k represents 1 to (i−
1);
inputting repetitionally public keys Qk generated so as to satisfy a condition that Qk=dkP, where k represents 1 to (i−
1);
computing an element (Ri−
1) of an abelian group in accordance with
computing a hash value (r′
i−
1=h(Ri−
1);
issuing data indicating “
authenticated”
when said hash value, ri−
1′
, coincides with a tally, ri−
1, of said (i−
1)-tuple digital signature; and
issuing data indicating “
not-authenticated”
unless said hash value, ri−
1′
, coincides with said tally, ri−
1.
- 2), said method comprises the steps of;
-
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, Mi, 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, Mi, a first hash value, ei, satisfying a condition that ei=H(Mi) by using a first hash function, H;
(b) determining for a numerical value, xi, obtained by arithmetic operation of an inputted multiple digital signature (ri, si), a public key, Q, and an element, P, and independent of said message, a second hash value, ri′
, satisfying a condition that ri′
=h(xi) on the basis of said first hash value, ei, said digital signature (ri, si), 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, ri′
, 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. - View Dependent Claims (13, 14)
wherein for generating a digital signature (r1, s1) for a given message, M1, said system comprises: means for determining a hash value, e1, satisfying a condition that e1=H(M1) by using the first hash function, H;
means for generating a random number, k1;
means for determining an element, R1, by multiplying an element P, of the abelian group by said random number, k1;
means for determining a first numerical value, r1, satisfying a condition that r1=h(R1) 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, s1, satisfying a condition that s1=k1+d1(e1+r1) (mod n) by using order, n1, of said element, P, of the abelian group and a private key, d1; and
means for outputting a set of said determined numerical values (r1, s1) 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.- View Dependent Claims (16, 17)
wherein for verifying a digital signature (r1, s1) of a given message, M1, said system comprises: means for determining a hash value, e1, satisfying a condition that e1=H(M1);
means for inputting a public key, Q1, generated previously so as to satisfy a condition Q1,=d1P, where d1 represents a private key, said public key, Q1, having been registered;
means for determining arithmetically an element, R1, of an abelian group, said element, R1, being given by R1=s1P−
(e1+r1)Q1;
means for determining a hash value, r1′
, satisfying a condition that r1′
=h(R1);
means for outputting a data indicating that said digital signature is authenticated, when said hash value, r1′
, coincides with a tally, r1, of said digital signature; and
means for outputting a data indicating that said digital signature is not authenticated, unless said hash value, r1′
, coincides with said tally, r1, 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, Mi, 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, Mi, a first hash value, ei, satisfying a condition that e=H(M1) by using a first hash function, H;
second processing means for determining for a numerical value, xi, obtained from translation of a random number and independent of said message a second hash value, ri, satisfying a condition that ri=h(xi) 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 (ei and ri) determined by said third processing means. - View Dependent Claims (19)
wherein for generating said multiple digital signature, each of said users'"'"' units i (i≧ - 2) includes;
means for inputting said set of numerical values (xi−
1, yi−
1) obtained from the translation of random numbers;
means for computing a hash value given by e1=H(Mi);
means for generating a random number ki;
means for computing a point given by k1P=(x, y);
means for computing a point given by (x1, y1)=(xi−
1, yi−
1)+(x, y);
means for computing a hash value given by r1=h(xi);
means for determining a numerical value, s, by using a private key, di, said numerical value, si, satisfying a condition given by
andmeans for outputting a set of determined numerical values (r1, . . . , ri, si) 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, Mi, 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, Mi, a first hash value, ei, satisfying a condition that ei=H(Mi) by using a first hash function, H;
second arithmetic means for determining for a numerical value, xi, obtained by arithmetic operation of the inputted multiple digital signature (ri, si), a public key, Q, and a base point, P, and independent of said message, a second hash value, ri′
, satisfying a condition that ri′
=h(xi) on the basis of said first hash value, ei, said digital signature (ri, si), 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, ri, 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. - View Dependent Claims (21, 22)
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 (M1, . . . , Mi−
1) and (i−
1)-tuple digital signature (r1, . . . , ri−
1, si−
1) issued by an immediately preceding user'"'"'s units (i−
1);
means for repeating computation of hash values ek=H(Mk), where k represents 1 to (i−
1);
means for inputting repetitionally public keys Qk generated so as to satisfy a condition that Qk=dkP, where k represents 1 to (i−
1);
means for computing an element, Ri−
1, of an abelian group in accordance withmeans for computing hash values ri−
1′
=h(Ri−
1);
means for issuing data indicating that said multiple digital signature is authenticated when said hash value, ri−
1′
, coincides with a tally, ri−
1, of said (i−
1)-tuple digital signature, and issuing data indicating that said multiple digital signature is not-authenticated unless said hash value, ri−
1′
, coincides with said tally, ri−
1.
-
-
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 (r1, s1) for a given message, M1, by said given one computer, said method comprises: -
determining a hash value, e1, satisfying a condition that e1=H(M1) by using a first hash function, H;
generating a random number, k1;
determining a point, R1, by multiplying an element, P, of an abelian group by said random number, k1;
determining a first numerical value, r1, satisfying a condition that r1=h(R1) 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, s1 , satisfying a condition that s1=k1+d1(e1+r1) (mod n) on the basis of the order, n, of said element, P, of said abelian group and a private key, d1; and
sending a set of said determined numerical values (r1, s1) as a digital signature to said another computer via said network; and
for verifying said digital signature (r1, s1) by said another computer, said method comprises;
fetching said digital signature (r1, s1) sent from said given one computer, said element, P, a public key, Q, and order, n, from a public file;
determining a hash value, e1, satisfying a condition that e1=H(M1);
inputting a public key, Q1, generated previously so as to satisfy a condition Q1=d1P, where d1 represents a private key;
determining arithmetically a point, R1, of an abelian group, said point, R1, being given by R1=s1P−
(e1+r1)Q1;
determining a hash value, r1′
, satisfying a condition that r1′
=h(R1);
outputting a data indicating that said digital signature is authenticated, when said hash value, r1′
, coincides with a tally, r, of said digital signature; and
outputting data indicating that said digital signature is not authenticated unless said hash value, r1′
, coincides with said tally, r1, of said digital signature.
-
Specification