2023/9/6現(xiàn)代密碼學(xué)理論與實(shí)踐-081網(wǎng)絡(luò)信息安全

Chapter8

IntroductiontoNumberTheory2023/8/3現(xiàn)代密碼學(xué)理論與實(shí)踐-081網(wǎng)絡(luò)信息安全

C2023/9/6現(xiàn)代密碼學(xué)理論與實(shí)踐-082/68第二部分公鑰密碼和散列函數(shù)第8章：數(shù)論入門第9章：公鑰密碼與RSA第10章：密鑰管理和其他公鑰密碼體制第11章：消息認(rèn)證和散列函數(shù)第12章：散列和MAC算法第13章：數(shù)字簽名和認(rèn)證協(xié)議2023/8/3現(xiàn)代密碼學(xué)理論與實(shí)踐-082/68第二部分2023/9/6現(xiàn)代密碼學(xué)理論與實(shí)踐-083/68本章要點(diǎn)素?cái)?shù)是一種整數(shù)，在整除意義下，它只能被自身(正負(fù))和1整除。素?cái)?shù)在數(shù)論和密碼學(xué)里扮演重要角色。在公鑰密碼里起重要作用的兩個(gè)定理是費(fèi)馬定理和歐拉定理。許多密碼算法的一個(gè)重要前提是能夠選擇一個(gè)大的素?cái)?shù)。開發(fā)有效算法判定一個(gè)隨機(jī)整數(shù)是否為素?cái)?shù)是密碼研究重要課題。離散對(duì)數(shù)是許多公鑰算法的基礎(chǔ)。離散對(duì)數(shù)和普通對(duì)數(shù)類似，但是在模算術(shù)上進(jìn)行運(yùn)算。2023/8/3現(xiàn)代密碼學(xué)理論與實(shí)踐-083/68本章要點(diǎn)素2023/9/6現(xiàn)代密碼學(xué)理論與實(shí)踐-084/688.1素?cái)?shù)PrimeNumbers素?cái)?shù)的因子是1和其自身不能寫作其他數(shù)的乘積形式1是素?cái)?shù)，但是通常沒有什么作用

如，2,3,5,7是素?cái)?shù),4,6,8,9,10不是素?cái)?shù)是數(shù)論的核心小于200的素?cái)?shù)如下

2357111317192329313741434753596167717379838997101103107109113127131137139149151157163167173179181191193197199

2023/8/3現(xiàn)代密碼學(xué)理論與實(shí)踐-084/688.1素2023/9/6現(xiàn)代密碼學(xué)理論與實(shí)踐-085/68小于2000的素?cái)?shù)2023/8/3現(xiàn)代密碼學(xué)理論與實(shí)踐-085/68小于2002023/9/6現(xiàn)代密碼學(xué)理論與實(shí)踐-086/68One-wayFunctionand

One-wayTrapdoorFunction

定義8.1

單向函數(shù)(One-wayFunction) 一函數(shù)f若滿足下列條件,則稱f為單向函數(shù)：

(1)對(duì)于所有屬于f域的任一x,容易計(jì)算y=f(x) (2)對(duì)于幾乎所有屬于f域的任一y,求得x,使y=f(x),在計(jì)算上不可行。定義8.2

單向陷井門函數(shù)(One-wayTrapdoorFunction) 一“可逆”函數(shù)F若滿足下列二條件,則稱F為單向陷井門函數(shù):(1)對(duì)于所有屬于F域的任一x,容易計(jì)算F(x)=y；(2)對(duì)于幾乎所有屬于F域的任一y,除非獲得暗門信息(trapdoor),否則求出x,使得x=F-1(y)在計(jì)算上不可行,F-1為F之逆函數(shù);如有額外信息(暗門),則容易求出x=F-1(y)。2023/8/3現(xiàn)代密碼學(xué)理論與實(shí)踐-086/68One-w2023/9/6現(xiàn)代密碼學(xué)理論與實(shí)踐-087/681.DiscreteLogarithmProblem(DLP)離散對(duì)數(shù)問題

令質(zhì)數(shù)p滿足p-1含有另一大質(zhì)數(shù)q(q整除p-1)及一整數(shù)g,1<g<p-1。若給定整數(shù)x,求y=gxmodp,最多需要Llog2x?+w(x)-1次乘法,w(x)為x中所有1的個(gè)數(shù)。如x

=15,即x

=(1111)2,w(x)=4,則g15=((g2)g)2·g)2·gmodp,只需要3+4-1=6次乘法。但是若給定p,g及y,求x,則為DLP問題,最快方法需要L(p)=exp{(lnpln(lnp))?}次運(yùn)算。當(dāng)p=512位時(shí),L(p)約為2256≈1077,計(jì)算上不可行,因?yàn)?100≈1030,計(jì)算要1016年。單向函數(shù)舉例2023/8/3現(xiàn)代密碼學(xué)理論與實(shí)踐-087/681.Di2023/9/6現(xiàn)代密碼學(xué)理論與實(shí)踐-088/682.FactorizationProblem因數(shù)分解問題給定大素?cái)?shù)p和q,求n=p×q,只要一次乘法給定n,求p和q,即為因數(shù)分解問題(FAC),最快方法需要T(n)=exp{c(lnnln(lnn))?}次運(yùn)算,其中c為大于1的正整數(shù)。若p≈n,解離散對(duì)數(shù)比因數(shù)分解難。

3.背包問題KnapsackProblem給定有限個(gè)自然數(shù)序列集合B=(b1,b2,…bn)及二進(jìn)制序列x=(x1,x2,…xn),xi∈(0,1),求S=∑xibi最多只需n-1次加法；但若給定B和S,求x則非常困難。窮舉時(shí)有2n種可能,當(dāng)n很大時(shí)為計(jì)算上不可行。Garey和Johnson證明,背包問題是NP問題(Non-Polynomial)單向函數(shù)舉例(續(xù))2023/8/3現(xiàn)代密碼學(xué)理論與實(shí)踐-088/682.Fa2023/9/6現(xiàn)代密碼學(xué)理論與實(shí)踐-089/68單向函數(shù)的交換性(commutativeproperty) 單向函數(shù)本身對(duì)近代密碼學(xué)領(lǐng)域用處不大，但若具有交換性，則作用大。定義8.3

交換性

令Z為一集合，F(xiàn)為將Z映射到Z本身的函數(shù)集合。令z∈Z,Fx(z)表示此函數(shù)集合之第x函數(shù),若Fx(Fy(z))=Fy(Fx(z))，則稱此函數(shù)集合具有交換性。例：D(E(m))=E(D(m))單向函數(shù)及其交換性2023/8/3現(xiàn)代密碼學(xué)理論與實(shí)踐-089/68單向函數(shù)的2023/9/6現(xiàn)代密碼學(xué)理論與實(shí)踐-0810/688.2

費(fèi)馬定理和歐拉定理定理8.1

費(fèi)馬定理Fermat’sTheorem若p是素?cái)?shù),a是正整數(shù)且不能被p整除,則ap-1modp=1證明：因?yàn)閧amodp,2amodp,...,(p-1)amodp}是{1,2,...,(p-1)}的置換形,所以,(aｘ2aｘ...ｘ(p-1)a)≡(1ｘ2ｘ...ｘ(p-1))(modp)≡(p-1)!modp.但是,aｘ2aｘ...ｘ(p-1)a=(p-1)!ap-1,因此(p-1)!ap-1≡(p-1)!modp,兩邊去掉(p-1)!,即得ap-1modp=1.例如：a=7,p=19,ap-1modp=718mod19=?72=49≡11mod1974=121≡7mod1978=49≡11mod19716=121≡7mod19ap-1=718=716x72≡7x11≡1mod192023/8/3現(xiàn)代密碼學(xué)理論與實(shí)踐-0810/688.22023/9/6現(xiàn)代密碼學(xué)理論與實(shí)踐-0811/688.2

費(fèi)馬定理和歐拉定理用a乘以集合中所有元素并對(duì)p取模，則得到集合X={amodp,2amodp,…,(p-1)amodp}。因?yàn)閜不能整除a，所以X的元素都不等于0，而且各元素互不相等。假設(shè)ja≡ka(modp),其中1≤j<k≤p-1,因?yàn)閍和p互素，所以兩邊可以把a(bǔ)消去，則推出j≡k(modp)，而這是不可能的。因此X的p-1個(gè)元素都是正整數(shù)且互不相等。所以說X和{1,2,…,p-1}構(gòu)成相同，只是元素順序不同。2023/8/3現(xiàn)代密碼學(xué)理論與實(shí)踐-0811/688.22023/9/6現(xiàn)代密碼學(xué)理論與實(shí)踐-0812/68費(fèi)馬定理的等價(jià)形式費(fèi)馬定理等價(jià)形式ap≡amodp,p是素?cái)?shù)例如：p=5,a=3,35=243≡3mod5p=5,a=10,105=100000≡10mod5≡0mod52023/8/3現(xiàn)代密碼學(xué)理論與實(shí)踐-0812/68費(fèi)馬定理13（1）計(jì)算610mod11；（2）計(jì)算312mod11。費(fèi)馬小定理(范例)13費(fèi)馬小定理(范例)14（1）計(jì)算610mod11若p是素?cái)?shù),a是正整數(shù)且不能被p整除,則ap-1modp=1解法：我們可得610mod11=1。這是p=11時(shí)，可以使用費(fèi)馬小定理的第一個(gè)版本直接計(jì)算得到。費(fèi)馬小定理（范例）14（1）計(jì)算610mod11費(fèi)馬小定理（范例）15（2）計(jì)算312mod11ap≡amodp,p是素?cái)?shù)解法：此處指數(shù)（12）和模數(shù)（11）是不同的。費(fèi)馬小定理（范例）15（2）計(jì)算312mod11費(fèi)馬小定理（范例）2023/9/6現(xiàn)代密碼學(xué)理論與實(shí)踐-0816/68費(fèi)馬大定理（費(fèi)馬最后定理）將一個(gè)立方數(shù)分成兩個(gè)立方數(shù)之和，或一個(gè)四次冪分成兩個(gè)四次冪之和，或者一般地將一個(gè)高于二次的冪分成兩個(gè)同次冪之和，這是不可能的。關(guān)于此，我確信已發(fā)現(xiàn)了一種美妙的證法，可惜這里空白的地方太小，寫不下2023/8/3現(xiàn)代密碼學(xué)理論與實(shí)踐-0816/68費(fèi)馬大定17歐拉（Euler，Léonard，1707年4月15日—1783年9月18日）是瑞士數(shù)學(xué)家和物理學(xué)家。歐拉定理17歐拉（Euler，Léonard，1707年4月15日—2023/9/6現(xiàn)代密碼學(xué)理論與實(shí)踐-0818/68歐拉函數(shù)：Euler’sTotientFunctionφ(n)φ(n)是比n小且與n互素的正整數(shù)的個(gè)數(shù)，即模n的縮剩余系中元素之個(gè)數(shù)。2023/8/3現(xiàn)代密碼學(xué)理論與實(shí)踐-0818/68歐拉函數(shù)2023/9/6現(xiàn)代密碼學(xué)理論與實(shí)踐-0819/68歐拉函數(shù)φ(n)的證明定理8.2p和q是素?cái)?shù),n=p*q,φ(n)=φ(p)φ(q)=(p-1)(q-1)顯然，對(duì)于素?cái)?shù)p，φ(p)=p-1證明：考慮余數(shù)集合{0,1,…,(pq-1)}中不與n互素的余數(shù)集合是{p,2p,…,(q-1)p},{q,2q,…,(p-1)q}和0,所以φ(n)=pq-[(q-1)+(p-1)+1]=pq-(p+q)+1=(p-1)(q-1)=φ(p)φ(q)2023/8/3現(xiàn)代密碼學(xué)理論與實(shí)踐-0819/68歐拉函數(shù)20歐拉定理對(duì)任意互質(zhì)的a和n有：20歐拉定理21（1）若

n

是素?cái)?shù)，根據(jù)

和費(fèi)馬小定理，則上式成立；

若p是素?cái)?shù),a是正整數(shù)且不能被p整除,則ap-1modp=1（2）所有小于n，且與

n

互質(zhì)的正整數(shù)的集合歐拉定理（證明）

21（1）若n是素?cái)?shù)，根據(jù)和費(fèi)馬小22歐拉定理（證明）即每一個(gè)元素都有g(shù)cd(xi,n)=1。用a與R中的每個(gè)元素模n相乘：S是R的一個(gè)排列，因?yàn)?1)a與n互素，且xi與n互素，所以axi必與n互素，這樣S中所有元素均小于n且與n互素。(2)S中沒有重復(fù)元素，所以集合S是集合R的一個(gè)置換。22歐拉定理（證明）即每一個(gè)元素都有g(shù)cd(xi,n)=1。23歐拉定理（證明）23歐拉定理（證明）2023/9/6現(xiàn)代密碼學(xué)理論與實(shí)踐-0824/688.4ChineseRemainderTheorem

中國(guó)余數(shù)定理CRT說明某一范圍內(nèi)的整數(shù)可通過它對(duì)兩兩互素的整數(shù)取模所得的余數(shù)來重構(gòu)Z10(0,1,…,9)中的10個(gè)整數(shù)可通過它們對(duì)2和5(10的素因子)取模所得的兩個(gè)余數(shù)來重構(gòu).假設(shè)數(shù)x的余數(shù)r2=0且r5=3,即xmod2=0,xmod5=3,則x是Z10中的偶數(shù)且被5除余3,唯一解x=8.一種CRT的表示形式令M=mi,其中mi兩兩互素,1<=i,j<=k,i≠j,gcd(mi,mj)=1將Zm中的任一整數(shù)對(duì)應(yīng)一個(gè)k元組,該k元組的元素均在Zmi中,對(duì)應(yīng)關(guān)系為A?(a1,a2,…,ak),其中A∈Zm,對(duì)1<=i<=k,ai∈Zmi,且ai=Amodmi2023/8/3現(xiàn)代密碼學(xué)理論與實(shí)踐-0824/688.42023/9/6現(xiàn)代密碼學(xué)理論與實(shí)踐-0825/688.4ChineseRemainderTheorem

斷言一對(duì)任何A，0≤A≤M，有唯一的k元組(a1,a2,…,ak)與之對(duì)應(yīng)，其中0≤ai<mi，并且對(duì)任何這樣的k元組(a1,a2,…,ak)，ZM中有唯一的A與之對(duì)應(yīng)。

2023/8/3現(xiàn)代密碼學(xué)理論與實(shí)踐-0825/688.42023/9/6現(xiàn)代密碼學(xué)理論與實(shí)踐-0826/688.4ChineseRemainderTheorem

由A到(a1,a2,…,ak)的轉(zhuǎn)換顯然是唯一確定的。即只需取ai=Amodmi。對(duì)給定的(a1,a2,…,ak)，可如下計(jì)算A。2023/8/3現(xiàn)代密碼學(xué)理論與實(shí)踐-0826/688.42023/9/6現(xiàn)代密碼學(xué)理論與實(shí)踐-0827/688.4ChineseRemainderTheorem

第二個(gè)斷言與算術(shù)運(yùn)算有關(guān)，可從模算術(shù)規(guī)則推出2023/8/3現(xiàn)代密碼學(xué)理論與實(shí)踐-0827/688.42023/9/6現(xiàn)代密碼學(xué)理論與實(shí)踐-0828/68ChineseRemainderTheorem

定理8.7

中國(guó)余數(shù)定理,ChineseRemainderTheorem

令d1,…,dt兩兩互素,n=d1d2…dt,則

xmoddi=xi,i=1,…,t在[0,n-1]中有一個(gè)公共解x.證明：對(duì)每一個(gè)I,i=1,…,t,gcd(di,)=1,存在yi,使得

()yimoddi=1;進(jìn)一步地,()yimoddj=0,j≠i,(因?yàn)閐j是()的一個(gè)因數(shù))令x=[()yixi]modn. ∵xmoddi=()yiximoddi=xi,(()yimoddi=1)

∴x是xmoddi=xi(1≤i≤t)的公共解。2023/8/3現(xiàn)代密碼學(xué)理論與實(shí)踐-0828/68Chin2023/9/6現(xiàn)代密碼學(xué)理論與實(shí)踐-0829/68孫子定理(孫子算經(jīng),3-5世紀(jì))今有物不知其數(shù),三三數(shù)之剩二,五五數(shù)之剩三,七七數(shù)之剩二,問物幾何。

xmod3=2 n=3*5*7=105 xmod5=3 d1=3,d2=5,d3=7 xmod7=2 x1=2,x2=3,x3=22023/8/3現(xiàn)代密碼學(xué)理論與實(shí)踐-0829/68孫子定理2023/9/6現(xiàn)代密碼學(xué)理論與實(shí)踐-0830/68孫子定理(孫子算經(jīng),3-5世紀(jì))今有物不知其數(shù),三三數(shù)之剩二,五五數(shù)之剩三,七七數(shù)之剩二,問物幾何。

xmod3=2 n=3*5*7=105 xmod5=3 d1=3,d2=5,d3=7 xmod7=2 x1=2,x2=3,x3=2(1)求yi，()yimoddi=1

()y1mod3=1 ()y2mod5=1 ()y3mod7=1

得：35y1mod3=1 y1=2 21y2mod5=1 y2=1 15y3mod7=1 y3=1(2)x=(35×2×2＋21×1×3＋15×1×2)mod105=232023/8/3現(xiàn)代密碼學(xué)理論與實(shí)踐-0830/68孫子定理2023/9/6現(xiàn)代密碼學(xué)理論與實(shí)踐-0831/688.5離散對(duì)數(shù)(discretelogarithm)冪運(yùn)算是相對(duì)容易的,求解離散對(duì)數(shù)通常是難解問題離散對(duì)數(shù)是包括Diffie-Hellman密鑰交換和數(shù)字簽名(DSA)在內(nèi)的許多公鑰算法的基礎(chǔ)。2023/8/3現(xiàn)代密碼學(xué)理論與實(shí)踐-0831/688.52023/9/6現(xiàn)代密碼學(xué)理論與實(shí)踐-0832/68DiscreteLogarithms模n的整數(shù)冪根據(jù)歐拉定理(定理8.3),aφ(n)modn=1.考慮歐拉定理更一般的形式：ammodn=1,gcd(a,n)=1,至少有一個(gè)整數(shù)m滿足ammodn=1,即m=φ(n),使其成立的最小