代数攻击

信息工程大学田甜内容简介代数攻击的起源非线性方程组求解算法简介基于LFSR的序列密码算法的代数攻击标准代数攻击快速代数攻击布尔函数的代数免疫性简介基于NFSR的序列密码算法的代数攻击线性前馈模型的代数攻击Cube攻击结束语2什么是代数攻击通过求解一组代数方程来实现对密码算法的攻击。如何构造方程如何求解方程3代数攻击的起源1949,Shannon,《CommunicationTheoryofSecretSystems》“...thecryptanalystcansetupequationsforthedifferentkeyelementsk1,k2,…,kr(namelytheencipheringequations)...Eachoftheseequationsshouldthereforebecomplexintheki,andinvolvemanyofthem.Otherwisetheenemycansolvethesimpleonesandthenthemorecomplexonesbysubstitution.”4代数攻击的起源多变元公钥密码算法基于的困难问题：求解有限域上一组随机二次多变元多项式方程组是NP-hard问题.公钥：一组二次多变元多项式f1(x1,…,xn),f2(x1,…,xn),…,fn(x1,…,xn)k[x1,…,xn]加密：设明文(p1,p2,…,pn)kn,则密文(c1,c2,…,cn)满足c1f1(p1,p2,…,pn)c2f2(p1,p2,…,pn)…cnfn(p1,p2,…,pn)5代数攻击的起源多变元公钥密码算法Matsumoto-ImaicryptosystemJ.Patarin,CryptanalysisoftheMatsumotoandImaiPublicKeyschemeofEurocrypt’88,Crypto95.LinearizationEquationsAttack𝒂𝒊𝒋𝒙𝒊𝒚𝒋+𝒃𝒊𝒙𝒊+𝒄𝒋𝒚𝒋+𝒅=𝟎6k=Fq,K=FqnknknKKknknL1L2F(X)=X1+qknkn(f1(x1,…,xn),f2(x1,…,xn),…,fn(x1,…,xn))1idid代数攻击的起源2003年前后，NicolasT.Courtois等人将代数攻击思想用于分组密码和序列密码。代数攻击对基于LFSR的序列密码算法构成严重威胁。7非线性方程组求解算法简介8非线性方程组求解算法简介计算复杂度理论求解有限域上一组随机二次多变元多项式方程组是NP-hard问题.实际情形从具体的密码算法中得到的非线性方程组往往不符合随机的要求,这为代数攻击中解方程组提供了可能.9非线性方程组求解算法简介线性化方法Gröbner基方法SAT方法10线性化方法用新变元代替高次(2)单项式,使得原始的非线性方程组转化为线性方程组.再利用Gauss消元法求解关于新变元的线性方程组根据新变元的取值求解原始变元11线性化方法x1x2x4x1x3x5x0x2x6x2x3x7x0x3x8x0x1x9x4+x5+x0+x2=0x6+x4+x7+x1+x3+1=0x8+x7+x0+x1+x2=0x9+x8+x5+x2+x3+1=0x9+x6+x0+x3+1=0x4+x5+x0=0x6+x4+x7+x1=0x8+x7+x2=0x9+x8+x5+x1+x3+1=0x9+x6+x0+x2=0x1x2+x1x3+x0+x2=0x0x2+x1x2+x2x3+x1+x3+1=0x0x3+x2x3+x0+x1+x2=0x0x1+x0x3+x1x3+x2+x3+1=0x0x1+x0x2+x0+x3+1=0x1x2+x1x3+x0=0x0x2+x1x2+x2x3+x1=0x0x3+x2x3+x2=0x0x1+x0x3+x1x3+x1+x3+1=0x0x1+x0x2+x0+x2=0x0=0,x1=0,x2=0,x3=1,x4=0,x5=0,x6=0,x7=0,x8=0,x9=012线性化方法优点计算复杂度可估计：计算复杂度按高斯消元计算，大约𝒏𝒅𝝎,3.局限性对一个n变元的d次方程组来说,线性化后方程变元增至O(𝒏𝒅),因此对方程数量要求较高.13线性化方法Relinearization方法A.Kipnis,A.Shamir.CryptanalysisoftheHFEPublicKeyCryptosystem,Crypto'99.基本思想第一次线性化：xaxb=yab,xcxd=ycd,…因为(xaxb)(xcxd)(xaxc)(xbxd)(xaxd)(xbxc)所以yabycd=yacybd=yadybcyab=lab(z1,z2,…),ycd=lcd(z1,z2,…),…第二次线性化：zizj=vij,…•方程数量的增加大于变元数量的增加。•线性相关的方程。需要的方程个数大约为线性化方法所需方程个数的五分之一14(xaxb)(xcxd)(xexf)(xaxd)(xbxc)(xexf)线性化方法eXtendedLinearizations方法N.Courtois,A.Klimov,J.Patarin,andA.Shamir.Efficientalgorithmsforsolvingoverdefinedsystemsofmultivariatepolynomialequations,EUROCRYPT200015线性化方法eXtendedLinearizations方法设fi(x1,x2,,xn)0,i1,2,,m是二元域F2上的非线性方程组.16线性化方法eXtendedLinearizations方法参数：D乘单项式:𝒙𝒊𝒋𝒇𝒍𝒌𝒋=𝟏,k+deg(fl)D,l=1,2,…,m用线性化方法解新的方程组Free:线性独立方程数量,Freemin{R,T},R:方程总数T:方程的单项式个数FreeT时，XL算法可行17𝑛𝑖𝐷−deg⁡(𝑓𝑙)𝑖=1线性化方法18eXtendedLinearizations方法Free=min{T,R}ormin{T,R}−1ormin{T,R}−2n10101020202020m10161820406065Free11017417542084012601350Free/R1.0000.98860.88381.00001.00001.00000.9890Free/T0.62500.98860.99430.31090.62180.93620.9993D=3线性化方法19eXtendedLinearizations方法D345Free420401021699Free/R1.00000.95020.7301Free/T0.31090.64721.000n=20,m=20线性化方法20Relinearization方法和eXtendedLinearizations方法线性化方法的改进，减少了线性化方法所需方程数量方程数量与线性化的规模相当时，计算复杂度是多项式时间方程数量与方程规模相当的情形计算复杂度无法估计Gröbner基方法Gröbner基GröbnerBaseswereintroducedbyBrunoBuchbergerin1965.TheterminologyacknowledgetheinfluenceofWolfgangGröbneronBuchberger’swork.给定零维理想I,找K[x1,…,xn]/I在K上的一组基GröbnerBases,AComputationalApproachtoCommutativeAlgebra.GTM141.(Chapter5GröbnerBases)21Gröbner基方法多变元多项式环F2[x1,…,xn]项集：TT(x1,…,xn),T(f)x1,x1x2,x12x2x3f=x1+x1x2+x2x3x4,T(f)={x1,x1x2,x2x3x4}项序:定义在项集T上的大小关系字典序:x2x3x1次数字典序:x1x2x3…首项HT(f)22•线性序•对任意的XT(x1,…,xn),有1X;•对Y,X1,X2T(x1,…,xn),有X1X2YX1YX2.Gröbner基方法多项式约化（除法）PF2[x1,…,xn],f,gF2[x1,…,xn]f模P约化到g:fgfgmodId(P)若g模P不能再约化了，则g称为f模P的一个正规型f0fId(P)P23fg1p1g2p2gk=gpkPGröbner基方法什么是Gröbner基F2[x1,x2,...,xn]中理想的一组特殊的生成元I=Id(G),对任意的fI,存在gG满足HT(g)整除HT(f)给定项序，既约GröbnerBases唯一f模G的正规型唯一f0fId(G)G24Gröbner基方法Gröbner基算法Buchberger算法(Buchberger,1965)F4算法(Jean-CharlesFaugère,1999)F5算法(Jean-CharlesFaugère,2002)GVW(S.H.Gao,F.Volny,andM.S.Wang.,2010)25Gröbner基方法Gröbner基与解方程设fi(x1,x2,,xn)0,i1,2,,m是二元域F2上非线性方程组.在字典序下,计算由{f1,…,fm,x12x1,…,xn2xn}生成的理想I的既约Gröbner基G*={g1,g2,…,gk}.解方程组gi=0,i=1,…,k,即得原方程组的解.26Gröbner基方法Gröbner基与解方程设fi(x1,,xn)0,i1,2,,m是二元域F2上非线性方程组.在次数字典序下,计算由{f1,…,fm,x12x1,…,xn2xn}生成的理想I的既约Gröbner基G.利用Gröbner基的换序算法，计算在字典序下理想I的既约Gröbner基G*={g1,g2,…,gk}.解方程组gi=0,i=1,…,k,即得原方程组的解.27Gröbner基方法Gröbner基与解方程令Gi=G*F2[xi,…,xn],i=1,2,…,n,则依次解方程组Gn=0,Gn−1=0,…,G1=0可得方程组的全体解.28Gröbner基方法Gröbner基与解方程定理设fi(x1,,xn)0,i1,2,,m是二元域F2上非线性方程组,若该方程组在F2中有唯一一组解(x1,x2,,xn)(a1,a2,,an),则由{f1,…,fm,x12x1,…,xn2xn}生成的理想的既约Gröbner基为{x1a1,x2a2,,xnan}.29Gröbner基方法优点方程数量要求低局限性存储复杂度大计算复杂度无法估计30SAT方法BooleanSatisfiabilityProblem(SAT)布尔变量(Booleanvariable):取两个值True或False的变量布尔运算(Booleanoperations):and,or,not布尔公式(Booleanformula)：由,,,变量,括号构成的公式可满足(satisfiable)不可满足(unsatisfiable)SatisfiabilityProblem判断一个布尔公式是否可满足第一个NP-完全问题x1(x2x3)可满足的：x1=T,x2=T,x3=T.31SAT方法BooleanSatisfiabilityProblem(SAT)字(literal)：一个布尔变量或者一个布尔变量的取“非”子句(clause)：一些字的“或”合取范式