第13章-公钥密码实现程序2.ppt

南京邮电大学计算机学院计算机硬件基础教学中心,第13章公钥密码实现程序,网络编程技术TechnologyofNetworkProgramming,内容纲要,一般的数据加密模型常规密钥密码体制公开密钥密码体制,内容纲要,一般的数据加密模型常规密钥密码体制公开密钥密码体制,一般的数据加密模型,E加密算法,D解密算法,加密密钥K,解密密钥K,明文X,明文X,密文Y=EK(X),截取者,截获,篡改,密钥源,安全信道,密码编码学(cryptography)是密码体制的设计学，而密码分析学(cryptanalysis)则是在未知密钥的情况下从密文推演出明文或密钥的技术。密码编码学与密码分析学合起来即为密码学(cryptology)。,一般的数据加密模型,密码学一些重要概念,如果不论截取者获得了多少密文，但在密文中都没有足够的信息来惟一地确定出对应的明文，则这一密码体制称为无条件安全的，或称为理论上是不可破的。如果密码体制中的密码不能被可使用的计算资源破译，则这一密码体制称为在计算上是安全的。,一般的数据加密模型,密码学一些重要概念,内容纲要,一般的数据加密模型常规密钥密码体制公开密钥密码体制,所谓常规密钥密码体制，即加密密钥与解密密钥是相同的密码体制。这种加密系统又称为对称密钥系统。我们先介绍在常规密钥密码体制中的两种最基本的密码。,1、常规密钥密码体制,常规密钥密码体制概念,数据保密技术,1、常规密钥密码体制,替代密码,数据保密技术,替代密码(substitutioncipher)的原理可用一个例子来说明。(密钥是3),abcdefghijklmnopqrstuvwxyzDEFGHIJKLMNOPQRSTUVWXYZABC,caesarcipher,FDHVDUFLSKHU,明文密文,明文c变成了密文F,1、常规密钥密码体制,数据保密技术,替代密码,替代密码(substitutioncipher)的原理可用一个例子来说明。（密钥是3）,abcdefghijklmnopqrstuvwxyzDEFGHIJKLMNOPQRSTUVWXYZABC,caesarcipher,FDHVDUFLSKHU,明文密文,明文a变成了密文D,1、常规密钥密码体制,数据保密技术,替代密码,替代密码(substitutioncipher)的原理可用一个例子来说明。（密钥是3）,abcdefghijklmnopqrstuvwxyzDEFGHIJKLMNOPQRSTUVWXYZABC,caesarcipher,FDHVDUFLSKHU,明文密文,明文e变成了密文H,数据保密技术,序列码体制是将明文X看成是连续的比特流(或字符流)x1x2，并且用密钥序列Kk1k2中的第i个元素ki对明文中的xi进行加密，即,1、常规密钥密码体制,序列密码体制,EK(X)=Ek1(x1)Ek2(x2),1、常规密钥密码体制,序列密码体制,数据保密技术,密钥序列产生器,种子I0,发端,ki,密钥序列产生器,种子I0,收端,ki,密文序列,明文序列,明文序列,xi,xi,yi,yi,在开始工作时种子I0对密钥序列产生器进行初始化。按照模2进行运算，得出：,yi=Eki(xi)=xiki,1、常规密钥密码体制,序列密码体制,数据保密技术,密钥序列产生器,种子I0,发端,ki,密钥序列产生器,种子I0,收端,ki,密文序列,明文序列,明文序列,xi,xi,yi,yi,在收端，对yi的解密算法为：,序列密码又称为密钥流密码。,Dki(yi)=xiki=(xiki)ki=xi,序列密码体制的保密性取决于密钥的随机性。如果密钥是真正的随机数，则这种体制就是理论上不可破的。这称为一次一密乱码本体制。密码学家试图模仿这种一次一密乱码本体制。目前常使用伪随机序列作为密钥序列。关键是序列周期要足够长,且序列有很好的随机性。,1、常规密钥密码体制,序列密码体制的保密性,数据保密技术,它将明文划分成固定的n比特的数据组，然后以组为单位，在密钥的控制下进行一系列的线性或非线性的变化而得到密文分组密码。分组密码算法的一个重要特点就是：当给定一个密钥后，若明文分组相同，那么所变换出密文分组也相同。分组密码的一个重要优点是不需要同步,1、常规密钥密码体制,分组密码,数据保密技术,1、常规密钥密码体制,数据保密技术,输入,输出,加密算法,密钥,明文,输入,输出,解密算法,密钥,明文,nbit,nbit,nbit,nbit,密文,密文,分组密码体制,数据加密标准DES属于常规密钥密码体制，是一种分组密码。在加密前，先对整个明文进行分组。每一个组长为64bit。然后对每一个64bit二进制数据进行加密处理，产生一组64bit密文数据。最后将各组密文串接起来，即得出整个的密文。使用的密钥为64bit（实际密钥长度为56bit，有8bit用于奇偶校验)。,1、常规密钥密码体制,数据保密技术,数据加密标准DES,DES实际上就是一种单字符替代，而这种字符的长度是64bit。也就是说，对于DES算法，相同的明文就产生相同的密文。这对DES的安全性来说是不利的。为了提高DES的安全性，可采用加密分组链接的方法。,1、常规密钥密码体制,DES的明显缺点,数据保密技术,1、常规密钥密码体制,加密分组的链接,数据保密技术,X0,Y0,X1,Y1,X2,Y2,X3,Y3,X0,Y0,X1,Y1,X2,Y2,X3,Y3,初始向量,初始向量,密钥,密钥,明文,明文,密文,密文,加密,解密,E,E,E,E,D,D,D,D,DES的保密性仅取决于对密钥的保密，而算法是公开的。至今仍未能找到比穷举搜索密钥更有效的方法。DES是世界第一个公认的实用密码算法标准。目前较为严重的问题是DES的密钥的长度。已经设计出来搜索DES密钥的专用芯片。,1、常规密钥密码体制,DES的保密性,数据保密技术,三重DES使用两个密钥，执行三次DES算法。下图中的方框E和D分别表示执行加密和解密算法。因此加密时是E-D-E，解密时是D-E-D。,1、常规密钥密码体制,三重DES(TripleDES),数据保密技术,E,D,E,K1,K2,K1,明文,密文,D,E,D,K1,K2,K1,密文,明文,加密,解密,内容纲要,一般的数据加密模型常规密钥密码体制公开密钥密码体制,公开密钥密码体制使用不同的加密密钥与解密密钥，是一种“由已知加密密钥推导出解密密钥在计算上是不可行的”密码体制。公开密钥密码体制的产生主要是因为两个方面的原因，一是由于常规密钥密码体制的密钥分配问题，另一是由于对数字签名的需求。现有三种公开密钥密码体制，其中最著名的是RSA体制，它基于数论中大数分解问题的体制,2、公开密钥密码体制,公开密钥密码体制的特点,数据保密技术,在公开密钥密码体制中，加密密钥(即公开密钥)PK是公开信息，而解密密钥(即秘密密钥)SK是需要保密的。加密算法E和解密算法D也是公开的。虽然秘密密钥SK是由公开密钥PK决定的，但却不能根据PK计算出SK。,2、公开密钥密码体制,加密密钥与解密密钥,数据保密技术,任何加密方法的安全性取决于密钥的长度，以及攻破密文所需的计算量。公开密钥密码体制并不具有比传统加密体制更加优越之处。由于目前公开密钥加密算法的开销较大，在可见的将来还看不出来要放弃传统的加密方法。公开密钥还需要密钥分配协议，具体的分配过程并不比采用传统加密方法时更为简单。,2、公开密钥密码体制,公开密钥密码体制与传统加密体制,数据保密技术,(1)发送者用加密密钥PK对明文X加密后，在接收者用解密密钥SK解密，即可恢复出明文，或写为：DSK(EPK(X)X解密密钥是接收者专用的秘密密钥，对其他人都保密。此外，加密和解密的运算可以对调，即EPK(DSK(X)X,2、公开密钥密码体制,公开密钥算法的特点,数据保密技术,(2)加密密钥是公开的，但不能用它来解密，即DPK(EPK(X)X(3)在计算机上可容易地产生成对的PK和SK。(4)从已知的PK实际上不可能推导出SK，即从PK到SK是“计算上不可能的”。(5)加密和解密算法都是公开的。,2、公开密钥密码体制,公开密钥算法的特点,数据保密技术,2、公开密钥密码体制,公开密钥密码体制,数据保密技术,接收者,发送者,E加密算法,D解密算法,加密密钥PK,解密密钥SK,明文X,密文Y=EPK(X),密钥对产生源,明文X=DSK(EPK(X),RSA公开密钥密码体制所根据的原理是：根据数论，寻求两个大素数比较简单，而将它们的乘积分解开则极其困难。每个用户有两个密钥：加密密钥PKe,n和解密密钥SKd,n。,2、公开密钥密码体制,RSA公开密钥密码体制,数据保密技术,用户把加密密钥公开，使得系统中任何其他用户都可使用，而对解密密钥中的d则保密。N为两个大素数p和q之积（素数p和q一般为100位以上的十进数），e和d满足一定的关系。当敌手已知e和n时并不能求出d。,2、公开密钥密码体制,数据保密技术,RSA公开密钥密码体制,若用整数X表示明文，用整数Y表示密文（X和Y均小于n），则加密和解密运算为：加密：YXemodn解密：XYdmodn,2、公开密钥密码体制,数据保密技术,RSA（1）加密算法,计算n。用户秘密地选择两个大素数p和q，计算出npq。n称为RSA算法的模数。明文必须能够用小于n的数来表示。实际上n是几百比特长的数。计算(n)。用户再计算出n的欧拉函数(n)(p1)(q1)(n)定义为不超过n并与n互素的数的个数。选择e。用户从0,(n)1中选择一个与(n)互素的数e作为公开的加密指数。,2、公开密钥密码体制,数据保密技术,RSA（2）密钥的产生,计算d。用户计算出满足下式的ded1mod(n)作为解密指数。得出所需要的公开密钥和秘密密钥：公开密钥（即加密密钥）PKe,n秘密密钥（即解密密钥）SKd,n,2、公开密钥密码体制,数据保密技术,RSA（2）密钥的产生,设选择了两个素数，p7,q17。计算出npq717119。计算出(n)(p1)(q1)96。从0,95中选择一个与96互素的数e。选e5。然后根据(9-10)式，5d1mod96解出d。不难得出，d77,因为ed57738549611mod96。于是，公开密钥PK(e,n)5,119,秘密密钥SK77,119。,2、公开密钥密码体制,数据保密技术,RSA正确性的例子说明,对明文进行加密。先把明文划分为分组，使每个明文分组的二进制值不超过n,即不超过119。设明文X19。用公开密钥加密时，先计算Xe1952476099。再除以119，得出商为20807，余数为66。这就是对应于明文19的密文Y的值。在用秘密密钥SK77,119进行解密时，先计算Yd66771.27.10140。再除以119，得出商为1.06.10138，余数为19。此余数即解密后应得出的明文X。,2、公开密钥密码体制,数据保密技术,RSA正确性的例子说明,2、公开密钥密码体制,公开密钥密码体制的特点,数据保密技术,明文19,19=20807,公开密钥=5,119,加密,5,2476099,119,及余数66,密文66,66=1.0610,秘密密钥=77,119,解密,77,1.27.10,119,及余数19,明文19,140,138,数字签名必须保证以下三点：(1)接收者能够核实发送者对报文的签名；(2)发送者事后不能抵赖对报文的签名；(3)接收者不能伪造对报文的签名。现在已有多种实现各种数字签名的方法。但采用公开密钥算法要比采用常规密钥算法更容易实现。,2