第五讲-密码学的数学基础(第二部分)

2013/10/231第五讲密码学数学基础2013/10/232★本章授课提纲★（1）整除、素数、最大公约数，欧几里德算法（2）模运算、同余、乘法逆元素、扩展的欧几里德算法（3）中国剩余定理、费马小定理、欧拉定理（4）模的幂、模n逆矩阵、模n平方根（5）有限域理论（6）素数判定和因数分解2013/10/233★本讲授课提纲★（1）有限域及其元素的多项式表示法（2）有限域GF(pm)上的代数运算2013/10/234★本讲授课提纲★（1）有限域及其元素的多项式表示法（2）有限域GF(pm)上的代数运算2013/10/235★有限域的概念★群的概念群（G）：定义了二元运算（表示为.）的集合（a,b）－(a.b)满足：封闭性(A1):a.b属于G结合律(A2):a.(b.c)=(a.b).c单位元(A3):存在e使得a.e=e.a=a逆元(A4):存在a’使得a.a’=a’.a=e2013/10/236★有限域的概念★交换群的概念交换群就是满足交换律的群交换律(A5)：a.b=b.a交换群例子：加法运算下的整数集合（＋，－，0）；乘法运算下的非零实数集合；2013/10/237★有限域的概念★域的概念若一集合F在已定义的两个运算“+”和“.”中，具有下列性质者，则F称为一个域。（1）F在运算“+”中为一交换群，且具有单位元素0（2）F非零的元素在“.”中也为交换群（注意：交换群有逆元存在）（3）F中“.”对“+”运算满足分配律，即对F中的所有a,b,c满足a.(b+c)=a.b+a.c2013/10/238定义2:有限群、无限群、交换群、循环群；群的阶：一个有限群的元的个数。定义3G中元素g的阶为的最小正整数m的值.定理1假设G是一个阶为n的乘法群,G中元素g的阶整除n.定理2如果p是素数,则是一个循环群.定义4如果p是素数,g是中阶为p-1的元,则称g为模p的本原元或生成元.1mgpp2013/10/239一般地,如果a的阶m等于φ(n)，则称a为n的本原根。如果a是n的本原根，则a,a2,…,aφ(n)在modn下互不相同且都与n互素。特别地，如果a是素数p的本原根，则a,a2,…,ap-1在modp下都不相同。2013/10/2310例如：n=9，则φ(n)=6，考虑2在mod9下的幂21mod9≡2,22mod9≡423mod9≡8,24mod9≡7，25mod9≡5,26mod9≡1。即2的阶为φ(9)，所以2为9的本原根2013/10/2311★有限域的概念★本质上说：域就是一个集合，可以在其上进行加法、减法、乘法和除法而不脱离该集合。域的概念例子:有理数集合，实数集合，复数集合这些都是无限域2013/10/2312★有限域的概念★一个域，如果其元素个数为无限个，则称为无限域反之，如果域的元素个数为有限个，则称为有限域有限域的概念有限域的例子：模p的同余运算中，它的完全剩余集构成一个域，通常用GF(p)表示。2013/10/2313例如：n=19，a=3在mod19下的幂分别为3，9，8，5，15，7，2，6，18，16，10，11，14，4，12，17，13，1。即3的阶为18=φ(19)，所以3为19的本原根。2013/10/2314本原根不惟一。可验证除3外，19的本原根还有2，10，13，14，15。注意并非所有的整数都有本原根，只有以下形式的整数才有本原根：2,4,pα,2pα其中p为奇素数。2013/10/2315离散对数设p是素数，a是p的本原根，即a1,a2,…,ap-1在modp下产生1到p-1b∈{1,…,p-1}，有惟一的i∈{1,…,p-1}使得b≡aimodp。称i为模p下以a为底b的离散对数，记为i≡logab(modp)。当a、p、i已知时，用平方和乘法可比较容易地求出b，但如果已知a、b和p，求i则非常困难。目前已知的最快的求离散对数算法其时间复杂度为：所以当p很大时，该算法也是不可行的。2133explnlnlnOpp2013/10/2316离散对数问题的算法首先回忆一下一般对数的概念，指数函数y=ax(a0,a≠1)的逆函数称为以a为底x的对数，记为y=logax。对数函数有以下性质：loga1=0,logaa=1,logaxy=logax+logay,logaxy=ylogax在模运算中也有类似的函数。设p是一素数，a是p的本原根，则a,a2,…,ap-1产生出1到p-1之间的所有值，且每一值只出现一次。因此对任意b∈{1,…,p-1}，都存在惟一的i(1≤i≤p-1)，使得b≡aimodp。称i为模p下以a为底b的离散对数，记为i=logab。2013/10/2317离散对数有以下性质：①loga1=0。②logaa=1。分别由以下关系得出：a0modp=1modp=1,a1modp=a。以上假定模数p是素数，对于非素数也有类似的结论。2013/10/2318★有限域的概念★有限域GF(pm)上元素的多项式表示数学家已经证明，一个有限域GF(k)，其k必为p或者pm(p为素数)，其它的k将不能构成有限域。pm(p为素数)的完全剩余集的每一个元素，可以使用m位的p进制数来表示，并进而可以使用多项式来表示。2013/10/2319★有限域的概念★有限域GF(pm)上元素的多项式表示121210mmmmaaxaxaxa令a∈GF(pm)，则a可表示成如下阶数为m-1的多项式其中的系数ai为模p的整数，该表达式实质上是把一个整数用m位的p进制数来表示，系数ai就是每一位的具体数字。2013/10/2320★有限域的概念★有限域GF(pm)上元素的多项式表示121210mmmmaaxaxaxa有限域中的每一个元素a，都是模f(x)的一个余数，f(x)为一阶数为m在模p中的不可分解的多项式。所谓“模p的不可分解的多项式”，意味着f(x)不可分解为阶数小于m的多项式的乘积。例如f(x)=x3+x+1在GF(2n)中为不可分解多项式。2013/10/2321★有限域的概念★有限域GF(pm)上元素的多项式表示121210mmmmaaxaxaxa举例：在GF(33)，即GF(27)中，222axx表示3位3进制数212，它转换成十进制数为2×32+1×31+2＝232013/10/2322★本讲授课提纲★（1）有限域及其元素的多项式表示法（2）有限域GF(pm)上的代数运算2013/10/2323★有限域GF(pm)上的代数运算★多项式的加减乘除运算2013/10/2324★有限域GF(pm)上的代数运算★令a,b∈GF(pm)，有限域GF(pm)上的加法和减法121210mmmmaaxaxaxa121210mmmmbbxbxbxb121210mmmmcabcxcxcxc(mod)1iiicabpim那么其中2013/10/2325★有限域GF(pm)上的代数运算★121210mmmmcabcxcxcxc举例：在GF(33)中，若a=2x2+x+2，b=2x2+2x+2有限域GF(pm)上的加法和减法(mod)1iiicabpim那么，c=a+b=x2+12013/10/2326★有限域GF(pm)上的代数运算★在有限域内，把减法看作加法对待举例：在GF(33)中，若a=2x2+x+2，b=2x2+2x+2那么c=a-b=x有限域GF(pm)上的加法和减法121210mmmmcabcxcxcxc(mod)1iiicabpim2013/10/2327★有限域GF(pm)上的代数运算★有限域GF(pm)上的乘法和除法若a,b∈GF(pm)，a与b的乘积与一般的多项式乘积相同。其差别为，若其积的阶数等于或比m大时，必须以不可分解多项式f(x)除之。举例：在GF(33)中，若a=2x2+x+2，b=2x2+2x+2求d=ab2013/10/2328★有限域GF(pm)上的代数运算★有限域GF(pm)上的乘法和除法举例：在GF(33)中，若a=2x2+x+2，b=2x2+2x+2求d=ab(1)先求ab:212×222121121+12110101=x4+x2+12013/10/2329★有限域GF(pm)上的代数运算★有限域GF(pm)上的乘法和除法举例：在GF(33)中，若a=2x2+x+2，b=2x2+2x+2求d=ab(2)再除以f(x)=x3+2x+1x4+x2+1——10101x3+2x+1——1021二者相除，得到的余数是221即最终结果为2x2+2x+12013/10/2330★有限域GF(pm)上的代数运算★有限域GF(2m)上的代数运算有限域GF(2m)上的代数运算，是密码学里最为关心的，因为现代密码学系统中绝大部分数据都是01这样的比特。加、减运算是异或，加无进位，减无借位，乘法运算是“与”，除法运算只要位数够长即可进行。2013/10/2331★有限域GF(pm)上的代数运算★有限域GF(2m)上的代数运算举例2013/10/2332★有限域GF(pm)上的代数运算★有限域GF(23)上的代数运算举例2013/10/2333★本章授课提纲★（1）整除、素数、最大公约数，欧几里德算法（2）模运算、同余、乘法逆元素、扩展的欧几里德算法（3）中国剩余定理、费马小定理、欧拉定理（4）模的幂、模n逆矩阵、模n平方根（5）有限域理论（6）素数判定和因数分解2013/10/2334★本讲授课提纲★（1）素数判定概述（2）米勒－拉宾素数判定（3）因数分解概述2013/10/2335★本讲授课提纲★（1）素数判定概述（2）米勒－拉宾素数判定（3）因数分解概述2013/10/2336★素数判定概述★素数在公钥密码体制中的重要性公开密钥密码体制中需要大的素数，如基于因数分解困难性的RSA体制的密钥就是两个非常大的素数的乘积，如果素数选择过小，则分解它们是容易的，因而整个RSA密码体制系统就不安全。ElGamal是基于离散对数求解困难的公钥密码体制，同样需要产生非常大的素数，以保证密码体制的安全。这种非常大的素数通常也叫强素数2013/10/2337★素数判定概述★在长度为512位或略短一些的数中，有超过10151个素数。宇宙中仅有1077个原子，如果宇宙中从诞生到现在为止，每一微秒都需要10亿个新的素数，那么总共需要10109个素数，现在仍然剩下约10151个512位的素数。素数有多少个呢？2013/10/2338★素数判定概述★素数定理给出一种估计素数个数的方法：设π(x)是小于x的素数的个数，则π(x)≈x/lnx应用举例：64位二进制表示的素数的个数为264/ln264-263/ln263≈2.05×1017个素数定理2013/10/2339★素数判定概述★（1）素数分布极不规则（2）素数越大，其分布越稀疏。因为整数越大，比它小的素数也越多，从而被比它小的素数整除的概率也越大。平均而言，在64，128，256位中任选约23，46，92次奇数，即可获得一素数。素数的分布特点2013/10/2340★素数判定概述★欧拉定理是素数判定的必要非充分条件欧拉定理：对于任何互素的两个整数a和n，有aφ(n)≡1(modn)如果n=p是素数，则有ap-1≡1(modp)但是，反过来如果ap-1≡1(modp)，并不能推出p是素数2013/10/2341★素数判定概述★二次探测定理是素数判定的必要非充分条件二次探测定理：如果p是一个素数，且0xp，则方程x21(modp)的解为x=1，p-1。如果(p-1)21(modp)，那么p很有可能是素数，但仍然不能肯定p就是素数。像这样，满足欧拉定理和二次探测定理，但不是素数的合数，常被称为“伪素数”2013/10/2342★素数判定概述★Wilson定理是素数判定的充要条件Wilson定理：对于给