论文部分内容阅读
代数攻击是近年出现的重要密码分析方法,目前已被成功应用于对称和非对称密码领域中多种密码算法的分析之中。该技术借助于代数方程的思想,首先将若干加密算法实例转化为已知的明密文和未知密钥比特间的多变元代数方程组,然后通过求解该方程组还原未知密钥比特。本文研究了代数攻击的技术原理及其应用,并探讨了主要技术环节的软件实现问题,全文主要内容如下:1、首先讨论了代数攻击方法,重点归纳了求解二元域上代数方程组的算法。这类算法主要分三类:第一类是基于Gr bner基的方法,这是理论完备,应用广泛的经典求解方法;第二类来自于密码分析领域,如线性化Linearization,重线性化Relinearization以及扩展线性化方法XL等;第三类方法的代表是将解方程问题转化为可满足性问题,再利用可满足性求解器求解的方法,这是当前最有效的解方程手段。2、对AES算法的简单变体—单轮加密函数进行了代数攻击。首先在假设部分比特密钥未知条件下,利用中途相遇方法列出表征加密过程的代数方程组,再采用猜测和求解相结合的策略,通过Gr bner基方法和CryptoMiniSat求解器两种方法解方程求未知密钥比特;单机测试结果表明,用Gr bner基方法至多可求解出40比特密钥,而用CryptoMiniSat可求解出96比特密钥信息。因此,CryptoMiniSat求解器更适合于求解此类方程组。3、对Trivium算法的初始化过程与密钥流生成过程做了深入分析。主要研究了两大类问题:一是首次分析了Trivium算法及其变体的初始化过程的扩散性;二基于已知部分密钥信息条件,对Trivium算法及其变体算法进行了代数攻击,给出了最新的密码分析结果。结果表明,对此类方程组,CryptoMiniSat求解器性能与Gr bner基方法相当。4、研制了“代数攻击测试平台”软件,基于Windows XP操作系统下的VC++6.0集成开发环境,实现了针对两种算法列方程的功能与两种典型的方程求解算法,本文的所有测试数据均来自于该软件平台。