《密码学的数学基础课件.ppt》由会员分享，可在线阅读，更多相关《密码学的数学基础课件.ppt（37页珍藏版）》请在三一办公上搜索。
1、密码学的数学基础,初等数论素数的产生有限域内的离散对数单向哈希函数,初等数论,1.模运算2.素数3.最大公因数4.乘法逆元素5.Fermat小定理及欧拉函数6.中国剩余定理7.二次剩余8.Legendre（勒让得）符号9.Jacobi（雅各比）符号10.生成元11.有限域中的计算,1 模运算,同余：如果a=b+kn，k为整数，则a b（mod n）a mod n：a模n操作，表示a除以n的余数，为 0到n 1之间的整数。例如：(79)mod 12=16 mod 12=4 模运算（+、）满足交换律、结合律和分配律。按模计算原理：对中间结果作模运算与做完了全部运算后再做模运算结果相同。,按模指数运
2、算：am mod n将指数运算作为一系列乘法运算，每次做一次模运算。例：a8 mod n=(a2 mod n)2 mod n)2 mod n当m不是2的乘方时，将m表示成2的乘方和的形式。例如：25=(11001)2，即25=24+23+20 a25 mod n=(a16 a8 a)mod n=(a2)2)2)2(a2)2)2 a)mod n=(a2 a)2)2)2 a)mod n适当存储中间结果，则只需6次乘法：(a2mod n)a)mod n)2mod n)2mod n)2mod n)a)mod n,定理：若ab mod m，cd mod m，则1.acbd mod m2.acbd mod
3、 m证：a=km+b；c=hm+d,定理：若ac bc mod m，且gcd（c,m）=1，则ab mod m 证明：因为 ac bc mod m所以 ac=km+bc所以 c（a-b）=km又因为 gcd（c,m）=1所以 c|k所以 k=hc所以 a-b=hm所以 ab mod m,定理：若acbc mod m，d=gcd（c,m），则：ab mod m/d 因为 acbcmod m所以 ac=km+bc所以 c（a-b）=km又因为 d=gcd（c,m）所以 c=c1d，m=c2d，gcd（c1,c2）=1所以 c1d（a-b）=kc1d所以 c1（a-b）=kc2又因为 gcd（c1,
4、c2）=1所以 c1|k所以k=hc1所以 a-b=khc2所以 ab mod c2 所以 ab mod（m/d）,2 素数,素数（质数）：大于1的整数，只能被1和本身整除。有无穷多个素数。如：2，73，2521，2365347734339，2756839-1,整数的表示法1987的10进制表示：110391028107定理：设m是大于1的正整数，则每个正整数n可唯一的表示为：n=CkmkCk-1mk-1C1mC0 m为基（radix）设n0=n，则n1=n0/m C0=n0 mod m所以 Ci=ni mod m ni1=ni/m,例：n=389；m=5n0=389；C0=389 mod m
5、=4n1=389/5=77；C1=n1 mod 5=2n2=77/5=15；C2=n2 mod 5=0n3=15/5=3；C3=n3 mod 5=3所以 389=353254=（3024）5,3 最大公因数,公因数：两个整数a，b的公因数定义为能同时整除a，b的所有整数。3为6的因子，记为3|6，3除尽6 任意的a|b，a|c，称a为b，c的公因子 最大公因数：a与b的公因数中能被所有a，b的公因数整除的正整数，记为gcd(a，b)。互素（互质）：两个整数称为互素的，如果它们除了1以外没有其他的公因数，即 gcd(a,b)=1。,定理：若a=bq+r，则gcd（a,b）=gcd（b,r）证明：
6、d=（a,b），d=（b,r）d|a bq d|r，d为b,r的公因数；d|d d=hdd|bq+r d|a，d为a,b的公因数；d|d d=kd所以 kh=1 k=h=1；,最大公因数的求法：辗转相除法例如：求gcd(15,36)36=15 2+615=6 2+36=3 2+0因此，gcd(15,36)=3原理：若a b(mod c)，则 gcd(a,c)=gcd(b,c)这里，gcd(15,36)=gcd(15,6)=gcd(6,3)=3求最大公因数的Euclid算法,4 乘法逆元素,求x，满足(a x)mod n=1,即 x a-1(mod n)当a与n互素时,方程 x a-1(mod
7、n)有唯一解；当a与n不互素时,此方程无解。如果n为素数，则从1到n-1的任意整数都与n互素，即在1到n-1之间都恰好有一个关于模n的乘法逆元。求乘法逆元：扩展的Euclid算法例：求5关于模14的乘法逆元辗转相除：14=5 2+4 5=4+1逆推：1=5-4=5-（14-5 2）=5 3-14 因此，5关于模14的乘法逆元为3。,5 Fermat小定理及欧拉函数,Fermat小定理：如果m为素数，a不能被m整除，则 am-1 1(mod m)模n的简化剩余集：模n的完全剩余集的一个子集，其中每个元素与n互素。欧拉函数：记为(n)，为模n的简化剩余集中元素的个数。如果n是素数，则(n)=n-1
8、设n=p1r1 p2r2 pmrm,其中p1,p2,pm是n的素数因子,则(n)=n(1-1/p1)(1-1/p2)(1-1/pm)欧拉扩展的Fermat小定理：如果gcd(a,n)=1，则 a(n)mod n=1。,6 中国剩余定理,定理：如果n的素数因子分解式为p1p2 pt，则一组方程(x mod pi）=ai，其中i=1,2,t，有唯一解x，其中x小于n（其中某些pi可能相等）。例：今有物不知其数，三三数之剩二，五五数之剩三，七七数之剩二，问物几何？x mod 3=2x mod 5=3x mod 7=2,定理：令d1，d2，,dt为两两互素，并令n=d1d2dt，则 x mod di
9、xi(i=1,t)在0，n-1范围内有公共解x：x=mod n其中：mi=n/di，yi=mi-1 mod di,解法：令a1=2，a2=3，a3=2，p1=3，p2=5，p3=7，n=p1 p2 p3=105，M1=n/p1=35,M2=n/p2=21,M3=n/p3=15求解 35 x1 mod 3=1,得x1=2求解 21 x2 mod 5=1,得x2=1求解 15 x3 mod 3=1,得x3=1则 x=(M1 x1 a1+M2 x2 a2+M3 x3 a3)mod n=(35 2 2+21 1 3+15 1 2)mod 105=233 mod 105=23,孙子定理的应用：3x mo
10、d10=1解：10=25，3x1 mod2=1 and 3x2 mod 5=1x1=3(2)-1mod2=1,m1=5,m1-1=5(2)-1mod2=1x2=3(5)-1mod5=2,m2=2,m2-1=2(5)-1mod5=3所以 x=（151223）mod10=7,7 二次剩余,定义：设p为素数，a0且ap，如果存在某个x，满足x2 a(mod p)，则称a为模p的二次剩余；否则称a为模p的非二次剩余。,8 Legendre（勒让得）符号,记为L(a,p)，其中a为任意整数，p为大于2的素数。定义：L(a,p)=0，如果a能被p整除；L(a,p)=1，如果a是模p的二次剩余；L(a,p)
11、=-1，如果a是模p的非二次剩余；计算：L(a,p)=a(p-1)/2 mod p计算法则（略）,9 Jacobi（雅各比）符号,记为J(a,n)，是Legendre符号的扩展，其中a为任意整数，而n为任意奇数。定义：J(a,n)只对n为奇数时有意义J(0,n)=0如果n为素数，且n|a，则J(a,n)=0如果n为素数，且a是模n的二次剩余，则J(a,n)=1如果n为素数，且a是模n的非二次剩余，则J(a,n)=-1如果n是合数，则J(a,n)=J(a,p1)J(a,p2)J(a,pm)，其中将n因数分解为p1p2pm,Jacobi符号的计算（略）Blum整数：若p和q为两个素数，且都与3模4
12、同余，则n=pq称为Blum整数。若n为Blum整数，则每个模n的二次剩余恰好有4个平方根，其中一个也是一个二次剩余，称为原平方根。例如，139的模437的原平方根为24，另三个平方根为185，252和413。,10 生成元,定义：如果p为素数，gp，如果对每个b从1到p-1，存在a，使ga b(mod p)，则g为模p的生成元。例：p=11，2为模11的生成元生成元的测试 素数q,q|p-1,s.t g(p-1)/q mod p=1,则g不为p的生成元,11 有限域中的计算,有限域：元素个数有限的域，也叫伽罗瓦（Galois）域。在有限域中，非0数的加、减、乘、除都有定义。加法单位元是0，乘
13、法单位元是1，每个非0元素都有一个唯一的乘法逆元。有限域中运算满足交换律、结合律和分配律。有限域中元素个数为素数或素数的乘方：设p为素数，则有限域可记为GF(p)或GF(pn)。,不可约多项式：一个多项式如果除了1和本身外，不能分解成其他多项式的乘积形式，则成为不可约多项式。本原多项式：一个有限域内的生成元多项式，其系数是互素的。在GF(qn)中，所有运算都是模p(x)的运算，其中p(x)是n阶不可约多项式。,GF（pn）表示形式如：a=an-1xn-1+a1x+a0,其中ai是mod p的整数。也表示：an-1an-2a1a0一般研究GF（2n），如GF（25）：a(x)=x4+x3+1表示
14、11001。若p（x）不能为次数小于n的多项式之积，则p（x）称既约多项式。,二元多项式系数的运算：（U+V）mod 2=UV=0 or 1 UV=UV UV=UV例：GF（25）：a(x)=x4+x2+1,b(x)=x3+x2ab=10101+01100=11001,例：a=101，p（x）=x+x+1，GF（2），求（aa）mod p（x）aa=10001，p（x）=x+x+1=1011如果 p（x）为GF（2n）的既约多项式，则（p（x）=2n1。例：a=100，p=1011，GF（2），求a-1 练习：a=011，p（x）=1011，GF（2），求a-1,素数的产生,因数分解：对一个数
15、进行因数分解，是指找出这个数的素数因子。素数的产生:1.Solovay-Strassen方法2.Lehmann法3.Rabin-Miller法4.实际应用5.强素数,1 Solovay-Strassen方法,用Jacobi符号来测试p是否为素数：（1）选择一个随机数a，ap；（2）如果gcd(a,p)1，则p是合数，停止检测；（3）计算i=a(p-1)/2 mod p；（4）计算Jacobi符号J(a,p)；（5）如果i J(a,p)，则p不是素数；（6）如果i=J(a,p)，则p不是素数的概率小于50%。对t个不同的随机数a，重复进行这个测试。能通过所有t个测试的奇数是合数的概率小于1/2t
16、。,2 Lehmann法,测试p是否为素数：（1）选择一个小于p的随机数a；（2）计算a(p-1)/2 mod p；（3）如果a(p-1)/2 mod p 1或1(mod p)，则p不是素数；（4）如果a(p-1)/2 mod p 1或1(mod p)，则p不是素数的概率小于50%。,3 Rabin-Miller法,选择一个随机数p，进行测试。计算b，其中b是能整除p-1的2的次方数（即2b是指整除p-1的最大的2的幂），然后计算m，使得p=1+2b*m。（1）选择一个随机数a，使a小于p；（2）令i=0，Z=am mod p；（3）如果Z=1，或Z=p-1，则p可能是素数，通过了检测；（4）
17、如果i0，且Z=1，则p不是素数；（5）令i=i+1，如果ib且Z p-1，令Z=Z2 mod p，返回第（4）步。如果Z=p-1，则p通过检测，可能是素数；（6）如果i=b且Z p-1，则p不是素数。一个奇合数通过t次测试的概率小于1/4t。,4 实际应用,（1）产生一个n位随机数p（n位二进制）；（2）将最高位和最低位置为1；（3）检查p是否能被小素数整除：3，5，7，11，等等。许多实际应用中都用小于256地所有素数去除p；（4）对于随机数a，进行Rabin-Miller测试，如果p通过了，则产生另一个随机数a，再进行测试。选择值小一些的a可以令计算更快。做5次测试，如果p没通过其中的一
18、次，则产生另一个p再测试。,5 强素数,强素数p,q：能令乘积n难以用特定的因数分解算法进行因数分解的素数。性质：p-1和q1的最大公因数很小p-1和q-1都有大素数因子，记为p，q；p-1和q-1都有大素数因子；p+1和q+1应该都有大素数因子；(p-1)/2和(q-1)/2都是素数。,有限域内的离散对数,求x，使ax b(mod n)当n很大时，这是一个困难的问题并非所有的离散对数问题都有解密码学中常用的离散对数：GF(p)的乘法群GF(2n)的乘法群EC(F),单向哈希函数,定义：一个单向哈希函数H(M)，操作一个任意长度的消息M，返回一个固定长度的值h。h=H(M)。性质：给定M，很容易计算h；给定h，很难计算M，使H(M)=h；给定M，很难找到另一个消息M，使H(M)=H(M)。,
