搜索
信息安全原理与技术郭亚军宋建华李莉清华大学出版社2011-7-20Ch2-数学基础2第2章数学基础•主要知识点：--数论--代数基础--计算复杂性理论--单向函数2011-7-20Ch2-数学基础3因子•设Z表示全体整数所构成的集合。•定义2.1设a,b∈Z，a≠0，c∈Z，使得b=ac，则称a整除b，并称a是b的因子或者约数，b是a的倍数，记为a|b。•定理2.1（带余除法）设a,b∈Z，b≥1，则存在唯一的整数q和r，使得a=qb+r，0≤rb。q称a除以b所得的商，r称为a除以b所得的最小非负剩余。•定义2.2设a,b∈Z，a，b不全为0，如果c|a且c|b，则称c为a和b的公因子。特别地，我们把a和b的所有公因子中最大的，称为a和b的最大公因子，记为gcd(a,b)或者(a,b)。2011-7-20Ch2-数学基础4•计算两个数的最大公因子的最容易的方法是用欧几里德(Euclid)算法•定理2.3（欧几里德算法）给定整数a和b，且b0，重复使用带余除法，即每次的余数为除数去除上一次的除数，直到余数为0，这样可以得到下面一组方程：a=bq1+r1,0r1b,b=r1q2+r2,0r2r1,r1=r2q3+r3,0r3r2,……rj-1=rjqj+1最后一个不为0的余数rj就是a和b的最大公因子2011-7-20Ch2-数学基础5例2.1求gcd(1970，1066)•用欧几里德算法的计算过程如下：•1970＝1×1066+904•1066＝1×904+162•904＝5×162+94•162=1×94+68•94＝1×68+26•68＝2×26+16•26＝1×16+10•16＝1×10+6•10＝1×6+4•6=1×4+2•4＝2×2+0•因此gcd(1970，1066)=22011-7-20Ch2-数学基础6素数•定义2.4设p∈Z，p≥2，如果p的正因子只有1和p，则称p为素数，否则为合数•若正整数a有一因子b，而b又是素数，则称b为a的素因子•如果整数a与整数b的最大公因子是1，即gcd(a,b)=1，则称a与b互为素数，简称互素•设ϕ(m)为小于或等于m且与m互素的正整数个数，则称其为欧拉(Euler)函数2011-7-20Ch2-数学基础7同余•定义2.8两个整数a,b分别被m除，如果所得的余数相同，则称a与b对模m是同余的，记为a≡b(modm)，正整数m称为模数•同余具有下面的性质：(1)若a≡b(modm)，则则m|(b-a)。反过来，若m|(b-a)，则a≡b(modm)(2)如果a=km+b(k为整数)，则a≡b(modm)(3)每个整数恰与0,1,…，m-1这m个整数中的某一个对模m同余(4)同余关系是一种等价关系(5)a≡b(modm)当且仅当amodm=bmodm2011-7-20Ch2-数学基础8•定理2.8(乘法消去律)对于ab≡ac（modm）来说，若gcd(a,m)＝1则b≡c(modm)。•定理2.9(加法消去律)如果a+b≡a+c（modm），则b≡c(modm)•加法消去律是没有条件，但乘法消去律的条件是gcd(a,m)＝1，即a和m互素•例如6×3≡6×7≡2mod8，但3≡7mod8不成立2011-7-20Ch2-数学基础9模运算•求余运算称为模运算,下面是模运算的一些性质。(1)(a+b)modm=((amodm)+(bmodm))modm(2)(a-b)modm=((amodm)-(bmodm))modm(3)(a×b)modm=((amodm)×(bmodm))modm(4)(a×(b+c))modm=((a×b)modm)+((a×c)modm))modm•例如11mod8=3;15mod8=7,那么(11mod8)+(15mod8)mod8=(3+7)mod8=2(11+15)mod8=26mod8=2•在模运算中，加法单位元是0，(0+a)modm=amodm•乘法单位元是1，(1×a)modm=amodm2011-7-20Ch2-数学基础10•定义2.13对a∈Zm，存在b∈Zm，使得a+b≡0(modm)，则b是a的加法逆元，记b=-a。•定义2.14对a∈Zm，存在b∈Zm，使得a×b≡1(modm)，则称b为a的乘法逆元。•加法一定存在逆元，乘法不一定存在逆元。•在密码学特别是非对称密码体制中，常常需要求模逆元，求模逆元就是求乘法逆元。即寻找一个x，使得a×x≡1modm成立•求模逆元问题很困难，有时有结果，有时没有结果•利用扩展欧几里德算法能够计算出模逆元2011-7-20Ch2-数学基础11模8运算的例子•模8的加法和乘法运算与普通运算一样,只是将所得的值是去模8后的余数2011-7-20Ch2-数学基础122011-7-20Ch2-数学基础13模8的加法逆元和乘法逆元•对每一个x都有一个对应的y，使得x+y≡0mod8，则y是x的加法逆元。如对2，有6，使得2+6≡0mod8，那么6是2的加法逆元•如果对x，存在y，使得x×y≡1mod8，则y为x的乘法逆元。如3×3≡1mod8，因此3的乘法逆元是3。2011-7-20Ch2-数学基础14快速指数模运算•在非对称密码体制（公钥密码体制）中常常涉及指数模运算，如计算73327mod37•一种方法是利用前面介绍的模运算性质(a×b)modm=((amodm)×(bmodm))modm，将指数模运算可以看做是多次重复乘法，并且在计算中间结果时就取模•例如：计算117mod13，可以按照下面的思路：112=121≡4mod13114=(112)2≡42mod13≡3mod13117=11×112×114≡11×4×3mod13≡132mod13≡2mod132011-7-20Ch2-数学基础15快速求memodn算法一(1)a←e,b←m,c←1,其中a,b,c为三大整数寄存器。(2)如果a=0，则输出结果c即为所求的模n的大整数次幂。(3)如果a是奇数，转第(5)步。(4)a←(a÷2),b←(b×b)modn,转第(3)步。(5)a←(a-1),c←(c×b)modn,转第(2)步。2011-7-20Ch2-数学基础16计算3037mod772011-7-20Ch2-数学基础17费马定理和欧拉定理•费马定理和欧拉定理在公钥密码体制中占非常重要的地位•定理2.13(费马定理Format)若p是素数,且a是正整数，且gcd(a,p)=1，则：ap-1≡1(modp)•定理2.14(欧拉定理)对于任何互素的两个整数a和n，有aφ(n)≡1modn2011-7-20Ch2-数学基础18素性测试•很多密码算法需要随机选择一个或者多个非常大的素数•一般做法是先生成大的随机整数，然后确定该大数是否是素数•目前没有还没有简单有效的方法确定一个大数是否是素数•定理2.15:如果p为大于2的素数，则方程x2≡1(modp)的解只有x=1和x=-1。•定理2.15的逆否命题是：如果方程x2≡1(modp)有一解，那么p不是素数2011-7-20Ch2-数学基础19Miller-Rabin素性概率检验算法•WITNESS(a,n)•(1)将(n-1)表示为二进制形式bkbk-1…b0•(2)d←1•fori=kdownto0do{•x←d；•d←(d×d)modn；•if(d=1&x≠1&x≠n-1)thenreturnTRUE；•ifbi=1thend←(d×a)modn}•ifd≠1thenreturnTRUE；•elsereturnFALSE.2011-7-20Ch2-数学基础20•算法有两个输入，n是待检验的数，a是小于n的整数。如果算法的返回值为TRUE，则n肯定不是素数，如果返回值为FALSE，则n有可能是素数。•for循环后，有d=an-1modn，由费马定理可知，若n为素数，则d为1，因此若d≠1，则n不是素数，所以返回TRUE。•因为n-1≡-1modn，所以x≠1，x≠n-1，表示x2≡1(modp)有不在{-1，1}中的根，因此n不为素数，返回TRUE2011-7-20Ch2-数学基础21离散对数•离散对数是许多公钥算法的基础•本原根这一个重要概念•假设gcd(a,n)=1,如果m是使am≡1modn成立的最小正整数，则称它是a对模n的指数，记为Ordna若Ordna=φ(n)，则称a是模n的本原根(primitiveroot)，也称生成元2011-7-20Ch2-数学基础22求模7和模15的本原根•对于模7而言，满足gcd(a,n)=1的a是{1,2,3,4,5,6}，将它们的指数列表如下a123456Ord7a136362•从上表可以看到，当a是3和5时，Ord7a=φ(7)，因此，3和5是模7的本原根。2011-7-20Ch2-数学基础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,或者2pa，此处p是奇素数a12478111314Ord7a142442422011-7-20Ch2-数学基础24本原根的测试•通常找出一个本原根不是一件容易的问题•如果知道p-1的因子，它就变得容易•测试方法:令q1,q2,…,qn是p-1的素因子，对于所有的q1,q2,…,qn,计算a(p-1)/q(modp)，如果对某个q的某个值其结果为1，那么a不是一个本原根。如果对某个q的所有值其结果都不为1，那么a是一个本原根。2011-7-20Ch2-数学基础25•例2.9假设p=11,检验2和3是否是一个本原根。解：当p=11时,p-1=10，p-1有两个素因子2和5，现测试2是否是一个本原根。2(10-1)/5(mod11)=42(10-1)/2(mod11)=10计算结果没有1，所以2是本根原。测试3是否是本根原3(10-1)/5(mod11)=93(10-1)/2(mod11)=1所以3不是本根原2011-7-20Ch2-数学基础26离散对数•模运算用于指数计算可以表示为axmodn，我们称为模指数运算•模指数运算的逆问题就是找出一个数的离散对数，即求解x，使得ax≡bmodn•定义2.17（离散对数）对于一个整数b和素数n的一个本原根a，可以找到唯一的指数x，使得b≡axmodn，其中0≤x≤n-1，指数x称为b的以a为基数的模n的离散对数2011-7-20Ch2-数学基础27代数基础•有限域在现代密码学中的地位越来越重要•本节先简单介绍群、环和域等概念，然后详细介绍有限域中的运算2011-7-20Ch2-数学基础28群•群G有时记做{G，·}，是定义了一个二元运算的集合，这个二元运算可以表示为·(它具有一般性，可以指加法，乘法或者其他的数学运算)，G中每一个序偶(a，b)通过运算生成G中的元素(a·b)，并满足以下公理：•(Al)封闭性：如果a和b都属于G，则a·b也属于G。•(A2)结合律；对于G中任意元素a,b,c，都有a·(b·c)=(a·b)·c成立•(A3)单位元：G中存在一个元素e，对于G中任意元素a，都有a·e=e·a=a成立•(A4)逆元：对于G中任意元素a，G中都存在一个元素a’，使得式a·a’=a’·a=e成立。•如果一个群的元素个数是有限的，则该群称为有限群。并且群的阶等于群中元素的个数。否则，称该群为无限群。•一个群如果还满足以下条件，则称为交换群（或称Able群）•(A5)交换律:对于G中任意的元素a,b，都有.a·b=b·a成立2011-7-20Ch2-数学基础29环•环R有时记为{R，+，×}，是一个有两个二元运算的集合，这两个二元运算分别称为加法和乘法，且对于R中的任意元素a,b,c，满足以下公理：•(Al-A5)R关于加法是一个交换群；对于此种情况下的加法群，我们用0表示其单位元，-a表示a的逆元。•(M1)乘法的封闭性：如果a和b都属于R，则ab也