Algebraic Cryptanalysis of McEliece Variants with Compact Keys
Algebraic Cryptanalysis of McEliece Variants with Compact Keys
复制标题
DOI：
10.1007/978-3-642-13190-5_14
复制
发表时间：
2010-05
期刊：
影响因子：
--
通讯作者：
J. Faugère;A. Otmani;Ludovic Perret;J. Tillich
中科院分区：
文献类型：
--
作者：
J. Faugère;A. Otmani;Ludovic Perret;J. Tillich
在本文中，我们提出了一种新的方法来研究的安全性McEliece密码系统。我们回想一下，这种密码系统依赖于纠错码的使用。自三十年前发明以来，还没有设计出能够成功恢复私钥的有效攻击。我们证明了该密码系统的私钥满足一个双齐次多项式方程组。这个属性是由于考虑的特定类别的代码是交替代码。我们已经使用这些高度结构化的代数方程，安装一个有效的密钥恢复攻击对最近的两个变种的McEliece密码系统，旨在减少公钥的大小。McEliece的这两个紧凑变体设法提出了少于20，000位的密钥。为此，他们建议使用准循环或二元结构。我们的代数攻击在计算机代数系统Magmaallows的实现找到的秘密密钥在一个可以忽略不计的时间（不到一秒），几乎所有的挑战。例如，为256位安全设计的私钥在0.06秒内通过大约217.8次操作找到。
In this paper we propose a new approach to investigate the security of the McEliece cryptosystem. We recall that this cryptosystem relies on the use of error-correcting codes. Since its invention thirty years ago, no efficient attack had been devised that managed to recover the private key. We prove that the private key of the cryptosystem satisfies a system of bi-homogeneous polynomial equations. This property is due to the particular class of codes considered which are alternant codes. We have used these highly structured algebraic equations to mount an efficient key-recovery attack against two recent variants of the McEliece cryptosystems that aim at reducing public key sizes. These two compact variants of McEliece managed to propose keys with less than 20,000 bits. To do so, they proposed to use quasi-cyclic or dyadic structures. An implementation of our algebraic attack in the computer algebra systemMagmaallows to find the secret-key in a negligible time (less than one second) for almost all the proposed challenges. For instance, a private key designed for a 256-bit security has been found in 0.06 seconds with about 217.8operations.