1、数论基础及对称加密算法1提纲n数论基础v加密系统中常用的数论知识v复杂性理论简介n对称加密算法v对称密码体制模型v流密码v分组密码vDESvRijndael密码体制（ AES加密算法）vKASUMI分组密码 2数论基础3加密系统中常用数论知识n模 q运算v定义：给定任一正整数 q和任一整数 a，如果用a除以 q，得到商 s和余数 r，则有 a=sq+r，记ra mod q;v运算操作：加法 ： (a mod q)+(b mod q)=(a+b) mod q乘法： (a mod q)(b mod q)=(ab) mod q4加密系统中常用数论知识n模 q运算v运算性质：Zn定义为集合 0,1,q
2、-1 ，也称为模 q的剩余类集合，以下为 Zn上的模运算的性质；交换律： (a+b) mod q=(b+a) mod q(ab) mod q=(ba) mod q结合律： (a+b)+c mod q= a+(b+c) mod q(ab)c mod q= a(bc) mod q分配律： a(b+c) mod q=ab+ac mod q恒等律 ： (0+a) mod q=a mod q(1a) mod q=a mod q加法逆元：若存在 a,b Zn，使得 (a b) mod q=0，则 b是 a模 q的加法逆元。乘法逆元：若存在 a,b Zn，使得 ab=1 mod q，则 b是 a模 q的乘法
3、逆元。5加密系统中常用数论知识n模 q运算v求模逆运算 : (辗转相除法 )定理：设 r1=b1u mod q， r2=b2u mod q， r1=mr2+r3，则 r3=(b1-mb2)u mod q。求逆元： u,q已知，求 x， (0r3 rkrk+10，以上操作必终止于有限步，不妨设 rk+1=0，那么必有1=rk=(rk,rk-1)=(r 3,r2)=(r2,r1)=(u,q)利用性质：若 r 是 a b 的余数 , 则 gcd(a,b) = gcd(b,r) 所以 rk=bku mod q，得 bku1 mod q，于是 u-1bk mod q 6加密系统中常用数论知识n 群v群是
4、一种 代数结构 ，由一个 集合 以及一个 二元运算 所组成。 v群是一个 集合 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.
5、逆元。对于每个 G 中的 a，存在 G 中的一个元素 b 使得 a b = b a = e，这里的 e 是单位元。v使等式 a b = b a 总是成立的群叫做 阿贝尔群 （以 尼尔斯 阿贝尔 命名）。 v例子： 整数 配备上 加法 运算就形成一个群。 7加密系统中常用数论知识n环v集合 R和定义于其上的二元运算 + 和 ， (R, +, )构成一个环，若它们满足：(R, +)形成一个 交换群 ，其幺元称为零元素，记作 0。即： (a + b) = (b + a) (a + b) + c = a + (b + c) 0 + a = a + 0 = a a (a) 满足 a + a = a +
6、a = 0 (R, )形成一个 半群 ，即： (ab)c = a(bc) 乘法关于加法满足分配律： a(b + c) = (ab) + (ac) (a + b)c = (ac) + (bc) 其中，乘法运算符 常被省略，所以 ab 可简写为 ab。 此外，乘法是比加法优先的运算，所以 a + bc 其实是 a + (bc)。v交换环 ：若环 R中， (R, )还满足交换律，从而构成 交换半群 ，即： a， b R，有 ab=ba，则 R称为交换环。 8加密系统中常用数论知识n域：是一种可进行加、减、乘和除（除了除以零之外）运算的代数结构，是数域以及四则运算的推广；n 域分为两种：v 无限域，元
7、素个数无限，特征为0；v 有限域，元素个数有限，特征为p；v 特征：假设 p是最小的正整数， 使得 p个 1相加等于 0， 那么 p就称为域的特征；v 有限域元素个数为 q=pn；n 有限域 GF(q)同构于 GF(p)x/f(x)，其中 f(x)为 GF(p)上的不可约多项式；n 多项式在 GF(p)上不可约：有限域GF(p)的任一元素都不是多项式方程的解。域无限域 有限域特征 0 特征 p,含有q = pn个元素GF(q)同构于 GF(p)x/f(x)其中 f(x)为 GF(p)上不可约多项式9加密系统中常用数论知识n欧拉定理v若 m,a为正 整数 ，且 m,a互素 ， (gcd(a,m) = 1)，则a(m)1 mod m，其中 (m)为 欧拉函数 ， mod m为 同余 关系。 v在 数论 中，对正 整数 n，欧拉函数 (n)是小于或等于 n的正整数中与 n互质 的数的数目。此 函数 以其首名研究者 欧拉 命名，它又称为 函数、欧拉商数等。例如(8)=4，因为 1,3,5,7均和 8互质。v这个定理可以用来简化幂的模运算。比如计算 7222的个位数，实际是求 7222被 10除的余数。 7和 10互素 ，且(10)=4，由欧拉定理知 74 1 (mod 10)，所以：7222=7455+2=(74)557215572499 (mod 10)10
