非对称密码体制.ppt

第六章

非对称密码体制;6.1概述

6.1.1对称密码体制的缺陷

密钥的平安传递比较困难

n个用户多点通信所需密钥数为n(n-1)/2个

难以提供对抗抵赖功能的支持

6.1.2公钥〔非对称〕密码体制的根本思想

WhitfieldDiffie和MartinHellman在1976年n首先提出：用公开的密钥〔公钥〕加密，用与之对应的不公开的密钥〔私钥〕解密。

公钥密码体制提出的标志性文献──密码学的新方向：

W.Diffieand,NewDirectionsinCryptography,IEEETransactiononInformationTheory,V.IT-22.No.6,Nov1976,PP.644-654;例：卢毅要传送密信给胡旦，用胡旦的公钥对明文进行加密，然后通过公共信道将密文传送给胡旦，胡旦用的与自己的公钥对应的私钥〔只有胡旦自己知道〕解密得到明文。俞敏祺企图知道密信内容，截获到密文，虽然他也知道加密所用的公钥，但他无法通过公钥倒推出相应的私钥，当然就不可能解密出明文。;;6.1.3单向陷门函数

公钥密码体制必须设计一个满足以下条件的函数f：

正向易算性──由消息x和密钥pk容易计算y=fpk(x)

反向不可算性──在不知道密钥sk的情况下，由任意的y倒过来计算x=f-1sk(y)都是不可行的

陷门依赖性──如果给定另一密钥sk，那么f-1(y)是可以计算的，sk与pk配对，相当于陷门。

满足1、2的函数称为单向函数

满足1、2、3的函数被称为带陷门的单向函数;;6.1.4公钥密码体制的特点

无需密钥的平安传递

n个用户仅需n个“公钥-私钥〞对

支持数字签名机制

平安性基于带陷门的单向函数

加密、解密速度比DES、AES等分组密码体制慢

可用于对称密钥的交换;6.2数论背景——欧拉函数与欧拉定理

欧拉数

设正整数n，那么欧拉数φ(n)定义为小于n且与n互素的正整数的个数〔特殊地，φ(1)=1〕。

例如：φ(6)=2(小于6且与6互素的是1和5);φ(7)=6(1,2,3,4,5,6);φ(11)=10(1~10)

素数的欧拉数

对于素数p，其欧拉数φ(p)=p-1(1~p-1)

欧拉数的初等性质

当p、q都是素数时，

φ(pq)=φ(p)φ(q)=(p-1)(q-1)

例：φ(15)=φ(3)φ(5)=2*4=8(1,2,4,7,8,11,13,14);当e与m互素，那么存在正整数d，使得

ed=1(modm)

称d是e关于模m的乘法逆元〔简称“模乘逆元〞或“模逆元〞〕，记作e-1

例如??设m=13，

那么5*8=40=3*13+1=1(mod13)

故5-1=8

欧拉定理

假设m、n互素，那么mφ(n)=1(modn)

例如：设m=13，n=7，

那么136=4826809=689544*7+1=1(mod7);

费马小定理──欧拉定理的推论

设p与m互素，且p是素数，那么

mp-1=1(modp)〔因为φ(p)=p-1〕

根底定理──RSA的理论根底

设n是两个不同的素数p、q之积，x是小于n的非负整数，k是非负整数，那么有：

xkφ(n)+1=x(modn);证明：假设x不是素数p的倍数，那么p与x互素，由费马小定理可得：xp-1=1(modp)，于是由前述各式可得：

xkφ(n)=xkφ(pq)=xkφ(p)φ(q)=xk(p-1)(q-1)

=(xp-1)k(q-1)=1(modp)，故xkφ(n)+1=x(modp)

假设x是p的倍数，那么x=0(modp)，于是也有：

xkφ(n)+1=0=x(modp)

故存在非负整数i，使得xkφ(n)+1=ip+x(modp)，

同理存在非负整数j，使得xkφ(n)+1=jq+x(modq)，

从而可得ip=jq

又由于p、q互素，故

q?i，设整商为t，即i=tq，于是：

xkφ(n)+1=ip+x=tqp+x=tn+x=x(modn)

即最后证得：xkφ(n)+1=x(modn);6.3RSA算法

6.3.1概述

创造人RSA(RonRivest,AdiShamir和

Leonard