信息安全原理與技術數學基礎

1、信息安全原理與技術數學基礎第1頁，共53頁，2022年，5月20日，0點38分，星期一2022/9/1Ch2-數學基礎2第2章 數學基礎 主要知識點： -數論 -代數基礎 -計算復雜性理論 -單向函數 第2頁，共53頁，2022年，5月20日，0點38分，星期一2022/9/1Ch2-數學基礎3因子 設Z表示全體整數所構成的集合。定義2.1 設a, b Z，a0，cZ，使得b = ac，則稱a整除b，并稱a是b的因子或者約數，b是a的倍數，記為a | b。定理2.1 （帶余除法）設a, b Z，b1，則存在唯一的整數q和r，使得a = qb + r，0r 0，重復使用帶余除法，即每次的余數為除

2、數去除上一次的除數，直到余數為0，這樣可以得到下面一組方程： a = bq1+r1, 0 r1 b, b = r1q2+r2, 0 r2 r1, r1 = r2q3+r3, 0 r3 r2, rj-1 = rjqj+1 最后一個不為0的余數rj就是a和b的最大公因子 第4頁，共53頁，2022年，5月20日，0點38分，星期一2022/9/1Ch2-數學基礎5例2.1 求gcd (1970，1066)用歐幾里德算法的計算過程如下：197011066+90410661904+1629045162+94162=194+6894168+2668226+1626116+1016110+61016+46

3、=14+2422+0因此gcd (1970，1066) = 2第5頁，共53頁，2022年，5月20日，0點38分，星期一2022/9/1Ch2-數學基礎6素數 定義2.4 設p Z，p2，如果p的正因子只有1和p，則稱p 為素數，否則為合數 若正整數a有一因子b，而b又是素數，則稱b為a的素因子如果整數a與整數b的最大公因子是1，即gcd (a, b) = 1，則稱a與b互為素數，簡稱互素設(m)為小于或等于m且與m互素的正整數個數，則稱其為歐拉(Euler)函數 第6頁，共53頁，2022年，5月20日，0點38分，星期一2022/9/1Ch2-數學基礎7同余定義2.8 兩個整數a, b分

4、別被m除，如果所得的余數相同，則稱a與b對模m是同余的，記為a b (mod m)，正整數m稱為模數 同余具有下面的性質： (1) 若a b (mod m)，則則m|(b-a)。反過來，若m|(b-a)，則a b (mod m) (2) 如果a=km+b (k為整數)， 則a b (mod m) (3) 每個整數恰與0,1,，m-1這m個整數中的某一個對模m同余 (4) 同余關系是一種等價關系 (5) a b (mod m)當且僅當a mod m = b mod m第7頁，共53頁，2022年，5月20日，0點38分，星期一2022/9/1Ch2-數學基礎8定理2.8 (乘法消去律)對于ab

5、ac（mod m）來說，若gcd(a, m)1則b c(mod m)。 定理2.9 (加法消去律)如果a+b a+c（mod m），則b c(mod m)加法消去律是沒有條件，但乘法消去律的條件是gcd(a, m)1，即a和m互素例如 63672 mod 8，但37 mod 8不成立 第8頁，共53頁，2022年，5月20日，0點38分，星期一2022/9/1Ch2-數學基礎9模運算 求余運算稱為模運算, 下面是模運算的一些性質。 (1) (a+b) mod m = (a mod m) + (b mod m) mod m (2) (a-b) mod m = (a mod m) - (b mod

6、 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 在模運算中，加法單位元是0，(0+a) mod m = a mod m乘法單位元是1，(1a) mod m = a mod m第9頁，共53頁，2022年，5月20日，0

7、點38分，星期一2022/9/1Ch2-數學基礎10定義2.13 對aZm，存在bZm，使得a+b 0 (mod m)，則b是a的加法逆元，記b= - a。定義2.14 對aZm，存在bZm，使得ab 1 (mod m)，則稱b為a的乘法逆元。加法一定存在逆元，乘法不一定存在逆元。在密碼學特別是非對稱密碼體制中，常常需要求模逆元，求模逆元就是求乘法逆元。即尋找一個x，使得ax 1 mod m成立 求模逆元問題很困難，有時有結果，有時沒有結果 利用擴展歐幾里德算法能夠計算出模逆元 第10頁，共53頁，2022年，5月20日，0點38分，星期一2022/9/1Ch2-數學基礎11模8運算的例子 模

8、8的加法和乘法運算與普通運算一樣,只是將所得的值是去模8后的余數 第11頁，共53頁，2022年，5月20日，0點38分，星期一2022/9/1Ch2-數學基礎12第12頁，共53頁，2022年，5月20日，0點38分，星期一2022/9/1Ch2-數學基礎13模8的加法逆元和乘法逆元 對每一個x都有一個對應的y，使得x+y 0 mod 8，則y是x的加法逆元。如對2，有6，使得2+60 mod 8，那么6是2的加法逆元如果對x，存在y，使得xy 1 mod 8，則y為x的乘法逆元。如331 mod 8， 因此3的乘法逆元是3。 第13頁，共53頁，2022年，5月20日，0點38分，星期一2

9、022/9/1Ch2-數學基礎14快速指數模運算 在非對稱密碼體制（公鑰密碼體制）中常常涉及指數模運算，如計算73327 mod 37 一種方法是利用前面介紹的模運算性質(ab) mod m = (a mod m) (b mod m) mod m，將指數模運算可以看做是多次重復乘法，并且在計算中間結果時就取模 例如：計算117mod 13，可以按照下面的思路： 112=1214 mod 13 114= (112)242mod 13 3 mod 13 117=11112114 1143 mod 13 132 mod 13 2 mod 13第14頁，共53頁，2022年，5月20日，0點38分，星

10、期一2022/9/1Ch2-數學基礎15快速求me mod n算法一 (1) ae, bm, c1, 其中a, b, c為三大整數寄存器。 (2) 如果a=0，則輸出結果c即為所求的模n的大整數次冪。 (3) 如果a是奇數，轉第(5)步。 (4) a(a2), b(bb) mod n, 轉第(3)步。 (5) a(a-1), c(cb) mod n, 轉第(2)步。第15頁，共53頁，2022年，5月20日，0點38分，星期一2022/9/1Ch2-數學基礎16計算3037 mod 77 第16頁，共53頁，2022年，5月20日，0點38分，星期一2022/9/1Ch2-數學基礎17費馬定理

11、和歐拉定理 費馬定理和歐拉定理在公鑰密碼體制中占非常重要的地位 定理2.13 (費馬定理Format) 若p是素數, 且a是正整數，且gcd(a, p) = 1，則： ap-1 1(mod p) 定理2.14(歐拉定理) 對于任何互素的兩個整數a和n，有 a(n) 1 mod n第17頁，共53頁，2022年，5月20日，0點38分，星期一2022/9/1Ch2-數學基礎18素性測試 很多密碼算法需要隨機選擇一個或者多個非常大的素數 一般做法是先生成大的隨機整數，然后確定該大數是否是素數 目前沒有還沒有簡單有效的方法確定一個大數是否是素數 定理2.15: 如果p為大于2的素數，則方程x 21

12、(mod p)的解只有x=1和x=-1。定理2.15的逆否命題是：如果方程x 21 (mod p)有一解，那么p不是素數 第18頁，共53頁，2022年，5月20日，0點38分，星期一2022/9/1Ch2-數學基礎19Miller-Rabin素性概率檢驗算法WITNESS(a, n) (1) 將(n-1)表示為二進制形式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 retur

13、n TRUE； else return FALSE.第19頁，共53頁，2022年，5月20日，0點38分，星期一2022/9/1Ch2-數學基礎20算法有兩個輸入，n是待檢驗的數，a是小于n的整數。如果算法的返回值為TRUE，則n肯定不是素數，如果返回值為FALSE，則n有可能是素數。 for循環(huán)后，有d = an-1 mod n，由費馬定理可知，若n為素數，則d為1，因此若d1，則n不是素數，所以返回TRUE。 因為n-1-1 mod n，所以x1，x n-1，表示x 21 (mod p)有不在-1，1中的根，因此n不為素數，返回TRUE 第20頁，共53頁，2022年，5月20日，0點3

14、8分，星期一2022/9/1Ch2-數學基礎21離散對數 離散對數是許多公鑰算法的基礎本原根這一個重要概念 假設gcd (a, n) =1,如果m是使am 1 mod n 成立的最小正整數，則稱它是a對模n的指數，記為Ordna 若Ordna =(n)，則稱a是模n的本原根(primitive root)，也稱生成元第21頁，共53頁，2022年，5月20日，0點38分，星期一2022/9/1Ch2-數學基礎22求模7和模15的本原根 對于模7而言，滿足gcd (a, n) =1的a是1,2,3,4,5,6，將它們的指數列表如下 a123456Ord7a136362從上表可以看到，當a是3和5

15、時，Ord7a =(7)，因此，3和5是模7的本原根。第22頁，共53頁，2022年，5月20日，0點38分，星期一2022/9/1Ch2-數學基礎23對于模15而言，滿足gcd (a, n) =1的a是1,2,4,7,8,11,13,14，將它們的指數列表如下： 上表中不存在一個a，使Ord15a =(15)，所以模15沒有本原根 定理2.18 模m的本原根存在的必要條件是m = 2, 4, pa, 或者2 pa，此處p是奇素數 a12478111314Ord7a14244242第23頁，共53頁，2022年，5月20日，0點38分，星期一2022/9/1Ch2-數學基礎24本原根的測試 通

16、常找出一個本原根不是一件容易的問題 如果知道p-1的因子，它就變得容易 測試方法:令q1,q2, qn是p-1的素因子，對于所有的q1,q2, qn, 計算a(p-1)/q (mod p) ，如果對某個q的某個值其結果為1，那么a 不是一個本原根。如果對某個q的所有值其結果都不為1 ，那么a 是一個本原根。 第24頁，共53頁，2022年，5月20日，0點38分，星期一2022/9/1Ch2-數學基礎25例2.9 假設p=11, 檢驗2和3是否是一個本原根。解： 當p=11時, p-1=10，p-1有兩個素因子2和5，現測試2是否是一個本原根。 2(10-1)/5 (mod 11) = 4 2

17、(10-1)/2 (mod 11) = 10 計算結果沒有1，所以2是本根原。 測試3是否是本根原 3(10-1)/5 (mod 11) = 9 3(10-1)/2 (mod 11) = 1所以3不是本根原第25頁，共53頁，2022年，5月20日，0點38分，星期一2022/9/1Ch2-數學基礎26離散對數 模運算用于指數計算可以表示為ax mod n，我們稱為模指數運算 模指數運算的逆問題就是找出一個數的離散對數，即求解x，使得 ax b mod n定義2.17（離散對數）對于一個整數b和素數n的一個本原根a，可以找到唯一的指數x，使得b ax mod n，其中0 x n-1，指數x稱為

18、b的以a為基數的模n的離散對數第26頁，共53頁，2022年，5月20日，0點38分，星期一2022/9/1Ch2-數學基礎27代數基礎 有限域在現代密碼學中的地位越來越重要本節(jié)先簡單介紹群、環(huán)和域等概念，然后詳細介紹有限域中的運算 第27頁，共53頁，2022年，5月20日，0點38分，星期一2022/9/1Ch2-數學基礎28群 群G有時記做G，是定義了一個二元運算的集合，這個二元運算可以表示為 (它具有一般性，可以指加法，乘法或者其他的數學運算)，G中每一個序偶(a，b)通過運算生成G中的元素(ab)，并滿足以下公理：(Al) 封閉性：如果a和b都屬于G，則ab也屬于G。(A2) 結合律

19、；對于G中任意元素a, b, c，都有 a(bc)=(ab)c成立(A3) 單位元：G中存在一個元素e，對于G中任意元素a，都有ae= ea= a 成立(A4) 逆元：對于G中任意元素a，G中都存在一個元素a，使得式aa=a a=e成立。如果一個群的元素個數是有限的，則該群稱為有限群。并且群的階等于群中元素的個數。否則，稱該群為無限群。一個群如果還滿足以下條件，則稱為交換群（或稱Able群）(A5) 交換律: 對于G中任意的元素a, b，都有.ab=ba成立 第28頁，共53頁，2022年，5月20日，0點38分，星期一2022/9/1Ch2-數學基礎29環(huán) 環(huán)R有時記為R，+，是一個有兩個二

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

21、整環(huán)：(M5)乘法單位元： 在R中存在元素1，使得對于R中的任意元素a，有 al = 1a = a成立。(M6)無零因子：如果有R中元素a, b，且ab=0，則必有a=0或b=0 第29頁，共53頁，2022年，5月20日，0點38分，星期一2022/9/1Ch2-數學基礎30域 域F有時記為F，+，是有兩個二元運算的集合，這兩個二元運算分別稱為加法和乘法，且對于F中的任意元素a, b, c，滿足以下公理：(Al-M6) F是一個整環(huán)；也就是說F滿足從Al到A5以及從M1到M6的所有原則。(M7)乘法逆元:對于F中的任意元素a(除0以外),F中都存在一個元素a-1,使得式aa-1=(a-1)a

22、=1成立 第30頁，共53頁，2022年，5月20日，0點38分，星期一2022/9/1Ch2-數學基礎31根據域中元素的個數是不是有限，把域劃分成有限域和無限域無限域在密碼學中沒有特別的意義，然而有限域卻在許多密碼編碼學中扮演著重要的角色。定義2.19 :有限域中元素的個數稱為有限域的階。定理2.19:有限域的階必為素數p的冪pn，n為正整數定理2.20: 對任意素數p和正整數n，存在pn階的有限域，記為GF(pn)。當時n=1，有限域GF(p)也稱素域。 在密碼學中，最常用的域一般是素域GF(p)或者階為2m的GF(2m)域 第31頁，共53頁，2022年，5月20日，0點38分，星期一2

23、022/9/1Ch2-數學基礎32有限域GF(p) 給定一個素數p，元素個數為p的有限域GF(p)定義為整數0,1,p-1的集合Zp，其運算為模p的算術運算 最簡單的有限域是GF(2)，該域元素的個數是2，它們分別是0和1，在GF(2)上的加運算等價于異或運算，乘等價于邏輯與運算表2.5 是在有限域GF(7)中的算術運算，這是一個階為7，采用模7運算，它滿足域的所有性質。需要注意的是，前面介紹的表2.1只是表示集合Z8中模8運算，其中的非零整數不一定有乘法逆元，因此不是域第32頁，共53頁，2022年，5月20日，0點38分，星期一2022/9/1Ch2-數學基礎33模7加法 第33頁，共53

24、頁，2022年，5月20日，0點38分，星期一2022/9/1Ch2-數學基礎34模7乘法 第34頁，共53頁，2022年，5月20日，0點38分，星期一2022/9/1Ch2-數學基礎35模7的加法逆元和乘法逆元第35頁，共53頁，2022年，5月20日，0點38分，星期一2022/9/1Ch2-數學基礎36域上多項式 若ai 0，稱n為該多項式的次數，并稱an為首項系數。首項系數為1的多項式稱為首1多項式。域F上x多項式全體集合記為Fx 多項式運算包括加法、減法、乘法和除法 第36頁，共53頁，2022年，5月20日，0點38分，星期一2022/9/1Ch2-數學基礎37在域F上的多項式加

25、法運算定義為 乘法運算定義為：第37頁，共53頁，2022年，5月20日，0點38分，星期一2022/9/1Ch2-數學基礎38定理2.21 設a(x)和b(x)是域F上的多項式，且b(x)0，則存在唯一的一對多項式，使 其中q(x)為商式，r(x)為余式，r(x)的次數小于b(x)的次數 多項式除法具有與普通除法一樣的長除法如整數運算類似，我們可以將余式r(x)寫成a(x) mod b(x)，稱為a(x)模b(x)，b(x)稱為模多項式 第38頁，共53頁，2022年，5月20日，0點38分，星期一2022/9/1Ch2-數學基礎39定義2.21 設a(x)和b(x)是域F上的多項式 (1)

26、 設b(x)0，若存在q(x)使， 則稱b(x)是a(x)的因式或者除式。b(x)整除 a(x)，記為b(x) | a(x)。 (2) 設a(x)和b(x)不全為0，a(x)和b(x)的次數最高的首1公因式稱為它們的最高公因式，記為gcd (a(x), b(x)。若gcd (a(x), b(x)=1，稱a(x)和b(x)互素。 (3) 若存在次數大于或者等于1的q(x)和b(x)，使a(x) = q(x)b(x)，則稱a(x)為可約多項式，否則稱a(x)為不可約多項式（也稱既約多項式）第39頁，共53頁，2022年，5月20日，0點38分，星期一2022/9/1Ch2-數學基礎40例如，GF(

27、2)上的多項式 是可約多項式，因為。 而多項式 則是不可約多項式，因為它沒有一個因式 第40頁，共53頁，2022年，5月20日，0點38分，星期一2022/9/1Ch2-數學基礎41有限域GF(2n) 為pn模的模運算不一定能產生域 用不可約多項式可以構造一個域 對于Fx中的每個不可約多項式p(x)，可以構造一個域Fx p(x) 設p(x)是Fx中n次不可約多項式，令Fx p(x)為Fx中所有次數小于n的多項式集合 其中ai F，即在集合0,1,p-1上取值 第41頁，共53頁，2022年，5月20日，0點38分，星期一2022/9/1Ch2-數學基礎42定義Fx p(x)上的二元運算加法和

28、乘法運算如下：域Fx p(x)中的單位元和零元分別是F中的單位元和零元 上面的運算定義可以看到： (1)該運算遵循基本代數規(guī)則中的普通多項式運算規(guī)則 (2) 系數運算以p模，即遵循有限域上Zp的運算規(guī)則 (3) 乘法運算是兩個多項式相乘結果再模一個不可約多項式p(x)，如果兩個多項式相乘結果是次數大于n-1的多項式，它將除以次數為n的不可約多項式p(x)并取余第42頁，共53頁，2022年，5月20日，0點38分，星期一2022/9/1Ch2-數學基礎43定理2.22 是域,當且僅當p(x)是F上的不可約多項式，其中F是有限域。特別地，在GF(2n)中，Fx p(x)中所有次數小于n的多項式表

29、示為：系數ai是二進制數，該多項式可以由它的n個二進制系數唯一地表示。因此GF(2n)中的每個多項式都可以表示成一個n位的二進制整數。 第43頁，共53頁，2022年，5月20日，0點38分，星期一2022/9/1Ch2-數學基礎44高級加密標準中的有限域GF(28) 上運算不可約多項式為 假設多項式加法運算過程為 =乘法運算過程為：第44頁，共53頁，2022年，5月20日，0點38分，星期一2022/9/1Ch2-數學基礎45由于a(x)和b(x)相乘的多項式次數大于n，將它們相乘結果再除不可約多項式p(x)，可得商為x5+x3，余數為x7+x6+1，因此 用十六進制表示為57 83=C1

30、用二進制表示為 =(11000001)說明：在上面的十六進制表示中，是用一個十六進制字符表示4位二進制數，一個字節(jié)的二進制數用括號括起來的兩個十六進制字符表示 第45頁，共53頁，2022年，5月20日，0點38分，星期一2022/9/1Ch2-數學基礎46從上面的例子我們也可以發(fā)現，多項式加法是將對應的系數分別相加 GF(2n)中兩個多項式加法和減法等同于按位異或，需要注意的是加法不進位，減法不借位第46頁，共53頁，2022年，5月20日，0點38分，星期一2022/9/1Ch2-數學基礎47計算復雜性理論 計算復雜性理論提供了一種分析不同密碼技術和算法的計算復雜性方法 計算復雜性理論給出

31、了求解一個問題的計算是“容易”還是“困難”的確切定義，這有助于確定一個密碼算法的安全強度破譯一個密碼算法所花費的時間或者空間代價超出了密碼本身所保密內容的價值，破譯就沒有意義計算機復雜性理論涉及算法的復雜性和問題的復雜性 第47頁，共53頁，2022年，5月20日，0點38分，星期一2022/9/1Ch2-數學基礎48問題的復雜性 一個問題的復雜性是由可解這個問題的算法的計算復雜性所決定 可解一個問題的算法可能有多個，在理論上定義一個問題的計算復雜性為可解該問題的最有效算法的計算復雜性 計算復雜性粗分為三類， 即P類(確定性多項式時間可解類)、NP類(不確定性多項式時間可解類)和NP完全類(記為NPC，不確定性多項式時間可解完全類) P類問題稱為易解問題，NP類問題稱為難解問題，NPC問題稱