信息安全第五章有限域

信息安全第五章有限域第1頁，共33頁，2023年，2月20日，星期三簡介有限域，finitefields在密碼領(lǐng)域的重要性日益突出AES,EllipticCurve,IDEA,PublicKey對“數(shù)”的操作概念：群、環(huán)和域（groups,rings,fields）2023/4/32第2頁，共33頁，2023年，2月20日，星期三群（Group）Group,定義了二元運算的集合，記為{G,·}集合上的二元運算結(jié)果仍在該集合中(封閉性)遵循:封閉性：a,b屬于G，則a.b屬于G結(jié)合律：(a·b)·c=a·(b·c)

單位元

e：e·a=a·e=a

逆元a-1：a·a-1=e有限群、無限群：元素數(shù)量有限或者無限如果滿足交換律：a·b=b·a

則構(gòu)成阿貝爾群(abeliangroup)2023/4/33第3頁，共33頁，2023年，2月20日，星期三循環(huán)群（CyclicGroup）定義求冪運算為重復(fù)運用群中的運算如：

a3=a·a·a定義：e=a0稱一個群為循環(huán)群，如果：群中每個元素都是一個固定元素a的冪，即

b=

ak

（forsomeaandeverybingroup）a

稱為群的一個生成元（generator）2023/4/34第4頁，共33頁，2023年，2月20日，星期三環(huán)（Ring）環(huán)，是一個定義了兩種運算的集合,記為{R,＋,·}兩種運算

通常稱為加法和乘法，且滿足對加法，構(gòu)成阿貝爾群

對乘法滿足封閉性結(jié)合律：a·(b·c)=(a·b)·c分配律：a·(b+c)=a·b+a·c如果乘法滿足交換律，則稱交換環(huán)(commutativering)如過乘法有單位元且無零因子，則稱整環(huán)(integraldomain)零因子：若a≠0且b≠0，但a·b=b·a=0，則稱a或b為零因子2023/4/35第5頁，共33頁，2023年，2月20日，星期三域（Field）域，是定義了兩種運算的集合，記為{F,＋,·}兩種運算：對加法，構(gòu)成阿貝爾群

對乘法，構(gòu)成阿貝爾群（除0外）環(huán)作加、減、乘和除法（除0外）運算，結(jié)果仍在集合中繼承關(guān)系：群->環(huán)->域P69圖4.12023/4/36第6頁，共33頁，2023年，2月20日，星期三2023/4/37第7頁，共33頁，2023年，2月20日，星期三模運算定義：模運算“amodn”表示用n去除a所得得余數(shù)術(shù)語“同余”：a=bmodn

用n去除a和b，他們有相同的余數(shù)

如：100=34mod11b稱作a模n的余數(shù)整數(shù)總可以寫作：a=qn+b通常選擇最小的非負(fù)整數(shù)作為余數(shù)，

即

0<=b<=n-1

2023/4/38第8頁，共33頁，2023年，2月20日，星期三因子整除：a=mb(a,b,m

都是整數(shù))b是一個因子(沒有余數(shù))記作：

b|a

b是a的一個因子

如：1,2,3,4,6,8,12,24都是24的因子2023/4/39第9頁，共33頁，2023年，2月20日，星期三模算術(shù)運算is'clockarithmetic'usesafinitenumberofvalues,andloopsbackfromeitherendmodulararithmeticiswhendoaddition&multiplicationandmoduloreduceanswercandoreductionatanypoint,i.e.a+bmodn=[amodn+bmodn]modn

2023/4/310第10頁，共33頁，2023年，2月20日，星期三模算術(shù)運算模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/4/311第11頁，共33頁，2023年，2月20日，星期三模8加法+012345670012345671123456702234567013345670124456701235567012346670123457701234562023/4/312第12頁，共33頁，2023年，2月20日，星期三2023/4/313第13頁，共33頁，2023年，2月20日，星期三交換律結(jié)合律分配律恒等式加法逆元2023/4/314第14頁，共33頁，2023年，2月20日，星期三最大公因子(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/4/315第15頁，共33頁，2023年，2月20日，星期三歐幾里得算法（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/4/316第16頁，共33頁，2023年，2月20日，星期三求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/4/317第17頁，共33頁，2023年，2月20日，星期三一個元素個數(shù)有限的域稱為有限域，或者伽羅華域（Galoisfield）。有限域中元素的個數(shù)為一個素數(shù)，或者一個素數(shù)的冪，記為GF(p)或GF(pn),其中p為素數(shù)。有限域中運算滿足交換律、結(jié)合律和分配律。加法的單位元是0,乘法的單位元是1，每個非零元素都有一個唯一的乘法逆元。密碼學(xué)中用到很多有限域中的運算，因為可以保持?jǐn)?shù)在有限的范圍內(nèi)，且不會有取整的誤差。常用的有限域：GF(p)GF(2n)有限域2023/4/318第18頁，共33頁，2023年，2月20日，星期三伽羅華域GF(p)GF(p)是整數(shù)集合Zp={0,1,…,p-1}具有模素數(shù)p的代數(shù)運算Zp中的整數(shù)模運算的性質(zhì)（表4.2，P73）：交換律、結(jié)合律、分配律、恒等式、加法逆元Zn中的任一整數(shù)有乘法逆元，當(dāng)且僅當(dāng)該整數(shù)與n互素p為素數(shù)，Zp中所有的非零整數(shù)都與p互素，因此Zp中所有非零整數(shù)都有乘法逆元。乘法逆元(w-1)：任意w∈Zn，w≠0，存在z∈Zn

，使得w×z≡1modp，z就是w的乘法逆元w-12023/4/319第19頁，共33頁，2023年，2月20日，星期三GF(7)乘法

0123456000000001012345620246135303625144041526350531642606543212023/4/320第20頁，共33頁，2023年，2月20日，星期三求逆算法：擴(kuò)展的歐幾里德算法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/4/321第21頁，共33頁，2023年，2月20日，星期三求GF(1759)中550的乘法逆元QA1A2A3B1B2B3—101759015503015501–310951–3109–516521–5165106–33941106–3394–11135512023/4/322第22頁，共33頁，2023年，2月20日，星期三擴(kuò)展Euclid算法擴(kuò)展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/4/323第23頁，共33頁，2023年，2月20日，星期三擴(kuò)展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/4/324第24頁，共33頁，2023年，2月20日，星期三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/4/325第25頁，共33頁，2023年，2月20日，星期三多項式運算n次多項式f(x)=anxn+an-1xn-1+…+a1x+a0=∑aixiai組成的集合稱為系數(shù)集討論三種多項式運算使用代數(shù)基本規(guī)則的普通多項式運算系數(shù)運算是模p運算的多項式運算，即系數(shù)在Zp中系數(shù)在Zp中，且多項式被定義為模一個n次多項式m(x)的多項式運算2023/4/326第26頁，共33頁，2023年，2月20日，星期三普通多項式運算對應(yīng)系數(shù)相加減（＋，－）系數(shù)依次相乘（×）如

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注意：定義在整數(shù)集上的多項式不支持除法運算，整數(shù)集不是域2023/4/327第27頁，共33頁，2023年，2月20日，星期三系數(shù)在模Zp中的多項式運算系數(shù)是域F的元素時，構(gòu)成多項式環(huán)（不構(gòu)成整環(huán)，因為有可能有零因子）系數(shù)是Zp的元素的多項式最感興趣的是mod2所有系數(shù)是0或1例如：f(x)=x3+x2

和g(x)=x2+x+1 f(x)+g(x)=x3+x+1 f(x)xg(x)=x5+x22023/4/328第28頁，共33頁，2023年，2月20日，星期三多項式的因式對于任何多項式:f(x)=q(x)g(x)+r(x)r(x)稱為余式r(x)=f(