信息安全导论5密码学数学基础.ppt

2020/4/29,1,信息安全导论第五讲密码学技术中的数学基础华中科技大学图象所信息安全研究室Dr.ZuxiWang,2020/4/29,2,密码学是研究密码系统或通信安全的一门学科，分为密码编码学和密码分析学。密码编码学是使得消息保密的学科，从事此行的称为密码编码者。密码分析学（密码破译学）是研究加密消息的破译的学科，从事此行的称为密码分析者。精于此道的人被称为密码学家，现代的密码学家通常是理论数学家。,2020/4/29,3,密码学是一门交叉学科，它很大程度上是应用数学学科。密码学中涉及数论、代数、概率论、组合数学、计算复杂理论等多种数学知识。还涉及信息论学科知识。密码学所涉及的知识十分广阔，这里仅介绍部分数学基本知识。,2020/4/29,4,数论基础,素数同余、模运算中国剩余定理Euclean算法Fermat定理、Euler定理素性检验因子分解离散对数,2020/4/29,5,整除、素数,记整数集合Z=,-3,-2,-1,0,1,2,3,整除设a,bZ，a0，如果存在mZ，使得b=ma，则称a整除b，以a|b表示，a是b的一个因子或约数。如果没有任何m，使得b=ma，则称a不能整除b,记ab，此时有a=mb+r且01被称为素数是指p的因子仅有1，-1，p，-p。否则，称为合数。,2020/4/29,6,整除基本性质a|a;b0，b|0;Ifa|b,b|c,thena|c;ifa|1,thena=1;ifa|b,andb|a,thena=b;ifb|gandb|h,thenb|(mg+nh),foranyintegersmandn注意:ifa=0modn,thenn|a,2020/4/29,7,互素与最大公约数,最大公约数（最大公因子）：若a,b,cZ，如果ca，cb，称c是a和b的公约数。正整数d称为a和b的最大公约数(记d=gcd(a,b)或(a,b)，如果它满足:d是a和b的公约数。对a和b的任何一个公约数c有cd。等价的定义形式是：gcd(a,b)=maxk:ka，kb若gcd(a,b)=1，称a与b是互素的。,2020/4/29,8,最小公倍数,最小公倍数a,b的倍数中最小者称为a,b的最小公倍数，记为：lcm(a,b)a,b不全为0，有ab=gcd(a,b)lcm(a,b).注意：对有限个整数a1,a2,an,也可定义最大公约数gcd(a1,a2,an)和最小公倍数lcm(a1,a2,an).,2020/4/29,9,带余除法,带余除法：aZ,m0，可找出两个唯一确定的整数q和r使a=qm+r,0rP2P3Pt是素数，其中i0整数。,2020/4/29,11,目前没有可用于整数分解的有效算法。对于整数a,b(a,b2)，a,b的素数分解式分别为：，其中ei，fi0,ti1，则有：,2020/4/29,12,带余除法中，aZ，m0，a=qm+r，0r1）分成一些两两不交的等价类（剩余类）。2、整数模m同余类共有m个，他们分别为mk+0,mk+1,mk+2,mk+(m-1);kz，每一个算一类，每一类都可以选一个代表元，一般选这一类中的最小的非负整数。于是称0,1,2,m-1为标准完全剩余系。其中与m互素的剩余类构成模m的简约剩余系。Z模12的标准完全剩余系为：0,1,2,3,4,5,6,7,8,9,10,11,2020/4/29,14,Modulo7Example,.-21-20-19-18-17-16-15-14-13-12-11-10-9-8-7-6-5-4-3-2-1012345678910111213141516171819202122232425262728293031323334.,2020/4/29,15,3、模运算：对于某个固定模m的同余式可以象普通的等式那样相加相减和相乘：a(modm)b(modm)=(ab)(modm)a(modm)*b(modm)=a*b(modm)例：由同余式演算证明5601是56的倍数，2231是47的倍数。解：注意53=12513(mod56)于是有561691(mod56)对同余式的两边同时升到10次幂，即有56(560-1)。其次,注意26=64-30(mod47),于是223=(26)325=(2626)2625900*(-30)*(32)mod(47)(7)*(-30)*(32)(mod47)1(mod47)于是有47(223-1),2020/4/29,16,Modulo8Example,2020/4/29,17,4、定理：(消去律)对于abac(modm)来说，若最大公因子gcd(a,m)1（即a与m是互素），则bc(modm)加法消去律：a+ba+c(modm)，有bc(modm).5、一次同余方程axb(modm)，这个方程有没有解，相当于问有没有那样一个整数x，使得对于某个整数y来说，有ax+my=b定理：记最大公因子(a,m)=d，则同余方程axb(modm)有解的充分必要条件是db。当这个条件满足时，恰有d个模m同余类中的整数是上述方程的解。证明：略。（从ax+my=b入手）,2020/4/29,18,6、整数环z模正整数m得到的剩余类集合可以记为zm(或z/(m),zm=0,1,m-1在3、中已说明zm对剩余类的加法，乘法是封闭的，可列出它们的加乘表。我们称zm为剩余类环（或同余类环）7、在整数环z中是没有零因子的，即两个非零整数的乘积一定不等于0，但是剩余环则不然。例z12中：3*4=12=0说明，zm中的元素可分为两类，一类是零因子，即若zm,0，存在zm且0，有*=0，则称，都为zm中的零因子。另一类是可逆元，即若zm，存在zm，使*=1，此时,互为各自的逆元，记-1=；-1=,2020/4/29,19,定理：剩余类环zm中元素=a为zm的可逆元最大公约数(a,m)=1要证明这个定理，只需证明下列引理：引理：任意两个整数a和b都有一个最大公约数，这样一个最大公约数d可以表示成a,b二数关于整系数的线性组合，即有s,tz，使dsatb。证明：不妨设b0，用辗转相除法，先用b去除a，得a=q1b+r1,0r1b;(1)如果r1=0，停止，否则再用r1去除b，得b=q2r1+r2,0r2r1;(2)如果r2=0，停止，否则再用r2去除r1，得r1=q3r2+r3;0r3r2;(3)等等，这样一直进行下去，可得一系列关系式：rk-3=qk-1rk-2+rk-1,0rk-1r3r4rk0是严格递降的一串非负整数，故最后总会出现余数为0的情形：rk-1=qk+1rk(k+1)所以，进行有限步必停止，此时d=rk=(a,b)成立，这是因为1).可知rk为a和b的公约数，只要按倒序分析自然有此结论。2).a和b的任何一个公约数c都是rk的约数，只要按正序分析，自然可知。为证定理的后一部分，将式(1)做移项有r1=s1a+t1b（其中s1=1,t1=-q1）再将式(2)右端通过移项变为r2=s2a+t2b这样一直下去，最后得d=rk=s*a+t*b,s,tz.,2020/4/29,21,例子：求(180，252)，并将他表示为180和252这两个数的一个带整系数的线性组合。解：252=1*180+72(1)180=2*72+36(2)72=2*36(3)得(180,252)=36，同时有72=252-1*180(1)由(2)得36=180-2*72(2)将(1)代入(2)，即得36=180-2*(250-180)=3*180-2*252,2020/4/29,22,中国剩余定理,例子：（孙子算经）今有物不知其数：三三数之余二；五五数之余三；七七数之余二。问物几何？答曰：二十三。232*70+3*21+2*15(mod105)（口诀：三人同行七十稀，五树梅花廿一枝，七子团圆月正半，除百零五便得知。）问，70，21，15如何得到的？原问题为：求解同余方程组,2020/4/29,23,注意：若x0为上述同余方程组的解，则x0=x0+105*k(kz)也为上述同余方程组的解。有意义的是，解题口诀提示我们先解下面三个特殊的同余方程组(1)(2)(3)的特殊解=?=?=?以方程（1）为对象，相当于解一个这样的同余方程35y1(mod3)，为什么呢？原因是，从（1）的模数及条件知，x应是35的倍数，于是可以假设x35y，有,2020/4/29,24,35y1(mod3)相当于2y1(mod3)解出y=2（mod3）于是x35*2(mod(3*35)70(mod105)类似地得到（2）、（3）方程的模105的解21、15。于是有得,2020/4/29,25,中国剩余定理：设自然数m1,m2,mr两两互素，并记M=m1m2mr，则同余方程组在模M同余的意义下有唯一解。,2020/4/29,26,证明：考虑方程组，(1=i=r)由于诸mi(1=i1时，它的值(n)等于比n小而与n互素的正整数的个数。以n24为例，比24小而与24互素的正整数为：1,5,7,11,13,17,19,23。因此，我们有(24)8。若p为素数，则(p)p-1。若p，q都为素数且pq，此时有(pq)(p)(q)=(p-1)(q-1)证明：考虑zpq剩余类的集合是0，1，2，（pq-1）,集合中与pq不互素的元素子集为p,2p,(p-1)q和子集q,2q,(p-1)q以及0，于是若设npq，有(n)=pq-(q-1)+(p-1)+1=(p-1)(q-1)=(p)(q).例：(21)=(3*7)=(3)(7)=2*6=12.,2020/4/29,33,若m1,m2互素，则(m1m2)(m1)(m2).设n=p1e1p2e2prer，其中p1,p2,pr为互异素数，则(n)=p1e1-1p2e2-1prer-1(p1-1)(p2-1)(pr-1)=n(1-1/p1)(1-1/p2)(1-1/p3)(1-1/pr)Euler公式证明：考虑1/n,2/n,n/n，然后化简成既约分数，分母为d的一类分数有(d)个，于是欧拉定理（Euler）：若整数a与整数n互素，则a(n)1(modn)。证明：设小于n而和n互素的(n)个正整数为r1,r2,r3,r(n)(1),2020/4/29,34,他们是模n两两互不同余的。对每一个定数i来说，由于a和ri都与n互素，所以(ari,n)=1，所以ari同余于（1）中的某个ri即ariri(modn)，1i(n)并且当ij时有ari/arj(modn).于是,为的置换.所以有由(ri,n)=1,所以Remarks：1*.np时，(a,p)=1,有ap-11(modp)为Fermat定理！而对任意的a，有apa(modp)（Fermat）2*.易见a(n)+1a(modn)3*.若n=pq，p与q为相异素数，取00），那么称该算法运算的时间是多项式阶的，假如T(n)=O(ap(n)（a0），则称该算法运算的时间是指数阶的。其中P(n)是n的一个多项式。对于指数阶的运算时间算法，适当增大n，计算将变成不可能。因此，一般认为，如果破译一个密码体制所需的时间是指数阶的，则它在计算上是安全的，因而实际上也是安全的。,空间复杂性和时间复杂性往往是可以相互转换的。比如，可以预算某些明文和密文对，分析时只需使用查询即可，这样计算的时间就转换成了存储空间。,2020/4/29,114,（2）P问题和NP问题：在理论研究中，算法通常分为确定性算法和非确定性算法。确定性算法的每一步操作结果都是确定的，其计算时间就是完成这些确定步骤所需的时间。而不确定性算法的某些操作结果是不确定的，在所有使算法成功操作的序列中，所需时间最少的序列所需时间就是该不确定性算法的计算时间。使用确定性算法可以在多项式时间内求解的的问题称为P问题。在多项式时间内可以用非确定性算法求解的问题称为NP问题。,注意：NP问题包含P问题，NP问题中许多问题可能要比P中的问题难得多，但是P问题中是否包含NP问题，目前还没有证实。同时PNP目前有没有证明，但是如果P=NP，那么整个密码学将失去意义，密码算法也不再是牢不可破的。因此，计算复杂性理论也密码技术的基础理论之一。现已证明，正整数因式分解问题就是一个NP问题。,问题复杂性,2020/4/29,115,在实际研究中，如果问题X可以在多项式时间内用确定性算法转化为问题Y，而Y的解可以在多项式时间内用确定性算法转化为X的解，则称问题X可规约化为问题Y。因此，如果某类NP问题中任何一个问题可以规约为问题Y，而且Y本身就是NP问题，则称Y是一个NP完全问题，记为NPC。而对于一个NP问题，不存在任何已知的确定性算法在多项式时间内求解该问题，所以如果能找到一个计算序列作为解密算法，那么密码分析者在不知道计算序列的情况下来求解问题（称为客观求解）在计算上是不可能的。由此可见，NP问题可以用来构造密码体制。Diffie和Hellman通过大量的证明指出，NPC问题更适合构造密码体制。因为现在密码算法的安全性都是基于NPC问题的，这样若想破译一密码体制相当于解一NPC问题。,2020/4/29,116,典型的NPC问题有：大整数因子分解问题当n较小时，问题不难，但当n较大时就变得非常困难。特别当n达到几百位时，用现有算法中最快的计算机也不行。背包问题一支背包最多能装满总重量M的标本，现共有n件标本，每件的重量均为正整数，分别为a1,a2,an，且a1+a2+anM。现要求从n件标本中选出若干件，使得被选出标本的总重量为M。,2020/4/29,117,数学模型：已知正整数a1,a2,an和另一整数M，满足a1+a2+anM，现要找一数组(m1,m2,mn)，mi=0or1，I=1,2,n，使得m1a1+m2a2+mnan=M。n较小时可穷举得解。可n很大时，(m1,m2,mn)的各种选法有2n，随n指数增大，要验证多种选法已是计算上不可行的。离散对数问题设x,r,n是正整数。已知x,r和n，可很快算出y=xr(modn)。反过来，已知y,r和n，求r使得y=xr(modn),这便是离散对数问题。它属于NPC问题。,2020/4/29,118,Summary,关键术语概念双射、素数、合数、互素、因子、阶、中国剩余定理、带余除法、Euclean算法、Euler定理、Euler函数、Fermat定理本原根、离散对数、指标模运算、多项式模运算、多项式运算、余数(式)、取模运算群、环、域、有限域、循环群、置换群、剩余类群(环)、生成元、逆元、不可约多项式、最大公因子,2020/4/29,119,参考文献,密码编码学与网络安全原理与实践(第三版)张禾瑞：近世代数基础熊全淹：初等数论洪帆：离散数学基础,2020/4/29,120,作业,参考书密码编码学与网络安全原理与实践(第三版)p100102：4.1,4.9,4.13,4.14,4.15,4.19p186187：思考题：8.18.6习题：8.2,8.3,8.6,8.11,8.14,