《物联网信息安全》课件第2章

2.1数论2.2群环域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个素数矛盾，所以可得出素数是无限多的。

关于素数在自然数中的分布规律，一直是数论学者研究的重点。一个个单独来看，素数在自然数中的出现没有什么规律。可是总体地看，素数的个数是有规可循的。

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

定理2-6

设是小于x的素数的个数，则,

当时，比值。

该结果最早为德国数学家高斯发现，严格的证明来自于法国数学家哈达玛。

定义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群环域

2.2.1群论

在数学中，群是一种代数结构，由一个集合以及一个二元运算组成。例如整数集合上赋予加法运算就形成一个整数加群。一个群必须满足一些被称为“群公理”的条件，也就是封闭性、结合律、单位元和逆元。很多熟知的数学结构比如数系统都遵从这些公理。

定义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， + )是一个生成周期为无限的循环群。

分析：这个群的单位元素是0，且如果，则它的逆元素为－a。该群的生成元素为1，因为对任意一个正整数m均有，对于0有，对于任意负整数－m均有,

所以(Z，+)是由1所生成的群，且其周期为无限。2.2.2环理论

定义2-19

设L是一非空集合，a，b为L中的元素，在L上定义了两个代数运算，一个叫加法，记为a+b，一个叫乘法，记为ab，如果满足以下条件，则称L为环：

(1) L对于加法构成一个交换群；

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

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

例2-11

全体整数集合，在其上赋予通常的加法和乘法运算，则构成一个环，称为整数环。环的基本性质如下：

(1)用0代表环中加法群的零元素，则对于任意，有成立；

(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算法复杂度理论

算法复杂度分为时间复杂度和空间复杂度。时间复杂度是执行算法所需要的计算工作量的量度；而空间复杂度是执行这个算法所需要的内存空间的量度。2.3.1时间复杂度

一个算法执行所耗费的时间，从理论上是不能算出来的，必须上机运行测试之后才能知道。现实中不可能也没有必要对每个算法都上机测试其花费的具体时间。2.3.2空间复杂度

一个算法所需的存储空间用f(n)表示，n表示问题的规模，记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．非确定型图灵机

如果不加特殊说明，通常所说的图灵机都是确定型图灵机。

非确定型图灵机和确定型图灵机的不同之处在于，在计算的每一时刻，根据当前状态和读写头所读的符号，机器存在多种状态转移方案，机器将任意地选择其中一种方案继续运作，直到最后停机为止。具体而言，其状态转移函数为其中：Q是状态集合，是带字母表，L、R分别表示读写头向左和向右移动，符号2A表示集合A的幂集，即

6．P与NP问题

复杂度类P即为所有可以由一个确定型图灵机在多项式表达的时间内解决的问题；类NP为由所有可以在多项式表达的时间内验证解是否正确的决定问题组成，或者等效地说，那些解可以在非确定型图灵机上在多项式表达的时间内找出的问题的集合。

2.4公 钥 密 码 学

2.4.1基本概念

公钥密码学，又称非对称钥匙密码学，相对于对称钥匙密码学，其最大的特点在于加密和解密使用不同的钥匙。在对称钥匙密码学中，加密和解密使用相同的钥匙，也许对不同的信息使用不同的钥匙，但都面临钥匙管理的难题。由于每对通信方都必须使用异于其他组的钥匙，当网络成员的数量增加时，钥匙数量成二次方增加。2.4.2RSA算法

1978年，MIT的RonRivest、AdiShamir和LenAdleman提出了公钥加密算法RSA。RSA取名来自开发者的名字。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很大时，则非常困难。已有的大整数分解的算法有试除法、二次筛选法、数域筛选法等。迄今为止，关于大整数分解尚未发现快速算法。

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中事件所包含的信息量统计平均，则平均值

称为集合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相互统计独立时，等号成立。

2.6概率论

2.6.1概率论的基本概念

定义2-27

随机试验：随机现象是相对于决定性现象而言的，通常在概率论中把符合下面三个特点的试验叫做随机试验：

(1)每次试验的可能结果不止一个，并且能事先明确试验的所有可能结果；

(2)进行一次试验之前无法确定哪一个结果会出现；

(3)可以在同一条件下重复进行试验。

定义2-28

单位事件：是在一次随机试验中可能发生的不能再细分的结果，又被称为基本事件。

定义2-29

事件空间：随机试验所有可能发生的单位事件的集合，又称为样本空间。

定义2-30

随机事件：是事件空间S的子集，它由事件空间S中的单位元素构成。

定义2-31

设随机事件的样本空间为Ω，对于Ω中的每一个事件A，都有实函数P(A)，满足：

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

(2)规范性：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同时发生的概率为

(7)无关事件乘法法则：两个不相关联