数论基础及对称加密算法

关于数论基础及对称加密算法12

数论基础第2页,共33页，2024年2月25日，星期天3加密系统中常用数论知识模q运算定义：给定任一正整数q和任一整数a，如果用a除以q，得到商s和余数r，则有a=sq+r，记r≡amodq;运算操作：加法：[(amodq)+(bmodq)]=(a+b)modq乘法：[(amodq)×(bmodq)]=(a×b)modq第3页,共33页，2024年2月25日，星期天4加密系统中常用数论知识模q运算运算性质：Zn定义为集合{0,1,……,q-1}，也称为模q的剩余类集合，以下为Zn上的模运算的性质；交换律：(a+b)modq=(b+a)modq(a×b)modq=(b×a)modq结合律：[(a+b)+c]modq=[a+(b+c)]modq[(a×b)×c]modq=[a×(b×c)]modq分配律：[a×(b+c)]modq=[a×b+a×c]modq恒等律：(0+a)modq=amodq(1×a)modq=amodq加法逆元：若存在a,b∈Zn，使得(a＋b)modq=0，则b是a模q的加法逆元。乘法逆元：若存在a,b∈Zn，使得ab=1modq，则b是a模q的乘法逆元。第4页,共33页，2024年2月25日，星期天5加密系统中常用数论知识模q运算求模逆运算:(辗转相除法)定理：设r1=b1umodq，r2=b2umodq，r1=mr2+r3，则r3=(b1-mb2)umodq。求逆元：u,q已知，求x，(0<x<q)，使得ux=1modq解：令r1=q，r2=u，则r1=q≡0×umodq，r2=u≡1×umodq

即有:b1=0，b2=1

令r1=m1r2+r3，0≤r3<r2，得到r3≡(b1-m1b2)umodq，记b3=b1-mb2，则有r2≡b2umodq，r3≡b3umodq。令r2=m2r3+r4，0≤r4<r3，得到r4≡(b2-m2b3)umodq，记b4=b2-mb3，则有r4≡b4umodq。继续下去，总之有：

r1≡b1umodq，r2≡b2umodq，r1=m1r2+r3，0≤r3<r2r2≡b2umodq，r3≡b3umodq，r2=m2r3+r4，0≤r4<r3……rk-1≡bk-1umodq，rk≡bkumodq，rk-1=mk-1rk+rk+1，0≤rk+1<rk……由于r2>r3>……>rk>rk+1≥0，以上操作必终止于有限步，不妨设rk+1=0，那么必有1=rk=(rk,rk-1)=……=(r3,r2)=(r2,r1)=(u,q)利用性质：若r是a÷b的余数,则gcd(a,b)=gcd(b,r)所以rk=bkumodq，得bku≡1modq，于是u-1≡bkmodq第5页,共33页，2024年2月25日，星期天6加密系统中常用数论知识群群是一种代数结构，由一个集合以及一个二元运算所组成。群是一个集合G，连同一个运算"·"，它结合了任何两个元素a

和b

而形成另一个元素指示，记为a·b。符号"·"是对具体给出的运算，比如上面加法的一般的占位符。要具备成为群的资格，这个集合和运算(G,·)必须满足叫做群公理的四个要求:1.闭合。对于所有G

中a,b，运算a·b

的结果也在G

中。2.结合律。对于所有G

中的a,b

和c，等式(a·b)·c=a·(b·c)成立。3.单位元。存在G

中的一个元素e，使得对于所有G

中的元素a，等式e·a=a·e=a

成立。4.逆元。对于每个G

中的a，存在G

中的一个元素b

使得a·b=b·a=e，这里的e

是单位元。使等式a·b=b·a

总是成立的群叫做阿贝尔群（以尼尔斯·阿贝尔命名）。例子：整数配备上加法运算就形成一个群。第6页,共33页，2024年2月25日，星期天7加密系统中常用数论知识环集合R和定义于其上的二元运算+和·，(R,+,·)构成一个环，若它们满足：(R,+)形成一个交换群，其幺元称为零元素，记作‘0’。即：(a+b)=(b+a)(a+b)+c=a+(b+c)0+a=a+0=a∀a∃(−a)满足a+−a=−a+a=0(R,·)形成一个半群，即：(a·b)·c=a·(b·c)乘法关于加法满足分配律：a·(b+c)=(a·b)+(a·c)(a+b)·c=(a·c)+(b·c)其中，乘法运算符·常被省略，所以a·b可简写为ab。此外，乘法是比加法优先的运算，所以a+bc其实是a+(b·c)。交换环：若环R中，(R,·)还满足交换律，从而构成交换半群，即：∀a，b∈R，有ab=ba，则R称为交换环。第7页,共33页，2024年2月25日，星期天8加密系统中常用数论知识域：是一种可进行加、减、乘和除（除了除以零之外）运算的代数结构，是数域以及四则运算的推广；域分为两种：无限域，元素个数无限，特征为0；有限域，元素个数有限，特征为p；特征：假设p是最小的正整数，使得p个1相加等于0，那么p就称为域的特征；有限域元素个数为q=pn；有限域GF(q)同构于GF(p)[x]/f(x)，其中f(x)为GF(p)上的不可约多项式；多项式在GF(p)上不可约：有限域GF(p)的任一元素都不是多项式方程的解。域无限域有限域特征0特征p,含有q=pn个元素GF(q)同构于GF(p)[x]/f(x)其中f(x)为GF(p)上不可约多项式第8页,共33页，2024年2月25日，星期天9加密系统中常用数论知识欧拉定理若m,a为正整数，且m,a互素，(gcd(a,m)=1)，则aφ(m)≡1modm，其中φ(m)为欧拉函数，modm为同余关系。在数论中，对正整数n，欧拉函数φ(n)是小于或等于n的正整数中与n互质的数的数目。此函数以其首名研究者欧拉命名，它又称为φ函数、欧拉商数等。例如φ(8)=4，因为1,3,5,7均和8互质。这个定理可以用来简化幂的模运算。比如计算7222的个位数，实际是求7222被10除的余数。7和10互素，且φ(10)=4，由欧拉定理知74≡1(mod10)，所以：7222=74×55+2=(74)55×72≡155×72≡49≡9(mod10)第9页,共33页，2024年2月25日，星期天10加密系统中常用数论知识费马定理费马小定理是数论中的一个定理：假如a是一个整数，p是一个素数，那么：

ap≡a(modp)如果a不是p的倍数，这个定理也可以写成：

ap-1≡1(modp)费马定理是欧拉定理的一种特殊情况。第10页,共33页，2024年2月25日，星期天11复杂性理论简介算法复杂性时间复杂性T(n)：以某特定的基本步骤为单元，完成计算过程所需的总单元数称为算法的时间复杂性，或时间复杂度，n是输入的规模和尺寸；时间复杂度：多项式时间复杂度和指数时间复杂度；空间复杂性S(n)：以某特定的基本存储空间为单元，完成计算过程所用的存储单元数，称为算法的空间复杂性或空间复杂度，n是输入的规模和尺寸。第11页,共33页，2024年2月25日，星期天12复杂性理论简介问题复杂性图灵机：一种具有无限读写能力的有限状态机，是一种具有无限读写能力的有限状态机，有确定型和非确定型的两种。P类：确定性多项式时间可解类。在确定型图灵机上多项式时间可解的问题，为P问题，也就是易处理问题。NP类：不确定性多项式可解类，在非确定型图灵机上多项式时间可解的问题，为NP问题，难解问题。NPC类：不确定性多项式时间可解完全类。NPC问题，又称NP完全问题或NP完备问题，是NP（非决定性多项式时间）中最难的决定性问题。因此NP完备问题应该是最不可能被化简为P（多项式时间可决定）的决定性问题的集合。第12页,共33页，2024年2月25日，星期天13

对称密码体制第13页,共33页，2024年2月25日，星期天14对称密码算法如果一个系统加密密钥和解密密钥相同，或存在简单的可推导关系，那么就称为对称密码体制；对称密码体制有很高保密程度，运算速度很快，处理效率很高；对称密码体制安全使用的关键在于：加密算法本身必须是足够强的，至少在攻击者获得一个或者多个密文是无法破译；发送者和接收者必须在某种安全的条件下获得密钥，并保证密钥的安全。核心问题在于密钥的管理；机制本身决定了不能处理不可抵赖问题；典型算法：DES算法；分为：序列密码和分组密码两类。第14页,共33页，2024年2月25日，星期天15流密码（序列密码）军事和外交场合常用；安全强度取决于产生的伪随机序列；速度快，安全程度高；分为：同步流密码和自同步流密码。产生伪随机序列使用该序列加密信息流(逐比特)明文密文第15页,共33页，2024年2月25日，星期天16同步流密码利用滚动密钥ki对输入的明文符号xi进行加密的，加密器可分为密钥流生成器和加密变化器两部分。在传输过程中出现一个错误只影响一个字符，不会影响后继字符。对敌方的恶意篡改没有任何检测能力。初始密钥有记忆元件的密钥流生成器加密器当前时刻加密密钥当前时刻明文当前时刻密文第16页,共33页，2024年2月25日，星期天17自同步流加密算法其加密器也可划分为密钥流生成器和加密变换器两部分，但是密钥流的生成与明文有关，因此密文不但与当前时刻明文有关，还与之前时刻明文有关将明文每个字符都扩散在密文的多个字符中，具有较强的抗统计分析能力。有记忆元件的密钥流生成器加密器当前时刻加密密钥当前时刻明文当前时刻密文第17页,共33页，2024年2月25日，星期天18分组密码将明文按照固定长度进行分组，加密以分组为单位进行；速度快，易于标准化，便于软硬件实现；与流密码相比，加密器中没有有记忆功能的元件。其核心是相信复杂函数可以由简单函数迭代得到；根据明文组和密文组的长度，可分为有数据扩展、有数据压缩和通常的分组加密算法主要算法包括：DES,3-DES,IDEA,Skipjack,Safer-64,LOK189,Shark等第18页,共33页，2024年2月25日，星期天19DES算法密匙长度是56位（因为每个第8位都用作奇偶校验），密匙可以是任意的数；DES对64(bit)位的明文进行一个初始置换IP置换并分成左半部分和右半部分(L0,R0)，各32位长。在每一轮中:密匙位移位，然后再从密匙的56位中选出48位。通过一个扩展置换将数据的右半部分扩展成48位，并通过一个异或操作替代成新的32位数据，在将其置换换一次。这四步运算构成了函数f。通过另一个异或运算，函数f的输出与左半部分结合，其结果成为新的右半部分，原来的右半部分成为新的左半部分。算法保密性依赖于密钥，密钥分为弱密钥，半弱密钥和互补密钥；

第19页,共33页，2024年2月25日，星期天20对称加密算法发展DES算法变形，得到3-DES,独立子密钥方法，GDES等；差分攻击法可攻击DES算法；AES算法：信息块长度和密钥长度都可变；宽轨迹设计策略；每层由线性混合层、非线性层和密钥加层组成；第20页,共33页，2024年2月25日，星期天21有限域计算在AES中应用有限域GF(28)由不可约多项式定义m(x)=x8+x4+x3+x+18765432101000110111

1

Bx6+x4+x2+x+157x7+x+183+x7+x6+x4+x2D4二进制位异或x7+x6+1C1×a(x)×b(x)modm(x)这里选的M(x)所有次数为8的不可约多项式列表中的第一个如果a(x)×b(x)modm(x)=1那么称b(x)为a(x)的逆元第21页,共33页，2024年2月25日，星期天22有限环运算环和域的区别在于，域可以进行除法运算而环不可以；加法定义为简单的比特位异或；两个系数为GF(28)上的多项式a(x)=a3x3+a2x2+a1x1+a0b(x)=b3x3+b2x2+b1x1+b0×c(x)=c6x6+c5x5+c4x4+c3x3+c2x2+c1x1+c0c6=a3*b3c5=a3*b2⊕a2b3c4=a3*b1⊕a2b2⊕a1b3c3=a3*b0⊕a2b1⊕a1b2⊕a0b3c2=a2*b0⊕a1b1⊕a0b2c1=a1*b0⊕a0b1c0=a0*b0d3=a3*b0⊕a2b1⊕a1b2⊕a0b3d2=a2*b0⊕a1b1⊕a0b2⊕a3b3d1=a1*b0⊕a0b1⊕a3b2⊕a2b3d0=a0*b0⊕a3b1⊕a2b2⊕a1b3因xqmodx4+1=xqmod4因此a(x)×b(x)=d(x)其中d(x)=d3x3+d2x2+d1x1+d0第22页,共33页，2024年2月25日，星期天23AES算法框架流程PlainTextInitialRoundAddRoundKeyStandardRoundByteSubShiftRowMixColumnAddRoundKeyFinalRoundByteSub

ShiftRowAddRoundKeyCipherTextNr-1RoundsCipherKeyExpansionExpandedKeySelectionRoundKey1RoundKey2…RoundKeyNr-1RoundKeyNr第23页,共33页，2024年2月25日，星期天24128位AES算法流程第24页,共33页，2024年2月25日，星期天25AES轮函数AES的轮函数每一轮迭代的结构都一样，由下述4个不同的变换构成，只是最后一轮省略了列混合变换。

字节替换（ByteSub）：对数据的每一字节应用一个非线性变换。行移位(ShiftRow)：对每一行的字节循环重新排序。列混合（MixColumn）：对矩阵的列应用一个线性变换。轮密钥加(AddRoundKey)：把轮密钥混合到中间数据。第25页,共33页，2024年2月25日，星期天26S-BOX替换盒把数据块分成字的形式，每个字包含4个字节，每个字节8bit；字节变换ByteSub是一种非线性字节变换，定义入右图所示，其中ai,j代表了一个字节，而ai,j-1

则是ai,j在GF(28)中的乘法逆；在具体实现中，S-BOX使用查表法实现来提供效率；替代表是一个16×16的矩阵。表中纵向的x取自状态矩阵中的高4比特，横向的y取自低取自状态矩阵中的4比特。替代的过程如下表，x行和y列的数据就用来替代的数据=+第26页,共33页，2024年2月25日，星期天27AES字节变换替换表第27页,共33页，2024年2月25日，星期天28AES行位移变换行移位运算（ShiftRow）：这是状态中字节的循环移位运算。这个运算可以表示