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

1、信息安全导论第五讲密码学技术中的数学基础信息安全研究室Dr. Zuxi Wang2022/8/311密码学是研究密码系统或通信安全的一门学科，分为密码编码学和密码分析学。密码编码学是使得消息保密的学科，从事此行的称为密码编码者。密码分析学（密码破译学）是研究加密消息的破译的学科，从事此行的称为密码分析者。精于此道的人被称为密码学家，现代的密码学家通常是理论数学家。2022/8/312密码学是一门交叉学科，它很大程度上是应用数学学科。密码学中涉及数论、代数、概率论、组合数学、计算复杂理论等多种数学知识。还涉及信息论学科知识。密码学所涉及的知识十分广阔，这里仅介绍部分数学基本知识。2022/8/3

2、13数论基础素数同余、模运算中国剩余定理Euclean算法Fermat定理、Euler定理素性检验因子分解离散对数2022/8/314整除、素数记整数集合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且0r1被称为素数是指p的因子仅有1，-1，p，-p。否则，称为合数。2022/8/315整除基本性质a|a; b0，b | 0;If a|b,b|c,then a|c;if a|1, then a=1;if a|b, and b

3、|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|a2022/8/316互素与最大公约数最大公约数（最大公因子）：若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是互素的。2022/8/317最小公倍数最小公倍数a,b的倍数中最小者

4、称为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).2022/8/318带余除法带余除法：aZ, m0，可找出两个唯一确定的整数q和r使a=qm+r, 0rP2P3Pt是素数，其中i0整数。2022/8/3110目前没有可用于整数分解的有效算法。对于整数a,b(a,b2)，a,b的素数分解式分别为： ， ，其中ei，fi0,ti1，则有：2022/8/3111带余除法中，aZ，m0，a=qm+r， 0r1）分成一些两两不交的

5、等价类（剩余类）。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,112022/8/3113Modulo 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

6、 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 . 2022/8/31143、模运算：对于某个固定模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)

7、,于是223=(26)325=(26 26)26 25 900*(-30)*(32) mod(47) (7)* (-30)*(32) (mod47) 1(mod47) 于是有 47(223-1)2022/8/3115Modulo 8 Example2022/8/31164、定理：(消去律)对于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 定理：记最大公

8、因子(a,m)=d，则同余方程axb(mod m)有解的充分必要条件是db。当这个条件满足时，恰有d个模m同余类中的整数是上述方程的解。 证明：略。（从ax+my=b入手）2022/8/31176、整数环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中

9、的零因子。另一类是可逆元，即若zm，存在zm，使*=1，此时,互为各自的逆元，记-1=；-1=2022/8/3118定理：剩余类环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

10、)等等，这样一直进行下去，可得一系列关系式： rk-3=qk-1rk-2+rk-1,0rk-1rk-2; (k-1) rk-2=qkrk-1+rk,0rk 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+

11、t2b这样一直下去，最后得d=rk=s*a+t*b,s,tz.2022/8/3120例子：求(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*2522022/8/3121中国剩余定理例子：（孙子算经）今有物不知其数：三三数之余二；五五数之余三；七七数之余二。问物几何？答曰：二十三。232*7

12、0+3*21+2*15(mod 105)（口诀：三人同行七十稀，五树梅花廿一枝， 七子团圆月正半，除百零五便得知。）问，70，21，15如何得到的？原问题为：求解同余方程组2022/8/3122注意：若x0为上述同余方程组的解，则x0=x0+105*k(kz) 也为上述同余方程组的解。有意义的是，解题口诀提示我们先解下面三个特殊的同余方程组(1) (2) (3)的特殊解=?=?=?以方程（1）为对象，相当于解一个这样的同余方程 35y1(mod 3)，为什么呢？原因是，从（1）的模数及条件知，x应是35的倍数，于是可以假设x35y，有2022/8/312335y1(mod 3)相当于2y1(m

13、od 3) 解出y=2（mod3）于是x35*2(mod(3*35) 70(mod105)类似地得到（2）、（3）方程的模105的解21、15。于是有得2022/8/3124中国剩余定理：设自然数m1,m2,mr两两互素，并记M=m1m2mr，则同余方程组在模M同余的意义下有唯一解。2022/8/3125证明：考虑方程组，(1=i=r)由于诸mi(1=i1时，它的值(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)(

14、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.2022/8/3132若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/

15、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)2022/8/3133他们是模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时，(

16、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).2022/8/31344*.对于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)2022/8/3135素性检验、因子分解在许多加密算法中

17、，需要随机选择一个或多个非常大素数，因此必须确定一个给定的大数是否是素数。素性检验(测试)目前还没有简单有效的方法解决该问题。Miller和Rabin提出一种算法，其利用了Fermat定理。该算法产生的数不一定数素数，但令人惊讶的是，其产生的数几乎可以肯定是素数。2022/8/3136素性检验、因子分解RSA算法安全性以对大整数进行素数分解的困难性为基础，即无法在多项式时间内对于一个足够大的整数进行分解。一旦这个难题被破解，则RSA算法的安全性便不复存在。一些具代表性的因子分解算法包括：二次筛法p-1因子分解方法是更为有效的椭圆曲线方法的基础数域筛法等2022/8/3137强素数许多密码算法关

18、心强素数。设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进行因子分解也非常困难。2022/8/3138为了增加密码算法的安全性，建议使用长度大并且具有随机性结构的强素数，其中，素数的长度比其结构特点更为重要。但是，从因子算法对整数进行分解的概率的角度考虑，强素数与其他素数相比并没有明确

19、的优势。2022/8/3139代数基础群、环、域、布尔代数概述群、环、域基本概念有限域 GF(pn)多项式算术布尔代数与布尔函数2022/8/3140概 述有限群、有限域、布尔函数等在密码技术和应用中越来越重要。cryptographyAES, Elliptic Curve, IDEA, Public Key将从抽象代数的群、环、域的基本概念开始介绍。2022/8/3141群（Group）代数系统：一个集合以及定义在其上的一组运算一起构成一个代数系统。群（group）是一个代数系统 ，它仅有一个二元运算*（由于是代数系统，所以运算封闭性满足），并满足:结合律:(a*b)*c = a*(b*c)

20、 具有单位元e:e*a = a*e = a 每一元a 有逆元a-1:a*a-1 = e如果满足交换律: a*b = b*a 则形成一个交换群(commutative group),也叫阿贝尔群(abelian group).Remark:在不引起歧义下，经常将运算符号省略。 a*b=ab2022/8/3142 例1 和 不是群。 、和 都是群。例2 设有Z4=0,1,2,3，模4的加法运算 定义为则构成一个群。0 1 2 301230 1 2 31 2 3 02 3 0 13 0 1 2Examples:2022/8/3143Examples:是一个交换群，也叫加群。+是关于模m加法；，是关于

21、模m的乘法。当m是素数时，它构成一个乘法交换群；但当m不是素数时，它不构成群。2022/8/3144循环群（Cyclic Group）群元素的幂example: a3 = a*a*aak = 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生成的循环

22、群.2022/8/3145对任意负整数 ,按照群中逆元的表示方法例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)=12022/8/3146 例5 设G= a,b,c,e ，* 是G上的二元运算， *e a b ceabca e c bb c e ac b a ee a b c

23、 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四元群。2022/8/3147群的阶和元素的周期设是一个群，如果G是有限集，则称是有限群，G中元素的个数称为群的阶；若G是无限集，则称是无限群。设是一个群，a G，若存在正整数 r ，使得 ar =e，则称元素 a 具有有限周期。使ar=e成立的最小的正整数 r 称为 a 的周期。如果对于任何正整数r，均有 ar e，则称 a 的周期为无限。2022/8/3148群的阶和元素的周期Examples在群

24、中，单位元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，其周期均为无限，群是一个无限阶的循环群。2022/8/3149群的部分性质消去律：设是一个群，则对任意的a,b G，（1）存在唯一的元素xG，使a*x=b；（2）存在唯一的元素yG，使y*a=b。设是一个群，则对任意的a,b,cG（1）若a*b=a*c, 则

25、 b=c；（2）若b*a=c*a，则 b=c。2022/8/3150群的部分性质求逆:设是一个群，则对任意的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.群中任一元素与它的逆元具有相同的周期。在有限群中，每个元素均具有有限周期，且周期不超过群的阶。结论对无限群不成立。如群 . 2022/8/3151群的部分性质设是一由元素 g 生成的循环群，则若 g 的周期为 n ，则是一个阶为 n 的有限循环群；若 g 的周期为无限，则是一个无限

26、阶的循环群。2022/8/3152群的部分性质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)，是一个群。给出其单位元；各元素的逆元；各元素的周期。2022/8/3153设是一个群，若是的子代数，单位元e H，且对于任意的a H，有a-1 H，则称是的子群。的非空子集H关于G的运算*构成子群，必须满足：封闭性：H关于 * 封闭，a,bH，有a*b H;单位元：G的单位元eH;

27、可逆性：任意aH，有a-1H.Example:对于任意的整数m，若令Im= mi: i I. 则均构成的子群。子群（Subgroup）2022/8/3154若是的子群，则也是群。设是一个群，H是G的非空子集，若也是群，则称是的子群。（子群等价定义）设是群，H是G的非空子集，若(1)对于任意的a,bH，有a*bH；(2)对任意的aH，有a-1H，则是的子群。子群（Subgroup）2022/8/3155设是群，H是G的非空子集，若对于任意的a,bH，有a*b -1H，则是的子群。设是一有限群，若是的子代数，则是的子群。即：若对于任意的a,bH，有a*bH，则是的子群（H有限且关于运算封闭就构成子

28、群）。设是一个群，若是的有限子代数，则是的子群。子群（Subgroup）2022/8/3156子群（Subgroup）Examples设是一个群，a是G中任一元素，令H是a的所有整数次幂的集合，则H对于G的运算构成的子群。显然是由元素a生成的一个循环群。设是一个群，定义G的子集H=h:对任意x G,h*x=x*h，H对于运算*构成的子群。2022/8/3157陪集（coset）、正规子群（normal subgroup）H是G的子群，a属于G，aH=ah|h属于H称为G的一个关于H的左陪集（a所在的陪集）。同样Ha构成一个右陪集。对a，aH不一定等于Ha。如果对所以的a，都有aHHa，则称H为

29、G的一个正规子群。称aH或Ha为陪集。2022/8/3158拉格朗日(Lagrange)定理陪集定理：G的关于H的所有不用的左（右）陪集构成G的一个分划。Lagrange定理：群G必为其子群H及其全部不相同的陪集的直和。推论：有限群的阶必为其子群的阶的整数倍。素数阶群只有平庸子群（群自身与单位元）2022/8/3159群的同态与同构h:G1G2群间的一个映射，如果h保持群的运算，即：a,b of G，有h(ab)=h(a)h(b)，则称h为群G1,G2间的一个同态映射，简称同态(homomorphism)。若同态h同时是一个双射，那么称h为一个同构映射，简称同构(isomorphism) 。这

30、是称两群G1,G2是同构的。从代数结构的角度看，同构的群具有相同的代数结构，被视为同一群。2022/8/3160商群（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同构。2022/8/3161变换群（Transform group）集合A上的若干双射（一一映射）对于映射的复合运

31、算构成一个群，称其为A上的一个变换群。一个集合A的所有一一变换作成一个变换群。任何一个群都与一个变换群同构。2022/8/3162置换群（permutation group）有限集A到直身的一个双射称为A上的一个置换。A=n，称A上的置换为n阶置换。An，A上所有的n阶置换在置换乘积（映射复合操作）下构成一个群，称为n阶对称群(Symmetric group)，记为Sn。Sn的任一子群，都称为一个置换群。所有n阶偶置换（可分解为偶数个对换的乘积的置换）构成Sn的一个子群，叫交错群(Alternative group)，记为An。2022/8/3163置换群（permutation group）

32、对称群Sn的阶为n!，交错群An的阶为n!/2。凯莱(Caylay)定理：每一个有限群均同构于由群元素集合上的一个置换群（ Sn的一个子群） (gG，gf(g),f(g)为G上一个置换，f(g)： gi g gi ,全体f(g)构成G上的置换群)2022/8/3164群的生成元系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).群的生成元系通常不唯一。2

33、022/8/3165对称群的生成系对称群Sn的每个元都可以写成(12),(13),(1n)这n-1个对换（2-循环置换）中的若干个的乘积。S=(12),(13),(1n)是Sn的一个生成元系。Remark：Sn还有其他生成元系。2022/8/3166环（Ring）带两个运算（称加法和乘法）的集合满足:关于加法+构成一个abelian群，其单位元为0称为零元；关于乘法 满足:乘法封闭律；满足结合律； a(bc)=(ab)c对加法的分配律: a(b+c) = ab + ac则称为一个环（Ring）如果乘法是交换的，则称环为交换环( commutative ring)环中关于乘法如果有单位元，称之为

34、环的单位元。2022/8/3167子环、理想、剩余类环的子代数即为其子环。R的子集关于R的运算仍然是环，称为R的子环。R的子环I，如果同时关于乘法还满足：对R中任意元r，I中任意元a，有ar,ra均仍属于I.则称I为一个理想。R的理想I，关于加法构成的剩余类集合上关于模I的加法和乘法构成环，叫R的模I的剩余类环。记为R/I.2022/8/3168环的同态与同构环的同态与同构映射定义类似群的同态与同构。两个环之间的映射如果保持分别保持环的运算，就称为环的同态如果同态是一一映射，就称为同构。类似地有同态基本定理。2022/8/3169零因子、整环若ab=0,但a,b都不是R中的零元, 那么a(b)

35、均称为左(右)零因子.否则，称为非零因子.无零因子环: 如果R中的a, b有ab=o,那么必有a=0 or b=0.整环（domain）：交换的有单位元的无零因子环，称为一个整环。2022/8/3170Example:整数集关于普通的加法和乘法构成一个环且是一个整环.是一个交换环，称为模m的剩余类环。当m是合数时，剩余类环Zm中有零因子，Zm中的a，若(a,m)=1,则a有逆元；当m是素数时，剩余类环Zm是整环。2022/8/3171除环、域一个环关于其乘法不一定有单位元，另外其任一元也不一定有乘法逆元。如果一个环有单位元，并且任一非零元均有逆元，则称其为一个除环。所以是除环，它至少有一非零元

36、，且是加群；是群。一个除环，如果其关于乘法是交换的，则称其为一个域（Field）。2022/8/3172有限域（Galois Fields）有限域也叫Galois 域，在密码学中有重要作用。三个结论：每个有限域的阶必为素数的幂。对任意的素数p和正整数n，存在pn阶域。同阶的有限域必同构。于是：在同构意义下，pn阶的有限域有且只有一个，记为GF(pn).特别地，经常用到有限域:GF(p) 称为素域GF(2n)2022/8/3173Galois Fields GF(p)GF(p) 是 0,1, , p-1上关于模p加法、乘法构成的有限域。P为素数时，其中任意非零数都有逆元.2022/8/3174E

37、xample GF(7)2022/8/3175GF(p)中乘法逆元算法通过扩展Euclidean算法得到:EXTENDED EUCLID(m, b)1. (A1, A2, A3)=(1, 0, m); (B1, B2, B3)=(0, 1, b)2. if B3 = 0return A3 = gcd(m, b); （b mod m 没有逆）3. if B3 = 1 return B3 = gcd(m, b); B2 = b1 mod m4. Q = A3 div B3（A3除以B3的商）5. (T1, T2, T3)=(A1 Q B1, A2 Q B2, A3 Q B3)6. (A1, A2,

38、 A3)=(B1, B2, B3)7. (B1, B2, B3)=(T1, T2, T3)8. goto 2GF(pn)中乘法求逆类似（换成关于多项式的除法）2022/8/3176Inverse of 550 in GF(1759)2022/8/3177域上的多项式域F上的多项式为形如：的表达式，其中nN,aiF,i=1,2,n.若an0,称n为该多项式的次数,记n=deg(f(x),并称an为首项系数,首项系数为1的多项式称为首1多项式.2022/8/3178多项式整环记Fx为域上所有多项式f(x)构成的集合，则Fx关于通常的多项式加法+和乘法 形成一个整环，叫域F上的（一元）多项式环。0为

39、其零元，1为其单位元。在Fx上类似于整数环，关于多项式有商式、余式、整除、互素、最高公因式、最低公倍式等概念。2022/8/3179多项式带余除法带余除法：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)称为模多项式。2022/8/3180不可约多项式若存在q(x),b(x)，deg(q(x)1, deg(b(x)1，使a(x)=q(x)b(x)，则称a(x)为可

40、约多项式，否则称为不可约(既约)多项式。2022/8/3181多项式运算仅考虑一元多项式可把多项式运算分为三种：使用代数基本规则的普通多项式运算；系数运算是模p运算的多项式运算，即系数在Zp中；系数在Zp中，且多项式被定义为模一个多项式m(x)的多项式运算。2022/8/3182普通多项式运算加法、减法为(相同次项)对应系数的加减法乘法为逐项相乘。eglet f(x) = x3 + x2 + 2 and g(x) = x2 x + 1f(x) + g(x) = x3 + 2x2 x + 3f(x) g(x) = x3 + x + 1f(x) x g(x) = x5 + 3x2 2x + 220

41、22/8/3183系数 在Zp中的多项式运算在普通多项式运算中，所有系数都取modp运算。特别是 mod 2 的多项式运算ie all coefficients are 0 or 1eg. let f(x) = x3 + x2 and g(x) = x2 + x + 1f(x) + g(x) = x3 + x + 1f(x) x g(x) = x5 + x22022/8/3184模多项式运算基于多项式带余除法:f(x) = q(x) g(x) + r(x)r(x) 称为余式(remainder)记r(x) = f(x) mod g(x)定义模g(x)的多项式加法、乘法。如果没有余式，说g(x)

42、 整除 f(x)如果g(x)仅有它自己和1为其因式，说g(x)不可约(或既约)多项式(或素多项式)所有多项式在模不可约多项式加法乘法下构成一个域。2022/8/3185模p(x)的剩余类环Fx中一个多项式p(x)，(p(x)为由p(x)生成的Fx的子环，它是一个理想(主理想).Fx/(p(x)形成一个模p(x)的剩余类环。它等同于所有n-1次多项式集合上关于模p(x)加法乘法运算构成的环。当p(x)为不可约多项式时，其形成一个域。2022/8/3186最大公因式寻找多项式的最大公因式c(x) = GCD(a(x), b(x) 如果 c(x) 是同时整除 a(x), b(x) 的次数最高的多项式

43、。（等价定义）通过扩充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 22022/8/3187模多项式运算、GF(2n)有限域的元素个数必为pn，p为素数，n为正整数。p个元素上以模p运算产生一个域,Zp。但具有pn个元素的集合上模pn运算却不一定能产生域。如何定义合适运算，使之pn个元成域？Zpn关于模pn运算是不行的。2022/8/3188

44、模多项式运算、GF(2n)S为域Zp上次数小于等于n-1的所有多项式组成。S中共有pn个不同的多项式。定义合适运算，每个这样的S都是一个有限域。运算定义为：运算遵循基本代数规则中的普通多项式运算规则系数运算以p为模，即遵循有限域Zp上的运算规则。多项式运算遵循模某个n次既约多项式m(x)的运算。S即为一个pn阶有限域，在同构意义下，即为GF(pn).实际上，S=Zpx/(m(x).2022/8/3189模多项式运算、GF(2n)P=2时，即为 GF(2n). 求其中的逆元通过扩展的Euclidean求逆算法（与前面的GF(p)中求逆类似，将那里的整数换成Zp上的多项式）2022/8/3190E

45、xample GF(23)2022/8/3191计算上的考虑GF(2n)中的多项式系数都是0 or 1,所以任一多项式都可以由它的n个二进制系数唯一表示。所以GF(2n)中的每个多项式都可以表示成一个n位的二进制整数。两个多项式加法等同于按位异或(XOR)运算。乘法通过左移一位后按位异或来实现重复取模运算来简约高次的多项式 (also shift & XOR)2022/8/3192布尔代数代数系统(B;,)(这里和分别称并和交运算、称为求补运算)如果满足如下性质，称为一个布尔代数：对于B中的任意元素x,y,z，有：(1) 交换律: x yy x，x yy x(2) 结台律: x (y z)(x

46、 y) z x (y z)(x y) z(3) 等幂律: x xx，x xx(4) 吸收律: x (x y)x，、x (x y)x2022/8/3193(5) 分配律: x (y z)(x y) (x z) x (y z)(x y) (x z)(6) 同一律: x 0 x,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条性质并不都是独立的。事实上，所有其它的性质都可由其中的四条：交换律、分配律、同一律和互补律推导出来。2022/8/3194如

47、：集合M的幂集2M关于集合的并集、交集、补集运算形成一个布尔代数。有限布尔代数的基域的基数是2的幂。2022/8/3195布尔函数布尔表达式布尔代数B上由x1,x2,xn产生的布尔表达式归纳地定义为B的元素以及符号x1,x2,xn都是布尔表达式；布尔表达式的并、交、补运算还是布尔表达式。布尔函数如果x1,x2,xn被解释为只能在B中取值的变量，则一个由x1,x2,xn产生的布尔表达式实际上就是一个从Bn到B的函数。2022/8/3196由x1,x2,xn产生的布尔表达式有时也称为B上的一个n元布尔函数。Bn到B的函数不一定是布尔函数，B2时，肯定有不是布尔函数的函数存在。B=2时，Bn到B的函

48、数都是布尔函数。多重布尔函数：(f1,f2,fm): Bn Bn.Bn到Bm的函数。其中fi是Bn到B的布尔函数。2022/8/3197GF(2)上布尔函数GF(2)只有两个：0，1。关于这两个量之间的逻辑运算， GF(2)成为布尔代数。这时，GF(2) n到GF(2)的一个映射就称为一个n元布尔函数(因为GF(2) 的基数为2)。对于GF(2)中的元素，有x yxyx yx+y+xyx=x+1这里的+,分别表示GF(2)中的加(异或)、乘(与)运算。2022/8/3198作为逻辑运算的函数，布尔函数是研究数字逻辑电路的重要数学工具，也是研究以此为基础的一切科学技术的重要工具，从而也是研究密码

49、学和密码技术的重要工具。无论在流密码还是在分组密码中，无论在私钥还是在公钥密码中，布尔函数都有重要的应用。2022/8/3199布尔函数的表示为了方便布尔函数的理论和应用，人们在不同的情况下对布尔函数采用了不同的表示方法，主要有：真值表表示法小项表示法多项式表示法walsh谱表示法矩阵表示法等2022/8/31100布尔函数的研究问题布尔函数的表示布尔函数的研究方法布尔函数的设计实现布尔函数的性质满足一定性质的布尔函数的特征刻划、存在性、构造与计数布尔函数不同性质之间等价、相斥、相容、制约等关系密码学中，布尔函数的一条性质反映一种安全性能指标，当不同性能指标相互制约时，如何折衷以提高综合性能；

50、随着技术的发展和新的攻击方法的出现，新的性质的提出和研究 等等2022/8/31101本原根（本原元）由Euler定理有: a(n)=1 mod n, GCD(a,n)=1考虑更一般的表示形式 am=1 mod n, GCD(a,n)=1则至少有 m= (n)使之成立，但可能有更小的m存在一旦幂次到m, a的幂便出现周期循环如果最小的m= (n)，则a称为n的一个本原根(primitive root)如果n=p为素数，则a的连续的幂生成模p的剩余类群。2022/8/31102使 am=1 mod n 成立的最小正幂m (这里(a,n)=1)为下列之一a mod n的阶a 所属的模n的指数a 所

51、产生的周期长。Zp中的a，如果a的阶数(n)，在a就是n的一个本原根。如果a是n的本原根，则其幂a, a2, a(n)是(模n)各不相同的，且均与n互素。2022/8/31103特别的，对素数p，若a是p的本原根，则a, a2, ap-1是(模p)各不相同的。a是Zp的生成元。如：素数19的本原根为2,3,10,13,14,15.并不是所有的整数都有本原根。事实上，只有形为 2,4,pb,2pb的整数才有本原根，这里p任何奇素数，b正整数。2022/8/31104离散对数或指标求一个数模p的离散对数(discrete logarithm) 是求幂的逆问题即求x 使之满足ax = b mod p

52、 记x=loga b mod p or x=inda,p(b)以底a(模p)的b的指标。如果a是一个本原根，则x总存在,否则不一定。x = log3 4 mod 13 (x 使 3x = 4 mod 13)不存在而x = log2 3 mod 13 = 4（通过列出所以幂便知）2022/8/31105离散对数问题模指数运算被认为是一个单向函数，即：对于给定的整数n,a和x，容易通过“平方-乘”方法计算出ax mod n；但是，对于给定的整数n,a和b，由方程ax=b mod n求解整数x确是一个难题。有限域Zp上的离散对数问题是：对于给定的素数p，有限域Zp上的一个本原元a，Zp中的非零元b，

53、求解满足ax=b mod p的整数x(0 xp-2)，x=logab(mod p)(通常记为x=logab)。2022/8/31106离散对数计算目前还没有能够计算离散对数问题的多项式时间算法。对于已知的攻击方法，素数的选取应该满足至少两个条件：长度大于150位p-1至少有一个大的素数因子穷搜索方法可以对离散对数进行求解，但对于足够大的素数p并不可行，其所需计算时间和存储空间均为O(p).2022/8/31107离散对数计算有3个群的离散对数是密码设计人员最为关心的。这三个群分别是：素域GF(p)的乘法群特征为2的有限域GF(2n)上的乘法群有限域F上的椭圆曲线群EC(F)2022/8/311

54、08离散对数计算GF(p)上计算离散对数问题的算法有很多种。平凡算法：通过预计算所有可能的ax值并按有序对(x,ax)的第二个坐标排序。表明可以在O(1)时间内解决离散对数问题，所需预计算时间和存储空间均为O(p)。非平凡算法有多种：Pohlig-Hellman算法线性筛选法(Linear Sieve)数域筛选法(Number Field Sieve-NFS)2022/8/31109离散对数计算Shakes算法指数算法 等等算法等内容可以参考有关文献。2022/8/31110计算复杂性理论 （1）理论安全性（无条件安全性）:如果具有无限计算资源的密码分析者也无法破译该密码体制，这就是理论安全性

55、（无条件安全性），也称绝对不可破译，即是说密码分析者无论截获多少密文以及无论用什么方法进行攻击都不可能破译。（2）可证明安全性：如果从理论上证明破译该系统的代价（困难性）不低于求解某个已知的数学难题，这就是可证明安全性。（3）计算安全性：如果用用已知的最好算法和利用现有的（或密码系统生命期内）最大计算资源仍然不可能在合理的时间内完成破译该系统所要求的计算（量），这就是计算安全性。即密码分析者根据可以利用的资源进行破译所用的时间非常长，或者说破译的时间长到原来的明文失去保密价值。可证明安全性和计算安全性统称为实际安全性。 2022/8/31111 计算机复杂性理论是密码安全性理论的基础，它为分析不同密码技术和算法的“复杂性”提供了一种方法，它对不同的密码算法和技术进行比较，从而给出问题求解困难性的数量指标，并确定它们的安全性。 什么是计算机复杂性理论？（1）算法复杂性：密码分析所需的计算量则是密码体制安全性的生命指标。如果用n 表示问题