《物聯(lián)網(wǎng)信息安全》課件第2章

2.1數(shù)論2.2群環(huán)域2.3算法復(fù)雜度理論2.4公鑰密碼學(xué)2.5信息論2.6概率論第2章物聯(lián)網(wǎng)信息安全的數(shù)學(xué)基礎(chǔ)

2.1數(shù)論

數(shù)論是研究整數(shù)性質(zhì)的一門理論。素?cái)?shù)是組成整數(shù)的基本元素，數(shù)論的本質(zhì)是對(duì)素?cái)?shù)性質(zhì)的研究。人們對(duì)于數(shù)論的研究非常早，數(shù)論幾乎和平面幾何有著同樣悠久的歷史。根據(jù)研究方法，可以將數(shù)論分為初等數(shù)論和高等數(shù)論。2.1.1整除

整數(shù)集對(duì)于加法、減法和乘法三種運(yùn)算都是封閉的，但對(duì)于除法運(yùn)算是不封閉的，為此引進(jìn)整除的概念。

定義2-1

設(shè)a，b∈Z，b?≠

0，如果存在q∈Z，使得等式a?=?bq成立，那么稱b整除a或a被b整除，記作：b|a，此時(shí)b被稱為a的約數(shù)，a被稱為b的倍數(shù)。

如果不存在滿足等式a?=?bq的整數(shù)q，那么稱b不能整除a或a不能被b整除，記作：b

a。關(guān)于整除，有如下幾個(gè)簡(jiǎn)單的性質(zhì)。

設(shè)a，b，c∈Z，b?≠

0，c?≠

0，則有：

(1)如果c|b，b|a，那么c|a；

(2)如果b|a，那么bc|ac，反之亦真；

(3)如果c|a，c|b，那么，對(duì)于任意m，n∈Z，有c|(ma?+?nb)；

(4)如果b|a，a≠0，那么|b|≤|a|；

(5)如果b|a，a|b，那么|b|

=

|a|。

定理2-1(帶余除法)設(shè)a，b∈Z，b?≠

0，則存在q，r∈Z，使得a?=?bq?+?r，0≤r<|b|，并且q，r是唯一的。

證明存在性。當(dāng)b|a時(shí)，取q?=?a/b，r?=

0即可。

當(dāng)b

a時(shí)，考慮集合E?=

{a－bk|k∈Z}，易知E中有正整數(shù)，因此E中有最小正整數(shù)，設(shè)為r?=?a－bk>0，下證r?<

|b|。

因?yàn)閎

a，所以r?≠

|b|，若r>|b|，則存在r′=r－|b|>0，又r′∈E，故與r的最小性矛盾，從而存在q，r∈Z，使得a=bq+r，0≤r<|b|。

唯一性。設(shè)另有q′，r′∈Z，使得a?=?bq′+?r′，0≤r′<|b|，則b(q－q′)=r′－r，于是b|(r′－r)，但由于0≤|r′－r|<|b|，故r′－r=0，即r=r′，從而q=q′。

定義2-2

等式a?=?bq+r，0≤r<|b|中的整數(shù)q稱為a被b除所得的(不完全)商，整數(shù)r稱為a被b除所得的余數(shù)。

例2-1

設(shè)b?=?15，則

當(dāng)a?=?255時(shí)，a?=?17b?+?0，故q?=?17，r?=?0；

當(dāng)a?=?417時(shí)，a?=?27b?+?12，故q?=?27，r?=?12；

當(dāng)a?=?-81時(shí)，a?=?－6b?+?9，故q?=?－6，r?=?9。2.1.2最大公約數(shù)

定義2-3

最大公約數(shù)：設(shè)a，b是兩個(gè)整數(shù)，若整數(shù)d滿足d|a并且d|b，則稱d為a，b的一個(gè)公約數(shù)；公約數(shù)中最大的一個(gè)稱為最大公約數(shù)，記作：gcd(a，b)，可簡(jiǎn)記為(a，b)。

若gcd(a，b)?=?1，則稱a，b互素。

最大公約數(shù)是數(shù)論中的一個(gè)重要概念，迄今為止有多種求最大公約數(shù)的算法，其中最為著名的是由古希臘學(xué)者歐幾里得提出的輾轉(zhuǎn)相除法，又稱為歐幾里德算法(Euclideanalgorithm)，是目前已知的最古老的算法。輾轉(zhuǎn)相除法是現(xiàn)代數(shù)論中的基本工具，有很多重要的應(yīng)用，它是RSA算法(一種在電子商務(wù)中廣泛使用的公鑰加密算法)的重要部分。輾轉(zhuǎn)相除法基于如下原理：兩個(gè)正整數(shù)a與b(a>b)的最大公約數(shù)等于其中較小的數(shù)b和兩數(shù)相除的余數(shù)r的最大公約數(shù)。令r0?=?a，r1?=?b，輾轉(zhuǎn)相除法過程如下：直到

其中

定理2-2

設(shè)兩數(shù)為a、b(b<a)，r?=?amodb，為a除以b以后的余數(shù)，k為a除以b的商，則gcd(a，b)?=?gcd(b，r)。

證明

第一步：令c?=?gcd(a，b)，則可設(shè)a?=?mc，b?=?nc。

第二步：根據(jù)前提可知r?=?a－kb?=mc－knc=(m－kn)c。

第三步：根據(jù)第二步結(jié)果可知c也是r的因數(shù)。

第四步：可以斷定m－kn與n互素。否則，可設(shè)m－kn=xd,n=yd，(d?>

1)，則m?=?kn?+?xd?=?kyd?+?xd?=?(ky?+?x)d，則a?=?mc?=?(ky?+?x)dc，b?=?nc?=?ycd，故a與b的最大公約數(shù)為cd，而非c，與前面結(jié)論矛盾。

從而可知gcd(b，r)?=?c，繼而gcd(a，b)?=?gcd(b，r)。

例2-2

利用輾轉(zhuǎn)相除法求4081與20723的最大公約數(shù)。

解根據(jù)輾轉(zhuǎn)相除法可以進(jìn)行如下計(jì)算：

20723?=?4081?×?5?+?318

4081?=?318?×?12?+?265

318?=?265?×?1?+?53

265?=?53?×?5?+?0

所以gcd(4081，20?723)?=?53

例2-3

利用輾轉(zhuǎn)相除法求8251和6105的最大公約數(shù)。

解根據(jù)輾轉(zhuǎn)相除法可以進(jìn)行如下計(jì)算：

8251?=?6105?×?1?+?2146

6105?=?2146?×?2?+?1813

2146?=?1813?×?1?+?333

1813?=?333?×?5?+?148

333?=?148?×?2?+?37

148?=?37?×?4?+?0

所以37為8251與6105的最大公約數(shù)。輾轉(zhuǎn)相除法在計(jì)算機(jī)上很容易實(shí)現(xiàn)，可以使用迭代或者遞歸的策略。兩種策略對(duì)應(yīng)的C程序設(shè)計(jì)如下：

迭代策略：遞歸策略：2.1.3模運(yùn)算與同余關(guān)系

定義2-4

模運(yùn)算：如果a是一個(gè)整數(shù)，n是一個(gè)正整數(shù)，a除以n的余數(shù)r可以用a?(modn)表示，n稱為模，因此求余數(shù)的運(yùn)算也被稱為模運(yùn)算。在模運(yùn)算的意義下，很容易定義如下幾種運(yùn)算，設(shè)正整數(shù)p和整數(shù)a，b，則有

模p加法：(a?+?b)modp，其結(jié)果是a?+?b的算術(shù)和除以p的余數(shù)；

模p減法：(a－b)modp，其結(jié)果是a?-?b的算術(shù)差除以p的余數(shù)；

模p乘法：(a?×?b)modp，其結(jié)果是a?×?b的算術(shù)積除以p的余數(shù)。

定義2-5

同余關(guān)系：給定正整數(shù)m，如果整數(shù)a與b模m的余數(shù)相同，或者說a與b之差能被m整除，則稱a與b對(duì)于模m同余，或稱a與b同余，模為m，記為

a

b(modm)

很明顯同余關(guān)系是一個(gè)等價(jià)關(guān)系，具有如下三個(gè)基本性質(zhì)：

(1)自反性：a?≡?a(modm)。

(2)對(duì)稱性：若a?≡?b(modm)，則b?≡a(modm)。

(3)傳遞性：若a≡?b(modm)，b?≡?c(modm)，則

a≡?c(modm)。2.1.4中國剩余定理

定義2-6

一次同余方程：同余式

是含有一個(gè)未知量x的一次式，叫做一次同余方程。若存在

代入上述方程使兩邊同余，則c為上述方程的一個(gè)解。上述方程的兩個(gè)解c1和c2看做相同當(dāng)且僅當(dāng)

時(shí)。

定理2-3

設(shè)，則一次同余方程有且只有一個(gè)解。

對(duì)于如下一次同余方程組其中為大于1的整數(shù)，兩兩互素，

是任意給定的整數(shù)。如果帶入方程組使得同余式同時(shí)都成立，則c叫做上述方程組的解。上述方程組的兩個(gè)解c1和c2看做相同當(dāng)且僅當(dāng)時(shí)。

定理2-4

孫子定理：設(shè)上面一次同余方程組中大于1的整數(shù)兩兩互素，是任意給定的整數(shù)，則一次同余方程組有且只有一個(gè)解。2.1.5素?cái)?shù)

定義2-7

素?cái)?shù)：又稱質(zhì)數(shù)，指在一個(gè)大于1的自然數(shù)中，除了1和此整數(shù)自身外，不能被其他自然數(shù)整除的數(shù)。素?cái)?shù)在數(shù)論中有著很重要的地位，是數(shù)論研究的中心內(nèi)容。我國著名數(shù)學(xué)家陳景潤研究的“哥德巴赫猜想”與“孿生素?cái)?shù)猜想”都是關(guān)于素?cái)?shù)的。

定義2-8

合數(shù)：是指除了1和它本身兩個(gè)因數(shù)外，還有其他因數(shù)的數(shù)。

由2?÷?1?=?2，2?÷?2?=?1，可知2的因數(shù)只有1和它本身2這兩個(gè)約數(shù)，所以2是素?cái)?shù)。由于4?÷?1?=?4，4?÷?2?=?2，4?÷?4?=?1，很顯然，4的因數(shù)除了1和它本身4這兩個(gè)因數(shù)以外，還有因數(shù)2，所以4是合數(shù)。100以內(nèi)的質(zhì)數(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，共有25個(gè)。

注：(1)?1既不是質(zhì)數(shù)也不是合數(shù)，因?yàn)樗星抑挥?這一個(gè)因數(shù)。

(2)?2和3是所有素?cái)?shù)中唯一兩個(gè)連著的數(shù)。

(3)?2是唯一一個(gè)為偶數(shù)的素?cái)?shù)。

定理2-5

素?cái)?shù)的個(gè)數(shù)是無窮的。

關(guān)于素?cái)?shù)的無窮性的證明有很多版本，最經(jīng)典的來自于歐幾里得。證明的思路是使用反證法。

證明假設(shè)質(zhì)數(shù)只有有限的n個(gè)，從小到大依次排列為p1，p2，…，pn，設(shè)N?=?p1?×?p2?×?…?×?pn，那么，N+1是不能被p1，p2，…，pn中的任意一個(gè)數(shù)整除的，所以N+1是素?cái)?shù)。這與假設(shè)只有n個(gè)素?cái)?shù)矛盾，所以可得出素?cái)?shù)是無限多的。

關(guān)于素?cái)?shù)在自然數(shù)中的分布規(guī)律，一直是數(shù)論學(xué)者研究的重點(diǎn)。一個(gè)個(gè)單獨(dú)來看，素?cái)?shù)在自然數(shù)中的出現(xiàn)沒有什么規(guī)律?？墒强傮w地看，素?cái)?shù)的個(gè)數(shù)是有規(guī)可循的。

素?cái)?shù)定理對(duì)素?cái)?shù)在自然數(shù)中的分布做出了一定的回答。

定理2-6

設(shè)是小于x的素?cái)?shù)的個(gè)數(shù)，則,

當(dāng)時(shí)，比值。

該結(jié)果最早為德國數(shù)學(xué)家高斯發(fā)現(xiàn)，嚴(yán)格的證明來自于法國數(shù)學(xué)家哈達(dá)瑪。

定義2-9

歐拉函數(shù)：對(duì)于正整數(shù)n，將0，1，2，…，n－1中與n互素的整數(shù)的個(gè)數(shù)記作φ(n)，稱作歐拉函數(shù)。

例2-5

計(jì)算j(8)與j(10)。

解因?yàn)?，3，5，7均和8互素，所以j

(8)?=?4；

因?yàn)?，3，7，9均和10互素，所以j

(10)?=?4。

歐拉函數(shù)是數(shù)論中的一個(gè)重要函數(shù)，下面給出歐拉函數(shù)的一些基本性質(zhì)。

(1)若p是素?cái)?shù)，則j

(p)?=?p－1。

(2)若n是素?cái)?shù)p的k次冪，則j

(n)?=?(p－1)p(k－1)，因?yàn)槌藀的倍數(shù)外都與p互素。

(3)歐拉函數(shù)是積性函數(shù)，若，則j

(mn)?=?j(m)j(n)。

根據(jù)性質(zhì)(2)和(3)，很容易根據(jù)數(shù)學(xué)歸納法得到性質(zhì)(4)：

(4)設(shè),為不同素?cái)?shù)，ei≥1，則

(5)。

定理2-7

歐拉定理：若n與a為正整數(shù)，且n與a互素，即(a，n)?=?1，則

即與1在模n下同余，其中為歐拉函數(shù)。

例2-6

令a?=?3，n?=?5。比5小的正整數(shù)中與5互素的數(shù)有1、2、3和4，所以。3與5互素，則根據(jù)歐拉定理可知

另一方面34?=?81，而1(mod5)，與定理結(jié)果相符。

定理2-8

費(fèi)馬小定理：假如p是一個(gè)質(zhì)數(shù)，而且(a，p)=1,則

定義2-10

整數(shù)模n的剩余類：對(duì)于一個(gè)給定的模數(shù)n，全體整數(shù)按照模n同余分成一些等價(jià)類，此時(shí)的等價(jià)類被稱為整數(shù)模n的剩余類。

定義2-11

完全剩余代表系：剩余類中的任意一個(gè)元素稱為該剩余類的一個(gè)代表。從每一個(gè)剩余類中任取一個(gè)代表，由這些代表組成的集合叫做整數(shù)模n的一個(gè)完全剩余代表系，用Zn表示。

注：很明顯，集合是模n的一個(gè)完全剩余代表系。

定義2-12

模n的既約剩余代表系：從完全剩余代表系中選出與n互素的代表，組成的集合叫做模n的既約剩余代表系，用

表示。

例2-7

n?=?10，，而。

定義2-13

a對(duì)模m的指數(shù)：在(a，m)?=?1時(shí)，a對(duì)模m的指數(shù)Ordm(a)為使成立的最小的正整數(shù)d。

定義2-14

本原元：根據(jù)歐拉定理可知Ordm(a)一定小于等于j(m)，若Ordm(a)?=?j(m)，則稱a是模m的本原元。

例2-8

設(shè)m?=?7，則。

(1)設(shè)a?=?2，由于，而3<6，所以2不是模7的一個(gè)本原元。

(2)設(shè)a?=?3，由于，，

，，，,因此有，所以3是模7的一個(gè)本原元。

2.2群環(huán)域

2.2.1群論

在數(shù)學(xué)中，群是一種代數(shù)結(jié)構(gòu)，由一個(gè)集合以及一個(gè)二元運(yùn)算組成。例如整數(shù)集合上賦予加法運(yùn)算就形成一個(gè)整數(shù)加群。一個(gè)群必須滿足一些被稱為“群公理”的條件，也就是封閉性、結(jié)合律、單位元和逆元。很多熟知的數(shù)學(xué)結(jié)構(gòu)比如數(shù)系統(tǒng)都遵從這些公理。

定義2-15

代數(shù)運(yùn)算：設(shè)A是一個(gè)非空集合。任意一個(gè)由

到A的映射就稱為定義在A上的一個(gè)代數(shù)運(yùn)算。

群有許多等價(jià)定義，本書引用聶靈沼和丁石孫合著的《代數(shù)學(xué)引論》中的定義。

定義2-16

群：設(shè)G是一個(gè)非空集合，a、b為其中的元素，如果在G上定義了一個(gè)代數(shù)運(yùn)算，稱為乘法，記作ab(或稱為加法，記為a+b)，而且它滿足以下條件，那么稱G為一個(gè)群：

(1)對(duì)于G中任意元素a、b、c，有(ab)c?=?a(bc)(結(jié)合律)；

(2)?G中存在一個(gè)元素e，對(duì)G中任意元素a有ea?=?a；

(3)在G中，對(duì)于任意元素a都存在一個(gè)元素b使ba?=?e。

例2-9

全體非零實(shí)數(shù)對(duì)于通常的乘法構(gòu)成一個(gè)群，全體正實(shí)數(shù)對(duì)于通常的乘法構(gòu)成一個(gè)群，全體整數(shù)對(duì)于通常的加法構(gòu)成一個(gè)群。

設(shè)G為一個(gè)群，則它有如下基本性質(zhì)：

(1)?a、b、e∈G，如果ba=e，則ab=e；

(2)如果對(duì)所有的，有ea=a，那么也有ae=a，對(duì)所有的。

(3)?G中存在唯一的元素e，對(duì)所有的，都有

；

(4)對(duì)于群G中的任意元素a有唯一的元素b，使；

(5)對(duì)于群G中任意元素a、b，方程ax=b在G中有唯一解。

定義2-17

子群：如果群G的非空集合H對(duì)于G的運(yùn)算也成一個(gè)群，那么H稱為G的一個(gè)子群。

例2-10

整數(shù)加群：(Z，?+?)是一個(gè)生成周期為無限的循環(huán)群。

分析：這個(gè)群的單位元素是0，且如果，則它的逆元素為－a。該群的生成元素為1，因?yàn)閷?duì)任意一個(gè)正整數(shù)m均有，對(duì)于0有，對(duì)于任意負(fù)整數(shù)－m均有,

所以(Z，+)是由1所生成的群，且其周期為無限。2.2.2環(huán)理論

定義2-19

設(shè)L是一非空集合，a，b為L中的元素，在L上定義了兩個(gè)代數(shù)運(yùn)算，一個(gè)叫加法，記為a+b，一個(gè)叫乘法，記為ab，如果滿足以下條件，則稱L為環(huán)：

(1)?L對(duì)于加法構(gòu)成一個(gè)交換群；

(2)乘法的結(jié)合律：對(duì)L中任意的元素a、b、c，有(ab)c=a(bc)；

(3)乘法對(duì)于加法的分配律:對(duì)L中任意的元素a、b、c,有

例2-11

全體整數(shù)集合，在其上賦予通常的加法和乘法運(yùn)算，則構(gòu)成一個(gè)環(huán)，稱為整數(shù)環(huán)。環(huán)的基本性質(zhì)如下：

(1)用0代表環(huán)中加法群的零元素，則對(duì)于任意，有成立；

(2)對(duì)于任意，有

(3)對(duì)任意整數(shù)n、m，任意a，b

L，有

(4)對(duì)于正整數(shù)n、m，有

定理2-9

每個(gè)有限域的階必須為素?cái)?shù)的冪。

定理2-10

對(duì)于任意素?cái)?shù)p與正整數(shù)n，存在pn階域，記為GF(pn)。當(dāng)n=1時(shí)，有限域GF(p)也稱為素?cái)?shù)域。

在密碼學(xué)中，最常見的域一般為素?cái)?shù)域GF(p)或階為2m的域GF(2m)。2.2.4離散對(duì)數(shù)

為定義離散對(duì)數(shù)，首先定義一個(gè)素?cái)?shù)p的原根，為其各次冪產(chǎn)生從1到p－1的所有整數(shù)根，也就是說，如果a是素?cái)?shù)p的一個(gè)原根，那么數(shù)值

amodp，a2modp，…，ap-1modp

是各不相同的整數(shù)，并且以某種排列方式組成了從1到p-1的所有整數(shù)。

對(duì)于一個(gè)整數(shù)b和素?cái)?shù)p的一個(gè)原根a，可以找到唯一的指數(shù)i，使得

b?=?aimodp，其中0≤i≤p－1

指數(shù)i稱為b的以a為基數(shù)的模p的離散對(duì)數(shù)。

2.3算法復(fù)雜度理論

算法復(fù)雜度分為時(shí)間復(fù)雜度和空間復(fù)雜度。時(shí)間復(fù)雜度是執(zhí)行算法所需要的計(jì)算工作量的量度；而空間復(fù)雜度是執(zhí)行這個(gè)算法所需要的內(nèi)存空間的量度。2.3.1時(shí)間復(fù)雜度

一個(gè)算法執(zhí)行所耗費(fèi)的時(shí)間，從理論上是不能算出來的，必須上機(jī)運(yùn)行測(cè)試之后才能知道?，F(xiàn)實(shí)中不可能也沒有必要對(duì)每個(gè)算法都上機(jī)測(cè)試其花費(fèi)的具體時(shí)間。2.3.2空間復(fù)雜度

一個(gè)算法所需的存儲(chǔ)空間用f(n)表示，n表示問題的規(guī)模，記S(n)=O(f(n))，表示算法的空間復(fù)雜度。2.3.3圖靈機(jī)

1．基本思想

圖靈的基本思想是用機(jī)器來模擬人們用紙筆進(jìn)行數(shù)學(xué)運(yùn)算的過程，他把這樣的過程看做下列兩種簡(jiǎn)單的動(dòng)作：

(1)在紙上寫上或擦除某個(gè)符號(hào)；

(2)把注意力從紙的一個(gè)位置移動(dòng)到另一個(gè)位置。

3．停機(jī)問題

停機(jī)問題(haltingproblem)是目前邏輯數(shù)學(xué)的焦點(diǎn)，是第三次數(shù)學(xué)危機(jī)的解決方案。其本質(zhì)問題是：給定一個(gè)圖靈機(jī)T和一個(gè)任意語言集合S，T是否會(huì)最終停機(jī)于每一個(gè)。其意義類似于可確定語言。顯然任意有限S是可判定性的，可數(shù)的(countable)?S也是可停機(jī)的。

4．圖靈機(jī)的變體

圖靈機(jī)有很多變種，但可以證明這些變種的計(jì)算能力都是等價(jià)的，即它們識(shí)別同樣的語言類。證明兩個(gè)計(jì)算模型A和B的計(jì)算能力等價(jià)的基本思想是：用A和B相互模擬，若A可模擬B且B可模擬A，則它們的計(jì)算能力等價(jià)。注意這里我們暫時(shí)不考慮計(jì)算的效率，只考慮計(jì)算的理論“可行性”。

5．非確定型圖靈機(jī)

如果不加特殊說明，通常所說的圖靈機(jī)都是確定型圖靈機(jī)。

非確定型圖靈機(jī)和確定型圖靈機(jī)的不同之處在于，在計(jì)算的每一時(shí)刻，根據(jù)當(dāng)前狀態(tài)和讀寫頭所讀的符號(hào)，機(jī)器存在多種狀態(tài)轉(zhuǎn)移方案，機(jī)器將任意地選擇其中一種方案繼續(xù)運(yùn)作，直到最后停機(jī)為止。具體而言，其狀態(tài)轉(zhuǎn)移函數(shù)為其中：Q是狀態(tài)集合，是帶字母表，L、R分別表示讀寫頭向左和向右移動(dòng)，符號(hào)2A表示集合A的冪集，即

6．P與NP問題

復(fù)雜度類P即為所有可以由一個(gè)確定型圖靈機(jī)在多項(xiàng)式表達(dá)的時(shí)間內(nèi)解決的問題；類NP為由所有可以在多項(xiàng)式表達(dá)的時(shí)間內(nèi)驗(yàn)證解是否正確的決定問題組成，或者等效地說，那些解可以在非確定型圖靈機(jī)上在多項(xiàng)式表達(dá)的時(shí)間內(nèi)找出的問題的集合。

2.4公?鑰?密?碼?學(xué)

2.4.1基本概念

公鑰密碼學(xué)，又稱非對(duì)稱鑰匙密碼學(xué)，相對(duì)于對(duì)稱鑰匙密碼學(xué)，其最大的特點(diǎn)在于加密和解密使用不同的鑰匙。在對(duì)稱鑰匙密碼學(xué)中，加密和解密使用相同的鑰匙，也許對(duì)不同的信息使用不同的鑰匙，但都面臨鑰匙管理的難題。由于每對(duì)通信方都必須使用異于其他組的鑰匙，當(dāng)網(wǎng)絡(luò)成員的數(shù)量增加時(shí)，鑰匙數(shù)量成二次方增加。2.4.2RSA算法

1978年，MIT的RonRivest、AdiShamir和LenAdleman提出了公鑰加密算法RSA。RSA取名來自開發(fā)者的名字。RSA是目前最有影響力的公鑰加密算法，它能夠抵抗到目前為止已知的所有密碼攻擊，已被ISO推薦為公鑰數(shù)據(jù)加密標(biāo)準(zhǔn)。RSA算法基于一個(gè)十分簡(jiǎn)單的數(shù)論事實(shí)：將兩個(gè)大素?cái)?shù)相乘十分容易，但想要對(duì)其乘積進(jìn)行因式分解卻極其困難，因此可以將乘積公開作為加密密鑰。假設(shè)Alice想要通過一個(gè)不可靠的媒體接收Bob的一條私人信息，她可以用以下的方式來產(chǎn)生一個(gè)公鑰和一個(gè)私鑰：

(1)隨意選擇兩個(gè)大的素?cái)?shù)p和q，p不等于q，計(jì)算N=pq；

(2)根據(jù)歐拉函數(shù)，求得r=j(n)=j(p)j(q)=(p－1)(q－1)；

(3)選擇一個(gè)小于r的整數(shù)e，求得e關(guān)于模r的模反元素，命名為d(模反元素存在，當(dāng)且僅當(dāng)e與r互質(zhì)時(shí))；

(4)將p和q的記錄銷毀。

(N，e)是公鑰，(N，d)是私鑰。Alice將她的公鑰(N，e)傳給Bob，而將她的私鑰(N，d)藏起來。加密消息：

假設(shè)Bob想給Alice送一個(gè)消息m，他知道Alice產(chǎn)生的N和e，使用事先與Alice約好的格式將m轉(zhuǎn)換為一個(gè)小于N的整數(shù)n，比如他可以將每一個(gè)字轉(zhuǎn)換為這個(gè)字的Unicode碼，然后將這些數(shù)字連在一起組成一串?dāng)?shù)字。假如他的信息非常長的話，他可以將這個(gè)信息分為幾段，然后將每一段轉(zhuǎn)換為n，用下面這個(gè)公式他可以將n加密為c：

計(jì)算c并不復(fù)雜。Bob算出c后就可以將它傳遞給Alice。解密消息：

Alice得到Bob的消息c后就可以利用她的密鑰d來解碼。她可以用以下這個(gè)公式來將c轉(zhuǎn)換為n：

得到n后，她可以將原來的信息m重新復(fù)原。

解碼的原理是：由費(fèi)馬小定理可證明(因?yàn)閜和q是素?cái)?shù))

這說明(p和q互素)2.4.3單向陷門函數(shù)

定義2-23

單向函數(shù)：

一函數(shù)f若滿足下列兩個(gè)條件，則稱f為單向函數(shù)：

(1)對(duì)于所有屬于f定義域的任一x，可以很容易計(jì)算f(x)?=?y；

(2)對(duì)于幾乎所有屬于f值域的任一y，在計(jì)算上不可能(ComputationallyInfeasible)求出x，使得y?=?f(x)。

定義2-24

單向陷門函數(shù)：

(1)正向計(jì)算容易。給定x、k1，計(jì)算是容易的；

(2)反向計(jì)算可行，但要知道k2。給定y與k2，計(jì)算

是容易的；

(3)不知道k2，反向計(jì)算不可行。即給定y，不知道k2，計(jì)算x是不可行的，將k2稱為陷門信息。常見的單向陷門函數(shù)有以下幾種。

1．大整數(shù)分解

已知兩個(gè)大素?cái)?shù)p和q，求n=pq只需要一次乘法，但若由n求出p和q，則是幾千年來數(shù)論學(xué)者的攻克對(duì)象。當(dāng)n很大時(shí)，則非常困難。已有的大整數(shù)分解的算法有試除法、二次篩選法、數(shù)域篩選法等。迄今為止，關(guān)于大整數(shù)分解尚未發(fā)現(xiàn)快速算法。

2．離散對(duì)數(shù)

設(shè)p是一個(gè)素?cái)?shù)，是其生成元，已知，求

，稱為在模運(yùn)算意義下的冪指數(shù)運(yùn)算。但是，反過來，若成立，已知y求x的問題稱為在模運(yùn)算意義下的離散對(duì)數(shù)問題(DLP)。

3．多項(xiàng)式求根

有限域GF(p)上的一個(gè)多項(xiàng)式,

當(dāng)給定時(shí)，易于求y。反之，已知

，求解x，需對(duì)高次方程求根。當(dāng)n、p很大時(shí)很難求解。

4．背包問題

已知向量，ai為正整數(shù)，給定向量

，，求和是容易的。但反過來，已知y和A，求x非常困難，稱這個(gè)問題為背包問題。背包問題用窮舉法有2n種可能，當(dāng)n很大時(shí)，求解相當(dāng)困難，已證明這是一個(gè)非多項(xiàng)式時(shí)間可解的問題。

5．二次剩余問題

設(shè)n為正整數(shù)，若存在整數(shù)a，滿足(a,n)=1，且x2=amodn有解，則稱a為模n的二次剩余，否則a稱為模n的二次非剩余，用QRn表示所有模n的二次剩余集合。給定正奇合數(shù)n，取

x=1,2,…,n－1，計(jì)算x2modn可得所有模n的二次剩余集合。但是，反過來，給定奇合數(shù)n和整數(shù)a，判定a是否是模n的二次剩余是困難的。

2.5信息論

定義2-25

設(shè)一個(gè)離散隨機(jī)變量，令xi出現(xiàn)的概率為P(xi)≥0，1≤i≤n，且，事件xi所包含的信息定義為

定義2-26

將集合X中事件所包含的信息量統(tǒng)計(jì)平均，則平均值

稱為集合X的熵。式中采用以2為底的對(duì)數(shù)運(yùn)算，信息的單位為比特(bit)。集合X和Y的聯(lián)合熵定義為

集合X相對(duì)于事件的條件熵定義為集合X相對(duì)于集合Y的條件熵定義為

定理2-110≤H(X)≤lbn。當(dāng)且僅當(dāng)對(duì)某一i有p(xi)=1，對(duì)其他的時(shí)，有p(xj)?=?0，H(X)=0；當(dāng)且僅當(dāng)對(duì)一切1≤i≤n，有時(shí)，H(X)=lb?n。

定理2-12

推論若H(X|Y)≤H(X)，當(dāng)且僅當(dāng)X與Y相互統(tǒng)計(jì)獨(dú)立時(shí)，等號(hào)成立。

2.6概率論

2.6.1概率論的基本概念

定義2-27

隨機(jī)試驗(yàn)：隨機(jī)現(xiàn)象是相對(duì)于決定性現(xiàn)象而言的，通常在概率論中把符合下面三個(gè)特點(diǎn)的試驗(yàn)叫做隨機(jī)試驗(yàn)：

(1)每次試驗(yàn)的可能結(jié)果不止一個(gè)，并且能事先明確試驗(yàn)的所有可能結(jié)果；

(2)進(jìn)行一次試驗(yàn)之前無法確定哪一個(gè)結(jié)果會(huì)出現(xiàn)；

(3)可以在同一條件下重復(fù)進(jìn)行試驗(yàn)。

定義2-28

單位事件：是在一次隨機(jī)試驗(yàn)中可能發(fā)生的不能再細(xì)分的結(jié)果，又被稱為基本事件。

定義2-29

事件空間：隨機(jī)試驗(yàn)所有可能發(fā)生的單位事件的集合，又稱為樣本空間。

定義2-30

隨機(jī)事件：是事件空間S的子集，它由事件空間S中的單位元素構(gòu)成。

定義2-31

設(shè)隨機(jī)事件的樣本空間為Ω，對(duì)于Ω中的每一個(gè)事件A，都有實(shí)函數(shù)P(A)，滿足：

(1)非負(fù)性：P(A)≥0；

(2)規(guī)范性：P(Ω)?=?1；

(3)可加性：對(duì)n個(gè)兩兩互斥事件A1，…，An有

任意一個(gè)滿足上述條件的函數(shù)P都可以作為樣本空間Ω的概率函數(shù)，稱函數(shù)值P(A)為Ω中事件A的概率。2.6.2基本性質(zhì)

事件與集合的性質(zhì)非常相似，所以很容易理解下面的性質(zhì)。

(1)互補(bǔ)原則：定義一個(gè)事件的補(bǔ)事件為，則。

(2)不可能事件的概率為零：。

(3)如果事件A1,A2,…,An中的任意兩者不相交，則和事件的概率等于單個(gè)事件的概率之和，即

(4)?。

(5)加法法則：對(duì)于事件空間中的任意兩個(gè)事件A和B都有

(6)乘法法則：事件A與B同時(shí)發(fā)生的概率為

(7)無關(guān)事件乘法法則：兩個(gè)不相關(guān)聯(lián)