Digital signature method using an elliptic curve, a digital signature system, and a program storage medium having the digital signature method stored therein

• US 6,088,798 A
• Filed: 09/26/1997
• Issued: 07/11/2000
• Est. Priority Date: 09/27/1996
• Status: Expired due to Fees

• Current Assignee: Kabushiki Kaisha Toshiba (Toshiba Corporation)
• Original Assignee: Kabushiki Kaisha Toshiba (Toshiba Corporation)
• Inventors: Shimbo, Atsushi
• Primary Examiner(s): Swann, Tod R.
• Assistant Examiner(s): Darrow, Justin T.
• Application Number:
  US08/938,958
• Time in Patent Office: 1,019 Days
• Field of Search: 713/100, 713/170, 713/176, 713/180, 380/23, 380/28, 380/30
• US Class Current: 713/176
• 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 method comprises the signature data generating step of, by the use of system information including an elliptic curve E/Fq over a finite field and a base point G on the elliptic curve E/Fq, a signer'"'"'s public key Y defined by a point on the elliptic curve E/Fq, and the signer'"'"'s secret key x generated so as to fulfill the public key Y=x·G, generating signature data including not only at least part of data on a point R on the elliptic curve E/Fq dependent on an arbitrarily generated random number k and the base point G on the elliptic curve E/Fq but also an integer s dependent on the plaintext data M, secret key x, and random number k, and the signature checking step of, by the use of an integer m dependent only on the plaintext data M, an integer r dependent on at least the point R of the point R on the elliptic curve E/Fq and the plaintext data M, at least part of data on the point R and the integer s that constitute the signature data, and the system information, and the signer'"'"'s public key Y, checking a signature by using a relational equation defined as ±s·G=±m·Y±r·R over E/Fq (where the + and - signs are determined by a specific condition) or a relational equation equivalent to the above relational equation as a signature checking equation.

Claims

1. A digital signature method for generating digital signature data for plaintext data M and checking a signature on the basis of the digital signature data, said digital signature method comprising the steps of:

generating signature data satisfying public key Y=x·

G including at least part of data on a point R of an elliptic curve E/Fq over a finite field Fq dependent on an arbitrarily generated random number k, base point G on the elliptic curve E/Fq, and an integer s dependent on the plaintext data M, secret key x, and the random number k; and

checking a signature by confirming that a relational equation defined as

space="preserve" listing-type="equation">±

s·

G=±

m·

Y±

r·

R over E/Fq

is satisfied, wherein

s and R constitute the signature data, m is an integer dependent only on the plaintext data M, and r is an integer dependent on at least point R of the elliptic curve E/Fq.

2. A digital signature method for generating digital signature data for plaintext data M and checking a signature on the basis of the digital signature data, said digital signature method comprising the steps of:

generating signature data satisfying public key Y=x·

G including at least part of data on a point R of an elliptic curve E/Fq over a finite field Fq dependent on an arbitrarily generated random number k, base point G on the elliptic curve E/Fq, and an integer s dependent on the plaintext data M, secret key x, and the random number k; and

checking a signature by confirming that a relational equation defined by an arithmetic operation between a first term s·

G, a second term m·

Y, and a third term r·

R

is satisfied, wherein

s and R constitute the signature data, m is an integer dependent only on the plaintext data M, and r is an integer dependent on at least point R of the elliptic curve E/Fq.

3. A digital signature method for generating digital signature data for plaintext data M among n number of signers and checking a signature on the basis of the digital signature data, said digital signature method comprising the steps of:

generating signature data satisfying public key Y_i =x_i ·

G for (i=1,2,3, . . . n) including at least part of data on a point R of an elliptic curve E/Fq over a finite field Fq dependent on random number k_i generated for each of the signers, base point G on the elliptic curve E/Fq, and an integer s dependent on the plaintext data M, secret key x_i, and the random number k_i ; and

checking a signature by confirming that a relational equation defined as

space="preserve" listing-type="equation">±

s·

G=±

m·

(Y.sub.1 +Y.sub.2 + . . . +Y.sub.n)±

r·

R over E/Fq

is satisfied, wherein

s and R constitute the signature data, m is an integer dependent only on the plaintext data M, and r is an integer dependent on at least point R of the elliptic curve E/Fq.

4. A digital signature method for generating digital signature data for plaintext data M among n number of signers and checking a signature on the basis of the digital signature data, said digital signature method comprising the steps of:

generating signature data satisfying public key Y_i =x_i ·

G for (i=1, 2, 3, . . . , n) including at least part of data on a point R of an elliptic curve E/Fq over a finite field Fq dependent on random number k_i generated for each of the signers, base point G on the elliptic curve E/Fq, and an integer s dependent on the plaintext data M, secret key x_i for each of the signers, and each random number k_i ; and

checking a signature by confirming that a relational equation defined by an arithmetic operation between a first term s·

G, a second term m·

(Y₁ +Y₂ + . . . +Y_n), and a third term r·

R

is satisfied, wherein

s and R constitute the signature data, m is an integer dependent only on the plaintext data M, and r is an integer dependent on at least point R of the elliptic curve E/Fq.

5. A digital signature method for generating digital signature data for plaintext data M among n number of signers and checking a signature on the basis of the digital signature data, said digital signature method comprising the steps of:

generating signature data satisfying public key Y_i =x_i ·

G for (i=1, 2, 3, . . . , n) including at least part of data on a point R_i of an elliptic curve E/Fq over a finite field Fq dependent on random number k_i generated for each of the signers, base point G on the elliptic curve E/Fq, and an integer s dependent on the plaintext data M, secret key x_i for each of the signers, and each random number k_i ; and

checking a signature by confirming that a relational equation defined by an arithmetic operation between a first term s·

G, a second term m·

(Y₁ +Y₂ + . . . +Y_n), and a third term (r₁ ·

R₁ +r₂ ·

R₂ + . . . +r_n ·

R_n) is satisfied, wherein

s and R constitute the signature data, m is an integer dependent only on the plaintext data M, and r is an integer dependent on at least point R of the elliptic curve E/Fq.

6. A digital signature system for generating digital signature data for plaintext data M and for checking a signature based on the digital signature data, comprising:

a signature data generating device comprising means for generating signature data satisfying public key Y=x·

G including at least part of data on a point R of an elliptic curve E/Fq over a finite field Fq dependent on an arbitrarily generated random number k, base point G on the elliptic curve E/Fq, and an integer s dependent on the plaintext data M, secret key x, and the random number k; and

a signature checking device comprising means for checking a signature by confirming that a relational equation defined by a specific arithmetic operation between a first term s·

G, a second term m·

Y, and a third term r·

R is satisfied, wherein

s and R constitute the signature data, m is an integer dependent only on the plaintext data M, and r is an integer dependent on at least point R of the elliptic curve E/Fq.

7. A digital signature system for generating digital signature data for plaintext data M among n number of signers and for checking a signature on the basis of the digital signature data, comprising:

a signature data generating device comprising means for generating signature data satisfying public key Y_i =x_i ·

G for (i=1, 2, 3, . . . n) including at least part of data on a point R of an elliptic curve E/Fq over a finite field Fq dependent on a random number k_i generated for each of the signers, base point G on the elliptic curve E/Fq, and an integer s dependent on the plaintext data M, secret key x_i for each of the signers, and each random number k_i ; and

a signature checking device comprising means for checking a signature by confirming that a relational equation defined by an arithmetic operation between a first term s·

G, a second term m·

(Y₁ +Y₂ + . . . +Y_n), and a third term r·

R is satisfied, wherein

s and R constitute the signature data, m is an integer dependent only on the plaintext data M, and r is an integer dependent on at least point R of the elliptic curve E/Fq.

8. A digital signature system for generating digital signature data for plaintext data M among n number of signers and for checking a signature on the basis of the digital signature data, comprising:

a signature data generating device comprising means for generating signature data satisfying public key Y_i =x_i ·

G for (i=1, 2, 3, . . . n) including at least part of data on a point R_i of an elliptic curve E/Fq over a finite field Fq dependent on random number k_i generated for each of the signers, base point G on the elliptic curve E/Fq, and an integer s dependent on the plaintext data M, secret key x_i for each of the signers, and each random number k_i ; and

a signature checking device comprising means for checking a signature by confirming that a relational equation defined by an arithmetic operation between a first term s·

G, a second term m·

(Y₁ +Y₂ + . . . +Y_n), and a third term (r₁ ·

R₁ +r₂ ·

R₂ + . . . +r_n ·

R_n) is satisfied, wherein

s and R constitute the signature data, m is an integer dependent only on the plaintext data M, and r is an integer dependent on at least point R of the elliptic curve E/Fq.

9. A computer program storage device including a computer readable medium tangibly embodying a set of instructions from controlling a computing unit to perform a method for generating digital signature data for plaintext data M and checking a signature on the basis of the digital signature data, comprising the steps of:

generating signature data satisfying public key Y=x·

G including at least part of data on a point R of an elliptic curve E/Fq over a finite field Fq dependent on an arbitrarily generated random number k, base point G on the elliptic curve E/Fq, and an integer s dependent on the plaintext data M, secret key x, and the random number k; and

checking a signature by confirming that a relational equation defined by an arithmetic operation between a first term s·

G, a second term m·

Y, and a third term r·

R is satisfied, wherein

s and R constitute the signature data, m is an integer dependent only on the plaintext data M, and r is an integer dependent on at least point R of the elliptic curve E/Fq.

10. A computer program storage device including a computer readable medium tangibly embodying a set of instructions from controlling a computing unit to perform a method for generating digital signature data for plaintext data M and checking a signature on the basis of the digital signature data, comprising the steps of:

generating signature data satisfying public key Y_i =x_i ·

G for (i=1, 2, 3, . . . , n) including at least part of data on a point R of an elliptic curve E/Fq over a finite field Fq dependent on random number k_i generated for each of the signers, base point G on the elliptic curve E/Fq, and an integer s dependent on the plaintext data M, secret key x_i for each of the signers, and each random number k_i ; and

checking a signature by confirming that a relational equation defined by an arithmetic operation between a first term s·

G, a second term m·

(Y₁ +Y₂ + . . . +Y_n), and a third term r·

R is satisfied, wherein

s and R constitute the signature data, m is an integer dependent only on the plaintext data M, and r is an integer dependent on at least point R of the elliptic curve E/Fq.

11. A computer program storage device including a computer readable medium tangibly embodying a set of instructions from controlling a computing unit to perform a method for generating digital signature data for plaintext data M and checking a signature on the basis of the digital signature data, comprising the steps of:

generating signature data satisfying public key Y_i =x_i ·

G for (i=1, 2, 3, . . . , n) including at least part of data on a point R_i of an elliptic curve E/Fq over a finite field Fq dependent on random number k_i generated for each of the signers, base point G on the elliptic curve E/Fq, and an integer s dependent on the plaintext data M, secret key x_i for each of the signers, and each random number k_i ; and

checking a signature by confirming that a relational equation defined by an arithmetic operation between a first term s·

G, a second term m·

(Y₁ +Y₂ + . . . +Y_n), and a third term (r₁ ·

R₁ +r₂ ·

R₂ + . . . +r_n ·

R_n) is satisfied, wherein

s and R constitute the signature data, m is an integer dependent only on the plaintext data M, and r is an integer dependent on at least point R of the elliptic curve E/Fq.

12. A digital signature system for generating digital signature data for plaintext data M and for checking a signature based on the digital signature data, comprising:

a computing unit configured to generate signature data satisfying public key Y=x·

G including at least part of data on a point R of an elliptic curve E/Fq over a finite field Fq dependent on an arbitrarily generated random number k, base point G on the elliptic curve E/Fq, and an integer s dependent on the plaintext data M, secret key x, and the random number k, and to check a signature by confirming that a relational equation defined by a specific arithmetic operation between a first term s·

G, a second term m·

Y, and a third term r·

R is satisfied, wherein

s and R constitute the signature data, m is an integer dependent only on the plaintext data M, and r is an integer dependent on at least point R of the elliptic curve E/Fq.

13. A digital signature system for generating digital signature data for plaintext data M among n number of signers and for checking a signature on the basis of the digital signature data, comprising:

a computing unit configured to generate signature data satisfying public key Y_i =x_i ·

G for (i=1, 2, 3, . . . n) including at least part of data on a point R of an elliptic curve E/Fq over a finite field Fq dependent on an random number k_i generated for each of the signers, base point G on the elliptic curve E/Fq, and an integer s dependent on the plaintext data M, secret key x_i for each of the signers, and each random number k_i, and to check a signature by confirming that a relational equation defined by an arithmetic operation between a first term s·

G, a second term m·

(Y₁ +Y₂ + . . . +Y_n), and a third term r·

R is satisfied, wherein

s and R constitute the signature data, m is an integer dependent only on the plaintext data M, and r is an integer dependent on at least point R of the elliptic curve E/Fq.

14. A digital signature system for generating digital signature data for plaintext data M among n number of signers and for checking a signature on the basis of the digital signature data, comprising:

a computing unit configured to generate signature data satisfying public key Y₁ =x_i ·

G for (i=1, 2, 3, . . . n) including at least part of data on a point R_i of an elliptic curve E/Fq over a finite field Fq dependent on random number k_i generated for each of the signers, base point G on the elliptic curve E/Fq, and an integer s dependent on the plaintext data M, secret key x_i for each of the signers, and each random number k_i, and to check a signature by confirming that a relational equation defined by an arithmetic operation between a first term s·

G, a second term m·

(Y₁ +Y₂ + . . . +Y_n), and a third term (r₁ ·

R₁ +r₂ ·

R₂ + . . . +r_n ·

R_n) is satisfied, wherein

s and R constitute the signature data, m is an integer dependent only on the plaintext data M, and r is an integer dependent on at least point R of the elliptic curve E/Fq.