KR20040064780A - Method for verifying digitally signed documents - Google Patents

Abstract

PURPOSE: A method for verifying a digitally signed documents is provided to drastically increase the convenience of the user in the information society by supplying a safe output and verification method. CONSTITUTION: A method for verifying a digitally signed documents includes the steps of: inserting the electronic signature into the electronic documents(11) to transmit, wherein the electronic signature is capable of printing on the singer terminal; requesting the verification of the printed electronic documents(11) by outputting the electronic documents(11) in the verifier's terminal; and verifying the corresponding electronic documents(11) through the verification of the electronic signature which is inserted into the electronic documents(11) outputted from the verifier's terminal.

Description

Method for Verifying Digitally Signed Documents}

The present invention relates to a method for verifying an electronically signed document. In particular, the present invention provides a method for contributing to the activation of direct two-way processing of electronic documents between trading partners by constructing an infrastructure that can verify and process electronic documents and their output documents together. It is about.

In general, the problem of information infringement, which is a dysfunction of informatization, has emerged seriously in the process of entering the information society in earnest. The direct and indirect resources of individuals and society are becoming highly informatized, and the distribution of various electronic documents is expected to increase in earnest.

With the development of information and communication technology and the spread of high-speed Internet, the demand for information protection is exploding in various fields of society. The global information security technology market is expected to grow at an annual average of 27% or more and reach $ 30 billion annually in 2005 from $ 11 billion in 2000.

Governments and corporations at home and abroad are making efforts to promote the distribution of electronically signed documents through the dissemination of public key infrastructure. In other words, with the introduction of the concept of digital signature, the security reliability of transactions is partially guaranteed even in the virtual space such as the Internet.

However, as the Internet became a part of life, many users have expanded the concept of electronic documents and their range of application, and now they want to issue electronic documents for documents that could only be issued through offline methods (face-to-face authentication). Was done. In other words, it can be said that there is a great potential of demand for application services using digital signatures.

However, while electronically signed documents can be validated in electronic form, a similar level of validation method does not currently exist for offline documents printed through a printer. As a result, most transactions are still centered around the real world.

SUMMARY OF THE INVENTION The present invention has been made to solve the above-described problems, and an object thereof is to provide proof of an output signature inserted in an electronic document in which the signer inserts and transmits an output signature that can appear on the output document. Through the verification of the electronic document through this, the infrastructure to verify and process the electronic document and its output document together is to contribute to the activation of direct two-way processing of electronic documents between trading partners.

1 is a block diagram of an electronic document verification system according to an embodiment of the present invention.

2 is a conceptual diagram for verifying an electronically signed document according to an embodiment of the present invention.

3 is a verification structural diagram of an electronically signed document in FIG.

4 is a control flow diagram for verifying an electronically signed document in accordance with one embodiment of the present invention.

5 is a control flowchart for setting parameters in FIG. 4;

6 is a control flow diagram for generating a signature in FIG.

FIG. 7 is a control flowchart of signature verification of the outputted electronic document in FIG. 4; FIG.

Explanation of symbols on the main parts of the drawings

10: signer terminal 20: authentication server

30: prover terminal 40: verifier terminal

According to an aspect of the present invention, there is provided a method of verifying an electronically signed document, the method comprising: inserting and outputting an electronic document output from a signer terminal into an electronic document; Requesting verification of the outputted electronic document by digitally outputting the electronic document in a verifier terminal; And a step of verifying the electronic document through the proof of the electronic signature inserted in the outputted electronic document in the authenticator terminal.

Preferably, the step of inserting and transmitting the electronic signature into the electronic document comprises: selecting a main field of the electronic document which is data signed by an authentication method at the signer terminal; Encoding the main field to generate a data matrix code; Generating a signature matrix code for the primary field; And inserting the generated data matrix code and signature matrix code into an electronic document and transmitting the same.

Also preferably, generating the signature matrix code comprises: setting a parameter for generating the outputable electronic signature; Generating a digital signature for the primary field using the set parameter; And encoding the generated signature value.

Advantageously, setting the parameter for the digital signature comprises a large prime number p with a bit length of 512 + 256i (i = 0, ..., 6), and a bit length of 128 + 32j (j = 0). , ... 4) Is the prime q, group Z _p ^* in g = a ^{(p-1) / q} mod p (a Generating a generator g of the only recursive subgroup of rank q of Z _p ^* ) and a secret key x from Z _p ^* ; Computing a public key y such that y = g ^-x mod p using the generated p, g, and x, and issuing a certificate from a certification authority to calculate a hash value of user variable z = h (CertData). It is characterized by comprising.

Also preferably, generating the digital signature comprises selecting a random random variable k (0 <k <q); Calculating a first value r = h (g ^k mod p) of the signature using the selected random variable k; Using the calculated r, the second value of the signature s = x (kr calculating h (z, m) mod q; Transmitting the calculated r, s and certificates to an authentication server; Selecting a secret key t (0 <t <q) which is an arbitrary integer in the authentication server; Calculating s ', which is s' = s + t mod q, which encrypts the transmitted s using the selected t; Transmitting the calculated s' to a signer terminal; Using t validation allowance = y ^-t mod p Computing and storing with the r, characterized in that consisting of.

Also preferably, the process of authenticating the electronic document output from the prover terminal may include bit strings r (0 <r <q) and s '(0 <s'<) of the outputted electronic document transmitted from the verifier terminal. q) checking; Sending the r to an authentication server to request verification permission; Verification permission value from the authentication server Calculating a user variable z = h (CertData) when is received; Median u = r using the calculated z calculating h (z, m) mod q; Calculating a proof value w = y ^{s '} mod p using the ^s' ; Using the calculated w and u v = h (w calculating g ^u mod p); And comparing the calculated v with the r and accepting the corresponding signature when v = r.

More preferably, transmitting and receiving information of the count n for limiting the number of verifier terminals in the signer terminal and the authentication server; Encrypting count information in a signature matrix code at the signer terminal and inserting the count information into an electronic document; Confirming whether n = 0 after decreasing the count n when a verification permission request is received from a prover terminal at the authentication server; If the count n is 0, the verification permission request is rejected. If the count n is not 0, the verification permission value stored therein is stored. It characterized in that it further comprises the step of transmitting to the prover terminal.

Hereinafter, exemplary embodiments of the present invention will be described in detail with reference to the accompanying drawings.

1 is a diagram showing a system configuration for the safe and reliable output and verification of electronically signed documents.

A draft of a specific protocol for implementing the system of FIG. 1 was designed based on KCDSA, a Korean standard digital signature algorithm, and the system is a signer terminal (hereinafter referred to only as a 'signer') 10 and an authentication server 20. And a verifier terminal (hereinafter referred to only as 'verifier') 30 and a prover terminal (hereinafter referred to as 'certifier') 40 to perform a proposed protocol between each component block, thereby performing Achieve objectives for safe and reliable printing and verification. In particular, the present invention has completed the specific design of the proposed protocol, and also analyzed the safety.

The signer 10 works with the authentication server 20 to generate a signature of the electronic document and transmit the signed document to the verifier 40.

The verifier 40 prints the electronic document transmitted from the signer 10 and then requests the verifier 30 to validate the output document.

The prover 30 verifies the signature on the output (printed) electronic document in cooperation with the authentication server 20.

The requirements for the relationship between the building blocks are as follows.

The signer 10 trusts the authentication server 20 that controls the verification process, but does not need to inform the authentication server 20 of the main material, but requests the verifier 40 to output the signed document. In addition, the signer 10 does not trust the authenticator 30 and the verifier 40 in consideration of the possibility that the prover 30 and the verifier 40 can manipulate the signed document. This implies the concept of integrity.

The authentication server 20 trusts the signer 10 generating the signature, but considering the possibility that the prover 30 and the verifier 40 can manipulate the signed document, the authenticator 30 and the verifier ( 40) Do not trust This implies the concept of integrity.

The authenticator 30 trusts the authentication server 20 that controls the verification process, but does not need to inform the authentication server 20 of the main material, and assumes that the document signed by the signer 10 can be reused or modified. Do not trust the child (40).

The verifier 40 trusts the signer 10 that generates the signature and allows the authenticator 30 to verify the electronic document signed by the signer.

As mentioned above, there are two clear paths to the system for the safe and reliable printing and verification of electronically signed documents. The first path between the signer 10 and the authentication server 20 and the authenticator 30 is a path for controlling the printable signature, and the second path, the signer 10 and the verifier 40 and The path between the provers 30 is a path for completing the signature process.

In order for each building block to be interconnected in the system, the first path provides the confidentiality of the document and the second path provides the integrity of the document. In other words, the signer 10 and the authenticator 30 do not need to inform the authentication server 20 by the confidentiality provided in the first path, and further, the signer 10 and the authenticator 30 in the second path. It is believed that the verifier 40 cannot modify the document due to the integrity provided.

Each building block of the system is considered to be classified by the above requirements. However, for the sake of flexibility, consider the following cases. In other words, each entity is classified if the above requirements are applied correctly. However, if the authenticator 30 also trusts the signer 10 as the authentication server 20 trusts, the signer 10 and the authentication server 20 may be the same entity, and the signer 10 and the prover The 30 may be the same entity, and the signer 10, the authentication server 20, and the authenticator 30 may be the same entity.

Next, the protocol applied to the system will be described in detail. In general, the protocol P has a signature generation and signature processing as shown in FIG. And signature authentication.

In the signature generation, the signer 10 generates an electronic document 11 through interworking with the authentication server 20, selects primary fields 12 of the electronic document 11, The main field 12 is encoded into a barcode to generate a data matrix code 13. Then, the main field 12 is digitally signed, the signature value is encoded into a barcode to generate a signature matrix code 14, and the data matrix code 13 and signature matrix code 14 are generated in the electronic document 11. ) To generate a printable signature.

In the signature transaction, the signer 10 and the verifier 40 verify the electronic signature (digital signature) of the electronic document and print the digitally signed document.

In the signature verification process, the authenticator 30 scans the matrix codes 13 and 14 of the printed document 11 'to verify the main fields 12 of the data matrix code 13. And verifies the electronic signature of the main field 12.

The main field 12 means data signed by an authentication method. Since the present invention is for generating a signature that can print only selected data, it is not necessary to sign the entire data. Since the prover 30 can easily identify the key fields 12 in the printed document 11 ', the key field 12 should clearly describe the information about the original electronic document 11.

Anyone can generate a signature of all data in the electronic document 11. The data matrix code 13 encodes the main fields 12 by document identification information. Finally, the signature matrix code 14 encrypts the printable signature in the data matrix code 13. Both matrix codes 13 and 14 must be made to be printed in the original electronic document 11.

Next, an electronic signature technique will be described as an embodiment of the present invention. Electronic signature techniques are used for electronic signatures for electronic documents and for electronic signatures for printed and printed documents. Accordingly, electronic signature techniques are modified to meet the following predetermined requirements when applied to printed and output documents.

That is, in the digital signature for the output document, the signer 10 should not inform the authentication server 20 of the main material in the signature generation step. Further, the verifier 40 cannot modify the data matrix in the signature processing step, and cannot modify the signature matrix. Also, the verifier 40 cannot reuse the document unless the verifier 40 is allowed access to the signed document.

The prover 30 should not inform the authentication server 20 of the main material in the signature verification step, and cannot modify the data matrix and the signature matrix after the signature verification is completed. In addition, the authenticator 30 cannot reuse the document unless the authenticator 30 is allowed access to the signed document.

Next, the matrix code will be described in detail.

In the present invention, an appropriate encryption and code display method is used. The matrix code M includes a data matrix code and a signature matrix code.

The data matrix code encrypts key material fields and printed document specific information (e.g., the serial number and expiration date of the document). The signature matrix code is then encoded with electronic signature values for the main material.

In the present invention, as an embodiment, KCDSA is used as a printable digital signature protocol. Other digital signature algorithms may be used for the same purpose.

Hereinafter, KCDSA (Korean Certificate-based Digital Signature Algorithm) will be described.

KCDSA is one of the ElGamal signature methods and is based on the difficulty of discrete logarithm problems in the finite field. One well-known variant of the ElGamal signature algorithm is the Digital Signature Standard (DSS) and GOST 34.10.

When converting between integer bit strings in KCDSA data type conversion, when converting an integer x of bit length n into a bit string, express x in binary notation, and then, the most significant bit is the first bit and the least significant bit is the last. Make it a bit In other words,

x = x _n-1 2 ^n-1 + x _n-2 2 ^n-2 + ... + x ₁ 2 + x _0- > {x _n-1 x _n-2 ... x ₀ }

Similarly, a bit string of length n can be converted to an integer as follows.

{x ₀ x ₁ ... x _n-1 }-> x = x ₀ 2 ^n-1 + x ₁ 2 ^n-2 + ... + x _n-2 2 + x _n-1

Next, the conversion between bit strings will be described. A byte string conversion of a bit string of length n {b ₀ b ₁ ... + b _n-1 } is performed as many times as necessary in the uppermost part until n is a multiple of 8. Fills zeros with, then makes the most significant 8 bits the first byte and the last 8 bits the last byte. In other words,

{b ₀ b ₁ ... + b _n-1 }-> {x ₀ x ₁ ... + x _t-1 }

Where t is the length of the converted byte string, the smallest integer greater than or equal to real n / 8, and for i greater than 0 x _ti = b _n-8i b + n-8i + 1 ... b _{n-8i +} Given as ₇ and some of the most significant bits of x ₀ can be filled with zeros. In the same way, a byte string of length n can be converted into a bit string of length 8n.

KCDSA is a certificate-based add-on digital signature. For the security of digital signatures, it is necessary to verify that the public verification key and domain variables used in signature verification are correct values. This means that a third party (CA) that is trusted by users can have their private signature signed by the public verification key certification information in the public verification key verification information including domain variables, the user's public verification key, the user's identifier, and the expiration date. This can be done by using a certificate issued by digital signature with a key.

When issuing a certificate, a third party (CA) must include a process of verifying the identity of the user and then confirming whether the user knows the private signature key corresponding to the public verification key to be authenticated. In general, the certificate format is ITU-T Rec. It uses what is defined in X.509.

Next, domain variables p, q and g can be used in common if they are agreed within a particular group. In this case, the group's security officer should choose the length of the prime p and q depending on the importance of the application. Currently recommended for most signature applications, the length of prime p, q is approximately | p | = 1024, | q | = 160 or so. However, for signatures used in very important applications (for example, the signature key of the highest-level certification authority), it is recommended to use 2048 bits of P and 256 bits of q. In this case, you must also provide the necessary verification data so that users can verify that prime numbers p and q have been generated by legitimate procedures.

The domain variables p, q, and g for digital signatures can also be used for Diffie-Hellman type key distribution based on discrete algebra problems. However, the general view is that it is not desirable to use the same domain variable in common for different purposes. In particular, it is strongly recommended to avoid using private signing keys and public verification keys for key distribution even though domain variables are commonly used.

KCDSA consists of a signature generation process and a signature verification process, which consists of a pair of bit strings r and an integer s, which takes the message M as input and is calculated by the following steps: = {r, s} as a signature Specifically, verify that the domain variables p, q, g and the public verification key y are correct, and set the random number k to {1,... , q-1}, and randomly calculate the evidence value w = g ^k mod p.

Then compute the first part of the signature, r = h (w), calculate z = y mod 2 ^l , compute the hash code H = h (z || M), and then calculate the median value e = (r H) Calculate mod q

Then, calculate the second value of the signature s = x (k-e) mod q (if s = 0 then choose a random value k again), which is a pair of bit strings r and integer s, = {r, s} as a signature

To verify the said domain parameter and a public verification key is performed only once in the first place and to use each time and then the signature generation p, q, g, and can securely hold the y, and the first part of the signature from the random number k select r The process of calculating is independent of the message to be signed and can be calculated in advance.

In other words, you can calculate k and r in advance, store them safely, and then calculate the user variable z in real time when you get a message to sign. This precomputation method can be useful when it is necessary to calculate a large number of signatures in real time, which requires extra safe memory to store the precomputed k, r.

Since w is an integer in r = h (w), it must be converted into a bit string and then given as an input of a hash function. In the calculation of the intermediate value e, the bit string r and the bit string H are subjected to bitwise XOR operation, and as a result, the bit string is converted into an integer.

Next, before verifying the signature first in the signature verification process, the verifier 40 must obtain correct values for the public verification key y of the signer 10 and domain variables p, q, g, and the like. To this end, a method of verifying a certificate of a signer 10 issued by a trusted certificate authority and obtaining domain variables p, q, g and public verification key y extracted therefrom can be used.

Specifically, optionally verify the signer 10's certificate, extract domain variables p, q, g and public verification key y for signature verification, and receive the received signature ^{For '} = {r', s'}, check that the bit string r 'is equal to the output length of the hash function, and check that 0 <s'<Q.

Then compute the hash code H '= h (z || M') for the message M 'to be verified by calculating z = y mod 2 ^l , and the median e' = (r ' H ') calculates mod q, calculates the evidence value w' = y ^{s '} g ^e' mod p using the signer's public verification key y, and checks whether h (w ') = r' holds.

Signature if all of the above verification passes ^' Is verified to sign the received message M with the private signature key x corresponding to the public verification key y. In the above, when M '= M and s' = s, a process in which h (w ') = r' has been described.

If any of the above verification steps fail, either the message M 'is illegally signed or the message has been altered, indicating that the signature on M' is false without going to the next step.

As described above, KCDSA is one of the ElGamal signature methods based on the difficulty of the discrete logarithm problem in the finite field. One well-known variant of the ElGamal signature algorithm is the Digital Signature Standard (DSS) and GOST 34.10.

In one embodiment, the present invention uses KCDSA as a basic signature algorithm for electronic signatures for electronic documents and electronic signatures for printed documents. The above-mentioned KCDSA can be used without change for the electronic signature for the electronic document, but the electronic signature for the printed document is carefully changed and used due to the requirements.

Hereinafter, an electronic signature algorithm for a printed document will be described with reference to the accompanying drawings.

Printable KCDSA (P-KCDSA) is a modification of KCDSA to meet the requirements of digital signatures for printed documents. In FIG. 3, a message in parentheses in {} means encrypted with the public key of the receiver for confidentiality, and a message in parentheses in [] means including a message authentication code (MAC) or an electronic signature for integrity. The main purpose of the P-KCDSA is to ensure the integrity of r and s' of the path to the document printed in FIG.

As shown in FIG. 4, the P-KCDSA includes a parameter setting process (S500), a signature generation process (S600), and a signature verification process (S700).

First, the parameter setting process S500 will be described with reference to FIG. 5, and the signer 10 as a client object proceeds to the next step for parameter setting. That is, | p | A large prime number p = 512 + 256i (i = 0, ..., 6) is selected (S511). | p | represents the bit length of p.

And | q | = 128 + 32j (j = 0, ..., 4) and select a prime q such that q | (p-1) (S512), g = a ^(p-1) in group Z _p ^{* / q} mod p (a Z _p ^* ) selects a generator g of a unique cyclic subgroup of order q, in step S513.

Then, a random integer x is selected from Z _p ^* (S514). x is the secret key in KCDSA.

After that, a public key is calculated such that y = g ^-x mod p (S515), a certificate is issued from a certification authority, and then a hash value is calculated from the certificate as z = h (CertData) (S516, S517). . CertData is the signer's certificate data.

Next, the signature generation process S600 will be described with reference to FIG. 6, but assume that the signer 10 signs the binary message m of any length. Here, m means information encoded in the data matrix, that is, main fields and document-related information.

The signer 10 secretly selects a random integer k (0 <k <q) (S611), calculates r = h (g ^k mod p) (S612), and s = x (k-r h (z, m)) mod q is calculated (S613).

Then, (r, s) and the certificate are transmitted to the trusted server (authentication server) 20 while maintaining confidentiality (S614).

Then, the authentication server 20 secretly selects an arbitrary integer t (0 <t <q) (S615), calculates s '= s + t mod q (S616), and calculates the calculated s' as a signer ( 10) is transmitted in a way that can be authenticated (S617). Also, = y ^-t mod p Calculate and store with r (S618).

The printable signature of the signer 10 for the message m is (id, r, s'). S 'is encrypted when the signer 10 and the authentication server 20 share a temporary key t. t is a private key whose public key y ^-t is sent in encrypted form to the prover 30 in the next transaction.

Further, the signer 10 and the authentication server 20 exchange information of count n limiting the number of validators 40, and finally the signer 10 includes the count information in the signature matrix code to include in the document. .

Finally, the signature verification process (S700) is described with reference to FIG. 7, the verifier 30 proceeds to the next step to verify the signature (id, r, s') of the signer 10 for the message m. do.

That is, by obtaining a certificate of the signer 10 through a certificate authority (S711), to verify whether the signature of the message is by the signer 10 (S712), r (0 <r <q) and s' ( 0 <s' <q) is checked (S713).

Then, the r is transmitted to the authentication server 20 by the authenticated method and requests verification permission (S714).

Then, the authentication server 20 confirms that there is no limit on the number of verifications, and if there is no limit, secretly sends the verification permission to the prover 30. If the authentication server 20 exchanges information about the count n with the signer 10, the authentication server 20 decrements the count n when it sends a verification permission to the prover 30.

If the count n becomes zero, the authentication server 20 rejects the verification permission. Here, we used r as an index to make the verification permission, but we can make a more specific way.

The validator 30 having the verification permission (S715) calculates z = h (CertData) (S716), and u = r h (z, m) mod q is calculated (S717) and w = y ^s' mod p is calculated (S718).

Then, v = h (w g ^u mod p) is calculated (S719), and if v = r, the signature is accepted (S720, S721).

On the other hand, it is assumed that KCDSA is safe in a random oracle model. Under this assumption, the passive attacker cannot obtain the information of the signature transaction. Based on the safety of the KCDSA, how the P-KCDSA satisfies the requirements for electronic signatures of printed documents to prevent active attackers. Explain.

It is assumed that the active attacker impersonates the authenticator 30, and that the private keys of the signer 10 and the validator 40 are safe. Consider a spoof validator (D ').

The signer 10 should not disclose the main data to the authentication server 20 at the time of signature generation. That is, only the initial signatures r and s are delivered to the authentication server 20, and the authentication server 20 receives r (= h (g^kmod p)) and s (= x (k-rh (z, m)) You can't get any information about message m only through mod q).

Verifier 40 should not be able to change the data matrix in the signature transaction. That is, the data matrix information is signed by the signer 10 and encoded into the signature matrix, and the verifier 40 and the spoof verifier D 'cannot generate the signature of the signer 10 without x in the signature transaction. .

And the verifier 40 should not be able to change the signature matrix in the signature transaction. That is, the signature matrix information includes s 'and r instead of s, so that the verifier 40 cannot verify the signature, and the verifier 40 and the spoof verifier D' are previously assigned to s or t. You can't remove t from s '(s' = s + t mod q) without any information about it. In fact, the spoof validator D 'cannot get t from s' because it cannot get s from {r, s}.

In addition, the verifier 40 can only reuse the signed document if permitted. In order to use printable signatures, there must always be an authentication server 20 in the protocol. That is, the prover 30 should request the verification server 20 to verify the signature.

The prover 30 should not disclose the main data at the time of signature verification. That is, the prover 30 provides r only when verifying the signature to the authentication server 20, and the verifier 40 cannot obtain m from r (= h (g ^k mod p)).

And, the prover 30 should not be able to change the data matrix and signature matrix after signature verification. That is, as the difficulty of the discrete log problem, the prover terminal t cannot be obtained from (= y ^-t mod p), and the spoof validator (D ') cannot obtain t from s' because s is encrypted, the validator (40) and the spoof validator (D') Cannot remove t from s'.

In addition, the authenticator 30 can only reuse the signed document if permitted. In order to use printable signatures, there must always be an authentication server 20 in the protocol. That is, another prover must request the authentication server 20 to verify the signature.

Next, the P-KCDSA parameter according to an embodiment of the present invention will be described .

First, the signature received by the verifier 40 ^{If '} = {r', s '} is a valid signature for message M', then the verification process proves that h (w ') = r'.

o Theorem: If M '= M, r' = r, s' = s, then h (w ') = r'.

o Proof: Assume that M '= M, r' = r where H '= h (z || M') = h (z || M) = H and e '= (r' H ') mod q = (r H) mod q = e Also, from the fact that s '= s = x (k-e) mod q and e' = e,

w '= y ^s' g ^e' mod p = y ^s g ^e mod p

= y ^{x (ke) mod q} g ^e mod p = g ^{1 / xx (ke) mod q} g ^e mod p

= g ^{(ke) mod q} g ^e mod p = g ^k mod p

That is, h (w ') = h (g ^k mod p) = r, and r' = r, so h (w ') = r'.

Next, an algorithm for generating prime numbers p, q and generator g that can be used for KCDSA will be described.

To get the prime p and q, we use a prime judgment algorithm. The next algorithm is by Gary L. Miller and M. O. Rabin, whose probability that the integers passed through this algorithm are not prime is less than or equal to 1 / 4n. Thus, if n is around 50 (you can choose a different value), in most cases it gives a low enough probability of error.

The fractional decision algorithm finds a and m such that w = 1 + 2am as the first step. Where 2a is the largest power of 2 dividing w-1, thus m is odd.

Set i = 1 as the second step and select n ≧ 50. As a third step, create a random number b with 1 <b <w. If gcd (b, w)? 1 as the fourth step, the process proceeds to the seventh step below to complete the algorithm.

And as a fifth step, z = b ^m mod w is calculated, and if z = 1, the process proceeds to the following eighth step. As the sixth step, j = 1,... If z = w-1 while a-1, z proceed to step 8 below, calculate z = z ² mod w, and proceed to step 7 below if z = 1.

Since w is not a prime number as the seventh step, the algorithm is finished. If i <n as the eighth step, i = i + 1 and proceed to the third step.

As the ninth step, w is likely to be a prime number, so it is determined to be a prime number and the corresponding algorithm is terminated.

In the above algorithm, in order to reduce the execution time, in the first step, w may be divided into a predetermined number of small prime numbers (for example, the first 1000 prime numbers) to first check whether a small prime factor is obtained. Also, instead of using n | w | bits of random numbers b in steps 2 through 6, the first k uses small random numbers and the remaining nk uses | w | bits of random numbers, so that the first k Efficiency can be increased when calculating the power of two dogs (eg n = 50, k = 20).

Next, the prime number P and Q generation algorithms will be described.

KCDSA requires two prime numbers p, q that satisfy the following conditions:

(1) 2 ^α-1 <P <2 ^α , (| p | = α), = 1024 + 256i (0 ≦ i ≦ 4).

(2) 2 ^β-1 <q <2 ^β , (| q | = β), = 160 + 32j (0 ≦ j ≦ 3).

(3) q divides p-1, and (p-1) / 2 q is the product of prime numbers greater than or greater than q.

The above conditions (1) and (2) define the sizes that prime numbers p and q can have, and condition (3) is a condition for preventing possible attacks when p-1 has prime factors smaller than q. Here, a method of generating p and q such that the prime numbers p and q are also primes will be described as J = (p-1) / 2q.

At this time, since J is a prime number larger than q, the prime number r is first found, and then the execution speed can be increased by determining whether 2Jq + 1 is prime for several prime numbers q. HAS-160 can be used to generate random numbers for generation of prime numbers p and q.

A pseudo random number generator that outputs an arbitrary n-bit integer from an arbitrary bit string seed as an output is defined as follows.

PRNG (Seed, n) = v ₀ + v ₁ 2 ¹⁶⁰ +. . . + v _k-1 2 ^{(k-1) .160} + v _k 2 ^k.160

v _i = HAS-160 for i = 0, 1,... , k-1

v _k = HAS-160 (Seed || k) mod 2 ^r

Here, k = n / 160 and r = n mod 160, and i and k connected to the seed are represented by an 8-bit number. In addition, it is assumed that when a conversion between a bit string and an integer is necessary, the operation occurs after appropriate conversion based on the conversion rule.

The following algorithm produces a prime p, q with p = 2Jq + 1 (p, q, r is prime): Where the inputs are the bit length α of p and the bit length β of q and the outputs are prime p, q, J, evidence seed and count.

As a first step, an arbitrary bit string seed of bit size is selected. As a second step, the selected seed is input to the random number generator PRNG to generate a random number u of bits. (U = PRNG (Seed, α-β-4))

In the third step, 4 bits 1000 are added to the upper part of u, and the least significant bit is 1, which is set to J (J = 2 ^α-β-1 ∨ u ∨ 1).

As a fourth step, J is determined by a strong decimal decision algorithm, and if not, the flow proceeds to the first step. In the fifth step, the count is initialized to 0. In the sixth step, the count is increased by one. When the count is greater than 2 ^{24 in} the seventh step, the count proceeds to the first step.

In the eighth step, a β-bit random number u is generated by inputting the PRNG by connecting the count to the seed. (U = PRNG (Seed || count, β)

As a ninth step, we make the most significant and least significant bits of u 1 and leave it at 1. (q = 2 ^β-1 u u 1)

As a tenth step, if the number of bits of p = 2Jq + 1 is greater than the sixth step, the process proceeds to the sixth step, and as the eleventh step, q is determined by a strong decimal decision algorithm, and if it is not a decimal, the sixth step is performed. The strong decimal decision algorithm determines p and proceeds to step 6 above if it is not a prime number.

As a thirteenth step, the prime numbers p, q, J, and the evidence value seed and count are output.

In the seventh step, the count is converted into a 4-byte bit string based on a conversion rule, and the output seed and count are prime numbers p 'and q' by this algorithm. It can be used to confirm that it is properly generated.

That is, it is confirmed that J generated by performing the second to third steps as the output seed is a prime number such as (p'-1) / 2q ', and counts the seed again. As a concatenated value, it is confirmed that q obtained by performing the eighth to ninth steps is a prime number equal to a given q ', and finally, p = 2Jq + 1 is a prime number.

On the other hand, the generator g necessary to implement KCDSA is generated by an algorithm that receives p, q, and J and outputs generator g as follows.

First, an arbitrary number a smaller than p is generated as the first step, and g = a ^2J mod p is calculated as the second step. And if g = 1 as a 3rd step, it progresses to a 1st step and outputs g as a 4th step.

G output from the algorithm can be confirmed that it was properly generated by checking g ^q mod p = 1.

Next, generation of random numbers x and k for KCDSA will be described.

To implement KCDSA, you need to be able to generate random or pseudo-random numbers. KCDSA uses the user's private signature key x (0 <x <q) and a different random value k (0 <k <q) for each message. Describes an algorithm that can be used to precompute r = h (g ^k mod p). In each algorithm, the pseudorandom number generator PRNG (Seed, n) defined above is used to generate a pseudo random number | q | bit length from a given bit string.

First, the algorithm for generating the signer's private signature key x is described. The m random numbers are generated by generating m random values x _j (j = 0, 1, ..., m-1) as follows. Can be used as a private signing key for m users.

As a first step, an arbitrary random number of b bits is selected and left as the X key. (Where b ≥ | q |)

As a second step, j = 0, 1,... For m-1, calculate

XSEED _j = PRNG (optional user-provided random input, b)

XVAL = (XKEY + XSEED _j ) mod 2 ^b (| q | ≤ b ≤ B, B is a multiple of 32)

x _j = PRNG (XVAL, b) mod q

XKEY = XKEY + PRNG (x _j + XSEED _j mod 2 ^b , b) mod 2 ^b

Normally a private signing key of a user will be generated by each user, so m in this second step will be 1 in most cases. The user's optional input is used to ensure that the randomness of the private signing key is affected by the user's intention as well as by algorithms or mechanical devices that rely on rules. It is desirable to use the user's optional input value XSEED, since the user's private signing key is generated only once and is naturally dependent on the user's intentions.

The user input for the XSEED must be provided with a random number long enough so that the entropy is at least | q | bits or more (typically, the user input has entropy of about 1 bit per character). And, XKEY is a secret state variable that is updated after every x _j creation after initial initialization. Once all private signing keys have been created, the secret state variable XKEY and the user's secret input XSEED _j should be safely discarded.

Next k and r, t and An algorithm for precomputing will be described.

The algorithm calculates m random values k and r = h (g ^k mod p) in advance, and uses these values to sign m messages, which can use the random number generation algorithm described above. Since it is impractical to receive user input each time for the occurrence of, use a fixed KSEED, which is calculated as a hash value of a random number generated inside the computer. t and = g ^t mod p is the same as for h ().

The algorithm selects a random random number of b bits as the first step and puts it as KKEY (where b ≥ | q |), and calculates KSEED = PRNG (optional machine-generated random input, b) as the second step. As a third step, j = 0, 1,... Calculate the following for m-1.

KVAL = KKEY + KSEED mod 2 ^b

k _j = PRNG (KVAL, b) mod q

KKEY = KKEY + PRNG (k _j + KSEED mod 2 ^b , b) mod 2 ^b

w _j = mod p

r _j = h (w _j )

Then, as a fourth step, M ₀ , M ₁ ,... , Assuming that m _m-1 is m messages to be signed, j = 0, 1,... For m-1, calculate

H _j = h (z || M _j )

e _j = (r _j H _j ) mod q

s _j = x (k _j -e _j ) mod q

The signature for M _j is {r _j || s _j }.

The fifth step proceeds to the third step. Values (k ₀ , r ₀ ), (k ₁ , r ₁ ),... Required for signing the next m messages in the third step. Calculate, (k _m-1 , r _m-1 ) in advance. In the fourth step, if the first message M ₀ of m messages is ready, it can be started at any time, and execution can be stopped at any time if the message M _j (0 <j ≤ m-1) to be signed next during execution is not ready. .

In addition, a memory for two arrays of length m capable of storing {(k _i , r _i )} calculated in the third step is required.

In this algorithm, KSEED and KKEY are as important as the private signature key x, so they should never be exposed during use. In a typical computing environment, there is no secure storage, so the secret values KSEED and KKEY are created early in the execution of this algorithm and continue to use it, but when an application that uses this algorithm terminates (rather than storing it in a file or other storage for later use) Dispose of safely.

Next, an algorithm for obtaining the value of x ⁻¹ mod q required for the exponent when calculating the public verification key y will be described.

As the first step, i = q, h = x, v = 0, d = 1, and as the second step = [i / h], c = h as the third step, h = i- as the fourth step c, i = c as the fifth step, c = d as the sixth step, d = v− as the seventh step c, v = c as the eighth step, and then proceeds to step 2 if h is positive in the ninth step. Finally, in step 10, v becomes x ⁻¹ mod q.

In the tenth step, since v may be a negative number, it should be corrected so that v is an integer between 0 and q.

Next, ASN.1 notation for signature, public verification key and domain variable will be described.

The ASN.1 notation for the signature, public verification key, and domain variable can be defined as follows.

P-KCDSASignatureValue :: = SEQUENCE {

r BIT STRING,

s INTEGER}

P-KCDSAParameters :: = SEQUENCE {

p INTEGER,-odd prime p = 2Jq + 1

q INTEGER,-odd prime

g INTEGER,-generator of order q

J INTEGER OPTIONAL,-odd prime

Seed OCTET STRING OPTIONAL

Count INTEGER OPTIONAL}

P-KCDSAPublicKey :: = INTEGER-Public key y

Next, examples of calculation values obtained at each step by referring to and implementing KCDSA will be described. The following calculation values may be used as reference values when verifying suitability for the implementation result when developing an electronic signature application.

First, the case where | p | = α = 1024 and | q | = β = 160 will be described with reference to the reference implementation values for the algorithms for generating the prime numbers p, q and generator g.

Any bit string of the bit size selected in the first step of the above-described prime number p, q, generator g generation algorithm Seed:

Seed = 68 ad b0 d1 b6 ae f1 44 a9 50

f3 e7 84 c9 89 3d 36 04 09 0e

Random number u of bits generated in step 2:

u = PRNG (Seed, 860) = 0cfa55c3 2582e0d7 4a09ef55

c5d2acac 5b46e9f3 5470ac48 1d95438c 7f5cc107 1d4e0bc5

877e0a0f c6b30dc6 c743f238 9bc69b8f cb7affeb dea013f8

64c68ac2 cb8bd7b5 c434809f c6d1b62c d9f20bb1 a7fab58c

c3f5d2dc a511e2e4 077e9def 912141f8 47f8751d 1dc47f3d

J generated in step 3 (passes the strong decimal decision algorithm in step 4):

J = 2 ^α-β-1 ∨ u ∨ 1 = 8cfa55c3 2582e0d7 4a09ef55

c5d2acac 5b46e9f3 5470ac48 1d95438c 7f5cc107 1d4e0bc5

877e0a0f c6b30dc6 c743f238 9bc69b8f cb7affeb dea013f8

64c68ac2 cb8bd7b5 c434809f c6d1b62c d9f20bb1 a7fab58c

c3f5d2dc a511e2e4 077e9def 912141f8 47f8751d 1dc47f3d

Final count value: Count = 5189 = 0x1445

Random number u of bits generated in step 8:

Seed || Count = 68 ad b0 d1 b6 ae f1 44 a9 50 f3 e7

84 c9 89 3d 36 04 09 0e 00 00 14 45

u = PRNG (Seed || Count, 160)

= c3ddd371 7bf05b8f 8dd725c1 62f0b943 2c6f77fb

The q generated in step 9 (passes the strong decimal decision algorithm in step 11):

q = 2 ^β-1 ∨ u ∨ 1

= c3ddd371 7bf05b8f 8dd725c1 62f0b943 2c6f77fb

P generated in step 10: p = 2Jq + 1 (pass the strong decimal decision algorithm of step 12):

p = 2Jq + 1

= d7b9afc1 04f4d53f

737db88d 6bf77e12 cd7ec3d7 1cbe3cb7 4cd224bf f348154a

fba6bfed 797044df c655dcc2 0c952c0e c43a97e1 ad67e687

d10729ca f622845d 162afca8 f0248cc4 12b3596c 4c5d3384

f7e25ee6 44ba87bb 09b164fb 465477b8 7fdba5ea a400ffa0

925714ae 19464ffa cead3a97 50d12194 8ab2d8d6 5c82379f

Example of obtaining the generation source g using the generated p, q, J:

G selected in step 1:

g = random αbits = 1711797e cf9bc4b8

1c5ad487 b2d9f3d4 f4de8616 c47bb030 355ea4bf 2ab07104

0ee59c95 453119d7 68af7a79 95133c2d a1e302c6 9128afba

129e698d c7982f56 064c70c1 8fb523ba 826b76f8 1efa58a9

1226e6af c96e2010 97589940 8e785fe4 a338b398 065ffd22

2fd1e1b7 a1da01a0 90b84168 e3522241 d2855a4e fe87611a

Calculated in step 2 g: g = a ^2J mod p (passed test in step 3)

g = a ^2J mod p = 50e414c7 a56892d1

ad633e42 d5cd8346 f2c09808 111c772c c30b0c54 4102c27e

7b5f9bec 57b9df2a 15312891 9d795e46 652b2a07 2e1f2517

f2a3afff 5815253a aefe3572 4cfa1af6 afce3a6b 41e3d0e1

3bed0eff 54383c46 65e69b47 ba79bbc3 339f86b9 be2b5889

4a18b201 afc41fe3 a0d93d31 25efda79 bc50dbbb 2c3ab639

Next, an example of generating a signature using p, q and g will be described with respect to the numerical example of the signature generation algorithm.

Domain variables p, q, g:

p = d7b9afc1 04f4d53f

737db88d 6bf77e12 cd7ec3d7 1cbe3cb7 4cd224bf f348154a

fba6bfed 797044df c655dcc2 0c952c0e c43a97e1 ad67e687

d10729ca f622845d 162afca8 f0248cc4 12b3596c 4c5d3384

f7e25ee6 44ba87bb 09b164fb 465477b8 7fdba5ea a400ffa0

925714ae 19464ffa cead3a97 50d12194 8ab2d8d6 5c82379f

q = c3ddd371 7bf05b8f 8dd725c1 62f0b943 2c6f77fb

g = 50e414c7 a56892d1

ad633e42 d5cd8346 f2c09808 111c772c c30b0c54 4102c27e

7b5f9bec 57b9df2a 15312891 9d795e46 652b2a07 2e1f2517

f2a3afff 5815253a aefe3572 4cfa1af6 afce3a6b 41e3d0e1

3bed0eff 54383c46 65e69b47 ba79bbc3 339f86b9 be2b5889

4a18b201 afc41fe3 a0d93d31 25efda79 bc50dbbb 2c3ab639

Next, a numerical example of the private signature key x generation algorithm will be described.

b = 160

XKEY = f2072ce3 0a017656 8324564b fdbd7077 173b7e3f

Optional User-provided Random Input (160bytes) =

“Saldjfawp399u374r098u98 ^% ^% hkrgn; lwkrp47t93c% $ 89439859k”

“Jdmnvcm cvk o4u09r 4j oj2out209xfqw; l * &! ^ # @ U # * # $) (# z x”

“O957tc-95 5 v5oiuv9876 6 vj o5iuv-053, mcvlrkfworet”

XSEED = PRNG (Optional User-provided Random Input, 160)

= 524c2b44 27571044 17668b0f 332476d7 af9a8f77

XVAL = XKEY + XSEED mod 2160

= 44535827 3158869a 9a8ae15b 30e1e74e c6d60db6

PRNG (XVAL, 160) = 068c4ef3 55d8b6f5 3eff1df6 f243f985 63896c58

x = PRNG (XVAL, 160) mod q

= 068c4ef3 55d8b6f5 3eff1df6 f243f985 63896c58

Example of public verification key y and z generation:

x-1 mod q = a614b9b6 d25986c5 3621f7bc bc3af2ff 8b426e67

y = g ^x-1 mod q mod p = 96dce0e7 b2f17009

3d9b51d2 ba782027 33b62c40 6d376975 8b3e0cbb a1ff6c78

727a3570 3cb6bc24 76c3c293 743dfee9 4aa4b9ef a9a17fa6

bf790ac2 5a82c615 23f50aba ac7b6464 7eb15c95 7b07f5ed

7d467243 089f7469 5cd58fbf 57920cc0 c05d4582 9c0a8161

b943f184 51845760 ed096540 e78aa975 0b03d024 48cbf8de

z = y mod 2 ^l =

23 f5 0a ba ac 7b 64 64 7e b1 5c 95 7b 07 f5 ed

7d 46 72 43 08 9f 74 69 5c d5 8f bf 57 92 0c c0

c0 5d 45 82 9c 0a 81 61 b9 43 f1 84 51 84 57 60

ed 09 65 40 e7 8a a9 75 0b 03 d0 24 48 cb f8 de

Message to be signed M: Use 7-bit ASCII code

M = “This is a test message for KCDSA usage!” =

54 68 69 73 20 69 73 20 61 20 74 65 73 74 20 6d

65 73 73 61 67 65 20 66 6f 72 20 4b 43 44 53 41

20 75 73 61 67 65 21

Signature generation process:

① Generate random number k: b = 160

KKEY = 552daa16 42b91114 f9952200 4fd4a0c3 c63ef69f

Optional Machine-generated Random Input (160bits) =

1b f1 23 b0 27 52 e2 c9 ed 81

51 74 69 f2 0b 0c 19 a9 97 a4

KSEED = PRNG (Optional Machine-generated Random Input, 160)

= b014bdc2 21ca3428 0c6f1998 072f745e e4a680e8

KVAL = (KKEY + KSEED) mod 2160

= 054267d8 6483453d 06043b98 57041522 aae57787

PRNG (KVAL, 160) = 4b037e4b 573bb7e3 34cad0a7 0bed6b58 81df9e8e

k = PRNG (KVAL, 160) mod q

= 4b037e4b 573bb7e3 34cad0a7 0bed6b58 81df9e8e

② proof value w = gk mod p:

w = 0d2ace49 f0415880

843e4cff 2a224dcc a4d12a79 11323aac e1eaf5b4 f479a91f

94d01820 193d40a5 f71347e3 8f97ef41 8bd25959 879ea7f6

2d3fbaa7 e70a9d78 b8dc7933 00bbf669 0829961a ab4e59a8

410510da ada05ef8 7e48144d 6efe5075 29011382 38c84b5d

2c3f590c 06e1b918 7ee5d509 e15ccab2 c257d549 ac1a5086

③ First part of signature r = h (w): Bit string of hashed result after converting w to bit string

r = 8f 99 6a 98 ed a5 7c c8 d8 8a

a6 ff df ae a2 2f 39 d7 fa 8a

④ Hash code of the message H = h (z || M): z || Bit string of hashed result of M

z = y mod 2^l

= 23 f5 0a ba ac 7b 64 64 7e b1 5c 95 7b 07 f5 ed

7d 46 72 43 08 9f 74 69 5c d5 8f bf 57 92 0c c0

c0 5d 45 82 9c 0a 81 61 b9 43 f1 84 51 84 57 60

ed 09 65 40 e7 8a a9 75 0b 03 d0 24 48 cb f8 de

z || M = 23 f5 0a ba ac 7b 64 64 7e b1 5c 95 7b 07 f5 ed

7d 46 72 43 08 9f 74 69 5c d5 8f bf 57 92 0c c0

c0 5d 45 82 9c 0a 81 61 b9 43 f1 84 51 84 57 60

ed 09 65 40 e7 8a a9 75 0b 03 d0 24 48 cb f8 de

54 68 69 73 20 69 73 20 61 20 74 65 73 74 20 6d

65 73 73 61 67 65 20 66 6f 72 20 4b 43 44 53 41

20 75 73 61 67 65 21

H = af 3f b0 4b 07 03 c6 ea 56 08

d8 9b 38 c3 3b 35 9c bc a2 b0

⑤ median value e = (r H) mod q:

r H = 20a6dad3 eaa6ba22 8e827e64 e76d991a a56b583a

e = (rH) mod q

= 20a6dad3 eaa6ba22 8e827e64 e76d991a a56b583a

⑥ second part of signature s = x (k-e) mod q:

s = 541f7dc4 f92c65eb 7f63b6b4 f22177f1 ee2cf339

⑦ Signature = {r, s}:

r = 8f 99 6a 98 ed a5 7c c8 d8 8a

a6 ff df ae a2 2f 39 d7 fa 8a

s = 541f7dc4 f92c65eb 7f63b6b4 f22177f1 ee2cf339

Next, a numerical example of the signature verification algorithm will be described.

The verifier terminal signs the received message M 'and ^{Through the} following process ^It can be confirmed that the signer terminal having the private signing key x corresponding to this public key y is the correct signature for M, which is created through the correct signature generation process.

① Receive M ', r', s': Check the size of r ', s'

M '= 54 68 69 73 20 69 73 20 61 20 74 65 73 74 20 6d

65 73 73 61 67 65 20 66 6f 72 20 4b 43 44 53 41

20 75 73 61 67 65 21

r '= 8f 99 6a 98 ed a5 7c c8 d8 8a

a6 ff df ae a2 2f 39 d7 fa 8a

s' = 541f7dc4 f92c65eb 7f63b6b4 f22177f1 ee2cf339

(2) Hash code of the message to verify H '= h (z || M'):

z = y mod 2 ^l

= 23 f5 0a ba ac 7b 64 64 7e b1 5c 95 7b 07 f5 ed

7d 46 72 43 08 9f 74 69 5c d5 8f bf 57 92 0c c0

c0 5d 45 82 9c 0a 81 61 b9 43 f1 84 51 84 57 60

ed 09 65 40 e7 8a a9 75 0b 03 d0 24 48 cb f8 de

z || M '= 23 f5 0a ba ac 7b 64 64 7e b1 5c 95 7b 07 f5 ed

7d 46 72 43 08 9f 74 69 5c d5 8f bf 57 92 0c c0

c0 5d 45 82 9c 0a 81 61 b9 43 f1 84 51 84 57 60

ed 09 65 40 e7 8a a9 75 0b 03 d0 24 48 cb f8 de

54 68 69 73 20 69 73 20 61 20 74 65 73 74 20 6d

65 73 73 61 67 65 20 66 6f 72 20 4b 43 44 53 41

20 75 73 61 67 65 21

H '= af 3f b0 4b 07 03 c6 ea 56 08

d8 9b 38 c3 3b 35 9c bc a2 b0

③ median e '= (r' H ') mod q:

r 'H '= 20a6dad3 eaa6ba22 8e827e64 e76d991a a56b583a

e '= (r' H ') mod q

= 20a6dad3 eaa6ba22 8e827e64 e76d991a a56b583a

④ the proof value w '= y ^s' g ^e' mod p:

w '= 0d2ace49 f0415880

843e4cff 2a224dcc a4d12a79 11323aac e1eaf5b4 f479a91f

94d01820 193d40a5 f71347e3 8f97ef41 8bd25959 879ea7f6

2d3fbaa7 e70a9d78 b8dc7933 00bbf669 0829961a ab4e59a8

410510da ada05ef8 7e48144d 6efe5075 29011382 38c84b5d

2c3f590c 06e1b918 7ee5d509 e15ccab2 c257d549 ac1a5086

⑤ h (w ') = r':

h (w ') = 8f 99 6a 98 ed a5 7c c8 d8 8a

a6 ff df ae a2 2f 39 d7 fa 8a

= r '

In addition, the embodiments according to the present invention are not limited to the above-described embodiments, and various alternatives, modifications, and changes can be made within the scope apparent to those skilled in the art.

As described above, according to the present invention, it is possible to greatly increase the convenience of the user in the information society by providing a method for securely outputting and verifying an electronically signed document to an organization that issues a first certificate such as a university or a government office.

In addition, by implementing direct two-way processing of the electronic document between the parties in simple identification purposes, it can contribute to the activation of the electronic signature.

Claims (7)

Inserting and outputting an electronic signature output from the signer terminal into an electronic document; Requesting verification of the outputted electronic document by digitally outputting the electronic document in a verifier terminal; And a step of verifying the electronic document through the proof of the electronic signature inserted in the outputted electronic document in the authenticator terminal. The method of claim 1, The step of inserting and transmitting the electronic signature into the electronic document includes: selecting a main field of the electronic document which is data signed by an authentication method at the signer terminal; Encoding the main field to generate a data matrix code; Generating a signature matrix code for the primary field; And inserting the generated data matrix code and signature matrix code into an electronic document and transmitting the same. The method of claim 2, Generating the signature matrix code may comprise: setting a parameter for generating the outputable electronic signature; Generating a digital signature for a main field using the set parameter; And encoding the generated signature value. The method of claim 3, wherein The step of setting the parameter includes a large prime number p having a bit length of 512 + 256i (i = 0, ..., 6), and a bit length of 128 + 32j (j = 0, ... 4) Is the prime q, group Z _p ^* in g = a ^{(p-1) / q} mod p (a Generating a generator g of the only recursive subgroup of rank q of Z _p ^* ) and a secret key x from Z _p ^* ; Computing a public key y such that y = g ^-x mod p using the generated p, g, and x, and issuing a certificate from a certification authority to calculate a hash value of user variable z = h (CertData). Validation method of the electronically signed document, characterized in that it comprises a. The method of claim 3, wherein Generating the digital signature comprises: selecting a random random variable k (0 <k <q); Calculating a first value r = h (g ^k mod p) of the signature using the selected random variable k; Using the calculated r, the second value of the signature s = x (kr calculating h (z, m) mod q; Transmitting the calculated r, s and certificates to an authentication server; Selecting a secret key t (0 <t <q) which is an arbitrary integer in the authentication server; Calculating s ', which is s' = s + t mod q, which encrypts the transmitted s using the selected t; Transmitting the calculated s' to a signer terminal; Using t validation allowance = y ^-t mod p Calculating and then storing the data together with the r. The method of claim 1, The proofing of the electronic document may include checking bit streams r (0 <r <q) and s '(0 <s' <q) of the output electronic document transmitted from the verifier terminal in the prover terminal. Wow; Sending the r to an authentication server to request verification permission; Verification permission value from the authentication server Calculating a user variable z = h (CertData) when is received; Median u = r using the calculated z calculating h (z, m) mod q; Calculating a proof value w = y ^{s '} mod p using the ^s' ; Using the calculated w and u v = h (w calculating g ^u mod p); And comparing the calculated v with the r and accepting a corresponding signature when v = r. The method according to claim 5 or 6, Transmitting and receiving information of count n for limiting the number of verifier terminals in the signer terminal and the authentication server; Encrypting count information in a signature matrix code at the signer terminal and inserting the count information into an electronic document; Confirming whether n = 0 after decreasing the count n when a verification permission request is received from a prover terminal at the authentication server; If the count n is 0, the verification permission request is rejected. If the count n is not 0, the verification permission value stored therein is stored. The method of claim 1, further comprising the step of transmitting to the authenticator terminal.