| 基于中国剩余定理的公钥加密算法的破解 |
| |
| 引用本文： | 毕经国,韩立东,刘明洁.基于中国剩余定理的公钥加密算法的破解[J].北京工业大学学报,2012,38(5):768-772. |
| |
| 作者姓名： | 毕经国 韩立东 刘明洁 |
| |
| 作者单位： | 1. 山东大学数学学院,济南,250100
2. 清华大学高等研究院,北京,100084 |
| |
| 基金项目： | 国家“九七三”计划资助项目，山东大学研究生自主创新基金资助项目，清华大学自主科研计划资助项目 |
| |
| 摘 要： | 基于中国剩余定理的快速加密算法,给出了一个启发式的格基规约攻击.该攻击利用公钥构造出格L的一组基,密文构造出目标向量t,则要恢复的明文即为格L中距离向量t很近的向量;利用Kannan的嵌入技术,在格L的基础上构造出一个新格L1,则要恢复的明文就是格L1中很短的向量.由于格L和格L1的维数分别是6和7,攻击者可以用LLL算法找到这2个向量,恢复出明文.实验结果证明攻击是有效的.
|
| 关 键 词： | 公钥密码学 格基规约 最近向量问题 最短向量问题 LLL算法 |
Cryptanalysis of a Public-key Scheme Based on the Chinese Remainder Theorem |
| |
| BI Jing-guo,HAN Li-dong,LIU Ming-jie.Cryptanalysis of a Public-key Scheme Based on the Chinese Remainder Theorem[J].Journal of Beijing Polytechnic University,2012,38(5):768-772. |
| |
| Authors: | BI Jing-guo HAN Li-dong LIU Ming-jie |
| |
| Affiliation: | 1.School of Mathematics,Shandong University,Jinan 250100,China; 2.Center for Advanced Study,Tsinghua University,Beijing 100084,China) |
| |
| Abstract: | 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. |
| |
| Keywords: | public-key cryptography lattice basis reduction the closest vector problem the shortest vector problem Lenstra-Lestra-Lovasz algorithm(LLL algorithm) |
| 本文献已被 CNKI 万方数据 等数据库收录！ |
|
