基于中国剩余定理的公钥加密算法的破解

摘要

基于中国剩余定理的快速加密算法,给出了一个启发式的格基规约攻击.该攻击利用公钥构造出格L的一组基,密文构造出目标向量t,则要恢复的明文即为格L中距离向量t很近的向量;利用Kannan的嵌入技术,在格L的基础上构造出一个新格L1,则要恢复的明文就是格L1中很短的向量.由于格L和格L1的维数分别是6和7,攻击者可以用LLL算法找到这2个向量,恢复出明文.实验结果证明攻击是有效的.%A heuristic attack against a fast public-key scheme is put forward,which is based on the Chinese remainder theorem.A basis of lattice L is constructed using the public-key and a target vector t using the ciphertext,then the plaintext is a lattice vector close to t.By Kannan＇s embedding technique,a new lattice L1 is designed from lattice L,and the plaintext will be a short vector of lattice L1.As the dimensions of L and L1 are 6 and 7,respectively,the attacker can compute the two vectors by invoking the Lenstra-Lestra-Lovasz（LLL） algorithm in practice and then obtain the plaintext.Experimental results show that the attack is validated.