第13次課密碼學(xué)中常用數(shù)學(xué)知識(shí)課件

1、密碼學(xué)中常用的數(shù)學(xué)知識(shí)密碼學(xué)中常用的數(shù)學(xué)知識(shí)群、環(huán)、域群、環(huán)、域素?cái)?shù)和互素?cái)?shù)素?cái)?shù)和互素?cái)?shù)模運(yùn)算模運(yùn)算費(fèi)爾瑪定理和歐拉定理費(fèi)爾瑪定理和歐拉定理素性檢驗(yàn)素性檢驗(yàn)歐幾里德算法歐幾里德算法中國(guó)剩余定理中國(guó)剩余定理群的定義: u一些數(shù)字組成的集合 u一個(gè)二元運(yùn)算，運(yùn)算結(jié)果屬于此集合（封閉性）u服從結(jié)合律。有單位元，逆元 。u如果是可交換的，則成為Abel群*為乘法時(shí)，稱(chēng)為乘法群為乘法時(shí)，稱(chēng)為乘法群 逆元（逆元（a-1）*為加法時(shí)，稱(chēng)為加法群為加法時(shí)，稱(chēng)為加法群 逆元（逆元（-a）環(huán)環(huán)的定義的定義: u Abel 群，及一個(gè)乘法運(yùn)算：群，及一個(gè)乘法運(yùn)算：u 滿(mǎn)足結(jié)合律與滿(mǎn)足結(jié)合律與加法的分配律加法的分配律

2、 u 如果加法滿(mǎn)足交換律如果加法滿(mǎn)足交換律, 則稱(chēng)交換環(huán)則稱(chēng)交換環(huán)u 例：整數(shù)例：整數(shù) mod N （for any N ）域的定義： u是Abel加群 u環(huán) u是Abel 乘群 u例： 整數(shù) mod P （ P 為素?cái)?shù)）Galois 域：域：u 如果如果 n是素?cái)?shù)是素?cái)?shù) p ，則模運(yùn)算，則模運(yùn)算modulo p 形成形成 Galois Field modulo p u 記為：記為： GF(p) 因子：對(duì)整數(shù) b!=0 及 a , 如果存在整數(shù) m 使得 a=mb,稱(chēng) b 整除 a, 也稱(chēng)b是a的因子。記作 b|a 例 1,2,3,4,6,8,12,24 整除 24素?cái)?shù)：素?cái)?shù)： 素?cái)?shù)素?cái)?shù): :

3、 只有因子只有因子 1 1 和自身和自身 1 1 是一個(gè)平凡素?cái)?shù)是一個(gè)平凡素?cái)?shù) 例例 2,3,5,7 2,3,5,7 是素?cái)?shù)是素?cái)?shù), 4,6,8,9,10 , 4,6,8,9,10 不是不是200200以?xún)?nèi)的素?cái)?shù)：以?xún)?nèi)的素?cái)?shù)： 2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97 101 103 107 109 113 127 131 137 139 149 151 157 163 167 173 179 181 191 193 197 199素?cái)?shù)分解：素?cái)?shù)分解： 把整數(shù)把整數(shù)n n寫(xiě)成素?cái)?shù)的乘積寫(xiě)成素?cái)?shù)的

4、乘積 分解整數(shù)要比乘法困難分解整數(shù)要比乘法困難 整數(shù)整數(shù) n n的素?cái)?shù)分解是把它寫(xiě)素?cái)?shù)的乘積的素?cái)?shù)分解是把它寫(xiě)素?cái)?shù)的乘積 eg. 91 = 7 eg. 91 = 7 13 ; 3600 = 2 13 ; 3600 = 24 4 3 32 2 5 52 2 互素?cái)?shù)：互素?cái)?shù)： 整數(shù)整數(shù) a, ba, b 互素是指互素是指 它們沒(méi)有除它們沒(méi)有除1之外的其它因子之外的其它因子。8 與與15 互素互素 8的因子的因子1,2,4,8 15的因子的因子 1,3,5,15 1 是唯一的公因子是唯一的公因子 記為：記為：gcd(8,15)=1設(shè)n是一正整數(shù),a是整數(shù),若 a=qn+r, 0rd1. Xf;Yd;

5、2. If Y=0 then return X=gcd(f,d)3. R=X mod Y4. X=Y;5. Y=R6. Goto 2假定輸入是兩個(gè)正整數(shù)假定輸入是兩個(gè)正整數(shù)Euclid算法：算法：ngcd(55,22)=gcd(22,11)=gcd(11,0)=11ngcd(11,10)=gcd(10,1)=1歐幾里德算法-求乘法逆元 若gcd(a,b)=1, b在模a下有乘法逆元(設(shè)ba)。 即存在xd)1.（X1 X2 X3)(1,0,f);(Y1Y2 Y3)(0,1,d);2. If Y3=0, then return X3=gcd(f,d);停止，沒(méi)有逆元停止，沒(méi)有逆元;3. If Y

6、3=1, then return Y3=gcd(f,d);Y2=d-1 mod f;4. Q=X3 div Y3（整數(shù)除）（整數(shù)除）;5. (T1 T2 T3)(X1-QY1,X2-QY2,X3-QY3);6. (X1 X2 X3)(Y1Y2 Y3);7. (Y1Y2 Y3)(T1 T2 T3);8.Goto 2擴(kuò)展歐幾里德算法：擴(kuò)展歐幾里德算法：求求d模模f的逆元的逆元例：求解例：求解 11d (mod51) = 1的步驟。的步驟。 即求即求11-1mod51=？循循環(huán)環(huán)次次數(shù)數(shù)QX1X2X3Y1Y2Y3初初值值-10510111Extended Euclid(f,d) (fd)1.（X1

7、X2 X3)(1,0,f); (Y1Y2 Y3)(0,1,d);2. If Y3=0, then return X3=gcd(f,d); 停止，沒(méi)有逆元停止，沒(méi)有逆元;3. If Y3=1, then return Y3=gcd(f,d);Y2=d-1 mod f;4. Q=X3 div Y3（整數(shù)除）（整數(shù)除）;5. (T1 T2 T3) (X1-QY1,X2-QY2,X3-QY3);6. (X1 X2 X3)(Y1Y2 Y3);7. (Y1Y2 Y3)(T1 T2 T3);8.Goto 21411-1mod51=14Q=X3 div Y3 = 51/11 = 4 T1=X1-Q*Y1 =

8、1- 4*0 = 1 1- 470111211- 47-15431-1542-93412- 93-3 141f *X1+ d*X2 =X3f *Y1+ d*Y2 =Y3f *T1+ d*T2 =T3孫子算經(jīng)里所提出的問(wèn)題之一如下: “今有物不知其數(shù), 三三數(shù)之剩二, 五五數(shù)之剩三, 七七數(shù)之剩二. 問(wèn)物幾何？” “答日二十三.” 把這個(gè)問(wèn)題的提法用同余式的式子來(lái)表達(dá)，它可表把這個(gè)問(wèn)題的提法用同余式的式子來(lái)表達(dá)，它可表示成解示成解同余式組同余式組x 2(mod 3), x 3(mod 5), x 2(mod 7)其中其中x是所求物數(shù)是所求物數(shù).一般解為一般解為: x 70a+21b+15c (m

9、od 105)這個(gè)解法這個(gè)解法, , 在明朝程大位的在明朝程大位的算法統(tǒng)宗算法統(tǒng)宗(1593)(1593)里有下面一首詩(shī)歌里有下面一首詩(shī)歌: : 三人同行七十稀，三人同行七十稀， 五樹(shù)梅花甘一枝，五樹(shù)梅花甘一枝， 七子團(tuán)圓整半月，七子團(tuán)圓整半月， 除百零五便得知。除百零五便得知。x=70*2+21*3+15*2(mod105) =233mod105 =23用途若已知某個(gè)數(shù)關(guān)于一些兩兩互素的數(shù)的同余集，可重構(gòu)此數(shù)。大數(shù)用小數(shù)表示、大數(shù)的運(yùn)算通過(guò)小數(shù)實(shí)現(xiàn)。例如：例如：Z Z1010中每個(gè)數(shù)都可從這個(gè)數(shù)關(guān)于中每個(gè)數(shù)都可從這個(gè)數(shù)關(guān)于2 2和和5 5（1010的兩個(gè)互素的的兩個(gè)互素的因子）的同余類(lèi)重構(gòu)。

10、因子）的同余類(lèi)重構(gòu)。 比如已知比如已知x x關(guān)于關(guān)于2 2和和5 5的同余類(lèi)分別是的同余類(lèi)分別是00和和33，即：即：x mod 20 x mod 20，x mod 53x mod 53。可知是偶數(shù)且被可知是偶數(shù)且被5 5除后余數(shù)是除后余數(shù)是3 3，所以可得所以可得8 8是滿(mǎn)足這一關(guān)系的惟一的是滿(mǎn)足這一關(guān)系的惟一的x x。大數(shù)用小數(shù)表示、大數(shù)的運(yùn)算通過(guò)小數(shù)實(shí)現(xiàn)。大數(shù)用小數(shù)表示、大數(shù)的運(yùn)算通過(guò)小數(shù)實(shí)現(xiàn)。例如：假設(shè)只能處理例如：假設(shè)只能處理5 5以?xún)?nèi)的數(shù)，要考慮以?xún)?nèi)的數(shù)，要考慮1515以?xún)?nèi)的數(shù)。以?xún)?nèi)的數(shù)。將將1515分解為分解為3 3和和5 5。將。將1515以?xún)?nèi)的數(shù)（以?xún)?nèi)的數(shù)（0-140-14）

11、列表（行）列表（行0-20-2，列，列0-40-4）。）。0123400612391101713425112814數(shù)字所在行號(hào)為該數(shù)除數(shù)字所在行號(hào)為該數(shù)除3 3的余數(shù)的余數(shù)數(shù)字所在列號(hào)為該數(shù)除數(shù)字所在列號(hào)為該數(shù)除5 5的余數(shù)的余數(shù)乘法：乘法：1212* *13(mod15)=13(mod15)=？1212的行號(hào)的行號(hào)0 0，列號(hào)，列號(hào)2 2；1313的行號(hào)的行號(hào)1 1，列號(hào)，列號(hào)3 3。行：行：0*1(mod3)=0列：列：2*3(mod5)=1612*13(mod15)=6加法：加法：12+13(mod15)=?12+13(mod15)=?行：行：0+1(mod3)=10+1(mod3)=1

12、列：列：2+3(mod5)=02+3(mod5)=01012+13(mod15)=10定理定理3.5（中國(guó)剩余定理）（中國(guó)剩余定理） 設(shè)設(shè)m1,m2,mk是兩兩互素的正是兩兩互素的正整數(shù)，整數(shù)， ，則一次同余方程組，則一次同余方程組對(duì)模對(duì)模M有惟一解有惟一解:其中其中ei滿(mǎn)足滿(mǎn)足1122modmodmodkkamxamxamx1kiiMm1 12212modkkkMMMxe ae ae aMmmm1 mod1, 2,iiiMemikm令令Mi=M/mi ; ei=Mi=Mi-1(modmi)x=M1M1a1+M2M2a2+MkMkak (modM) 韓信點(diǎn)兵韓信點(diǎn)兵:有兵一隊(duì)有兵一隊(duì), 若列成

13、五行縱隊(duì)若列成五行縱隊(duì), 則末行一人則末行一人; 成六行縱成六行縱隊(duì)隊(duì), 則末行五人則末行五人; 成七行縱隊(duì)成七行縱隊(duì),則末行四人則末行四人; 成十一行縱隊(duì)成十一行縱隊(duì),則末行則末行十人十人, 求兵數(shù)求兵數(shù).解 設(shè)設(shè)x是所求兵數(shù)是所求兵數(shù), 則依題意則依題意: x 1(mod 5), x 5(mod 6), x 4(mod 7), x 10(mod 11)則：則：m1=5,m2=6,m3=7,m4=11 a1=l, a2=5, a3=4, a4=10 M=m1m2m3m4=56711=2310 M1=M/m1=2310/5=462, M2=385, M3=330, M4=210. 有有M1M1 1(mo