一种多变量公钥加密方法

摘要

本发明公开了一种多变量公钥加密方法。在密钥生成过程中，采用迭代方法构造矩阵，大大缩短了密钥的长度，便于密钥管理；采用概率加密，在加密中引入随机参数，解密方必须通过解密过程求解出该随机参数，并参与明文的解密，只有知道随机参数的大小才能正确解密明文，增加了攻击者破解密文的难度，即使在公钥相同的情况下密文也是不同的，公钥能以类似电话号码的形式公布，提高了加密安全性；基于组合优化困难问题和多变量二次多项式问题，能抵抗量子计算机的攻击，加解密速度快，能够运用于移动终端，如手机等；基于有限域上的运算，简化了运算过程；具有加法同态和减法同态，在特殊条件下具有乘法同态，能应用于云计算等新兴领域。

主权项

一种多变量公钥加密方法，其特征在于，包括如下步骤：(1)生成密钥，进一步包括如下步骤：选取有限域Z及有限域Z中的k个整数p₁,p₂,…,p_i,…,p_k，其中，i为不大于k的正整数；在有限域Z上选取如下整数：(β₁₁，β₁₂)，(β₂₁，β₂₂)，…，(β_i1，β_i2),…,(β_k1,β_k2)和(x₁,x₂,…,x_i,…,x_k)；构造与(β₁₁，β₁₂)，(β₂₁，β₂₂)，…，(β_i1，β_i2)，…，(β_k1，β_k2)和p₁,p₂,,p_i,…,p_k相关的两组参数a₁₁,a₂₁,…,a_i1,…,a_k1和a₁₂,a₂₂,…,a_i2,…,a_k2，使a_i1和a_i2的二进制长度相同；构造k×n维满秩矩阵A＝(a_ij)，j＝1,…，n，其中，j>2时，构造矩阵K_l×k和矩阵D_k×l，使其满足D·K＝λ·E_k×k，且k≥l，其中，E_k×k是单位矩阵，λ为任意非零整数；计算矩阵C＝K·A＝(c_yj)，y＝1,...,l，选取正整数h，0＜h＜n，确定随机参数ε的取值范围[1,e]，其中，t为任意正整数；选取l个整数P₁,...,P_l，满足不等式得到P₁,...,P_l的最小公倍数N；求解同余方程组得到向量d＝(d₁,d₂,…,d_j,…,d_n)；将d和h一起作为公钥，或者将d、h和N一起作为公钥，对应的私钥至少包括(x₁,x₂,…,x_i,…,x_k)、p₁,p₂,…,p_i,…,p_k、P₁,...,P_l、(β₁₁,β₁₂),(β₂₁,β₂₂),…,(β_i1,β_i2)，…，(β_k1,β_k2)和D；(2)用公钥加密，进一步包括如下步骤：获取明文M＝(m₁,…,m_n)，选定随机参数ε；用步骤(1)得到的公钥以概率加密的方式对明文进行加密，得到密文C；(3)用私钥解密，进一步包括如下步骤：求解同余方程组计算[S_A1 … S_Ak]^T＝D[C_P1 … C_Pl]^T；通过解密方法或者同步方法获取随机参数ε；通过(S_A1,…,S_Ak)和随机参数ε求解得到明文M＝(m₁,…,m_n)。