信息安全导论-5密码学数学基础省公开课一等奖全国示范课微课金奖课件

信息安全导论第五讲密码学技术中数学基础华中科技大学图象所信息安全研究室Dr.ZuxiWang2025/2/211第1页密码学是研究密码系统或通信安全一门学科，分为密码编码学和密码分析学。密码编码学是使得消息保密学科，从事此行称为密码编码者。密码分析学（密码破译学）是研究加密消息破译学科，从事此行称为密码分析者。精于此道人被称为密码学家，当代密码学家通常是理论数学家。2025/2/212第2页密码学是一门交叉学科，它很大程度上是应用数学学科。密码学中包括数论、代数、概率论、组合数学、计算复杂理论等各种数学知识。还包括信息论学科知识。密码学所包括知识十分辽阔，这里仅介绍部分数学基本知识。2025/2/213第3页数论基础素数同余、模运算中国剩下定理Euclean算法Fermat定理、Euler定理素性检验因子分解离散对数2025/2/214第4页整除、素数记整数集合Z={…,-3,-2,-1,0,1,2,3,…}整除设a,b∈Z，a≠0，假如存在m∈Z，使得b=ma，则称a整除b，以a|b表示，a是b一个因子或约数。假如没有任何m，使得b=ma，则称a不能整除b,记a†b，此时有a=mb+r且0<r<b。素数(质数)

整数p>1被称为素数是指p因子仅有1，-1，p，-p。不然，称为合数。2025/2/215第5页整除基本性质a|a;b≠0，b|0;Ifa|b,b|c,thena|c;ifa|1,thena=±1;ifa|b,andb|a,thena=±b;ifb|gandb|h,thenb|(mg+nh),foranyintegersmandn注意:ifa=0modn,thenn|a2025/2/216第6页互素与最大条约数最大条约数（最大公因子）：若a,b,c∈Z，假如c∣a，c∣b，称c是a和b条约数。正整数d称为a和b最大条约数(记d=gcd(a,b)或(a,b))

，假如它满足:d是a和b条约数。对a和b任何一个条约数c有c∣d。等价定义形式是：

gcd(a,b)=max{k:k∣a，k∣b}若gcd(a,b)=1，称a与b是互素。2025/2/217第7页最小公倍数最小公倍数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).2025/2/218第8页带余除法带余除法：

a∈Z,m>0，可找出两个唯一确定整数q和r使a=qm+r,0≤r<m。(若r=0则m∣a）

q和r这两个数分别称为以m去除a所得到商数和余数.记：q=adivm或[a/m],r=amodm。存在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))=12025/2/219第9页算术基本定理下面关于素数事实均成立假如p是一个素数，而且p|ab，则有p|a或p|b；素数有没有穷多个；素数定理:记π(x)为小于x素数个数，则有它表明，对于充分大x，能够用xlnx近似地表示π(x)。算术基本定理：任何一个不等于0正整数a都能够写成唯一表示式，这里P1>P2>P3…>Pt是素数，其中αi>0整数。2025/2/2110第10页当前没有可用于整数分解有效算法。对于整数a,b(a,b≥2)，a,b素数分解式分别为：

，，其中ei，fi≥0,t≥i≥1，则有：2025/2/2111第11页带余除法中，a∈Z，m>0，a=qm+r，0≤r<m，r为a除以m余数或剩下(Residue)，m称为模数，所以称r为a模正整数m剩下，记r≡amodmm∣(a-b)

a=q1m+r,b=q2m+r。即a和b分别除以m有相同余数同余称整数a模正整数m同余(数)于整数b，并写a≡b（modm）是指m∣(a－b),m称为模数。note:ifa=0modm,thenm|a整数同余式和同余方程2025/2/2112第12页1、模关系：相对于某个固定模数m同余关系，是指整数间一个等价关系。含有等价关系三点基本性质：

自反性：对任意整数a，有a≡a（modm）

对称性：若a≡b(modm)，则b≡a（modm）

传递性：若a≡b(modm),b≡c(modm),则a≡c(modm)全体整数集合Z可按模m（m>1）分成一些两两不交等价类（剩下类）。2、整数模m同余类共有m个，他们分别为mk+0,mk+1,mk+2,…mk+(m-1);k∈z，每一个算一类，每一类都能够选一个代表元，普通选这一类中最小非负整数。于是称[0],[1],[2],…[m-1]为标准完全剩下系。其中与m互素剩下类组成模m简约剩下系。Z模12标准完全剩下系为：[0],[1],[2],[3],[4],[5],[6],[7],[8],[9],[10],[11]2025/2/2113第13页Modulo7Example...-21-20-19-18-17-16-15-14-13-12-11-10-9-8-7-6-5-4-3-2-10123456

78910111213141516171819202122232425262728293031323334...2025/2/2114第14页3、模运算：对于某个固定模m同余式能够象普通等式那样相加相减和相乘：a(modm)±b(modm)=(a±b)(modm)a(modm)*b(modm)=a*b(modm)例：由同余式演算证实560－1是56倍数，223－1是47倍数。解： 注意53=125≡13(mod56)

于是有56≡169≡1(mod56)

对同余式两边同时升到10次幂， 即有56∣(560-1)。 其次,注意26=64≡-30(mod47),于是223=(26)3·25=(26·26)26·25

≡900*(-30)*(32)mod(47)≡(7)*(-30)*(32)(mod47)≡1(mod47)

于是有47∣(223-1)2025/2/2115第15页Modulo8Example2025/2/2116第16页4、定理：(消去律)对于ab≡ac(modm)来说，若最大公因子gcd(a,m)＝1（即a与m是互素），则b≡c(modm)加法消去律：

a+b≡a+c(modm)，有b≡c(modm).5、一次同余方程ax≡b(modm)，这个方程有没有解，相当于问有没有那样一个整数x，使得对于某个整数y来说，有ax+my=b

定理：记最大公因子(a,m)=d，则同余方程ax≡b(modm)有解充分必要条件是d∣b。当这个条件满足时，恰有d个模m同余类中整数是上述方程解。证实：略。（从ax+my=b入手）2025/2/2117第17页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=α2025/2/2118第18页定理：剩下类环zm中元素α=[a]为zm可逆元

最大条约数(a,m)=1要证实这个定理，只需证实以下引理：引理：任意两个整数a和b都有一个最大条约数，这么一个最大条约数d能够表示成a,b二数关于整系数线性组合，即有s,t∈z，使d＝sa＋tb。证实：不妨设b>0，用辗转相除法，先用b去除a，得

a=q1b+r1,0≤r1<b; (1)假如r1=0，停顿，不然再用r1去除b，得

b=q2r1+r2,0≤r2<r1; (2)假如r2=0，停顿，不然再用r2去除r1，得

r1=q3r2+r3;0≤r3<r2; (3)等等，这么一直进行下去，可得一系列关系式：

rk-3=qk-1rk-2+rk-1,0≤rk-1<rk-2; (k-1) rk-2=qkrk-1+rk,0≤rk<rk-1; (k)2025/2/2119第19页因为历次所得余数

r1>r2>r3>r4>…rk>…≥0是严格递降一串非负整数，故最终总会出现余数为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,t∈z.2025/2/2120第20页例子：求(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*2522025/2/2121第21页中国剩下定理例子：（孙子算经）今有物不知其数：三三数之余二；五五数之余三；七七数之余二。问物几何？答曰：二十三。23≡2*70+3*21+2*15(mod105)（口诀：三人同行七十稀，五树梅花廿一枝，

七子团圆月正半，除百零五便得知。）问，70，21，15怎样得到？原问题为：求解同余方程组2025/2/2122第22页注意：若x0为上述同余方程组解，则x0

=x0+105*k(k∈z)也为上述同余方程组解。有意义是，解题口诀提醒我们先解下面三个特殊同余方程组(1) (2) (3) 特殊解 =? =? =?以方程（1）为对象，相当于解一个这么同余方程35y≡1(mod3)，为何呢？原因是，从（1）模数及条件知，x应是35倍数，于是能够假设x＝35y，有2025/2/2123第23页35y≡1(mod3)相当于2y≡1(mod3)

解出y=2（mod3）

于是x35*2(mod(3*35))70(mod105)类似地得到（2）、（3）方程模105解21、15。

于是有

得

2025/2/2124第24页中国剩下定理：设自然数m1,m2,…mr两两互素，并记M=m1m2…mr，则同余方程组在模M同余意义下有唯一解。2025/2/2125第25页证实：考虑方程组，

(1<=i<=r)

因为诸mi(1<=i<=r)两两互素，这个方程组作变量替换，令x=(M/mi)*y，方程组等价于解同余方程： (M/mi)y≡1(modmi)2025/2/2126第26页若得到特解yi,只要令

xi=(M/mi)yi则方程组解为

x0=b1x1+b2x2+…+brxr(modM)模N意义下唯一。中国剩下定理用途之一是，它给出了一个方法，使非常大数对M模运算转化到更小数上来进行运算，当M为150位或150位以上时，这种方法非常有效。2025/2/2127第27页Euclidean算法依据(a,b)=(b,amodb)辗转除法是求解两个整数最大公因子传统方法，由此而得欧几里得算法是一个用于计算两个整数最大公因子有效算法。Euclidean算法：输入a和b，wherea,b∈z,a,b≥0,a≥b.假如b≠0，则依次完成:r←amodb,a←b,b←r,不然返回a.输出gcd(a,b)=r.2025/2/2128第28页ExampleGCD(1970,1066)1970=1x1066+904 gcd(1066,904)1066=1x904+162 gcd(904,162)904=5x162+94 gcd(162,94)162=1x94+68 gcd(94,68)94=1x68+26 gcd(68,26)68=2x26+16 gcd(26,16)26=1x16+10 gcd(16,10)16=1x10+6 gcd(10,6)10=1x6+4 gcd(6,4)6=1x4+2 gcd(4,2)4=2x2+0 gcd(2,0)2025/2/2129第29页扩展Euclidean算法经扩张Euclidean算法不但能够被用于计算d=gcd(a,b)，而且能够找到满足等式ax+by=d整数x和y。扩展Euclidean算法：输入a和b，wherea,b∈z,a,b≥0,a≥b.假如b=0，则:d←a,x←1,y←0,返回(d,x,y).x2←1,x1←0,y2←0,y1←1假如b≠0，则依次完成:q←[a/b],r←a-qb,x←x2-qx1,y←y2-qy1;a←b,b←r,x2←x1,y2←y1,x1←x,y1←yd←a,x←x2,y←y2，返回(d,x,y).Euclidean算法和扩展Euclidean算法时间复杂度为O((lgn)2).2025/2/2130第30页Fermat定理和Euler定理Fermat定理：假如p是素数而且a是正整数,(p,a)=1那么，ap-1≡1(modp)

证实：设z*p≡{α∈zp∣(α,p)=1}

易见，z*p={1,2,3,…,(p-1)}且因为（a,p）＝1知

az*p={[a],[2a],[3a],…,[(p-1)a]}=z*p，原因是az*p内元素两两不一样。他们刚好为1,2,3…,(p－1)一个排列。所以

[a]*[2a]*[3a]*…[(p-1)a]≡1*2*3*…(p-1)(modp)

由（(p－1)！，p）＝1，

所以ap-1≡1(modp)推论：对素数p，任意正整数a，有ap≡a(modp).usefulinpublickeyandprimalitytesting2025/2/2131第31页Euler函数φEuler函数φ(n)是这么来定义：

当n＝1时,φ(1)＝1；当n>1时，它值φ(n)等于比n小而与n互素正整数个数。以n＝24为例，比24小而与24互素正整数为：1,5,7,11,13,17,19,23。所以，我们有φ(24)＝8。若p为素数，则φ(p)＝p-1。若p，q都为素数且p≠q，此时有

φ(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，于是若设n＝pq，有φ(n)=pq-[(q-1)+(p-1)+1]=(p-1)(q-1)=φ(p)φ(q).例：φ(21)=φ(3*7)=φ(3)φ(7)=2*6=12.2025/2/2132第32页若m1,m2互素，则φ(m1m2)＝φ(m1)φ(m2).设n=p1e1p2e2…prer，其中p1,p2,…,pr为互异素数，则φ(n)=p1e1-1p2e2-1…prer-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(modn)。证实：设小于n而和n互素φ(n)个正整数为

r1,r2,r3…,rφ(n) (1)2025/2/2133第33页他们是模n两两互不一样余。对每一个定数i来说，因为a和ri都与n互素，所以(ari,n)=1，所以ari同余于（1）中某个ri’即

ari≡ri’(modn)，1≤i≤φ(n)而且当i≠j时有ari

/≡arj(modn).于是,为

置换.所以有由(ri,n)=1,所以

Remarks：1*.n＝p时，(a,p)=1,有ap-1≡1(modp)为Fermat定理！而对任意a，有ap≡a(modp)（Fermat）2*.易见aφ(n)+1≡a(modn)3*.若n=pq，p与q为相异素数，取0<m<n，若(m,n)=1，有mφ(n)+1≡m(modn)，也即m(p-1)(q-1)+1≡m(modn).2025/2/2134第34页4*.对于3中，若(m,n)＝p或q，也一样有mφ(n)+1≡m(modn)5*.由(mφ(n))k≡1k(modn)知

mkφ(n)≡1(modn)，深入

mkφ(n)+1≡m(modn) mk(p-1)(q-1)+1≡m(modn)2025/2/2135第35页素性检验、因子分解在许多加密算法中，需要随机选择一个或多个非常大素数，所以必须确定一个给定大数是否是素数。－－素性检验(测试)当前还没有简单有效方法处理该问题。Miller和Rabin提出一个算法，其利用了Fermat定理。该算法产生数不一定数素数，但令人诧异是，其产生数几乎能够必定是素数。2025/2/2136第36页素性检验、因子分解RSA算法安全性以对大整数进行素数分解困难性为基础，即无法在多项式时间内对于一个足够大整数进行分解。一旦这个难题被破解，则RSA算法安全性便不复存在。一些具代表性因子分解算法包含：二次筛法p-1因子分解方法是更为有效椭圆曲线方法基础数域筛法等2025/2/2137第37页强素数许多密码算法关心强素数。设n∈Z，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进行因子分解也非常困难。2025/2/2138第38页为了增加密码算法安全性，提议使用长度大而且含有随机性结构强素数，其中，素数长度比其结构特点更为主要。不过，从因子算法对整数进行分解概率角度考虑，强素数与其它素数相比并没有明确优势。2025/2/2139第39页代数基础－－群、环、域、布尔代数概述群、环、域基本概念有限域

GF(pn)多项式算术布尔代数与布尔函数2025/2/2140第40页概述有限群、有限域、布尔函数等在密码技术和应用中越来越主要。cryptographyAES,EllipticCurve,IDEA,PublicKey将从抽象代数群、环、域基本概念开始介绍。2025/2/2141第41页群（Group）代数系统：一个集合以及定义在其上一组运算一起组成一个代数系统。群（group）是一个代数系统<G；*>，它仅有一个二元运算*（因为是代数系统，所以运算封闭性满足），并满足:结合律: (a*b)*c=a*(b*c)

含有单位元e: e*a=a*e=a

每一元a有逆元a-1: a*a-1=e假如满足交换律:a*b=b*a

则形成一个交换群(commutativegroup),也叫阿贝尔群(abeliangroup).Remark:在不引发歧义下，经常将运算符号省略。a*b=ab2025/2/2142第42页

例1<N；+><Z；+><I；·>和<R；·>不是群。

<I；+>、<R；+>和<R-｛0｝；·>都是群。例2设有Z4=｛0,1,2,3｝，模4加法运算定义为则<Z4;>组成一个群。

012301230123123023013012Examples:2025/2/2143第43页Examples:<Zm,+>是一个交换群，也叫加群。+是关于模m加法；<Zm-{0},·>，·是关于模m乘法。当m是素数时，它组成一个乘法交换群；但当m不是素数时，它不组成群。2025/2/2144第44页循环群（CyclicGroup）群元素幂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>.称为由g生成循环群.2025/2/2145第45页对任意负整数,按照群中逆元表示方法例3

群<I；+>是循环群，1是生成元，10=0，对任意正整数n，n=1+1+…+1，按照群中元素幂表示方法n=1n.

例4

例2中群<Z4；

4>是循环群，1是其生成元，3也是其生成元。因为10=0，11=1，12=1

41=res4(2)=2,13=12

41=2

41=res4(3)=3又30=0，31=3，32=3

43=res4(6)=2,33=32

43=2

43=res4(5)=12025/2/2146第46页

例5

设G={a,b,c,e}，*是G上二元运算，

*eabceabcaecbbceacbaeeabc

a*a=b*b=c*c=e*e=e,a*b=b*a=c,b*c=c*b=a，a*c=c*a=b<G；*>是一阿贝尔群，但它不是循环群，普通称这个群为Klein四元群。2025/2/2147第47页群阶和元素周期设<G；*>是一个群，假如G是有限集，则称<G；*>是有限群，G中元素个数称为群<G；*>阶；若G是无限集，则称<G；*>是无限群。设<G;*>是一个群，a∈G，若存在正整数r，使得ar=e，则称元素a含有有限周期。使ar=e成立最小正整数r称为a周期。假如对于任何正整数r，都有ar≠

e，则称a周期为无限。2025/2/2148第48页群阶和元素周期Examples在群<R-{0};·>中，单位元1周期为1,-1周期为2.（-1）2=（-1）4=（-1）6=…=1群<Z4；

4>中，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，循环群<Z4；

4>阶也为4。循环群<I；+>生成元1和–1，其周期均为无限，群<I；+>是一个无限阶循环群。2025/2/2149第49页群部分性质消去律：设<G;*>是一个群，则对任意a,b∈G，（1）存在唯一元素x∈G，使a*x=b；（2）存在唯一元素y∈G，使y*a=b。设<G;*>是一个群，则对任意a,b,c∈G（1）若a*b=a*c,则b=c；（2）若b*a=c*a，则b=c。2025/2/2150第50页群部分性质求逆:设<G;*>是一个群，则对任意a,b,a1,a2,…,ak∈G(a*b)-1=b-1*a-1;(a1*a2*…*ak)-1=ak-1*…*a2-1*a1-1.关于元素周期:群<G;*>中元素

a若含有有限周期r，则当且仅当k

是r整数倍时，ak

=e.群中任一元素与它逆元含有相同周期。在有限群<G;*>中，每个元素均含有有限周期，且周期不超出群<G;*>阶。结论对无限群不成立。如群<I；+>.

2025/2/2151第51页群部分性质设<G;*>是一由元素g生成循环群，则若g周期为n，则<G;*>是一个阶为n有限循环群；若g周期为无限，则<G;*>是一个无限阶循环群。2025/2/2152第52页群部分性质Examples群<Z4；

4>中单位元0周期是1；1和3周期均为4；2周期为2，群<Z4；

4>阶4.设<G;*>是一个群，且对于任意a,b∈G，有(a*b)2=a2

*b2,则<G;*>是阿贝尔群。设Z6={0,1,2,3,4,5},

6是模6加法，定义为：a

6b=res6(a+b)，<Z6;6>是一个群。给出其单位元；各元素逆元；各元素周期。2025/2/2153第53页设<G;*>是一个群，若<H;*>是<G;*>子代数，单位元e∈H，且对于任意a∈H，有a-1∈H，则称<H;*>是<G;*>子群。<G;*>非空子集H关于G运算*组成子群，必须满足：封闭性：H关于

*

封闭，a,b∈H，有a*b∈H;单位元：G单位元e∈H;可逆性：任意a∈H，有a-1∈H.Example:对于任意整数m，若令Im={mi:i

∈I}.则<Im;+>均组成<I；+>子群。子群（Subgroup）2025/2/2154第54页若<H;*>是<G;*>子群，则<H;*>也是群。设<G;*>是一个群，H是G非空子集，若<H;*>也是群，则称<H;*>是<G;*>子群。（子群等价定义）设<G;*>是群，H是G非空子集，若(1)对于任意a,b∈H，有a*b∈H；(2)对任意a∈H，有a-1∈H，则<H;*>是<G;*>子群。子群（Subgroup）2025/2/2155第55页设<G;*>是群，H是G非空子集，若对于任意a,b∈H，有a*b-1∈H，则<H;*>是<G;*>子群。设<G;*>是一有限群，若<H;*>是<G;*>子代数，则<H;*>是<G;*>子群。即：若对于任意a,b∈H，有a*b∈H，则<H;*>是<G;*>子群（H有限且关于运算封闭就组成子群）。设<G;*>是一个群，若<H;*>是<G;*>有限子代数，则<H;*>是<G;*>子群。子群（Subgroup）2025/2/2156第56页子群（Subgroup）Examples设<G;*>是一个群，a是G中任一元素，令H是a全部整数次幂集合，则H对于G运算组成<G;*>子群。显然<H;*>是由元素a生成一个循环群。设<G;*>是一个群，定义G子集H={h:对任意x∈G,h*x=x*h}，H对于运算*组成<G;*>子群。2025/2/2157第57页陪集（coset）、正规子群（normalsubgroup）H是G子群，a属于G，aH={ah|h属于H}称为G一个关于H左陪集（a所在陪集）。一样Ha组成一个右陪集。对a，aH不一定等于Ha。假如对所以a，都有aH＝Ha，则称H为G一个正规子群。称aH或Ha为陪集。2025/2/2158第58页拉格朗日(Lagrange)定理陪集定理：G关于H全部不用左（右）陪集组成G一个分划。Lagrange定理：群G必为其子群H及其全部不相同陪集直和。推论：有限群阶必为其子群阶整数倍。素数阶群只有平庸子群（群本身与单位元）2025/2/2159第59页群同态与同构h:G1→G2群间一个映射，假如h保持群运算，即：a,bofG，有h(ab)=h(a)h(b)，则称h为群G1,G2间一个同态映射，简称同态(homomorphism)。若同态h同时是一个双射，那么称h为一个同构映射，简称同构(isomorphism)

。这是称两群G1,G2是同构。从代数结构角度看，同构群含有相同代数结构，被视为同一群。2025/2/2160第60页商群（Quotientgroup）群G正规子群H与其全部不相同陪集在陪集乘法意义下组成一个群，称为G关于H商群，记为G/H。f:G→G’群间一个同态映射，kerf＝{g:f(g)=e’,e’为G’单位元}，即kerf为G’单位元e’在G中原象集合。称kerf为同态映射f核。同态基本定理：设G’为G关于同态映射f象，则有：1.kerf是G正规子群；2.G’与商群G/kerf同构。2025/2/2161第61页变换群（Transformgroup）集合A上若干双射（一一映射）对于映射复合运算组成一个群，称其为A上一个变换群。一个集合A全部一一变换作成一个变换群。任何一个群都与一个变换群同构。2025/2/2162第62页置换群（permutationgroup）有限集A到直身一个双射称为A上一个置换。＃A=n，称A上置换为n阶置换。＃A＝n，A上全部n阶置换在置换乘积（映射复合操作）下组成一个群，称为n阶对称群(Symmetricgroup)，记为Sn。Sn任一子群，都称为一个置换群。全部n阶偶置换（可分解为偶数个对换乘积置换）组成Sn一个子群，叫交织群(Alternativegroup)，记为An。2025/2/2163第63页置换群（permutationgroup）对称群Sn阶为n!，交织群An阶为n!/2。凯莱(Caylay)定理：每一个有限群均同构于由群元素集合上一个置换群（Sn一个子群）(

gG，gf(g),f(g)为G上一个置换，f(g)：gig

gi,全体f(g)组成G上置换群)2025/2/2164第64页群生成元系G是一个群，S是G一个非空子集S生成子群H:G包含S最小子群,记H＝(S)。S生成子群H由S中元素及逆元任意乘积组成。假如G=(S)，那么称S为群G一个生成元系(Generatorsystemorgeneratorset)。当＃S＝1，S＝{a}，那么S生成G一个循环子群，(S)＝<a>.群生成元系通常不唯一。2025/2/2165第65页对称群生成系对称群Sn每个元都能够写成(12),(13),…,(1n)这n-1个对换（2-循环置换）中若干个乘积。S={(12),(13),…,(1n)}是Sn一个生成元系。Remark：Sn还有其它生成元系。2025/2/2166第66页环（Ring）带两个运算（称加法和乘法）集合<R,+,·>满足:关于加法+组成一个abelian群<R,+>，其单位元为‘0’称为零元；关于乘法·满足:乘法封闭律；满足结合律；a(bc)=(ab)c对加法分配律:a(b+c)=ab+ac则称<R,+,·>为一个环（Ring）假如乘法是交换，则称环为交换环(commutativering)环中关于乘法假如有单位元，称之为环单位元。2025/2/2167第67页子环、理想、剩下类环<R,+,·>子代数即为其子环。R子集关于R运算依然是环，称为R子环。R子环I，假如同时关于乘法还满足：对R中任意元r，I中任意元a，有ar,ra均仍属于I.则称I为一个理想。R理想I，关于加法组成剩下类集合上关于模I加法和乘法组成环，叫R模I剩下类环。记为R/I.2025/2/2168第68页环同态与同构环同态与同构映射定义类似群同态与同构。两个环之间映射假如保持分别保持环运算，就称为环同态假如同态是一一映射，就称为同构。类似地有同态基本定理。2025/2/2169第69页零因子、整环若ab=0,但a,b都不是R中零元,

那么a(b)均称为左(右)零因子.不然，称为非零因子.无零因子环:假如R中a,b有ab=o,那么必有a=0orb=0.整环（domain）：交换有单位元无零因子环，称为一个整环。2025/2/2170第70页Example:整数集关于普通加法和乘法组成一个环且是一个整环.<Zm,+,·>是一个交换环，称为模m剩下类环。当m是合数时，剩下类环Zm中有零因子，Zm中a，若(a,m)=1,则a有逆元；当m是素数时，剩下类环Zm是整环。2025/2/2171第71页除环、域一个环关于其乘法不一定有单位元，另外其任一元也不一定有乘法逆元。假如一个环有单位元，而且任一非零元都有逆元，则称其为一个除环。所以<R,+,·>是除环，它最少有一非零元，且<R,+>是加群；<R-{0},·>是群。一个除环，假如其关于乘法是交换，则称其为一个域（Field）。2025/2/2172第72页有限域（GaloisFields）有限域也叫Galois域，在密码学中有主要作用。三个结论：每个有限域阶必为素数幂。对任意素数p和正整数n，存在pn阶域。同阶有限域必同构。于是：在同构意义下，pn阶有限域有且只有一个，记为GF(pn).尤其地，经惯用到有限域:GF(p)－－称为素域GF(2n)2025/2/2173第73页GaloisFieldsGF(p)GF(p)是{0,1,…,p-1}上关于模p加法、乘法组成有限域。P为素数时，其中任意非零数都有逆元.2025/2/2174第74页ExampleGF(7)2025/2/2175第75页GF(p)中乘法逆元算法经过扩展Euclidean算法得到:EXTENDEDEUCLID(m,b)1.(A1,A2,A3)=(1,0,m); (B1,B2,B3)=(0,1,b)2.ifB3=0 returnA3=gcd(m,b);（bmodm没有逆）3.ifB3=1 returnB3=gcd(m,b);B2=b–1modm4.Q=A3divB3（A3除以B3商）5.(T1,T2,T3)=(A1–QB1,A2–QB2,A3–QB3)6.(A1,A2,A3)=(B1,B2,B3)7.(B1,B2,B3)=(T1,T2,T3)8.goto2GF(pn)中乘法求逆类似（换成关于多项式除法）2025/2/2176第76页Inverseof550inGF(1759)2025/2/2177第77页域上多项式域F上多项式为形如：表示式，其中n∈N,ai∈F,i=1,2,…,n.若an≠0,称n为该多项式次数,记n=deg(f(x)),并称an为首项系数,首项系数为1多项式称为首1多项式.2025/2/2178第78页多项式整环记F[x]为域上全部多项式f(x)组成集合，则F[x]关于通常多项式加法+和乘法·形成一个整环，叫域F上（一元）多项式环。0为其零元，1为其单位元。在F[x]上类似于整数环，关于多项式有商式、余式、整除、互素、最高公因式、最低公倍式等概念。2025/2/2179第79页多项式带余除法带余除法：a(x),b(x)∈F[x],且b(x)≠0,则存在唯一q(x),r(x)∈F[x],使a(x)=q(x)b(x)+r(x),式中deg(r(x))≤deg(b(x)).q(x)称为商式,r(x)称为余式也用a(x)modp(x)

表示a(x)除以p(x)余式.称为a(x)模p(x)，p(x)称为模多项式。2025/2/2180第80页不可约多项式若存在q(x),b(x)，deg(q(x))≥1,deg(b(x))≥1，使a(x)=q(x)b(x)，则称a(x)为可约多项式，不然称为不可约(既约)多项式。2025/2/2181第81页多项式运算仅考虑一元多项式可把多项式运算分为三种：使用代数基本规则普通多项式运算；系数运算是模p运算多项式运算，即系数在Zp中；系数在Zp中，且多项式被定义为模一个多项式m(x)多项式运算。2025/2/2182第82页普通多项式运算加法、减法为(相同次项)对应系数加减法乘法为逐项相乘。egletf(x)=x3+x2+2andg(x)=x2–x+1f(x)+g(x)=x3+2x2–x+3f(x)–g(x)=x3+x+1f(x)xg(x)=x5+3x2–2x+22025/2/2183第83页系数在Zp中多项式运算在普通多项式运算中，全部系数都取modp运算。尤其是mod2多项式运算ieallcoefficientsare0or1eg.letf(x)=x3+x2andg(x)=x2+x+1f(x)+g(x)=x3+x+1f(x)xg(x)=x5+x22025/2/2184第84页模多项式运算基于多项式带余除法:f(x)=q(x)g(x)+r(x)r(x)称为余式(remainder)记r(x)=f(x)modg(x)定义模g(x)多项式加法、乘法。假如没有余式，说g(x)整除

f(x)假如g(x)仅有它自己和1为其因式，说g(x)不可约(或既约)多项式(或素多项式)全部多项式在模不可约多项式加法乘法下组成一个域。2025/2/2185第85页模p(x)剩下类环F[x]中一个多项式p(x)，(p(x))为由p(x)生成F[x]子环，它是一个理想(主理想).F[x]/(p(x))形成一个模p(x)剩下类环。它等同于全部n-1次多项式集合上关于模p(x)加法乘法运算组成环。当p(x)为不可约多项式时，其形成一个域。2025/2/2186第86页最大公因式寻找多项式最大公因式c(x)=GCD(a(x),b(x))假如c(x)

是同时整除a(x),b(x)

次数最高多项式。（等价定义）经过扩充Euclidean算法来寻找:EUCLID[a(x),b(x)]1.A(x)←a(x);B(x)←b(x)2.ifB(x)=0returnA(x)=gcd[a(x),b(x)]3.R(x)=A(x)modB(x)4.A(x)←B(x)5.B(x)←R(x)6.goto22025/2/2187第87页模多项式运算、GF(2n)有限域元素个数必为pn，p为素数，n为正整数。p个元素上以模p运算产生一个域,Zp。但含有pn个元素集合上模pn运算却不一定能产生域。怎样定义适当运算，使之pn个元成域？Zpn关于模pn运算是不行。2025/2/2188第88页模多项式运算、GF(2n)S为域Zp上次数小于等于n-1全部多项式组成。S中共有pn个不一样多项式。定义适当运算，每个这么S都是一个有限域。运算定义为：运算遵照基本代数规则中普通多项式运算规则系数运算以p为模，即遵照有限域Zp上运算规则。多项式运算遵照模某个n次既约多项式m(x)运算。S即为一个pn阶有限域，在同构意义下，即为GF(pn).实际上，S=Zp[x]/(m(x)).2025/2/2189第89页模多项式运算、GF(2n)P=2时，即为GF(2n).求其中逆元经过扩展Euclidean求逆算法（与前面GF(p)中求逆类似，将那里整数换成Zp上多项式）2025/2/2190第90页ExampleGF(23)2025/2/2191第91页计算上考虑GF(2n)中多项式系数都是0or1,所以任一多项式都能够由它n个二进制系数唯一表示。所以GF(2n)中每个多项式都能够表示成一个n位二进制整数。两个多项式加法等同于按位异或(XOR)运算。乘法经过左移一位后按位异或来实现重复取模运算来简约高次多项式(alsoshift&XOR)2025/2/2192第92页布尔代数代数系统(B;－,,)(这里

和

分别称并和交运算、－称为求补运算)假如满足以下性质，称为一个布尔代数：对于B中任意元素x,y,z，有：(1)交换律:x

y＝y

x，x

y＝y

x(2)结台律:x

(y

z)＝(x

y)

zx

(y

z)＝(x

y)

z(3)等幂律:x

x＝x，x

x＝x(4)吸收律:x

(x

y)＝x，、x

(x

y)＝x2025/2/2193第93页(5)分配律:x

(y

z)＝(x

y)

(x

z)x

(y

z)＝(x

y)

(x

z)(6)同一律:x

0＝x,x

1＝x(7)零一律:x

1＝1，x

0＝o(8)互补律:x

(－x)=1，x

(－x)＝o(9)对合律:－(－x)＝x(10)德·摩根定律:－(x

y)＝(－x)(－y)－(x

y)＝(－x)(－y)以上这10条性质并不都是独立。实际上，全部其它性质都可由其中四条：交换律、分配律、同一律和互补律推导出来。2025/2/2194第94页如：集合M幂集2M关于集合并集、交集、补集运算形成一个布尔代数。有限布尔代数基域基数是2幂。2025/2/2195第95页布尔函数布尔表示式布尔代数B上由x1,x2,…,xn产生布尔表示式归纳地定义为B元素以及符号x1,x2,…,xn都是布尔表示式；布尔表示式并、交、补运算还是布尔表示式。布尔函数假如x1,x2,…,xn被解释为只能在B中取值变量，则一个由x1,x2,…,xn产生布尔表示式实际上就是一个从Bn到B函数。2025/2/2196第96页由x1,x2,…,xn产生布尔表示式有时也称为B上一个n元布尔函数。Bn到B函数不一定是布尔函数，＃B>2时，必定有不是布尔函数函数存在。＃B=2时，Bn到B函数都是布尔函数。多重布尔函数：(f1,f2,…,fm):Bn×Bn×...×Bn到Bm函数。其中fi是Bn到B布尔函数。2025/2/2197第97页GF(2)上布尔函数GF(2)只有两个：0，1。关于这两个量之间逻辑运算，GF(2)成为布尔代数。这时，GF(2)

n到GF(2)一个映射就称为一个n元布尔函数(因为GF(2)基数为2)。对于GF(2)中元素，有x

y＝x·yx

y＝x+y+x·y－x=x+1这里+,·分别表示GF(2)中加(异或)、乘(与)运算。2025/2/2198第98页作为逻辑运算函数，布尔函数是研究数字逻辑电路主要数学工具，也是研究以此为基础一切科学技术主要工具，从而也是研究密码学和密码技术主要工具。不论在流密码还是在分组密码中，不论在私钥还是在公钥密码中，布尔函数都有主要应用。2025/2/2199第99页布尔函数表示为了方便布尔函数理论和应用，人们在不一样情况下对布尔函数采取了不一样表示方法，主要有：真值表表示法小项表示法多项式表示法walsh谱表示法矩阵表示法等2025/2/21100第100页布尔函数研究问题布尔函数表示布尔函数研究方法布尔函数设计实现布尔函数性质满足一定性质布尔函数特征刻划、存在性、结构与计数布尔函数不一样性质之间等价、相斥、相容、制约等关系密码学中，布尔函数一条性质反应一个安全性能指标，当不一样性能指标相互制约时，怎样折衷以提升综合性能；伴随技术发展和新攻击方法出现，新性质提出和研究等等2025/2/21101第101页本原根（本原元）由Euler定理有:aø(n)=1modn,GCD(a,n)=1考虑更普通表示形式am=1modn,GCD(a,n)=1则最少有m=ø(n)使之成立，但可能有更小m存在一旦幂次到m,a幂便出现周期循环假如最小m=ø(n)，则a称为n一个本原根(primitiveroot)假如n=p为素数，则a连续幂生成模p剩下类群。2025/2/21102第102页使am=1modn

成立最小正幂m(这里(a,n)=1)为以下之一amodn阶a

所属模n指数a

所产生周期长。Zp中a，假如a阶数ø(n)，在a就是n一个本原根。假如a是n本原根，则其幂a,a2,…,aø(n)是(模n)各不相同，且均与n互素。2025/2/21103第103页尤其，对素数p，若a是p本原根，则a,a2,…,ap-1是(模p)各不相同。a是Zp生成元。如：素数19本原根为2,3,10,13,14,15.并不是全部整数都有本原根。实际上，只有形为2,4,pb,2pb整数才有本原根，这里p任何奇素数，b正整数。2025/2/21104第104页离散对数或指标求一个数模p离散对数(discretelogarithm)是求幂逆问题即求x使之满足ax=bmodp记x=logabmodporx=inda,p(b)－－以底a(模p)b指标。假如a是一个本原根，则x总存在,不然不一定。x=log34mod13(x使3x=4mod13)不存在而x=log23mod13=4（经过列出所以幂便知）2025/2/21105第105页离散对数问题模指数运算被认为是一个单向函数，即：对于给定整数n,a和x，轻易经过“平方-乘”方法计算出axmodn；不过，对于给定整数n,a和b，由方程ax=bmodn求解整数x确是一个难题。有限域Zp上离散对数问题是：对于给定素数p，有限域Zp上一个本原元a，Zp中非零元b，求解满足ax=bmodp整数x(0≤x≤p-2)，x=logab(modp)(通常记为x=logab)。2025/2/21106第106页离散对数计算当前还没有能够计算离散对数问题多项式时间算法。对于已知攻击方法，素数选取应该满足最少两个条件：长度大于150位p-1最少有一个大素数因子穷搜索方法能够对离散对数进行求解，但对于足够大素数p并不可行，其所需计算时间和存放空间均为O(p).2025/2/21107第107页离散对数计算有3个群离散对数是密码设计人员最为关心。这三个群分别是：素域GF(p)乘法群特征为2有限域GF(2n)上乘法群有限域F上椭圆曲线群EC(F)2025/2/21108第108页离散对数计算GF(p)上计算离散对数问题算法有很各种。平凡算法：经过预计算全部可能ax