次课-密码学中常用数学知识.ppt

1、公钥密码,密码学中常用的数学知识 公钥密码体制的基本概念 RSA算法,4.1.1 群、环、域,群的定义: 一些数字组成的集合 一个二元运算，运算结果属于此集合（封闭性） 服从结合律。有单位元，逆元 。 如果是可交换的，则成为Abel群,*为乘法时，称为乘法群 逆元（a-1） *为加法时，称为加法群 逆元（-a）,环的定义: Abel 群，及一个乘法运算： 满足结合律与加法的分配律 如果加法满足交换律, 则称交换环 例：整数 mod N （for any N ）,域的定义： 是Abel加群 环 是Abel 乘群 例： 整数 mod P （ P 为素数）,Galois 域： 如果 n是素数 p ，

2、则模运算modulo p 形成 Galois Field modulo p 记为： GF(p),4.1.2 素数和互素数,因子： 对整数 b!=0 及 a , 如果存在整数 m 使得 a=mb,称 b 整除 a, 也称b是a的因子。 记作 b|a 例 1,2,3,4,6,8,12,24 整除 24,素数： 素数: 只有因子 1 和自身 1 是一个平凡素数 例 2,3,5,7 是素数, 4,6,8,9,10 不是,200以内的素数： 2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97 101 103 107

3、 109 113 127 131 137 139 149 151 157 163 167 173 179 181 191 193 197 199,素数分解： 把整数n写成素数的乘积 分解整数要比乘法困难 整数 n的素数分解是把它写素数的乘积 eg. 91 = 7 13 ; 3600 = 24 32 52,互素数： 整数 a, b 互素是指 它们没有除1之外的其它因子。 8 与15 互素 8的因子1,2,4,8 15的因子 1,3,5,15 1 是唯一的公因子 记为：gcd(8,15)=1,4.1.3 模运算,设n是一正整数,a是整数,若 a=qn+r, 0rn, 则a mod n=r 若(a

4、mod n)=(b mod n),称为a,b模n同余， 记为ab mod n 称与a模n同余的数的全体为a的同余类，记为a，a称为这个同余类的代表元素。,-21 -20 -19 -18 -17 -16 15 -14 -13 -12 -11 -10 -9 -8 -7 -6 -5 -4 -3 -2 -1 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34,同余的性质： 若n|(a-b)，则ab mod n (a mod n) (b mod n),则ab mod

5、n ab mod n，则ba mod n ab mod n， bc mod n，则ac mod n,求余运算a mod n将a映射到集合0,1,n-1,求余运算称为模运算。,模运算的性质 (a mod n)+(b mod n) mod n=(a+b) mod n (a mod n)-(b mod n) mod n=(a-b) mod n (a mod n)(b mod n) mod n=(ab) mod n,定理:设aZn,gcd(a,n)=1,则a在Zn有逆元。 证明思路： 用反证法证明a和Zn中任何两个不同的数相乘结果都不相同 从1得出aZn=Zn,因此存在xZn,使ax=1 mod n

6、设a为素数，Zp中每一个非零元素都与a互素，因此有乘法逆元，有乘法可约律 (ab)=(ac) mod n, b=c mod n,定义Zn为小于n的所有非负整数集合,Zn=0,1,2,n-1,4.1.4 费尔玛定理和欧拉定理,费尔玛定理： 若p是素数，a是正整数且gcd(a,p)=1，则ap-11 mod p 证明：,当gcd(a,p)=1,则aZp=Zp 。,又因为a00modp,所以a(Zp-0)=Zp-0,即：a mod p,2a mod p,(n-1)a mod p =1,p-1,(a mod p) (2a mod p) (n-1)a mod p=(p-1)!ap-1 mod p,因此：

7、(p-1)! ap-1 mod p =(p-1)!modp,(p-1)!与p互素，所以乘法可约律，ap-1=1 mod p,欧拉函数 设n为一正整数，小于n且与n互素的正整数的个数称为n的欧拉函数，记为(n),欧拉定理 若a和n互素,则a(n)=1 mod n,例：(6)=2, (7)=6, (8)=4 显然，若n是素数， (n)=n-1,定理： 若n是两个素数p和q的乘积，则(n) (p) (q)=(p-1)(q-1),例：21=37 ，因此(21)= (3) (7)=26=12,4.1.5 素性检验,爱拉托斯散(Eratosthenes)筛法 定理： 设n是正整数，若对所有满足p 的素数p

8、，都有 p | n，那么n一定是素数。,对给定的数检验其是否为素数,若要找出不大于n的所有素数：,先将2到n之间的整数列出，从中删除小于等于 的所有素数的倍数，余下的整数即是所要求的素数。,此方法在n很大时，实际上是不可行的。,Miller-Rabin素性概率检测法,引理： 如果p为大于2的素数，则方程x21 mod p的解只有和x1和x-1,证明: x21 mod p x2 -1 0 mod p(x+1)(x-1)0 mod p 所以：p|(x+1)或p|(x-1)或p|(x+1)且p|(x-1) 若p|(x+1)且p|(x-1)，则存在k,j，使x+1=kp, x-1=jp 可得：2=(k

9、-j)p, 这是不可能的。 所以： p|(x+1)或p|(x-1) 设： p|(x+1)，则x+1=kp x=-1modp 设： p|(x-1)，则x-1+1=kp x=1modp,引理的逆命题： 若方程x21 mod p，有唯一解x不为+1或-1，p不是素数。,Miller-Rabin素性概率检测法 n为待检测数，a为小于n的整数，将n-1表示为二进制形式bkbk-1b0,d赋初值为1，算法核心如下： for i=k downto 0 do xd; d(dd) mod n; if d=1 and (x1)and(xn-1) then return False if bi=1 the d(da

10、) mod n if d 1 then return False; return True 若返回False,n不是素数,若返回True,有可能是素数。,For循环结束,有dan-1 mod n。由费尔玛定理,若n为素数,d为1。所以d1，则d不是素数。,n-1-1 mod n,所以x 1和x n-1指x21 mod n 有非1的根,n不是素数。,4.1.6 欧几里得算法,2. 两个正整数互素，可以求一个数关于另一个数的乘法逆元 性质: 对任意非负整数a和正整数b, 有 gcd(a,b)=gcd(b,a mod b) 证明：,1. 求两个正整数的最大公因子,a=kb+rr mod b a mo

11、d b=a-kb,设d是a，b的公因子，即d|a , d|b, 所以d|kb.,由d|a和d|kb，得d|(a mod b)， 故d是b和a mod b的公因子。,a,b以及b,a mod b公因子集合相同，故最大公因子也相同。,gcd(55,22)=gcd(22,11)=gcd(11,0)=11 gcd(11,10)=gcd(10,1)=1,Euclid(f,d) fd 1. Xf;Yd; 2. If Y=0 then return X=gcd(f,d) 3. R=X mod Y 4. X=Y; 5. Y=R 6. Goto 2,假定输入是两个正整数,Euclid算法：,gcd(55,22)

12、=gcd(22,11)=gcd(11,0)=11 gcd(11,10)=gcd(10,1)=1,欧几里德算法-求乘法逆元 若gcd(a,b)=1, b在模a下有乘法逆元(设ba)。 即存在xa,bx1 mod a 思路：求gcd(a,b)，当gcd(a,b)=1时，则返回b的逆元。,整除中的一个论断： 若gcd(a,b)=d，则存在m,n，使得d=ma+nb。 那么当gcd(a,b)=1时，有ma+nb=1， 即m是a模b的逆元，n是b模a的逆元。,Extended Euclid(f,d) (fd) 1.（X1 X2 X3)(1,0,f);(Y1Y2 Y3)(0,1,d); 2. If Y3=

13、0, then return X3=gcd(f,d);停止，没有逆元; 3. If Y3=1, then return X3=gcd(f,d);Y2=d-1 mod f; 4. Q=X3 div Y3（整数除）; 5. (T1 T2 T3)(X1-QY1,X2-QY2,X3-QY3); 6. (X1 X2 X3)(Y1Y2 Y3); 7. (Y1Y2 Y3)(T1 T2 T3); 8.Goto 2,扩展欧几里德算法：,求d模f的逆元,例：求解 11d (mod51) = 1的步骤。 即求11-1mod51=？,Extended Euclid(f,d) (fd) 1.（X1 X2 X3)(1,0,f); (Y1Y2 Y3)(0,1,d); 2. If Y3=0, then return X3=gcd(f,d); 停止，没有逆元; 3. If Y3=1, then return X3=gcd(f,d);Y2=d-1 mod f; 4. Q=X3 div Y3（整数除）; 5. (T1 T2 T3) (X1-QY1,X2-QY2,X3-QY3); 6. (X1 X2 X3)(Y1Y2 Y3); 7.