《信息安全原理与技术数学基础PPT讲稿.ppt》由会员分享，可在线阅读，更多相关《信息安全原理与技术数学基础PPT讲稿.ppt（53页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、信息安全原理与技术数学基础第1页，共53页，编辑于2022年，星期四2022/9/28Ch2-数学基础2第2章 数学基础 主要知识点主要知识点：-数论 -代数基础 -计算复杂性理论 -单向函数 第2页，共53页，编辑于2022年，星期四2022/9/28Ch2-数学基础3因子 设Z表示全体整数所构成的集合。定义定义2.1 设a,b Z，a0，cZ，使得b=ac，则称a整除b，并称a是b的因子因子或者约数约数，b是a的倍数倍数，记为a|b。定理定理2.1（带余除法带余除法）设a,b Z，b1，则存在唯一的整数q和r，使得a=qb+r，0r 0，重复使用带余除法，即每次的余数为除数去除上一次的除数
2、，直到余数为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的最大公因子 第4页，共53页，编辑于2022年，星期四2022/9/28Ch2-数学基础5例例2.1 求gcd(1970，1066)用欧几里德算法的计算过程如下：197011066+90410661904+1629045162+94162=194+6894168+2668226+1626116+1016110+61016+46=14+2422+0因此gcd(1970，1066)=2第5页，
3、共53页，编辑于2022年，星期四2022/9/28Ch2-数学基础6素数 定义定义2.4 设p Z，p2，如果p的正因子只有1和p，则称p 为素数素数，否则为合数合数 若正整数a有一因子b，而b又是素数，则称b为a的素因子素因子如果整数a与整数b的最大公因子是1，即gcd(a,b)=1，则称a与b互为素数，简称互素互素设(m)为小于或等于m且与m互素的正整数个数，则称其为欧拉欧拉(Euler)函数函数 第6页，共53页，编辑于2022年，星期四2022/9/28Ch2-数学基础7同余定义定义2.8 两个整数a,b分别被m除，如果所得的余数相同，则称a与b对模m是同余同余的，记为a b(mod
4、 m)，正整数m称为模数模数 同余具有下面的性质：(1)若a b(mod m)，则则m|(b-a)。反过来，若m|(b-a)，则a b(mod m)(2)如果a=km+b(k为整数)，则a b(mod m)(3)每个整数恰与0,1,，m-1这m个整数中的某一个对模m同余 (4)同余关系是一种等价关系 (5)a b(mod m)当且仅当a mod m=b mod m第7页，共53页，编辑于2022年，星期四2022/9/28Ch2-数学基础8定理定理2.8(乘法消去律)对于ab ac（mod m）来说，若gcd(a,m)1则b c(mod m)。定理定理2.9(加法消去律)如果a+b a+c（m
5、od m），则b c(mod m)加法消去律是没有条件，但乘法消去律的条件是gcd(a,m)1，即a和m互素例如 63672 mod 8，但37 mod 8不成立 第8页，共53页，编辑于2022年，星期四2022/9/28Ch2-数学基础9模运算模运算 求余运算求余运算称为模运算模运算,下面是模运算的一些性质。下面是模运算的一些性质。(1)(a+b)mod m=(a mod m)+(b mod m)mod m (2)(a-b)mod m=(a mod m)-(b mod m)mod m (3)(ab)mod m=(a mod m)(b mod m)mod m (4)(a(b+c)mod m=
6、(ab)mod m)+(ac)mod m)mod m例如 11 mod 8=3;15 mod 8=7,那么(11 mod 8)+(15 mod 8)mod 8=(3+7)mod 8=2 (11+15)mod 8=26 mod 8=2 在模运算中，加法单位元是0，(0+a)mod m=a mod m乘法单位元是1，(1a)mod m=a mod m第9页，共53页，编辑于2022年，星期四2022/9/28Ch2-数学基础10定义定义2.13 对aZm，存在bZm，使得a+b 0(mod m)，则b是a的加法逆元，记b=-a。定义定义2.14 对aZm，存在bZm，使得ab 1(mod m)，则
7、称b为a的乘法逆元。加法一定存在逆元，乘法不一定存在逆元。在密码学特别是非对称密码体制中，常常需要求模逆元，求模逆元就是求乘法逆元。即寻找一个x，使得ax 1 mod m成立 求模逆元问题很困难，有时有结果，有时没有结果 利用扩展欧几里德算法展欧几里德算法能够计算出模逆元 第10页，共53页，编辑于2022年，星期四2022/9/28Ch2-数学基础11模模8运算的例子运算的例子 模8的加法和乘法运算与普通运算一样,只是将所得的值是去模8后的余数 第11页，共53页，编辑于2022年，星期四2022/9/28Ch2-数学基础12第12页，共53页，编辑于2022年，星期四2022/9/28Ch
8、2-数学基础13模8的加法逆元和乘法逆元 对每一个x都有一个对应的y，使得x+y 0 mod 8，则y是x的加法逆元加法逆元。如对2，有6，使得2+60 mod 8，那么6是2的加法逆元如果对x，存在y，使得xy 1 mod 8，则y为x的乘法逆元乘法逆元。如331 mod 8，因此3的乘法逆元是3。第13页，共53页，编辑于2022年，星期四2022/9/28Ch2-数学基础14快速指数模运算快速指数模运算 在非对称密码体制（公钥密码体制）中常常涉及指数模运算，如计算73327 mod 37 一种方法是利用前面介绍的模运算性质(ab)mod m=(a mod m)(b mod m)mod m
9、，将指数模运算可以看做是多次重复乘法，并且在计算中间结果时就取模 例如：计算117mod 13，可以按照下面的思路：112=1214 mod 13 114=(112)242mod 13 3 mod 13 117=11112114 1143 mod 13 132 mod 13 2 mod 13第14页，共53页，编辑于2022年，星期四2022/9/28Ch2-数学基础15快速求快速求me mod n算法一算法一 (1)ae,bm,c1,其中a,b,c为三大整数寄存器。(2)如果a=0，则输出结果c即为所求的模n的大整数次幂。(3)如果a是奇数，转第(5)步。(4)a(a2),b(bb)mod
10、n,转第(3)步。(5)a(a-1),c(cb)mod n,转第(2)步。第15页，共53页，编辑于2022年，星期四2022/9/28Ch2-数学基础16计算3037 mod 77 第16页，共53页，编辑于2022年，星期四2022/9/28Ch2-数学基础17费马定理和欧拉定理 费马定理和欧拉定理在公钥密码体制中占非常重要的地位 定理定理2.13(费马定理费马定理Format)若p是素数,且a是正整数，且gcd(a,p)=1，则：ap-1 1(mod p)定理定理2.14(欧拉定理欧拉定理)对于任何互素的两个整数a和n，有 a(n)1 mod n第17页，共53页，编辑于2022年，星期
11、四2022/9/28Ch2-数学基础18素性测试 很多密码算法需要随机选择一个或者多个非常大的素数 一般做法是先生成大的随机整数，然后确定该大数是否是素数 目前没有还没有简单有效的方法确定一个大数是否是素数 定理定理2.15:如果p为大于2的素数，则方程x 21(mod p)的解只有x=1和x=-1。定理2.15的逆否命题是：如果方程x 21(mod p)有一解，那么p不是素数 第18页，共53页，编辑于2022年，星期四2022/9/28Ch2-数学基础19Miller-Rabin素性概率检验算法WITNESS(a,n)(1)将(n-1)表示为二进制形式bkbk-1b0 (2)d1 for
12、i=k downto 0 do xd；d(d d)mod n；if(d=1&x 1&x n-1)then return TRUE；if bi=1 then d(d a)mod n if d1 then return TRUE；else return FALSE.第19页，共53页，编辑于2022年，星期四2022/9/28Ch2-数学基础20算法有两个输入，n是待检验的数，a是小于n的整数。如果算法的返回值为TRUE，则n肯定不是素数，如果返回值为FALSE，则n有可能是素数。for循环后，有d=an-1 mod n，由费马定理可知，若n为素数，则d为1，因此若d1，则n不是素数，所以返回TR
13、UE。因为n-1-1 mod n，所以x1，x n-1，表示x 21(mod p)有不在-1，1中的根，因此n不为素数，返回TRUE 第20页，共53页，编辑于2022年，星期四2022/9/28Ch2-数学基础21离散对数 离散对数是许多公钥算法的基础本原根本原根这一个重要概念 假设gcd(a,n)=1,如果m是使am 1 mod n 成立的最小正整数，则称它是a对模n的指指数数，记为Ordna 若Ordna=(n)，则称a是模n的本原根本原根(primitive root)，也称生成元生成元第21页，共53页，编辑于2022年，星期四2022/9/28Ch2-数学基础22求模7和模15的本
14、原根 对于模7而言，满足gcd(a,n)=1的a是1,2,3,4,5,6，将它们的指数列表如下 a123456Ord7a136362从上表可以看到，当a是3和5时，Ord7a=(7)，因此，3和5是模7的本原根。第22页，共53页，编辑于2022年，星期四2022/9/28Ch2-数学基础23对于模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,或者2 pa，此处p是奇素数 a12478111314Ord7a14
15、244242第23页，共53页，编辑于2022年，星期四2022/9/28Ch2-数学基础24本原根的测试本原根的测试 通常找出一个本原根不是一件容易的问题 如果知道p-1的因子，它就变得容易 测试方法测试方法:令q1,q2,qn是p-1的素因子，对于所有的q1,q2,qn,计算a(p-1)/q(mod p)，如果对某个q的某个值其结果为1，那么a 不是一个本原根。如果对某个q的所有值其结果都不为1，那么a 是一个本原根。第24页，共53页，编辑于2022年，星期四2022/9/28Ch2-数学基础25例例2.9 假设p=11,检验2和3是否是一个本原根。解：当p=11时,p-1=10，p-1
16、有两个素因子2和5，现测试2是否是一个本原根。2(10-1)/5(mod 11)=4 2(10-1)/2(mod 11)=10 计算结果没有1，所以2是本根原。测试3是否是本根原 3(10-1)/5(mod 11)=9 3(10-1)/2(mod 11)=1所以3不是本根原第25页，共53页，编辑于2022年，星期四2022/9/28Ch2-数学基础26离散对数 模运算用于指数计算可以表示为ax mod n，我们称为模指数运算模指数运算 模指数运算的逆问题模指数运算的逆问题就是找出一个数的离离散对数散对数，即求解x，使得 ax b mod n定义定义2.17（离散对数离散对数）对于一个整数b和
17、素数n的一个本原根a，可以找到唯一的指数x，使得b ax mod n，其中0 x n-1，指数x称为b的以a为基数的模n的离散对数离散对数第26页，共53页，编辑于2022年，星期四2022/9/28Ch2-数学基础27代数基础 有限域在现代密码学中的地位越来越重要本节先简单介绍群、环和域群、环和域等概念，然后详细介绍有限域中的运算有限域中的运算 第27页，共53页，编辑于2022年，星期四2022/9/28Ch2-数学基础28群群 群群G有时记做G，是定义了一个二元运算的集合，这个二元运算可以表示为(它具有一般性，可以指加法，乘法或者其他的数学运算)，G中每一个序偶(a，b)通过运算生成G中
18、的元素(ab)，并满足以下公理：(Al)封闭性：如果a和b都属于G，则ab也属于G。(A2)结合律；对于G中任意元素a,b,c，都有 a(bc)=(ab)c成立(A3)单位元：G中存在一个元素e，对于G中任意元素a，都有ae=ea=a 成立(A4)逆元：对于G中任意元素a，G中都存在一个元素a，使得式aa=a a=e成立。如果一个群的元素个数是有限的，则该群称为有限群有限群。并且群的阶阶等于群中元素的个数。否则，称该群为无限群无限群。一个群如果还满足以下条件，则称为交换群交换群（或称Able群群）(A5)交换律:对于G中任意的元素a,b，都有.ab=ba成立 第28页，共53页，编辑于2022
19、年，星期四2022/9/28Ch2-数学基础29环环 环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中的
20、任意元素a,b，有ab=ba成立。在交换环的基础上，满足以下公理的环叫做整环整环：(M5)乘法单位元：在R中存在元素1，使得对于R中的任意元素a，有 al=1a=a成立。(M6)无零因子：如果有R中元素a,b，且ab=0，则必有a=0或b=0 第29页，共53页，编辑于2022年，星期四2022/9/28Ch2-数学基础30域域 域F有时记为F，+，是有两个二元运算的集合，这两个二元运算分别称为加法和乘法，且对于F中的任意元素a,b,c，满足以下公理：(Al-M6)F是一个整环；也就是说F满足从Al到A5以及从M1到M6的所有原则。(M7)乘法逆元:对于F中的任意元素a(除0以外),F中都存在
21、一个元素a-1,使得式aa-1=(a-1)a=1成立 第30页，共53页，编辑于2022年，星期四2022/9/28Ch2-数学基础31根据域中元素的个数是不是有限，把域划分成有限域有限域和无限域无限域无限域在密码学中没有特别的意义，然而有限域却在许多密码编码学中扮演着重要的角色。定义定义2.19:有限域中元素的个数称为有限域的阶阶。定理定理2.19:有限域的阶必为素数p的幂pn，n为正整数定理定理2.20:对任意素数p和正整数n，存在pn阶的有限域，记为GF(pn)。当时n=1，有限域GF(p)也称素域素域。在密码学中，最常用的域一般是素域GF(p)或者阶为2m的GF(2m)域 第31页，共
22、53页，编辑于2022年，星期四2022/9/28Ch2-数学基础32有限域有限域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运算，其中的非零整数不一定有乘法逆元，因此不是域第32页，共53页，编辑于2022年，星期四2022/9/28Ch2-数学
23、基础33模7加法 第33页，共53页，编辑于2022年，星期四2022/9/28Ch2-数学基础34模7乘法 第34页，共53页，编辑于2022年，星期四2022/9/28Ch2-数学基础35模7的加法逆元和乘法逆元第35页，共53页，编辑于2022年，星期四2022/9/28Ch2-数学基础36域上多项式域上多项式 若ai 0，称n为该多项式的次数次数，并称an为首项系数首项系数。首项系数为1的多项式称为首首1多项式多项式。域F上x多项式全体集合记为Fx 多项式运算包括加法、减法、乘法和除法加法、减法、乘法和除法 第36页，共53页，编辑于2022年，星期四2022/9/28Ch2-数学基础
24、37在域F上的多项式加法运算定义为 乘法运算定义为：第37页，共53页，编辑于2022年，星期四2022/9/28Ch2-数学基础38定理定理2.21 设a(x)和b(x)是域F上的多项式，且b(x)0，则存在唯一的一对多项式，使 其中q(x)为商式，r(x)为余式，r(x)的次数小于b(x)的次数 多项式除法具有与普通除法一样的长除法如整数运算类似，我们可以将余式r(x)写成a(x)mod b(x)，称为a(x)模b(x)，b(x)称为模多项式模多项式 第38页，共53页，编辑于2022年，星期四2022/9/28Ch2-数学基础39定义定义2.21 设a(x)和b(x)是域F上的多项式 (
25、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)为不可约不可约多项式多项式（也称既约多项式既约多项式）第39页，共53页，编辑于2022年，星期四2022/9/28Ch2-数学基础40例
26、如，GF(2)上的多项式 是可约多项式可约多项式，因为。而多项式 则是不可约多项式不可约多项式，因为它没有一个因式 第40页，共53页，编辑于2022年，星期四2022/9/28Ch2-数学基础41有限域有限域GF(2n)为pn模的模运算不一定能产生域 用不可约多项式不可约多项式可以构造一个域构造一个域 对于Fx中的每个不可约多项式p(x)，可以构造一个域构造一个域Fx p(x)设p(x)是Fx中n次不可约多项式，令Fx p(x)为Fx中所有次数小于n的多项式集合 其中ai F，即在集合0,1,p-1上取值 第41页，共53页，编辑于2022年，星期四2022/9/28Ch2-数学基础42定义
27、Fx p(x)上的二元运算加法和乘法运算如下：域Fx p(x)中的单位元和零元分别是F中的单位元和零元 上面的运算定义可以看到：(1)该运算遵循基本代数规则中的普通多项式运算规则 (2)系数运算以p模，即遵循有限域上Zp的运算规则 (3)乘法运算是两个多项式相乘结果再模一个不可约多项式p(x)，如果两个多项式相乘结果是次数大于n-1的多项式，它将除以次数为n的不可约多项式p(x)并取余第42页，共53页，编辑于2022年，星期四2022/9/28Ch2-数学基础43定理定理2.22 是域,当且仅当p(x)是F上的不可约多项式，其中F是有限域。特别地，在GF(2n)中，Fx p(x)中所有次数小
28、于n的多项式表示为：系数ai是二进制数，该多项式可以由它的n个二进制系数唯一地表示。因此GF(2n)中的每个多项式都可以表示成一个n位的二进制整数。第43页，共53页，编辑于2022年，星期四2022/9/28Ch2-数学基础44高级加密标准中的有限域GF(28)上运算不可约多项式为 假设多项式加法运算加法运算过程为 =乘法运算过程为：第44页，共53页，编辑于2022年，星期四2022/9/28Ch2-数学基础45由于a(x)和b(x)相乘的多项式次数大于n，将它们相乘结果再除不可约多项式p(x)，可得商为x5+x3，余数为x7+x6+1，因此 用十六进制表示为57 83=C1用二进制表示为
29、 =(11000001)说明说明：在上面的十六进制表示中，是用一个十六进制字符表示4位二进制数，一个字节的二进制数用括号括起来的两个十六进制字符表示 第45页，共53页，编辑于2022年，星期四2022/9/28Ch2-数学基础46从上面的例子我们也可以发现，多项式加法是将对应的系数系数分别相加 GF(2n)中两个多项式加法和减法等同于按位异或，需要注意的是加法不进位，减法不借位第46页，共53页，编辑于2022年，星期四2022/9/28Ch2-数学基础47计算复杂性理论 计算复杂性理论计算复杂性理论提供了一种分析不同密码技术和算法的计算复杂性方法 计算复杂性理论计算复杂性理论给出了求解一个
30、问题的计算是“容易”还是“困难”的确切定义，这有助于确定一个密码算法的安全强度破译一个密码算法所花费的时间或者空间代价超出了密码本身所保密内容的价值，破译就没有意义计算机复杂性理论涉及算法的复杂性算法的复杂性和问题的复杂性问题的复杂性 第47页，共53页，编辑于2022年，星期四2022/9/28Ch2-数学基础48问题的复杂性 一个问题的复杂性是由可解这个问题的算法的计算复杂性所决定 可解一个问题的算法可能有多个，在理论上定义一个问题的计算复杂性为可解该问题的最有效算法的计算复杂性最有效算法的计算复杂性 计算复杂性粗分为三类，即P类类(确定性多项式时间可解类)、NP类类(不确定性多项式时间可
31、解类)和NP完全完全类类(记为NPC，不确定性多项式时间可解完全类)P类问题称为易解问题易解问题，NP类问题称为难解问题难解问题，NPC问题称为困难问题困难问题。由于NPC问题不存在有效的算法，现在的密码算法的安全性都是基于NPC问题的 第48页，共53页，编辑于2022年，星期四2022/9/28Ch2-数学基础49算法的复杂性 算法的复杂性表示算法在实际执行时所需计算能力方面的信息，通常它由该算法所要求的最大时间与储存空间来确定 算法所需的时间和空间往往取决于问题实例的规模n 算法在用于相同规模n的不同实例时，其时间和空间需求也可能会有很大差异，因此，实际中我们常常研究的是算法关于输入规模
32、n的所有实例的时间与空间需求的所有实例的时间与空间需求的平均值平均值 表2.6 显示:如果一个密码算法具有指数级的时间复杂性，那么可以认为它是计算上不可行的 第49页，共53页，编辑于2022年，星期四2022/9/28Ch2-数学基础50第50页，共53页，编辑于2022年，星期四2022/9/28Ch2-数学基础51单向函数 单向和陷门单向函数是公钥密码学的核心，可以说公钥密码体制的设计就是陷门单向函数的设计 定义定义2.23 (单向函数单向函数)一个可逆函数f：AB，若它满足：(1)对所有xA，易于计算f(x)。(2)对几乎所有xA，由f(x)求x极为困难，以至于实际上不可能做到，则称f
33、为单向函单向函数数(One-way Function)第51页，共53页，编辑于2022年，星期四2022/9/28Ch2-数学基础52定义定义2.24(单向陷门函数单向陷门函数)一“可逆”函数F若满足下列二条件，则称F为单向陷单向陷门函数门函数(One-way Trapdoor Function)：(1)对于所有属于域F中的的任一x，容易计算F(x)=y；(2)对于几乎所有属于域F中的任一y，除非获得陷门信息(trapdoor)，否则求出x，使得 x=F-1(y)在计算上不可行，F-1为F的逆函数 单向函数是求逆困难的函数求逆困难的函数，而单向陷门函数是在不知不知陷门信息下求逆困难的函数陷门信息下求逆困难的函数，当知道陷门信息后，求逆是易于实现的 第52页，共53页，编辑于2022年，星期四2022/9/28Ch2-数学基础53目前，还不能从理论上证明单向函数是存在的 现实中却存在几个候选单向函数.说他们是“候选”，是因为他们表现出了单向函数的性质，但还没有办法从理论上证明它们一定是单向函数 常见的候选单向函数:-离散对数 -因数分解问题 -背包问题 第53页，共53页，编辑于2022年，星期四