CN102136911A

CN102136911A - Method for encrypting electronic document

Info

Publication number: CN102136911A
Application number: CN2011100598473A
Authority: CN
Inventors: 张善文; 周争光; 王宝仓
Original assignee: Xijing University
Current assignee: Xijing University
Priority date: 2011-03-11
Filing date: 2011-03-11
Publication date: 2011-07-27

Abstract

一种电子公文的加密方法，先进行密钥生成公钥和私钥，再加密成密文二元组，然后解密，最后进行秘密分配，本发明采用组合矩阵的公钥密码方法，其安全性与整数分解问题有关，但并不是直接基于整数分解，而是依赖于一类特殊的矩阵组合问题，因此，即使整数分解问题被有效地解决了，该算法仍然有效，加密和解密只需要进行几次简单的模乘法和模加法运算，故而系统实现的代价小，同时具有加密和解密速度快的优点。An encryption method for electronic official documents, which first generates a public key and a private key from the key, then encrypts it into a ciphertext binary group, then decrypts it, and finally distributes it secretly. It is related to the integer factorization problem, but it is not directly based on the integer factorization problem, but relies on a special class of matrix combination problems. Therefore, even if the integer factorization problem is solved efficiently, the algorithm is still effective, and encryption and decryption only need a few operations. The second-simple modular multiplication and modular addition operations, so the cost of system implementation is small, and it has the advantages of fast encryption and decryption speed.

Description

An Encryption Method for Electronic Official Documents

技术领域technical field

本发明属于电子公文加密技术领域，具体涉及一种电子公文的加密方法。The invention belongs to the technical field of electronic document encryption, and in particular relates to an electronic document encryption method.

背景技术Background technique

随着社会信息技术的迅速发展，各级政府部门通过电子公文传输、交换、共享及各种事务处理，加快了公文流转速度，提高了办公效率和资源利用率，实现了跨平台的信息交换和信息共享，一方面带来的是资源节约和工作效率的极大提高，另一方面带来的是电子公文的安全性问题。With the rapid development of social information technology, government departments at all levels have accelerated the circulation of official documents, improved office efficiency and resource utilization, and realized cross-platform information exchange and Information sharing, on the one hand, brings resource saving and great improvement in work efficiency, and on the other hand, it brings about the security of electronic documents.

电子公文是通过网络传送的，其传送和接收是在高度自由的网络环境中进行的，为了保证电子公文的安全性，需要从制作、使用、传输、保存等各方面对电子公文和公章实现加密保护。电子公文的安全性包括公文传输流程设计、身份识辨、电子排版、电子盖章及印章管理、全程加密、远程传版、收发文审计管理和可开放定制等。与一般的信息系统不同，电子公文传输系统对加密机制有着独特的要求。一般的信息加密都侧重于对信道加密，注重对接收方的身份识别，对合格的接收方并不做防范。但由于电子公文中的公章是不允许被接收方所掌握的，因此即使是合法接收方也要严加限定，为此电子公文安全传输系统采用全程加密技术，全程加密是指公文文件从电子盖章形成电子公文开始，一直以密文形式存在，不仅在信道上传输需要加密，就是在“落地”后也需要保持在加密状态，并严格处在加密卡的保护之下。全程加密不仅实现了对电子公文内容的保护，同时对电子印章的保护也起到了很好的作用。Electronic official documents are transmitted through the network, and their transmission and reception are carried out in a highly free network environment. In order to ensure the security of electronic official documents, it is necessary to implement electronic official documents and official seals from various aspects such as production, use, transmission, and storage. Encryption protection. The security of electronic official documents includes document transmission process design, identification, electronic typesetting, electronic seal and seal management, full encryption, remote version transmission, audit management of sending and receiving documents, and open customization, etc. Different from general information systems, electronic document transmission systems have unique requirements for encryption mechanisms. General information encryption focuses on encrypting the channel, focusing on the identification of the receiver, and does not take precautions against qualified receivers. However, since the official seal in the electronic official document is not allowed to be grasped by the receiver, even the legal receiver must be strictly limited. For this reason, the electronic official document security transmission system adopts full-process encryption technology. From the beginning of the formation of the electronic official document, it has always existed in the form of ciphertext. Not only does it need to be encrypted for transmission on the channel, but it also needs to be kept in an encrypted state after "landing", and it must be strictly protected by an encryption card. Whole-process encryption not only realizes the protection of the content of electronic official documents, but also plays a very good role in the protection of electronic seals.

国内外现有的电子公文加密方法可以分为两种：The existing electronic document encryption methods at home and abroad can be divided into two types:

一、采用数字水印技术实现电子公文的安全性。此类系统的共同点是采取了将电子公文信息进行数字签名后以数字水印的形式嵌入到印章图片中。这种实现方式的优点在于它能够很好地对文档的完整性进行验证。数字签名值及用户、制造商的标识信息作为水印信息嵌入到印章图像数据中，掩蔽了这些信息的存在和储存方法，由于单向散列函数的特性，使得对电子公文的任何修改都会导致公文信息哈希值的相应改变，从而在验证的时候，验证方把它与从印章中提取出来的水印信息进行比较，就会发现两次的哈希值不相等，即说明电子公文被篡改过，公文验证失败。但是此类电子签章系统也存在着一些缺点。首先从安全性的角度来说，这类系统主要采用了数字水印技术，做到了对公文的完整性的保证以及对印章图片的唯一性保证。但公文是谁签署的？如果签章者签署完毕以后，因为某种原因被解除了职务，那么系统怎么能够保证对这个人签署的公文验证不通过？系统无法说明。这是因为它们大多只是简单地使用了公钥的数字签名技术，而没有充分利用数字证书。这一切都是此类电子公文签章系统所不能解决的。其次从系统实现的代价角度来看，采用数字水印技术的电子公文安全系统是把签名值用相应的水印嵌入算法嵌入到印章图片中，在电子公文上可以用对应的水印提取算法来提取水印，如果把电子公文打印到纸张上，此时就需要用到相应的水印识别设备来识别水印。这就意味着需要另外生产对应硬件设备来支持，这样势必加大系统实现的代价。1. Use digital watermarking technology to realize the security of electronic documents. The common point of these systems is to embed the electronic document information into the seal image in the form of digital watermark after digital signature. The advantage of this implementation is that it does a good job of verifying the integrity of the document. The digital signature value and the identification information of the user and the manufacturer are embedded in the seal image data as watermark information, which conceals the existence and storage method of these information. Due to the characteristics of the one-way hash function, any modification to the electronic official document will result in The corresponding change of the information hash value, so that when verifying, the verifier compares it with the watermark information extracted from the seal, and will find that the two hash values are not equal, which means that the electronic document has been tampered with. Document verification failed. But this kind of electronic signature system also has some shortcomings. First of all, from the perspective of security, this type of system mainly uses digital watermarking technology to ensure the integrity of official documents and the uniqueness of seal pictures. But who signed the document? If the signer is dismissed for some reason after signing, how can the system guarantee that the official document signed by this person will not pass the verification? The system cannot explain. This is because most of them simply use the digital signature technology of the public key, but do not make full use of the digital certificate. All these cannot be solved by this kind of electronic official document signature system. Secondly, from the perspective of the cost of system implementation, the electronic document security system using digital watermark technology embeds the signature value into the seal image with the corresponding watermark embedding algorithm, and the corresponding watermark extraction algorithm can be used to extract the watermark on the electronic document. If the electronic document is printed on paper, a corresponding watermark recognition device is required to recognize the watermark. This means that additional corresponding hardware devices need to be produced to support it, which will inevitably increase the cost of system implementation.

二、采用公钥技术，建立认证中心(CA)中心和“印章管理中心”，实现电子公文安全性。印章管理中心的任务主要是受理印章的制作请求，对印章的制作申请进行审查，即核对申请人的身份与申请印章代表的身份是否一致，申请的信息是否有效，该印章的使用权利，申请者制作印章时是否满足相应的标准，是否拥有对应公钥的私钥等注册期的任务，并根据审查后的信息利用印章制作中心的私钥来对申请的印章进行签名后颁发。用户要进行电子公文的签章，需要向印章中心申请电子印章，经批准后，印章中心通过网络将电子印章发送给申请的用户。用户收到合法的电子印章后就可以对公文进行签章操作。这类系统也同样存在实现代价大的问题。2. Use public key technology to establish a certification center (CA) center and a "seal management center" to realize the security of electronic documents. The task of the seal management center is mainly to accept the request for making the seal, and to review the application for making the seal, that is, to check whether the identity of the applicant is consistent with the identity of the representative applying for the seal, whether the information of the application is valid, the right to use the seal, the applicant Whether to meet the corresponding standards when making the seal, whether to have the private key corresponding to the public key and other tasks during the registration period, and use the private key of the seal making center to sign the applied seal according to the information after review and issue it. To sign electronic official documents, users need to apply for an electronic seal to the seal center. After approval, the seal center will send the electronic seal to the applying user through the network. After receiving the legal electronic seal, the user can sign the official document. This type of system also has the problem of high implementation cost.

发明内容Contents of the invention

为了克服上述现有技术的缺点，本发明的目的在于提供一种电子公文的加密方法，系统实现的代价小，同时具有加密和解密速度快的优点。In order to overcome the above-mentioned shortcomings of the prior art, the object of the present invention is to provide an encryption method for electronic documents, which has the advantages of low system implementation cost and fast encryption and decryption speed.

为了达到上述目的，本发明采用的技术方案为：In order to achieve the above object, the technical scheme adopted in the present invention is:

一种电子公文的加密方法，包括以下步骤：An encryption method for an electronic document, comprising the following steps:

第一步，密钥生成，密钥生成方法所涉及到的矩阵的维数记为n，一对公钥和私钥按如下方式产生：随机选取一个1024RSA模数N＝pq，其中p和q是素数，而且|p|₂＝|q|₂＝512，随机选取一个n维矩阵AThe first step is key generation. The dimension of the matrix involved in the key generation method is recorded as n, and a pair of public key and private key is generated as follows: randomly select a 1024RSA modulus N=pq, where p and q is a prime number, and |p| ₂ ＝|q| ₂ ＝512, randomly select an n-dimensional matrix A

$A A = = [\begin{matrix} {a a}_{1111} & {a a}_{1212} & \cdot &Center Dot; \cdot &Center Dot; \cdot &Center Dot; & {a a}_{11 n no} \\ {a a}_{21 twenty one} & {a a}_{22 twenty two} & \cdot &Center Dot; \cdot &Center Dot; \cdot &Center Dot; & {a a}_{22 n no} \\ \cdot &Center Dot; \cdot &Center Dot; \cdot &Center Dot; & \cdot &Center Dot; \cdot &Center Dot; \cdot &Center Dot; & \cdot &Center Dot; \cdot &Center Dot; \cdot &Center Dot; & \cdot &Center Dot; \cdot &Center Dot; \cdot &Center Dot; \\ {a a}_{n no 11} & {a a}_{n no 22} & \cdot &Center Dot; \cdot &Center Dot; \cdot &Center Dot; & {a a}_{nn nn} \end{matrix}]$

这里要求|a_ij|₂＝59，矩阵A在R上是可逆的并把其逆矩阵记作A^-1，Here it is required that |a _ij | ₂ =59, the matrix A is invertible on R and its inverse matrix is recorded as A ^-1 ,

随机选取四个矩阵C、D、E和F，记为Randomly select four matrices C, D, E and F, denoted as

$C C = = [\begin{matrix} {c c}_{1111} & {c c}_{1212} & \cdot &Center Dot; \cdot &Center Dot; \cdot &Center Dot; & {c c}_{11 n no} \\ {c c}_{21 twenty one} & {c c}_{22 twenty two} & \cdot &Center Dot; \cdot &Center Dot; \cdot &Center Dot; & {c c}_{22 n no} \\ \cdot &Center Dot; \cdot &Center Dot; \cdot &Center Dot; & \cdot &Center Dot; \cdot &Center Dot; \cdot &Center Dot; & \cdot &Center Dot; \cdot &Center Dot; \cdot \cdot & \cdot &Center Dot; \cdot &Center Dot; \cdot &Center Dot; \\ {c c}_{n no 11} & {c c}_{n no 22} & \cdot \cdot \cdot &Center Dot; \cdot &Center Dot; & {c c}_{nn nn} \end{matrix}],,$ $D D. = = [\begin{matrix} {d d}_{1111} & {d d}_{1212} & \cdot &Center Dot; \cdot &Center Dot; \cdot \cdot & {d d}_{11 n no} \\ {d d}_{21 twenty one} & {d d}_{22 twenty two} & \cdot \cdot \cdot &Center Dot; \cdot &Center Dot; & {d d}_{22 n no} \\ \cdot \cdot \cdot &Center Dot; \cdot \cdot & \cdot \cdot \cdot &Center Dot; \cdot &Center Dot; & \cdot &Center Dot; \cdot \cdot \cdot \cdot & \cdot &Center Dot; \cdot &Center Dot; \cdot \cdot \\ {d d}_{n no 11} & {d d}_{n no 22} & \cdot &Center Dot; \cdot \cdot \cdot &Center Dot; & {d d}_{nn nn} \end{matrix}],,$ $E E. = = [\begin{matrix} {e e}_{1111} & {e e}_{1212} & \cdot \cdot \cdot \cdot \cdot &Center Dot; & {e e}_{11 n no} \\ {e e}_{21 twenty one} & {e e}_{22 twenty two} & \cdot &Center Dot; \cdot &Center Dot; \cdot &Center Dot; & {e e}_{22 n no} \\ \cdot &Center Dot; \cdot \cdot \cdot &Center Dot; & \cdot &Center Dot; \cdot &Center Dot; \cdot &Center Dot; & \cdot &Center Dot; \cdot &Center Dot; \cdot \cdot & \cdot &Center Dot; \cdot &Center Dot; \cdot &Center Dot; \\ {e e}_{n no 11} & {e e}_{n no 22} & \cdot \cdot \cdot &Center Dot; \cdot &Center Dot; & {e e}_{nn nn} \end{matrix}],,$ $F f = = [\begin{matrix} {f f}_{1111} & {f f}_{1212} & \cdot &Center Dot; \cdot &Center Dot; \cdot &Center Dot; & {f f}_{11 n no} \\ {f f}_{21 twenty one} & {f f}_{22 twenty two} & \cdot \cdot \cdot \cdot \cdot \cdot & {f f}_{22 n no} \\ \cdot \cdot \cdot \cdot \cdot \cdot & \cdot \cdot \cdot \cdot \cdot &Center Dot; & \cdot \cdot \cdot &Center Dot; \cdot \cdot & \cdot &Center Dot; \cdot \cdot \cdot &Center Dot; \\ {f f}_{n no 11} & {f f}_{n no 22} & \cdot \cdot \cdot \cdot \cdot \cdot & {f f}_{nn nn} \end{matrix}],,$

其中，a_ij，c_ij，d_ij，e_ij，f_ij分别为矩阵A，C，D，E，F的任意一个元素，且a_ij，c_ij，d_ij，e_ij，f_ij∈ZN，满足下面两个条件Among them, a _ij , c _ij , d _ij , e _ij , and f _ij are any elements of matrices A, C, D, E, and F respectively, and a _ij , c _ij , d _ij , e _ij , f _ij ∈ ZN , satisfying the following two conditions

再选取另外一个矩阵Then choose another matrix

$A A = = [\begin{matrix} {a a}_{1111}^{' '} & {a a}_{1212}^{' '} & \cdot \cdot \cdot &Center Dot; \cdot &Center Dot; & {a a}_{11 n no}^{' '} \\ {a a}_{21 twenty one}^{' '} & {a a}_{22 twenty two}^{' '} & \cdot \cdot \cdot \cdot \cdot \cdot & {a a}_{22 n no}^{' '} \\ \cdot &Center Dot; \cdot &Center Dot; \cdot \cdot & \cdot \cdot \cdot \cdot \cdot \cdot \\ {a a}_{n no 11}^{' '} & {a a}_{n no 22}^{' '} & \cdot \cdot \cdot \cdot \cdot \cdot & {a a}_{nn nn}^{' '} \end{matrix}]$

其中，

γ_ij∈Z_N，in,

γ _ij ∈ Z _N ,

矩阵A^-1、C、D、E和F是模N可逆的，并把矩阵D和F模N的逆矩阵分别记作D^-1和F^-1，计算The matrices A ^-1 , C, D, E and F are reversible modulo N, and the inverse matrices of matrices D and F modulo N are denoted as D ^-1 and F ^-1 respectively, and the calculation

B＝(b_ij)_n×n≡D^-1A′(modN)B=(b _ij ) _n×n ≡D ^-1 A′(modN)

G＝(g_ij)_n×n≡D^-1C(modN)G＝(g _ij ) _n×n ≡D ^-1 C(modN)

H＝(g_ij)_n×n≡F^-1E(modN)H=(g _ij ) _n×n ≡ F ^-1 E(modN)

则矩阵B、G和H以及模数N是公钥，由D、F、A^-1、p和q构成私钥；Then the matrix B, G and H and the modulus N are the public key, and the private key is composed of D, F, A ^-1 , p and q;

第二步，加密，将待加密明文M分为n块：m₁，m₂，...，m_n，每块的长度记为|m_i|＝l，则M的长度记为|M|₂＝ln，按照下面算法加密明文M，发送者随机选取2n个整数r₁，r₂，...，r_n，s₁，s₂，...，s_n∈Z_n，计算发送者密文为The second step is encryption. The plaintext M to be encrypted is divided into n blocks: m ₁ , m ₂ , ..., m _n , the length of each block is recorded as |m _i |=l, and the length of M is recorded as |M | ₂ = ln, according to the following algorithm to encrypt the plaintext M, the sender randomly selects 2n integers r ₁ , r ₂ ,..., r _n , s ₁ , s ₂ ,..., s _n ∈ Z _n , calculates and sends The ciphertext is

U＝(u₁，u₂，...，u_n)^T U=(u ₁ , u ₂ , . . . , u _n ) ^T

＝B(r₁，r₂，...，r_n)^T+G(m₁，m₂，...，m_n)^T，=B(r ₁ , r ₂ , . . . , r _n ) ^T +G(m ₁ , m ₂ , . . . , m _n ) ^T ,

+(s₁，s₂，...，s_n)^T(modN)+(s ₁ , s ₂ ,...,s _n ) ^T (modN)

V＝(v₁，v₂，...，v_n)^T V=(v ₁ , v ₂ , . . . , v _n ) ^T

＝H(r_n，r_n-1，...，r₁)^T+(s_n，s₁，...，s_n-2，s_n-1)^T(modN)=H(r _n , r _n-1 , ..., r ₁ ) ^T + (s _n , s ₁ , ..., s _n-2 , s _n-1 ) ^T (modN)

则密文为二元组(U，V)；Then the ciphertext is a two-tuple (U, V);

第三步，解密，收到密文二元组(U，V)后，接收者按下列步骤获取明文M，The third step is decryption. After receiving the ciphertext tuple (U, V), the receiver follows the steps below to obtain the plaintext M,

T＝(t₁，t₂，...，t_n)^T＝DU+FV(modN)T = (t ₁ , t ₂ , . . . , t _n ) ^T = DU+FV(modN)

M＝(t₁，t₂，...，t_n)^T＝A^-1(w₁，w₂，...，w_n)^T M = (t ₁ , t ₂ , ..., t _n ) ^T = A ^-1 (w ₁ , w ₂ , ..., w _n ) ^T

其中，

in,

第四步，秘密分配，采用Shamir门限秘密分割方案，Shamir门限方案按如下的一般方式构造，设GF(q)是一有限域，其中q是一大素数，满足q≥n+1，秘密s是在GF(q)\{0}上均匀选取的一个随机数，表示为s∈GF(q)\{0}，k-1个系数a₀，a₁，…，a_k-1的选取满足a_i∈_RGF(q)\{0}(i＝1，2，...，k-1)，在GF(q)上构造一个k-1次多项式The fourth step, secret distribution, uses the Shamir threshold secret partition scheme. The Shamir threshold scheme is constructed in the following general way. Let GF(q) be a finite field, where q is a large prime number, satisfying q≥n+1, and the secret s is a random number uniformly selected on GF(q)\{0}, expressed as s∈GF(q)\{0}, the selection of k-1 coefficients a ₀ , a ₁ ,...,a _k-1 Satisfy a _i ∈ _R GF(q)\{0}(i=1, 2, ..., k-1), construct a polynomial of degree k-1 on GF(q)

f(x)＝a₀+a₁x+…+a_k-1x^k-1 f(x)＝a ₀ +a ₁ x+…+a _k-1 x ^k-1

设m个参与者为p₁，p₁，…，p_m，记p_i分配到的子秘密为f(i)，如果任意k个参与者

(1≤i₁＜i₂＜…＜i_k≤m)要想得到秘密s，利用(i_l，f(i_l)|l＝1，2....，k)构造线性方程组：Let m participants be p ₁ , p ₁ ,..., p _m , and record the sub-secret allocated to p _i as f(i), if any k participants

(1≤i ₁ <i ₂ <...<i _k ≤m) To get the secret s, use (i _l , f(i _l )|l=1, 2...., k) to construct a system of linear equations:

$\{\begin{matrix} {a a}_{00} + + {a a}_{11} (({i i}_{11})) + + \cdot \cdot \cdot \cdot \cdot \cdot + + {a a}_{k k - - 11} {(({i i}_{11}))}^{k k - - 11} = = f f (({i i}_{11})) \\ {a a}_{00} + + {a a}_{11} (({i i}_{22})) + + \cdot &Center Dot; \cdot \cdot \cdot \cdot + + {a a}_{k k - - 11} {(({i i}_{22}))}^{k k - - 11} = = f f (({i i}_{22})) \\ \cdot \cdot \cdot &Center Dot; \cdot &Center Dot; \cdot &Center Dot; \cdot &Center Dot; \cdot &Center Dot; \\ {a a}_{00} + + {a a}_{11} (({i i}_{k k})) + + \cdot &Center Dot; \cdot &Center Dot; \cdot &Center Dot; + + {a a}_{k k - - 11} {(({i i}_{k k}))}^{k k - - 11} = = f f (({i i}_{k k})) \end{matrix}$

因为i_l(1≤l≤k)均不相同，所以由Lagrange插值公式构造多项式：Because i _l (1≤l≤k) are all different, the polynomial is constructed by the Lagrange interpolation formula:

$f f ((x x)) = = {Σ Σ}_{j j = = 11}^{k k} f f (({i i}_{j j})) {Π Π}_{\underset{l l &NotEqual; &NotEqual; j j}{l l = = 11}}^{k k} \frac{((x x - - {i i}_{l l}))}{(({i i}_{j j} - - {i i}_{l l}))} ((mod mod q q))$

从而得到秘密s＝f(0)，Thus get the secret s=f(0),

然而，参与者仅需知道f(x)的常数项f(0)而无需知道整个多项式f(x)，所以仅根据下式就可求出秘密s：However, participants only need to know the constant term f(0) of f(x) without knowing the entire polynomial f(x), so the secret s can be obtained only according to the following formula:

$s the s = = {((- - 11))}^{k k - - 11} {Σ Σ}_{j j = = 11}^{k k} f f (({i i}_{j j})) {Π Π}_{\underset{l l &NotEqual; &NotEqual; j j}{l l = = 11}}^{k k} \frac{{i i}_{l l}}{(({i i}_{j j} - - {i i}_{l l}))} ((mod mod q q))$

如果k-1个参与者要想获得秘密s，则构造出由k-1个方程构成的线性方程组，其中有k个未知量，对GF(q)中的任一值s₀，可设f(0)＝s₀，由此可得第k个方程，并由Lagrange插值公式得出f(x)，因此，对每一s₀∈GF(q)都有一个惟一的多项式满足式s，所以已知k-1个子秘密得不到关于秘密s的任何信息，在电子公文加密、解密过程中，取l＝450，A^-1中的元素是有理数。If k-1 participants want to obtain the secret s, a linear equation system composed of k-1 equations is constructed, in which there are k unknown quantities. For any value s ₀ in GF(q), it can be set f(0)=s ₀ , thus the kth equation can be obtained, and f(x) can be obtained by the Lagrange interpolation formula, therefore, for each s ₀ ∈GF(q), there is a unique polynomial satisfying the formula s , so the known k-1 sub-secrets can not get any information about the secret s, in the process of encrypting and decrypting electronic documents, take l=450, and the elements in A ^-1 are rational numbers.

由于本发明采用组合矩阵的公钥密码算法，其安全性与整数分解问题有关，但并不是直接基于整数分解，而是依赖于一类特殊的矩阵组合问题，因此，即使整数分解问题被有效地解决了，该算法仍然有效。在该算法中，加密和解密只需要进行几次简单的模乘法和模加法运算，故而系统实现的代价小，同时具有加密和解密速度快的优点。Because the present invention adopts the public-key cryptographic algorithm of combination matrix, its security is related to the integer decomposition problem, but not directly based on the integer decomposition, but depends on a special type of matrix combination problem, therefore, even if the integer decomposition problem is effectively Solved, the algorithm still works. In this algorithm, encryption and decryption only need several simple modular multiplication and modular addition operations, so the cost of system implementation is small, and it has the advantages of fast encryption and decryption.

具体实施方式Detailed ways

下面结合实施例对本发明进行详细说明。The present invention will be described in detail below in conjunction with examples.

第一步：密钥生成，对电子公文加密之前首先要生成密钥，密钥生成过程中所涉及到的矩阵的维数记为n，选取n＝4，一对公钥和私钥按如下方式产生：随机选取一个1024RSA模数N＝pq，其中p和q是素数，而且|p|₂＝|q|₂＝512，随机选取一个n维矩阵A，The first step: Key generation. Before encrypting the electronic document, the key must be generated first. The dimension of the matrix involved in the key generation process is recorded as n, and n=4 is selected. A pair of public key and private key is as follows Way generation: randomly select a 1024RSA modulus N=pq, wherein p and q are prime numbers, and |p| ₂ =|q| ₂ =512, randomly select an n-dimensional matrix A,

$A A = = [\begin{matrix} {a a}_{1111} & {a a}_{1212} & \cdot \cdot \cdot \cdot \cdot \cdot & {a a}_{11 n no} \\ {a a}_{21 twenty one} & {a a}_{22 twenty two} & \cdot \cdot \cdot \cdot \cdot &Center Dot; & {a a}_{22 n no} \\ \cdot \cdot \cdot &Center Dot; \cdot \cdot & \cdot &Center Dot; \cdot &Center Dot; \cdot \cdot & \cdot \cdot \cdot \cdot \cdot \cdot & \cdot &Center Dot; \cdot &Center Dot; \cdot &Center Dot; \\ {a a}_{n no 11} & {a a}_{n no 22} & \cdot \cdot \cdot &Center Dot; \cdot \cdot & {a a}_{nn nn} \end{matrix}]$

这里要求|a_ij|2＝59，矩阵A在R上是可逆的并把其逆矩阵记作A^-1，Here it is required that |a _ij |2=59, the matrix A is invertible on R and its inverse matrix is recorded as A ^-1 ,

$C C = = [\begin{matrix} {c c}_{1111} & {c c}_{1212} & \cdot &Center Dot; \cdot &Center Dot; \cdot \cdot & {c c}_{11 n no} \\ {c c}_{21 twenty one} & {c c}_{22 twenty two} & \cdot &Center Dot; \cdot \cdot \cdot &Center Dot; & {c c}_{22 n no} \\ \cdot &Center Dot; \cdot \cdot \cdot &Center Dot; & \cdot \cdot \cdot \cdot \cdot \cdot & \cdot \cdot \cdot &Center Dot; \cdot &Center Dot; & \cdot &Center Dot; \cdot \cdot \cdot \cdot \\ {c c}_{n no 11} & {c c}_{n no 22} & \cdot \cdot \cdot &Center Dot; \cdot \cdot & {c c}_{nn nn} \end{matrix}],,$ $D D. = = [\begin{matrix} {d d}_{1111} & {d d}_{1212} & \cdot &Center Dot; \cdot &Center Dot; \cdot \cdot & {d d}_{11 n no} \\ {d d}_{21 twenty one} & {d d}_{22 twenty two} & \cdot &Center Dot; \cdot &Center Dot; \cdot &Center Dot; & {d d}_{22 n no} \\ \cdot &Center Dot; \cdot \cdot \cdot \cdot & \cdot \cdot \cdot &Center Dot; \cdot \cdot & \cdot &Center Dot; \cdot &Center Dot; \cdot &Center Dot; & \cdot &Center Dot; \cdot &Center Dot; \cdot &Center Dot; \\ {d d}_{n no 11} & {d d}_{n no 22} & \cdot &Center Dot; \cdot &Center Dot; \cdot &Center Dot; & {d d}_{nn nn} \end{matrix}],,$ $E E. = = [\begin{matrix} {e e}_{1111} & {e e}_{1212} & \cdot &Center Dot; \cdot &Center Dot; \cdot \cdot & {e e}_{11 n no} \\ {e e}_{21 twenty one} & {e e}_{22 twenty two} & \cdot &Center Dot; \cdot &Center Dot; \cdot &Center Dot; & {e e}_{22 n no} \\ \cdot &Center Dot; \cdot &Center Dot; \cdot &Center Dot; & \cdot &Center Dot; \cdot &Center Dot; \cdot &Center Dot; & \cdot &Center Dot; \cdot &Center Dot; \cdot &Center Dot; & \cdot &Center Dot; \cdot &Center Dot; \cdot &Center Dot; \\ {e e}_{n no 11} & {e e}_{n no 22} & \cdot &Center Dot; \cdot &Center Dot; \cdot &Center Dot; & {e e}_{nn nn} \end{matrix}],,$ $F f = = [\begin{matrix} {f f}_{1111} & {f f}_{1212} & \cdot &Center Dot; \cdot &Center Dot; \cdot &Center Dot; & {f f}_{11 n no} \\ {f f}_{21 twenty one} & {f f}_{22 twenty two} & \cdot &Center Dot; \cdot &Center Dot; \cdot &Center Dot; & {f f}_{22 n no} \\ \cdot &Center Dot; \cdot &Center Dot; \cdot &Center Dot; & \cdot &Center Dot; \cdot &Center Dot; \cdot &Center Dot; & \cdot \cdot \cdot &Center Dot; \cdot &Center Dot; & \cdot &Center Dot; \cdot &Center Dot; \cdot &Center Dot; \\ {f f}_{n no 11} & {f f}_{n no 22} & \cdot &Center Dot; \cdot &Center Dot; \cdot &Center Dot; & {f f}_{nn nn} \end{matrix}],,$

其中，a_ij，c_ij，d_ij，e_ij，f_ij分别为矩阵A，C，D，E，F的任意一个元素，且a_ij，c_ij，d_ij，e_ij，f_ij∈Z_N，满足下面两个条件Among them, a _ij , c _ij , d _ij , e _ij , f _ij are any elements of matrices A, C, D, E, F respectively, and a _ij , c _ij , d _ij , e _ij , f _ij ∈ Z _N , satisfy the following two conditions

再选取另外一个矩阵Then choose another matrix

${A A}^{' '} = = [\begin{matrix} {a a}_{1111}^{' '} & {a a}_{1212}^{' '} & \cdot &Center Dot; \cdot &Center Dot; \cdot &Center Dot; & {a a}_{11 n no}^{' '} \\ {a a}_{21 twenty one}^{' '} & {a a}_{22 twenty two}^{' '} & \cdot \cdot \cdot &Center Dot; \cdot &Center Dot; & {a a}_{22 n no}^{' '} \\ \cdot \cdot \cdot \cdot \cdot \cdot & \cdot \cdot \cdot \cdot \cdot &Center Dot; \\ {a a}_{n no 11}^{' '} & {a a}_{n no 22}^{' '} & \cdot \cdot \cdot &Center Dot; \cdot &Center Dot; & {a a}_{nn nn}^{' '} \end{matrix}]$

其中，

γ_ij∈Z_N，in,

γ _ij ∈ Z _N ,

为使该加密算法的解密正确，要求矩阵A^-1、C、D、E和F是模N可逆的，并把矩阵D和F模N的逆矩阵分别记作D^-1和F^-1，计算In order to make the decryption of the encryption algorithm correct, the matrices A ^-1 , C, D, E and F are required to be reversible modulo N, and the inverse matrices of the matrices D and F modulo N are denoted as D ^-1 and F ^-1 respectively, calculate

B＝(b_ij)_n×n≡D^-1A′(modN)B=(b _ij ) _n×n ≡D ^-1 A′(modN)

G＝(g_ij)_n×n≡D^-1C(modN)G＝(g _ij ) _n×n ≡D ^-1 C(modN)

H＝(h_ij)_n×n≡F^-1E(modN)H=(h _ij ) _n×n ≡ F ^-1 E(modN)

第二步：加密，将待加密明文M分为n块：m₁，m₂，...，m_n，每块的长度记为|m_i|＝l，则M的长度记为|M|₂＝ln，按照下面算法加密明文M，发送者随机选取2n个整数r₁，r₂，...，r_n，s₁，s₂，...，s_n∈Z_n，计算发送者密文为The second step: Encryption, the plaintext M to be encrypted is divided into n blocks: m ₁ , m ₂ ,..., m _n , the length of each block is recorded as |m _i |=l, then the length of M is recorded as |M | ₂ = ln, according to the following algorithm to encrypt the plaintext M, the sender randomly selects 2n integers r ₁ , r ₂ ,..., r _n , s ₁ , s ₂ ,..., s _n ∈ Z _n , calculates and sends The ciphertext is

U＝(u₁，u₂，...，u_n)^T U=(u ₁ , u ₂ , . . . , u _n ) ^T

＝B(r₁，r₂，...，r_n)^T+G(m₁，m₂，...，m_n)^T =B(r ₁ ,r ₂ ,...,r _n ) ^T +G(m ₁ ,m ₂ ,...,m _n ) ^T

+(s₁，s₂，...，s_n)^T(modN)+(s ₁ , s ₂ ,...,s _n ) ^T (modN)

V＝(v₁，v₂，...，v_n)^T V=(v ₁ , v ₂ , . . . , v _n ) ^T

＝H(r_n，r_n-1，...，r₁)^T+(s_n，s₁，...，s_n-2，s_n-1)^T(modN)则电子公文加密后的密文为二元组(U，V)；＝H(r _n ，r _n-1 ，...，r ₁ ) ^T +(s _n ，s ₁ ，...，s _n-2 ，s _n-1 ) ^T (modN) then the encrypted electronic document The ciphertext of is a two-tuple (U, V);

第三步：解密，收到密文二元组(U，V)后，接收者按下列步骤获取明文M，The third step: decryption, after receiving the ciphertext two-tuple (U, V), the receiver obtains the plaintext M according to the following steps,

其中，

in,

第四步：秘密分配，对于需要将秘密分给多人掌管，并且必须同时到场才能恢复这一秘密，采用Shamir门限秘密分割方案，Shamir门限方案可按如下方式构造，设GF(q)是一有限域，其中q是一大素数，满足q≥n+1，秘密s＝(U，V)是在GF(q)\{0}上均匀选取的一个随机数，表示为s∈GF(q)\{0}，k-1个系数a₀，a₁，…，a_k-1的选取满足a_i∈_RGF(q)\{0}(i＝1，2，...，k-1)，在GF(q)上构造一个k-1次多项式Step 4: Secret distribution. For the secret that needs to be distributed to multiple people and must be present at the same time to recover the secret, the Shamir threshold secret partition scheme is adopted. The Shamir threshold scheme can be constructed as follows. Let GF(q) be a Finite fields, where q is a large prime number, satisfying q≥n+1, the secret s=(U, V) is a random number uniformly selected on GF(q)\{0}, expressed as s∈GF(q )\{0}, k-1 coefficients a ₀ , a ₁ ,...,a _k-1 are selected to satisfy a _i ∈ _R GF(q)\{0}(i=1, 2,..., k -1), construct a k-1 degree polynomial on GF(q)

f(x)＝a₀+a₁x+…+a_k-1x^k-1 f(x)＝a ₀ +a ₁ x+…+a _k-1 x ^k-1

设m个参与者为p₁，p₁，…，p_m，记p_i分配到的子密钥为f(i)，如果任意k个参与者

，(1≤i₁＜i₂＜…＜i_k≤m)要想得到秘密s，利用(i_l，f(i_l)|l＝1，2，..，k)构造线性方程组：Let m participants be p ₁ , p ₁ ,..., p _m , and record the subkey assigned to p _i as f(i), if any k participants

, (1≤i ₁ <i ₂ <...<i _k ≤m) To get the secret s, use (i _l , f(i _l )|l=1, 2, .., k) to construct a system of linear equations:

$\{\begin{matrix} {a a}_{00} + + {a a}_{11} (({i i}_{11})) + + \cdot &Center Dot; \cdot &Center Dot; \cdot \cdot + + {a a}_{k k - - 11} {(({i i}_{11}))}^{k k - - 11} = = f f (({i i}_{11})) \\ {a a}_{00} + + {a a}_{11} (({i i}_{22})) + + \cdot \cdot \cdot \cdot \cdot \cdot + + {a a}_{k k - - 11} {(({i i}_{22}))}^{k k - - 11} = = f f (({i i}_{22})) \\ \cdot \cdot \cdot &Center Dot; \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \\ {a a}_{00} + + {a a}_{11} (({i i}_{k k})) + + \cdot \cdot \cdot \cdot \cdot \cdot + + {a a}_{k k - - 11} {(({i i}_{k k}))}^{k k - - 11} = = f f (({i i}_{k k})) \end{matrix}$

因为i_l(1≤l≤k)均不相同，所以可由Lagrange插值公式构造多项式：Since i _l (1≤l≤k) are all different, polynomials can be constructed by the Lagrange interpolation formula:

从而可得秘密s＝f(0)，Thus the secret s=f(0) can be obtained,

然而，参与者仅需知道f(x)的常数项f(0)而无需知道整个多项式f(x)，所以仅根据下式就可求出s：However, the participants only need to know the constant term f(0) of f(x) and do not need to know the entire polynomial f(x), so s can be obtained only according to the following formula:

如果k-1个参与者要想获得秘密s，则构造出由k-1个方程构成的线性方程组，其中有k个未知量，对GF(q)中的任一值s₀，可设f(0)＝s₀，由此可得第k个方程，并由Lagrange插值公式得出f(x)，因此，对每一s₀∈GF(q)都有一个惟一的多项式满足式s，所以已知k-1个子秘密得不到关于秘密s的任何信息，因此这个方案是完善的，在电子公文加密、解密过程中，取l＝450，A^-1中的元素是有理数，这些数很难在计算机中进行有效的表示，因为矩阵A是模N可逆的当且仅当gcd(|A|，N)＝1，因此，对于较小的矩阵的维数n和较大的RSA数N＝pq，一个随机选取的n阶方阵总是模N可逆的。If k-1 participants want to obtain the secret s, a linear equation system consisting of k-1 equations is constructed, in which there are k unknown quantities. For any value s ₀ in GF(q), it can be set f(0)=s ₀ , thus the kth equation can be obtained, and f(x) can be obtained by the Lagrange interpolation formula, therefore, for each s ₀ ∈GF(q), there is a unique polynomial satisfying the formula s , so the k-1 sub-secrets are known and no information about the secret s can be obtained, so this scheme is perfect. In the process of encrypting and decrypting electronic documents, take l=450, the elements in A ^-1 are rational numbers, these Numbers are difficult to represent efficiently in a computer, because matrix A is reversible modulo N if and only if gcd(|A|, N)=1, therefore, for smaller matrix dimensions n and larger RSA Number N=pq, a randomly selected square matrix of order n is always modulo N invertible.

Claims

1. An encryption method of an electronic document is characterized by comprising the following steps:

firstly, generating a key, wherein the dimension of a matrix involved in the key generation method is marked as n, and a pair of a public key and a private key is generated as follows: randomly selecting a 1024RSA modulus N ═ pq, where p and q are prime numbers, and | p₂＝|q|₂Randomly selecting an n-dimensional matrix A as 512

Here, it is required that | a_ij|₂At 59, the matrix a is reversible in R and its inverse is denoted as a^-1，

Randomly select four matrices C, D, E and F, and mark them as

Wherein, a_ij，c_ij，d_ij，e_ij，f_ijIs any one element of the matrix A, C, D, E, F, respectively, and a_ij，c_ij，d_ij，e_ij，f_ij∈Z_NSatisfies the following two conditions

Another matrix is selected

Wherein,

γ_ij∈Z_N，

matrix A^-1C, D, E and F are modulo-N invertible and the matrices D and F modulo-N are denoted as D^-1And F^-1Calculating

B＝(b_ij)_n×n≡D^-1A′(modN)

G＝(g_ij)_n×n≡D^-1C(modN)

H＝(h_ij)_n×n≡F^-1E(modN)

Then the matrices B, G and H and the modulus N are public keys, numbered D, F, A^-1P and q constitute a private key;

and secondly, encrypting, namely dividing a plaintext M to be encrypted into n blocks: m is₁，m₂，...，m_nAnd the length of each block is recorded as | m_iL, then the length of M is denoted as | M₂Encrypting a plaintext M according to the following algorithm, wherein the sender randomly selects 2n integers r₁，r₂，...，r_n，s₁，s₂，...，s_n∈Z_nComputing sender ciphertext as

U＝(u₁，u₂，...，u_n)^T

＝B(r₁，r₂，...，r_n)^T+G(m₁，m₂，...，m_n)^T，

+(s₁，s₂，...，s_n)^T(modN)

V＝(v₁，v₂，...，v_n)^T

＝H(r_n，r_n-1，...，r₁)^T+(s_n，s₁，...，s_n-2，s_n-1)^T(modN) the ciphertext is a tuple (U, V);

thirdly, decryption, after receiving the ciphertext binary group (U, V), the receiver obtains the plaintext M according to the following steps,

T＝(t₁，t₂，...，t_n)^T＝DU+FV(modN)

M＝(t₁，t₂，...，t_n)^T＝A^-1(w₁，w₂，...，w_n)^T

wherein,

fourthly, secret distribution is carried out, a Shamir threshold secret segmentation scheme is adopted, the Shamir threshold scheme is constructed in the following general mode, GF (q) is a finite field, wherein q is a large prime number and satisfies that q is larger than or equal to n +1, and secrets are random numbers uniformly selected on GF (q) \ {0} and are represented as s epsilon GF (q) \ {0} and k < -1 > coefficients a₀，a₁，…，a_k-1Is selected to satisfy a_i∈_RGf (q) \ {0} (i ═ 1, 2., k-1), a polynomial of degree k-1 is constructed over gf (q)

f(x)＝a₀+a₁x+…+a_k-1x^k-1

Let m participants be p₁，p₁，…，p_mRemember p_iThe assigned sub-secret is f (i) if any k participants

，(1≤i₁＜i₂＜…＜i_kM) to obtain secret s, using (i)_l，f(i_l) 1, 2.., k) form a linear system of equations:

because i is_l(1 ≦ l ≦ k), so the polynomial is constructed from Lagrange's interpolation formula:

<math><mrow><mi>f</mi><mrow><mo>(</mo><mi>x</mi><mo>)</mo></mrow><mo>=</mo><munderover><mi>Σ</mi><mrow><mi>j</mi><mo>=</mo><mn>1</mn></mrow><mi>k</mi></munderover><mi>f</mi><mrow><mo>(</mo><msub><mi>i</mi><mi>j</mi></msub><mo>)</mo></mrow><munderover><mi>Π</mi><munder><mrow><mi>l</mi><mo>=</mo><mn>1</mn></mrow><mrow><mi>l</mi><mo>&NotEqual;</mo><mi>j</mi></mrow></munder><mi>k</mi></munderover><mfrac><mrow><mo>(</mo><mi>x</mi><mo>-</mo><msub><mi>i</mi><mi>l</mi></msub><mo>)</mo></mrow><mrow><mo>(</mo><msub><mi>i</mi><mi>j</mi></msub><mo>-</mo><msub><mi>i</mi><mi>l</mi></msub><mo>)</mo></mrow></mfrac><mrow><mo>(</mo><mi>mod</mi><mi>q</mi><mo>)</mo></mrow></mrow></math>

resulting in the secret s ═ f (0),

however, the participant only needs to know the constant term f (0) for f (x) and not the entire polynomial f (x), so s can be found only from:

<math><mrow><mi>s</mi><mo>=</mo><msup><mrow><mo>(</mo><mo>-</mo><mn>1</mn><mo>)</mo></mrow><mrow><mi>k</mi><mo>-</mo><mn>1</mn></mrow></msup><munderover><mi>Σ</mi><mrow><mi>j</mi><mo>=</mo><mn>1</mn></mrow><mi>k</mi></munderover><mi>f</mi><mrow><mo>(</mo><msub><mi>i</mi><mi>j</mi></msub><mo>)</mo></mrow><munderover><mi>Π</mi><munder><mrow><mi>l</mi><mo>=</mo><mn>1</mn></mrow><mrow><mi>l</mi><mo>&NotEqual;</mo><mi>j</mi></mrow></munder><mi>k</mi></munderover><mfrac><msub><mi>i</mi><mi>l</mi></msub><mrow><mo>(</mo><msub><mi>i</mi><mi>j</mi></msub><mo>-</mo><msub><mi>i</mi><mi>l</mi></msub><mo>)</mo></mrow></mfrac><mrow><mo>(</mo><mi>mod</mi><mi>q</mi><mo>)</mo></mrow></mrow></math>

if k-1 participants want to obtain the secret s, a linear system of k-1 equations is constructed, where there are k unknowns for any value s in GF (q)₀And f (0) may be s₀From this, the kth equation can be derived and f (x) can be derived from Lagrange's interpolation formula, thus, for each s₀e.GF (q) has a unique polynomial satisfying the formula s, so that if k-1 sub-secrets are known not to obtain any information about the secrets s, in the processes of encrypting and decrypting the electronic official document, taking l as 450, A^-1The elements in (1) are rational numbers.