信息安全原理与技术 课件 ch02-数学基础

信息安全原理与技术第3版第2章数学基础主要知识点：

--数论

--代数基础

--计算复杂性理论

--单向函数

2024/4/5Ch2-数学基础2因子设Z表示全体整数所构成的集合。定义2.1

设a,b∈Z，a≠0，c∈Z，使得b=ac，则称a整除b，并称a是b的因子或者约数，b是a的倍数，记为a|b。定理2.1

（带余除法）设a,b∈Z，b≥1，则存在唯一的整数q和r，使得a=qb+r，0≤r<b。q称a除以b所得的商，r称为a除以b所得的最小非负剩余。定义2.2

设a,b∈Z，a，b不全为0，如果c|a且c|b，则称c为a和b的公因子。特别地，我们把a和b的所有公因子中最大的，称为a和b的最大公因子，记为gcd(a,b)或者(a,b)。2024/4/5Ch2-数学基础3计算两个数的最大公因子的最容易的方法是用欧几里德(Euclid)算法定理2.3（欧几里德算法）给定整数a和b，且b>0，重复使用带余除法，即每次的余数为除数去除上一次的除数，直到余数为0，这样可以得到下面一组方程：

a=bq1+r1,0<r1<b,b=r1q2+r2,0<r2<r1,r1

=r2q3+r3,0<r3<r2,……rj-1

=rjqj+1最后一个不为0的余数rj就是a和b的最大公因子2024/4/5Ch2-数学基础4例2.1

求gcd(1970，1066)用欧几里德算法的计算过程如下：1970＝1×1066+9041066＝1×904+162904＝5×162+94162=1×94+6894＝1×68+2668＝2×26+1626＝1×16+1016＝1×10+610＝1×6+46=1×4+24＝2×2+0因此gcd(1970，1066)=22024/4/5Ch2-数学基础5素数定义2.4

设p∈Z，p≥2，如果p的正因子只有1和p，则称p

为素数，否则为合数

若正整数a有一因子b，而b又是素数，则称b为a的素因子如果整数a与整数b的最大公因子是1，即gcd(a,b)=1，则称a与b互为素数，简称互素设

(m)为小于或等于m且与m互素的正整数个数，则称其为欧拉(Euler)函数

2024/4/5Ch2-数学基础6同余定义2.8

两个整数a,b分别被m除，如果所得的余数相同，则称a与b对模m是同余的，记为a≡b(modm)，正整数m称为模数

同余具有下面的性质：(1)若a≡b(modm)，则则m|(b-a)。反过来，若m|(b-a)，则a≡b(modm)(2)如果a=km+b(k为整数)，则a≡b(modm)(3)每个整数恰与0,1,…，m-1这m个整数中的某一个对模m同余(4)同余关系是一种等价关系(5)a≡b(modm)当且仅当amodm=bmodm2024/4/5Ch2-数学基础7定理2.8(乘法消去律)对于ab

≡ac（modm）来说，若gcd(a,m)＝1则b≡c(mod

m)。

定理2.9(加法消去律)如果a+b

≡a+c（modm），则b≡c(mod

m)加法消去律是没有条件，但乘法消去律的条件是gcd(a,m)＝1，即a和m互素例如6×3≡6×7≡2mod8，但3≡7mod8不成立2024/4/5Ch2-数学基础8模运算

求余运算称为模运算,下面是模运算的一些性质。

(1)(a+b)modm=((amodm)+(bmodm))modm(2)(a-b)modm=((amodm)-(bmodm))modm(3)(a×b)modm=((amodm)×(bmodm))modm(4)(a×(b+c))modm=((a×b)modm)+((a×c)modm))modm例如11mod8=3;15mod8=7,那么(11mod8)+(15mod8)mod8=(3+7)mod8=2(11+15)mod8=26mod8=2

在模运算中，加法单位元是0，(0+a)modm=amodm乘法单位元是1，(1×a)modm=amodm2024/4/5Ch2-数学基础9定义2.13

对a∈Zm，存在b∈Zm，使得a+b≡0(modm)，则b是a的加法逆元，记b=-a。定义2.14对a∈Zm，存在b∈Zm，使得a×b≡1(modm)，则称b为a的乘法逆元。加法一定存在逆元，乘法不一定存在逆元。在密码学特别是非对称密码体制中，常常需要求模逆元，求模逆元就是求乘法逆元。即寻找一个x，使得a×x

≡1modm成立求模逆元问题很困难，有时有结果，有时没有结果利用扩展欧几里德算法能够计算出模逆元2024/4/5Ch2-数学基础10模8运算的例子

模8的加法和乘法运算与普通运算一样,只是将所得的值是去模8后的余数

2024/4/5Ch2-数学基础112024/4/5Ch2-数学基础12模8的加法逆元和乘法逆元

对每一个x都有一个对应的y，使得x+y≡0mod8，则y是x的加法逆元。如对2，有6，使得2+6≡0mod8，那么6是2的加法逆元如果对x，存在y，使得x×y≡1mod8，则y为x的乘法逆元。如3×3≡1mod8，因此3的乘法逆元是3。2024/4/5Ch2-数学基础13快速指数模运算

在非对称密码体制（公钥密码体制）中常常涉及指数模运算，如计算73327mod37一种方法是利用前面介绍的模运算性质(a×b)modm=((amodm)×(bmodm))modm，将指数模运算可以看做是多次重复乘法，并且在计算中间结果时就取模例如：计算117mod13，可以按照下面的思路：112=121≡4mod13114=(112)2≡42mod13≡3mod13117=11×112×114≡11×4×3mod13≡132mod13≡2mod132024/4/5Ch2-数学基础14快速求memodn算法一

(1)a

e,b

m,c

1,其中a,b,c为三大整数寄存器。

(2)如果a=0，则输出结果c即为所求的模n的大整数次幂。(3)如果a是奇数，转第(5)步。(4)a

(a÷2),b

(b×b)modn,转第(3)步。(5)a

(a-1),c

(c×b)modn,转第(2)步。2024/4/5Ch2-数学基础15计算3037mod772024/4/5Ch2-数学基础16费马定理和欧拉定理费马定理和欧拉定理在公钥密码体制中占非常重要的地位定理2.13(费马定理Format)若p是素数,且a是正整数，且gcd(a,p)=1，则：ap-1

1(modp)定理2.14(欧拉定理)

对于任何互素的两个整数a和n，有

aφ(n)≡1modn2024/4/5Ch2-数学基础17素性测试很多密码算法需要随机选择一个或者多个非常大的素数一般做法是先生成大的随机整数，然后确定该大数是否是素数目前没有还没有简单有效的方法确定一个大数是否是素数定理2.15:如果p为大于2的素数，则方程x2≡1(modp)的解只有x=1和x=-1。定理2.15的逆否命题是：如果方程x

2≡1(modp)有一解，那么p不是素数2024/4/5Ch2-数学基础18Miller-Rabin素性概率检验算法WITNESS(a,n)

(1)将(n-1)表示为二进制形式bkbk-1…b0(2)d

1fori=k

downto0do{x

d；

d

(d

d)modn；

if(d=1&x

1&x

n-1)thenreturnTRUE；

ifbi=1thend

(d

a)modn}ifd

1thenreturnTRUE；

elsereturnFALSE.2024/4/5Ch2-数学基础19算法有两个输入，n是待检验的数，a是小于n的整数。如果算法的返回值为TRUE，则n肯定不是素数，如果返回值为FALSE，则n有可能是素数。

for循环后，有d=an-1modn，由费马定理可知，若n为素数，则d为1，因此若d

1，则n不是素数，所以返回TRUE。因为n-1≡-1modn，所以x

1，x

n-1，表示x

2≡1(modp)有不在{-1，1}中的根，因此n不为素数，返回TRUE2024/4/5Ch2-数学基础20离散对数离散对数是许多公钥算法的基础本原根这一个重要概念假设gcd(a,n)=1,如果m是使am

≡1modn成立的最小正整数，则称它是a对模n的指数，记为Ordna

若Ordna=φ(n)，则称a是模n的本原根(primitiveroot)，也称生成元2024/4/5Ch2-数学基础21求模7和模15的本原根对于模7而言，满足gcd(a,n)=1的a是{1,2,3,4,5,6}，将它们的指数列表如下

a123456Ord7a136362从上表可以看到，当a是3和5时，Ord7a=φ(7)，因此，3和5是模7的本原根。2024/4/5Ch2-数学基础22对于模15而言，满足gcd(a,n)=1的a是{1,2,4,7,8,11,13,14}，将它们的指数列表如下：上表中不存在一个a，使Ord15a=φ(15)，所以模15没有本原根定理2.18

模m的本原根存在的必要条件是m=2,4,pa,或者2pa，此处p是奇素数a12478111314Ord7a142442422024/4/5Ch2-数学基础23本原根的测试

通常找出一个本原根不是一件容易的问题如果知道p-1的因子，它就变得容易测试方法:令q1,q2,…,qn是p-1的素因子，对于所有的q1,q2,…,qn,计算a(p-1)/q(modp)，如果对某个q的某个值其结果为1，那么a

不是一个本原根。如果对某个q的所有值其结果都不为1，那么a

是一个本原根。2024/4/5Ch2-数学基础24例2.9

假设p=11,检验2和3是否是一个本原根。解：当p=11时,p-1=10，p-1有两个素因子2和5，现测试2是否是一个本原根。

2(10-1)/5(mod11)=42(10-1)/2(mod11)=10计算结果没有1，所以2是本根原。测试3是否是本根原

3(10-1)/5(mod11)=93(10-1)/2(mod11)=1所以3不是本根原2024/4/5Ch2-数学基础25离散对数模运算用于指数计算可以表示为axmodn，我们称为模指数运算

模指数运算的逆问题就是找出一个数的离散对数，即求解x，使得

ax

≡bmodn定义2.17（离散对数）对于一个整数b和素数n的一个本原根a，可以找到唯一的指数x，使得b≡ax

modn，其中0≤x≤n-1，指数x称为b的以a为基数的模n的离散对数2024/4/5Ch2-数学基础26代数基础有限域在现代密码学中的地位越来越重要本节先简单介绍群、环和域等概念，然后详细介绍有限域中的运算

2024/4/5Ch2-数学基础27群

群G有时记做{G，·}，是定义了一个二元运算的集合，这个二元运算可以表示为·(它具有一般性，可以指加法，乘法或者其他的数学运算)，G中每一个序偶(a，b)通过运算生成G中的元素(a·b)，并满足以下公理：(Al)封闭性：如果a和b都属于G，则a·b也属于G。(A2)结合律；对于G中任意元素a,b,c，都有a·(b·c)=(a·b)·c成立(A3)单位元：G中存在一个元素e，对于G中任意元素a，都有a·e=e·a=a成立(A4)逆元：对于G中任意元素a，G中都存在一个元素a’，使得式a·a’=a’·a=e成立。如果一个群的元素个数是有限的，则该群称为有限群。并且群的阶等于群中元素的个数。否则，称该群为无限群。一个群如果还满足以下条件，则称为交换群（或称Able群）(A5)交换律:对于G中任意的元素a,b，都有.a·b=b·a成立2024/4/5Ch2-数学基础28环

环R有时记为{R，+，×}，是一个有两个二元运算的集合，这两个二元运算分别称为加法和乘法，且对于R中的任意元素a,b,c，满足以下公理：

(Al-A5)R关于加法是一个交换群；对于此种情况下的加法群，我们用0表示其单位元，-a表示a的逆元。

(M1)乘法的封闭性：如果a和b都属于R，则ab也属于R。(M2)乘法的结合律：对于R中任意元素a,b,c，有a(bc)=(ab)c成立。(M3)分配律：对于R中任意元素a,b,c，式a(b+c)=ab+ac和式(a+b)c=ac+bc总成立。环如果还满足一下条件则成为交换环：(M4)乘法的交换律：对于R中的任意元素a,b，有ab=ba成立。在交换环的基础上，满足以下公理的环叫做整环：(M5)乘法单位元：在R中存在元素1，使得对于R中的任意元素a，有al=1a=a成立。(M6)无零因子：如果有R中元素a,b，且ab=0，则必有a=0或b=0

2024/4/5Ch2-数学基础29域

域F有时记为{F，+，×}，是有两个二元运算的集合，这两个二元运算分别称为加法和乘法，且对于F中的任意元素a,b,c，满足以下公理：(Al-M6)F是一个整环；也就是说F满足从Al到A5以及从M1到M6的所有原则。(M7)乘法逆元:对于F中的任意元素a(除0以外),F中都存在一个元素a-1,使得式aa-1=(a-1)a=1成立2024/4/5Ch2-数学基础30根据域中元素的个数是不是有限，把域划分成有限域和无限域无限域在密码学中没有特别的意义，然而有限域却在许多密码编码学中扮演着重要的角色。定义2.19:有限域中元素的个数称为有限域的阶。定理2.19:有限域的阶必为素数p的幂pn，n为正整数定理2.20:

对任意素数p和正整数n，存在pn阶的有限域，记为GF(pn)。当时n=1，有限域GF(p)也称素域。在密码学中，最常用的域一般是素域GF(p)或者阶为2m的GF(2m)域2024/4/5Ch2-数学基础31有限域GF(p)

给定一个素数p，元素个数为p的有限域GF(p)定义为整数{0,1,…,p-1}的集合Zp，其运算为模p的算术运算最简单的有限域是GF(2)，该域元素的个数是2，它们分别是0和1，在GF(2)上的加运算等价于异或运算，乘等价于逻辑与运算表2.5是在有限域GF(7)中的算术运算，这是一个阶为7，采用模7运算，它满足域的所有性质。需要注意的是，前面介绍的表2.1只是表示集合Z8中模8运算，其中的非零整数不一定有乘法逆元，因此不是域2024/4/5Ch2-数学基础32模7加法2024/4/5Ch2-数学基础33模7乘法2024/4/5Ch2-数学基础34模7的加法逆元和乘法逆元2024/4/5Ch2-数学基础35域上多项式

若ai≠0，称n为该多项式的次数，并称an为首项系数。首项系数为1的多项式称为首1多项式。域F上x多项式全体集合记为F[x]多项式运算包括加法、减法、乘法和除法

2024/4/5Ch2-数学基础36在域F上的多项式加法运算定义为乘法运算定义为：2024/4/5Ch2-数学基础37定理2.21设a(x)和b(x)是域F上的多项式，且b(x)≠0，则存在唯一的一对多项式，使

其中q(x)为商式，r(x)为余式，r(x)的次数小于b(x)的次数多项式除法具有与普通除法一样的长除法如整数运算类似，我们可以将余式r(x)写成a(x)modb(x)，称为a(x)模b(x)，b(x)称为模多项式

2024/4/5Ch2-数学基础38定义2.21设a(x)和b(x)是域F上的多项式(1)设b(x)≠0，若存在q(x)使，则称b(x)是a(x)的因式或者除式。b(x)整除a(x)，记为b(x)|a(x)。

(2)设a(x)和b(x)不全为0，a(x)和b(x)的次数最高的首1公因式称为它们的最高公因式，记为gcd(a(x),b(x))。若gcd(a(x),b(x))=1，称a(x)和b(x)互素。

(3)若存在次数大于或者等于1的q(x)和b(x)，使a(x)=q(x)b(x)，则称a(x)为可约多项式，否则称a(x)为不可约多项式（也称既约多项式）2024/4/5Ch2-数学基础39例如，GF(2)上的多项式是可约多项式，因为。而多项式则是不可约多项式，因为它没有一个因式2024/4/5Ch2-数学基础40有限域GF(2n)

为pn模的模运算不一定能产生域用不可约多项式可以构造一个域

对于F[x]中的每个不可约多项式p(x)，可以构造一个域F[x]

p(x)

设p(x)是F[x]中n次不可约多项式，令F[x]

p(x)为F[x]中所有次数小于n的多项式集合

其中ai

∈F，即在集合{0,1,…,p-1}上取值

2024/4/5Ch2-数学基础41定义F[x]

p(x)上的二元运算加法和乘法运算如下：域F[x]

p(x)中的单位元和零元分别是F中的单位元和零元上面的运算定义可以看到：

(1)该运算遵循基本代数规则中的普通多项式运算规则

(2)系数运算以p模，即遵循有限域上Zp的运算规则(3)乘法运算是两个多项式相乘结果再模一个不可约多项式p(x)，如果两个多项式相乘结果是次数大于n-1的多项式，它将除以次数为n的不可约多项式p(x)并取余2024/4/5Ch2-数学基础42定理2.22是域,当且仅当p(x)是F上的不可约多项式，其中F是有限域。特别地，在GF(2n)中，F[x]

p(x)中所有次数小于n的多项式表示为：系数ai是二进制数，该多项式可以由它的n个二进制系数唯一地表示。因此GF(2n)中的每个多项式都可以表示成一个n位的二进制整数。2024/4/5Ch2-数学基础43高级加密标准中的有限域GF(28)上运算不可约多项式为假设多项式加法运算过程为=乘法运算过程为：2024/4/5Ch2-数学基础44由于a(x)和b(x)相乘的多项式次数大于n，将它们相乘结果再除不可约多项式p(x)，可得商为x5+x3，余数为x7+x6+1，因此用十六进制表示为{57}{83}={C1}用二进制表示为=(11000001)说明：在上面的十六进制表示中，是用一个十六进制字符表示4位二进制数，一个字节的二进制数用括号括起来的两个十六进制字符表示2024/4/5Ch2-数学基础45从上面的例子我们也可以发现，多项式加法是将对应的系数分别相加GF(2n)中两个多项式加法和减法等同于按位异或，需要注意的是加法不进位，减法不借位2024/4/5Ch2-数学基础46计算复杂性理论计算复杂性理论提供了一种分析不同密码技术和算法的计算复杂性方法计算复杂性理论给出了求解一个问题的计算是“容易”还是“困难”的确切定义，这有助于确定一个密码算法的安全强度破译一个密码算法所花费的时间或者空间代价超出了密码本身所保密内容的价值，破译就没有意义计算机复杂性理论涉及算法的复杂性和问题的复杂性

2024/4/5Ch2-数学基础47问题的复杂性一个问题的复杂性是由可解这个问题的算法的计算复杂性所决定可解一个问题的算法可能有多个，在理论上定义一个问题的计算复杂性为可解该问题的最有效算法的计算复杂性

计算复杂性粗分为三类，即P类(确定性多项式时间可解类)、NP类(不确定性多项式时间可解类)和NP完全类(记为NPC，不