学位论文 > 优秀研究生学位论文题录展示

对对称密码的代数攻击及解多元方程组算法的研究

作　者: 张宇宏
导　师: 王小云
学　校: 山东大学
专　业: 信息安全
关键词: 代数攻击 XL算法 MQ问题 SAT问题代数免疫度
分类号: TN918.1
类　型: 硕士论文
年　份: 2008年
下　载: 240次
引　用: 1次
阅　读: 论文下载

内容摘要

近些年来,对对称密码体制的一种全新有效的攻击方法——代数攻击,在密码学界中引起了越来越多的关注。与以前传统的“统计”攻击方法不同,使用代数方法对密码体制进行密码分析的攻击方法,统称为代数攻击。其主要思想是,将密码体制内在加密活动描述为输入(密钥)和输出之间的多元方程组,并且通过求解低次超定或稀疏方程组来恢复密钥。这样,求解大型低次超定稀疏多元方程组计算上的困难性,就成为许多现代对称密码体制安全性的一个必要条件,人们也越来越多得关注于寻找求解大型多元方程组的新的快速有效算法。代数攻击与其它已有的攻击方法相比有很大的优势,其中最引人注意的特色之一就是代数攻击所需要的数据量非常少,有时1个或2个己知明文就足够了,这对攻击者来说是非常有吸引力的。这也正是为什么现在代数攻击虽然还不成熟、效率低,却仍然是潜在得非常有破坏力的原因。代数攻击的另一个优势就是,它是一种全新的分析方法,目前涉足的也许只是代数分析方法的一小部分,还有许多未知的领域没有被探索和研究。因而代数攻击的前景非常广阔,可以有很大得提高和改进,对代数攻击进行研究具有很好的理论意义和应用价值。代数攻击最早用于对公钥密码及分组密码Rijndael和Serpent的攻击,通过将恢复密钥的问题转化为求解一个多元二次方程组(MQ问题)来进行密码分析。虽然代数攻击对Rijndael和Serpent还没有可行的攻击实例,但其S盒超定稀疏方程的存在已成为Rijndael和Serpent一种本质的威胁。随着解低次多元方程组有效算法——XL算法的提出和改进,对基于LFSR流密码体制的代数攻击成为一个热门课题,其攻击思想是由高阶相关攻击的思想衍变而来的,不再把输出作为输入的函数考虑,而是研究输入流和输出流之间的代数关系。研究表明代数攻击对基于LFSR的流密码体制非常有效,多个基于LFSR的流密码对代数攻击是(本质)脆弱的。近年来对分组密码的代数攻击又有了新的研究成果,采用将MQ问题转化为SAT问题求解的算法可以破解6轮DES(仅使用一个已知明文)和全部轮的KeeLoq密码体制。本文研究了对基于LFSR流密码和分组密码的代数攻击,既有理论方面的研究,又有对具体密码算法实际的攻击方法,如Toyocrypt、LILI-128、EO、Sfinks、Rijndael、Serpent、DES、KeeLoq等。本文还研究了传统的构造Grobner基的Buchberger算法、XL算法及改进和将MQ问题转化为SAT问题求解等解方程组的算法。相较于前两种算法,第三种算法非常简单有效,而且所需已知明文的个数也相对较少,采用这种算法,可以破解6轮DES和全部轮的KeeLoq,因而研究这种算法对推动代数攻击的发展有非常积极的意义。本文重点探讨了将低次稀疏多元方程组转化为CNF-SAT问题的有效方法,并仅用一个已知明文,固定20个密钥比特,采用S-盒的门电路表示方法,列出了6轮DES 3076个方程的2900元稀疏二次方程组,转化为4203个变元、16880个子句、子句总长度为51514的SAT问题,进而用MiniSAT 2.0求解,恢复出另外36比特密钥。本文最后简单介绍了代数免疫度概念(为抵抗代数攻击产生的新的密码设计标准)的提出和扩展,指出仅用零化子定义布尔函数代数免疫度的概念不能保证所有密码体制抵抗所有类型的代数攻击,必须考察密码体制中非线性函数(如布尔函数和S盒等组件)输入和输出之间的某些“简单”多元代数关系(I/O关系),以此来建立抵抗代数攻击的新的密码设计准则。

全文目录

中文摘要  8-10
ABSTRACT  10-12
第一章绪论  12-16
  §1.1 代数攻击的提出和发展  12-13
  §1.2 代数攻击的贡献和新的研究课题  13-14
  §1.3 本文的研究重点和内容安排  14-16
第二章对基于LFSR流密码的代数攻击  16-30
  §2.1 基本模型  16-19
    §2.1.1 代数攻击的适用场景  17-18
    §2.1.2 带记忆的组成器  18-19
  §2.2 快速代数攻击  19-21
  §2.3 推广的模型和攻击方法  21-25
  §2.4 攻击实例  25-30
    §2.4.1 Toyocrypt  25
    §2.4.2 LILI-128  25-26
    §2.4.3 EO  26-27
    §2.4.4 Sfinks  27-30
第三章对分组密码的代数攻击  30-42
  §3.1 Rijndael和Serpent  30-35
    §3.1.1 Serpent中S-盒的超定方程  32
    §3.1.2 Rijndael中S-盒的超定方程  32-34
    §3.1.3 XSL攻击  34-35
  §3.2 DES  35-39
    §3.2.1 S-盒的I/O方程  35-37
    §3.2.2 求解方程  37-38
    §3.2.3 "认证的"代数攻击  38-39
  §3.3 KeeLoq  39-42
    §3.3.1 算法的简单描述  39-40
    §3.3.2 直接的代数攻击  40-41
    §3.3.3 滑动-代数攻击  41-42
第四章解方程组算法的发展  42-60
  §4.1 Gr(o|¨)bner基方法  42-44
  §4.2 XL算法  44-50
    §4.2.1 复线性化和XL算法  44-47
    §4.2.2 GF(2)上的XL算法  47-50
  §4.3 MQ问题转化为SAT问题求解  50-58
    §4.3.1 SAT问题  50-51
    §4.3.2 转化步骤  51-53
    §4.3.3 SAT求解器  53-54
    §4.3.4 6轮DES转化为CNF-SAT问题求解  54-58
  §4.4 小结  58-60
第五章代数免疫度的提出和发展  60-64
  §5.1 布尔函数的代数免疫度(零化子)  60-61
  §5.2 推广的代数免疫度  61-64
结束语  64-66
附录第1轮DES中S1的66个方程  66-68
参考文献  68-70
致谢  70-72
学位论文评阅及答辩情况表  72

对对称密码的代数攻击及解多元方程组算法的研究

内容摘要

全文目录

相似论文