计算机网络安全与管理：第四讲

网络安全与管理

第四讲本讲内容块加密模式补充数论基础公钥密码学应用方式对于块定长，密钥长度定长的快加密算法实际应用当中常常需要加密任意长的数据ANSIX3.106-1983中定义了四种应用方式后来发展为5类应用于像AES&DES的算法具有块模式与流模式电子密码本

ElectronicCodebookBook(ECB)明文被分块独立加密，明文块与密文块具有一一对应的关系。就像密码本（记得上节课提到的特大字符的概念吗）Ci=DESK1(Pi)用于单一值的安全传输ECB的优缺点明文块的重复会体现在密文当中，当报文量很小时没什么，但当报文量大的时候，特别是报文具备结构性特征：比如总是以某些事先规定好的域开始。那么分析者有可能获得很多可供分析的明文-密文对。结合64bit的划分，给篡改，重排带来隐患应用范围：小规模数据传输（几块）密码分组链接方式

CipherBlockChaining(CBC)消息经过分块通过加密操作将分块链接起来通过将前一个密文块与当前明文块连接（异或）因而得名步骤开始时利用一个初始值Ci=DESK1(PiXORCi-1)C-1=IV

用于：大量数据的加密，鉴别（http，email,ftp)CipherBlockChaining(CBC)消息填充

MessagePadding消息最后可能需要处理一个小分组，这是需要进行消息填充填充方法可以是填入空值，也可以是填入填充值。Eg：[b1b2b300005]就是说8个字节前面三个是消息，后面五个是填充这样的填充有可能需要一个完整的块某些更加深奥的方法可能避免该块CBC的优缺点每一块都依赖于其前面所有的块对一块的改变可影响其后所有初始向量IV需要双方知道若明文传输，攻击者有可能篡改用固定文字（EFTPOS）先用ECB加密传。密码反馈模式

CipherFeedBack(CFB)消息被作为一个数据流对待添加到加密器的后端结果被反馈在后面的过程中（由此得名）标准允许任意长度的比特数。CFB-1,CFB-8,CFB-64,CFB-128etcCi=PiXORDESK1(Ci-1)C-1=IV

用于：流数据加密，鉴别CFBCFB优缺点适应于数据一比特或字节到达最常见的流模式每过n比特需要等待块加密加密过程应用于两端错误影响其后多个块输出反馈模式

OutputFeedBack(OFB)消息被作为数据流对待加密结果被加到消息上输出的是接下来的反馈反馈独立于消息Ci=PiXOROi

Oi=DESK1(Oi-1)O-1=IV用于噪声信道优缺点比特错误不会传播易受报文篡改攻击双方应保持同步目前用的就是64bit与128bit的Counter(CTR)一个新的方式与OFT相似但是加密的是对应值（countervalue）而不是反馈值每个明文块都要有不同的密钥与对应值Ci=PiXOROi

Oi=DESK1(i)用于高速网络加密传播优缺点高效可并行可预处理爆发性高速连接随机存取加密块可证安全需保证密钥与对应值不复用流加密将报文作为数据流处理有一个伪随机密钥流通过XOR操作与原文按位复合随机的密钥流完全破坏了报文的统计特性：Ci=MiXORStreamKeyi

不可重用StreamCipherStructure特点设计准则应该满足：长时期的不重复较强的统计随机性依赖于足够大的密钥较大的线性复杂度设计恰当的话能达到不亚于块加密的效果简便高速RC4RonRivest设计，简单高效可变密钥长度，面向字节的广泛应用（ssl，wep）密钥构成对8比特数据的置换每次一个字节将报文进行置换乱排方案

开始由一个数组S：0，。。。，255利用密钥进行混洗S构成了初始状态fori=0to255doS[i]=iT[i]=K[imodkeylen])j=0fori=0to255doj=(j+S[i]+T[i])(mod256)swap(S[i],S[j])RC4加密加密过程继续混洗数组通过混洗，置换等操作取出子密钥按字节加密i=j=0foreachmessagebyteMii=(i+1)(mod256)j=(j+S[i])(mod256)swap(S[i],S[j])t=(S[i]+S[j])(mod256)Ci=MiXORS[t]安全性对已知攻击方式抵御较好很好的非线性不可重用密钥WEP的应用问题群一个元素的集合对于定义的运算封闭遵从结合律：(a.b).c=a.(b.c)

由单位元e：e.a=a.e=a

有逆元：a-1: a.a-1=e如果还遵从交换律：a.b=b.a

则我们称该群为阿贝尔群（交换群）abeliangroup循环群定义幂运算为群上运算的重复叠加例：a3=a.a.a且有单位元e=a0我们说一个群是循环的就是指对该群中的任意元素均可表示为某一固定元素的幂ieb=

ak

对某个a

与与任意一个b在群中。其中a称为该群的生成元环集合上定义了两种操作（乘和加）对于加法运算是一个阿贝尔群对于乘法运算有是封闭的满足结合律具有对加运算符合分配率：a(b+c)=ab+ac若对乘法具有可交换性则称为交换环若对乘法运算有单位元但无零因子，则称为整环域域作为定义了两中运算的集合具有对于加法是阿贝尔群对于乘法是阿贝尔群（忽略0）是一个环模运算定义“amodn”表示用n去除a得到的余数用“a=bmodn”表示a与b模n具有相同的余数对于一个数a通常可以表示为a=qn+r称r为余数（余数通常取最小的正数）模运算的性质模运算我们在整数群上定义模运算

Zn={0,1,…,n-1}构成了一个加法交换群具有乘法单位元具有下面的性质：if(a+b)=(a+c)modn thenb=cmodnbutif(a.b)=(a.c)modn thenb=cmodn当且仅当a与n互质例如：出现这种情况的原因是当有公因数时不会产生完整的余数集合最大公约数gcd该问题是数论中的一个普便问题GCD(a,b)表示能同时整除a与b的数中最大的一个当除1外不存在其它公因式时称作互质EuclideanAlgorithm该算法是一个很有效的计算最大公约数的算法利用到了GCD(a,b)=GCD(b,amodb)

EUCLID(a,b)1.A=a;B=b2.ifB=0returnA=gcd(a,b)3.R=AmodB4.A=B5.B=R6.goto2

例1970=1x1066+904 gcd(1066,904)1066=1x904+162 gcd(904,162)904=5x162+94 gcd(162,94)162=1x94+68 gcd(94,68)94=1x68+26 gcd(68,26)68=2x26+16 gcd(26,16)26=1x16+10 gcd(16,10)16=1x10+6 gcd(10,6)10=1x6+4 gcd(6,4)6=1x4+2 gcd(4,2)4=2x2+0 gcd(2,0)练习：gcd（2152，764）迦罗华域（有限域）

GaloisFields有限域理论在密码学中具有重要作用元素数为某一个素数的n次方这样的域被称为有限域（迦罗华域）记为GF(pn)经常用到的有：GF(p)GF(2n)GaloisFieldsGF(p)GF(p)是{0,1,…,p-1}的集合，其上定义了模p的算术运算构成了一个有限域因为乘法运算有逆元其上可以进行加减乘除运算GF(7)Example012345600000000101234562024613530362514404152635053164260654321FindingInversesEXTENDEDEUCLID(m,b)1. (A1,A2,A3)=(1,0,m); (B1,B2,B3)=(0,1,b)2.ifB3=0 returnA3=gcd(m,b);noinverse3.ifB3=1 returnB3=gcd(m,b);B2=b–1modm4.Q=A3divB35.(T1,T2,T3)=(A1–QB1,A2–QB2,A3–QB3)6.(A1,A2,A3)=(B1,B2,B3)7.(B1,B2,B3)=(T1,T2,T3)8.goto2练习：550在1769上的逆Inverseof550inGF(1759)QA1A2A3B1B2B3—101759015503015501–310951–3109–516521–5165106–33941106–3394–1113551多项式算数可以使用多项式运算

f(x)=anxn+an-1xn-1+…+a1x+a0=∑aixinb.并不关心x的值x作为不确定的值可以有若干可变的选择原始多项式运算modp多项式运算modp与modm(x)多项式运算原始多项式算数可以有加，减，乘eg取f(x)=x3+x2+2g(x)=x2–x+1f(x)+g(x)=x3+2x2–x+3f(x)–g(x)=x3+x+1f(x)xg(x)=x5+3x2–2x+2模系数的多项式运算在计算系数的时候模某个值构成一个多项式环可以模任意的素数更为关心的是mod2的运算ie所有的系数为0或1eg.letf(x)=x3+x2andg(x)=x2+x+1 f(x)+g(x)=x3+x+1 f(x)xg(x)=x5+x2多项式除法可以把任意多项式写成如下形式:f(x)=q(x)g(x)+r(x)可以把r(x)作为一个余项r(x)=f(x)modg(x)如果没有余项说g(x)整除f(x)如果g(x)没有除了1和它自身以外的因子则称其为不可归约多项式或（素）多项式算数模和不可约多项式构成了一个域多项式最大公约数可以找到多项式的最大公约数c(x)=GCD(a(x),b(x))如果c(x)isthepolyofgreatestdegreewhichdividesbotha(x),b(x)可以通过欧几里得算法求出: EUCLID[a(x),b(x)]

1.A(x)=a(x);B(x)=b(x) 2.ifB(x)=0returnA(x)=gcd[a(x),b(x)] 3.R(x)=A(x)modB(x) 4.A(x)¨B(x) 5.B(x)¨R(x) 6.goto2模多项式算数可以在域GF(2n)中运算多项式系数都模2次数小于n因此需要利用一个次数为n的不可归约多项式为模进行简化(仅对乘运算)构成一个有限域总能找到相应的逆元可以利用扩展的欧几里得求逆算法寻找ExampleGF(23)计算的考量因为系数是0或者1,可以把任意的比特串转化为多项式形式加法成为这样比特串的XOR运算乘法是shift&XOR模运算通过将最高次幂替换为不可归约多项式的余项获得(alsoshift&XOR)ComputationalExampleinGF(23)have(x2+1)is1012&(x2+x+1)is1112soadditionis(x2+1)+(x2+x+1)=x101XOR111=0102andmultiplicationis(x+1).(x2+1)=x.(x2+1)+1.(x2+1) =x3+x+x2+1=x3+x2+x+1011.101=(101)<<1XOR(101)<<0= 1010XOR101=11112

polynomialmoduloreduction(getq(x)&r(x))is(x3+x2+x+1)mod(x3+x+1)=1.(x3+x+1)+(x2)=x21111mod1011=1111XOR1011=01002UsingaGeneratorequivalentdefinitionofafinitefieldageneratorgisanelementwhosepowersgenerateallnon-zeroelementsinFhave0,g0,g1,…,gq-2cancreategeneratorfromrootoftheirreduciblepolynomialthenimplementmultiplicationbyaddingexponentsofgeneratorAES起源很明显DES需要被改进具有理论的攻击方式加以破解穷举密钥搜索攻击示范可以使用Triple-DES–但是速度较慢而且分块较小USNIST1997提出了对加密器的征求98年六月挑选了15个算法99年8月进入最后候选2000年10月Rijndael获选为AES200110月发布为FIPS（theFederalInformationProcessingStandards,(美国)联邦信息处理标准）PUB197AES需求对称块加密128-bit数据,128/192/256-bit密钥相比于Triple-DES更加快速与安全实际应用20-30年(+实际应用)提供了完整的规范与设计细节

同时具有C&Java实现NIST已经解密了所有提交的和非机密的分析AES评估标准初始标准:安全性

–实际密码分析的的效果成本

–依据计算效率算法与实现的性能最终标准一般安全性软硬件实现对于实施的攻击灵活性

(inen/decrypt,keying,otherfactors)AESShortlist经过测试与评估,99年8月提出的shortlist:MARS(IBM)-complex,fast,highsecuritymarginRC6(USA)-v.simple,v.fast,lowsecuritymarginRijndael(Belgium)-clean,fast,goodsecuritymarginSerpent(Euro)-slow,clean,v.highsecuritymarginTwofish(USA)-complex,v.fast,highsecuritymargin然后对其进行更进一步的analysis&comment在算法中进行对比复杂论变换与简单变换现有加密器与新标准TheAES加密器-Rijndael由比利时Rijmen-Daemen设计有128/192/256bit密钥,128bit数据一个胜于feistel加密器的迭代把数据作为4字节4列的块进行处理在每一轮对整个数据块进行操作设计以达到:抵抗已知攻击在许多CPUs上的速度与代码的紧致设计的简明Rijndael4列4个字节的数据块作为statekey被扩展为字符数组在9/11/13轮中state做下面变化:逐字节替代(1S-box用在每一个字节)行移位(permutebytesbetweengroups/columns)列混淆(subsusingmatrixmultipyofgroups)加轮密钥(将轮密钥与stateXOR)可以看做交替的使用轮密钥XOR与对数据字节进行扰乱的操作XORkey需要初始化操作&最后一轮只有三步变化可以采用高速的查表操作实现RijndaelByteSubstitution对每个字节进行简单的替代操作使用一个16x16字节的表，其中包含了256个8bit值的置换每个state的字节通过查表左4bits的行号与右4bit的列号替代eg.byte{95}被第

9行第

5列的{2A}替代S-box的构造利用了

GF(28)上值的变换被设计来抵抗已知的攻击ByteSubstitution行移位

对行进行循环移位操作1strow不变2ndrow左移一个字节3rdrow左移两个字节4throw左移三个字节解密逆操作使用右移相应字节的方式实现由于

state是按照列进行操作的,这一步在列之间进行了字节置换操作ShiftRows列混洗每一列均单独处理each每个字节均由一个与其同列的4个字节相关值替代使用GF(28)上的矩阵乘运算使用的“素”多项式m(x)=x8+x4+x3+x+1MixColumnsMixColumns可以把每一列表示为4个等式以获得每一列的新的字节解密需要使用逆矩阵使用了大系数,所以有一点难有另一种描述方式

每一列是一个4次多项式使用GF(28)上的系数多项式乘的模为(x4+1)加轮密钥XORstate使用

128-bits的轮密钥再一次以列为单位操作(通过一系列以字节