第5讲 公钥密码技术1

2020/1/21Ch4(1)-公钥加密技术1第4章公钥密码技术主要知识点：公钥密码体制背包密码RSA密码ElGamal密码椭圆曲线密码公钥分配利用公钥密码分配对称密钥Diffie-Hellman密钥交换2020/1/21Ch4(1)-公钥加密技术2公钥密码技术是为了解决对称密码技术中最难解决的两个问题而提出的一是对称密码技术的密钥分配问题二是对称密码不能实现数字签名Diffie和Hellmna于1976年在《密码学的新方向》中首次提出了公钥密码的观点，标志着公钥密码学研究的开始1977年由Rviest，Shmair和Adlmena提出了第一个比较完善的公钥密码算法，即RSA算法。从那时候起，人们基于不同的计算问题提出了大量的公钥密码算法2020/1/21Ch4(1)-公钥加密技术3公钥密码体制公钥密码体制（Public-KeyCryptosystem）也称非对称密码体制(AsymmetricCryptosystem)或者双钥密码体制(Two-KeyCryptosystem)公钥密码算法是基于数学函数（如单向陷门函数）而不是基于代换和置换公钥密码是非对称的，它使用两个独立的密钥，即公钥和私钥，任何一个都可以用来加密，另一个用来解密公钥可以被任何人知道，用于加密消息以及验证签名；私钥仅仅自己知道的，用于解密消息和签名加密和解密会使用两把不同的密钥，因此称为非对称2020/1/21Ch4(1)-公钥加密技术4一个公钥密码体制有6个部分构成：明文，加密算法，公钥和私钥，密文，解密算法可以构成两种基本的模型：加密模型和认证模型在加密模型中，发送方用接收方的公钥作为加密密钥，接收方用私钥作解密密钥，由于该私钥只有接收方拥有，因此即只有接收者才能解密密文得到明文在认证模型中，发送方用自己的私钥对消息进行变换，产生签名。接收者用发送者的公钥对签名进行验证以确定签名是否有效。只有拥有私钥的发送者才能对消息产生有效的签名，任何人均可以用签名人的公钥来检验该签名的有效性2020/1/21Ch4(1)-公钥加密技术5消息加密算法解密算法消息MMC攻击者接收方B发送方A密钥源PRBPUB图4.1公钥加密模型2020/1/21Ch4(1)-公钥加密技术6消息加密算法解密算法消息MMC攻击者接收方B发送方A密钥源PUAPRA图4.2公钥认证模型2020/1/21Ch4(1)-公钥加密技术7消息加密算法解密算法消息MXC接收方B发送方A密钥源PUAPRA图4.3公钥密码体制的保密和认证加密算法X解密算法M密钥源PRBPUB2020/1/21Ch4(1)-公钥加密技术8公钥密码系统满足的要求同一算法用于加密和解密，但加密和解密使用不同的密钥。两个密钥中的任何一个都可用来加密，另一个用来解密，加密和解密次序可以交换。产生一对密钥（公钥和私钥）在计算上是可行的。已知公钥和明文，产生密文在计算上是容易的。接收方利用私钥来解密密文在计算上是可行的。仅根据密码算法和公钥来确定私钥在计算上不可行。已知公钥和密文，在不知道私钥的情况下，恢复明文在计算上是不可行的。2020/1/21Ch4(1)-公钥加密技术9上面要求的实质是要找一个单向陷门函数单向函数指计算函数值是容易的，而计算函数的逆是不可行的陷门单向函数则存在一个附加信息，当不知道该附加信息时，从函数逆是困难的，但当知道该附加信息时，求函数逆就变得容易了陷门单向函数在附加信息未知时是单向函数，而当附加信息已知时，就不再是单向函数了通常把附加信息称为陷门信息，陷门信息作为私钥，公钥密码体制就是基于这一原理而设计的其安全强度取决于它所依据的问题的计算复杂度。2020/1/21Ch4(1)-公钥加密技术10公钥密码分析和对称密码体制一样，如果密钥太短，公钥密码体制也易受到穷举搜索攻击但公钥密码体制所使用的可逆函数的计算复杂性与密钥长度是比线性函数增大更快函数。密钥长度太大又会使得加密和解密运算太慢而不实用目前提出的公钥密码体制的密钥长度已经足够抵抗穷举攻击，但也使它加密和解密速度变慢，因此公钥密码体制一般用于加密小数据，如会话钥，目前主要用于密钥管理和数字签字。对公钥密码算法的第二种攻击是从公钥计算出私钥。目前为止，还没有在数学上证明这个方面是不可行的。2020/1/21Ch4(1)-公钥加密技术11背包密码(Knapsack)最早提出的公钥密码体制2020/1/21Ch4(1)-公钥加密技术12背包(Knapsack)密码给定一组n个重量W0,W1,...,Wn-1和一个总重量S,能否找到一组系数ai{0,1}满足S=a0W0+a1W1+...+an-1Wn-1(也称其为“子集-和”问题)实例重量(62,93,26,52,166,48,91,141)问题：找到系数满足S=302答案:62+26+166+48=302此处系数为（10101100）已证明一般knapsack问题是NP-完全问题(非常难解)2020/1/21Ch4(1)-公钥加密技术13背包(Knapsack)问题一般背包问题(GK)很难解决但超递增背包问题(super-increasingknapsack)(SIK)很容易解决SIK要求重量递增排列且每个重量比前面所有重量和还大实例重量(2,3,7,14,30,57,120,251)问题:找出子集满足和=186从大到小逐步推算…答案:120+57+7+2=186系数为(1,0,1,0,0,1,1,0)2020/1/21Ch4(1)-公钥加密技术14背包密码系统算法解密1.创建一个超级递增背包(SIK)2.将超级背包转换成“普通”背包(GK)3.公钥:普通背包问题4.私钥:超级递增背包加转换因子很容易用普通背包(GK)加密很容易用私钥解密(将密文转换成SIK)在没有私钥的情况下,必须解决普通背包问题?(非常困难)2020/1/21Ch4(1)-公钥加密技术15背包密码系统实例假设(2,3,7,14,30,57,120,251)是超级递增背包选择m=41、n=491。这里m,n互素并且n大于背包各元素之和则普通背包产生方式：241mod491=82341mod491=123741mod491=2871441mod491=833041mod491=2485741mod491=37312041mod491=1025141mod491=471普通背包:(82,123,287,83,248,373,10,471)2020/1/21Ch4(1)-公钥加密技术16背包密码系统实例私钥:(2,3,7,14,30,57,120,251)及12（m1modn称为m的模逆）m1modn=411mod491=12(491+1=492/12=41)公钥:(82,123,287,83,248,373,10,471),n=491实例:加密明文1001011082+83+373+10=548（密文）解密,(548·12)mod491=6576%491=1936576=491*13+193用私钥(2,3,7,14,30,57,120,251)解193得到明文10010110(2+14+57+120=193)2020/1/21Ch4(1)-公钥加密技术17背包密码系统实例分析如果没有私钥[(2,3,7,14,30,57,120,251),12]攻击者必须找到公钥(82,123,287,83,248,373,10,471)里的某个子集满足元素之和为491变成了普通背包问题，非常难解将超递增背包通过模运算转换为普通背包就是陷门，没有私钥的情况下将很难解密2020/1/21Ch4(1)-公钥加密技术18背包密码系统分析陷门:通过模运算将超级超递增背包转换为一般递增背包单向:一般背包容易用来加密，难解密;超递增则容易解密这种背包密码系统是不安全的在1983被苹果II电脑破解攻击采用的是格约简(latticereduction)技术“普通背包”并不够‘简单’!这种特殊的背包很容易破解!现在很多背包密码的变形是安全的，但已很少应用2020/1/21Ch4(1)-公钥加密技术19RSA密码RSA算法是1977年由Rivest、Shamir、Adleman提出的非常著名的公钥密码算法它是基于大合数的质因子分解问题的困难性RSA算法是一种分组密码，明文和密文是0到n-1之间的整数，通常n的大小为1024位二进制数或309位十进制数.2020/1/21Ch4(1)-公钥加密技术20算法描述1.密钥的产生随机选择两个大素数p,q计算n=p×q计算秘密的欧拉函数(n)=(p-1)(q-1)选择e使得1e(n)，且gcd(e,(n))=1解下列方程求出ded≡1mod(n)，且0≤d≤n公开公钥：PU={e,N}保存私钥：PR={d,p,q}2020/1/21Ch4(1)-公钥加密技术212.加密过程1.加密时明文以分组为单位进行加密，每个分组m的二进制值均小于n，对明文分组m作加密运算：2.c=memodn,且0≤mn3.解密过程1.密文解密m=cdmodn4.签名过程1.计算签名s=mdmodn5.签名验证过程1.签名验证m=semodn2020/1/21Ch4(1)-公钥加密技术22例4.1选择素数：p=47和q=71。计算n=pq=47×71=3337，(n)=(p–1)(q-1)=46×70=3220。选择e：使gcd(e,3220)=1，选取e=79；决定d：de≡1mod3220，得d=1019公开公钥{79,3337}，保存私钥{1019,47,71}；假设消息为M=6882326879666683，进行分组，分组的位数比n要小，我们选取M1=688，M2=232，M3=687，M4=966，M5=668，M6=003。M1的密文为C1=68879mod3337=1570，继续进行类似计算，可得到最终密文为C=1570275620912276158解密时计算M1=15701019mod3337=688，类似可以求出其他明文。2020/1/21Ch4(1)-公钥加密技术23RSA算法的安全性RSA密码体制的安全性是基于分解大整数的困难性假设RSA算法的加密函数c=memodn是一个单向函数，所以对于攻击者来说，试图解密密文是计算上不可行的对于接收方解密密文的陷门是分解n=pq，由于接收方知道这个分解，他可以计算(n)=(p-1)(q-1)，然后用扩展欧几里德算法来计算解密私钥d。2020/1/21Ch4(1)-公钥加密技术24对RSA算法的攻击有下面几个方法：穷举攻击，数学攻击，选择密文攻击，公共模数攻击，计时攻击最基本的攻击是穷举攻击，也就是尝试所有可能的私钥数学攻击的实质是试图对两个素数乘积的分解计时攻击也可以用于对RSA算法的攻击。计时攻击是攻击者通过监视系统解密消息所花费的时间来确定私钥。时间攻击方式比较独特，它是一种只用到密文的攻击方式