CN1207866C - Safe digital signature system and method - Google Patents

Abstract

The invention relates to a safe digital signature system and method. The system includes a task allocator, k operators, m synthesizers and sub-key distributors connected through a broadcast channel. The sub-key distribution operation includes: the sub-key distributor expresses the private key d as the sum of t sub-keys d _j and a sub-key _ci , and makes t<k; the distributor distributes k random d _j is distributed to k operators, and a set of equation combination representations of c _i are obtained, all equation combination representations and their corresponding c _i are exhaustively searched according to the synthesizer safety conditions to obtain m groups, and distributed to m synthesizers Prestored. The digital signature operation includes: the task allocator broadcasts the HASH value M that needs to be signed and sends it to k operators; the operator calculates the power M ^dj and broadcasts it to the synthesizer; the synthesizer compares it with the pre-stored _ci equation combination representation , find the matching equation combination representation and get the corresponding c _i , multiply the corresponding raising power M ^dj to get the result R, calculate M ^ci , and finally get the digital signature S=M ^d .

Description

A secure digital signature system and method

technical field

The present invention relates to network communication security technology, more specifically to a system and method for ensuring digital signature security that can tolerate intrusion.

Background technique

Digital Signature (Digital Signature) is the most basic technology in today's network communication security. It uses an asymmetric algorithm (Asymmetric Algorithm) to achieve the purpose that others can verify the signature but cannot counterfeit the signature. The most commonly used asymmetric algorithms are RSA, DSA, and elliptic curve algorithms, etc. Currently, many digital signature systems are based on the RSA algorithm.

The so-called asymmetric algorithm means that a person cannot derive the parameters of the reverse calculation through the known forward calculation parameters, that is, the known forward calculation process has no reverse calculation ability. This asymmetric algorithm itself is public, but everyone can choose different parameters, and the transformation functions formed by different parameters are different. For someone, he can choose a set of parameters, some of which are used for reverse calculation, called secret parameters, technically called secret key or private key; the other part is used for forward calculation, which is public parameters, technically known as the public key or public key.

Digital signatures are implemented based on this asymmetric algorithm. On the one hand, protect your own secret parameter - the private key to ensure that others cannot pretend to be yourself to sign; is computationally infeasible to derive the secret parameters).

Digital signature is first of all a guarantee for network communication and interaction. It can ensure that the other party is authentic and that the one on the Internet is yourself. It can also be used as a tool when signing electronic documents to protect your own documents and signatures. Many countries today regard digital signatures as handwritten signatures, and both have the same legal efficiency.

Digital signature algorithms can also be used to negotiate secret parameters. For example, when user A needs to communicate secretly with user B, user A can set some secret parameters first, and then use the public key (public key) of user B to act. At this time, only user B can restore the original value, because only User B knows his private key (private key).

In addition, digital signatures can also be used in places that require confidentiality, places that require identity authentication, and other places that require non-repudiation services.

The PKI (Public Key Infrastructure: public key infrastructure) that is being vigorously promoted internationally is an application of digital signatures, and it is the most important infrastructure in the network digital society. The importance of this technology is just like the power infrastructure. Facilities do the same for industry.

In order to ensure the security and speed of digital signatures, before signing, HASH calculation must be performed on the signed content to find a HASH value M (HASH value is sometimes called digest value or hash value), and then use the secret key (private key) ) to transform the digest result to obtain the signature value; when verifying the signature, first perform HASH calculation on the content, then use the public parameters (public key) to act on the signature value, and then compare the obtained result with the above HASH result, if they are equal , it means that the signature is correct, otherwise the verification fails.

However, when a user A has his own private key and discloses the public key, if an attacker B regenerates the public key and private key, and replaces the public key released by user A with the public key of the attacker B, the At this time, only the attacker B knows the information sent by the friend of user A to user A, because user A has no way of knowing the private key corresponding to the public key faked by attacker B. At this time, a CA (CertificateAuthority: Certificate Authority or Certificate Authority) is required to prove which public key belongs to user A, or which public key does not belong to user A.

The CA has a longer private key than the private key of ordinary users, that is to say, the private key of the CA is more secure, and the public key of the CA can be widely known in various ways, so that each user can verify what is issued by the CA. When a user binds his identity with his public key and is signed by a CA, he gets an electronic certificate. This certificate can prove the identity of the owner of the public key, and anyone can verify but no one can impersonate.

At present, electronic certificate has become the most critical part of PKI infrastructure, and CA is the most important basic unit in PKI. Using electronic certificates can effectively solve security issues such as confidentiality, integrity and non-repudiation on the network.

PKI-based security will ultimately come down to the protection of the CA's private key. Once the CA's private key is leaked, all certificates issued by the CA must be invalidated, and the entire network security under the jurisdiction of the CA will become insecure. to speak of. With the continuous increase of various attack methods on the network, system loopholes are constantly being discovered, so how to ensure that digital signature services can be provided online while ensuring security has become an important topic in modern network security research.

For the RSA algorithm, the secret key is generally recorded as d, which is an integer that can be as long as 2048 bits (it is generally believed that a private key with a length of 1024 bits can already guarantee security, but for CA, it is necessary to use 2048 bits or more. of). In the RSA algorithm, the modular exponentiation calculation of a number N is used, that is, to find M ^d mod N. This calculation is required to complete the digital signature. When the required public parameters (public key) are disclosed, the protection number d is The private key is protected.

The goal of a secure digital signature is to complete the signature without divulging the private key. There have been many theoretical studies on this topic in the world, many of which cannot be realized due to the difficulty. On the other hand, the focus of current development in the world is how to realize mutually compatible digital signature products, but there are very few developments in terms of intrusion-tolerant security signatures, and the industry has not launched related products. The so-called intrusion tolerance (Intrusion Tolerance) is relative to the technology to ensure the security of CA by detecting intrusion, that is, after some parts of the system are attacked or occupied, the confidential information of the CA system will not be exposed.

To sum up, PKI is based on the public key cryptography algorithm. In the PKI system, the CA is also a trust center in a domain. The communication and verification between devices or individuals on the network depend on the digital certificate (signature) issued by the CA. ). A digital certificate is a data obtained by binding a public key with a personal identity and signing it with a CA's private key. When one party wants to verify the identity of the other party, it can be done in two steps. First, verify whether the certificate signature of the other party is correct (the signature can only be completed by the private key of the CA, and only the CA can sign); If the private key corresponding to the public key in the certificate can be established, the identity of the other party can be determined and can be trusted.

Therefore, the CA's private key is the core of CA security, and protecting it from disclosure is the basis for the security of the entire CA domain. Generally speaking, a CA must be an online network device, especially a CA that directly faces users in order to provide corresponding certificate services, so it is inevitable to encounter network attacks. When a hacker successfully attacks a CA, the attacker may obtain Its internal resources, so as to find the private key of the CA, will cause a fatal blow to the PKI system. key.

In the following, several existing secure digital signature methods are described only from the aspect of equating the signature to realizing the formula M ^d mod N (where d is the private key that should be kept secret).

Referring to FIG. 1 , it shows a block diagram of a prototype system of the ITTC project scheme of Stanford University in the United States. The system implements system intrusion tolerance through threshold cryptography technology, and the system includes signing parties (Clients), servers (Servers) and administrators (Admin). The web server of the signing party refers to the web server that needs to be signed, and the CA is the certificate authority or certificate authority; the server side includes multiple sharing servers (ShareServer, also called sharing calculator or sharing calculator), as shown in the figure Share server 1 To 3, responsible for secure digital signature; the administrator (Admin) is an optional device used to manage each shared server. The characteristics of this scheme are: simple structure and good security, the system adopts multiple shared servers in a single-layer structure.

The security principle of the system is: first decompose the private key d into the sum of t numbers: d=d ₁ +d ₂ +...+d _t ; then distribute each number (d _i ) to each shared server middle. When a signature is required, the client (Web or CA) sends the required signature information-HASH result M value to t sharing servers; each sharing server then sends the calculation result $m_i=m^{d_i}$ Send back to client (Web or CA); multiplication by client (Web or CA):

$\mathrm{<span\; class="notranslate">\; S</span>}<span\; class="notranslate">\; =</span>\underset{\mathrm{<span\; class="notranslate">\; i</span>}<span\; class="notranslate">\; =</span>\mathrm{<span\; class="notranslate">\; 1</span>}}{\overset{\mathrm{<span\; class="notranslate">\; t</span>}}{\mathrm{<span\; class="notranslate">\; \&Pi;</span>}}}{\mathrm{<span\; class="notranslate">\; m</span>}}^{{\mathrm{<span\; class="notranslate">\; d</span>}}_{\mathrm{<span\; class="notranslate">\; i</span>}}}<span\; class="notranslate">\; =</span>{\mathrm{<span\; class="notranslate">\; m</span>}}^{\underset{\mathrm{<span\; class="notranslate">\; i</span>}<span\; class="notranslate">\; =</span>\mathrm{<span\; class="notranslate">\; 1</span>}}{\overset{\mathrm{<span\; class="notranslate">\; t</span>}}{\mathrm{<span\; class="notranslate">\; \&Sigma;</span>}}}{\mathrm{<span\; class="notranslate">\; d</span>}}_{\mathrm{<span\; class="notranslate">\; i</span>}}}<span\; class="notranslate">\; =</span>{\mathrm{<span\; class="notranslate">\; m</span>}}^{\mathrm{<span\; class="notranslate">\; d</span>}}$

The desired result is obtained.

Since redundancy cannot be achieved, multiple sets of equations can be further used to generate redundant configurations, that is, several sets of numbers are randomly found, such as:

The first group: d=d ₁₁ +d ₁₂ +...+d _1t ;

The second group: d=d ₂₁ +d ₂₂ +...+d _2t ;

………,

Then divide multiple sets of numbers (d _ij ) into different sharing servers, and each sharing server gets multiple d _ij , but only gets one data in the same set of data (for example, sharing server 1 gets a first set of data d ₁₁ and another second set of data d ₂₃ ). For example, in the case of 4 shared servers, when t=3, they can be allocated according to the following table: shared server 1 share server 2 share server 3 share server 4 d ₁₁ d ₁₂ d ₁₃ d ₁₃ d ₂₃ d ₂₁ d ₂₂ d ₂₃

When the client (Web or CA) needs to calculate, the client (Web or CA) selects t intact sharing servers, and then tells these sharing servers which set of data (parameters) to use, and then the sharing server can calculate Signed accordingly.

The advantage of this technical solution is obvious, and its weak point has the following points:

1. The distribution and management of the key is difficult. When adding a shared server, the key data must be distributed to each online shared server, and the client must also know the increase;

2. When there are many sharing servers, the key storage capacity of the sharing servers will increase rapidly. If the total number of sharing servers is k, and the total number of intact sharing servers is required to be t, then the number of keys stored in each sharing server At least C _k ^t-1 (C represents a combination), when k=10, t=3, the number of each shared server storage key is 45;

3. There is a problem that must be synchronized first. Before calculation, the client must first select t shared servers. After the selection of t shared servers is completed, it must also find a data group that matches the t shared servers and notify them , when one of the servers is destroyed, the entire process of selecting the shared server above must be repeated;

4. It is difficult for the client (CA or Web server) to remember the change of the shared server every time, and it is not easy to manage and expand. When the client is online, it is even more difficult to expand, resulting in the need to Update the client.

Victor Shoup of IBM Research-Zurich Institute published an article called "Practical threshold signatures" at the European Cryptography Annual Conference in 2000, which also introduced a theoretical scheme. This scheme uses RSA strong prime number, its secret prime number p=2p'+1, q=2q'+1. All interpolation equations are performed in rings modulo m=p'q'. Because M ^4m modulo N is equal to 1, the square is added once when calculating separately, and the combiner (Combiner) squares each result again to obtain M ^4Δ(gm+d) . where Δ=(k!) ² , and g is an integer. In this scheme, _ci is completed by a combiner, which eliminates the synchronization problem before calculation, but brings the calculation difficulty of the combiner and reduces the calculation performance. As the synthesizer must compute:

$\mathrm{<span\; class="notranslate">\; W</span>}<span\; class="notranslate">\; =</span>{\mathrm{<span\; class="notranslate">\; the\; y</span>}}_{{\mathrm{<span\; class="notranslate">\; i</span>}}_{\mathrm{<span\; class="notranslate">\; 1</span>}}}^{\mathrm{<span\; class="notranslate">\; 2</span>}\mathrm{<span\; class="notranslate">\; \&lambda;</span>}{\mathrm{<span\; class="notranslate">\; c</span>}}_{{\mathrm{<span\; class="notranslate">\; i</span>}}_{\mathrm{<span\; class="notranslate">\; 1</span>}}}}{\mathrm{<span\; class="notranslate">\; the\; y</span>}}_{{\mathrm{<span\; class="notranslate">\; i</span>}}_{\mathrm{<span\; class="notranslate">\; 2</span>}}}^{\mathrm{<span\; class="notranslate">\; 2</span>}\mathrm{<span\; class="notranslate">\; \&lambda;</span>}{\mathrm{<span\; class="notranslate">\; c</span>}}_{{\mathrm{<span\; class="notranslate">\; i</span>}}_{\mathrm{<span\; class="notranslate">\; 2</span>}}}}<span\; class="notranslate">\; \&Center\; Dot;</span><span\; class="notranslate">\; \&Center\; Dot;</span><span\; class="notranslate">\; \&Center\; Dot;</span>{\mathrm{<span\; class="notranslate">\; the\; y</span>}}_{{\mathrm{<span\; class="notranslate">\; i</span>}}_{\mathrm{<span\; class="notranslate">\; t</span>}}}^{\mathrm{<span\; class="notranslate">\; 2</span>}\mathrm{<span\; class="notranslate">\; \&lambda;</span>}{\mathrm{<span\; class="notranslate">\; c</span>}}_{{\mathrm{<span\; class="notranslate">\; i</span>}}_{\mathrm{<span\; class="notranslate">\; t</span>}}}}$

Among them, y _i is the calculation result of each sharing server, λ=k! .

It can be seen that the characteristics and shortcomings of this scheme are:

1. It is still a single-layer sharing structure composed of sharing servers. Its synthesizer does not store any secrets and can be synthesized by any device;

2. The calculation amount of the synthesizer is close to or equivalent to t signatures, which is far greater than the calculation amount of the sharing server. Even if the algorithm can be implemented, it cannot be used for actual signatures;

3. Requiring the use of strong prime numbers will limit some applications;

4. It is only theoretically stated that when adding or deleting a shared server will not affect other devices, but only provides mathematical formulas, without any implementation and system structure instructions.

Yair Frankel of New York CertCo Company and others proposed another scheme, but did not provide the framework and details of system realization. In their scheme, it is proposed to let the coefficients a _i of polynomials be in {0, L, . . . , 2L ³ N ^2+e t), where L=k! . And take x _i belongs to [1, 2, ..., k-1]. Since all f( _xi ) can be divided by L, the calculation of _bi can be performed in integers without the inverse operation. The scheme can be performed with the general RSA algorithm without strong prime numbers of RSA. Because the selection of its parameters is greatly limited, it brings the complexity of the algorithm principle and security proof. When the shared server calculates _bi , because _bi depends on the selection of _xi , there is also a synchronization problem.

As can be seen from the description of its mathematical scheme, this scheme has the following disadvantages:

1. Adopt equal secret sharing, that is, sharing is a single-layer structure;

2. The selection of parameters is limited, which proves that its security is very complicated and increases the possibility of loopholes;

3. There is a problem of synchronization, and if the synchronization is removed, the calculation amount of the synthesizer will be greatly increased.

The above scheme of IBM Research-Zurich Institute and the scheme of New York CertCo are both based on the scheme of Shamir's secret sharing, using the LaGrange interpolation equation. In the original Shamir secret sharing scheme, a secret key can be generated by randomly taking t keys. However, in the original Shamir scheme, the secret key must be recovered first, which is undesirable in any scheme. Because the secure signature scheme must first ensure that the secret key cannot be recovered in any device.

The basic principle of this Shamir-based secret sharing scheme is:

given a polynomial $f\left(x\right)=\underset{i=0}{\overset{t-1}{\mathrm{\&Sigma;}}}{a}_i{x}_i,$ Using the LaGrange interpolation formula, there are:

$\mathrm{<span\; class="notranslate">\; f</span>}<span\; class="notranslate">\; (</span>\mathrm{<span\; class="notranslate">\; x</span>}<span\; class="notranslate">\; )</span><span\; class="notranslate">\; =</span>\underset{\mathrm{<span\; class="notranslate">\; i</span>}<span\; class="notranslate">\; =</span>\mathrm{<span\; class="notranslate">\; 1</span>}}{\overset{\mathrm{<span\; class="notranslate">\; t</span>}}{\mathrm{<span\; class="notranslate">\; \&Sigma;</span>}}}<span\; class="notranslate">\; (</span>\mathrm{<span\; class="notranslate">\; f</span>}<span\; class="notranslate">\; (</span>{\mathrm{<span\; class="notranslate">\; x</span>}}_{\mathrm{<span\; class="notranslate">\; i</span>}}<span\; class="notranslate">\; )</span>\underset{\mathrm{<span\; class="notranslate">\; j</span>}<span\; class="notranslate">\; =</span>\mathrm{<span\; class="notranslate">\; 1</span>}<span\; class="notranslate">\; ,</span>\mathrm{<span\; class="notranslate">\; t</span>}}{\overset{\mathrm{<span\; class="notranslate">\; j</span>}<span\; class="notranslate">\; \&NotEqual;</span>\mathrm{<span\; class="notranslate">\; i</span>}}{\mathrm{<span\; class="notranslate">\; \&Pi;</span>}}}\frac{\mathrm{<span\; class="notranslate">\; x</span>}<span\; class="notranslate">\; -</span>{\mathrm{<span\; class="notranslate">\; x</span>}}_{\mathrm{<span\; class="notranslate">\; j</span>}}}{{\mathrm{<span\; class="notranslate">\; x</span>}}_{\mathrm{<span\; class="notranslate">\; i</span>}}<span\; class="notranslate">\; -</span>{\mathrm{<span\; class="notranslate">\; x</span>}}_{\mathrm{<span\; class="notranslate">\; j</span>}}}<span\; class="notranslate">\; )</span><span\; class="notranslate">\; -</span><span\; class="notranslate">\; -</span><span\; class="notranslate">\; -</span><span\; class="notranslate">\; (</span>\mathrm{<span\; class="notranslate">\; 1</span>}<span\; class="notranslate">\; )</span>$

Choose t x _i and f( _xi ), you can get:

${\mathrm{<span\; class="notranslate">\; a</span>}}_{\mathrm{<span\; class="notranslate">\; 0</span>}}<span\; class="notranslate">\; =</span>\mathrm{<span\; class="notranslate">\; f</span>}<span\; class="notranslate">\; (</span>\mathrm{<span\; class="notranslate">\; 0</span>}<span\; class="notranslate">\; )</span><span\; class="notranslate">\; =</span>\underset{\mathrm{<span\; class="notranslate">\; i</span>}<span\; class="notranslate">\; =</span>\mathrm{<span\; class="notranslate">\; 1</span>}}{\overset{\mathrm{<span\; class="notranslate">\; t</span>}}{\mathrm{<span\; class="notranslate">\; \&Sigma;</span>}}}<span\; class="notranslate">\; (</span>\mathrm{<span\; class="notranslate">\; f</span>}<span\; class="notranslate">\; (</span>{\mathrm{<span\; class="notranslate">\; x</span>}}_{\mathrm{<span\; class="notranslate">\; i</span>}}<span\; class="notranslate">\; )</span>\underset{\mathrm{<span\; class="notranslate">\; j</span>}<span\; class="notranslate">\; =</span>\mathrm{<span\; class="notranslate">\; 1</span>}<span\; class="notranslate">\; ,</span>\mathrm{<span\; class="notranslate">\; t</span>}}{\overset{\mathrm{<span\; class="notranslate">\; j</span>}<span\; class="notranslate">\; \&NotEqual;</span>\mathrm{<span\; class="notranslate">\; i</span>}}{\mathrm{<span\; class="notranslate">\; \&Pi;</span>}}}\frac{<span\; class="notranslate">\; -</span>{\mathrm{<span\; class="notranslate">\; x</span>}}_{\mathrm{<span\; class="notranslate">\; j</span>}}}{{\mathrm{<span\; class="notranslate">\; x</span>}}_{\mathrm{<span\; class="notranslate">\; i</span>}}<span\; class="notranslate">\; -</span>{\mathrm{<span\; class="notranslate">\; x</span>}}_{\mathrm{<span\; class="notranslate">\; j</span>}}}<span\; class="notranslate">\; )</span><span\; class="notranslate">\; -</span><span\; class="notranslate">\; -</span><span\; class="notranslate">\; -</span><span\; class="notranslate">\; (</span>\mathrm{<span\; class="notranslate">\; 2</span>}<span\; class="notranslate">\; )</span>$

You can set a ₀ as the secret key d, at this time, the signature calculation for a HASH value M is:

${\mathrm{<span\; class="notranslate">\; m</span>}}^{\mathrm{<span\; class="notranslate">\; d</span>}}<span\; class="notranslate">\; =</span>{\mathrm{<span\; class="notranslate">\; m</span>}}^{\mathrm{<span\; class="notranslate">\; f</span>}<span\; class="notranslate">\; (</span>\mathrm{<span\; class="notranslate">\; 0</span>}<span\; class="notranslate">\; )</span>}<span\; class="notranslate">\; =</span>\underset{\mathrm{<span\; class="notranslate">\; i</span>}<span\; class="notranslate">\; =</span>\mathrm{<span\; class="notranslate">\; 1</span>}}{\overset{\mathrm{<span\; class="notranslate">\; t</span>}}{\mathrm{<span\; class="notranslate">\; \&Pi;</span>}}}{\mathrm{<span\; class="notranslate">\; m</span>}}^{\mathrm{<span\; class="notranslate">\; f</span>}<span\; class="notranslate">\; (</span>{\mathrm{<span\; class="notranslate">\; x</span>}}_{\mathrm{<span\; class="notranslate">\; i</span>}}<span\; class="notranslate">\; )</span>\underset{\mathrm{<span\; class="notranslate">\; j</span>}<span\; class="notranslate">\; =</span>\mathrm{<span\; class="notranslate">\; 1</span>}<span\; class="notranslate">\; ,</span>\mathrm{<span\; class="notranslate">\; t</span>}}{\overset{\mathrm{<span\; class="notranslate">\; j</span>}<span\; class="notranslate">\; \&NotEqual;</span>\mathrm{<span\; class="notranslate">\; i</span>}}{\mathrm{<span\; class="notranslate">\; \&Pi;</span>}}}\frac{<span\; class="notranslate">\; -</span>{\mathrm{<span\; class="notranslate">\; x</span>}}_{\mathrm{<span\; class="notranslate">\; j</span>}}}{{\mathrm{<span\; class="notranslate">\; x</span>}}_{\mathrm{<span\; class="notranslate">\; i</span>}}<span\; class="notranslate">\; -</span>{\mathrm{<span\; class="notranslate">\; x</span>}}_{\mathrm{<span\; class="notranslate">\; j</span>}}}}<span\; class="notranslate">\; =</span>\underset{\mathrm{<span\; class="notranslate">\; i</span>}<span\; class="notranslate">\; =</span>\mathrm{<span\; class="notranslate">\; 1</span>}}{\overset{\mathrm{<span\; class="notranslate">\; t</span>}}{\mathrm{<span\; class="notranslate">\; \&Pi;</span>}}}{\mathrm{<span\; class="notranslate">\; m</span>}}^{{\mathrm{<span\; class="notranslate">\; b</span>}}_{\mathrm{<span\; class="notranslate">\; i</span>}}}<span\; class="notranslate">\; -</span><span\; class="notranslate">\; -</span><span\; class="notranslate">\; -</span><span\; class="notranslate">\; (</span>\mathrm{<span\; class="notranslate">\; 3</span>}<span\; class="notranslate">\; )</span>$

in $b_i=f\left(x_i\right)*c_i=f\left(x_i\right)\underset{j=1,t}{\overset{j\&NotEqual;i}{\mathrm{\&Pi;}}}\frac{-x_j}{x_i-x_j}---\left(4\right)$

In this way, the secret key d can be divided into k shared servers (k≥t). Each sharing server calculates M ^bi , and then a synthesizer multiplies the calculation results of each sharing server to obtain M ^d , and any sharing server will not disclose the secret key d. Since there is a division calculation in b _i in formula (4), it is easy to think of finding a field or ring Z _v for calculation. Among them, the condition that must be satisfied is: v is a prime number, or the value of the determinant of all t-order (Vandermonde) matrices formed by x _i is guaranteed to be mutually prime to v.

In general, the result of calculating M ^bi separately is to do multiplication: $\underset{i=1}{\overset{t}{\mathrm{\&Pi;}}}{m}^{b_i}=m^{d+\mathrm{wv}}.$ How to remove the influence of v, many people think of using Φ(N), because M ^Φ(N) =1. But choosing v=Φ(N) will make the selection of x _i greatly limited by the above conditions, and knowing a certain element o and its inverse o ^-1 to Φ(N), we can find Φ(N), obviously this is not safe.

Therefore, it can be seen from the theory that the above schemes have obvious weaknesses, and there are still many problems to be solved before the actual application.

Contents of the invention

The purpose of the present invention is to design a digital signature system and security signature method, which is an intrusion-tolerant security signature system and method. On the basis of the existing basic principles of CA security, the problem of pre-synchronization can be eliminated, and online CA can be satisfied. The security requirements of the system can also ensure that the system secrets are not leaked when some components of the system are attacked or occupied, or when some key components of the system conspire.

In the secure digital signature method of the present invention, the CA is based on the RSA algorithm. The method should at least meet the following conditions:

1. Although the intruder attacks or occupies several components in the system, or some key components conspire to attack, they cannot obtain the private key;

2. The system is easy to expand. When a shared calculator needs to be added, it will not affect the work of the entire system;

3. The management during operation is simple. Management includes adding, removing, and modifying service hardware and software. When there are system management and configuration activities, the system operation cannot be affected;

4. When one or more devices are damaged, the normal service will not be affected;

5. When a shared computing unit is damaged, the operating efficiency of the entire system will not decrease too much, that is, the task allocation unit does not need to know any information about the task executor;

6. When starting the calculation, any device does not need to know who its partner is, so there is no need for a designated organization of the cooperation group (pre-synchronization);

7. The algorithm and principle of the system should be very simple;

8. After the design is completed, the operating efficiency of the entire system should be kept at the same level as the conventional system.

The technical scheme that realizes the object of the present invention is such: a kind of safe digital signature system, is used for obtaining digital signature, is characterized in that:

Including at least one online task distributor, k online secret sharing operators, m online secret sharing synthesizers and offline sub-key distributors; the offline sub-key distributors are used during system initialization or system configuration Connect with k secret-sharing operators and m secret-sharing synthesizers to issue sub-keys, including: generating random numbers corresponding to k secret-sharing operators and distributing them as the first sub-key to k secret-sharing operators , and the corresponding m secret-sharing synthesizers calculate the second sub-key and pre-store it in m secret-sharing synthesizers; the online task distributor connects with k secret-sharing operators through the first broadcast channel, and calculates the digital signature During the processing, the M value that needs to be signed is sent to k secret sharing operators, and each secret sharing operator calculates according to the M value and the first subkey, and sends the calculation result and the M value to m secret sharing operators through the second broadcast channel. A secret sharing synthesizer, each secret sharing synthesizer calculates and obtains a digital signature according to the receiving result, the M value and the pre-stored second subkey, and k and m are positive integers.

More preferably, it also includes a separately set output interface device, which is connected with m secret sharing synthesizers through the third broadcast channel.

More preferably, an output interface device is set in the online task allocator to connect with the m secret sharing synthesizers through the first broadcast channel.

The at least one online task distributor, k online secret sharing operators, m online secret sharing synthesizers, and offline subkey distributors all use common computers or servers.

The first broadcast channel, the second broadcast channel and the third broadcast channel are physically connected channels or independent channels that are not connected at all.

The technical solution for realizing the purpose of the present invention is still like this: a safe digital signature method, including issuing and calculating digital signatures of subkeys, is characterized in that:

The issuance of the subkey includes the following processing steps:

A. Set up a secure digital signature system, including online task distributors, online k secret sharing operators, online m secret sharing synthesizers, broadcast channels and offline subkey distributors, where k and m are positive integer;

B. The offline subkey distributor expresses the saved digital signature private key d as the sum of t first subkeys dj and a second subkey ci, where d, t, c, j, and i are all Positive integer and let t<k, j is the serial number of the first subkey dj variable;

C. The offline sub-key distributor distributes k random numbers as the first sub-key d _j to k secret sharing operators, and obtains a set of second sub-keys by subtraction according to the sum formula in step B Key c _i and its equation combination representation, put all the second subkey c _i and its equation combination representation in a large group;

D. The off-line sub-key distributor conducts an exhaustive search for all the second sub-keys _ci and their equation combination representations in the large group according to the security conditions of the synthesizer, and obtains the second sub-keys _ci and Its equation combination expresses:

E offline sub-key distributor sends m grouped second sub-keys _ci and their equation combination representations to m secret sharing synthesizers for pre-stored;

The described computing digital signature includes the following processing steps:

F. The online task distributor sends the HASH value M that needs to be signed to k secret sharing operators through the broadcast data packet through the first broadcast channel;

Among the Gk secret sharing operators, t or more secret sharing operators calculate the raising power M ^dj according to the received M value, and send the code j of the secret sharing operator, the HASH value M to be signed and the calculation result M ^dj sends the broadcast data packet to m secret sharing synthesizers through the second broadcast channel;

Hm secret sharing synthesizers compare the received result with the equation combination representation of the second subkey c _i of the pre-stored group, find a matching equation combination representation and obtain the corresponding second subkey c _i , and then combine with Multiply the exponentiation results of the matching t secret sharing operators to obtain the result R, calculate M ^ci according to the found second subkey _ci , and finally multiply M ^ci and R to obtain the digital signature S=M ^d .

More preferably, the step A also includes randomly assigning a code name to the online task allocator, assigning different code names to k secret sharing operators, and assigning m secret sharing synthesizers respectively Not the same code and set the initial value of t.

More preferably, said step C further includes:

c1. Take k random numbers less than d/t as the first subkey d _j by the offline subkey distributor;

c2. The offline sub-key distributor sends the k first sub-keys d _j to the k secret sharing operators correspondingly through management permission;

c3. Take t d _j from the k first sub-keys (d ₁ , d ₂ , d ₃ , ..., d _k ) by the offline sub-key distributor, and form them according to the combination formula $\mathrm{no}=C_k^t$ combination representations, and calculate the second sub-keys c _i corresponding to all combination representations according to the sum formula (i=1, 2, . . .

More preferably, described step D further comprises:

d1. Randomly setting an order for the combinations in the large group, and randomly setting an empty group B;

d2. Take out a second subkey _ci and its equation combination representation from the large group sequentially, record it as the combination representation A, judge whether putting A into B satisfies the safety condition of the synthesizer, if so, put it into group B and start from the large group delete the combination and the corresponding second subkey from the group, and if the security condition of the synthesizer is not satisfied, the combination and the corresponding second subkey are still kept in the large group;

d3. Repeat step d2 for all combinations in the large group;

d4. If there is still a combination representation in the large group, determine the second empty group as B, and repeat steps d2 and d3 until there is no second subkey _ci and its equation combination representation in the large group:

d5. The number m of non-empty groups formed by statistics is the m groups mentioned above.

Whether the described judgment meets the safety condition of the synthesizer further includes: comparing the serial number of the variable in the combined representation A with the serial number of the variable in the combined representation q _s in the group B, if there is in the combined representation A and in the combined representation q _s The number of serial numbers of the variables that do not exist is greater than t/2, and this combination indicates that A meets the security conditions for the combination of q _s ; if the combination indicates that A meets the security conditions for each combination in group B, the combination indicates that A is put In group B, the synthesizer security condition is satisfied.

More preferably, in the step E, the offline sub-key distributor distributes the second sub-keys c _i of the m groups and their corresponding equation combination representations to the In the m secret sharing synthesizer described above.

More preferably, the offline subkey distributor is in a physically isolated state or shut down after executing steps A, B, C, D, and E to distribute the subkeys.

More preferably, described step F further comprises:

f1. The online task distributor receives digitally signed tasks, and conducts security checks and checks;

f2. Determine a task number that is unique to the task distributor within a predetermined time for the task by the online task distributor;

f3. Broadcast the broadcast data packet composed of its code name and task number along with the HASH value M that needs to be signed to the first broadcast channel by the online task distributor;

Described step G further comprises:

g1. After receiving the broadcast, t or more secret sharing operators send a notification to the online task allocator that they have been received;

g2. t or more secret sharing calculators check the uniqueness of the task, and perform the calculation of raising the power when it is determined to be a new task;

g3. t or more secret sharing calculators will also form the code name of the online task allocator and the task number along with the code j of the secret sharing calculator, the HASH value M to be signed and the calculation result M ^dj The broadcast data packet is broadcast to the second broadcast channel;

Described step H, further comprises:

h1. The secret sharing synthesizer that receives the broadcast puts the broadcast data packets with the same task dispatcher code and task number in one group;

h2. The above-mentioned secret sharing synthesizer finds at least t broadcast data packets, and then finds an equation combination representation matching the pre-stored equation combination representation, and obtains the corresponding second subkey c _i .

The steps F, G, and H are executed sequentially to complete the calculation operation of the digital signature.

More preferably, said step H also includes a step I, by the online secret sharing synthesizer, the digital signature S=M ^d and the task distributor code number, task number to form a broadcast data packet and broadcast to an online output On the interface device, the output interface device checks the signature result with the public key, ends the digital signature if it is correct, and performs error handling or alarm if it is wrong.

More preferably, in the step I, the online secret sharing synthesizer broadcasts the broadcast data packet to a separately set online output interface device through a third broadcast channel.

More preferably, in the step I, the online secret sharing synthesizer broadcasts the broadcast data packet to the output interface device set in the task allocator through the first broadcast channel.

The secure digital signature system and method of the present invention is based on the RSA algorithm, through an unbalanced double-layer structure of secret sharing, overcomes the difficulties in system management and implementation in the background technology, and achieves the purpose of the invention.

The method and system of the present invention have the following characteristics:

1. The online task distributor can broadcast digital signature tasks without selecting a secret sharing calculator and specifying a key. When the system is updated, it can guarantee that the work of the online task distributor will not be affected. When a secret sharing calculator is suddenly damaged It will also not affect the execution time of the broadcast task (if it is designated to be calculated by a secret sharing calculator, but this device does not respond in the end, you must re-designate the device and key and start again);

2. When adding a secret sharing operator, you only need to generate a sub-key for it, and the offline sub-key distributor will compare the serial number of the newly added secret sharing operator with the serial number of the existing secret sharing operator. Equation combination, calculate the corresponding second subkey c, and then add these newly added equation combination expressions and calculated c to the secret sharing synthesizer in a way approved by key management. This addition does not affect the system works;

3. When dismantling a secret sharing calculator, it is only necessary to turn off the device. For the sake of efficiency, the combined representation of the serial number of the secret sharing calculator and the corresponding c _n in the secret sharing synthesizer can be deleted;

4. Simultaneously, the present invention, like other background technologies, also has the ability of intrusion tolerance, when less than t sets of secret sharing calculators are invaded, the system secret d will not be revealed, and because the structure of the secret sharing synthesizer is added, even if All secret-sharing calculators are hacked, and the system secret d will not be disclosed (it can also be proved theoretically that the system secret d cannot be obtained by attacking the secret-sharing synthesizer. Although there are many equations, the coefficient matrix of all equations rank is less than the number of variables);

5. It can resist the attack of the secret sharing calculator and the secret sharing synthesizer colluding with the system, that is, when a secret sharing calculator and a secret sharing synthesizer jointly attack the system, the secret d cannot be obtained.

Description of drawings

Figure 1 is a schematic diagram of the prototype structure of the CA system in the ITTC project plan studied by Stanford University.

Fig. 2 is a schematic structural diagram of a secure digital signature system of the present invention.

Fig. 3 is a schematic structural diagram of another secure digital signature system of the present invention.

Fig. 4 is a block diagram of an implementation flow of a secret sharing calculator.

Fig. 5 is a block diagram of an implementation flow of a secret sharing synthesizer.

Detailed ways

Referring to Fig. 2, the figure schematically shows a secure digital signature system structure, which adopts the RSA algorithm as the basic algorithm.

This structure includes an offline sub-key distribution machine (device, the same below) 21, at least one online task distribution machine 22, k online secret sharing calculators 23, and m online secret sharing synthesizers 24 And an independently set online output interface device 25. These devices can all be served by different ordinary computers or servers. The online task distribution machine 22 is connected with the k station secret sharing computing unit 23 through the broadcast channel B1 (such as UDP protocol channel), and the k station secret sharing computing unit 23 is connected with the m station secret sharing synthesizer 24 through the broadcast channel B2. The sharing synthesizer 24 is connected to the output interface device 25 through the broadcast channel B3, and the offline sub-key distribution machine is respectively connected to the k sub-secret sharing computing unit 23 and the m sub-secret sharing computing unit 24 (as shown in the figure) when the system is initialized or the system is configured. shown by the dotted line).

The off-line sub-key distributor 21 keeps the secret d and does not have network connection with other systems. The broadcast channels B1, B2, and B3 may be one broadcast channel that is physically connected, or broadcast channels that are completely unconnected and independent of each other.

The basic principle of realizing the whole system structure is to express a large integer as the sum of several integers, using an expression such as d=d ₁ +d ₂ +d ₃ +...+d _t +c _j , expressed by d _j Any one of d ₁ to d _t in the equation, set the private key in the digital signature as d in the equation, the number of d _j is t, d, d ₁ , d ₂ , d ₃ ...d Both _t and c _j are positive integers, and d _j uses random numbers to realize simple management. This equation expression differs from the equation expression d=d ₁ +d ₂ +d ₃ +...+d _t in the background technology in that a c _j term (i=1, 2,..., n ), thus forming a new secure and easy-to-manage system structure.

In this system structure, the sharing of secret d is completed by two layers of components. One layer of components is composed of a simple secret sharing calculator 23, and the other layer of components is composed of a secret sharing synthesizer 24. The d _j items are respectively stored in the device 23, and the c _j items are stored in the secret sharing synthesizer, thereby forming a two-layer secret sharing structure. Subkeys are stored in the two layers of equipment, respectively the first subkey d _j and the second subkey c _j . The two-layer sharing structure is also manifested in: only after the secret sharing operator of the first layer completes the calculation, the secret sharing synthesizer of the second layer can start to work; since the secret sharing synthesizer also saves the subkey c _j , so it is impossible for the secret sharing synthesizer to be replaced by other devices.

The system first completes the distribution of subkeys, and the operation process adopted is as follows:

The off-line sub-key distributor 21 generates a random d _j for each secret sharing operator 23, for a system with k secret operation sharers 23, there will be k first sub-keys d _j , j=1, 2, 3, 4, . . . , k. These first subkeys are sent to the corresponding secret sharing calculator 23 in a manner approved by key management.

It is necessary to design a suitable t in advance, and the meaning of t is that when t-1 secret sharing calculators 23 are invaded, the security of the system will not be affected. It should be guaranteed that t<k, so as to ensure that the system can obtain t results from k secret sharing calculators 23 to complete the calculation.

The offline sub-key distributor 21 takes t sub-keys out of k sub-keys, according to the equation d=d ₁ +d ₂ +d ₃ +...+d _t +c _i can then calculate c by subtraction _i . Since there are C _k ^t methods of taking t out of k, the c _i of C _k ^t equations can be calculated. here, $\mathrm{no}=C_k^t$ represents combinations such as $C_5^3=10,$ There are 10 _ci values and 10 equation combinations, and each equation combination is a combination of the corresponding t first subkey d _j subscripts (or serial numbers of variables), such an equation The label of the corresponding key d _j is the key combination. Obviously, different first subkeys in an equation combination are in different secret sharing operators, and the equation combination is only related to the subscript j of the first subkey d _j (or the serial number of the variable), Do not disclose any subkey information.

The number of bits of d _j is far less than 1/4 of the number of bits of c _i , such as when d is a number of 2048 bits, c _i is a number of 2048 bits, and d _j is a number of 500 bits or less, so as to ensure the secret sharing operation unit 23 Operation speed, thereby improving the operation speed of the entire digital signature system.

The off-line sub-key distributor 21 groups all equation combinations and corresponding _ci values according to the security conditions of the synthesizer through exhaustive search. The equation combinations in each group are limited, and then according to the number of groups (m) Correspondingly set secret sharing synthesizers (m) to store the equation combination representations of these groups and the corresponding c _i values. In the figure, five secret sharing calculators 23 (k=5) and t=3 are set as an example for illustration.

For example, the ten equations are divided into the following five groups:

First group

c ₁ ＝dd ₁ -d ₂ -d ₃ Equation combination representation (1, 2, 3)

c ₆ ＝dd ₁ -d ₄ -d ₅ Equation combination representation (1, 4, 5)

Second Group

c ₁₀ = dd ₃ -d ₄ -d ₅ Equation combination representation (3, 4, 5)

c ₃ ＝dd ₁ -d ₂ -d ₅ Equation combination representation (1, 2, 5)

The third group

c ₂ ＝dd ₁ -d ₂ -d ₄ Equation combination representation (1, 2, 4)

c ₈ ＝dd ₂ -d ₃ -d ₅ Equation combination representation (2, 3, 5)

Fourth group

c ₄ ＝dd ₁ -d ₃ -d ₄ Equation combination representation (1, 3, 4)

c ₉ ＝dd ₂ -d ₄ -d ₅ Equation combination representation (2, 4, 5)

fifth group

c ₇ ＝dd ₂ -d ₃ -d ₅ Equation combination representation (2, 3, 4)

c ₅ ＝dd ₁ -d ₃ -d ₅ Equation combination representation (1, 3, 5)

Then select five secret sharing synthesizers 24 to store these five groups of parameters respectively.

How to group is the key problem of implementing the scheme of the present invention. From the perspective of the secret sharing combiner 24, its _ci is known, and the others are all unknown variables. The security condition of the synthesizer is put forward according to its equation and system security requirements, namely: a new equation obtained by linear combination of the equations contained in a secret sharing synthesizer, and the number of variables is greater than t.

If this condition is met, the collusion attack on the system by the synthesizer and the shared operator can be avoided. However, this condition is too complex to be implemented with a program or process. Therefore, in order to achieve safe synthesis, there must be a feasible algorithm.

By using the particularity of the equation, the security condition can be simplified as: an equation obtained by a linear combination of any two equations in a synthesizer, and the number of variables is greater than t.

For this simplified security condition, its implementation includes the following steps:

Step 1, according to the expression of d=d _j +...+d _t + _ci and the combined formula C _k ^t , there are all 10 kinds of combined expressions of c _i , which are respectively:

c ₁ ＝dd ₁ -d ₂ -d ₃ Equation combination representation (1, 2, 3)

c ₂ ＝dd ₁ -d ₂ -d ₄ Equation combination representation (1, 2, 4)

c ₃ ＝dd ₁ -d ₂ -d ₅ Equation combination representation (1, 2, 5)

c ₄ ＝dd ₁ -d ₃ -d ₄ Equation combination representation (1, 3, 4)

c ₅ ＝dd ₁ -d ₃ -d ₅ Equation combination representation (1, 3, 5)

c ₆ ＝dd ₁ -d ₄ -d ₅ Equation combination representation (1, 4, 5)

c ₇ ＝dd ₂ -d ₃ -d ₅ Equation combination representation (2, 3, 4)

c ₈ ＝dd ₂ -d ₃ -d ₅ Equation combination representation (2, 3, 5)

c ₉ ＝dd ₂ -d ₄ -d ₅ Equation combination representation (2, 4, 5)

c ₁₀ = dd ₃ -d ₄ -d ₅ Equation combination representation (3, 4, 5)

Put them all into one big group, specifying the above order;

Step 2, take out a combination sequentially from the large group, such as the equation combination expression (1, 2, 3), c ₁ =dd ₁ -d ₂ -d ₃ , and put it into the first grouping, the grouping denoted as B;

Step 3, take out a combination from the large group sequentially, such as the combination expression of the equation (1, 2, 4), c ₂ =dd ₁ -d ₂ -d ₄ , record it as combination expression A, and express the combination in group B Both are recorded as q _s ;

Step 4, comparing the combination representation A with the existing combination representation in the first group B, and judging whether the comparison result meets the security conditions, including:

Step 41, compare the sequence numbers of the variables in combination representation A with the sequence numbers of the variables in each combination representation q _s in the grouping, if the sequence numbers of the variables that are present in combination representation A and not in combination representation q _s are greater than 3/2 (t/2), the combination means that even if q _s satisfies the safety condition, if the combination means (1, 2, 3) is compared with (3, 4, 5), the number of different serial numbers is 2, and when t=3 The combination expression (3, 4, 5) meets the safety condition, obviously the combination expression of the equation (1, 2, 3), c ₁ = dd ₁ -d ₂ -d ₃ and the combination expression A(1, 3, 5), c ₅ = dd ₁ -d ₃ -d ₅ , when compared, the number of its different serial numbers is 1, can not meet the safety condition; put the combination representation A that satisfies the safety condition for all the combinations in B in the group B, will not be able to Group representations that meet the security conditions remain in the large group;

Step 42, compare all combination representations in the large group one by one, let the combination representations that meet the safety conditions continue to be put into group B, the result of the operation is that there is no combination representation in the large group that can meet the synthesizer safety conditions, that is, at this time All combinations that can satisfy the synthesizer safety condition in group B are only (1, 2, 3) and (3, 4, 5);

Step 5, then determine the second group, and repeat steps 2, 3, and 4 until there is no combination representation in the large group, and five groups as mentioned above are formed.

After the process is completed, the combination representations of all non-empty groups are taken out, and the combination representations in each group are correspondingly pre-stored in a secret sharing synthesizer in a way allowed by management.

According to the different combination representations randomly selected, the combination representations of the formed m groups will also be different, such as:

First group

c ₁ ＝dd ₁ -d ₂ -d ₃ Equation combination representation (1, 2, 3)

c ₉ ＝dd ₂ -d ₄ -d ₅ Equation combination representation (2, 4, 5)

Second Group

c ₂ ＝dd ₁ -d ₂ -d ₄ Equation combination representation (1, 2, 4)

c ₅ ＝dd ₁ -d ₃ -d ₅ Equation combination representation (1, 3, 5)

The third group

c ₃ ＝dd ₁ -d ₂ -d ₅ Equation combination representation (1, 2, 5)

c ₄ ＝dd ₁ -d ₃ -d ₄ Equation combination representation (1, 3, 4)

Fourth group

c ₆ ＝dd ₁ -d ₄ -d ₅ Equation combination representation (1, 4, 5)

c ₇ ＝dd ₂ -d ₃ -d ₅ Equation combination representation (2, 3, 4)

fifth group

c ₈ ＝dd ₂ -d ₃ -d ₅ Equation combination representation (2, 3, 5)

The sixth group

c ₁₀ = dd ₃ -d ₄ -d ₅ Equation combination representation (3, 4, 5)

The final result of this grouping method is to set up six secret sharing synthesizers to pre-store the six groups of _ci and their equation combination representations respectively.

Therefore, each secret sharing combiner 24 does not store all combinations for all subkeys d _j , but all secret sharing combiners 24 store content and results that can guarantee to contain all d _j combinations for secret sharing operators.

The system performs the operation process of calculating the digital signature. During the operation, the secret sharing calculator 23 calculates the raising power for the subkey it owns, and the secret sharing combiner finds a matching combination, calculates and synthesizes the result.

When calculating a digital signature: the task distributor sends the HASH value M that needs to be signed to k secret sharing operators 23 via the broadcast channel B1, as long as there are more than t correct secret sharing operators (referring to the unattacked The secret sharing calculator) can guarantee the calculation result after receiving the data;

The j-th secret sharing operator calculates the raising power M ^dj after receiving the data, each secret sharing operator calculates the raising power for the first subkey it owns, and uses its own code j, The HASH value M and the calculation result M ^dj are sent to the secret sharing synthesizer 24 through the broadcast channel B2;

The secret sharing combiner 24 compares the received data packets with the combination expressions of the equations stored in it by traversal method, finds t combination expressions that can be matched and obtains the corresponding sub-keys c _i , and then combines the matched Multiply the results of raising the power to get the result R, then calculate M ^ci according to the found _ci , and finally multiply M ^ci by R to get the digital signature S=M ^d that should be obtained;

The secret sharing synthesizer 24 sends the digital signature result S to the output interface device 25, and the output interface device 25 checks the correctness of the signature result according to the public key.

In the above calculation process, all broadcast data packets should also include: the code name of the task allocator, the task code assigned by the task allocator, etc. To ensure that the system can distinguish different tasks and support multi-task parallel operation.

Referring to Fig. 3, it is an embodiment structure of a secure digital signature system, using an offline sub-key distributor 31, five secret sharing operators 33 (k=5), five secret sharing synthesizers 34, one The online task allocator 32 also serves as an output interface device. The online task allocator 32 is connected to five secret sharing calculators 33 through the broadcast channel B1, and the five secret sharing calculators 33 are synthesized with five secret sharing calculators through the broadcast channel B2. The five secret sharing synthesizers 34 are also connected to the online task distributor 32 through the broadcast channel B1, and an offline sub-key distributor 31 is respectively connected to five secret sharing operators during system initialization or system configuration. 33 and two secret sharing synthesizers 34.

First perform the issuing operation of the subkey:

Given any code number of the online task distributor 32, such as 22, a code name of each secret sharing calculator 33, such as 1, 2, 3, 4, 5, and a code name of each secret sharing synthesizer 34, such as 1 , 2, 3, 4, 5, the system sets the initial value t=3, and the offline subkey distributor 31 grasps the secret key d;

Offline sub-key distributor 31 arbitrarily selects 5 random numbers d ₁ , d ₂ , d ₃ , d ₄ , d ₅ less than d/3(d/t), and assigns d ₁ Send to secret sharing calculator #1, send _d2 to secret sharing calculator #2, send d3 to secret sharing calculator # ₃ , send _d4 to secret sharing calculator #4, send _d5 to No. 5 Secret Sharing Calculator;

According to the expression of d=d _j +...+d _t + _ci and the combination formula C _k ^t , a large group is formed, which contains 10 kinds of equation combination expressions of _ci and 10 _ci ;

Obtain the combined representation of five groups and their c _i through exhaustive search according to the security conditions of the sharer;

The off-line sub-key distributor 31 sends the _ci values of the five groups and the corresponding equation combination expressions to the five secret sharing synthesizers 34 in a management-allowed manner, that is, each secret sharing synthesizer 34 Each has two equation combination representations and two corresponding _ci values.

After the subkey distribution is completed, the off-line subkey distributor 31 can be shut down.

The workflow for computing a digital signature is:

The task that must be signed is received by the online task distributor 32, and corresponding security checks and checks are performed, and then the HASH value M that needs to be signed is obtained;

Determine a task number for the current signature by the online task distributor 32, which should be unique to the task distributor within a certain time frame (such as two days);

The task allocator broadcasts its own code (22), the task number of the task, and the HASH value M into a data packet to the broadcast channel B1;

After the secret sharing calculator j (at least 3 secret sharing calculators in the secret sharing calculator 33, t=3) receives the broadcast, it notifies the task distributor 32 that it has successfully received;

The secret sharing calculator j checks the uniqueness of the task, and calculates M ^dj when the task is a new task;

Secret sharing calculator j broadcasts its own code j, task dispatcher code 22, task number, HASH value M and calculation result M ^dj to the broadcast channel B2;

The secret sharing synthesizer 34 receives the broadcast data packet, and puts information with the same task distributor code number and task number in the same group;

The secret sharing synthesizer 34 checks whether there are more than three results in a set of results and three of them match the stored equation combination representation, if so, find the corresponding matching equation combination representation, obtain the corresponding c _i , and calculate M according to c _i ^ci , then calculate R (which is the product of the corresponding three results matched with the combined representation), and finally multiply M ^ci with R to get the digital signature S=M ^d that should be obtained;

The secret sharing synthesizer 34 sends the code name of the task distributor, task number and digital signature result S= ^Md to the broadcast channel B1;

After the task distributor 32 receives the digital signature result, it uses the public key to check whether the signature result is correct. If it is wrong, it will enter error processing or alarm, and if it passes the check, it will end the calculation task.

The detailed execution steps in this embodiment are also applicable to the embodiment in FIG. 2 .

The method of the invention can effectively resist the collusion attack on the system when the secret sharing synthesizer and the secret sharing calculator are united. As in the above example, any sharing synthesizer must collude with at least three secret sharing operators to obtain the secret d. And it can effectively resist the collusion attack of sharing synthesizers and sharing operators.

Referring to Fig. 4 and Fig. 5, they are block diagrams of the implementation flow of the secret sharing calculator and the secret sharing synthesizer in Fig. 2 and Fig. 3 respectively, which are a specific practical flow. Its realization is to use multi-threading technology, that is, the multi-task parallel technology used in computer operating systems, as shown in the figure, three threads: task processing program, listening program and interface program, to realize a secret sharing calculator or secret sharing synthesizer. All tasks that need to be calculated are managed by a task queue, and system parameters (including subkeys) required for calculation are also accessible to all three threads.

The task handler is specially used for calculation. Since calculation is the most time-consuming work, a separate thread is created for calculation to ensure that the interaction with the user can be maintained during calculation, and at the same time, the network data can be maintained. monitoring so as not to lose network data. The thread first uses the event synchronization mechanism to wait, which can save CPU time when there is no task, and can use system events such as EVENT in NT to perform synchronization; when the task execution thread is awakened, it scans the tasks of the system Queue, find the tasks that should be processed and process them, including the sending of data packets that should be resent.

The listener is set up to ensure that the data of network communication is not lost. A single thread is used to monitor the broadcast data of the network. This process only performs simple task processing, such as deleting a task or adding a task. When there is a new computing task , wake up the task processing thread.

The interface program is used for user interface processing, and a separate thread is also used to ensure that system parameters can be modified, subkeys can be added, etc. without affecting system operation.

The digital signature device with security function designed according to the technical scheme of the present invention can be widely used in enterprises and institutions. Each device stores a set of corresponding data for each enterprise, and the task distributor puts the enterprise code in the data when broadcasting tasks. In order to distinguish different enterprises, the secret sharing calculator finds and calculates the corresponding key according to the enterprise code, and the calculation result is sent to the synthesizer together with the enterprise code.

After the management of enterprise code is added to the whole system, the system can become the agent of users and enterprises at different levels, and carry out secure digital signatures on behalf of them. And the sub-key distributor and task distributor can be controlled by the enterprise or individual themselves. Under this structure, multiple sub-key distribution centers, multiple task distributors, multiple secret sharing calculators, and multiple secret sharing synthesizers are formed, forming a complete secure digital signature service system.

The system structure of the present invention is simple, easy to implement, and has intrusion tolerance. Although the total workload of signing a signature is increased compared with the general signature, it can ensure system security. By adopting parallel computing and making the number of bits of _dj far The number of bits is smaller than _ci (at least 4 times), so that the total signature time is basically equal to the general signature time, and more importantly, it can deal with the joint attack of the secret sharing operator and the secret sharing synthesizer on the system.

The weak point of the scheme of the present invention is: in order to resist the conspiracy of the secret sharing synthesizer and the secret sharing calculator to attack the system, the number of secret sharing synthesizers will be greatly increased. For example, when the number of secret sharing calculators becomes 6, The number of secret-sharing synthesizers will increase to 8, thus consuming too many hardware resources; in addition, such a combination of secret-sharing synthesizers and secret-sharing calculators will lead to task imbalance, that is, a digital signature task requires at least t The secret sharing calculator calculates once, but only one secret sharing synthesizer is required to participate in the work. For example, in the above example, the number of secret sharing synthesizers is more than the number of secret sharing calculators, and there is an imbalance between the two. The problem.

Claims (17)

1. A safe digital signature system for obtaining a digital signature, characterized in that: Including at least one online task distributor, k online secret sharing operators, m online secret sharing synthesizers and offline sub-key distributors; the offline sub-key distributors are used during system initialization or system configuration Connect with k secret-sharing operators and m secret-sharing synthesizers to issue sub-keys, including: generating random numbers corresponding to k secret-sharing operators and distributing them as the first sub-key to k secret-sharing operators , and the corresponding m secret-sharing synthesizers calculate the second sub-key and pre-store it in m secret-sharing synthesizers; the online task distributor connects with k secret-sharing operators through the first broadcast channel, and calculates the digital signature During the processing, the M value that needs to be signed is sent to k secret sharing operators, and each secret sharing operator calculates according to the M value and the first subkey, and sends the calculation result and the M value to m secret sharing operators through the second broadcast channel. A secret sharing synthesizer, each secret sharing synthesizer calculates and obtains a digital signature according to the receiving result, the M value and the pre-stored second subkey, and k and m are positive integers. 2. A secure digital signature system according to claim 1, characterized in that it further comprises a separate output interface device connected to m secret sharing synthesizers through a third broadcast channel. 3. A kind of safe digital signature system according to claim 1, characterized in that: said online task distributor is also provided with an output interface device, through said first broadcast channel and said m Secretly share synthesizer connections. 4. A secure digital signature system according to claim 1, 2 or 3, characterized in that: said at least one online task distributor, k online secret sharing operators, m online secret Shared synthesizers and offline sub-key distributors all use ordinary computers or servers. 5. A secure digital signature system according to claim 1, 2 or 3, characterized in that: the first broadcast channel, the second broadcast channel and the third broadcast channel are physically connected channels or completely Independent channels that are not connected. 6. A safe digital signature method, comprising the issuing of subkeys and calculating digital signatures, characterized in that: The issuance of the subkey includes the following processing steps: A. Set up a secure digital signature system, including online task distributors, online k secret sharing operators, online m secret sharing synthesizers, broadcast channels and offline subkey distributors, where k and m are positive integer; B. The offline sub-key distributor expresses the stored digital signature private key d as the sum of t first sub-keys d _j and a second sub-key c _i , d, t, c, j, i Both are positive integers and let t<k, j is the serial number of the first subkey d _j variable; C. The offline sub-key distributor uses k random numbers as the first sub-key d _j , distributes them to k secret sharing operators, and obtains a set of second sub-keys by subtraction according to the sum formula in step B Subkey _ci and its equation combination representation, put all the second subkey _ci and its equation combination representation in a large group; D. The off-line sub-key distributor conducts an exhaustive search for all the second sub-keys _ci and their equation combination representations in the large group according to the security conditions of the synthesizer, and obtains the second sub-keys _ci and Its equation combination expresses: E offline sub-key distributor sends m grouped second sub-keys _ci and their equation combination representations to m secret sharing synthesizers for pre-stored; The described computing digital signature includes the following processing steps: F. The online task distributor sends the HASH value M that needs to be signed to k secret sharing operators through the broadcast data packet through the first broadcast channel; Among the Gk secret sharing operators, t or more secret sharing operators calculate the raising power M ^dj according to the received M value, and send the code j of the secret sharing operator, the HASH value M to be signed and the calculation result M ^dj sends the broadcast data packet to m secret sharing synthesizers through the second broadcast channel; Hm secret sharing synthesizers compare the received result with the equation combination representation of the second subkey c _i of the pre-stored group, find a matching equation combination representation and obtain the corresponding second subkey c _i , and then combine with Multiply the exponentiation results of the matching t secret sharing operators to obtain the result R, calculate M ^ci according to the found second subkey _ci , and finally multiply M ^ci and R to obtain the digital signature S=M ^d . 7. A kind of safe digital signature method according to claim 6, characterized in that: in the described step A, also includes arbitrarily given a code name to the online task distributor, and given to k secret sharing operators respectively Set different code names, give different code names to m secret sharing synthesizers and set the initial value of t. 8. A safe digital signature method according to claim 6, characterized in that: said step C further comprises: c1. Take k random numbers less than d/t as the first subkey d _j by the offline subkey distributor; c2. The offline sub-key distributor sends the k first sub-keys d _j to the k secret sharing operators through management permission; c3. Take t d j from the k first sub-keys (d ₁ , d ₂ , d ₃ , ..., d _k ) by the offline sub-key distributor, and form _them according to the combination formula $\mathrm{no}=C_k^t$ combination representations, and calculate the second sub-keys c _i corresponding to all combination representations according to the sum formula (i=1, 2, . . . 9. A kind of safe digital signature method according to claim 6, characterized in that: Described step D further comprises: d1. Randomly set an order for the combinations in the large group, and randomly set an empty group B; d2. Take a second subkey ci _and its equation combination representation from the large group sequentially, record it as the combination representation A, judge whether putting A into B satisfies the safety condition of the synthesizer, if so, put it into group B and Delete the combination and the corresponding second subkey from the large group, and if the synthesizer security condition is not satisfied, the combination and the corresponding second subkey remain in the large group; d3. Repeat step d2 for all combinations in the large group; d4. If there is still a combination representation in the large group, determine the second empty group as B, and repeat steps d2 and d3 until there is no second subkey _ci and its equation combination representation in the large group ; d5. The number m of non-empty groups formed by statistics is the m groups mentioned above. 10. A kind of safe digital signature method according to claim 9, it is characterized in that whether said judging satisfies the safety condition of the synthesizer, further comprising: combining the sequence number of the variable in the combination representation A and the combination representation q in the group B Compare the sequence numbers of the variables in _s , if the combination indicates that there are variables in A and the combination indicates that the number of variables that are not in q _s is greater than t/2, this combination indicates that A meets the security conditions for the combination of q _s ; if the combination indicates A satisfies the security condition for each combination in group B, then the combination means that A put into group B satisfies the security condition of the combiner. 11. A kind of safe digital signature method according to claim 6, characterized in that: in the step E, the second subkey of the m groups is distributed by the off-line subkey distributor in a manner permitted by management. Key _ci and its corresponding equation combination representations are correspondingly distributed to the m secret sharing synthesizers. 12. A kind of safe digital signature method according to claim 6, characterized in that: said off-line sub-key distributor completes the distribution of sub-keys after executing steps A, B, C, D, E After that, it is physically isolated or shut down. 13. A safe digital signature method according to claim 6, characterized in that: said step F further comprises: f1. The online task distributor receives digitally signed tasks, and conducts security checks and checks; f2. Determine a task number that is unique to the task distributor within a predetermined time for the task by the online task distributor; f3. Broadcast the broadcast data packet composed of its code name and task number along with the HASH value M that needs to be signed to the first broadcast channel by the online task distributor; Described step G further comprises: g1. After receiving the broadcast, t or more secret sharing operators send a notification to the online task allocator that they have been received; g2. t or more secret sharing calculators check the uniqueness of the task, and perform the calculation of raising the power when it is determined to be a new task; g3. t or more secret sharing calculators will also form the code name of the online task allocator and the task number along with the code j of the secret sharing calculator, the HASH value M to be signed and the calculation result M ^dj The broadcast data packet is broadcast to the second broadcast channel; Described step H, further comprises: h1. The secret sharing synthesizer that receives the broadcast puts the broadcast data packets with the same task dispatcher code and task number in one group; h2. The above-mentioned secret sharing synthesizer finds at least t broadcast data packets, and then finds an equation combination representation matching the pre-stored equation combination representation, and obtains the corresponding second subkey c _i . 14. A safe digital signature method according to claim 6 or 13, characterized in that: said steps F, G, H are performed sequentially to complete the calculation operations of the digital signature. 15. A safe digital signature method according to claim 6, characterized in that: Also include a step I after the described step H, by the online secret sharing synthesizer, the digital signature S= ^Md and the task allocator code name, task number form the broadcast data packet and broadcast it to an online output interface device, and The output interface device checks the signature result with the public key, ends the digital signature if it is correct, and performs error handling or alarm if it is wrong. 16. A kind of safe digital signature method according to claim 15, is characterized in that: described step 1 is to broadcast described broadcast packet to a third broadcast channel by an online secret sharing synthesizer Separately set on the online output interface device. 17. A kind of safe digital signature method according to claim 15, is characterized in that: described step 1, is to broadcast described broadcast data packet by described first broadcast channel by online secret sharing combiner to the output interface device set in the task distributor.

Images