Method and apparatus for en-bloc verification of plural...

Electrical computers and digital processing systems: support – Multiple computer communication using cryptography – Particular communication authentication technique

Reexamination Certificate

Rate now

  [ 0.00 ] – not rated yet Voters 0   Comments 0

Details

C713S177000, C713S180000, C380S030000

Reexamination Certificate

active

06212637

ABSTRACT:

BACKGROUND OF THE INVENTION
The present invention relates to a method and apparatus which enable a verifier to conduct an en-bloc verification of individual, multiple or superimposed signatures electronically attached by a plurality of signers to one or more electronified documents in a system for decision making by circulating them to the signers. The invention also pertains to a recording medium with the verification method recorded thereon.
A typical digital signature scheme is one that utilizes the RSA cryptosystem (R. L. Rivest, et al., “A Method for Obtaining Digital Signatures and Public-Key Cryptosystems”, Communications of the ACM, Vol. 21, No. 2, pp.120-126 (1978)). The RSA cryptosystem is such as described below.
A signer A generates a signature key (d, N) and a verification key (e, N) so that they satisfy
N=P×Q
e×d≡1(mod L)
where L=LCM{(P−1), (Q−1)}
Then the signer A publishes the verification key while keeping the signature key in secret. In the above, LCM{a, b} represents the least common multiple of the integers a and b, and P and Qare assumed to be two large different prime numbers. Further, a≡b(mod L) represents that a-b is a multiple of L.
The RSA cryptosystem is a cryptosystem that bases its security on the difficulty in factorizing N into prime numbers when the N is large. It is difficult to compute the d-component of the secret signature key from the published verification key (N, e).
A verifier B keeps the verification key (e, N) of the signer A in combination with his identification information (ID). A trusted center may sometimes holds such verification keys in the form of a public information management directory.
A signature function D and averification function E are defined as follows:
D(
m
)=
m
d
mod N
E(
y
)=
y
e
mod N
It is possible to show that the following equation holds true for an integer m which satisfies 0≦m<N.
E(D(
m
))=
m
where a mod N represents the remainder that results from the division of a by N.
The digital signature scheme utilizing the RSA cryptosystem is such as described below. The signer A generates f(m) from a document m using a one-way function f, then adds thereto a signature y=D(f(m)) using the secret signature function D, and sends a combination (ID, m, y) of his identification information (ID), the document m and the signature y as a signed message to the verifier B.
The verifier B retrieves the verification key information (e, N) of the signer A from the public information management file using the signer's identification information ID as the key therefor, then computes E(y)=y
e
mod N from the y-component of the signed message through the use of the retrieved verification key information (e, N), nd makes a check to see if E(y) matches f(m) derived from m using he one-way function f. If E(y)=f(m), then the verifier B judges that the sender is the genuine signer A and that the signed message (ID, m, y) has not been forged, because it is only the true signer A that knows the signature function D(m)=m
d
mod N, i.e. the aforementioned d-component.
The one-way function f mentioned herein is a function with which it is easy to calculate f(x) from x but it is difficult to obtain x from f(x). The one-way function f can be set up using a traditional high-speed encryption system, for example, a DES cryptosystem (Data Encryption Standard, Federal Information Processing Standards Publication 46, 1977). With the use of high-speed components, the time for computing the function f would substantially be negligible. The one-way function recited hereinafter is such one that can calculated a value for an x of an arbitrary data-length.
The integer N for use in the RSA cryptosystem is usually decimal 308 digits (1024 bits) or so in length. The d-component of the signature key is also about 1024-bit long. It is well-known in the art that a square-and-multiply algorithm is used to calculate the signature function D. The computation of a 308-digit integer (including a modular N calculation) needs to be performed on an average of 1536 times, imposing a heavy computational load on the signer A for signature generation.
The square-and-multiply algorithm for computing x
a
mod N is such as described below.
Step S1: z=1
Step S2: The following steps S2-1 and S2-2 are repeated until a numerical subscript i becomes |a|−1 from 0 (Assume that |a| represents the number of bits of a).
Step S2-1: z′=z
2
mod N
Step S2-2: if a
i
=1, update z with z=z′x mod N (a
i
being a value, 0 or 1, of an i-th bit of a), and return to step S2-1.
If a
i
=0, return to step S2-1 without updating z.
Step S3: z is output.
(The square-and-multiply algorithm is described, for example, in Douglas R. Stinson, “CRYPTOGRAPHY, Theory and Practice,” CRC, Press p127, 1995
With a view to solving the problem of increased computational load on the signer apparatus for signature generation, there have been proposed interactive proofs (typical examples of which are a Fiat-Shamir and a Schnorr scheme) (A. Fiat and A. Shamir, “How to prove yourself: practical solutions to identification and signature problems,” Advances in Cryptology-Crypto 86, Springer-Verlag, pp. 186-194; C. P. Schnorr, “Efficient Identification and Signatures for smart Card,” Advances in Cryptology-EUROCRYPT7 89, springer-verlag, pp. 235-251; and M. Tompa and H. Woll, “Random Self-Reducibility and Zero Knowledge Interactive Proofs of Possession of Information,” Proceedings of the 28th IEEE Symposium on the Foundation of Computer Science, pp. 472-482 (1987)).
A description will be given of a digital signature by the Schnorr scheme.
A trusted center publishes two large primes p and q which bear a relation that q is a measure of p−1, and an integer g&egr;(Z/pZ)*={1, 2, . . . , p−1} which has an order q.
Step S1: The signer A generates a random number s&egr;(Z/qZ)={0, 1, 2, . . . q−1}, then computes public information I by
 I=
g
s
mod p  (1)
and publishes a pair of identification information (ID) and information I.
The signer A goes through the following procedure to prove to the verifier B that the document or message m is true or genuine.
Step S2: The signer A generates a random number r&egr;(Z/qZ), and computes
X=
g
r
mod p  (2)
Step S3: The signer A computes an integer e&egr;(Z/qZ) by the following equation using the one-way function f.
e=f
(X,
m
)  (3)
Step S4: The signer A generates the signature y by
y=r+er
mod q  (4)
and sends {ID, m, X, y} as a signed message to the verifier B.
Step S5: The verifier B computes the integer e&egr;(Z/qZ) using the one-way function f by
e=f
(X,
m
)  (5)
Step S6: The verifier B makes a check to see if the following equation holds true.
g
y
≡XI
e
(mod p)  (6)
where I is public information corresponding to the identification information ID.
As is seen from the way of generating the signature y, g
y
≡g
r
(g
s
)
e
≡XI
e
(mod p); hence, when Eq. (6) holds true, then the verifier B recognizes the document m as duly sent from the signer A.
In steps S2 through S4 described above, the signature of the signer could be forged if {ID, X, m, y} were sent as a signed message when the integer e&egr;(Z/qZ), with which e=f(X, m) would hold, could be found by calculating X&egr;(Z/pZ)*, which would satisfy Eq. (6), after suitably choosing the integers e&egr;(Z/qZ) and y&egr;(Z/qZ). Since the probability with which the verification equation e=f(m, X) holds true is 1/q, however, the computational complexity involved in the forgery of signature depends on the value q. In the following description the number of bits of the prime p will be represented by |p|.
With the Schnorr scheme, the signature generation processing by the sender involves a multiplication (including modular p cal

LandOfFree

Say what you really think

Search LandOfFree.com for the USA inventors and patents. Rate them and share your experience with other people.

Rating

Method and apparatus for en-bloc verification of plural... does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Method and apparatus for en-bloc verification of plural..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method and apparatus for en-bloc verification of plural... will most certainly appreciate the feedback.

Rate now

     

Profile ID: LFUS-PAI-O-2542688

  Search
All data on this website is collected from public sources. Our data reflects the most accurate information available at the time of publication.