密码学6-非对称密码体制.ppt

第六章 非对称密码体制
《信息平安技术》
概述
对称密码体制的缺陷
密钥的平安传递比较困难
n个用户多点通信所需密钥数为n(n-1)/2个
难以供应对主动攻击的抗击
公钥（非对称）密码体制的基本= x k(p-1)(q-1)
=( xp-1) k(q-1) =1 (mod p) ，故x kφ(n) +1=x (mod p)
若x是p的倍数，则 x=0 (mod p) ，于是也有：
x kφ(n) +1=0=x (mod p)
故存在非负整数i，使得x kφ(n) + 1=ip+x (mod p)，
同理存在非负整数j ，使得x kφ(n) +1=jq+x (mod q)，
从而可得ip=jq
又由于p、q互素，故
qi，设整商为t，即i=tq，于是：
x kφ(n) +1=ip+x= tqp+x=tn+x=x (mod n)
即最终证得：x kφ(n) +1=x (mod n)
RSA算法
概述
独创人RSA(Ron Rivest, AdiShamir 和 Leonard Adleman)
1977年在麻省理工学院开发
1978年发表
是最典型的公钥密码体制
算法基于单向陷门函数的原理
以模幂运算为基本运算
平安性基于大数因子分解的困难性（将一个充分大的正整数分解成两个素数之积几乎是不行能的）
数学基础是著名的欧拉(Euler)数论
RSA密码体制的创建
选择两个充分大的不同的素数p和q
计算积n=pq及其欧拉数φ(n)=(p-1)(q-1)
选择一个介于1到φ(n)之间且与φ(n)互素的正整数e
即1<e<φ(n)且GCD(e,φ(n))=1
求出d=e-1 (mod φ(n) )
即e d=1 (mod φ(n) )
对明文空间0～n-1中的数x，
例：P115【例6-2】
以<e,n>为公钥加密： y=E(x)=xe (mod n)
以< d,n> 为私钥解密：x=D(y)=yd (mod n)
解密还原性的证明：
由于ed=1 (mod φ(n))，故存在非负整数k，使得：
ed =kφ(n)+1，于是由基础定理可得：
D(E(x))=(xe)d =xed =x kφ(n) +1 =x (mod n)
注1：p,q从理论上讲也是私钥的组成部分，但因在解密过程中不用，故在确定e,d之后应予以销毁
注2: 加密前明文M需表示为若干0～n-1的代码Mi
实例：对英文字母从1~26编码，空格为0，对明文双字母编码，如“its all greek to me ”编码为：0920、1900、0112、1200、0718、 0505、1100、2015、0013、0500
设p=47、q=59，则n=2773， φ(2773)=46*58=2668
因17*157=2669=1 (mod 2668)，故取公钥为<17,2773>，私钥为< 157,2773>
对明文组M=0920加密，C=92017
=0948 (mod 2773)，190017
=2342 (mod 2773)，其余各组的密文为： 1084、1444、2663、2390、0778、0774、0219、1655
对密文组C=948解密，
M=948157
=920 (mod 2773) 详见：
计算方法及其程序实现
如何计算模逆元
要在已知e、m的状况下，求d，使得 e*d=1(mod m)
也即找整数k，使得e*d+mk=1
这相当于求解d、k都是未知数的二元一次不定方程 e*d+mk=1的最小整数解
扩展Euclid算法
输入：正整数a、b
输出：GCD(a,b)及满足ax+by=GCD(a,b)的整数x、y
例如：设a=21、b=15，则GCD(a,b)=3，x=-2、y=3
算法步骤描述：
置x1=1，x2=0，y1=0，y2=1
计算q=a / b，r=a % b
若r=0，则GCD(a,b)=b，x=x2，y=y2，算法结束；否则做下步
依次令a=b，b=r，t=x2，x2=x1-qx2，x1=t，
t=y2，y2=y1-qy2，y1=t，然后转2)
附：
乘法逆元的计算
输入：正整数e、m
输出：GCD(e,m)及满足ed=GCD(e,m) (mod m)的整数d
当GCD(e,m)=1 （即e、m互素），
则d=e-1 (mod m)
例如：设e=7、m=17，则GCD(7,17)=1，d=5=7-1；因为7*5=35=17*2+1=1 (m