密码学课件 有限域上的分组密码

密码学导论IntroductiontoCryptology主讲教师：李卫海第4章有限域上的分组密码有限域上的分组密码有限域计算其它有限域上的分组密码高级加密标准AES有限域上的分组密码有限域计算其它有限域上的分组密码高级加密标准AES群、环、域的关系群：A1加法封闭；A2加法结合律；A3加法单位元；A4加法逆元交换群：A5加法交换律环：M1乘法封闭；M2乘法结合律；M3分配律交换环：M4乘法交换律整环：M5乘法单位元；M6无零因子域：M7乘法逆元群Group群G，记作{G,•},定义一个二元运算“•”的集合，G中每一个序偶(a,b)通过运算生成G中元素(a•b)，满足下列公理：(A1)封闭性Closure：如果a和b都属于G，则a•b也属于G(A2)结合律Associative：对G中的任意元素a，b，c，都有a•(b•c)=(a•b)•c成立(A3)单位元Identityelement：G中存在一个元素e，对于G中任意元素a，都有a•e=e•a=a(A4)逆元Inverseelement：对于G中任意元素a,G中都存在一个元素a-1，使得a•a-1=a-1•a=e减法：当群中的运算符是加法时，其单位元是0a的逆元是-a减法定义为：a–b=a+(-b)群Group有限群FiniteGroup和无限群InfiniteGroup：如果一个群的元素是有限的，则该群称为有限群，且群的阶等于群中元素的个数；否则称为无限群交换群（阿贝尔群）AbelianGroup：满足交换律的群(A5)交换律Commutative：对于G中任意的元素a,b，都有a•b=b•a成立循环群CyclicGroup:如果群中的每一个元素都是一个固定的元素a(a∈G)的幂ak(k为整数)，则称群G为循环群元素a生成了群G，或者说a是群G的生成元环Ring环R，记作{R,+,x}，定义二元运算加法“+”和乘法“×”的集合，R中任意元素a,b,c满足下列公理：(A1-A5),R关于加法是交换群，单位元是0，a的逆元是-a(M1)乘法封闭性：如果a和b都属于R，则ab也属于R(M2)乘法结合律：如果a,b,c都属于R，则a(bc)=(ab)c(M3)分配律：如果a,b,c都属于R，则a(b+c)=ab+ac或(a+b)c=ac+bc交换环CommutativeRing：满足下列条件的环(M4)乘法交换律：对R中任意元素a,b，都有ab=ba成立整环IntegralDomain：满足下列条件的交换环(M5)乘法单位元：在R中存在元素1，使得对于R中任意元素a，都有a1=1a成立(M6)无零因子：若元素a,b满足ab=0，则必有a=0或b=0域Field域F，记作{F,+,×}，定义为满足下列关系的整环：(M7)乘法逆元Multiplicativeinverse:对F中每个元素a（除0以外），存在元素a-1满足

aa-1=(a-1)a=1除法：对F中任意元素a和任意非零元素b，定义为a/b=a(b-1)密码学的运算多定义在有限域中整除、因子Factor,

Divisor如果a=mb,其中a,b,m为整数，则当b≠0时，称b能整除a，b是a的一个因子，或a除以b余数为0，记为b|a例：24的正因子有1,2,3,4,6,8,12和24。以下关系成立如果a|1,则a=±1如果a|b，且b|a,则a=±b任何b≠0能整除0如果b|g，且b|h，则对任何整数m和n，有b|(mg+nh)例：7|14and7|63，则7|(3×14+2×63)模运算：同余(congruence)给定整数a,b及n≠0,当且仅当a-b=kn时，a与b模n同余，记为a≡b(modn)例：17≡7(mod5)53≡11(mod7)若a是整数，n是正整数，定义a除以n的余数为a模n，记为amodn对于任意整数a，总可写出：a=

a/n

×n+(amodn)例：11mod7=4-11mod7=3a≡b(modn)当且仅当amodn=bmodn如果a≡0(modn)，则n|a同余的性质定理：如果n|(a-b)，则a≡b(modn)证明：如果n|(a-b)，则有(a-b)=kn,k为某些整数，所以a=b+kn故amodn=(b+kn)modn=bmodn反身性：a≡a(modn)对称性：a≡b(modn)，则

b≡a(modn)传递性：a≡b(modn)且b≡(cmodn)，则a≡c(modn)逆元加法逆元(-w)对每一个w∈Zn，存在一个z，使得w+z≡0modn，则z即为加法逆元-w乘法逆元(w-1)若p为素数，对每一个w∈Zp，w与p互素，存在一个z，使得w×z≡1modp。z即为乘法逆元w-1用w乘以Zp中的所有数模p，余数将以不同次序涵盖Zp中的所有数如果有两个余数相同，则将他们相减将与p是素数矛盾其中必有一个为1。这个数就是w的乘法逆元w-1模数不是素数时，某些但非全部元素存在唯一乘法逆元。如果gcd(a,n)=1,则能在Zn中找到b，使得a×b≡1(modn)。b即为乘法逆元a-1例，模8的运算加法表乘法表逆元表＋01234567001234567112345670223456701334567012445670123556701234667012345770123456

01234567000000000101234567202460246303614725404040404505274163606420642707654321w01234567-w07654321w-1-1-3-5-7模算术运算

剩余类集Residues定义比n小的非负整数集合为Zn：Zn

={0,1,…,(n-1)}模n的完全剩余类集(CompleteSetofResiduesmodn)：如果对每个整数a，在集合{r1,r2,…,rn}中恰有一个余数ri，使得amodn=ri，则称{r1,r2,…,rn}为模n的完全剩余类集，{0,1,…,n-1}形成模n的完全剩余类集，即Zn所有模n同余的数，构成一个剩余类。取每个剩余类中最小的非负元素构成的集合就是模n的完全剩余类集模n的缩剩余类集(ReducedsetofResiduesmodn)：完全剩余集的子集，其中的元素都和n互素（包括1）例：n=10，模n的完全剩余集是{0,1,2,…,9}模n的缩剩余集是{1,3,7,9}有限域GF(p)GaloisFields有限域在密码学中扮演重要角色有限域的元素个数是一个素数的幂pn,n为正整数，一般记为GF(pn)，即Galoisfields,模pn.关注两种特殊情形n=1时的有限域，即GF(p)p为2时的有限域，即GF(2n)最简单的有限域是GF(2)，代数运算简述如下：

+01

01 w-ww-1 001 000 00 110 101 111

加

乘

求逆伽罗瓦域GF(p)GF(p)的空间是模p的完全剩余类Zp：{0,1,…,p-1}模数p是素数，域中每个整数a∈[1,p-1]与p互素，都有唯一的乘法逆例，GF(7)上的运算加法表乘法表逆元表＋012345600123456112345602234560133456012445601235560123466012345

012345600000000101234562024613530362514404152635053164260654321w0123456-w0654321w-1-145236伽罗瓦域GF(2n)

普通多项式运算加法和减法规则：对应项系数的加或减乘法规则：各项交叉相乘再求和例：令f(x)=x3+x2+2和g(x)=x2

-x+1f(x)+g(x)=x3+2x2-x+3f(x)-g(x)=x3+x+1f(x)×g(x)=x5+3x2-2x+2f(x)/g(x)=x+2……x系数在Zp中的多项式运算系数进行模p运算模可以是任意素数当p=2时，所有系数为0或1。此时加法和减法等价例：在GF(2)上，令f(x)=x3+x2

+1和

g(x)=x2+x+1f(x)+g(x)=x3+xf(x)×g(x)=x5+x+1有限域GF(2n)上的多项式运算在GF(2)的基础上，将结果对一个n次素多项式m(x)取模最高次数小于n有助于二进制计算机实现2值运算，且长度有限非零元素有逆可以用扩展Euclidean算法求逆素多项式任何多项式可以写为：f(x)=q(x)g(x)+r(x)r(x)称为余式r(x)=f(x)modg(x)若不存在余式，则称g(x)整除f(x)，g(x)|f(x)若f(x)除了它本身和1外，不存在其它因式，则称f(x)是不可约多项式，或既约多项式、素多项式系数在GF(p)中，以素多项式取模的多项式构成一个域例：以(x3+x+1)为模的GF(22)上的运算+01xx+1x2x2+1x2+xx2+x+1001xx+1x2x2+1x2+xx2+x+1110x+1xx2+1x2x2+x+1x2+xxxx+101x2+xx2+x+1x2x2+1x+1x+1x10x2+x+1x2+xx2+1x2x2x2x2+1x2+xx2+x+101xx+1x2+1x2+1x2x2+x+1x2+x10x+1xx2+xx2+xx2+x+1x2x2+1xx+101x2+x+1x2+x+1x2+xx2+1x2x+1x10

01xx+1x2x2+1x2+xx2+x+1000000000101xx+1x2x2+1x2+xx2+x+1x0xx2x2+xx+11x2+x+1x2+1x+10x+1x2+xx2+1x2+x+1x21xx20x2x+1x2+x+1x2+xxx2+11x2+10x2+11x2xx2+x+1x+1x2+xx2+x0x2+xx2+x+11x2+1x+1xx2x2+x+10x2+x+1x2+1x1x2+xx2x+1计算上的考虑系数是0或1，用二进制表示较为方便加法即比特串的按位异或运算乘法即比特串的移位及异或运算多项式取模的运算：反复用既约多项式减掉最高次项例：在GF(23)中，(x2+1)可以表示为1012

，(x2+x+1)可以表示为1112加法：(x2+1)+(x2+x+1)=x；1012⊕1112=0102乘法：(x2+x+1)×(x+1)=x3+x2+x+1；1112×1012=((1112)<<2)⊕((1112)<<0)=110112

多项式取模：(x4+x3+x+1)mod(x3+x+1)=x2+x+1110112mod10112=1102101+111010111×10111111111011mod101111011011110计算上的考虑例：在GF(23)中计算d=a2,a=1012,p=10112a

a=1012×1012=101002⊕1012=100012d=a2modp=100012mod10112=1112例：在GF(23)中计算d=a

b,a=1112,b=1002,p=10112a

b=1112

1002=111002a

b模p：111002mod10112=0012即1112

1002mod10112=0012，在模10112时a与b互逆。101×10110110110001mod1011111111×10011100mod1011101010111欧几里德算法EuclideanAlgorithm两个正整数的最大公约数(GreatestCommonDivisor)：gcd(a,b)定理：对任何整数a和b，都有gcd(a,b)=gcd(amodb,b)证明：不妨设a>b，可以令a=kb+r，amodb=r若d是a、b的公因子，则d|kb，必然有d是r、b的公因子若d是b、r的公因子，显然d|a，即d也是a、b的公因子因此定理成立若a和b只有唯一的正公因子1，则称整数a和b是互素的，即gcd(a,b)=1例，用欧几里德算法求gcd(1970,1066)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)1970106690416294682616106420abamodb…d0扩展欧几里德算法,求d=gcd(a,b)，并解ax+by=dax1+by1(x1=1,y1=0)=aax2+by2(x2=0,y2=1)=ba(x1-qx2)+b(y1-qy2)=amodb=a-bq…=…ax+by=dax'+by'=0qxyd-104864-01345811-114062-2364625-71145-273876132-45382-911280例：a=4864，b=34584864×32+3458×(-45)=384864×(-91)+3458×128=0在GF(p)中求乘法逆元，y=b-1modp即求解px+by=1modpby1(y1=0)=P(modp)by2(y2=1)=b(modp)b(y1-qy2)=pmodb=p-bq(modp)…=…(modp)by=1(modp)qyd-01759-15503-3109516521-339413551例，求550在GF(1759)里的乘法逆元多项式的欧几里德算法求最大公因式c(x)=gcd(a(x),b(x))c(x)是能同时整除a(x)和b(x)的次数最高的多项式例：求gcd((x8+x4+x3+x+1),(x7+x+1))GF(2n)中求逆元的过程类似x8+x4+x3+x+1x7+x+1x4+x3+x2+1x10有限域上的分组密码有限域计算其它有限域上的分组密码高级加密标准AESAES的起源AES的起源DES不够安全3DES（或称T-DES）安全，但速度慢1997年9月，美国国家标准技术协会（NIST）公开征集新的密码方案1998年6月，15个候选算法通过第一轮评估1999年8月，5个候选算法通过第二轮评估2000年10月，Rijndael算法被选中，作为AES算法2001年11月，发布最终标准FIPSPUB197NIST对AES在以下方面的最终评估良好安全性：实际安全、密文随机性、数学合理性、公众评价、对所有已知的攻击免疫代价：在各种平台上代码紧凑、软件执行效率、硬件执行效率、有限存储空间环境算法及执行特性：密钥灵活、指令级并行操作、加密算法效率高于解密算法、其它多功能性和适应性AES主要参数AES的参数Rijndael允许分组长度为128位，192位或256位密钥长度128b(16B,4W)192b(24B,6W)256b(32B,8W)分组长度128b(16B,

4W)轮数101214每轮的密钥长度分组长度扩展密钥长度分组长度×(轮数+1)AES结构输入分组以正方形矩阵State描述密钥扩展为矩阵进行9/11/13轮迭代字节代换行移位列混淆轮密钥加最后一个不完整轮矩阵State转换为输出分组轮密钥加逆行移位逆字节代换轮密钥加逆列混淆第1轮逆行移位逆字节代换轮密钥加逆列混淆第9轮逆行移位逆字节代换轮密钥加第10轮轮密钥加行移位字节代换轮密钥加列混淆第1轮行移位字节代换轮密钥加列混淆第9轮行移位字节代换轮密钥加第10轮密钥扩展w[0,3]w[4,7]w[40,43]w[36,39]密文明文密钥密文明文AES结构：输入分组描述输入分组用以字节为单位的正方形矩阵State描述然后对State进行迭代运算最后将State转换为输出分组in0in4in8in12in1in5in9in13in2in6in10in14in3in7in11in15s0,0s0,1s0,2s0,3s1,0s1,1s1,2s1,3s2,0s2,1s2,2s2,3s3,0s3,1s3,2s3,3s0,0s0,1s0,2s0,3s1,0s1,1s1,2s1,3s2,0s2,1s2,2s2,3s3,0s3,1s3,2s3,3out0out4out8out12out1out5out9out13out2out6out10out14out3out7out11out15AES结构：单轮结构在算法的开始和结束都有轮密钥加阶段以不需要密钥的运算用于开始和结束不能增加安全性每轮迭代中轮密钥加实质上是一种Vernam密码，本身不难破译字节代换、行移位、列混淆三个阶段一起提供了混淆、扩散和非线性功能。这些阶段不涉及密钥，其本身并不提供安全性各阶段均可逆解密算法与加密算法并不一样，各阶段为逆操作（轮密钥加阶段算法相同）轮密钥加逆行移位逆字节代换轮密钥加逆列混淆第1轮逆行移位逆字节代换轮密钥加逆列混淆第9轮逆行移位逆字节代换轮密钥加第10轮轮密钥加行移位字节代换轮密钥加列混淆第1轮行移位字节代换轮密钥加列混淆第9轮行移位字节代换轮密钥加第10轮密钥扩展w[0,3]w[4,7]w[40,43]w[36,39]密文明文密钥密文明文AES结构：字节代换正向字节代换是简单查表操作S盒是一个16×16字节的矩阵，包含8bits值的256种可能的变换字节的高4位作为行值，低4位作为列值，取S盒中对应行列的元素输出例：(95)16被映射为S盒中第9行第5列的值AES结构：S盒构造S盒的构造：初始化S盒：x行y列的元素值为(xy)16每个字节映射为GF(28)中的逆，模(x8+x4+x3+x+1)(00)16映射为(00)16这保证逆操作可行(xy)16←→(x'y')16每个字节记为(b7,b6,b5,b4,b3,b2,b1,b0)，做如下代换：AES结构：逆S盒构造逆向字节代换使用逆S盒逆S盒构造:先做如下代换，再求其逆可以验证此逆代换是构造S盒的代换的逆AES结构：S盒评价评价：S盒被设计成能够防止各种已有的密码分析攻击输入位和输出位之间几乎没有相关性输出值不能利用一个简单数学函数变换输入值得到变换中常数的选择使得S盒中没有不动点〔S盒(a)=a〕，也没有反不动点〔S盒(a)=ā〕。这里ā指a的反。S盒是可逆的：逆S盒(S盒(a))=aS盒是不自逆的：S盒(a)≠逆S盒(a)AES结构：行移位正向行移位变换State的第一行不变，第二行循环左移一个字节，第三行循环左移两个字节，第四行循环左移三个字节逆向行移位变换将左移改为右移评价将某个字节从一列移到另一列中，确保某列中的4字节扩展到了4个不同的列AES结构：列混淆正向列混淆变换对每列独立进行操作变换中的乘法定义在GF(28)上的，模(11B)16；加法定义为异或逆向列混淆变换使用逆矩阵变换AES结构：列混淆的性能评价：变换矩阵的系数是基于在码字间有最大距离的线性编码正向变换的系数(01)16(02)16(03)16考虑到算法执行效率系数的乘法至多涉及一次移位、一次异或各项和需要三次异或、无需GF(28)中的模运算不考虑逆向变换的算法执行效率。加密被视为比解密重要在每列的所有字节中有良好的混淆性列混淆和行移位变换使得经过几轮迭代后，所有输出位均于所有输入位相关AES结构：轮密钥加正向轮密钥加与逆向轮密钥加过程相同以字节为单位，在GF(28)中的加法s0,0s0,1s0,2s0,3s1,0s1,1s1,2s1,3s2,0s2,1s2,2s2,3s3,0s3,1s3,2s3,3w0w1w2w3s'0,0s'0,1s'0,2s'0,3s'1,0s'1,1s'1,2s'1,3s'2,0s'2,1s'2,2s'2,3s'3,0s'3,1s'3,2s'3,3+=第1列四个比特第2列四个比特第3列四个比特第4列四个比特AES结构：AES单轮结构图AES结构：密钥扩展密钥描述：密钥用以字节为单位的矩阵描述，再扩展为一个以字为单位的密钥序列数组每次轮密钥加运算使用4个字k0k4k8k12k1k5k9k13k2k6k10k14k3k7k11k15w0w1w2…w42w43AES结构：密钥扩展密钥扩展（对128位密钥）输入密钥直接复制到扩展密钥数组的前四个字w[i]的值依赖于w[i-1]和w[i-4]g是一个复杂函数：字循环：四个字节循环左移一个字节字节代换：用S盒对每个字节进行代换与轮常量Rcon[j]异或AES结构：密钥扩展轮常量右边三个字节总为0：Rcon[j]=(RC[j],0,0,0)RC[1]=1RC[j]=2·RC[j-1]，乘法定义在域GF(28)上，模(11B)16评价：轮密钥扩展的方式描述较为简单，与加密算法有相似之处使用轮常量排除可能的对称性将密钥的差异性扩散到轮密钥中：密钥的每个位能影响到扩展轮密钥的所有位足够的非线性：轮密钥的差异与密钥的差异关系复杂能够在各种处理器上有效地执行知道部分不连续的密钥或轮密钥，不能计算出轮密钥的其他位是一个可逆变换：知道扩展密钥中任何连续的4个字，能够重建整个扩展密钥j12345678910RC[j]01020408102040801B36AES解密解密过程中各变换的顺序与加密中变换的顺序不同解密的一个等效版本与加密算法有相同的结构，变换顺序相同（但用逆向变换取代正向变换）轮密钥加逆行移位逆字节代换轮密钥加逆列混淆第1轮逆行移位逆字节代换轮密钥加逆列混淆第9轮逆行移位逆字节代换轮密钥加第10轮轮密钥加行移位字节代换轮密钥加列混淆第1轮行移位字节代换轮密钥加列混淆第9轮行移位字节代换轮密钥加第10轮密钥扩展w[0,3]w[4,7]w[40,43]w[36,39]密文明文密钥密文明文轮密钥加逆行移位逆字节代换轮密钥加逆列混淆第1轮逆行移位逆字节代换轮密钥加逆列混淆第9轮逆行移位逆字节代换轮密钥加第10轮密钥扩展w[0,3]w[4,7]w[40,43]w[36,39]密文密钥明文逆列混淆逆列混淆AES解密逆向行移位和逆向字节代换可交换，不影响结果轮密钥加和逆向列混淆可交换，但要对密钥扩展进行修改AES的快速实现

行移位字节代换轮密钥加列混淆s0,0s0,1s0,2s0,3s1,0s1,1s1,2s1,3s2,0s2,1s2,2s2,3s3,0s3,1s3,2s3,3s'0,0s'0,1s'0,2s'0,3s'1,0s'1,1s'1,2s