信息安全原理與技術(shù)ch02-數(shù)學(xué)基礎(chǔ)課件

1、信息安全原理與技術(shù)郭亞軍 宋建華 李莉清華大學(xué)出版社 2022/9/141Ch2-數(shù)學(xué)基礎(chǔ)第2章 數(shù)學(xué)基礎(chǔ) 主要知識(shí)點(diǎn)： -數(shù)論 -代數(shù)基礎(chǔ) -計(jì)算復(fù)雜性理論 -單向函數(shù) 2022/9/142Ch2-數(shù)學(xué)基礎(chǔ)因子 設(shè)Z表示全體整數(shù)所構(gòu)成的集合。定義2.1 設(shè)a, b Z，a0，cZ，使得b = ac，則稱a整除b，并稱a是b的因子或者約數(shù)，b是a的倍數(shù)，記為a | b。定理2.1 （帶余除法）設(shè)a, b Z，b1，則存在唯一的整數(shù)q和r，使得a = qb + r，0r 0，重復(fù)使用帶余除法，即每次的余數(shù)為除數(shù)去除上一次的除數(shù)，直到余數(shù)為0，這樣可以得到下面一組方程： a = bq1+r1, 0

2、 r1 b, b = r1q2+r2, 0 r2 r1, r1 = r2q3+r3, 0 r3 r2, rj-1 = rjqj+1 最后一個(gè)不為0的余數(shù)rj就是a和b的最大公因子 2022/9/144Ch2-數(shù)學(xué)基礎(chǔ)素?cái)?shù) 定義2.4 設(shè)p Z，p2，如果p的正因子只有1和p，則稱p 為素?cái)?shù)，否則為合數(shù) 若正整數(shù)a有一因子b，而b又是素?cái)?shù)，則稱b為a的素因子如果整數(shù)a與整數(shù)b的最大公因子是1，即gcd (a, b) = 1，則稱a與b互為素?cái)?shù)，簡(jiǎn)稱互素設(shè)(m)為小于或等于m且與m互素的正整數(shù)個(gè)數(shù)，則稱其為歐拉(Euler)函數(shù) 2022/9/146Ch2-數(shù)學(xué)基礎(chǔ)同余定義2.8 兩個(gè)整數(shù)a, b

3、分別被m除，如果所得的余數(shù)相同，則稱a與b對(duì)模m是同余的，記為a b (mod m)，正整數(shù)m稱為模數(shù) 同余具有下面的性質(zhì)： (1) 若a b (mod m)，則則m|(b-a)。反過來，若m|(b-a)，則a b (mod m) (2) 如果a=km+b (k為整數(shù))， 則a b (mod m) (3) 每個(gè)整數(shù)恰與0,1,，m-1這m個(gè)整數(shù)中的某一個(gè)對(duì)模m同余 (4) 同余關(guān)系是一種等價(jià)關(guān)系 (5) a b (mod m)當(dāng)且僅當(dāng)a mod m = b mod m2022/9/147Ch2-數(shù)學(xué)基礎(chǔ)模運(yùn)算 求余運(yùn)算稱為模運(yùn)算, 下面是模運(yùn)算的一些性質(zhì)。 (1) (a+b) mod m =

4、(a mod m) + (b mod m) mod m (2) (a-b) mod m = (a mod m) - (b mod m) mod m (3) (ab) mod m = (a mod m) (b mod m) mod m (4) (a(b+c) ) mod m = (ab) mod m) + (ac) mod m) mod m例如 11 mod 8 = 3; 15 mod 8 =7, 那么 (11 mod 8 )+ (15 mod 8) mod 8 = (3+7) mod 8 = 2 (11+15) mod 8 = 26 mod 8 =2 在模運(yùn)算中，加法單位元是0，(0+a) m

5、od m = a mod m乘法單位元是1，(1a) mod m = a mod m2022/9/149Ch2-數(shù)學(xué)基礎(chǔ)定義2.13 對(duì)aZm，存在bZm，使得a+b 0 (mod m)，則b是a的加法逆元，記b= - a。定義2.14 對(duì)aZm，存在bZm，使得ab 1 (mod m)，則稱b為a的乘法逆元。加法一定存在逆元，乘法不一定存在逆元。在密碼學(xué)特別是非對(duì)稱密碼體制中，常常需要求模逆元，求模逆元就是求乘法逆元。即尋找一個(gè)x，使得ax 1 mod m成立 求模逆元問題很困難，有時(shí)有結(jié)果，有時(shí)沒有結(jié)果 利用擴(kuò)展歐幾里德算法能夠計(jì)算出模逆元 2022/9/1410Ch2-數(shù)學(xué)基礎(chǔ)模8運(yùn)算的

6、例子 模8的加法和乘法運(yùn)算與普通運(yùn)算一樣,只是將所得的值是去模8后的余數(shù) 2022/9/1411Ch2-數(shù)學(xué)基礎(chǔ)2022/9/1412Ch2-數(shù)學(xué)基礎(chǔ)模8的加法逆元和乘法逆元 對(duì)每一個(gè)x都有一個(gè)對(duì)應(yīng)的y，使得x+y 0 mod 8，則y是x的加法逆元。如對(duì)2，有6，使得2+60 mod 8，那么6是2的加法逆元如果對(duì)x，存在y，使得xy 1 mod 8，則y為x的乘法逆元。如331 mod 8， 因此3的乘法逆元是3。 2022/9/1413Ch2-數(shù)學(xué)基礎(chǔ)快速指數(shù)模運(yùn)算 在非對(duì)稱密碼體制（公鑰密碼體制）中常常涉及指數(shù)模運(yùn)算，如計(jì)算73327 mod 37 一種方法是利用前面介紹的模運(yùn)算性質(zhì)(

7、ab) mod m = (a mod m) (b mod m) mod m，將指數(shù)模運(yùn)算可以看做是多次重復(fù)乘法，并且在計(jì)算中間結(jié)果時(shí)就取模 例如：計(jì)算117mod 13，可以按照下面的思路： 112=1214 mod 13 114= (112)242mod 13 3 mod 13 117=11112114 1143 mod 13 132 mod 13 2 mod 132022/9/1414Ch2-數(shù)學(xué)基礎(chǔ)計(jì)算3037 mod 77 2022/9/1416Ch2-數(shù)學(xué)基礎(chǔ)費(fèi)馬定理和歐拉定理 費(fèi)馬定理和歐拉定理在公鑰密碼體制中占非常重要的地位 定理2.13 (費(fèi)馬定理Format) 若p是素?cái)?shù),

8、且a是正整數(shù)，且gcd(a, p) = 1，則： ap-1 1(mod p) 定理2.14(歐拉定理) 對(duì)于任何互素的兩個(gè)整數(shù)a和n，有 a(n) 1 mod n2022/9/1417Ch2-數(shù)學(xué)基礎(chǔ)Miller-Rabin素性概率檢驗(yàn)算法WITNESS(a, n) (1) 將(n-1)表示為二進(jìn)制形式bkbk-1b0 (2) d1 for i= k downto 0 do xd； d(d d) mod n； if (d=1 & x 1 & x n-1) then return TRUE； if bi=1 then d(d a) mod n if d1 then return TRUE； el

9、se return FALSE.2022/9/1419Ch2-數(shù)學(xué)基礎(chǔ)算法有兩個(gè)輸入，n是待檢驗(yàn)的數(shù)，a是小于n的整數(shù)。如果算法的返回值為TRUE，則n肯定不是素?cái)?shù)，如果返回值為FALSE，則n有可能是素?cái)?shù)。 for循環(huán)后，有d = an-1 mod n，由費(fèi)馬定理可知，若n為素?cái)?shù)，則d為1，因此若d1，則n不是素?cái)?shù)，所以返回TRUE。 因?yàn)閚-1-1 mod n，所以x1，x n-1，表示x 21 (mod p)有不在-1，1中的根，因此n不為素?cái)?shù)，返回TRUE 2022/9/1420Ch2-數(shù)學(xué)基礎(chǔ)離散對(duì)數(shù) 離散對(duì)數(shù)是許多公鑰算法的基礎(chǔ)本原根這一個(gè)重要概念 假設(shè)gcd (a, n) =1,

10、如果m是使am 1 mod n 成立的最小正整數(shù)，則稱它是a對(duì)模n的指數(shù)，記為Ordna 若Ordna =(n)，則稱a是模n的本原根(primitive root)，也稱生成元2022/9/1421Ch2-數(shù)學(xué)基礎(chǔ)求模7和模15的本原根 對(duì)于模7而言，滿足gcd (a, n) =1的a是1,2,3,4,5,6，將它們的指數(shù)列表如下 a123456Ord7a136362從上表可以看到，當(dāng)a是3和5時(shí)，Ord7a =(7)，因此，3和5是模7的本原根。2022/9/1422Ch2-數(shù)學(xué)基礎(chǔ)對(duì)于模15而言，滿足gcd (a, n) =1的a是1,2,4,7,8,11,13,14，將它們的指數(shù)列表如

11、下： 上表中不存在一個(gè)a，使Ord15a =(15)，所以模15沒有本原根 定理2.18 模m的本原根存在的必要條件是m = 2, 4, pa, 或者2 pa，此處p是奇素?cái)?shù) a12478111314Ord7a142442422022/9/1423Ch2-數(shù)學(xué)基礎(chǔ)本原根的測(cè)試 通常找出一個(gè)本原根不是一件容易的問題 如果知道p-1的因子，它就變得容易 測(cè)試方法:令q1,q2, qn是p-1的素因子，對(duì)于所有的q1,q2, qn, 計(jì)算a(p-1)/q (mod p) ，如果對(duì)某個(gè)q的某個(gè)值其結(jié)果為1，那么a 不是一個(gè)本原根。如果對(duì)某個(gè)q的所有值其結(jié)果都不為1 ，那么a 是一個(gè)本原根。 2022/

12、9/1424Ch2-數(shù)學(xué)基礎(chǔ)離散對(duì)數(shù) 模運(yùn)算用于指數(shù)計(jì)算可以表示為ax mod n，我們稱為模指數(shù)運(yùn)算 模指數(shù)運(yùn)算的逆問題就是找出一個(gè)數(shù)的離散對(duì)數(shù)，即求解x，使得 ax b mod n定義2.17（離散對(duì)數(shù)）對(duì)于一個(gè)整數(shù)b和素?cái)?shù)n的一個(gè)本原根a，可以找到唯一的指數(shù)x，使得b ax mod n，其中0 x n-1，指數(shù)x稱為b的以a為基數(shù)的模n的離散對(duì)數(shù)2022/9/1426Ch2-數(shù)學(xué)基礎(chǔ)代數(shù)基礎(chǔ) 有限域在現(xiàn)代密碼學(xué)中的地位越來越重要本節(jié)先簡(jiǎn)單介紹群、環(huán)和域等概念，然后詳細(xì)介紹有限域中的運(yùn)算 2022/9/1427Ch2-數(shù)學(xué)基礎(chǔ)環(huán) 環(huán)R有時(shí)記為R，+，是一個(gè)有兩個(gè)二元運(yùn)算的集合，這兩個(gè)二元運(yùn)

13、算分別稱為加法和乘法，且對(duì)于R中的任意元素a, b, c，滿足以下公理： (Al-A5) R關(guān)于加法是一個(gè)交換群；對(duì)于此種情況下的加法群，我們用0表示其單位元，-a表示a的逆元。 (M1)乘法的封閉性：如果a和b都屬于R，則ab也屬于R。(M2)乘法的結(jié)合律：對(duì)于R中任意元素a, b, c，有a(bc)=(ab)c成立。(M3)分配律：對(duì)于R中任意元素a, b, c，式a(b+c) = ab+ac和式(a+b)c=ac+bc總成立。環(huán)如果還滿足一下條件則成為交換環(huán)：(M4)乘法的交換律：對(duì)于R中的任意元素a,b，有ab=ba成立。在交換環(huán)的基礎(chǔ)上，滿足以下公理的環(huán)叫做整環(huán)：(M5)乘法單位元：

14、 在R中存在元素1，使得對(duì)于R中的任意元素a，有 al = 1a = a成立。(M6)無零因子：如果有R中元素a, b，且ab=0，則必有a=0或b=0 2022/9/1429Ch2-數(shù)學(xué)基礎(chǔ)域 域F有時(shí)記為F，+，是有兩個(gè)二元運(yùn)算的集合，這兩個(gè)二元運(yùn)算分別稱為加法和乘法，且對(duì)于F中的任意元素a, b, c，滿足以下公理：(Al-M6) F是一個(gè)整環(huán)；也就是說F滿足從Al到A5以及從M1到M6的所有原則。(M7)乘法逆元:對(duì)于F中的任意元素a(除0以外),F中都存在一個(gè)元素a-1,使得式aa-1=(a-1)a=1成立 2022/9/1430Ch2-數(shù)學(xué)基礎(chǔ)根據(jù)域中元素的個(gè)數(shù)是不是有限，把域劃分

15、成有限域和無限域無限域在密碼學(xué)中沒有特別的意義，然而有限域卻在許多密碼編碼學(xué)中扮演著重要的角色。定義2.19 :有限域中元素的個(gè)數(shù)稱為有限域的階。定理2.19:有限域的階必為素?cái)?shù)p的冪pn，n為正整數(shù)定理2.20: 對(duì)任意素?cái)?shù)p和正整數(shù)n，存在pn階的有限域，記為GF(pn)。當(dāng)時(shí)n=1，有限域GF(p)也稱素域。 在密碼學(xué)中，最常用的域一般是素域GF(p)或者階為2m的GF(2m)域 2022/9/1431Ch2-數(shù)學(xué)基礎(chǔ)有限域GF(p) 給定一個(gè)素?cái)?shù)p，元素個(gè)數(shù)為p的有限域GF(p)定義為整數(shù)0,1,p-1的集合Zp，其運(yùn)算為模p的算術(shù)運(yùn)算 最簡(jiǎn)單的有限域是GF(2)，該域元素的個(gè)數(shù)是2，

16、它們分別是0和1，在GF(2)上的加運(yùn)算等價(jià)于異或運(yùn)算，乘等價(jià)于邏輯與運(yùn)算表2.5 是在有限域GF(7)中的算術(shù)運(yùn)算，這是一個(gè)階為7，采用模7運(yùn)算，它滿足域的所有性質(zhì)。需要注意的是，前面介紹的表2.1只是表示集合Z8中模8運(yùn)算，其中的非零整數(shù)不一定有乘法逆元，因此不是域2022/9/1432Ch2-數(shù)學(xué)基礎(chǔ)模7加法 2022/9/1433Ch2-數(shù)學(xué)基礎(chǔ)模7乘法 2022/9/1434Ch2-數(shù)學(xué)基礎(chǔ)模7的加法逆元和乘法逆元2022/9/1435Ch2-數(shù)學(xué)基礎(chǔ)域上多項(xiàng)式 若ai 0，稱n為該多項(xiàng)式的次數(shù)，并稱an為首項(xiàng)系數(shù)。首項(xiàng)系數(shù)為1的多項(xiàng)式稱為首1多項(xiàng)式。域F上x多項(xiàng)式全體集合記為Fx

17、多項(xiàng)式運(yùn)算包括加法、減法、乘法和除法 2022/9/1436Ch2-數(shù)學(xué)基礎(chǔ)在域F上的多項(xiàng)式加法運(yùn)算定義為 乘法運(yùn)算定義為：2022/9/1437Ch2-數(shù)學(xué)基礎(chǔ)定理2.21 設(shè)a(x)和b(x)是域F上的多項(xiàng)式，且b(x)0，則存在唯一的一對(duì)多項(xiàng)式，使 其中q(x)為商式，r(x)為余式，r(x)的次數(shù)小于b(x)的次數(shù) 多項(xiàng)式除法具有與普通除法一樣的長(zhǎng)除法如整數(shù)運(yùn)算類似，我們可以將余式r(x)寫成a(x) mod b(x)，稱為a(x)模b(x)，b(x)稱為模多項(xiàng)式 2022/9/1438Ch2-數(shù)學(xué)基礎(chǔ)定義2.21 設(shè)a(x)和b(x)是域F上的多項(xiàng)式 (1) 設(shè)b(x)0，若存在q(

18、x)使， 則稱b(x)是a(x)的因式或者除式。b(x)整除 a(x)，記為b(x) | a(x)。 (2) 設(shè)a(x)和b(x)不全為0，a(x)和b(x)的次數(shù)最高的首1公因式稱為它們的最高公因式，記為gcd (a(x), b(x)。若gcd (a(x), b(x)=1，稱a(x)和b(x)互素。 (3) 若存在次數(shù)大于或者等于1的q(x)和b(x)，使a(x) = q(x)b(x)，則稱a(x)為可約多項(xiàng)式，否則稱a(x)為不可約多項(xiàng)式（也稱既約多項(xiàng)式）2022/9/1439Ch2-數(shù)學(xué)基礎(chǔ)例如，GF(2)上的多項(xiàng)式 是可約多項(xiàng)式，因?yàn)椤?而多項(xiàng)式 則是不可約多項(xiàng)式，因?yàn)樗鼪]有一個(gè)因式

19、2022/9/1440Ch2-數(shù)學(xué)基礎(chǔ)有限域GF(2n) 為pn模的模運(yùn)算不一定能產(chǎn)生域 用不可約多項(xiàng)式可以構(gòu)造一個(gè)域 對(duì)于Fx中的每個(gè)不可約多項(xiàng)式p(x)，可以構(gòu)造一個(gè)域Fx p(x) 設(shè)p(x)是Fx中n次不可約多項(xiàng)式，令Fx p(x)為Fx中所有次數(shù)小于n的多項(xiàng)式集合 其中ai F，即在集合0,1,p-1上取值 2022/9/1441Ch2-數(shù)學(xué)基礎(chǔ)定義Fx p(x)上的二元運(yùn)算加法和乘法運(yùn)算如下：域Fx p(x)中的單位元和零元分別是F中的單位元和零元 上面的運(yùn)算定義可以看到： (1)該運(yùn)算遵循基本代數(shù)規(guī)則中的普通多項(xiàng)式運(yùn)算規(guī)則 (2) 系數(shù)運(yùn)算以p模，即遵循有限域上Zp的運(yùn)算規(guī)則 (

20、3) 乘法運(yùn)算是兩個(gè)多項(xiàng)式相乘結(jié)果再模一個(gè)不可約多項(xiàng)式p(x)，如果兩個(gè)多項(xiàng)式相乘結(jié)果是次數(shù)大于n-1的多項(xiàng)式，它將除以次數(shù)為n的不可約多項(xiàng)式p(x)并取余2022/9/1442Ch2-數(shù)學(xué)基礎(chǔ)定理2.22 是域,當(dāng)且僅當(dāng)p(x)是F上的不可約多項(xiàng)式，其中F是有限域。特別地，在GF(2n)中，F(xiàn)x p(x)中所有次數(shù)小于n的多項(xiàng)式表示為：系數(shù)ai是二進(jìn)制數(shù)，該多項(xiàng)式可以由它的n個(gè)二進(jìn)制系數(shù)唯一地表示。因此GF(2n)中的每個(gè)多項(xiàng)式都可以表示成一個(gè)n位的二進(jìn)制整數(shù)。 2022/9/1443Ch2-數(shù)學(xué)基礎(chǔ)高級(jí)加密標(biāo)準(zhǔn)中的有限域GF(28) 上運(yùn)算不可約多項(xiàng)式為 假設(shè)多項(xiàng)式加法運(yùn)算過程為 =乘法運(yùn)

21、算過程為：2022/9/1444Ch2-數(shù)學(xué)基礎(chǔ)由于a(x)和b(x)相乘的多項(xiàng)式次數(shù)大于n，將它們相乘結(jié)果再除不可約多項(xiàng)式p(x)，可得商為x5+x3，余數(shù)為x7+x6+1，因此 用十六進(jìn)制表示為57 83=C1用二進(jìn)制表示為 =(11000001)說明：在上面的十六進(jìn)制表示中，是用一個(gè)十六進(jìn)制字符表示4位二進(jìn)制數(shù)，一個(gè)字節(jié)的二進(jìn)制數(shù)用括號(hào)括起來的兩個(gè)十六進(jìn)制字符表示 2022/9/1445Ch2-數(shù)學(xué)基礎(chǔ)從上面的例子我們也可以發(fā)現(xiàn)，多項(xiàng)式加法是將對(duì)應(yīng)的系數(shù)分別相加 GF(2n)中兩個(gè)多項(xiàng)式加法和減法等同于按位異或，需要注意的是加法不進(jìn)位，減法不借位2022/9/1446Ch2-數(shù)學(xué)基礎(chǔ)計(jì)算

22、復(fù)雜性理論 計(jì)算復(fù)雜性理論提供了一種分析不同密碼技術(shù)和算法的計(jì)算復(fù)雜性方法 計(jì)算復(fù)雜性理論給出了求解一個(gè)問題的計(jì)算是“容易”還是“困難”的確切定義，這有助于確定一個(gè)密碼算法的安全強(qiáng)度破譯一個(gè)密碼算法所花費(fèi)的時(shí)間或者空間代價(jià)超出了密碼本身所保密內(nèi)容的價(jià)值，破譯就沒有意義計(jì)算機(jī)復(fù)雜性理論涉及算法的復(fù)雜性和問題的復(fù)雜性 2022/9/1447Ch2-數(shù)學(xué)基礎(chǔ)問題的復(fù)雜性 一個(gè)問題的復(fù)雜性是由可解這個(gè)問題的算法的計(jì)算復(fù)雜性所決定 可解一個(gè)問題的算法可能有多個(gè)，在理論上定義一個(gè)問題的計(jì)算復(fù)雜性為可解該問題的最有效算法的計(jì)算復(fù)雜性 計(jì)算復(fù)雜性粗分為三類， 即P類(確定性多項(xiàng)式時(shí)間可解類)、NP類(不確定性多項(xiàng)式時(shí)間可解類)和NP完全類(記為NPC，不確定性多項(xiàng)式時(shí)間可解完全類) P類問題稱為易解問題，NP類問題稱為難解問題，NPC問題稱為困難問題。由于NPC問題不存在有效的算法，現(xiàn)在的密碼算法的安全性都是基于NPC問題的 2022/9/1448Ch2-數(shù)學(xué)基礎(chǔ)算法的復(fù)雜性 算法的復(fù)雜性表示算法在實(shí)際執(zhí)行時(shí)所需計(jì)算能力方面的信息，通常它由該算法所要求的最大時(shí)間與儲(chǔ)存空間來確定