《物聯網信息安全》課件第2章

2.1數論2.2群環(huán)域2.3算法復雜度理論2.4公鑰密碼學2.5信息論2.6概率論第2章物聯網信息安全的數學基礎

2.1數論

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

整數集對于加法、減法和乘法三種運算都是封閉的，但對于除法運算是不封閉的，為此引進整除的概念。

定義2-1

設a，b∈Z，b?≠

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

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

a。關于整除，有如下幾個簡單的性質。

設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，那么，對于任意m，n∈Z，有c|(ma?+?nb)；

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

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

=

|a|。

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

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

證明存在性。當b|a時，取q?=?a/b，r?=

0即可。

當b

a時，考慮集合E?=

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

|b|。

因為b

a，所以r?≠

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

唯一性。設另有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|中的整數q稱為a被b除所得的(不完全)商，整數r稱為a被b除所得的余數。

例2-1

設b?=?15，則

當a?=?255時，a?=?17b?+?0，故q?=?17，r?=?0；

當a?=?417時，a?=?27b?+?12，故q?=?27，r?=?12；

當a?=?-81時，a?=?－6b?+?9，故q?=?－6，r?=?9。2.1.2最大公約數

定義2-3

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

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

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

其中

定理2-2

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

證明

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

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

第三步：根據第二步結果可知c也是r的因數。

第四步：可以斷定m－kn與n互素。否則，可設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的最大公約數為cd，而非c，與前面結論矛盾。

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

例2-2

利用輾轉相除法求4081與20723的最大公約數。

解根據輾轉相除法可以進行如下計算：

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

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

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

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

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

例2-3

利用輾轉相除法求8251和6105的最大公約數。

解根據輾轉相除法可以進行如下計算：

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的最大公約數。輾轉相除法在計算機上很容易實現，可以使用迭代或者遞歸的策略。兩種策略對應的C程序設計如下：

迭代策略：遞歸策略：2.1.3模運算與同余關系

定義2-4

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

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

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

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

定義2-5

同余關系：給定正整數m，如果整數a與b模m的余數相同，或者說a與b之差能被m整除，則稱a與b對于模m同余，或稱a與b同余，模為m，記為

a

b(modm)

很明顯同余關系是一個等價關系，具有如下三個基本性質：

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

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

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

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

定義2-6

一次同余方程：同余式

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

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

時。

定理2-3

設，則一次同余方程有且只有一個解。

對于如下一次同余方程組其中為大于1的整數，兩兩互素，

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

定理2-4

孫子定理：設上面一次同余方程組中大于1的整數兩兩互素，是任意給定的整數，則一次同余方程組有且只有一個解。2.1.5素數

定義2-7

素數：又稱質數，指在一個大于1的自然數中，除了1和此整數自身外，不能被其他自然數整除的數。素數在數論中有著很重要的地位，是數論研究的中心內容。我國著名數學家陳景潤研究的“哥德巴赫猜想”與“孿生素數猜想”都是關于素數的。

定義2-8

合數：是指除了1和它本身兩個因數外，還有其他因數的數。

由2?÷?1?=?2，2?÷?2?=?1，可知2的因數只有1和它本身2這兩個約數，所以2是素數。由于4?÷?1?=?4，4?÷?2?=?2，4?÷?4?=?1，很顯然，4的因數除了1和它本身4這兩個因數以外，還有因數2，所以4是合數。100以內的質數有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個。

注：(1)?1既不是質數也不是合數，因為它有且只有1這一個因數。

(2)?2和3是所有素數中唯一兩個連著的數。

(3)?2是唯一一個為偶數的素數。

定理2-5

素數的個數是無窮的。

關于素數的無窮性的證明有很多版本，最經典的來自于歐幾里得。證明的思路是使用反證法。

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

關于素數在自然數中的分布規(guī)律，一直是數論學者研究的重點。一個個單獨來看，素數在自然數中的出現沒有什么規(guī)律?？墒强傮w地看，素數的個數是有規(guī)可循的。

素數定理對素數在自然數中的分布做出了一定的回答。

定理2-6

設是小于x的素數的個數，則,

當時，比值。

該結果最早為德國數學家高斯發(fā)現，嚴格的證明來自于法國數學家哈達瑪。

定義2-9

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

例2-5

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

解因為1，3，5，7均和8互素，所以j

(8)?=?4；

因為1，3，7，9均和10互素，所以j

(10)?=?4。

歐拉函數是數論中的一個重要函數，下面給出歐拉函數的一些基本性質。

(1)若p是素數，則j

(p)?=?p－1。

(2)若n是素數p的k次冪，則j

(n)?=?(p－1)p(k－1)，因為除了p的倍數外都與p互素。

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

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

根據性質(2)和(3)，很容易根據數學歸納法得到性質(4)：

(4)設,為不同素數，ei≥1，則

(5)。

定理2-7

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

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

例2-6

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

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

定理2-8

費馬小定理：假如p是一個質數，而且(a，p)=1,則

定義2-10

整數模n的剩余類：對于一個給定的模數n，全體整數按照模n同余分成一些等價類，此時的等價類被稱為整數模n的剩余類。

定義2-11

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

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

定義2-12

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

表示。

例2-7

n?=?10，，而。

定義2-13

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

定義2-14

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

例2-8

設m?=?7，則。

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

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

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

2.2群環(huán)域

2.2.1群論

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

定義2-15

代數運算：設A是一個非空集合。任意一個由

到A的映射就稱為定義在A上的一個代數運算。

群有許多等價定義，本書引用聶靈沼和丁石孫合著的《代數學引論》中的定義。

定義2-16

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

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

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

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

例2-9

全體非零實數對于通常的乘法構成一個群，全體正實數對于通常的乘法構成一個群，全體整數對于通常的加法構成一個群。

設G為一個群，則它有如下基本性質：

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

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

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

；

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

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

定義2-17

子群：如果群G的非空集合H對于G的運算也成一個群，那么H稱為G的一個子群。

例2-10

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

分析：這個群的單位元素是0，且如果，則它的逆元素為－a。該群的生成元素為1，因為對任意一個正整數m均有，對于0有，對于任意負整數－m均有,

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

定義2-19

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

(1)?L對于加法構成一個交換群；

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

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

例2-11

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

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

(2)對于任意，有

(3)對任意整數n、m，任意a，b

L，有

(4)對于正整數n、m，有

定理2-9

每個有限域的階必須為素數的冪。

定理2-10

對于任意素數p與正整數n，存在pn階域，記為GF(pn)。當n=1時，有限域GF(p)也稱為素數域。

在密碼學中，最常見的域一般為素數域GF(p)或階為2m的域GF(2m)。2.2.4離散對數

為定義離散對數，首先定義一個素數p的原根，為其各次冪產生從1到p－1的所有整數根，也就是說，如果a是素數p的一個原根，那么數值

amodp，a2modp，…，ap-1modp

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

對于一個整數b和素數p的一個原根a，可以找到唯一的指數i，使得

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

指數i稱為b的以a為基數的模p的離散對數。

2.3算法復雜度理論

算法復雜度分為時間復雜度和空間復雜度。時間復雜度是執(zhí)行算法所需要的計算工作量的量度；而空間復雜度是執(zhí)行這個算法所需要的內存空間的量度。2.3.1時間復雜度

一個算法執(zhí)行所耗費的時間，從理論上是不能算出來的，必須上機運行測試之后才能知道。現實中不可能也沒有必要對每個算法都上機測試其花費的具體時間。2.3.2空間復雜度

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

1．基本思想

圖靈的基本思想是用機器來模擬人們用紙筆進行數學運算的過程，他把這樣的過程看做下列兩種簡單的動作：

(1)在紙上寫上或擦除某個符號；

(2)把注意力從紙的一個位置移動到另一個位置。

3．停機問題

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

4．圖靈機的變體

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

5．非確定型圖靈機

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

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

6．P與NP問題

復雜度類P即為所有可以由一個確定型圖靈機在多項式表達的時間內解決的問題；類NP為由所有可以在多項式表達的時間內驗證解是否正確的決定問題組成，或者等效地說，那些解可以在非確定型圖靈機上在多項式表達的時間內找出的問題的集合。

2.4公?鑰?密?碼?學

2.4.1基本概念

公鑰密碼學，又稱非對稱鑰匙密碼學，相對于對稱鑰匙密碼學，其最大的特點在于加密和解密使用不同的鑰匙。在對稱鑰匙密碼學中，加密和解密使用相同的鑰匙，也許對不同的信息使用不同的鑰匙，但都面臨鑰匙管理的難題。由于每對通信方都必須使用異于其他組的鑰匙，當網絡成員的數量增加時，鑰匙數量成二次方增加。2.4.2RSA算法

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

(1)隨意選擇兩個大的素數p和q，p不等于q，計算N=pq；

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

(3)選擇一個小于r的整數e，求得e關于模r的模反元素，命名為d(模反元素存在，當且僅當e與r互質時)；

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

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

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

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

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

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

解碼的原理是：由費馬小定理可證明(因為p和q是素數)

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

定義2-23

單向函數：

一函數f若滿足下列兩個條件，則稱f為單向函數：

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

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

定義2-24

單向陷門函數：

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

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

是容易的；

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

1．大整數分解

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

2．離散對數

設p是一個素數，是其生成元，已知，求

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

3．多項式求根

有限域GF(p)上的一個多項式,

當給定時，易于求y。反之，已知

，求解x，需對高次方程求根。當n、p很大時很難求解。

4．背包問題

已知向量，ai為正整數，給定向量

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

5．二次剩余問題

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

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

2.5信息論

定義2-25

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

定義2-26

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

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

集合X相對于事件的條件熵定義為集合X相對于集合Y的條件熵定義為

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

定理2-12

推論若H(X|Y)≤H(X)，當且僅當X與Y相互統(tǒng)計獨立時，等號成立。

2.6概率論

2.6.1概率論的基本概念

定義2-27

隨機試驗：隨機現象是相對于決定性現象而言的，通常在概率論中把符合下面三個特點的試驗叫做隨機試驗：

(1)每次試驗的可能結果不止一個，并且能事先明確試驗的所有可能結果；

(2)進行一次試驗之前無法確定哪一個結果會出現；

(3)可以在同一條件下重復進行試驗。

定義2-28

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

定義2-29

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

定義2-30

隨機事件：是事件空間S的子集，它由事件空間S中的單位元素構成。

定義2-31

設隨機事件的樣本空間為Ω，對于Ω中的每一個事件A，都有實函數P(A)，滿足：

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

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

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

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

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

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

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

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

(4)?。

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

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

(7)無關事件乘法法則：兩個不相關聯