《《数据加密技术》PPT课件.ppt》由会员分享，可在线阅读，更多相关《《数据加密技术》PPT课件.ppt（37页珍藏版）》请在三一办公上搜索。
1、密 码 学,公开密钥密码（1）徐邦海鲁东大学计算机学院,一、公开密钥密码体制的基本思想,1、传统密码的缺点：收发双方持有相同密钥，密钥分配困难，网络环境更突出。不能方便地实现数字签名，商业等应用不方便。,Ke Kd,一、公开密钥密码体制的基本思想,2、公开密钥密码的基本思想：将密钥 K一分为二，一个专门加密，一个专门解密：Ke Kd 且由Ke 不能计算出 Kd，于是可将Ke公开，使密钥分配简单。由于Ke Kd且由Ke 不能计算出 Kd，所以 Kd 便成为用户的指纹，于是可方便地实现数字签名。,一、公开密钥密码体制的基本思想,3、公开密钥密码的基本条件：E和 D互逆；基本条件，保密条件 D（E（
2、M）M Ke Kd且由Ke 不能计算出 Kd；安全条件E和 D都高效。实用条件E（D（M）M 保真条件 如果满足 可保密，如果满足 可保真，如果4个条件都满足，可同时保密保真。,二、公开密钥密码的基本工作方式,设 M为明文，C为密文，E为公开密钥密码的加密算法，D为解密算法，Ke为公开的加密钥，Kd为保密的解密钥，每个用户都分配一对密钥，而且将所有用户的公开的加密钥Ke存入共享的密钥库PKDB。,A KeA,B KeB,PKDB,二、公开密钥密码的基本工作方式,1、确保数据秘密性：A B发方：A首先查PKDB，查到B的公开的加密钥KeB。A用KeB 加密M得到密文C：C=E（M，KeB）A发C
3、给B。收方：B接受C。B用自己的KdB解密，得到明文M=D(C，KdB)。,M,二、公开密钥密码的基本工作方式,1、确保数据秘密性：安全性分析：只有B才有KdB，因此只有B才能解密，所以确保了秘密性。任何人都可查PKDB得到A的KeA，所以任何人都可冒充A给B发送数据。不能确保真实性。,二、公开密钥密码的基本工作方式,2、确保数据真实性：A B发方：A首先用自己的KdA对M解密，得到C=D(M，KdA)。A发C给B。收方：B接受C。B查PKDB查到A的公开的加密钥KeA。B用KeA加密C，得到明文M=E（C，KeA）。,M,二、公开密钥密码的基本工作方式,2、确保数据秘密性：安全性分析：只有A
4、才有KdA，因此只有A才能解密产生C，所以确保了真实性。任何人都可查PKDB得到A的KeA，所以任何人都可加密得到明文。不能确保秘密性。,二、公开密钥密码的基本工作方式,3、同时确保数据秘密性和真实性：A B 发方：A首先用自己的KdA对M解密，得到S：S=D(M，KdA)查PKDB，查到B的公开的加密钥KeB。用KeB 加密S得到C：C=E（S，KeB）A发C给B。,M,二、公开密钥密码的基本工作方式,3、同时确保数据秘密性和真实性：收方：B接受C。B用自己的KdB解密C，得到S：S=D（C，KdB）B查PKDB查到A的公开的加密钥KeA。B用A的公开的加密钥KeA 加密S，得到M：M=E（
5、S，KeA）,二、公开密钥密码的基本工作方式,3、同时确保数据秘密性和真实性：安全性分析：只有A才有KdA，因此只有A才能解密产生S，所以确保了真实性。只有B才有KdB，因此只有B才能获得明文，所以确保了秘密性。,三、RSA公开密钥密码,1978年美国麻省理工学院的三名密码学者R.L.Rivest,A.Shamir和L.Adleman提出了一种基于大合数因子分解困难性的公开密钥密码，简称为RSA密码。RSA密码被誉为是一种风格幽雅的公开密钥密码。既可用于加密，又可用于数字签名，安全、易懂。RSA密码已成为目前应用最广泛的公开密钥密码。,三、RSA公开密钥密码,1、加解密算法随机地选择两个大素数
6、 p和 q，而且保密；计算n=pq，将 n公开；计算(n)=(p-1)(q-1)，对(n)保密；,三、RSA公开密钥密码,随机地选取一个正整数e，1e(n)且（e，(n)）=1，将 e公开；根据 ed1 mod(n)，求出d，并对d保密；加密运算：CM e mod n解密运算：MC d mod n,三、RSA公开密钥密码,2、算法论证 E和D的可逆性要证明：D(E(M)=M MCd(Me)dMed mod n因为ed1 mod(n)，这说明edt(n)+1,其中t为某整数。所以，Med Mt(n)+1 mod n。因此要证明 Med M mod n，只需证明 M t(n)+1 M mod n。
7、,三、RSA公开密钥密码,2、算法论证 E和D的可逆性在（M，n）1的情况下，根据数论(Euler定理)，M t(n)1 mod n，于是有，M t(n)+1 M mod n。,三、RSA公开密钥密码,2、算法论证 E和D的可逆性在（M，n）1的情况下，分两种情况：第一种情况：M1,2,3,n-1 因为n=pq，p和q为素数，M1,2,3,n-1，且（M，n）1。这说明M必含p或q之一为其因子，而且不能同时包含两者，否则将有Mn，与M1,2,3,n-1矛盾。,三、RSA公开密钥密码,2、算法论证 E和D的可逆性不妨设Map。又因q为素数，且M不包含q，故有（M，q）1，于是有，M(q)1 mo
8、d q。进一步有，M t(p-1)(q)1 mod q。因为q是素数，(q)（q-1），所以t(p-1)(q)t(n)，所以有 M t(n)1 mod q。,三、RSA公开密钥密码,2、算法论证 E和D的可逆性于是，M t(n)bq+1，其中b为某整数。两边同乘M，M t(n)+1 bqM+M。因为Map，故 M t(n)+1 bqap+M=abn+M。取模n得，M(n)+1 M mod n。,三、RSA公开密钥密码,2、算法论证 E和D的可逆性在（M，n）1的情况下，分两种情况：第二种情况：M0当M0时，直接验证，可知命题成立。,三、RSA公开密钥密码,2、算法论证加密和解密运算的可交换性
9、D(E(M)=(Me)d=Med=(Md)e=E(D(M)mod n所以，RSA密码可同时确保数据的秘密性和数据的真实性。加解密算法的有效性 RSA密码的加解密运算是模幂运算，有比较有效的算法。,三、RSA公开密钥密码,2、算法论证在计算上由公开密钥不能求出解密钥 小合数的因子分解是容易的，然而大合数的因子分解却是十分困难的。关于大合数的因子分解的时间复杂度下限目前尚没有一般的结果。根据这一结论，只要合数足够大，进行因子分解是相当困难的。,三、RSA公开密钥密码,2、算法论证在计算上由公开密钥不能求出解密钥假设截获密文C，从中求出明文M。他知道 MCd mod n，因为n是公开的，要从C中求出
10、明文M，必须先求出d，而d是保密的。但他知道，ed1 mod(n)，e是公开的，要从中求出d，必须先求出(n)，而(n)是保密的。,三、RSA公开密钥密码,2、算法论证在计算上由公开密钥不能求出解密钥但他又知道，(n)=(p-1)(q-1)，要从中求出(n)，必须先求出p和q，而p和q是保密的。但他知道，n=pq，要从n求出p和q，只有对n进行因子分解。而当n足够大时，这是很困难的。,三、RSA公开密钥密码,2、算法论证在计算上由公开密钥不能求出解密钥 只要能对n进行因子分解，便可攻破RSA密码。由此可以得出，破译RSA密码的困难性对n因子分解的困难性。目前尚不能证明两者是否能确切相等，因为不
11、能确知除了对n进行因子分解的方法外，是否还有别的更简捷的破译方法。目前只有Rabin密码具有：破译Rabin密码的困难性=对n因子分解的困难性。,四、RSA密码的实现,1、参数选择为了确保RSA密码的安全，必须认真选择密码参数：p和q要足够大；一般应用：p和q应 512 b 重要应用：p和q应 1024 b p和q应为强素数 文献指出，只要(p-1)、(p+1)、(q-1)、(q+1)四个数之一只有小的素因子，n就容易分解。p和q的差要大；,四、RSA密码的实现,1、参数选择（p-1）和（q-1）的最大公因子要小。如果（p-1）和（q-1）的最大公因子太大，则易受迭代加密攻击。e的选择 随机且
12、含1多就安全，但加密速度慢。于是，有的学者建议取e216+165537 d的选择 d不能太小，要足够大 不要许多用户共用一个模 n；易受共模攻击,四、RSA密码的实现,2、大素数的产生概率产生 目前最常用的概率性算法是Miller检验算法。Miller检验算法已经成为美国的国家标准。确定性产生确定性测试 确定性构造,四、RSA密码的实现,3、大素数的运算快速乘方算法反复平方乘算法：设e的二进制表示为 eek-1 2k-1+ek-2 2k-2+.,+e1 21+e0则 Me=(Mek-1)2 Mek-2)2Me1)2 Me0 mod n设e为k位二进制数，w(e)为e的二进制系数中为1的个数，则
13、最多只需要计算w(e)-1次平方和w(e)次数的模乘。从而大大简化了计算。,四、RSA密码的实现,3、大素数的运算快速模乘算法反复平方乘算法解决了快速乘方取模的问题，仍未解决快速模乘的问题；Montgomery算法是一种快速模乘的好算法；将以上两种算法结合成为实现RSA密码的有效方法。硬件协处理器是提高运算效率的有效方法。,四、RSA密码的实现,3、大素数的运算Montgomery算法的思路：要计算 Y=AB mod n,因为n很大，取模运算困难，采取一个小的模 R，回避大模的计算。利用空间换时间，多用存储空间换取快速。缺点：不能直接计算出 Y=AB mod n，只能计算出中间值 ABR-1
14、mod n，因此还需要预处理和调整运算。一次性计算Y=AB mod n并不划算。适合：RSA等密码中多次的模乘计算。,证明RSA密码加解密算法的可逆性 证明RSA密码加解密算法的可交换性 说明对于RSA密码从公开加密钥不能求出保密的解密钥令p=3,q=11,d=7,m=5,手算密文C。设RSA密码的 e=31,n=35,C=10,手算明文M。,习 题,设A，B为正整数，D=(A,B)。试证明：(AB)=D(A)(B)/(D)RSA密码的快速运算分析反复平方乘算法的效率说明 Montgomery算法为什么效率高？它适合哪些情况下应用？编程实现RSA密码的加解密运算。在RSA中使用e=3作为加密指
15、数有和优缺点？使用d=3作解密指数的做法好吗？为什么？,习 题,证明RSA密码加解密算法的可逆性 证明RSA密码加解密算法的可交换性 说明对于RSA密码从公开加密钥不能求出保密的解密钥令p=3,q=11,d=7,m=5,手算密文C。设RSA密码的 e=31,n=35,C=10,手算明文M。,习 题,设A，B为正整数，D=(A,B)。试证明：(AB)=D(A)(B)/(D)RSA密码的快速运算分析反复平方乘算法的效率说明 Montgomery算法为什么效率高？它适合哪些情况下应用？编程实现RSA密码的加解密运算。在RSA中使用e=3作为加密指数有和优缺点？使用d=3作解密指数的做法好吗？为什么？,习 题,谢 谢！,
