分组密码的主要攻击方法

信源信源编码加密信道编码扩频调制解调解扩信道译码解密信源译码信宿数据压缩密码纠错编码扩频通信信道研究背景（通信系统模型）研究背景（分组密码）4欧洲NESSIE计划推出的分组密码算法：MISTY1、Camellia、SHACAL2、Rijndael美国AES计划推出的分组密码算法：MARS、RC6、Rijndael、Serpent、Twofish其他计划推出的分组密码算法：ARIA、SMS4、FOX、CLEFIA等等研究背景（分组密码）4分组密码的主要攻击方法：差分密码攻击及其变种-差分均匀度线性密码攻击及其变种-非线性度积分攻击-积分分支数代数攻击-代数次数中间相遇攻击相关密钥攻击研究背景（序列密码）4欧洲Estream计划推出的序列密码算法：Grainv1、Trivium、Mickeyv2（面向硬件）HC、Rabbit、Salsa20、Sosemanuk（面向软件）欧洲NESSIE计划推出的序列密码算法：SNOW3G（3GPP数据加密标准）其他重要的序列密码算法：A5\1GSM数据加密算法RC4网络数据库加密算法E0蓝牙数据加密算法ZUC3GPP序列标准算法研究背景（序列密码）4序列密码的主要攻击方法：经典序列密码的攻击方法：线性逼近攻击-非线性度相关攻击-相关免疫度代数攻击-代数免疫度现代序列密码的攻击方法：选取初始值攻击、猜测决定攻击立方攻击、相关密钥攻击研究背景（Hash函数）4美国SHA3计划推出的Hash函数算法：JH、Grostl、Blake、Keccak、Skein已有的Hash函数标准算法：MD5、SHA1、SHA2我国Hash函数标准算法：SM3算法（2010年12月17日公布）研究背景（Hash函数）4Hash函数的主要攻击方法：差分密码分析比特追踪法反弹攻击法第1章布尔函数与向量值函数§1.1布尔函数及其表示定义1从到的映射称为n元布尔函数.◆记Bn为全体n元布尔函数的集合，则Bn关于布尔函数的加法与乘法构成一个环，称为布尔函数环.◆2212222112,[,,](,,),/nnnnBFxxxxxxxxx◆（当n比较大时，布尔函数的数量巨大）.2||2nnB22:nfFF2nF2F第1章布尔函数与向量值函数☆布尔函数的常用表示方法：（1）真值表,0,0,0(0,),(0,),,1,(1,,1,1)()fff（2）小项表示2121211(,,)(,,)(,,1)1()innnanFfxxfaaxxaxaa1221122(,,,)niaaaannFaxfaaxx其中.1iaiiixxa§1.1布尔函数及其表示第1章布尔函数与向量值函数（3）代数正规型10112(,,),niijnniiijijfxxaaxaxxx1112,,1,2,,121dddiiiinniiinaxxxxxa或12()(),(,,)(),iiIIInIiIiIIPNPNIfxxxxxxaax这里，P(N)表示N的幂集.当为空集时，规定{1,2},,nN§1.1布尔函数及其表示I0,1IIaax第1章布尔函数与向量值函数☆布尔函数的基本概念●重量2(){|()1}||nwxfFtfx●次数代数正规型中系数非零项所含有最多变元的个数.即degmax{||0,()}IfIaIPN●仿射函数集1200112{(,,),,,,}nnininiAxfxaFxaxaaa●线性函数集2112{(,,),}nniiiniLxafxxxFa§1.1布尔函数及其表示第1章布尔函数与向量值函数命题1设布尔函数f的代数正规型为122()(,,),,InIIPNIfxxaxxFa则（1）对任意122(,,,)nnFxxxxSupp()12(,,,)IxnIfxxax其中Supp(){11}|iinxx（2）对任意()IPN2,supp()().nFxIxIafx§1.1布尔函数及其表示第1章布尔函数与向量值函数定义2布尔函数f的循环Walsh谱是定义在F2n上的一个实值函数，即2)2(()(1),nfxxnfFwxWwFw其中为点积.1122nnxwxwxwxw（1）循环Walsh谱的逆变换为2()1(1)()(1)2nxwfxfnF§1.2布尔函数的Walsh变换第1章布尔函数与向量值函数（3）线性Walsh谱的逆变换如下：21()()(1)2nwwxfnFfxSw§1.2布尔函数的Walsh变换（2）称为线性Walsh谱.2()()(1)nxxwfFSwfx第1章布尔函数与向量值函数☆Walsh谱的基本性质（1）循环Walsh谱与线性Walsh谱具有如下关系2()()22(00)ffnfS（2），特别()22()nf2nFw(0)22()nfWwtf（3）(Parseval恒等式）222()2nnfF§1.2布尔函数的Walsh变换第1章布尔函数与向量值函数☆布尔函数的安全性指标●平衡性f为平衡函数1()2(0)0fnwtfw●代数次数degmax{||0,()}IfIaIPN§1.3布尔函数的安全性指标注：元平衡函数的代数次数至多为。事实上，重量为偶数的元布尔函数的代数次数至多为。1nnn1n第1章布尔函数与向量值函数●差分均匀度2202maxmax|{()()}|nnfFFxfxfxF（1）（2）若，则称布尔函数f为完全非线性函数.12nf122nnf§1.3布尔函数的安全性指标（3）f为完全非线性函数当且仅当对任意均为平衡函数。()()()fDxfxafx0a第1章布尔函数与向量值函数●非线性度()min(,)min()nnAAllNLfdflwtfl（1）（2）（3）若，则称f为Bent函数.211()2max|()|2nnfFwNLfWw1212()2nnNLf1212()2nnNLf§1.3布尔函数的安全性指标(4)为Bent函数当且仅当f22()2,nnfWaaF第1章布尔函数与向量值函数●相关免疫阶与弹性阶设z=f(x1,x2,…,xn)是一个n元布尔函数，其中x1,x2,…,xn是F2上独立分布的随机变量，如果z与x1,x2,…,xn中任意m个变量xi1,xi2,…,xim统计独立，则称f为m阶相关免疫函数.（1）Xiao-Massey定理设f(x)为n元布尔函数，1≤t≤n，如果对，均有，则f为t阶相关免疫函数.2,nwF()1wtwt()0fWw（2）注意到平衡函数是在w=0处Walsh谱取值为0的函数，称平衡的相关免疫函数为弹性函数.§1.3布尔函数的安全性指标第1章布尔函数与向量值函数●代数免疫度其中()mindeg0()(1){}ggAnnfAAIfnnf(){|,0}nAnnfggBfg（1）为中一个主理想，（2）（3）若，则称f为代数免疫度最优的函数.()AnnfnB()(1)(1)nAnnfffB122()fnnAI2()AIfn§1.3布尔函数的安全性指标第1章布尔函数与向量值函数定义3设n和m为两个正整数，从F2n到F2m的映射称为（n，m）函数，有时也称为向量值函数，多输出布尔函数或向量布尔函数.☆向量值函数的表示方法：（1）分量函数表示法：其中为n元布尔函数.122()((),(,),()),nmfFxfxfxxxF()ifx（2）代数正规型表示法：其中P(N)为N的幂集，.2mIaF()()()(),IIiIIPNiIIPNFxaxax§1.4向量值函数及其表示第1章布尔函数与向量值函数☆向量值函数的Walsh谱2)22((,)(1),(,)nvFxuxxnmFFWuvFFuv（1）向量值函数F在处的Walsh变换就是布尔函数在u处的Walsh变换.22(,)nmFuvFvF（2）称为F的Walsh谱.22(){(,)(,)}nmFWFWuvuvFF§1.4向量值函数及其表示（3）称为F的扩展Walsh谱.2~2(){(,)(,)}nmFFWFWuvuvF第1章布尔函数与向量值函数☆向量值函数的安全性指标●平衡性F为平衡函数对对为平衡布尔函数.12,|()|2mnmFFbb2,0,mvvFvF●代数次数与一致代数次数=分量函数代数次数的最大值degmax{||(0,0,,0),()}IFIaIPN2Degmin{deg()0}mFvFvF显然DegdegFF§1.5向量值函数的安全性指标第1章布尔函数与向量值函数●非线性度22021()min{()0}1maxmax|(,)|2mnnumFvFFvNLFNLFvFWuv（1）112()2nnNLF（2）若，则称F为向量Bent函数.112()2nnNLF（3）F为向量Bent函数对为Bent函数.2,0,mvvFvF§1.5向量值函数的安全性指标（4）如果F为向量Bent函数，则。2,2nnm第1章布尔函数与向量值函数●差分均匀度2202maxmax|{()()}|mnnFaFbFFaxFxFxb（1）（2）如果F为仿射函数，则2nF22nmnF（3）如果，则称向量值函数F为完全非线性函数.2nmF§1.5向量值函数的安全性指标（4）是完全非线性函数当且仅当对任意非零，为平衡函数，当且仅当为Bent函数。22:nmFFFa()()FxaFxF(,)nm第1章布尔函数与向量值函数●相关免疫阶和弹性F为t阶相关免疫函数对为t阶相关免疫函数.F为t阶弹性函数对为t阶弹性函数.2,0,mvvFvF2,0,mvvFvF●代数免疫度基本代数免疫度，图形代数免疫度，组合代数免疫度，设2,nSF12(){,|0}()min{0}deg()(()min{())|}nmSNSgggAISgAIFaaBgNSAIFF—基本代数免疫度§1.5向量值函数的安全性指标第1章布尔函数与向量值函数☆向量值函数的迹表示22:nmFFF设，这里，则F可以看作从到自身的函数，于是F可以有如下单变元表示：|mn2nF221()()(1())nnaFFxFaxa将上式展开合并得到：2120,()nnjjjjFxFx§1.6向量值函数的迹表示第1章布尔函数与向量值函数从而可以得到F(x)的迹表示：2101()2()()njnmmnjnmjjFtrxxx其中为使得成立的最小正整数.为分圆陪集首的集合.02122,,,jnnmmjjFnFmod212jmnnjj()mm特别，当m=1时，布尔函数有如下迹表示其中.121101)2((())njnnjjjnxFxtrx02122,,nnjjFF§1.6向量值函数的迹表示