信息安全导论5密码学数学基础.ppt

2019/5/17,1,信息安全导论 第五讲 密码学技术中的数学基础 华中科技大学图象所 信息安全研究室 Dr. Zuxi Wang,2019/5/17,2,密码学是研究密码系统或通信安全的一门学科，分为密码编码学和密码分析学。 密码编码学是使得消息保密的学科，从事此行的称为密码编码者。 密码分析学（密码破译学）是研究加密消息的破译的学科，从事此行的称为密码分析者。精于此道的人被称为密码学家，现代的密码学家通常是理论数学家。,2019/5/17,3,密码学是一门交叉学科，它很大程度上是应用数学学科。 密码学中涉及数论、代数、概率论、组合数学、计算复杂理论等多种数学知识。 还涉及信息论学科知识。 密码学所涉及的知识十分广阔，这里仅介绍部分数学基本知识。,2019/5/17,4,数论基础,素数 同余、模运算 中国剩余定理 Euclean算法 Fermat定理、Euler定理 素性检验 因子分解 离散对数,2019/5/17,5,整除、素数,记整数集合Z=,-3,-2,-1,0,1,2,3, 整除 设a,bZ，a0，如果存在mZ，使得b=ma，则称a整除b，以a|b表示，a是b的一个因子或约数。 如果没有任何m，使得b=ma，则称a不能整除b,记ab，此时有a=mb+r且01被称为素数是指p的因子仅有1，-1，p，-p。 否则，称为合数。,2019/5/17,6,整除基本性质 a|a; b0，b | 0; If a|b,b|c,then a|c; if a|1, then a=1; if a|b, and b|a,then a=b; if b|g and b|h, then b|(mg+nh),for any integers m and n 注意: if a=0 mod n, then n|a,2019/5/17,7,互素与最大公约数,最大公约数（最大公因子）： 若a,b,cZ，如果ca，cb，称c是a和b的公约数。正整数d称为a和b的最大公约数(记d=gcd(a,b)或(a,b) ，如果它满足: d是a和b的公约数。 对a和b的任何一个公约数c有cd。 等价的定义形式是： gcd(a,b)=maxk: ka，kb 若gcd(a,b)=1，称a与b是互素的。,2019/5/17,8,最小公倍数,最小公倍数 a,b的倍数中最小者称为a,b的最小公倍数，记为：lcm(a,b) a,b不全为0，有ab=gcd(a,b)lcm(a,b). 注意：对有限个整数a1,a2,an,也可定义最大公约数gcd(a1,a2,an)和最小公倍数lcm(a1,a2,an).,2019/5/17,9,带余除法,带余除法： aZ, m0，可找出两个唯一确定的整数q和r使a=qm+r, 0r m。 (若r=0则ma） q和r这两个数分别称为以m去除a所得到的商数和余数.记：q=a div m或a/m, r =a mod m。 存在x,y，gcd(a,b)ax+by 如果a=qb+r,则gcd(a,b)=gcd(b,r). gcd(a/gcd(a,b),b/gcd(a,b)=1,2019/5/17,10,算术基本定理,下面关于素数的事实均成立 如果p是一个素数，并且p|ab，则有p|a或p|b； 素数有无穷多个； 素数定理:记(x)为不大于x的素数的个数，则有 它表明，对于充分大的x，可以用xlnx近似地表示(x)。 算术基本定理： 任何一个不等于0的正整数a都可以写成唯一的表达式 ，这里P1P2P3Pt是素数，其中i0整数。,2019/5/17,11,目前没有可用于整数分解的有效算法。 对于整数a,b(a,b2)，a,b的素数分解式分别为： ， ，其中ei，fi0,ti1，则有：,2019/5/17,12,带余除法中，aZ，m0，a=qm+r， 0r m，r为a除以m的余数或剩余(Residue)，m称为模数，所以称r为a模正整数m的剩余，记ra mod m m(a-b)a=q1m+r,b=q2m+r。即a和b分别 除以m有相同的余数 同余称整数a模正整数m同余(数)于整数b，并写ab（mod m）是指m(ab), m称为模数。 note: if a=0 mod m, then m|a,整数同余式和同余方程,2019/5/17,13,1、模关系：相对于某个固定模数m的同余关系，是指整数间的一种等价关系。具有等价关系的三点基本性质： 自反性：对任意整数a，有aa（mod m） 对称性：若ab(mod m)，则ba（mod m） 传递性：若ab (mod m),bc(mod m),则ac(mod m) 全体整数集合Z可按模m（m1）分成一些两两不交的等价类（剩余类）。 2、整数模m同余类共有m个，他们分别为mk+0,mk+1, mk+2,mk+(m-1); kz，每一个算一类，每一类都可以选一个代表元，一般选这一类中的最小的非负整数。于是称0,1,2,m-1为标准完全剩余系。其中与m互素的剩余类构成模m的简约剩余系。Z模12的标准完全剩余系为：0,1,2,3,4,5,6,7,8,9,10,11,2019/5/17,14,Modulo 7 Example,. -21 -20 -19 -18 -17 -16 -15 -14 -13 -12 -11 -10 -9 -8 -7 -6 -5 -4 -3 -2 -1 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 .,2019/5/17,15,3、模运算：对于某个固定模m的同余式可以象普通的等式那样相加相减和相乘： a(mod m)b(mod m)=(ab)(mod m) a(mod m)*b(mod m)=a*b(mod m) 例：由同余式演算证明5601是56的倍数，2231是47的倍数。 解： 注意53=12513(mod56) 于是有561691(mod56) 对同余式的两边同时升到10次幂， 即有56(560-1)。 其次, 注意26=64-30(mod47),于是 223=(26)325=(26 26)26 25 900*(-30)*(32) mod(47) (7)* (-30)*(32) (mod47) 1(mod47) 于是有 47(223-1),2019/5/17,16,Modulo 8 Example,2019/5/17,17,4、定理：(消去律)对于abac(mod m)来说，若最大公因子gcd (a,m)1（即a与m是互素），则bc(mod m) 加法消去律： a+ba+c(mod m)，有bc(mod m). 5、一次同余方程axb(mod m)，这个方程有没有解，相当于问有没有那样一个整数x，使得对于某个整数y来说，有ax+my=b 定理：记最大公因子(a,m)=d，则同余方程axb(mod m)有解的充分必要条件是db。当这个条件满足时，恰有d个模m同余类中的整数是上述方程的解。 证明：略。（从ax+my=b入手）,2019/5/17,18,6、整数环z模正整数m得到的剩余类集合可以记为zm(或z/(m), zm=0,1,m-1 在3、中已说明zm对剩余类的加法，乘法是封闭的，可列出它们的加乘表。我们称zm为剩余类环（或同余类环） 7、在整数环z中是没有零因子的，即两个非零整数的乘积一定不等于0，但是剩余环则不然。 例z12中：3*4=12=0 说明，zm中的元素可分为两类，一类是零因子，即若zm,0，存在zm且0，有*=0，则称，都为zm中的零因子。另一类是可逆元，即若zm，存在zm，使*=1，此时,互为各自的逆元，记-1=；-1=,2019/5/17,19,定理：剩余类环zm中元素=a为zm的可逆元最大公约数(a,m)=1 要证明这个定理，只需证明下列引理： 引理：任意两个整数a和b都有一个最大公约数，这样一个最大公约数d可以表示成a,b二数关于整系数的线性组合，即有s,tz，使dsatb。 证明：不妨设b0，用辗转相除法，先用b去除a，得 a=q1b+r1,0r1b; (1) 如果r1=0，停止，否则再用r1去除b，得 b=q2r1+r2,0r2r1; (2) 如果r2=0，停止，否则再用r2去除r1，得 r1=q3r2+r3;0r3r2; (3) 等等，这样一直进行下去，可得一系列关系式： rk-3=qk-1rk-2+rk-1,0rk-1rk-2; (k-1) rk-2=qkrk-1+rk,0rkrk-1; (k),2019/5/17,20,由于历次所得的余数 r1 r2 r3 r4 rk0 是严格递降的一串非负整数，故最后总会出现余数为0的情形： rk-1=qk+1rk (k+1) 所以，进行有限步必停止，此时d=rk=(a,b)成立，这是因为 1). 可知rk为a和b的公约数，只要按倒序分析自然有此结论。 2). a和b的任何一个公约数c都是rk的约数，只要按正序分析，自然可知。 为证定理的后一部分，将式(1)做移项有 r1=s1a+t1b（其中s1=1,t1= -q1） 再将式(2)右端通过移项变为r2=s2a+t2b 这样一直下去，最后得d=rk=s*a+t*b, s,tz.,2019/5/17,21,例子：求(180，252)，并将他表示为180和252这两个数的一个带整系数的线性组合。 解： 252=1*180+72 (1) 180=2*72+36 (2) 72=2*36 (3) 得(180,252)=36，同时有 72=252-1*180 (1) 由(2)得 36=180-2*72 (2) 将(1)代入(2 )，即得 36=180-2*(250-180) =3*180-2*252,2019/5/17,22,中国剩余定理,例子：（孙子算经）今有物不知其数：三三数之余二；五五数之余三；七七数之余二。问物几何？ 答曰：二十三。 232*70+3*21+2*15(mod 105) （口诀：三人同行七十稀，五树梅花廿一枝， 七子团圆月正半，除百零五便得知。） 问，70，21，15如何得到的？ 原问题为： 求解同余方程组,2019/5/17,23,注意：若x0为上述同余方程组的解，则x0=x0+105*k(kz) 也为上述同余方程组的解。有意义的是，解题口诀提示我们先解下面三个特殊的同余方程组 (1) (2) (3) 的特殊解 =? =? =? 以方程（1）为对象，相当于解一个这样的同余方程 35y1(mod 3)，为什么呢？ 原因是，从（1）的模数及条件知，x应是35的倍数，于 是可以假设x35y，有,2019/5/17,24,35y1(mod 3)相当于2y1(mod 3) 解出y=2（mod3） 于是x35*2(mod(3*35) 70(mod105) 类似地得到（2）、（3）方程的模105的解21、15。 于是有 得,2019/5/17,25,中国剩余定理：设自然数m1,m2,mr两两互素，并记M=m1m2mr，则同余方程组 在模M同余的意义下有唯一解。,2019/5/17,26,证明：考虑方程组， (1=i=r) 由于诸mi(1=i=r)两两互素，这个方程组作变量替换，令x=(M/mi)*y，方程组等价于解同余方程： (M/mi)y1(mod mi),2019/5/17,27,若得到特解yi,只要令 xi=(M/mi)yi 则方程组的解为 x0=b1x1+ b2x2+ + brxr (mod M) 模N意义下唯一。 中国剩余定理的用途之一是，它给出了一种方法，使非常大的数对M的模运算转化到更小的数上来进行运算，当M为150位或150位以上时，这种方法非常有效。,2019/5/17,28,Euclidean算法,依据(a,b)=(b,a mod b)的辗转除法是求解两个整数的最大公因子的传统方法，由此而得的欧几里得算法是一个用于计算两个整数的最大公因子的有效算法。 Euclidean算法： 输入a和b，where a,bz,a,b0,ab. 如果b0，则依次完成:ra mod b,ab,br,否则返回a. 输出gcd(a,b)=r.,2019/5/17,29,Example GCD(1970,1066),1970 = 1 x 1066 + 904 gcd(1066, 904) 1066 = 1 x 904 + 162 gcd(904, 162) 904 = 5 x 162 + 94 gcd(162, 94) 162 = 1 x 94 + 68 gcd(94, 68) 94 = 1 x 68 + 26 gcd(68, 26) 68 = 2 x 26 + 16 gcd(26, 16) 26 = 1 x 16 + 10 gcd(16, 10) 16 = 1 x 10 + 6 gcd(10, 6) 10 = 1 x 6 + 4 gcd(6, 4) 6 = 1 x 4 + 2 gcd(4, 2) 4 = 2 x 2 + 0 gcd(2, 0),2019/5/17,30,扩展Euclidean算法,经扩张的Euclidean算法不仅能够被用于计算d=gcd(a,b)，而且能够找到满足等式ax+by=d的整数x和y。 扩展Euclidean算法： 输入a和b，where a,bz,a,b0,ab. 如果b=0，则:da,x1,y0, 返回(d,x,y). x21,x10,y20, y11 如果b 0，则依次完成: qa/b,ra- qb,xx2-qx1,yy2-qy1;ab,br,x2x1,y2y1,x1x,y1y da,xx2,yy2，返回(d,x,y). Euclidean算法和扩展Euclidean算法时间复杂度为O(lgn)2).,2019/5/17,31,Fermat定理和Euler定理,Fermat定理：如果p是素数并且a是正整数,(p,a)=1那么，ap-11(mod p) 证明： 设z*pzp(,p)=1 易见，z*p=1,2,3,(p-1)且因为（a,p）1知 a z*p=a,2a,3a,(p-1)a= z*p，原因是a z*p内的元素两两不同。他们刚好为1,2,3,(p1)的一个排列。所以 a*2a*3a*(p-1)a1*2*3*(p-1)(modp) 由（(p1)！，p）1， 所以 ap-11(modp) 推论：对素数p，任意正整数a，有apa(modp). useful in public key and primality testing,2019/5/17,32,Euler 函数 Euler函数(n)是这样来定义的： 当n1 时,(1)1；当n1时，它的值(n)等于比n小而与n互素的正整数的个数。 以n24为例，比24小而与24 互素的正整数为：1,5,7,11,13,17,19,23。因此，我们有(24)8。 若p为素数，则(p)p-1。 若p，q都为素数且pq，此时有 (pq)(p)(q)= (p-1)(q-1) 证明：考虑zpq剩余类的集合是0，1，2，（pq-1）,集合中与pq不互素的元素子集为p,2p,(p-1)q和子集 q,2q,(p-1)q以及0，于是若设npq，有 (n)=pq-(q-1)+(p-1)+1 =(p-1)(q-1)=(p)(q). 例：(21)=(3*7)=(3)(7)=2*6=12.,2019/5/17,33,若m1,m2互素，则(m1m2)(m1) (m2). 设n= p1e1p2e2prer，其中p1,p2,pr为互异素数，则(n)= p1e1-1p2e2-1prer-1(p1-1)(p2-1)(pr-1) =n(1-1/p1) (1-1/p2) (1-1/p3) (1-1/pr) Euler公式 证明：考虑1/n,2/n,n/n，然后化简成既约分数，分母为d的一类分数有(d)个，于是 欧拉定理（Euler）： 若整数a与整数n互素，则a(n)1(mod n)。 证明：设小于n而和n互素的(n)个正整数为 r1,r2,r3,r(n) (1),2019/5/17,34,他们是模n两两互不同余的。 对每一个定数i来说，由于a和ri都与n互素，所以(ari,n)=1， 所以ari同余于（1）中的某个ri即 ariri(mod n)，1i(n) 并且当ij时有ari /arj(mod n).于是, 为 的置换.所以有 由(ri,n)=1, 所以 Remarks： 1*. np时，(a,p)=1,有ap-11(mod p)为Fermat定理！ 而对任意的a，有apa(mod p)（Fermat） 2*.易见a(n)+1a(mod n) 3*.若n=pq，p与q为相异素数，取0mn，若(m,n)=1，有m(n)+1m(mod n)，也即m(p-1)(q-1)+1m(mod n).,2019/5/17,35,4*.对于3中，若(m,n)p或q，也同样有m(n)+1m(mod n) 5*.由 (m(n)k1k(mod n) 知 mk(n)1(modn)， 进一步 mk(n)+1m(mod n) mk(p-1)(q-1)+1m(mod n),2019/5/17,36,素性检验、因子分解,在许多加密算法中，需要随机选择一个或多个非常大素数，因此必须确定一个给定的大数是否是素数。素性检验(测试) 目前还没有简单有效的方法解决该问题。 Miller和Rabin提出一种算法，其利用了Fermat定理。该算法产生的数不一定数素数，但令人惊讶的是，其产生的数几乎可以肯定是素数。,2019/5/17,37,素性检验、因子分解,RSA算法安全性以对大整数进行素数分解的困难性为基础，即无法在多项式时间内对于一个足够大的整数进行分解。一旦这个难题被破解，则RSA算法的安全性便不复存在。 一些具代表性的因子分解算法包括： 二次筛法 p-1因子分解方法 是更为有效的椭圆曲线方法的基础 数域筛法等,2019/5/17,38,强素数,许多密码算法关心强素数。 设nZ，p和q是素数，并且n=pq。当p，q满足以下特性时，称之为强素数。 Gcd(p-1,q-1)比较小； p-1和q-1都有大的素因子（分别记为p*和q*）； p*-1和q*-1都有大的素因子； p+1和q+1都有大的素因子； (p-1)/2和(q-1)/2都是素数。 如果素数p具有特性,则它们一定具有特性和. 此时，即使采用某些特殊的因子分解方法，对整数n进行因子分解也非常困难。,2019/5/17,39,为了增加密码算法的安全性，建议使用长度大并且具有随机性结构的强素数，其中，素数的长度比其结构特点更为重要。 但是，从因子算法对整数进行分解的概率的角度考虑，强素数与其他素数相比并没有明确的优势。,2019/5/17,40,代数基础群、环、域、布尔代数,概述 群、环、域基本概念 有限域 GF(pn) 多项式算术 布尔代数与布尔函数,2019/5/17,41,概 述,有限群、有限域、布尔函数等在密码技术和应用中越来越重要。 cryptography AES, Elliptic Curve, IDEA, Public Key 将从抽象代数的群、环、域的基本概念开始介绍。,2019/5/17,42,群（Group）,代数系统：一个集合以及定义在其上的一组运算一起构成一个代数系统。 群（group）是一个代数系统 ，它仅有一个二元运算*（由于是代数系统，所以运算封闭性满足），并满足: 结合律: (a*b)*c = a*(b*c) 具有单位元e: e*a = a*e = a 每一元a 有逆元a-1: a*a-1 = e 如果满足交换律: a*b = b*a 则形成一个交换群(commutative group),也叫阿贝尔群(abelian group). Remark:在不引起歧义下，经常将运算符号省略。 a*b=ab,2019/5/17,43,例1 和 不是群。 、和 都是群。,例2 设有Z4=0,1,2,3，模4的加法运算 定义为 则构成一个群。,Examples:,2019/5/17,44,Examples:,是一个交换群，也叫加群。+是关于模m加法； ，是关于模m的乘法。当m是素数时，它构成一个乘法交换群；但当m不是素数时，它不构成群。,2019/5/17,45,循环群（Cyclic Group）,群元素的幂 example: a3 = a*a*a ak = a*a*a (k个a相乘，k正整数) 规定: e=a0，a-k=a-1*a-1*a-1=(a-1)-k(k个a-1相乘，k正整数) 对任意整数m,n,am*an=am+n,(am)n=amn,a-n=(a-1)n=(an)-1. 群中任何元都是某个元g的幂，称群为循环群，g称为其一个生成元(generator)。 i.e. 对群中任一元b,存在k,使 b = gk. 以g为生成元的循环群记为G=.称为由g生成的循环群.,2019/5/17,46,对任意负整数 ,按照群中逆元的表示方法,例3 群是循环群，1是生成元，10=0，对任意正整数n，n=1+1+1，按照群中元素的幂的表示方法n=1n.,例4 例2中的群是循环群，1是其生成元， 3也是其生成元。 因为10=0，11=1，12=141=res4(2)=2, 13=1241=2 41=res4(3)=3 又30=0，31=3，32=343=res4(6)=2, 33=32 43=243=res4(5)=1,2019/5/17,47,a*a=b * b=c * c=e * e=e , a * b=b * a=c, b * c=c * b=a， a * c=c * a=b 是一阿贝尔群，但它不是循环群，一般称这个群为Klein四元群。,2019/5/17,48,群的阶和元素的周期,设是一个群，如果G是有限集，则称是有限群，G中元素的个数称为群的阶；若G是无限集，则称是无限群。 设是一个群，a G，若存在正整数 r ，使得 ar =e，则称元素 a 具有有限周期。使ar=e成立的最小的正整数 r 称为 a 的周期。如果对于任何正整数r，均有 ar e，则称 a 的周期为无限。,2019/5/17,49,群的阶和元素的周期,Examples 在群 中，单位元1的周期为1, -1的周期为2. （-1）2=（-1）4=（-1）6= =1 群中， 14 = 13 41=3 41 = res4(4)=0； 21 = 2 ，22=2 42 = res4(4)= 0；34 = 33 43 = 1 43 = res4(4) = 0。 生成元1和3的周期均为4，循环群的阶也为4。 循环群的生成元1和1，其周期均为无限，群是一个无限阶的循环群。,2019/5/17,50,群的部分性质,消去律： 设是一个群，则对任意的a,b G， （1）存在唯一的元素xG，使a*x=b； （2）存在唯一的元素yG，使y*a=b。 设是一个群，则对任意的a,b,cG （1）若a*b=a*c, 则 b=c； （2）若b*a=c*a，则 b=c。,2019/5/17,51,群的部分性质,求逆: 设是一个群，则对任意的a,b,a1,a2,ak G (a*b)-1=b-1*a-1; (a1*a2*ak)-1=ak-1*a2-1*a1-1. 关于元素的周期: 群中的元素 a 若具有有限周期r，则当且仅当k 是r的整数倍时，ak = e. 群中任一元素与它的逆元具有相同的周期。 在有限群中，每个元素均具有有限周期，且周期不超过群的阶。结论对无限群不成立。如群 .,2019/5/17,52,群的部分性质,设是一由元素 g 生成的循环群，则 若 g 的周期为 n ，则是一个阶为 n 的有限循环群； 若 g 的周期为无限，则是一个无限阶的循环群。,2019/5/17,53,群的部分性质,Examples 群中单位元0的周期是1；1和3的周期均为4；2的周期为2，群的阶4. 设是一个群，且对于任意的a,bG，有(a * b)2=a2 * b2 , 则 是阿贝尔群。 设Z6 =0,1,2,3,4,5, 6 是模6的加法，定义为： a 6b = res6(a+b)，是一个群。 给出其单位元；各元素的逆元；各元素的周期。,2019/5/17,54,设是一个群，若是的子代数，单位元e H，且对于任意的a H，有a-1 H，则称是的子群。 的非空子集H关于G的运算*构成子群，必须满足： 封闭性：H关于 * 封闭，a,bH，有a*b H; 单位元：G的单位元eH; 可逆性：任意aH，有a-1H. Example: 对于任意的整数m，若令Im= mi: i I. 则均构成的子群。,子群（Subgroup）,2019/5/17,55,若是的子群，则也是群。 设是一个群，H是G的非空子集，若也是群，则称是的子群。（子群等价定义） 设是群，H是G的非空子集，若 (1)对于任意的a,bH，有a*bH； (2)对任意的aH，有a-1H， 则是的子群。,子群（Subgroup）,2019/5/17,56,设是群，H是G的非空子集， 若对于任意的a,bH，有a*b -1H，则是的子群。 设是一有限群，若是的子代数，则是的子群。 即：若对于任意的a,bH，有a*bH，则是的子群（H有限且关于运算封闭就构成子群）。 设是一个群，若是的有限子代数，则是的子群。,子群（Subgroup）,2019/5/17,57,子群（Subgroup）,Examples 设是一个群，a是G中任一元素，令H是a的所有整数次幂的集合，则H对于G的运算构成的子群。显然是由元素a生成的一个循环群。 设是一个群，定义G的子集H=h:对任意x G,h*x=x*h，H对于运算*构成的子群。,2019/5/17,58,陪集（coset）、正规子群（normal subgroup）,H是G的子群，a属于G，aH=ah|h属于H称为G的一个关于H的左陪集（a所在的陪集）。同样Ha构成一个右陪集。 对a，aH不一定等于Ha。 如果对所以的a，都有aHHa，则称H为G的一个正规子群。称aH或Ha为陪集。,2019/5/17,59,拉格朗日(Lagrange)定理,陪集定理：G的关于H的所有不用的左（右）陪集构成G的一个分划。 Lagrange定理：群G必为其子群H及其全部不相同的陪集的直和。 推论：有限群的阶必为其子群的阶的整数倍。 素数阶群只有平庸子群（群自身与单位元）,2019/5/17,60,群的同态与同构,h:G1G2群间的一个映射，如果h保持群的运算，即：a,b of G，有h(ab)=h(a)h(b)，则称h为群G1,G2间的一个同态映射，简称同态(homomorphism)。 若同态h同时是一个双射，那么称h为一个同构映射，简称同构(isomorphism) 。这是称两群G1,G2是同构的。 从代数结构的角度看，同构的群具有相同的代数结构，被视为同一群。,2019/5/17,61,商群（Quotient group）,群G的正规子群H与其全部不相同的陪集在陪集乘法意义下构成一个群，称为G关于H的商群，记为G/H。 f: GG群间的一个同态映射，kerfg:f(g)=e,e为G的单位元，即kerf为G的单位元e在G中的原象集合。称kerf为同态映射f的核。 同态基本定理：设G为G关于同态映射f的象，则有： 1.kerf是G的正规子群； 2.G与商群G/kerf同构。,2019/5/17,62,变换群（Transform group）,集合A上的若干双射（一一映射）对于映射的复合运算构成一个群，称其为A上的一个变换群。 一个集合A的所有一一变换作成一个变换群。 任何一个群都与一个变换群同构。,2019/5/17,63,置换群（permutation group）,有限集A到直身的一个双射称为A上的一个置换。A=n，称A上的置换为n阶置换。 An，A上所有的n阶置换在置换乘积（映射复合操作）下构成一个群，称为n阶对称群(Symmetric group)，记为Sn。 Sn的任一子群，都称为一个置换群。 所有n阶偶置换（可分解为偶数个对换的乘积的置换）构成Sn的一个子群，叫交错群(Alternative group)，记为An。,2019/5/17,64,置换群（permutation group）,对称群Sn的阶为n!，交错群An的阶为n!/2。 凯莱(Caylay)定理：每一个有限群均同构于由群元素集合上的一个置换群（ Sn的一个子群） (gG，gf(g),f(g)为G上一个置换， f(g)： gi g gi ,全体f(g)构成G上的置换群),2019/5/17,65,群的生成元系,G是一个群，S是G的一个非空子集 S生成的子群H:G的包含S的最小子群,记H(S)。 S生成的子群H由S中元素及逆元的任意乘积构成。 如果G=(S)，那么称S为群G的一个生成元系(Generator system or generator set)。 当S1，Sa，那么S生成G的一个循环子群，(S). 群的生成元系通常不唯一。,2019/5/17,66,对称群的生成系,对称群Sn的每个元都可以写成(12),(13),(1n)这n-1个对换（2-循环置换）中的若干个的乘积。 S=(12),(13),(1n)是Sn的一个生成元系。 Remark：Sn还有其他生成元系。,2019/5/17,67,环（Ring）,带两个运算（称加法和乘法）的集合满足: 关于加法+构成一个abelian群，其单位元为0称为零元； 关于乘法 满足: 乘法封闭律； 满足结合律； a(bc)=(ab)c 对加法的分配律: a(b+c) = ab + ac 则称为一个环（Ring） 如果乘法是交换的，则称环为交换环( commutative ring) 环中关于乘法如果有单位元，称之为环的单位元。,2019/5/17,68,子环、理想、剩余类环,的子代数即为其子环。 R的子集关于R的运算仍然是环，称为R的子环。 R的子环I，如果同时关于乘法还满足： 对R中任意元r，I中任意元a，有ar,ra均仍属于I. 则称I为一个理想。 R的理想I，关于加法构成的剩余类集合上关于模I的加法和乘法构成环，叫R的模I的剩余类环。记为R/I.,2019/5/17,69,环的同态与同构,环的同态与同构映射定义类似群的同态与同构。 两个环之间的映射如果保持分别保持环的运算，就称为环的同态 如果同态是一一映射，就称为同构。 类似地有同态基本定理。,2019/5/17,70,零因子、整环,若ab=0,但a,b都不是R中的零元, 那么a(b)均称为左(右)零因子.否则，称为非零因子. 无零因子环: 如果R中的a, b有ab=o,那么必有a=0 or b=0. 整环（domain）：交换的有单位元的无零因子环，称为一个整环。,2019/5/17,71,Example: 整数集关于普通的加法和乘法构成一个环且是一个整环. 是一个交换环，称为模m的剩余类环。 当m是合数时，剩余类环Zm中有零因子，Zm中的a，若(a,m)=1,则a有逆元；当m是素数时，剩余类环Zm是整环。,2019/5/17,72,除环、域,一个环关于其乘法不一定有单位元，另外其任一元也不一定有乘法逆元。 如果一个环有单位元，并且任一非零元均有逆元，则称其为一个除环。 所以是除环，它至少有一非零元，且是加群；是群。 一个除环，如果其关于乘法是交换的，则称其为一个域（Field）。,2019/5/17,73,有限域（Galois Fields）,有限域也叫Galois 域，在密码学中有重要作用。 三个结论： 每个有限域的阶必为素数的幂。 对任意的素数p和正整数n，存在pn阶域。 同阶的有限域必同构。 于是：在同构意义下，pn阶的有限域有且只有一个，记为GF(pn). 特别地，经常用到有限域: GF(p) 称为素域 GF(2n),2019/5/17,74,Galois Fields GF(p),GF(p) 是 0,1, , p-1上关于模p加法、乘法构成的有限域。 P为素数时，其中任意非零数都有逆元.,2019/5/17,75,Example GF(7),2019/5/17,76,GF(p)中乘法逆元算法,通过扩展Euclidean算法得到: EXTENDED EUCLID(m, b) 1. (A1, A2, A3)=(1, 0, m); (B1, B2, B3)=(0, 1, b) 2. if B3 = 0 return A3 = gcd(m, b); （b mod m 没有逆） 3. if B3 = 1 return B3 = gcd(m, b); B2 = b1 mod m 4. Q = A3 div B3（A3除以B3的商） 5. (T1, T2, T3)=(A1 Q B1, A2 Q B2, A3 Q B3) 6. (A1, A2, A3)=(B1, B2, B3) 7. (B1, B2, B3)=(T1, T2, T3) 8. goto 2 GF(pn)中乘法求逆类似（换成关于多项式的除法）,2019/5/17,77,Inverse of 550 in GF(1759),2019/5/17,78,域上的多项式,域F上的多项式为形如： 的表达式，其中nN,aiF,i=1,2,n. 若an0,称n为该多项式的次数,记n=deg(f(x),并称an为首项系数,首项系数为1的多项式称为首1多项式.,2019/5/17,79,多项式整环,记Fx为域上所有多项式f(x)构成的集合，则Fx关于通常的多项式加法+和乘法 形成一个整环，叫域F上的（一元）多项式环。0为其零元，1为其单位元。 在Fx上类似于整数环，关于多项式有商式、余式、整除、互素、最高公因式、最低公倍式等概念。,2019/5/17,80,多项式带余除法,带余除法：a(x),b(x)Fx,且b(x)0,则存在唯一的q(x),r(x)Fx,使a(x)=q(x)b(x)+r(x), 式中deg(r(x)deg(b(x). q(x)称为商式,r(x)称为余式 也用a(x) mod p(x) 表示a(x)除以p(x)的余式.称为a(x)模p(x)，p(x)称为模多项式。,2019/5/17,81,不可约多项式,若存在q(x),b(x)，deg(q(x)1, deg(b(x)1，使a(x)=q(x)b(x)，则称a(x)为可约多项式，否则称为不可约(既约)多项式。,2019/5/17,82,多项式运算,仅考虑一元多项式 可把多项式运算分为三种： 使用代数基本规则的普通多项式运算； 系数运算是模p运算的多项式运算，即系数在Zp中； 系数在Zp中，且多项式被定义为模一个多项式m(x)的多项式运算。,2019/5/17,83,普通多项式运算,加法、减法为(相同次项)对应系数的加减法 乘法为逐项相乘。 eg let f(x) = x3 + x2 + 2 and g(x) = x2 x + 1 f(x) + g(x) = x3 + 2x2 x + 3 f(x) g(x) = x3 + x + 1 f(x) x g(x) = x5 + 3x2 2x + 2,2019/5/17,84,系数 在Zp中的多项式运算,在普通多项式运算中，所有系数都取modp运算。 特别是 mod 2 的多项式运算 ie all coefficients are 0 or 1 eg. let f(x) = x3 + x2 and g(x) = x2 + x + 1 f(x) + g(x) = x3 + x + 1 f(x) x g(x) = x5 + x2,2019/5/17,85,模多项式运算,基于多项式带余除法: f(x) = q(x) g(x) + r(x) r(x) 称为余式(remainder) 记r(x) = f(x) mod g(x) 定义模g(x)的多项式加法、乘法。 如果没有余式，说g(x) 整除 f(x) 如果g(x)仅有它自己和1为其因式，说g(x)不可约(或既约)多项式(或素多项式) 所有多项式在模不可约多项式加法乘法下构成一个域。,2019/5/17,86,模p(x)的剩余类环,Fx中一个多项式p(x)，(p(x)为由p(x)生成的Fx的子环，它是一个理想(主理想). Fx/(p(x)形成一个模p(x)的剩余类环。 它等同于所有n-1次多项式集合上关于模p(x)加法乘法运算构成的环。 当p(x)为不可约多项式时，其形成一个域。,2019/5/17,87,最大公因式,寻找多项式的最大公因式 c(x) = GCD(a(x), b(x) 如果 c(x) 是同时整除 a(x), b(x) 的次数最高的多项式。（等价定义） 通过扩充Euclidean算法来寻找: EUCLIDa(x), b(x) 1. A(x) a(x); B(x) b(x) 2. if B(x) = 0 return A(x) = gcda(x), b(x) 3. R(x) = A(x) mod B(x) 4. A(x) B(x) 5. B(x) R(x) 6. goto 2,2019/5/17,88,模多项式运算、GF(2n),有限域的元素个数必为pn，p为素数，n为正整数。 p个元素上以模p运算产生一个域,Zp。 但具有pn个元素的集合上模pn运算却不一定能产生域。 如何定义合适运算，使之pn个元成域？ Zpn关于模pn运算是不行的。,2019/5/17,89,模多项式运算、GF(2n),S为域Zp上次数小于等于n-1的所有多项式组成。S中共有pn个不同的多项式。 定义合适运算，每个这样的S都是一个有限域。运算定义为： 运算遵循基本代数规则中的普通多项式运算规则 系数运算以p为模，即遵循有限域Zp上的运算规则。 多项式运算遵循模某个n次既约多项式m(x)的运算。 S即为一个pn阶有限域，在同构意义下，即为GF(pn).实际上，S=Zpx/(m(x).,2019/5/17,90,模多项式运算、GF(2n),P=2时，即为 GF(2n). 求其中的逆元 通过扩展的Euclidean求逆算法（与前面的GF(p)中求逆类似，将那里的整数换成Zp上的多项式）,2019/5/17,91,Example GF(23),2019/5/17,92,计算上的考虑,GF(2n)中的多项式系数都是0 or 1,所以任一多项式都可以由它的n个二进制系数唯一表示。所以GF(2n)中的每个多项式都可以表示成一个n位的二进制整数。 两个多项式加法等同于按位异或(XOR)运算。 乘法通过左移一位后按位异或来实现 重复取模运算来简约高次的多项式 (also shift & XOR),2019/5/17,93,布尔代数,代数系统(B;,)(这里和分别称并和交运算、称为求补运算)如果满足如下性质，称为一个布尔代数： 对于B中的任意元素x,y,z，有： (1) 交换律: x yy x，x yy x (2) 结台律: x (y z)(x y) z x (y z)(x y) z (3) 等幂律: x xx，x xx (4) 吸收律: x (x y)x，、x (x y)x,2019/5/17,94,(5) 分配律: x (y z)(x y) (x z) x (y z)(x y) (x z) (6) 同一律: x 0x,x 1x (7) 零一律: x 11，x 0o (8) 互补律: x (x)=1，x (x)o (9) 对合律: (x)x (10) 德摩根定律: (x y)(x) (y) (x y)(x) (y) 以上这10条性质并不都是独立的。事实上，所有其它的性质都可由其中的四条：交换律、分配律、同一律和互补律推导出来。,2019/5/17,95,如： 集合M的幂集2M关于集合的并集、交集、补集运算形成一个布尔代数。 有限布尔代数的基域的基数是2的幂。,2019/5/17,96,布尔函数,布尔表达式 布尔代数B上由x1,x2,xn产生的布尔表达式归纳地定义为 B的元素以及符号x1,x2,xn都是布尔表达式； 布尔表达式的并、交、补运算还是布尔表达式。 布尔函数 如果x1,x2,xn被解释为只能在B中取值的变量，则一个由x1,x2,xn产生的布尔表达式实际上就是一个从Bn到B的函数。,2019/5/17,97,由x1,x2,xn产生的布尔表达式有时也称为B上的一个n元布尔函数。 Bn到B的函数不一定是布尔函数，B2时，肯定有不是布尔函数的函数存在。 B=2时，Bn到B的函数都是布尔函数。 多重布尔函数： (f1,f2,fm): Bn Bn.Bn到Bm的函数。其中fi是Bn到B的布尔函数。,2019/5/17,98,GF(2)上布尔函数,GF(2)只有两个：0，1。关于这两个量之间的逻辑运算， GF(2)成为布尔代数。 这时，GF(2) n到GF(2)的一个映射就称为一个n元布尔函数(因为GF(2) 的基数为2)。 对于GF(2)中的元素，有 x yxy x yx+y+xy x=x+1 这里的+,分别表示GF(2)中的加(异或)、乘(与)运算。,2019/5/17,99,作为逻辑运算的函数，布尔函数是研究数字逻辑电路的重要数学工具，也是研究以此为基础的一切科学技术的重要工具，从而也是研究密码学和密码技术的重要工具。 无论在流密码还是在分组密码中，无论在私钥