信息安全原理与技术ch02-数学基础.ppt
《信息安全原理与技术ch02-数学基础.ppt》由会员分享,可在线阅读,更多相关《信息安全原理与技术ch02-数学基础.ppt(53页珍藏版)》请在三一文库上搜索。
1、信息安全原理与技术,郭亚军 宋建华 李莉 清华大学出版社,2019/3/15,Ch2-数学基础,2,第2章 数学基础,主要知识点: -数论 -代数基础 -计算复杂性理论 -单向函数,2019/3/15,Ch2-数学基础,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 b。q称a除以b所得的商,r称为a除以b所得的最小非负剩余。 定义2.2 设a, b Z,a,b不全为0,
2、如果c | a且c | b,则称c为a和b的公因子。特别地,我们把a和b的所有公因子中最大的,称为a和b的最大公因子,记为gcd ( a, b) 或者 (a, b)。,2019/3/15,Ch2-数学基础,4,计算两个数的最大公因子的最容易的方法是用欧几里德(Euclid)算法 定理2.3 (欧几里德算法)给定整数a和b,且b0,重复使用带余除法,即每次的余数为除数去除上一次的除数,直到余数为0,这样可以得到下面一组方程: a = bq1+r1, 0 r1 b, b = r1q2+r2, 0 r2 r1, r1 = r2q3+r3, 0 r3 r2, rj-1 = rjqj+1 最后一个不为0
3、的余数rj就是a和b的最大公因子,2019/3/15,Ch2-数学基础,5,例2.1 求gcd (1970,1066),用欧几里德算法的计算过程如下: 197011066+904 10661904+162 9045162+94 162=194+68 94168+26 68226+16 26116+10 16110+6 1016+4 6=14+2 422+0 因此gcd (1970,1066) = 2,2019/3/15,Ch2-数学基础,6,素数,定义2.4 设p Z,p2,如果p的正因子只有1和p,则称p 为素数,否则为合数 若正整数a有一因子b,而b又是素数,则称b为a的素因子 如果整数a
4、与整数b的最大公因子是1,即gcd (a, b) = 1,则称a与b互为素数,简称互素 设(m)为小于或等于m且与m互素的正整数个数,则称其为欧拉(Euler)函数,2019/3/15,Ch2-数学基础,7,同余,定义2.8 两个整数a, b分别被m除,如果所得的余数相同,则称a与b对模m是同余的,记为a b (mod 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个整数中的某一个对
5、模m同余 (4) 同余关系是一种等价关系 (5) a b (mod m)当且仅当a mod m = b mod m,2019/3/15,Ch2-数学基础,8,定理2.8 (乘法消去律)对于ab ac(mod m)来说,若gcd(a, m)1则b c(mod m)。 定理2.9 (加法消去律)如果a+b a+c(mod m),则b c(mod m) 加法消去律是没有条件,但乘法消去律的条件是gcd(a, m)1,即a和m互素 例如 63672 mod 8,但37 mod 8不成立,2019/3/15,Ch2-数学基础,9,模运算,求余运算称为模运算, 下面是模运算的一些性质。 (1) (a+b)
6、 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 = (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 在模运算中,加法单位元
7、是0,(0+a) mod m = a mod m 乘法单位元是1,(1a) mod m = a mod m,2019/3/15,Ch2-数学基础,10,定义2.13 对aZm,存在bZm,使得a+b 0 (mod m),则b是a的加法逆元,记b= - a。 定义2.14 对aZm,存在bZm,使得ab 1 (mod m),则称b为a的乘法逆元。 加法一定存在逆元,乘法不一定存在逆元。 在密码学特别是非对称密码体制中,常常需要求模逆元,求模逆元就是求乘法逆元。即寻找一个x,使得ax 1 mod m成立 求模逆元问题很困难,有时有结果,有时没有结果 利用扩展欧几里德算法能够计算出模逆元,2019/
8、3/15,Ch2-数学基础,11,模8运算的例子,模8的加法和乘法运算与普通运算一样,只是将所得的值是去模8后的余数,2019/3/15,Ch2-数学基础,12,2019/3/15,Ch2-数学基础,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。,2019/3/15,Ch2-数学基础,14,快速指数模运算,在非对称密码体制(公钥密码体制)中常常涉及指数模运算,如计
9、算73327 mod 37 一种方法是利用前面介绍的模运算性质(ab) mod m = (a mod m) (b mod m) mod m,将指数模运算可以看做是多次重复乘法,并且在计算中间结果时就取模 例如:计算117mod 13,可以按照下面的思路: 112=1214 mod 13 114= (112)242mod 13 3 mod 13 117=11112114 1143 mod 13 132 mod 13 2 mod 13,2019/3/15,Ch2-数学基础,15,快速求me mod n算法一,(1) ae, bm, c1, 其中a, b, c为三大整数寄存器。 (2) 如果a=0,
10、则输出结果c即为所求的模n的大整数次幂。 (3) 如果a是奇数,转第(5)步。 (4) a(a2), b(bb) mod n, 转第(3)步。 (5) a(a-1), c(cb) mod n, 转第(2)步。,2019/3/15,Ch2-数学基础,16,计算3037 mod 77,2019/3/15,Ch2-数学基础,17,费马定理和欧拉定理,费马定理和欧拉定理在公钥密码体制中占非常重要的地位 定理2.13 (费马定理Format) 若p是素数, 且a是正整数,且gcd(a, p) = 1,则: ap-1 1(mod p) 定理2.14(欧拉定理) 对于任何互素的两个整数a和n,有 a(n)
11、1 mod n,2019/3/15,Ch2-数学基础,18,素性测试,很多密码算法需要随机选择一个或者多个非常大的素数 一般做法是先生成大的随机整数,然后确定该大数是否是素数 目前没有还没有简单有效的方法确定一个大数是否是素数 定理2.15: 如果p为大于2的素数,则方程x 21 (mod p)的解只有x=1和x=-1。 定理2.15的逆否命题是:如果方程x 21 (mod p)有一解,那么p不是素数,2019/3/15,Ch2-数学基础,19,Miller-Rabin素性概率检验算法,WITNESS(a, n) (1) 将(n-1)表示为二进制形式bkbk-1b0 (2) d1 for i=
12、 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.,2019/3/15,Ch2-数学基础,20,算法有两个输入,n是待检验的数,a是小于n的整数。如果算法的返回值为TRUE,则n肯定不是素数,如果返回值为FALSE,则n有可能是素数。 for循环后,有d = an-1 mod n,由费马定理可知,若n为素数,则d为1,因此若d1,则n不是素数,所以返回TRUE。
13、因为n-1-1 mod n,所以x1,x n-1,表示x 21 (mod p)有不在-1,1中的根,因此n不为素数,返回TRUE,2019/3/15,Ch2-数学基础,21,离散对数,离散对数是许多公钥算法的基础 本原根这一个重要概念 假设gcd (a, n) =1,如果m是使am 1 mod n 成立的最小正整数,则称它是a对模n的指数,记为Ordna 若Ordna =(n),则称a是模n的本原根(primitive root),也称生成元,2019/3/15,Ch2-数学基础,22,求模7和模15的本原根,对于模7而言,满足gcd (a, n) =1的a是1,2,3,4,5,6,将它们的指
14、数列表如下,从上表可以看到,当a是3和5时,Ord7a =(7),因此,3和5是模7的本原根。,2019/3/15,Ch2-数学基础,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是奇素数,2019/3/15,Ch2-数学基础,24,本原根的测试,通常找出一个本原根不是一件容易的问题 如果知道p-1的因子,它就变得容易 测试方法:令q1,q2, qn是p-1的素因
15、子,对于所有的q1,q2, qn, 计算a(p-1)/q (mod p) ,如果对某个q的某个值其结果为1,那么a 不是一个本原根。如果对某个q的所有值其结果都不为1 ,那么a 是一个本原根。,2019/3/15,Ch2-数学基础,25,例2.9 假设p=11, 检验2和3是否是一个本原根。 解: 当p=11时, p-1=10,p-1有两个素因子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 (
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 信息 安全 原理 技术 ch02 数学 基础
链接地址:https://www.31doc.com/p-2276779.html