信息保障与安全课件：2010-第2周-密码学中的数学基础知识.ppt

1、密码学中的数学知识因子若b|a,则称b为a的因数若a=kb,而b既非a又非1,则称b是a的真因数. 例如 12的因子：1，2，3，4，6，1212的真因子：2，3，4，6整除实例Q: 下面哪个是对的?77 | 77 | 7724 | 240 | 2424 | 0实例Q: 1. 找出60的所有因子2. 列出80的所有真因子模运算 设n是正整数，a是整数，如果用n去除a，得商为q，余数为r，则可以表示为：a=qn+r,0r0, 则akbk(mod mk) ab(mod m), 如果d是m的因子，则a b(mod d)下面对进行证明。同余性质 证明：若adbd(mod m), 则m|(ad-bd),

2、 即m|d(a-b). 因(d, m)=1，故m|(a-b), 即a=b(mod m) 证明：d是m的因子，故存在m, 使得m=dm. 因为ab(mod m), 存在k, 使得a=b+mk= b+ dmk. 等式两边模d, 可得ab(mod d).最大公因数 设a, b是整数，则a, b的所有公因数中最大的一个公因数叫做最大公因数，通常记为gcd(a,b)。例如12和-18的最大公因数为6，记为gcd(12,-18) =6gcd(513,614)=？gcd(1024,888)=？如果两个整数的绝对值都比较小，求它们的最大公因数是比较容易的。如果两个数都比较大，可以用广义欧几里德除法，也称辗转相

3、除法。一个关于同余的性质 对任何非负整数a和非负整数b，设ab, a=bq+r, 0r1时，ax=1modm类方程的无解。进而，ax=bmodm类方程有解的条件是：（a,m）|b求解时，如果（a,m）=1，先求ax=bmodm的解，如果（a,m）1且（a,m）|b，暂时不讲仿射变换求解思考y=kp+bmod26时为什么要求(k,26)=1?大整数运算实现思考大整数加、减、乘法、除法、模运算，思考大整数加、减、乘法、除法、模运算，求逆程序改如何实现？求逆程序改如何实现？216=65 536 ，232=4294967296 ，264=18446744073709551616 1.84467441

4、1019（1）23567167967448973709551616+485667467073709551611 （2）23567167967448973709551616 mod 485667467073709551611 ？ 欧拉欧拉(Euler)函数函数 设(m)为小于或等于m且与m互素的正整数个数，称(m)为欧拉欧拉(Euler)函数。函数。例如， (1)1， (3)2，(5)4，(8)4。显然，当p为素数时，(p)p1。 欧拉欧拉(Euler)函数函数关于欧拉函数的重要结论关于欧拉函数的重要结论。若(m1，m2)1，则(m1m2)(m1)(m2), 尤其是当m1，m2都为素数时，(m1

5、m2)(m1)(m2) (m1-1)(m2-1). 例如，(15)= (3) (5)=24=8. 实际上，这些数是1，2，4，7，8，11，13，14，共8个。可以用等差数列的方式证明当m1，m2都为素数时的情形定理定理 若p为素数，k为正整数，则(pk)pk-1(p-1)。证明 因为小于或等于pk且与pk不互素的正整数有1p、2p、pk-1p，共pk-1个，所以(pk)pkpk-1pk-1(p1)。关于欧拉函数的重要结论(32) (25)=2 (5-1) (2-1)=16 (32)=?,(125)=?欧拉定理欧拉定理 欧拉定理欧拉定理 设n2且(a，n)1，则 a(n)1(mod n)例如，

6、求132001mod17。因为(13，17)1，所以13(17)1(mod 17)，因为(17)16，即13161(mod 17)。而2001125161， 132001（1316）125 13 13(mod 17)，即被17除得的余数为13。当n为素数p时，就是费尔马定理。费尔马定理费尔马定理 若p是素数，(a，p)1，则ap-1 1(mod p).群的定义 设G为非空集合，在G内定义了一种代数运算为，若满足下述公理：(1)有封闭性。对任意a、bG，恒有abG. (2)结合律成立。对任意a、b、cG，有(ab)c=a(bc)(3)G中有一恒等元e存在，对任意aG, 有eG, 使ae=ea=a

7、(4)对任意aG，存在a的逆元a-1G，使aa-1= a-1a =e则G构成一个群。若群G满足交换律，则称群G为交换群群举例例如，对于非空集合G=0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10，在mod11的情况下做加法运算，构成一个群，且是交换群。下面看看G，+满足公理的情况。(1)封闭性。对任意a、bG，恒有a+b(mod11)G. 例如, 8+9=176(mod11)G, 满足封闭性性质。 (2)结合律成立。对任意a、b、cG，有(a+b) +c=a+ (b+c)。这个容易理解。(3)G中有一恒等元e存在，对任意aG, 有eG, 使a+e=e+a=a. 在给定的集合G中

8、，e=0, 满足上面的性质，故恒等元存在。(4)对任意aG，存在a的逆元a-1G，使a+a-1= a-1+a=e. 例如, 7在集合中的逆元为4，因7+4(mod11) 0显然，加法满足交换律，故该群是交换群群的例子又如，对于非空集合G= 1, 2, 3, 4, 5, 6, 7, 8, 9, 10，在mod11的情况下做乘法运算，构成一个群，且是交换群。下面看看G，满足公理的情况。(1)封闭性。对任意a、bG，恒有ab(mod11)G. 例如89=726(mod11)G, 满足封闭性性质。 (2)结合律成立。对任意a、b、cG，有(ab) c=a (bc)。这个容易理解。(3)G中有一恒等元e

9、存在，对任意aG, 有eG, 使ae=ea=a. 在给定的集合G中，e=1, 满足上面的性质，故恒等元存在。(4)对任意aG，存在a的逆元a-1G，使aa-1= a-1a=e. 例如：7在集合中的逆元为8，因78(mod11) 1.显然，乘法满足交换律，故该群是交换群更多的例子0，1，+，mod21，*0，1，2，,n-1,+ modn1，2，,n-1,* modp（p是素数）有限域 （1）有限域的定义非空集合元素F，若在F中定义了加和乘两种运算，且满足下述公理：（1）F关于加法构成交换群。其加法恒等元记为0。（2）F中非零元素全体对乘法构成交换群。其乘法恒等元（单位元）记为1。（3）加法和乘

10、法间有如下分配律：a(b+c)=ab+ac(b+c)a=ba+ca则称F为一个域。若F中的元素个数有限，称F为有限域(Finite Field)。有限域也叫伽罗瓦(Galois Field)域。理解：“加”和“乘”运算，两种二元运算有限域举例例如，对于非空集合F=0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10，在mod11的情况下做加法和乘法运算，定义运算规则为：加法：如果a,bF, 则a+br mod11, rF乘法：如果a,bF, 则abs mod11, sF由前面的例题易得，F关于加法构成交换群，其加法恒等元为0；F中非零元素全体对乘法构成交换群，其乘法恒等元为1；分配

11、律也是成立的。故F在mod11的情况下做加法和乘法运算构成有限域。有限域举例实际上，对于素数p, 集合F=0,1,2,3,p-1在普通加法和乘法下，再加上modp运算，就成为有限域（2） 多项式同余多项式同余对于多项式f(x)，设它的次数为n，表示为deg(f)=n。对于多项式f(x)、g(x)、h(x)，设deg(f)n，如果g(x)=q(x)f(x)+h(x)，其中deg(h)n，则定义 g(x) h(x) mod f(x)例如：x5+x2+1=( x3+x+1)( x2-1)+(x+2), 所以，x5+x2+1 (x+2) mod( x3+x+1).（3） Zpx符号定义符号定义定义Zp

12、x为变元x的所有多项式的集合，多项式的每一项的系数为整数且都小于p. 而Zx表示变元x的所有多项式的集合，多项式的每一项的系数为整数。设整系数多项式f(x)=anxn+a1x+a0, 若f(x)Zpx, 则要求aiZp(0=i=n),即0=ai0和deg(f2)0 ,也即f1(x), f2(x)不能是常数。不可约多项式举例多项式可约与否，与其所在的集合相关。例如，x2+1在Zx中是不可约的，而在Z2x中是可约的，因为(x+1)( x+1)= x2+2x+1= x2+1.这里需要注意的是，在Zpx上进行运算时，多项式的系数是要模p的。以p=2为例，1+1=20mod2，-1-1+21mod2.

13、在上面的运算中，2x的系数20mod2，故一次项x的系数为0了。（5）不可约多项式构造域）不可约多项式构造域Zpx/f(x)是域当且仅当f(x)是不可约的，也就是说，如果f(x)是不可约的，则所有属于Zpx的多项式，在mod f(x)后的余式，组成的集合构成一个域。反之也成立。不可约多项式构造域举例不可约多项式构造域举例下面以选取f(x)= x3+x+1为例，容易知道x3+x+1在Z2x是不可约的。怎么去知道？不可约多项式构造域举例不可约多项式构造域举例计算Z2x/ x3+x+1, 可得所有余式构成八个元素的集合0, 1, x, x+1, x2, x2+1, x2+x, x2+x+1, 这个集

14、合构成一个有限域，加法单位元为0，乘法单位元为1. 举例试试看不可约多项式构造域举例不可约多项式构造域举例容易知道，1, x, x+1, x2, x2+1, x2+x, x2+x+1模x3+x+1就是自身，下面是进一步的例子。例如求x3 mod x3+x+1, 因为x3+x+10 mod x3+x+1, 故x3x3+ x3+x+1x+1 mod x3+x+1.又如求x4 mod x3+x+1，注意到x4 = x3x，故x4 ( x+1) x mod x3+x+1x2+x.不可约多项式构造域举例不可约多项式构造域举例 八个元素的集合0, 1, x, x+1, x2, x2+1, x2+x, x2

15、+x+1, 这八个域元素的系数为: (000,001,010,011,100,101,110,111)把多项式和二进制联系起来的有限域元素加运算 要计算两个域元素的和，可进行多项式相加（这里是在Z2x 中的加法，系数是模2加）例：例： (x2+1)(x2+x+1)=2x2+x+2 x mod（ x3+x+1 ）有限域元素加运算 实际上，八个域元素0, 1, x, x+1, x2, x2+1, x2+x, x2+x+1的系数为000, 001, 010, 011, 100, 101, 110, 111, 八个域元素0, 1, x, x+1, x2, x2+1, x2+x, x2+x+1之间的加法

16、，相当于000, 001, 010, 011, 100, 101, 110, 111中的加法(按位异或）。(x2+1)(x2+x+1)=2x2+x+2x mod(x3+x+1), 相当于(101) (111)=(010).有限域元素乘运算 要计算两个域元素的乘积，可进行多项式相乘，并且模x3+x+1约化（即用x3+x+1去除，找出余式）。由于是用一个三次多项式去除，余式的次数至多是2，因此余式是该域中的元素。如x2(x2+x+1) x4+x3+x2 (x+1)( x3+x+1)+1 1 mod（x3+x+1 ）因此，在Z2x中， （x2+1）(x2+x+1) x2+x mod（x3+x+1）有

17、限域元素求逆运算 对于集合0, 1, x, x+1, x2, x2+1, x2+x, x2+x+1，其模(x3+x+1)的加法逆元为就是自身；对于乘法逆元，可以用整数中的求逆元的方法类似得到，下面以求x2的逆元为例。有限域元素求逆运算 下面以求x2的逆元为例因为： x3+x+1x2x+(x+1)x2(x+1) (x+1)+1所以：1x2- (x+1)(x+1)x2-( x3+x+1)- (x2x) (x+1)x2+ (x2x) (x+1) - ( x3+x+1) (1+x)x2( x2+x+1) - ( x3+x+1)(1+x)故x2模(x3+x+1)的乘法逆元为x2+x+1，即：x2( x2

18、+x+1) 1 mod(x3+x+1)求逆元举例求x2模多项式x3+x+1的逆元步骤g(x) = q(x)f(x) + h(x)f(x)g(x)0-x3+x+1x2求逆元举例求x2模多项式x3+x+1的逆元步骤g(x) = q(x)f(x) + h(x)f(x)g(x)0-x3+x+1x21x3+x+1=x *x2+(x+1)x2x+1求逆元举例求x2模多项式x3+x+1的逆元步骤g(x) = q(x)f(x) + h(x)f(x)g(x)0-x3+x+1x21x3+x+1=x *x2+(x+1)x2x+12x2=(x+1) *(x+1)+1x+11求逆元举例求x2模多项式x3+x+1的逆元步

19、骤g(x) = q(x)f(x) + h(x)f(x)g(x)0-x3+x+1x21x3+x+1=x *x2+(x+1)x2x+12x2=(x+1) *(x+1)+1x+113x+1=(x+1)*1+010终止求逆元举例求x2模多项式x3+x+1的逆元步骤g(x) = q(x)f(x) + h(x)f(x)g(x)0-x3+x+1x21x3+x+1=x *x2+(x+1)x2x+12x2=(x+1) *(x+1)+1x+111=x2-(x+1) *(x+1)3x+1=(x+1)*1+010终止求逆元举例求x2模多项式x3+x+1的逆元步骤g(x) = q(x)f(x) + h(x)f(x)g(

20、x)0-x3+x+1x21x3+x+1=x *x2+(x+1)x2x+11=x2-x *(x3+x+1)-(x+1)*x2= -(x+1) *（x3+x+1)+(x2+x+1) *x22x2=(x+1) *(x+1)+1x+111=x2-(x+1) *(x+1)3x+1=(x+1)*1+010终止9. 原根原根对 于 一 个 素 数 p ， 如 果 数 值 ： g m o d p , g2modp, gp-1modp是各不相同的整数，并且以某种排列方式组成了从1到p-1的所有整数, 则称整数a是素数p的一个原根，也叫本原元或者生成元。上面定义的等价说法是：设p为奇素数，对于整数g, 1gbwh

21、ile b 0 t := b ;b := a mod b ;a := t; return a ;extended_gcd(a, b)伪代码function extended_gcd(a, b) x := 0 lastx := 1 y := 1 lasty := 0 while b 0 quotient := a div b temp := b b := a mod b a := temp temp := x x := lastx-quotient*x lastx := temp temp := y y := lasty-quotient*y lasty := temp return lastx

22、, lasty, a Evariste Galois(1811-1832) 17岁发现：代数方程的根式可解性是由这个方程的Galois群的可解性决定的.因此，5次及以上代数方程不存在求根公式。而古典代数学的其它难题（如尺规作图和倍方问题），此后也均可用Galois理论得到完全解决。从而古典代数学终结 古典代数学的终结古典代数学的终结 Galois的境遇的境遇1829:Galois论文由Cauchy审理，被遗失1830:由Fourier审理，不久Fourier逝世1831:再由Poisson审:“完全不能理解”,要其详细说明1832-5-30夜Galois留下1份说明第2天便与情敌决斗而死1846: Liouville决定发表Galois的文章1870: Jordan全面清晰地阐明Galois工作 从此Galois的工作得到完全承认Hermann Weyl 的评价的评价“Galois的论述在好几十年中一直被看成是“天书”；但是，它后来对数学的整个发展产生愈来愈深远的影响。如果从它所包含思想之新奇和意义之深远来判断，也许是整个人类知识宝库中价值最为重大的一件珍品”