JP3331487B2 - Document information and user validity authentication method and system - Google Patents

Description

DETAILED DESCRIPTION OF THE INVENTION

[0001]

BACKGROUND OF THE INVENTION 1. Field of the Invention The present invention relates to a method and system for authenticating document information and a user's validity, and more particularly to a method for authenticating document information and a user's validity for guaranteeing whether or not the document information has been tampered with. And systems.

[0002]

2. Description of the Related Art As a typical example of an authentication method, an RSA encryption system (Rivest. RL et al. "A method for Obtaining"
Digital Signatures and Public-Key Cryptosystems ",
Communications of the ACM, Vol. 21, No2, pp.120-12
6, (1978)). The RSA encryption system is as follows.

[0005] The user apparatus A converts the signature key (d, N) and the inspection key (e, N) into N = P × Q e × d≡1 (mod L) (where P and Q are prime numbers, L = LCM ｛(P−1),
(Q-1)｝) are generated so as to satisfy, and the inspection key (e,
N) is made public and the signature key (d, N) is secretly managed.

Here, LCM {a, b} is an integer a and b
, P and Q are two different large prime numbers. A≡b (mod L) indicates that a−b is a multiple of L. The RSA cryptosystem is a cryptosystem having a security basis that it is difficult to perform prime factorization of N when N is large, and converts the d component of a secret signature key from a public inspection key (e, N). It is difficult to ask.

[0005] The signature verification device B manages the inspection key (e, N) of the user device as an inspection key file in combination with personal identification information (ID). When the signature function D and the check function E are defined by D (P) = P ^d (mod N) E (C) = C ^e (mod N), E (D ( It can be seen that P)) = P holds. “A (mod N)” means that a is N
Represents the remainder when divided by.

[0006] The authentication method using the RSA encryption system is as follows. The signature generation device A applies a secret signature function D to f (m) generated from the document information m using the one-way function f, and generates a signature sentence C by C = D (f (m)). Then, a combination (ID, m, C) of the personal identification information ID, the document information m, and the signature text C is transmitted to the authentication device B as a signed communication text.

The signature verification apparatus B searches the inspection key file using the ID as a key to obtain an inspection function E, obtains a decrypted text from the C component of the signed communication message using E (C), and obtains the decrypted text from the document information m. It is checked whether it matches the one-way function f (m). E
If (C) = f (m) holds, since only the true user A performs the signature function D, the sender is the real A, and (ID, m, C) is falsified. Judge that there is no.

Here, f is a one-way function, and the function f
This function is easy to calculate (x), but difficult to find x from f (x). The function f is a high-speed conventional encryption device, for example, DES encryption (Data Encryption Standard F
ederal Information ProcessingStandards Publication
46, 1977). If high-speed components are used, the calculation time of the one-way function f can be almost ignored.

The integer N used in the RSA encryption is usually about 200 decimal digits (500 bits), and the d component of the signature key is also about 500 bits. Here, to calculate the signature function D, even if the fast exponential calculation method is used, 200
The multiplication of integers of digits (including the remainder calculation by the modulus N) requires 768 times on average, and there is a problem that the amount of processing for generating a signature sentence in the signature generation apparatus A is large. Ikeno, Koyama: Modern Cryptographic Theory, "IEICE, pp. 16-17, (1986).)

As a method for solving the problem of increasing the number of signatures to be processed by the signature generation device, there is a method of Fiat and Shamir (Fiat, A. and Shamir, A: "How to prove yourself:
practical solutions to identification and signatu
re problems ". Proceedingsof Crypto 86, Santa Barba
ra, August 1986, pp.18-1-18-7). The authentication methods of Fiat and Shamir are as follows. Here, a digital signature will be described.

A reliable center generates k pieces of secret information s _j (1 ≦ j ≦ k) in the following procedure for a user device using an ID as personal identification information (k is a parameter for determining security). And 1 or more). Step 1) Calculate v _j = f (ID, j) (1 ≦ j ≦ k) using the one-way function f.

Step 2) The reciprocal of (mod N) is calculated for v _j , and (mod N) is calculated using the prime factors P and Q of N.
Square root in

[0013]

(Equation 1)

Is calculated. That is, s _j ² = 1 / v _j (mo
d N). Step 3) k pieces of secret information s _j are secretly issued to the user device, and the combined number N is made public. The calculation method of the reciprocal in “(mod N)” is shown, for example, in Ikeno and Koyama—Modern Cryptography, IEICE, pp. 17-18 (1986). , N can be performed only when the prime factors (P and Q) are known, for example, by the method described in Rabin, Mo: "Digitalized Signature.
s and Public-Key Functions as Intractable as Facto
rization ", Tech. Rcp. MIT / LCS / TR-212 MIT Lab. Comp
ut. Sci. 1979. A specific configuration example of the square root calculator is disclosed in Japanese Patent Laid-Open Publication No. Sho 63-2
6137).

The signature generation device A certifies to the signature verification device B that the document information m is genuine in the following procedure. Step 10) The signature generation device A generates a random number r _i and calculates x _i = r _i ² (mod N) (1 ≦ i ≦ t) (t is a parameter for determining security and a value of 1 or more) ).

Step 11) Signature generation device A is 0, 1
Bit sequence e _ij a (1 ≦ i ≦ t, 1 ≦ j ≦ k) using a one-way function f, calculated in _{(e ij, ..., e tk} ) = f (m, x 1, ..., x t) I do. Step 12) The signature device A sends the signature sentence y _i (1 ≦ i ≦
t)

[0017]

(Equation 2)

, ID, m, e ₁₁ ,...
_{et tk} , y _i ,..., y _t } are sent to the signature verification device B. Step 13) The signature verification device B determines that v _j = f (ID,
j) Calculate (1 ≦ j ≦ k). Step 14) The signature verification device B

[0019]

(Equation 3)

Is calculated. Step 15) The signature verification device B (e)_1i , ..., e
_tk ) = F (m, z ₁, ..., z_t)
inspect. Signature component y_iFrom how to make

[0021]

(Equation 4)

Therefore, if the above inspection is passed,
The signature verification device B recognizes that the document information m has been transmitted from the signature generation device A. At this time, the bit string (e ₁₁
, ..., e _tk) and y _1, ..., x ₁ from Decide y _t,
.., X _t are calculated and if (e ₁₁ ,..., _Et k) = f (m, x ₁ ,..., X _t ) holds, then ｛ID, m, e _{11 ,.
If 1} , ..., y _t } is a signature, the signature is successfully forged. Check formula (e ₁₁ ,..., _Et k) = f (m, x ₁ ,.
_{Since the} probability that _t ) is satisfied is 1/2 ^kt , the amount of calculation required for forging a signature is considered to be proportional to 2 ^kt . Hereinafter, the calculation amount required for forgery is referred to as a safety factor. here,
k is the number of secret information (s _j ) secretly managed by the user device, and t defines the data amount of the message.

In the Fiat and Shamir scheme, the signature generation process at the sender can be performed on average by t (k + 2) / 2 multiplications (including the remainder calculation in the modulus N). In particular,
In the above document of Fiat and Shamir, in the case of digital signature, it is recommended to select k = 18 and t = 4. Therefore, the number of times of multiplication by the signature method of Fiat and Shamir is 40, and
It can be seen that the processing amount can be significantly reduced as compared with the signature method using the RSA encryption (40/768 = 0.05,
It can be realized with a throughput of about 5%).

[0024]

However, the above-mentioned conventional authentication method using the RSA encryption has a problem that the redundancy of the message is small and the amount of information managed secretly is small, but the amount of processing at the sender is large. is there. Meanwhile, Fiat and Sh
In the amir method, the number of redundant bits in a message is 500 ×
t + k × t bits. In order to ensure security, it is necessary to select k and t of a certain size, so that the redundancy is increased. Also, the number of information managed by the sender in secret is k, which is k times as large as that of the RSA encryption.
As described above, although the processing amount at the sender is small, in order to obtain a sufficiently large security coefficient, there is a problem that the redundancy of the message is large and the amount of information managed secretly is large.

The present invention has been made in view of the above points, and has a small processing amount at a sender, a small redundancy of a message, and a document capable of reducing the amount of information secretly managed by the sender. It is an object of the present invention to provide a method and a system for authenticating information and the validity of a user. It is a further object of the present invention to provide an efficient document information and user authenticity authentication method and system that can reduce the amount of signature processing at the sender and at the same time reduce the redundancy of messages. .

[0026]

FIG. 1 is a diagram (part 1) for explaining the principle of the present invention. The present invention provides a method of authenticating document information for verifying the validity of the document information by analyzing the contents of the signature information transmitted by the signature generation device together with the document information, and confirming the validity of the document information. As information setting processing, the center device generates a prime number (P, Q) and keeps it secret, and obtains a product N (N = P × Q) of the prime numbers (P, Q) and k integers ｛L ₁ ,. , L _k ｝
(K ≧ 2) is disclosed as public information (N, {L ₁ ,..., L _k }) (steps 101 and 102). Further, when a user who uses an ID as an identifier joins the system,
K secret information {S ₁ ,..., S _k }
Using {L ₁ ,..., L _k } and secret P and Q,
The user device transmits the random number R to the user device as a signature generation process under the remainder operation modulo the prime product N (L = L ₁ ×... × L _k ). X = ^RL (mod N) to obtain a value X to be used in the inspection by the signature verification device, and use a one-way function f for the document information m and the value X to be signed, using a one-way function f. component _{(E 1, ..., E k} ) = f (m, X) is calculated, and further, secret information _{{S 1, ..., S k} } and the random number R and the first communication text component (E _1, ..., E _k ), the second message component (Y ₁ ,..., Y _k ) is calculated, and signed document information ｛ID, m, (E ₁ ,..., E _k ), (Y ₁ ,.
_k )｝ is generated and transmitted to the signature verification device (step 10).
4), the signature verification device selects any i that satisfies 1 ≦ i ≦ k
Also, when the values obtained from ID, Y _i and E _i match X, and the matching value is Z, if (E ₁ ,..., E _k ) = f (m, Z ) The validity of the document information transmitted by the user device is confirmed (step 105).

According to the present invention, in the above center device , as processing information setting processing at the time of system construction, prime numbers P and Q are generated by a prime number generator and held secretly, and a multiplier is used by a multiplier. Multiply the prime numbers P and Q, publish the product N and k integers {L ₁ ,..., L _k } (k ≧ 2) generated by the random number generator to the user device, and use the ID as an identifier. When a user joins the system, k pieces of secret information {S ₁ ,..., S _k } related to the ID are calculated by using a one-way function calculator, a reciprocal calculator and an L-th root calculator. , S = (1 / V _j ) ^{1 / Lj} (mod N) (where j is an integer representing 1 ≦ j ≦ k, and V _j = f (I
D, j)) and sends it to the user device.

Also,The user device of the present invention includes:Signature generation process
Random numbers generated using a random number generatorRSignature inspection from
Using a joint exponentiation unit for the value X used in the inspection
X = R^L (Mod N) (where L = L₁ × L_Two × L_k Toss
Calculated for the document information m and the value X to be signed.
By the one-way function calculator, (E₁ , ..., E_k ) = F (m, X)Random number R and public information ｛L ₁ , ..., L _k From｝ R _i = R ^{L / Li} (Mod N) (1 ≦ i ≦ k) And calculate Secret information $ S₁ , ..., S_k }WhenR _i WhenFirst
Correspondencecomponent(E₁ ,…,E_k ), Joint power
Using an arithmetic unit, Y_i = R_i × S_i  ^Ei (Mod N) (However, 1 ≦ i ≦
second integer from the integer that satisfies k)component(Y_i , ..., Y_k ) Calculate the
1 messagecomponent(E₁ ,…,E_k ) And the second messagecomponent
(Y_i , ..., Y_k ) With document information m and ID added
Named document information ｛ID, m, (E₁ , ..., E_k ), (Y
_i , ..., Y_k) Is generated and transmitted to the signature verification device.

Further, the signature verification apparatus of the present inventionUser clothing
PlaceFrom the signed document information ｛ID, m, (E₁ , ..., E
_k ), (Y_i , ..., Y_k ) When you receive｝, the one-way
Using a number calculator,V _i = F (ID, i) (where i satisfies 1 ≦ i ≦ k
Plus integer) And calculate Public information (N @ L ₁ , ..., L _k I) and users
The first message component (E) received from the device ₁ , ..., E
_k ), The second message component (Y _i , ..., Y _k ) And documents
From the information m Using a joint exponentiation unit, Z_i = Y_i ^Li× V_i ^Ei (Mod N) and Z₁ = …… = Z_k Consists of
It is checked whether it stands or not, and w = f
(M, Z₁ , ..., Z_k ) Is calculated, and by the coincidence checker,
w = (E₁ , ..., E_k ) To determine if
When each equation is established by the match tester,userDevice
It is determined that the received document information is valid.

FIG. 2 is a diagram (part 2) for explaining the principle of the present invention. The present invention provides a method of verifying the validity of a user for verifying the validity of the user by analyzing the content transmitted by the user device to the verification device. In the initial information setting process, the center device generates two prime numbers (P, Q) and keeps them secret, and the product N (N = P × Q) of the prime numbers and k integers ｛L
_{1, ..., L k} (} K ≧ 2) public information (N, {L _1,
.., L _k }) (steps 201 and 20).
2) In the center device, when a user who uses an ID as an identifier joins the system, k associated with the ID is used.
Pieces of secret information _{{S 1, ..., S k} } of _{{L 1, ..., L k} }
Is calculated using the secret prime numbers P and Q, and transmitted to the user device (step 203). The user device converts the value X used by the verification device into a random number R as L (L = L ₁ x
.. × L _k ) and the remainder operation modulo N, X = R ^L (mod N), is transmitted to the verification device (step 204),
The verification device generates a first message (E
_1, ..., and sends the E _k) to the user device (step 20
5) The user device obtains R _i = R ^{L / Li} (mod N) from the public information {L ₁ ,..., L _k } and the random number R acquired from the center device, and obtains the secret information {S _1, ..., and S _k}, the random number R and the first
From the communication message (E ₁ ,..., E _k ) and R _i , Y _i = R _i × S _i ^Ei (mod N) (where i is 1 ≦ i
≦ k), the second message (Y ₁ ,..., Y _k ) is calculated.
D, and ｛ID , ( E ₁ ,..., E _k ), (Y ₁ ,
,..., Y _k )}, and sends them to the verification device (step 206). The verification device generates {ID , ( E _{1 ,.}
(Y ₁ ,..., Y _k )}, a one-way function V _i = f (ID, i) (where i is an integer satisfying 1 ≦ i ≦ k) is calculated, and public information (N, ｛L _1, ..., a first communication sentence sent to L _k}) and the user device (E _1, ..., E _k), and the Vi, calculates the ^{_{Z i = Y i Li × V}} i Ei (mod N) Then, it is checked whether or not Z ₁ =... = Z _k holds. Further, a one-way function w = f (m, Z ₁ ,..., Z _k ) is calculated, and w = (E _{1 ,.} ) Is checked, and in the case that both tests are the same , the validity of the user is confirmed (step 207).

The above centerapparatusAt the time of system construction
As initial information setting processing, prime numbers P and Q
Is generated and kept secret, and the prime numbers P and Q are
The number is multiplied to obtain a multiplied value N, and a random number R is generated by a random number generator.
, N, and k integers generated by a random number generator
｛L₁ , ..., L_k ｝ (K ≧ 2) is released and as an identifier
When a user using the ID joins the system,
K secret information ｛S related to ID₁ , ..., S_k ｝, S_j = (1 / V _j )^{1 / Lj}(Mod N) (where j is an integer satisfying 1 ≦ j ≦ k and V_j = F
(ID, j))  Then, the secret information is passed to the user device.

[0032]

Further , the above-mentioned verification device uses a one-way function calculator to calculate the first message (E ₁ ,..., E _k ) = f for the value X used in the inspection received from the user device. Is calculated and transmitted to the user device.

Further, the present invention provides a document information validity authentication system for confirming the validity of the document information by analyzing the contents of the signature information transmitted by the signature generation device together with the document information by the signature verification device. Then, a prime number (P, Q) is generated and kept secret, and a product N of the prime numbers (P, Q) (N = P × Q)
And k integers {L ₁ ,..., L _k } (k ≧ 2) are disclosed as public information (N, {L ₁ ,..., L _k }). , K secret information {S ₁ ,..., S _k } related to the ID
_Is calculated using {L ₁ ,..., L _k } and secret P and Q, and the remainder generation using the product N of prime numbers modulo as a signature generation process. And a random number R
Is raised to the power of L (L = L ₁ ×... L _k ), and a value X used in the inspection by the signature verification device is obtained by X = R ^L (mod N). the first communication text component using a one-way function _{f (E 1, ..., E} k) = f a (m, X) is calculated and further, secret information _{{S 1, ..., S k} } and the random number R And the first message component (E ₁ ,..., E _k ), the second message component (Y ₁ ,..., Y _k ) is calculated, and the signed document information ｛ID, m, (E ₁ ,. , E _k ), (Y ₁ ,..., Y
_k )｝, and a signature generation device having means for generating and transmitting the signature information to the signature verification device; public information (N, {L ₁ ,..., L _k }) and a first message component received from the signature generation device (E ₁ , ...,
E _k ), the second message component (Y ₁ ,..., Y _k ) and the document information m for any i satisfying 1 ≦ i ≦ k,
If the value obtained from D, Y _i and E _i matches X, and if the matching value is Z, if (E ₁ ,..., E _k ) = f (m, Z ), signature generation It comprises a signature verification device having means for confirming the validity of the document information transmitted by the device.

Further, the present invention is a user validity confirmation system for confirming the validity of a user by analyzing the contents transmitted by the user device to the verification device, and confirming the validity of the user. Generate and store two prime numbers (P, Q) secretly, and multiply the prime numbers N (N = P × Q) and k integers ｛L ₁ ,
.., L _k ｝ (K ≧ 2) to public information (N, ｛L ₁ ,.
L _k }), and when a user using an ID as an identifier joins the system, k pieces of secret information {S ₁ ,..., S _k } related to the ID are replaced with the {L ₁ ,. _k } and a center device having means for calculating using the secret prime numbers P and Q and transmitting the calculated values to the user device. The user device converts the value X used in the verification device into a random number R by L (L = L ₁ × ... × L
_k ) raised to the power, the remainder operation modulo N is obtained by X = R ^L (mod N), and means for transmitting to the verification device, and the first message (E ₁ ,..., E _k ) from the verification device The secret information {S ₁ ,..., S _k }, the random number R, and the first message (E ₁ ,
, E _k ), a second message (Y ₁ ,..., Y _k ) is calculated, an ID is added, and 通信 ID , ( E ₁ ,..., E _k ),
(Y ₁ ,..., Y _k )}, and transmits the first message (E ₁ ,..., E _k) consisting of k random number components. ) To the user device, and a one-way function V _i = f (ID, i) ({ID , ( E ₁ ,..., E _k ), (Y ₁ ,..., Y _k ))} , I are integers satisfying 1 ≦ i ≦ k) and public information (N, ｛L ₁ ,..., L
_k ｝) and the first message (E ₁ ,
, E _k ), the second message (Y ₁ ,..., Y _k ), and V
from _i, means for calculating a ^{_{Z i = Y i Li × V}} i Ei (mod N), Z 1 = ... = checks whether Z _k holds, further, the one-way function w = f (Z _1, .., Z _k ), and checks whether w = (E ₁ ,..., E _k ) is satisfied. Having.

[0036]

[0037]

[Function] Since the Fiat-Shamir method is based on the quadratic operation, there is a trade-off between the amount of confidential information and the amount of transfer information when security is fixed. On the other hand, the present invention provides a plurality (k) of L-order (lower-order) exponentiation operations (for example, k
= 2 and L ₁ , L ₂ ), a value X common to the signature generation device, the signature verification device, the device to be verified, and the verification device is _obtained by using L = L ₁ × Lk. = R ^L (mod N), (e ₁ ,... E _k ) = f (m, X), and Y _i = R _i × S _i ^ei (mod N) (where R _i = R ^{L / Li}
Signature (mod N) component Y _1, ..., and generates a _{Y k, {ID, m,} e 1, ..., e k, Y 1, ..., Y k} and signed communication text to.

In the present invention, Y_iY from how to make_i ^Li× v_i
^eLSince ≡X (mod N), the conventional inspection formula (e₁,
…, E_k) = F (m, X) plus each Y₁,
…, Y _kEach value calculated from is the same as X
Inspect. In the conventional Fiat-Shamir method, (e₁,…,
e_k), The safety factor was determined by the number of bits.
Is added to the inspection condition that the new common value X matches.
Therefore, if the number of bits of the value X is b, 2^bUp to safety
The coefficient can be increased. Normally, X is 512 bits
Therefore, even if k = 2 and t = 1, safety can be sufficiently guaranteed.
Can reduce the amount of confidential information and the amount of transferred information at the same time.
You.

[0039]

Embodiments of the present invention will be described below. First Embodiment Document Information Validity Authentication Processing In a first embodiment, an example will be described in which a signature verification device verifies the validity of a communication message generated by a signature creation device.

FIG. 3 is a system configuration diagram of the first embodiment of the present invention. In the system shown in FIG.
00 is connected to a plurality of stations 200 and 300 via a secure communication path 400. Also, the stations 200 and 30
0 are connected via an insecure channel 500. In the following first embodiment, the station 200 will be described as a signature generation device, and the station 300 will be described as a signature verification device.

The processing of the center 100 shown below includes initial information setting processing at the time of system construction, and processing when a station joins the system. FIG. 4 is a sequence chart showing the outline of the operation of checking the validity of document information according to the first embodiment of the present invention. Steps 301 and 302) First, as initial information setting processing, the center 100 generates a prime number (P, Q), keeps it secret, and multiplies its product N (P × Q) and k integers ｛L ₁ ,
, L _k } (k ≧ 2) are disclosed to the stations (the signature generation device 200 and the signature verification device 300).

Step 303) Further, the center 100
When a user who uses his / her own ID as an identifier joins the system, the user uses {L ₁ ,..., L _k } and prime numbers P and Q
Calculate k pieces of secret information {S ₁ ,..., S _k } related to D and pass them to the user device (signature generation device 200) of the user. Step 304) User device (signature generation device 2)
00) calculates the value X used in the inspection by the signature verification device 300 from the random number R, and converts the random number R to a value L under the remainder operation modulo N.
(= L ₁ × ... × L _k ), and the document components (E ₁ ,..., E _k ) = calculate the f (m, X), further, secret information _{{S 1, ..., S k} } and the random number R and the _{(E 1, ..., E k} ) document component (Y ₁ from ...,
Y _k ). Thereby, the document information {ID, m,
(E ₁ ,..., E _k ), (Y ₁ ,..., Y _k )} are transmitted to the signature verification device 300.

Step 304) Signature verification device 300
Is the public information (N, $ L) obtained from the center 300.₁,
…, L_k｝) And received from the signature creation device 200
(E₁, ..., E _k) And (Y₁, ..., Y_k) And document information
When the report m satisfies 1 ≦ i ≦ k, the signature generation device 200
Check the validity of the sent document information. Next, each configuration
explain. FIG. 5 shows a center 10 according to the first embodiment of the present invention.
0 is shown. The center 100 generates prime numbers P and Q.
Prime number generator 110, multiplication for multiplying prime numbers P and Q
Device 120, secret information S_jOne-way function for generating
Calculator 130, reciprocal calculator 140 and Lth root calculator 1
50.

First, an initial information setting process will be described as a process of the center when the system is constructed. [Initial Information Setting Process] FIG. 6 is a flowchart of the initial information setting process when the center system is constructed according to the first embodiment of the present invention.

Step 601) The center 100 generates two prime numbers P and Q by using the prime number generator 110, and calculates N = P × Q by the multiplier 120. Step 602) A random number is generated in a random number generator (not shown), and k integers {L ₁ ,..., L _k } are selected. However, it is assumed that 2 ≦ k. Here, considering security, the prime numbers P and Q each have a recommended value of about 70 to 100 decimal digits.

Step 603) Next, the one-way function calculator 130, the reciprocal calculator 140, and the L-th root calculator 150
To generate secret information. First, the one-way function calculator 130 sends an ID from a station that uses the ID as the station identification information.
Is obtained, a one-way function v _j is obtained, and a reciprocal calculator 140
To enter. The reciprocal calculator 140 obtains a reciprocal 1 / v _j from N generated in step 601 and inputs the reciprocal 1 / v _j to the L-th root calculator 150. The L-th root calculator 150 calculates the prime number P,
A secret that satisfies S _j = (1 / v _j ) ^{1 / Lj} (mod N) (where v _j = f (ID, j) (where 1 ≦ j ≦ k is satisfied) by Q and the reciprocal 1 / v _j. Generate information S _j .

Step 604) The secret information S _j generated in step 603 is distributed to the public information management book or the stations 200 and 300 together with the public information N. Next, processing of the center 100 when the stations 200 and 300 join the system will be described. [Process of the center when the station joins the system] FIG.
5 is a flowchart showing processing of the center when the station joins the system according to the first embodiment of the present invention.

Step 701) ID applied to the center 100 as station identification information from the station 200 or 300.
Is entered. Step 702) The center 100 uses the one-way function calculator 130 for the input ID, calculates a one-way function by v _j = f (ID, j), and inputs the one-way function to the reciprocal calculator 140. .

Step 703) The reciprocal calculator 140 calculates
The reciprocal of the input one-way function v _j is calculated by 1 / v _j (mod N), and 1 / v _j is input to the Lth root calculator 150. Step 704) The L-th root calculator 150 calculates the composite number N
The secret information S _j that satisfies S _j ^Lj ≡ 1 / v _j (mod N) is generated using the prime factors P and Q of Note that a specific configuration example of the L-th root calculating device is a public key cryptosystem (Japanese Patent Laid-Open No.
3-26137).

Step 705) L-th root calculator 150
Is a secure (without fear that the secret of the secret information S will be leaked)
Each station has its own secret information {S}₁,
…, S _k｝ And public information N, ｛L₁, ..., L_kＩＤ ID
Send to the entered station. At this time, without sending,
For example, when a station joins a network, an IC card
It is also conceivable to store the data in a file or the like.

Next, a procedure (digital signature) in which the station 200 certifies the authentication of its own document information to the station 300 will be described. Hereinafter, the station 200 is referred to as A (signature generation device), and the station 300 is referred to as B (signature verification device). Note that, similarly, the station 300 can operate as a signature generation device, and the station 200 can operate as a signature verification device. FIG. 8 shows a communication sequence of a communication message between the signature generation device A and the signature verification device B.
The configuration of the signature generation device A is shown in FIG. 9, and the configuration of the signature verification device B is shown in FIG. FIG. 8 shows a communication sequence between the signature generation device and the signature verification device according to the first embodiment of this invention.
The signature creation device A obtains (E ₁ ,..., E _k ) = f (m, X) from the center 100 by applying a one-way function to the document information m and the value X used for verification by the signature verification device. From the obtained secret information {S ₁ ,..., S _k }, a signed message {ID, m, (E ₁ ,..., E _k ), (Y ₁ ,.
Y _k )｝.

The signature verification device 300 transmits the message {ID, m, (E ₁ ,..., E) _k , (Y ₁ ,.
Y _k )} and the public information (N, {L ₁ ,..., L _k }, ID) are used to check that the message satisfies the check formula. [Signature Generating Apparatus] FIG. 9 shows the configuration of a signature generating apparatus according to the first embodiment of the present invention.

The signature generation device A includes a random number generator 210 for generating a random number R, and a value X used by the signature verification device 300 for verification.
, A one-way function calculator 230 for generating a first message to be transmitted to the signature verification device for the message m and the value x, a secret information S _i and a first A second joint exponentiation unit 240 and a third joint exponentiation unit 250 for generating a second communication sentence from a communication sentence, the document information m, the output of the one-way function calculator 230 and a third joint exponentiation operation And a transmission unit 260 for transmitting each output of the device 250 to the signature verification apparatus B as signature information.

FIG. 10 shows a signature generator according to the first embodiment of the present invention.
6 is a flowchart illustrating a generating operation. Step 901) The signature generation device A starts the random number generator 21
A random number R is generated from 0, and the first joint exponentiation unit 220
And to the second joint exponentiation operator 240. Step 902) The first joint exponentiation operator 220 calculates
Random number R, public information @L ₁, ..., L_k｝, N is input
And X = R^L(Mod N) is a common value that is used by the signature verification device 300 for inspection.
Calculate the value X. Where L = L₁×… × L_kAnd

Step 903) One-way function calculator 2
30 obtains (E ₁ ,..., E _k ) = f (m, X) from the document information m and the common value X. Step 904) The second joint exponentiation operator 240 calculates
Random number R input from random number generator 210 and public information ｛L
Calculate R _i = R ^{L / Li} (mod N) from ₁ ,..., L _k }, N (1 ≦ i ≦ k). Here, L / L _i = L ₁ × ··· L _(i − ₁₎ × L _(i + ₁₎ ··· × L _k .

Step 905) The third joint exponentiation unit 250 calculates Y from the R _i input from the second joint exponentiation unit 240, E _i , secret information S _i, and public information N obtained above. Calculate _i = R _i × S _i ^Ei (mod N). However, it is assumed that 1 ≦ i ≦ k.

Step 906) The transmitting section 260 obtains (E ₁ ,..., E _k ) obtained by the one-way function calculator 230 in step 903, and obtains the result by the third joint exponentiation calculator 250 in step 905. ID is added to the signature component (Y ₁ ,..., Y _k ), and ΔID, m,
(E ₁ ,..., E _k ), (Y ₁ ,..., Y _k )} are transmitted to the signature verification device B as signature information of the document information m.

[Signature Verification Apparatus] FIG. 11 shows a first embodiment of the present invention.
1 shows a configuration of a signature verification device according to the embodiment. The signature verification device B shown in the figure includes a first one-way function calculator 310 for obtaining a one-way function based on public information and information received from a signature generation device, and a joint power calculator 32 for obtaining a check formula.
0, a first match checker 330, a second one-way function calculator 340, and a second match checker 350.

FIG. 12 is a flowchart showing a signature verification operation according to the first embodiment of the present invention. Step 1001) The signature verification device B sends the signature information ｛ID, m, (E ₁ ,..., E _k ), (Y
_1, ..., receives the Y _k)}, by entering the ID to the one-way function calculator 310, a one-way _{function, v i = f (ID,} i) is calculated. However, it is assumed that 1 ≦ i ≦ k.

Step 1002) Next, the joint exponentiation operator 320 receives the {E ₁ ,
_{..., E k}, {Y} 1, ..., public information received from the Y _k} and the center _{100 {L 1, ..., L} k}, the ^{_{N, Z i = Y i Li}} × v i Ei (mod N) _{Is used to} calculate Z _i . However, it is assumed that 1 ≦ i ≦ k.

Step 1003) First coincidence checker 3
30 checks whether the check formula Z _i =... = Z _k holds, and if not, step 100
Move to 7. Step 1004) Next, the second one-way function calculator 340 receives the document information m and {Z _i } passed by the first coincidence checker 330, and obtains W = f (m, The _one- way function of Z ₁ ,... Z _k計算 is calculated, and (E ₁ ,..., E _k ) and W are input to the second coincidence checker 350.

Step 1005) Second coincidence checker 3
50 is obtained from the second one-way function calculator (E ₁ ,..., E
_k ) and the value W are inputted, it is determined whether or not (E ₁ ,..., E _k ) = W is satisfied.
06, if not satisfied, step 1007
Move to Step 1006) If the two values are the same, it is determined to be acceptable.

Step 1007) If the two values are different, it is determined to be rejected. It should be noted, how to make the above-mentioned Y _i is, Y _i ^{Li _{× v i i ≡X (mod N}} ) is established (1 ≦ i ≦ k). As an example of this numerical value, when k = 2 and L ₁ =
3, L ₂ = 5. At this time, L = 15. ^{_{Y 1 = R L / L1 ×}} S 1 E1 = R L2 × S 1 E1 = R 5 × S 1 E1 (mod N) Y 2 = R L / L2 × S 2 E2 = R L1 × S 2 E2 = R 3 × S ₂ ^E2 (mod N).

[0064] _{^{Here, S 1 L1 ≡S 1 3 ≡1}} / v S 1 3 × than _{(mod N) v 1 ≡1 (} mod N) S 2 L2 ≡S 2 5 ≡1 / v from (mod N) since S ₂ ⁵ × v ₁ ≡1 satisfy ^{_{(mod N), Y 1 L1}} × v 1 E1 ≡R 5 × (S 1 3E1 × v 1 E1) ≡ (R 5) 3 ≡X (mod N) Y 2 _{^{L2 × v 2 E2 ≡R 3 ×}} (S 2 5E1 × v 2 E2) ≡ (R 3) 5 ≡X (mod N) is established.

[Second Embodiment] User Validity Authentication Processing So far, the authentication means for document information has been described.
Hereinafter, user authentication for confirming a communication partner will be described. FIG. 13 shows a system configuration of the second embodiment of the present invention. The system shown in the figure includes a center 100, a user device 600, and a verification device 700. Center 10
0, the user device 600, and the verification device 700 are connected via a secure communication channel 400, but the insecure communication channel 500 between the user device 600 and the verification device 700 has a possibility of leaking confidentiality. It is connected.

In the present embodiment, the authentication device 700 verifies the user device 600 as a communication partner. FIG. 14 is a sequence chart showing an outline of communication of a message between a device to be verified and a verification device in user authentication according to the second embodiment of the present invention. The common value X used by the user device 600, which is the device to be verified, for the verification by the verification device 700.
(Step 1101), the verification device 700 receives the X component, and the E _i component (E ₁ , E ₁ ) composed of k random number components
, E _k ) to the user device 600 (step 1102), the user device 600 generates a Y _i component from the received E _i component, assigns its own ID, and sends the message {I
D, Y _1, ..., and transmits to the verification device 700 of the Y _k} (step 1103). Thus, the verification device 700 verifies the validity of the user device 600 based on the received message.

The configuration of the center 100 and the user device 600 is the same as the configuration of the signature generation device 200 of the first embodiment. FIG. 15 shows a configuration of a verification device in user verification according to the second embodiment of the present invention. The configuration of the verification device 700 shown in FIG. 11 includes a one-way function calculator 710, a joint exponentiation operator 720, a coincidence checker 730, and a random number generator 750.
And a transmission unit 760.

FIG. 16 is a sequence chart showing the operation of the second embodiment of the present invention. Step 1201) The center 100 executes the prime number generator 11
0 to generate two prime numbers P and Q,
To calculate N = P × Q. Further, a random number is generated in a random number generator (not shown), and k integers {L ₁ ,
.., L _k }. However, 2 ≦ k. Next, secret information is generated using the one-way function calculator 130, the reciprocal calculator 140, and the L-th root calculator 150. First, the one-way function calculator 130 acquires an ID from a station that uses the ID as station identification information, obtains a one-way function v _j , and inputs it to the reciprocal calculator 140. The reciprocal calculator 140 obtains the reciprocal 1 / v _j from the composite number N and inputs it to the L-th root calculator 150. The L-th root calculator 150 calculates the prime numbers P and Q and the reciprocal 1
The _{/ v j, S j = (} 1 / v j) 1 / Lj (mod N) ( _{where, v j = f (ID,} j) the secret information S _j satisfying (satisfy 1 ≦ j ≦ k) Generate and generate user device 600
Send to

Step 1202) User device 600
Inputs the random number R generated by using the random number generator 210 to the first joint exponentiation calculator 220, finds X = R ^L (mod N), and transmits it to the verification device 700. Step 1203) Upon receiving X, the verification device 700 generates (E ₁ ,..., E _k ) using the random number generator 750, and transmits it to the user device 600 via the transmission unit 760.

Step 1204) User device 600
_{Is, (E 1, ..., E} k) receiving the secret information _{{S 1, ..., S k} } from the center 100, and the received random number _{R (E 1, ..., E} k) Joint exponent calculated by By using the device 250, (Y ₁ ,..., Y _k ) is calculated from Y _i = R _i × S _i ^Ei (mod N) (where i is 1 ≦ i ≦ k), and the message {ID ,
(Y ₁ ,..., Y _k )} to the verification device 700.

Step 1205) The verification device 700
Public information (N, {L ₁ ,..., L _k }) and utilization device 700
Using the one-way function calculator 710 from the ID and Y _i components (Y ₁ ,..., Y _k ) received from V _i = f (ID, i) (where i is 1 ≦ i ≦ k) The calculated value is input to the joint power calculator 720. Joint power calculator 720 calculates the ^{_{Z i = Y i Li × v}} i Ei (mod N), is input to the coincidence checking unit 730. Match checker 7
30, (Y ₁ ,..., Y _k ) received from the device to be verified
For any i that satisfies 1 ≦ i ≦ k, ID,
When the value obtained from Y _i and E _i matches X, the user device 600 determines that the user is a valid user.

The present invention is not limited to the above-described embodiment, and various applications and modifications are possible within the scope of the claims.

[0073]

According to the present invention described above, the following effects can be obtained. (1) Processing Amount of Signature Creation Apparatus The calculation and addition of the one-way function are faster than the multiplication, and therefore the comparison is made using the number of times the processing quantity of the signature creation apparatus is multiplied (including the remainder calculation by the modulus N). .

System using RSA encryption: (3 log ₂ N) /
Twice Fiat and Shamir scheme: t (k + 2) / 2 times the present invention: (3 kb + 1) times (where a b = log ₂ L _i) For example, if a safety factor to 2 ^-72, log ₂ N = 512 , RSA encryption method: 770 times Fiat and Shamir method: 40 times (when k = 18, t = 4) The present invention: 19 times (k = 2, L ₁ = 3, L ₂ = 5) Therefore, according to the present invention, the processing speed is 40 times or more that of the method using the RSA encryption and twice or more that of the method of Fiat and Shamir.

(2) Redundancy of Message The message in the system using the RSA encryption is represented by {ID, m,
D (f (m))}, and the message in the Fiat and Shimir scheme is {ID, m, (e _ij ), y ₁ ,..., Y _t },
The message in the present invention is {ID, m, E ₁ ,..., Y ₁ ,.
Y _k }. Here, the number of bits of D (f (m)) is N
And the number of bits in (e _ij ) is (k × t)
In bits, the number of bits in y ₁ ,..., Y _t is equal to the number of bits in N. E _i is b bits, and Y _i is N bits.
(Where b = log ₂ L _i ).

Comparing the number of bits of a message with a signature when N is 512 bits, the method using the RSA encryption: the number of bits of 512 + m Fiat and the method of Shimir: the number of bits of 512t + kt + m The present invention: the number of bits of 512k + kb + m = 2, b =
3 can be selected).

As a result, the system using the RSA encryption <the present invention <the system of Fiat and Shimir. Therefore, the redundancy of the message according to the present invention is Fiat and Sh.
It can be seen that it is better than the case where t ≧ 2 in the imir method. (3) Amount of Secret Information in Sender In the method using the RSA encryption, the amount of secret information managed by the sender is about N bits (512 bits).
On the other hand, the amount of secret information in the Fiat and Shimir scheme and the present invention is k
× (the number of bits of N) (that is, 512 × k bits). However, in the present invention, k = 2 can be selected, but Fiat and Shim
Since k = 18 is recommended in the ir method, the present invention can greatly reduce the amount of secret information for the user.

(4) Security Grounds The public information (N, L ₁ , ID) is converted into secret information (P, Q, S).
_The inability to calculate _i ) means that factoring is difficult,
And it is guaranteed by be difficult calculation of power root of presentation (L _i root), the signature that the verifier is unable to obtain secret information of the signature creator, method is the theoretical study of computational complexity theory of the present invention It can be guaranteed by satisfying the zero-knowledge interactive proof system and non-transferability that are the results.

Regarding the zero-knowledge interactive proof system property and non-transferability, see, for example, Feige, U., Fiat, A. and Shamir,
A. "Zero Knowledge Proofs of Indentity" Proceeding
s ofthe 19th Annual ACM Symposium on Theory of Com
See puting, 1987, pp. 210-217.

[Brief description of the drawings]

FIG. 1 is a diagram (part 1) for explaining the principle of the present invention;

FIG. 2 is a diagram (part 2) for explaining the principle of the present invention;

FIG. 3 is a system configuration diagram of a first embodiment of the present invention.

FIG. 4 is a sequence chart showing an outline of an operation for checking the validity of document information according to the first embodiment of the present invention.

FIG. 5 is a configuration diagram of a center according to the first embodiment of the present invention.

FIG. 6 is a flowchart of an initial information setting process when constructing a system on the center side according to the first embodiment of this invention.

FIG. 7 is a flowchart showing processing of the center when the station joins the system according to the first embodiment of this invention.

FIG. 8 is a sequence chart between the signature generation device and the signature verification device according to the first embodiment of this invention.

FIG. 9 is a configuration diagram of a signature generation device according to the first exemplary embodiment of the present invention.

FIG. 10 is a flowchart illustrating a signature generation operation according to the first embodiment of this invention.

FIG. 11 is a configuration diagram of a signature verification device person according to the first embodiment of this invention.

FIG. 12 is a flowchart illustrating a signature verification operation according to the first embodiment of this invention.

FIG. 13 is a system configuration diagram of a second embodiment of the present invention.

FIG. 14 is a sequence chart showing an outline of communication between a device to be authenticated and a verification device in user authentication according to a second embodiment of the present invention.

FIG. 15 is a configuration diagram of a verification device according to a second embodiment of the present invention.

FIG. 16 is an operation sequence chart of the second embodiment of the present invention.

[Explanation of symbols]

 REFERENCE SIGNS LIST 100 center 110 prime number generator 120 multiplier 130 one-way function calculator 140 reciprocal calculator 150 L-root calculator 200 station 210 random number generator 220 first joint exponentiation calculator 230 one-way function calculator 240 second Joint exponentiation unit 250 third joint exponentiation unit 260 transmitter 300 station 310 first one-way function calculator 320 joint exponentiation operator 330 first coincidence checker 340 second one-way function calculator 350 Second coincidence checker 360 Transmitter 400 Secure communication channel 500 Insecure communication channel 600 User device 700 Verification device 710 One-way calculator 720 Joint exponentiation operator 730 Matching tester 750 Random number generator 760 Transmitter

────────────────────────────────────────────────── ─── Continuation of the front page (56) References JP-A-63-101987 (JP, A) JP-A-1-209834 (JP, A) JP-A-1-133092 (JP, A) (58) Field (Int.Cl. ⁷ , DB name) H04L 9/32 G09C 1/00 640 JICST file (JOIS)

Claims (9)

(57) [Claims] When a user device operates as a signature generation device, a signature verification device analyzes the content of signature information transmitted by the user device together with document information, and confirms the validity of the document information. In the method of authenticating the validity of document information, as an initial information setting process at the time of system construction, the center device generates a prime number (P, Q) and keeps it secret, and a product N (N) of the prime numbers (P, Q). = P × Q) and k integers {L ₁ ,..., L _k } (k ≧ 2) are made public information (N, {L
_1, ..., and published as L _k}), further, when the user using the ID as an identifier to subscribe to the system, k pieces of secret information {S ₁ associated with the ID,
, S _k } are calculated using {L ₁ ,..., L _k } and secret P and Q, and transmitted to the user device. The user device performs the prime generation as a signature generation process. Is multiplied by L (L = L ₁ ×... L _k ) under the remainder operation modulo N, and the value X used by the signature verification device in the check is X = R ^L (mod N) The first message component (E ₁ ,..., E _k ) = f (m, X) is calculated using the one-way function f for the document information m to be signed and the value X. further, the secret information _{{S 1, ..., S k} } the random number R
And the first message component (E ₁ ,..., E _k ), the second message component (Y ₁ ,..., Y _k ) is calculated, and the signed document information ｛ID, m, (E ₁ ,. , E _k ), (Y ₁ ,..., Y
_k )｝ is generated and transmitted to the signature verification device, and the signature verification device generates ID, Y _{i for} any i satisfying 1 ≦ i ≦ k.
Consistent with the values obtained from E _i is the X, and, when the matching value was placed and _{Z, (E 1, ...,} E k) = f (m, Z) if it meets the user device transmits Document information validity authentication method characterized by confirming the validity of document information obtained. 2. In the center apparatus, as processing information setting processing at the time of system construction, prime numbers P and Q are generated and kept secret by a prime number generator, and the prime numbers P and Q are multiplied by a multiplier. The product N and k integers {L ₁ ,..., L _k } (k
≧ 2) to the user device, and when the user who uses an ID as the identifier joins the system, k pieces of secret information {S
_1, ..., a one-way function calculator to S _k}, with reciprocal calculators and L root _{calculator, S = (1 / V j} ) 1 / Lj (mod N) ( where, j is 1 ≤j≤k, where V _j = f (I
2. The method according to claim 1, wherein the calculated value is calculated according to D, j) and transmitted to the user device. 3. The method according to claim 1, wherein the user device generates a random number R using a random number generator as a signature generation process.
From the above, the value X used in the inspection by the signature verification device is calculated using the congruential exponentiation unit from X = ^RL (mod N) (where L = L ₁ × L ₂ × L _k ). (E ₁ ,..., E _k ) = f (m, X) is calculated by the one-way function calculator for the document information m and the value X, and the random number R and the public information ｛L ₁ , ..., a _{L k}, R i = R} L / Li (mod N) and (1 ≦ i ≦ k) calculated, the secret information {S _1, ..., S _k} and wherein the R _i first
For the message components (E ₁ ,..., E _k ), Y _i = R _i × S _i ^Ei (mod N) (where 1 ≦ i ≦
k), the second message component (Y _i ,..., Y _k ) is calculated from the first message component (E ₁ ,..., E _k ) and the second message component. (Y _i ,..., Y _k ) contain the document information m and the I
D attached document information {ID, m, (E ₁ ,
.., E _k ), (Y _i ,..., Y _k )}, and transmits to the signature verification device. 4. The signature verification device, wherein the signed document information {ID, m,
When (E ₁ ,..., E _k ), (Y _i ,..., Y _k )} are received, V _i = f (ID, i) (where i is 1 ≦ i ≦ k), and public information (N {L ₁ ,..., L _k }) and the first message component (E ₁ ,..., E _k ) received from the user device ,
From the second message component (Y _i ,..., Y _k ) and V _i , Z _i = Y _i ^Li × V _i ^Ei (mod N) the vessel, Z ₁ = ...... = to check whether the Z _k is true, w = f (m by the one-way function calculator, Z _1, ..., Z
_k ) is checked by a coincidence checker to determine whether w = (E ₁ ,..., E _k ) is satisfied. When each equation is satisfied by the two coincidence checkers, the result is received from the user device. 2. The method according to claim 1, wherein the signed document information is determined to be valid. 5. analyzed is the verification device about what the user device transmits to the verification device, the validity checking method of the user for confirming the validity of the user, the initial information setting process at the time of system construction In the center device, two prime numbers (P, Q) are generated and kept secret, and the product N (N = P × Q) of the prime numbers and k integers ｛L ₁ ,
.., L _k ｝ (K ≧ 2) to public information (N, ｛L ₁ ,.
_k }), and in the center device, when a user using an ID as an identifier joins the system, k pieces of secret information {S ₁ ,.
_k } with the {L ₁ ,..., L _k } and the secret primes P and Q
The user device transmits the value X used by the verification device and the random number R to L (L = L ₁ ×
... × L _k ) and the remainder is obtained by a modulo operation X = R ^L (mod N) modulo N, and transmitted to the verification device. The verification device outputs a first message composed of k random number components. _{(E 1, ..., E k} ) sends to said user device, said user device, said public information acquired from the center device _{{L 1, ..., L k} } from the random number R, R _i = R ^{L / Li} sought (mod N), the secret information _{{S 1, ..., S k} } and, the random number R and the first communication text _{(E 1, ..., E k} ) Y and from the R _{i i} = R _i × S _i ^Ei (mod N) (where i is 1 ≦ i
≦ k), the second message (Y ₁ ,..., Y _k ) is calculated.
D, and ｛ID, ( E ₁ ,..., E _k ), (Y ₁ ,
.., Y _k )} and transmits the same to the verification device, and the verification device generates the { ID, ( E ₁ ,..., E _k ),
(Y ₁ ,..., Y _k )}, a one-way function V _i = f (ID, i) (where i is an integer satisfying 1 ≦ i ≦ k) is calculated, and the public information (N, ｛ L ₁ ,..., L _k }) and the first message (E ₁ ,..., E _k ) transmitted to the user device;
And from Vi, calculates the ^{_{Z i = Y i Li × V}} i Ei (mod N), Z 1 = ... = checks whether Z _k holds, further, the one-way function w = f (Z _1, ... , Z _k ), and checks whether w = (E ₁ ,..., E _k ) is satisfied.
A method for authenticating the validity of a user, characterized by confirming the validity of the user. 6. The center device generates prime numbers P and Q by a prime number generator and keeps the secret numbers secret, and multiplies the prime numbers P and Q by a multiplier as initial information setting processing at the time of system construction. A random number R is generated by a random number generator, and the multiplied value N and k integers ｛L ₁ ,..., L generated by the random number generator
When the user who discloses _k ｝ (k ≧ 2) and uses an ID as an identifier joins the system, k pieces of secret information ｛S associated with the ID are used.
_1, ..., a _{S k}, S j = (} 1 / V j) 1 / Lj (mod N) ( where, j is an integer satisfying _{1 ≦ j ≦ k, V j} = F
6. The method according to claim 5, wherein the secret information is calculated by (ID, j)) and passed to the user device. 7. The verification device according to claim 1, wherein the first message (E ₁ ,..., E _k ) is calculated by a one-way function calculator with respect to the value X used in the check received from the user device. 6. The method according to claim 5, wherein the value is calculated and transmitted to the user device. 8. A document information validity authentication system for analyzing the contents of signature information transmitted by a signature generation device together with document information by a signature verification device and confirming the validity of the document information. (P, Q) is generated and kept secret, and the prime number (P, Q) is
Q) and k integers {L ₁ ,..., L
_k ｝ (k ≧ 2) is public information (N, {L ₁ ,..., L _k ｝)
And published as further when the user using the ID as an identifier to subscribe to the system, k pieces of secret information _{{S 1, ..., S k} } associated with ID _{of, {L 1, ..., L} k} and A center device having means for calculating and transmitting using secret P and Q, and a signature generation process for generating a random number R as L (L = L ₁₎ under a remainder operation modulo the product N of the prime numbers ××× L _k ) to obtain a value X used in the inspection by the signature verification apparatus by X = R ^L (mod N). The document information m to be signed and the one-way function f the first communication text components using _{(E 1, ..., E k} ) = calculate the f (m, X), further, the secret information _{{S 1, ..., S k} } the random number R
And the first message component (E ₁ ,..., E _k ), the second message component (Y ₁ ,..., Y _k ) is calculated, and the signed document information ｛ID, m, (E ₁ ,. , E _k ), (Y ₁ ,..., Y
_k )}, and a signature generation device having means for generating the signature information and transmitting the signature information to the signature verification device; and the _first information received from the signature generation device and the public information (N, {L ₁ ,..., L _k }). Message components (E ₁ , ...,
E _k ), the value of the second message component (Y ₁ ,..., Y _k ) and the value obtained from ID, Y _i and E _i for any i where the document information m satisfies 1 ≦ i ≦ k Is equal to X, and when a matching value is Z, if (E ₁ ,..., E _k ) = f (m, Z ) is satisfied, the validity of the document information transmitted by the signature generation device is determined. A document information validity authentication system comprising a signature verification device having means for checking. 9. The user device is then analyzed the verification device contents to be transmitted to the verification device, a user of the authentication system for verifying the validity of the user, two prime numbers ( P, Q) is generated and kept secret, and the product N (N = P × Q) of the prime numbers and k integers {L ₁ ,..., L _k }
(K ≧ 2) is disclosed as public information (N, {L ₁ ,..., L _k }), and when a user using an ID as an identifier joins the system, k pieces of secret information related to the ID { S
_1, ..., the the _{S k} {L 1, ...} , L k} and calculated using the prime number P and Q of the secret has a center unit having a means for transmitting to said user apparatus, the use 's device, the random number _{R L (L = L 1 ×} ... × L k) th power to obtain the value X to be used in X = R ^L (mod N) the verification device by residue operation modulo N, the verified Means for transmitting to the device; R _i = R ^{L / Li} (mod N) from the random number R and the public information {L ₁ ,..., L _k }, and a first message (E ₁ , …, E
_k ), the secret information {S ₁ ,..., S _k }, the random number R, the first message (E ₁ ,..., E _k ) and Ri
From Y _i = R _i × S _i ^Ei (mod N) (where i is 1 ≦ i ≦
k) to calculate the second message (Y ₁ ,..., Y _k )
｛ID , ( E ₁ ,..., E _k ), (Y ₁ ,
,..., Y _k )}, and transmits the first message (E ₁ ,..., E) comprising k random number components.
_k ) to the user device; ｛ID, ( E ₁ ,..., E _k ), (Y ₁ ,.
_k ) means for calculating a one-way function V _i = f (ID, i) (where i is an integer satisfying 1 ≦ i ≦ _k ) from｝, and the public information (N, ｛L ₁ ,..., L _k }) and the first message (E ₁ ,..., E _k ) transmitted to the user device;
Said second communication text from _{(Y 1, ..., Y k} ), and V _i,
A means for performing the remainder calculation Z _i = Y _i ^Li × V _i ^Ei (mod N) and checking whether Z ₁ =... = Z _k hold, and furthermore, a one-way function w = f (Z ₁ ,. Z _k ) is calculated, and it is checked whether w = (E ₁ ,..., E _k ) is satisfied.
The user of the validity authentication system characterized by comprising a means to confirm the validity of the user.