数论基础及对称加密算法.ppt

***AES行位移变换行移位运算（ShiftRow）：这是状态中字节的循环移位运算。这个运算可以表示成为Bi,j=Ai,(i+j)mod4第29页,共31页，星期六，2024年，5月*AES列混合变换列混合变换：将状态每一列都视为环GF(28)上多项式s(x)，然后乘以固定多项式a(x)，并模除x4+1其中a(x)={03}x3+{01}x2+{01}x+{02}，定义变换公式根据环GF(28)的相关理论有：第30页,共31页，星期六，2024年，5月*AES轮密钥加密过程对状态和每轮的子密钥进行简单的异或操作。每轮子密钥是通过密钥调度算法从主密钥中产生，子密钥长度等于分组长度。轮密钥加运算需要用到4个导出的32比特子密钥。第31页,共31页，星期六，2024年，5月**********************************************************数论基础及对称加密算法**提纲数论基础加密系统中常用的数论知识复杂性理论简介对称加密算法对称密码体制模型流密码分组密码DESRijndael密码体制（AES加密算法）KASUMI分组密码第2页,共31页，星期六，2024年，5月*

数论基础第3页,共31页，星期六，2024年，5月*加密系统中常用数论知识模q运算定义：给定任一正整数q和任一整数a，如果用a除以q，得到商s和余数r，则有a=sq+r，记r≡amodq;运算操作：加法：[(amodq)+(bmodq)]=(a+b)modq乘法：[(amodq)×(bmodq)]=(a×b)modq第4页,共31页，星期六，2024年，5月*加密系统中常用数论知识模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的乘法逆元。第5页,共31页，星期六，2024年，5月*加密系统中常用数论知识模q运算求模逆运算:(辗转相除法)定理：设r1=b1umodq，r2=b2umodq，r1=mr2+r3，则r3=(b1-mb2)umodq。求逆元：u,q已知，求x，(0xq)，使得ux=1modq解：令r1=q，r2=u，则r1=q≡0×umodq，r2=u≡1×umodq即有:b1=0，b2=1令r1=m1r2+r3，0≤r3r2，得到r3≡(b1-m1b2)umodq，记b3=b1-mb2，则有r2≡b2umodq，r3≡b3umodq。令r2=m2r3+r4，0≤r4r3，得到r4≡(b2-m2b3)umodq，记b4=b2-mb3，则有r4≡b4umodq。继续下去，总之有：r1≡b1umodq，r2≡b2umodq，r1=m1r2+r3，0≤r3r2r2≡b2umodq，r3≡b3umodq，r2=m2r3+r4，0≤r4r3……rk-1≡bk-1umodq，rk≡bkumodq，rk-1=mk-1rk+rk+1，0≤rk+1rk……由于r2r3……rkrk+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第6页,共31页，星期六