信息安全第五章有限域

信息安全第五章有限域第一页，共三十三页，2022年，8月28日简介有限域，finitefields在密码领域的重要性日益突出AES,EllipticCurve,IDEA,PublicKey对“数”的操作概念：群、环和域（groups,rings,fields）2023/1/182第二页，共三十三页，2022年，8月28日群（Group）Group,定义了二元运算的集合，记为{G,·}集合上的二元运算结果仍在该集合中(封闭性)遵循:封闭性：a,b属于G，则a.b属于G结合律：(a·b)·c=a·(b·c)

单位元

e：e·a=a·e=a

逆元a-1：a·a-1=e有限群、无限群：元素数量有限或者无限如果满足交换律：a·b=b·a

则构成阿贝尔群(abeliangroup)2023/1/183第三页，共三十三页，2022年，8月28日循环群（CyclicGroup）定义求幂运算为重复运用群中的运算如：

a3=a·a·a定义：e=a0称一个群为循环群，如果：群中每个元素都是一个固定元素a的幂，即

b=

ak

（forsomeaandeverybingroup）a

称为群的一个生成元（generator）2023/1/184第四页，共三十三页，2022年，8月28日环（Ring）环，是一个定义了两种运算的集合,记为{R,＋,·}两种运算

通常称为加法和乘法，且满足对加法，构成阿贝尔群

对乘法满足封闭性结合律：a·(b·c)=(a·b)·c分配律：a·(b+c)=a·b+a·c如果乘法满足交换律，则称交换环(commutativering)如过乘法有单位元且无零因子，则称整环(integraldomain)零因子：若a≠0且b≠0，但a·b=b·a=0，则称a或b为零因子2023/1/185第五页，共三十三页，2022年，8月28日域（Field）域，是定义了两种运算的集合，记为{F,＋,·}两种运算：对加法，构成阿贝尔群

对乘法，构成阿贝尔群（除0外）环作加、减、乘和除法（除0外）运算，结果仍在集合中继承关系：群->环->域P69图4.12023/1/186第六页，共三十三页，2022年，8月28日2023/1/187第七页，共三十三页，2022年，8月28日模运算定义：模运算“amodn”表示用n去除a所得得余数术语“同余”：a=bmodn

用n去除a和b，他们有相同的余数

如：100=34mod11b称作a模n的余数整数总可以写作：a=qn+b通常选择最小的非负整数作为余数，

即

0<=b<=n-1

2023/1/188第八页，共三十三页，2022年，8月28日因子整除：a=mb(a,b,m

都是整数)b是一个因子(没有余数)记作：

b|a

b是a的一个因子

如：1,2,3,4,6,8,12,24都是24的因子2023/1/189第九页，共三十三页，2022年，8月28日模算术运算is'clockarithmetic'usesafinitenumberofvalues,andloopsbackfromeitherendmodulararithmeticiswhendoaddition&multiplicationandmoduloreduceanswercandoreductionatanypoint,i.e.a+bmodn=[amodn+bmodn]modn

2023/1/1810第十页，共三十三页，2022年，8月28日模算术运算模n的剩余集Zn={0,1,…,n-1}剩余类[0],[1],…[n-1]if(a+b)=(a+c)modn thenb=cmodnif(a·b)=(a·c)modn thenb=cmodnonlyif(a,n)=12023/1/1811第十一页，共三十三页，2022年，8月28日模8加法+012345670012345671123456702234567013345670124456701235567012346670123457701234562023/1/1812第十二页，共三十三页，2022年，8月28日2023/1/1813第十三页，共三十三页，2022年，8月28日交换律结合律分配律恒等式加法逆元2023/1/1814第十四页，共三十三页，2022年，8月28日最大公因子(GCD：GreatestCommonDivisor)GCD(a,b)＝GCD(|a|,|b|)如：GCD(60,24)=GCD(－60,24)=GCD(60,－24)＝12如果GCD(a,b)=1，则称a和b互素如：GCD(8,15)=1注意：GCD(a,0)=|a|2023/1/1815第十五页，共三十三页，2022年，8月28日欧几里得算法（EuclideanAlgorithm）求最大公因子的一个有效方法：欧几里得算法算法基于:GCD(a,b)=GCD(b,amodb)

计算GCD(a,b)的欧几里得算法:EUCLID(a,b)1.A=a;B=b2.ifB=0returnA=gcd(a,b)3.R=AmodB4.A=B5.B=R6.goto2

2023/1/1816第十六页，共三十三页，2022年，8月28日求GCD(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)2023/1/1817第十七页，共三十三页，2022年，8月28日一个元素个数有限的域称为有限域，或者伽罗华域（Galoisfield）。有限域中元素的个数为一个素数，或者一个素数的幂，记为GF(p)或GF(pn),其中p为素数。有限域中运算满足交换律、结合律和分配律。加法的单位元是0,乘法的单位元是1，每个非零元素都有一个唯一的乘法逆元。密码学中用到很多有限域中的运算，因为可以保持数在有限的范围内，且不会有取整的误差。常用的有限域：GF(p)GF(2n)有限域2023/1/1818第十八页，共三十三页，2022年，8月28日伽罗华域GF(p)GF(p)是整数集合Zp={0,1,…,p-1}具有模素数p的代数运算Zp中的整数模运算的性质（表4.2，P73）：交换律、结合律、分配律、恒等式、加法逆元Zn中的任一整数有乘法逆元，当且仅当该整数与n互素p为素数，Zp中所有的非零整数都与p互素，因此Zp中所有非零整数都有乘法逆元。乘法逆元(w-1)：任意w∈Zn，w≠0，存在z∈Zn

，使得w×z≡1modp，z就是w的乘法逆元w-12023/1/1819第十九页，共三十三页，2022年，8月28日GF(7)乘法

0123456000000001012345620246135303625144041526350531642606543212023/1/1820第二十页，共三十三页，2022年，8月28日求逆算法：扩展的欧几里德算法EXTENDEDEUCLID(m,b)1. (A1,A2,A3)=(1,0,m); (B1,B2,B3)=(0,1,b)2.ifB3=0 returnA3=gcd(m,b);noinverse3.ifB3=1 returnB3=gcd(m,b);B2=b–1modm4.Q=A3divB35.(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.goto22023/1/1821第二十一页，共三十三页，2022年，8月28日求GF(1759)中550的乘法逆元QA1A2A3B1B2B3—101759015503015501–310951–3109–516521–5165106–33941106–3394–11135512023/1/1822第二十二页，共三十三页，2022年，8月28日扩展Euclid算法扩展Euclid算法

做欧几里德算法的计算序列 r0＝q1r1＋r2 (令r0＝n，r1＝a) r1＝q2r2＋r3

… rm-2＝qm-1rm-1＋rm(1) rm-1＝qmrm＋rm+1

(0) 记 t0

＝rm+1，t1＝rm，… 依 tj＝tj-2

－qj-1tj-1modr0，…

得 tm

逆 r1的逆 2023/1/1823第二十三页，共三十三页，2022年，8月28日扩展Euclid算法举例22×□≡1mod31 31＝1×22＋9 -1×22≡9 即30×22≡9mod31 22＝2×9＋4 22-2×(30×22)

≡4 即3×22≡4mod31 9＝2×4＋1 30×22-2×(3×22)≡1即24×22≡1mod3128×□≡1mod75 75＝2×28＋19 -2×28≡19 即73×28≡19mod75 28＝1×19＋9 28-1×(73×28)≡9 即3×28≡9mod75 19＝2×9＋1 (73×28)-2×(3×38)≡1即67×28≡1mod75269×□≡1mod349 349＝1×269＋80 -1×269≡80 即-1×269 269＝3×80＋29 269-3×(-1×269)≡29 即4×269 80＝2×29＋22 (-1×269)-2×(4×269)≡22即-9×269 29＝1×22＋7 (4×269)-1×(-9×269)≡7即13×269 22＝3×7＋1 (-9×269)-3×(13×269)≡1即-48×269得3012023/1/1824第二十四页，共三十三页，2022年，8月28日Reverseintreverse(inta,intm){ intb,b1=1,b2=0;//逆元

intr,r1=a,r2=m;// do{ r=r2%r1;//y-kx=r b=(b2-(r2/r1)*b1)%m; r2=r1; b2=b1; r1=r; b1=b; }while(r>1);

if(r==0)//r1中就是gcd，

return0; if(b<0) b+=m; returnb;}2023/1/1825第二十五页，共三十三页，2022年，8月28日多项式运算n次多项式f(x)=anxn+an-1xn-1+…+a1x+a0=∑aixiai组成的集合称为系数集讨论三种多项式运算使用代数基本规则的普通多项式运算系数运算是模p运算的多项式运算，即系数在Zp中系数在Zp中，且多项式被定义为模一个n次多项式m(x)的多项式运算2023/1/1826第二十六页，共三十三页，2022年，8月28日普通多项式运算对应系数相加减（＋，－）系数依次相乘（×）如

f(x)=x3+x2+2，g(x)=x2–x+1f(x)+g(x)=x3+2x2–x+3f(x)–g(x)=x3+x+1f(x)xg(x)=x5+3x2–2x+2注意：定义在整数集上的多项式不支持除法运算，整数集不是域2023/1/1827第二十七页，共三十三页，2022年，8月28日系数在模Zp中的多项式运算系数是域F的元素时，构成多项式环（不构成整环，因为有可能有零因子）系数是Zp的元素的多项式最感兴趣的是mod2所有系数是0或1例如：f(x)=x3+x2

和g(x)=x2+x+1 f(x)+g(x)=x3+x+1 f(x)xg(x)=x5+x22023/1/1828第二十八页，共三十三页，2022年，8月28日多项式的因式对于任何多项式:f(x)=q(x)g(x)+r(x)r(x)称为余式r(x)=f(