1、2020/8/1,Page: 1,密碼學(xué)數(shù)學(xué)引論,楊秋偉 湖南大學(xué) 計(jì)算機(jī)與通信學(xué)院,2020/8/1,Page: 2,密碼學(xué)數(shù)學(xué)引論組成,數(shù)論：研究整數(shù)性質(zhì)的一個(gè)數(shù)學(xué)分支，重點(diǎn)研究素?cái)?shù)。 群論：一種代數(shù)系統(tǒng)，重點(diǎn)研究在整數(shù)上的代數(shù)運(yùn)算。 有限域理論：一種代數(shù)系統(tǒng)，比群更加復(fù)雜。 計(jì)算復(fù)雜性理論：分析不同密碼技術(shù)和算法的計(jì)算復(fù)雜性的方法，并進(jìn)行比較，確定其安全性。,2020/8/1,Page: 3,數(shù)論：整除,整除：設(shè)整數(shù)a和b，且a0。如果存在整數(shù)k使得b = ak，那么就說(shuō)b能被a整除，記做a|b，或者說(shuō)b是a的倍數(shù)。 整除的性質(zhì) 對(duì)所有的整數(shù)a，a|0和a|a成立。同理，對(duì)任意的整數(shù)b，

2、1|b 成立； 如果a|b且b|c，則a|c 成立； 如果a|b且a|c，則對(duì)所有的整數(shù)s和t，a|sb+tc。,2020/8/1,Page: 4,數(shù)論：素?cái)?shù),如果整數(shù)p(p1)只能被1或者是它本身整除，而不能夠被其他整數(shù)整除，則稱整數(shù)p為素?cái)?shù)。 素?cái)?shù)定理：設(shè)(x)是小于x的素?cái)?shù)的個(gè)數(shù)，則 (x) x / lnx,2020/8/1,Page: 5,數(shù)論：素?cái)?shù),算術(shù)基本定理：任何一個(gè)正整數(shù)都可以分解為幾個(gè)素?cái)?shù)的乘積，且該因數(shù)分解是唯一的，除非顛倒因子的順序。 補(bǔ)充定理：如果p是一個(gè)素?cái)?shù)，且乘積ab能被p整除，那么p|a 或者p|b。更一般地，如果乘積abz能夠被素?cái)?shù)p整除，那么abz 中某個(gè)數(shù)必

3、能被p整除。,2020/8/1,Page: 6,數(shù)論：帶余除法,任意的a Z且a 0，可找出兩個(gè)唯一確定的整數(shù)q和r，使a = qm + r，0 r m，q和r分別稱為m去除a所得到的商和余數(shù)。 例一：a = 13，m = 8， 13 = 1 8 + 5 例二：a = -13，m = 8， -13 = (-2) 8 + 3 模的由來(lái)：如果a是一個(gè)整數(shù)，m是一個(gè)正整數(shù)，定義“a mod m”為a除以m的余數(shù)。 例一：a = 13，m = 8， 5 13 mod 8,2020/8/1,Page: 7,數(shù)論：同余,同余：設(shè)整數(shù)a,b,n(n0),如果a-b 是 n 的整數(shù)倍(正的或者負(fù)的)，我們就說(shuō)

4、 a b(modn)(讀做a同余于b模n)。 同余命題一：設(shè)整數(shù)a,b,c,n(n0), 當(dāng)且僅當(dāng)n|a時(shí)，a 0(modn)； a a(modn)； 當(dāng)且僅當(dāng)b a(modn)時(shí)， a b(modn); 如果a b(modn) 且 b c(modn)，那么a c(modn)。 同余命題二：設(shè)整數(shù)a,b,c,d,n(n0),假設(shè)a b(modn),c d(modn),那么,2020/8/1,Page: 8,數(shù)論：剩余類完全剩余系,定義一：給定正整數(shù)m，對(duì)于每個(gè)整數(shù)i，0i m-1，稱集合 Ri(m) = n; ni(mod m), nN 是模m的一個(gè)剩余類。 定義二：設(shè)m是正整數(shù)，從模m的每一

5、個(gè)剩余類中任取一個(gè)數(shù)xi (0 i m-1)，稱集合x0, x1, , xm-1是模m的一個(gè)完全剩余系(或簡(jiǎn)稱為完全系)。 例一：m = 3，三個(gè)剩余類R0(3) = ,-3,0,3，R1(3) = ,-2,1,4，R2(3) = ,-1,2,5；完全剩余類0,1,2。,2020/8/1,Page: 9,數(shù)論：完全剩余系,整數(shù)集合A是模m的完全剩余系的充要條件是： A中含有m個(gè)整數(shù)； A中任何兩個(gè)整數(shù)對(duì)模m不同余。 由于xi的選取是任意的，則模m的完全剩余系有無(wú)窮多個(gè) 模m的最小非負(fù)完全剩余系：0,1,2, ,m-1； 模m的絕對(duì)最小完全剩余系：-m/2 + 1,0,1,m/2(當(dāng)2|m) 或

6、-(m-1)/2,0,1,(m-1)/2(當(dāng)2不整除m)。,2020/8/1,Page: 10,數(shù)論：最大公約數(shù),公約數(shù)：設(shè)a,bZ，a和b的公約數(shù)是能夠同時(shí)整除a和b的整數(shù)。 最大公約數(shù)：設(shè)a,bZ，稱正整數(shù)d為a和b的最大公約數(shù)，如果滿足 d是a和b的公約數(shù)； 對(duì)a和b的任何一個(gè)公約數(shù)c，有c|d。 記為gcd(a,b) = d。 互素?cái)?shù)：如果gcd(a,b)=1，則稱a和b互素。 可以用歐幾里德算法求兩個(gè)非負(fù)整數(shù)的最大公約數(shù)。,定理：對(duì)于任何非負(fù)的 整數(shù)a和b，有 gcb(a,b) = gcd(b,amodb),2020/8/1,Page: 11,數(shù)論：歐幾里德算法求最大公約數(shù),假設(shè)a大

7、于b，求a和b最大公約數(shù)c： 用a去除b：a = q1b + r1 如果 r1 = 0，那么a能夠被b整除，最大公約數(shù)為b；如果r1 0 則將b表示為如下形式： b = q2 r1 + r2 同理，一直進(jìn)行下去，直到余數(shù)為0，步驟如下： r1 = q3r2 + r3 rk-2 = qkrk-1 + rk 結(jié)論： gcd(a,b)=rk-1,int Gcd(int a, int b) if(b = 0) return a; return Gcd(b, a % b);,2020/8/1,Page: 12,數(shù)論：擴(kuò)展歐幾里德定理,歐幾里德定理的過(guò)失 丟棄了所有的中間商數(shù) 基于中間商數(shù)的推演 a =

8、q1b + r1 a + b (-q1) = r1 aq2 + b (-q1q2) = r1q2 r1q2= b r2 a(-q2) + b (1 + q1q2) = r2 ai + bi = ri ak-1+ bk-1 = rk-1 = gcd(a,b),2020/8/1,Page: 13,數(shù)論：擴(kuò)展歐幾里德定理,設(shè)a和b是兩個(gè)整數(shù)(至少有一個(gè)非零)，d = gcd(a,b)，則存在整數(shù)x和y使得ax + by = d成立。特殊情況下，如果a和b都是素?cái)?shù)，那么存在整數(shù)x和y使得ax + by = 1成立。 如何求解x和y？ 求解序列 實(shí)例：求x和y使得482x + 1180y = 2,202

9、0/8/1,Page: 14,數(shù)論：模運(yùn)算除法,乘法逆元：設(shè)模數(shù)為m，如果存在整數(shù)d和整數(shù) d-1 使得dd-1 1(modm)，則稱d-1 是d關(guān)于m的逆元。 除法：設(shè)整數(shù)a,b,c,n(n0)且gcd(a,n)=1，如果 ab ac(modn)，那么b c(modn)；換句話說(shuō)，如果a和n是互素的，我們可以在同余式兩邊同時(shí)除以a。 乘法,當(dāng)且僅當(dāng)gcd(d,m)=1時(shí)，d在模m下有逆元.,2020/8/1,Page: 15,數(shù)論：費(fèi)馬(Fermat)定理,費(fèi)馬定理：如果p是素?cái)?shù)，并且a是不能被p整除的正整數(shù)，那么 ap-1 1 mod p 例一：a = 5，p = 11，求ap-1 1 m

10、od p 費(fèi)馬定理的等價(jià)形式：如果p是素?cái)?shù)，并且a是不能被p整除的正整數(shù)，那么 ap a mod p,2020/8/1,Page: 16,數(shù)論：歐拉(Euler)定理,歐拉函數(shù) ：當(dāng)m 1時(shí)， 表示比m小且與m互素的正整數(shù)的個(gè)數(shù)。 m是素?cái)?shù)時(shí)： = m 1 m = pq，且p和q都是素?cái)?shù)時(shí)： 歐拉定理：對(duì)于任何互素的兩個(gè)整數(shù)a和n，有 當(dāng)n = p時(shí)候，ap-1 1 mod p，為費(fèi)馬定理 例一： a = 3，n = 8，求34 81 1 mod 8,2020/8/1,Page: 17,數(shù)論：同余方程,定義一：設(shè)f(x) = anxn+ +a1x+a0是整系數(shù)多項(xiàng)式，稱f(x) 0 (mod

11、m)是關(guān)于未知數(shù)x的模m的同余方程，簡(jiǎn)稱為模m的同余方程(或同余方程)。若an 0 (mod m)不成立，則稱為n次同余方程。 定義二：設(shè)x0是整數(shù), 當(dāng)x = x0時(shí)式f(x) 0 (mod m)成立，則稱x0是同余方程的解。凡對(duì)于模m同余的解，被視為同一個(gè)解。同余方程的解數(shù)是指它的關(guān)于模m互不同余的所有解的個(gè)數(shù)，也即在模m的一個(gè)完全剩余系中的解的個(gè)數(shù)。 由定義二，同余方程f(x) 0 (mod m)的解數(shù)不超過(guò)m。,2020/8/1,Page: 18,數(shù)論：同余方程組,方程組：又稱“聯(lián)立方程”。把若干個(gè)方程合在一起研究，使其中的未知數(shù)同時(shí)滿足每一個(gè)方程的一組方程。能同時(shí)滿足方程組中每個(gè)方程

12、的未知數(shù)的值，稱為方程組的“解”。求出它所有解的過(guò)程稱為“解方程組”。 同余方程組,2020/8/1,Page: 19,數(shù)論：中國(guó)剩余定理(CRT),設(shè)m1,m2,mk是兩兩互素的正整數(shù)， ，則一次同余方程組 對(duì)模M有唯一解： 其中ei滿足：,2020/8/1,Page: 20,數(shù)論：中國(guó)剩余定理證明正確性,設(shè) ，由M的定義得Mi和mi是互素的，可知Mi在模mi下有唯一的乘法逆元，即 的ei是唯一的。 正確性：上述x是方程組的解 當(dāng)ji時(shí)，mi|Mj，即Mj0(modmi)，則 而 所以,2020/8/1,Page: 21,數(shù)論：中國(guó)剩余定理證明唯一性,唯一性：方程組的解是唯一的 設(shè)x是方程組

13、的另一解，即 由 由于mi兩兩互素，有 所以,2020/8/1,Page: 22,數(shù)論：中國(guó)剩余定理舉例,例二：運(yùn)用中國(guó)剩余定理求解下列同余方程組 中國(guó)剩余定理在密碼學(xué)中的意義：將一個(gè)M用多個(gè)mi進(jìn)行表示，可以運(yùn)用到秘密共享、機(jī)密保護(hù)等方面。,2020/8/1,Page: 23,數(shù)論：中國(guó)剩余定理舉例,例一：一個(gè)數(shù)據(jù)庫(kù)文件由若干數(shù)據(jù)域組成，將每一數(shù)據(jù)域看成一個(gè)整數(shù)，用中國(guó)剩余定理可對(duì)該文件加密，使得一個(gè)用戶可解密一個(gè)特定的數(shù)據(jù)域，但無(wú)法解密其它數(shù)據(jù)域。 設(shè)數(shù)據(jù)庫(kù)文件是D=，k個(gè)用戶的解密密鑰分別是兩兩互素的正整數(shù)m1,m2,mk，設(shè) ； 求與解密密鑰mi對(duì)應(yīng)的加密密鑰 ，其中 ； D對(duì)應(yīng)的密文

14、為 ； 用戶i對(duì)x的解密可得x(modmi)ai，但得不到aj(ji)。,2020/8/1,Page: 24,密碼學(xué)數(shù)學(xué)引論組成,數(shù)論：研究整數(shù)性質(zhì)的一個(gè)數(shù)學(xué)分支，重點(diǎn)研究素?cái)?shù)。 群論：一種代數(shù)系統(tǒng)，重點(diǎn)研究在整數(shù)上的代數(shù)運(yùn)算。 有限域理論：一種代數(shù)系統(tǒng)，比群更加復(fù)雜。 計(jì)算復(fù)雜性理論：分析不同密碼技術(shù)和算法的計(jì)算復(fù)雜性的方法，并進(jìn)行比較，確定其安全性。,2020/8/1,Page: 25,群論：什么是代數(shù)系統(tǒng),代數(shù)系統(tǒng)：也稱為代數(shù)結(jié)構(gòu)，是對(duì)要研究的現(xiàn)象或過(guò)程建立起的一種數(shù)學(xué)模型，模型中包括要處理的數(shù)學(xué)對(duì)象的集合以及集合上的關(guān)系或運(yùn)算，運(yùn)算可以是一元的，也可以是多元的，可以是一個(gè)，也可以是多個(gè)

15、。 代數(shù)系統(tǒng)的表示： 例一：， 例二： 封閉性：集合中的元素經(jīng)過(guò)運(yùn)算得到的結(jié)果仍然包含在集合中。,2020/8/1,Page: 26,群論：群的概念,群由一個(gè)非空集合G組成，在集合G中定義了一個(gè)二元運(yùn)算“.”。滿足以下性質(zhì)的代數(shù)系統(tǒng)稱為群，記為G, . 封閉性：對(duì)任意的a,bG，有a . b G； 結(jié)合律：對(duì)任意的a,b,cG，有 a . b . c = (a . b) . c = a . ( b . c )； 單位元：對(duì)任意的aG，存在一個(gè)元素1G，稱為單位元，滿足a . 1 = 1 . a = a； 逆元：對(duì)任意的aG，存在一個(gè)元素a-1G，稱為逆元，滿足a . a-1 = a-1 . a

16、 = 1。 一個(gè)群如果對(duì)任意的a,bG，滿足a . b = b . a(交換律)，稱為交換群(Abel群)。,半群,半群,2020/8/1,Page: 27,群論：群的性質(zhì)和階,群中的單位元是唯一的； 群中的每一個(gè)元素的逆元是唯一的； 對(duì)任意的a,b,cG，如果a . b = a . c，則 b = c；同樣，如果b . a = c . a，則 b = c； 如果一個(gè)群的元素是有限的，則稱該群為有限群；反之，稱為無(wú)限群。有限群的階等于群中元素的個(gè)數(shù)。,2020/8/1,Page: 28,群論：循環(huán)群,循環(huán)群：群中每一個(gè)元素都是某一個(gè)元素a, G的冪akG(k為整數(shù))，則稱該群是循環(huán)群。元素a稱

17、為群G的生成元。 循環(huán)群的性質(zhì) 循環(huán)群總是交換群,2020/8/1,Page: 29,群論：環(huán),如果代數(shù)系統(tǒng)的二元運(yùn)算 + 和 . 滿足 是Abel群； 是半群； 運(yùn)算 . 在運(yùn)算 + 上可分配，即對(duì)任意的a,b,cG，有 a . (b + c) = a . b + a . c 和 (b + c) . a = b . a + c . a 則稱是環(huán)。 例一：是環(huán)，其中R(x)是所有實(shí)系數(shù)的多項(xiàng)式集合，+和.分別是多項(xiàng)式的加法和乘法。,2020/8/1,Page: 30,密碼學(xué)數(shù)學(xué)引論組成,數(shù)論：研究整數(shù)性質(zhì)的一個(gè)數(shù)學(xué)分支，重點(diǎn)研究素?cái)?shù)。 群論：一種代數(shù)系統(tǒng)，重點(diǎn)研究在整數(shù)上的代數(shù)運(yùn)算。 有限域理

18、論：一種代數(shù)系統(tǒng)，比群更加復(fù)雜。 計(jì)算復(fù)雜性理論：分析不同密碼技術(shù)和算法的計(jì)算復(fù)雜性的方法，并進(jìn)行比較，確定其安全性。,2020/8/1,Page: 31,有限域(Galois Field)：域的概念,域由一個(gè)非空集合F組成，在集合F中定義了 兩個(gè)個(gè)二元運(yùn)算“+”和“.”。滿足以下性質(zhì)的代數(shù)系統(tǒng)稱為域，記為F, +, . F關(guān)于加法“+”是一個(gè)交換群，其單位元是“0”，a的逆元是-a； F關(guān)于乘法“.”是一個(gè)交換群，其單位元是“1”，a的逆元是a-1； 分配律：對(duì)任意的a,b,cF，有 a . (b + c) = a . (b + c) = a . b + a . c； 無(wú)零因子：對(duì)任意的a,

19、b,cF，如果a . b = 0，則a = 0或b = 0。 例一：是域，其中Q是有理數(shù)集合。,2020/8/1,Page: 32,有限域(Galois Field)：有限域的概念,有限域是指域中元素個(gè)數(shù)有限的域，元素個(gè)數(shù)稱為域的階。 若q是素?cái)?shù)的冪，即q = pr，其中p是素?cái)?shù)，r是自然數(shù)，則稱階為q的域稱為Galois域(有限域)，記為GF(q)或GF(pr)或Fq。 當(dāng)r = 1時(shí)，有限域GF(q)稱為素域。,2020/8/1,Page: 33,密碼學(xué)數(shù)學(xué)引論組成,數(shù)論：研究整數(shù)性質(zhì)的一個(gè)數(shù)學(xué)分支，重點(diǎn)研究素?cái)?shù)。 群論：一種代數(shù)系統(tǒng)，重點(diǎn)研究在整數(shù)上的代數(shù)運(yùn)算。 有限域理論：一種代數(shù)系統(tǒng)，比群更加復(fù)雜。 計(jì)算復(fù)雜性理論：分析不同密碼技術(shù)的算法和問(wèn)題復(fù)雜性的方法，并進(jìn)行比較，確定其安全性。,2020/8/1,Page: 34,計(jì)算機(jī)復(fù)雜性理論：