《现代密码学第6章：公钥密码学》由会员分享，可在线阅读，更多相关《现代密码学第6章：公钥密码学（233页珍藏版）》请在金锄头文库上搜索。
1、1,公钥密码,现代密码学第6章,2,本章主要内容,1、数论简介 2、公钥密码体制的基本概念 3、RSA算法 4、背包密码体制 5、Rabin密码体制 6、椭圆曲线密码体制 习题,3,数论是密码学特别是公钥密码学的基本工具，本章首先介绍密码学中常用的一些数论知识，然后介绍公钥密码体制的基本概念和几种重要算法。,1. 数论简介,4,数论介绍,数论概念: 研究“离散数字集合” 运算是“+” ,“” 例: 整数: 5 + 9 = 14; 5 3 = 5 + 5 + 5 = 15 多项式: x2+1 + x = x2+x+1; x x2+1 = x3+x,5,运算概念,运算: 模数运算 模多项式运算 进
2、一步运算: 指数运算,逆运算 理解公钥算法的基础,6,整除,对整数 b!=0 及 a , 如果存在整数 m 使得 a=mb,称 b 整除 a, 也称b是a的因子 记作 b|a 例 1,2,3,4,6,8,12,24 整除 24,7,1. 因子 设a，b(b0)是两个整数，如果存在另一整数m，使得a=mb，则称b整除a，记为b|a，且称b是a的因子。,1.1 素数和互素数,8,整数具有以下性质： a|1，那么a=1。 a|b且b|a，则a=b。 对任一b (b0)，b|0。 b|g，b|h，则对任意整数m、n有b|(mg+nh)。,1.1 素数和互素数,9,这里只给出的证明，其他3个性质的证明都
3、很简单。 性质的证明： 由b|g，b|h知，存在整数g1、h1，使得g=bg1,h=bh1所以mg+nh=mbg1+nbh1 =b(mg1+nh1),因此b|(mg+nh)。,1.1 素数和互素数,10,2. 素数 称整数p(p1)是素数，如果p的因子只有1，p。 任一整数a(a1)都能惟一地分解为以下形式： 其中p1p2pt是素数，ai0(i=1,t)。例如91=711，11011=711213,1.1 素数和互素数,11,这一性质称为整数分解的惟一性，也可如下陈述：设P是所有素数集合，则任意整数a (a1)都能惟一地写成以下形式： 其中ap0,等号右边的乘积项取所有的素数，然而大多指数项a
4、p为0。相应地，任一正整数也可由非0指数列表表示。例如： 11011可表示为a7=1,a11=2,a13=1。 两数相乘等价于对应的指数相加，即由k=mn 可得：对每一素数p,kp=mp+np。而由a|b可得： 对每一素数p,apbp。这是因为pk只能被pj(jk)整除。,1.1 素数和互素数,12,3. 互素数 称c是两个整数a、b的最大公因子，如果 c是a的因子也是b 的因子，即c是a、b的公因子。 a和b的任一公因子，也是c的因子。 表示为c=gcd(a, b)。,1.1 素数和互素数,13,由于要求最大公因子为正，所以gcd(a,b)=gcd(a,-b)=gcd(-a,b)=gcd(-
5、a,-b)。一般gcd(a,b)=gcd(|a|,|b|)。由任一非0整数能整除0，可得gcd(a,0)=|a|。如果将a，b都表示为素数的乘积，则gcd(a, b)极易确定。 例如：300=223152； 18=2132 gcd(18,300)=213150=6 一般由c=gcd(a,b)可得： 对每一素数p，cp=min(ap,bp)。,1.1 素数和互素数,14,由于确定大数的素因子不很容易，所以这种方法不能直接用于求两个大数的最大公因子，如何求两个大数的最大公因子在下面介绍。 如果gcd(a,b)=1，则称a和b互素。,1.1 素数和互素数,15,整数互素,整数 a, b 互素是指 它
6、们没有除1之外的其它因子 8 与15 互素 8的因子1,2,4,8 15的因子 1,3,5,15 1 是唯一的公因子,16,素数与不可约多项式,素数: 只有因子 1 和自身 1 是一个平凡素数 例 2,3,5,7 是素数, 4,6,8,9,10 不是 素多项式或不可约多项式irreducible: 不可写成其他因式的乘积 x2+x = x x+1 是非不可约多项式; x3+x+1 是不可约多项式,17,一些素数,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 10
7、7 109 113 127 131 137 139 149 151 157 163 167 173 179 181 191 193 197 199,18,素数分解,把整数n写成素数的成绩 分解整数要比乘法困难 整数 n的素数分解是把它写素数的乘积 eg. 91 = 7 13 ; 3600 = 24 32 52,19,设n是一正整数，a是整数，如果用n除a，得商为q，余数为r，则 a=qn+r,0rn, 其中x为小于或等于x的最大整数。 用a mod n表示余数r，则 。 如果(a mod n)=(b mod n)，则称两整数a和b模n同余，记为ab mod n。称与a模n同余的数的全体为a的同
8、余类，记为a，称a为这个同余类的表示元素。 注意： 如果a0(mod n)，则n|a。,1.2 模运算,20,同余有以下性质： 若n|(a-b)，则ab mod n。 (a mod n)(b mod n)，则ab mod n。 ab mod n,则ba mod n。 ab mod n,bc mod n,则ac mod n。 从以上性质易知，同余类中的每一元素都可作为这个同余类的表示元素。,1.2 模运算,21,求余数运算（简称求余运算）a mod n将整数a映射到集合0,1, ,n-1，称求余运算在这个集合上的算术运算为模运算，模运算有以下性质： (a mod n)+(b mod n) mod
9、 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。,1.2 模运算,22,性质的证明： 设（a mod n）=ra，(b mod n)=rb，则存在整数j、k使得a=jn+ra，b=kn+rb。 因此 (a+b) mod n=(j+k)n+ra+rb mod n=(ra+rb) mod n = (a mod n)+(b mod n) mod n （证毕） 性质、的证明类似。,1.2 模运算,23,例： 设Z8=0,1,7，考虑Z8上的模加法和模乘法，结果如表4.1
10、所示。 从加法结果可见，对每一x，都有一y，使得x+y0 mod 8。如对2，有6，使得2+60 mod 8，称y为x的负数，也称为加法逆元。 对x，若有y，使得xy1 mod 8，如331 mod 8，则称y为x的倒数，也称为乘法逆元。本例可见并非每一x都有乘法逆元。,1.2 模运算,24,一般地，定义Zn为小于n的所有非负整数集合，即Zn=0,1, ,n-1，称Zn为模n的同余类集合。其上的模运算有以下性质： 交换律 (w+x) mod n=(x+w) mod n (wx) mod n=(xw) mod n 结合律 (w+x)+y mod n=w+(x+y) mod n (wx)y mod
11、 n=w(xy) mod n,1.2 模运算,25, 分配律 w(x+y) mod n=wx+wy mod n 单位元 (0+w) mod n=w mod n (1w) mod n=w mod n 加法逆元 对wZn，存在zZn，使得w+z0 mod n，记z=-w。,1.2 模运算,26,此外还有以下性质： 如果(a+b)(a+c) mod n，则bc mod n，称为加法的可约律。 该性质可由(a+b)(a+c) mod n的两边同加上a的加法逆元得到。,1.2 模运算,27,然而类似性质对乘法却不一定成立。例如63672 mod 8，但37 mod 8。原因是6乘以0到7得到的8个数仅为
12、Z8的一部分，见上例。 即如果将对Z8作6的乘法6Z8（即用6乘Z8中每一数）看作Z8到Z8的映射的话，Z8中至少有两个数映射到同一数，因此该映射为多到一的，所以对6来说，没有惟一的乘法逆元。但对5来说，551 mod 8，因此5有乘法逆元5。 仔细观察可见，与8互素的几个数1，3，5，7都有乘法逆元。 这一结论可推广到任一Zn。,1.2 模运算,28,定理4.1 设aZn，gcd(a, n)=1，则a在Zn中有乘法逆元。 证明： 首先证明a与Zn中任意两个不相同的数b、c（不妨设cb）相乘，其结果必然不同。否则设abac mod n，则存在两个整数k1,k2，使得ab=k1n+r，ac=k2
13、n+r，可得a(b-c)=(k1-k2)n，所以a是(k1-k2)n的一个因子。,1.2 模运算,29,又由gcd(a，n)=1，得a是k1-k2的一个因子，设k1-k2=k3a，所以a(b-c)=k3an，即b-c=k3n，与0cbn矛盾。 所以|aZn|=|Zn|，又知aZnZn，所以aZn=Zn。因此对1Zn，存在xZn，使得ax1 mod n，即x是a的乘法逆元。记为x=a-1。 （证毕）,1.2 模运算,30,设p为一素数，则Zp中每一非0元素都与p互素，因此有乘法逆元。类似于加法可约律，可有以下乘法可约律： 如果(ab)(ac) mod n且a有乘法逆元，那么对(ab)(ac) m
14、od n两边同乘以a-1，即得bc mod n,1.2 模运算,31,模算式,除法取余运算 同余( congruence) for a = b mod n 如果a,b 除以n,余数相同 eg. 100 = 34 mod 11 b 叫做a模n的剩余 通常 0=b=n-1 eg. -12mod7 = -5mod7 = 2mod7 = 9mod7 可以进行整数运算,32,模运算举例,-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 1
15、5 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34,33,模算术运算,加法 a+b mod n 减法 a-b mod n = a+(-b) mod n,34,乘法除法,乘法 a.b mod n 重复加法 除法 a/b mod n 乘以b的逆元: a/b = a.b-1 mod n 如果n是素数, b-1 mod n 存在 s.t b.b-1 = 1 mod n 例. 2.3=1 mod 5 hence 4/2=4.3=2 mod 5,35,模递归运算,模递归运算是“模除求余” 例.r = a mod n 计算 a = d.n +
16、 r 33 mod 7 = 4.7 + 5; 得数是 5 通常, r 取正数 例 -18 mod 7 = -3.7 + 3; 答案是3 a+/-b mod n = a mod n +/- b mod n mod n,36,费尔玛 (Fermat) 定理和欧拉 (Euler) 定理在公钥密码体制中起着重要作用。,1.3 费尔玛定理和欧拉定理,37,1. 费尔玛定理 定理4.2 (Fermat)若p是素数，a是正整数且gcd(a, p)=1，则ap-11 mod p。 证明：由4.1.2的讨论知当gcd(a, p)=1时,aZp=Zp，其中aZp表示a与Zp中每一元素做模p乘法。又知a00 mod p，所以aZp-0=Zp-0，a(Zp-0)=Zp-0。即a mod p,2a mod p,(p-1)a mod p =1,2,p-1,费尔玛定理,38,所以 a2a(p-1)a(a mod p) (2a mod p)(p-1)a mod p)
