一种电子公文的加密方法

摘要

一种电子公文的加密方法，先进行密钥生成公钥和私钥，再加密成密文二元组，然后解密，最后进行秘密分配，本发明采用组合矩阵的公钥密码方法，其安全性与整数分解问题有关，但并不是直接基于整数分解，而是依赖于一类特殊的矩阵组合问题，因此，即使整数分解问题被有效地解决了，该算法仍然有效，加密和解密只需要进行几次简单的模乘法和模加法运算，故而系统实现的代价小，同时具有加密和解密速度快的优点。

主权项

1.一种电子公文的加密方法，其特征在于，包括以下步骤：第一步，密钥生成，密钥生成方法所涉及到的矩阵的维数记为n，一对公钥和私钥按如下方式产生：随机选取一个1024RSA模数N＝pq，其中p和q是素数，而且|p|₂＝|q|₂＝512，随机选取一个n维矩阵A$A=\left[\begin{array}{cccc}{a}_{11}& a_{12}& ···& a_{1n}\\ a_{21}& a_{22}& ···& a_{2n}\\ ···& ···& ···& ···\\ a_{n1}& a_{n2}& ···& a_{\mathrm{nn}}\end{array}\right]$这里要求|a_ij|₂＝59，矩阵A在R上是可逆的并把其逆矩阵记作A^-1，随机选取四个矩阵C、D、E和F，记为$C=\left[\begin{array}{cccc}{c}_{11}& c_{12}& ···& c_{1n}\\ c_{21}& c_{22}& ···& c_{2n}\\ ···& ···& ···& ···\\ c_{n1}& c_{n2}& ···& c_{\mathrm{nn}}\end{array}\right],$$D=\left[\begin{array}{cccc}{d}_{11}& d_{12}& ···& d_{1n}\\ d_{21}& d_{22}& ···& d_{2n}\\ ···& ···& ···& ···\\ d_{n1}& d_{n2}& ···& d_{\mathrm{nn}}\end{array}\right],$$E=\left[\begin{array}{cccc}{e}_{11}& e_{12}& ···& e_{1n}\\ e_{21}& e_{22}& ···& e_{2n}\\ ···& ···& ···& ···\\ e_{n1}& e_{n2}& ···& e_{\mathrm{nn}}\end{array}\right],$$F=\left[\begin{array}{cccc}{f}_{11}& f_{12}& ···& f_{1n}\\ f_{21}& f_{22}& ···& f_{2n}\\ ···& ···& ···& ···\\ f_{n1}& f_{n2}& ···& f_{\mathrm{nn}}\end{array}\right],$其中，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，满足下面两个条件再选取另外一个矩阵$A=\left[\begin{array}{cccc}{a}_{11}^{\prime }& a_{12}^{\prime }& ···& a_{1n}^{\prime }\\ a_{21}^{\prime }& a_{22}^{\prime }& ···& a_{2n}^{\prime }\\ & ···& ···& \\ a_{n1}^{\prime }& a_{n2}^{\prime }& ···& a_{\mathrm{nn}}^{\prime }\end{array}\right]$其中，γ_ij∈Z_N，矩阵A^-1、C、D、E和F是模N可逆的，并把矩阵D和F模N的逆矩阵分别记作D^-1和F^-1，计算B＝(b_ij)_n×n≡D^-1A′(modN)G＝(g_ij)_n×n≡D^-1C(modN)H＝(h_ij)_n×n≡F^-1E(modN)则矩阵B、G和H以及模数N是公钥，由D、F、A^-1、p以及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，计算发送者密文为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)则密文为二元组(U，V)；第三步，解密，收到密文二元组(U，V)后，接收者按下列步骤获取明文M，T＝(t₁，t₂，...，t_n)^T＝DU+FV(modN)M＝(t₁，t₂，...，t_n)^T＝A^-1(w₁，w₂，...，w_n)^T其中，第四步，秘密分配，采用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次多项式f(x)＝a₀+a₁x+…+a_k-1x^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)构造线性方程组：$\left\{\begin{array}{c}{a}_0+a_1\left(i_1\right)+···+a_{k-1}{\left(i_1\right)}^{k-1}=f\left(i_1\right)\\ a_0+a_1\left(i_2\right)+···+a_{k-1}{\left(i_2\right)}^{k-1}=f\left(i_2\right)\\ ······\\ a_0+a_1\left(i_k\right)+···+a_{k-1}{\left(i_k\right)}^{k-1}=f\left(i_k\right)\end{array}\right.$因为i_l(1≤l≤k)均不相同，所以由Lagrange插值公式构造多项式：$f\left(x\right)=\underset{j=1}{\overset{k}{\Sigma }}f\left(i_j\right)\underset{\underset{l\ne j}{l=1}}{\overset{k}{\Pi }}\frac{(x-i_l)}{(i_j-i_l)}\left(\mathrm{mod}q\right)$从而得到秘密s＝f(0)，然而，参与者仅需知道f(x)的常数项f(0)而无需知道整个多项式f(x)，所以仅根据下式就可求出s：$s={(-1)}^{k-1}\underset{j=1}{\overset{k}{\Sigma }}f\left(i_j\right)\underset{\underset{l\ne j}{l=1}}{\overset{k}{\Pi }}\frac{i_l}{(i_j-i_l)}\left(\mathrm{mod}q\right)$如果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中的元素是有理数。