公钥密码体制及典型算法-RSA

1公钥密码体制及典型算法2在公钥密码体制以前的整个密码学史中，所有的密码算法，包括原始手工计算的、由机械设备实现的以及由计算机实现的，都是基于代换和置换这两个基本工具。而公钥密码体制则为密码学的发展提供了新的理论和技术基础，一方面公钥密码算法的基本工具不再是代换和置换，而是数学函数；另一方面公钥密码算法是以非对称的形式使用两个密钥，两个密钥的使用对保密性、密钥分配、认证等都有着深刻的意义。可以说公钥密码体制的出现在密码学史上是一个最大的而且是惟一真正的革命。1公钥密码体制的基本概念3公钥密码体制的概念是在解决单钥密码体制中最难解决的两个问题时提出的，这两个问题是密钥分配和数字签字。单钥密码体制在进行密钥分配时,要求通信双方或者已经有一个共享的密钥，或者可籍助于一个密钥分配中心。对第一个要求，常常可用人工方式传送双方最初共享的密钥，这种方法成本很高，而且还完全依赖信使的可靠性。第二个要求则完全依赖于密钥分配中心的可靠性。第二个问题数字签字考虑的是如何为数字化的消息或文件提供一种类似于为书面文件手书签字的方法。1976年W.Diffie和M.Hellman对解决上述两个问题有了突破，从而提出了公钥密码体制。公钥密码体制的基本概念4对称密码体制的缺陷密钥分配问题通信双方要进行加密通信，需要通过秘密的安全信道协商加密密钥，而这种安全信道可能很难实现；密钥管理困难问题在有多个用户的网络中，任何两个用户之间都需要有共享的秘密钥，当网络中的用户n很大时，需要管理的密钥数目是非常大。n用户保密通信网，用户彼此间进行保密通信需要个密钥。n=1000：499500个密钥n=5000：12497500个密钥没有签名功能，无法实现抗抵赖问题：当主体A收到主体B的电子文挡（电子数据）时，无法向第三方证明此电子文档确实来源于B。陌生人间不便进行保密通信问题2(1)/2nCnn5别名：公钥密码体制，双钥密码体制两个密钥：公开密钥（公钥）：可以被任何人知道,用于加密或验证签名秘密密钥（私钥）：只能被消息的接收者或签名者知道,用于解密或签名。加密或验证签名者不能解密或生成签名（已知密码算法和加密密钥，求解密密钥在计算上是不可行的）。安全性基础：基于数学难题标志性文献W.DiffieandM.E.Hellman,NewDirectionsinCryptography,IEEETransactiononInformationTheory,V.IT-22.No.6,Nov1976,PP.644-654公钥密码体制的基本概念6由私钥及其他密码信息容易计算出公开密钥(apolynomialtime(P-time)problem)由公钥及算法描述,计算私钥是难的(anNP-timeproblem)因此,公钥可以发布给其他人(wishingtocommunicatesecurelywithitsowner)密钥分配问题不是一个容易的问题(thekeydistributionproblem)公钥密码体制的基本概念7公钥算法分类Public-KeyDistributionSchemes(PKDS，公钥分配系统)用于交换秘密信息(依赖于双方主体)常用于对称加密算法的密钥PublicKeyEncryption(PKE，公钥加密)用于加密任何消息任何人可以用公钥加密消息私钥的拥有者可以解密消息任何公钥加密方案能够用于密钥分配方案PKDS许多公钥加密方案也是数字签名方案SignatureSchemes（签名方案）用于生成对某消息的数字签名私钥的拥有者生成数字签名任何人可以用公钥验证签名8公钥密码系统可用于以下三个方面：(1)通信保密：此时将公钥作为加密密钥，私钥作为解密密钥，通信双方不需要交换密钥就可以实现保密通信。Alice的公钥Joy明文输入加密算法，如RSA传输密文解密算法明文输出Alice的私钥Bob的公钥环TedAliceMike9(2)数字签名：将私钥作为加密密钥，公钥作为解密密钥，可实现由一个用户对数据加密而使多个用户解读。Bob的公钥Joy明文输入加密算法，如RSA传输密文解密算法明文输出Bob的私钥Alice的公钥环TedBobMike10(3)密钥交换：通信双方交换会话密钥，以加密通信双方后续连接所传输的信息。每次逻辑连接使用一把新的会话密钥，用完就丢弃。11公开密钥算法的特点:（1）发送者用加密密钥PK对明文X加密后，在接收者用解密密钥SK解密，即可恢复出明文，或写为：DSK(EPK(X))X解密密钥是接收者专用的秘密密钥，对其他人都保密。此外，加密和解密的运算可以对调，即EPK(DSK(X))X（2）加密密钥是公开的，但不能用它来解密，即DPK(EPK(X))X12公开密钥算法的特点:（3）在计算机上可以容易地产生成对的PK和SK。（4）从已知的PK实际上不可能推导出SK，即从PK到SK是“计算上不可能的”。（5）加密和解密算法都是公开的。13公钥密码算法的最大特点是采用两个相关密钥将加密和解密能力分开，其中一个密钥是公开的，称为公开密钥，简称公开钥，用于加密；另一个密钥是为用户专用，因而是保密的，称为秘密密钥，简称秘密钥，用于解密。因此公钥密码体制也称为双钥密码体制。算法有以下重要特性：已知密码算法和加密密钥，求解密密钥在计算上是不可行的。公钥密码体制的原理14图公钥体制加密的框图加密算法解密算法发送者A接收者B密码分析员(窃听者)密钥源mBˆKScmˆBPKBSKm15加密过程有以下几步：①要求接收消息的端系统，产生一对用来加密和解密的密钥，如图中的接收者B，产生一对密钥PKB，SKB，其中PKB是公开钥，SKB是秘密钥。②端系统B将加密密钥（如图中的PKB）予以公开。另一密钥则被保密（图中的SKB）。公钥密码体制的原理16③A要想向B发送消息m，则使用B的公开钥加密m，表示为c=EPKB[m],其中c是密文，E是加密算法。④B收到密文c后，用自己的秘密钥SKB解密，表示为m=DSKB[c]，其中D是解密算法。公钥密码体制的原理17公钥密码体制认证框图18因为只有B知道SKB，所以其他人都无法对c解密。公钥加密算法不仅能用于加、解密，还能用于对发方A发送的消息m提供认证，如下图所示。用户A用自己的秘密钥SKA对m加密，表示为c=ESKA[m]将c发往B。B用A的公开钥PKA对c解密，表示为m=DPKA[c]公钥密码体制认证的原理19因为从m得到c是经过A的秘密钥SKA加密，只有A才能做到。因此c可当做A对m的数字签字。另一方面，任何人只要得不到A的秘密钥SKA就不能篡改m，所以以上过程获得了对消息来源和消息完整性的认证。公钥密码体制认证的原理20在实际应用中，特别是用户数目很多时，以上认证方法需要很大的存储空间，因为每个文件都必须以明文形式存储以方便实际使用，同时还必须存储每个文件被加密后的密文形式即数字签字，以便在有争议时用来认证文件的来源和内容。改进的方法是减小文件的数字签字的大小，即先将文件经过一个函数压缩成长度较小的比特串，得到的比特串称为认证符。认证符具有这样一个性质：如果保持认证符的值不变而修改文件这在计算上是不可行的。用发送者的秘密钥对认证符加密，加密后的结果为原文件的数字签字。公钥密码体制认证的原理21以上认证过程中，由于消息是由用户自己的秘密钥加密的，所以消息不能被他人篡改，但却能被他人窃听。这是因为任何人都能用用户的公开钥对消息解密。为了同时提供认证功能和保密性，可使用双重加、解密。如下图所示。公钥密码体制认证的原理22公钥密码体制的认证、保密框图23发方首先用自己的秘密钥SKA对消息m加密，用于提供数字签字。再用收方的公开钥PKB第2次加密，表示为c=EPKB[ESKA[m]]解密过程为m=DPKA[DSKB[c]]即收方先用自己的秘密钥,再用发方的公开钥对收到的密文两次解密。公钥密码体制认证的原理2019/10/1424公钥保密和认证体制为了要同时实现保密性和确证性，要采用双重加、解密保密公开保密公开用户ADSKAEPKBDSKBEPKA用户Bmm保密认证25公钥密码算法应满足以下要求:①接收方B产生密钥对（公开钥PKB和秘密钥SKB）在计算上是容易的。②发方A用收方的公开钥对消息m加密以产生密文c，即c=EPKB[m]在计算上是容易的。③收方B用自己的秘密钥对c解密，即m=DSKB[c]在计算上是容易的。公钥密码算法应满足的要求26④敌手由B的公开钥PKB求秘密钥SKB在计算上是不可行的。⑤敌手由密文c和B的公开钥PKB恢复明文m在计算上是不可行的。⑥加、解密次序可换，即EPKB[DSKB(m)]=DSKB[EPKB(m)]其中最后一条虽然非常有用，但不是对所有的算法都作要求。公钥密码算法应满足的要求27以上要求的本质之处在于要求一个陷门单向函数。单向函数是两个集合X、Y之间的一个映射，使得Y中每一元素y都有惟一的一个原像x∈X，且由x易于计算它的像y，由y计算它的原像x是不可行的。这里所说的易于计算是指函数值能在其输入长度的多项式时间内求出，即如果输入长n比特，则求函数值的计算时间是na的某个倍数，其中a是一固定的常数。这时称求函数值的算法属于多项式类P，否则就是不可行的。例如，函数的输入是n比特，如果求函数值所用的时间是2n的某个倍数，则认为求函数值是不可行的。公钥密码算法应满足的要求28注意这里的易于计算和不可行两个概念与计算复杂性理论中复杂度的概念极为相似，然而又存在着本质的区别。在复杂性理论中，算法的复杂度是以算法在最坏情况或平均情况时的复杂度来度量的。而在此所说的两个概念是指算法在几乎所有情况下的情形。称一个函数是陷门单向函数，是指该函数是易于计算的，但求它的逆是不可行的，除非再已知某些附加信息。当附加信息给定后，求逆可在多项式时间完成。公钥密码算法应满足的要求29总结为：陷门单向函数是一族可逆函数fk，满足①Y=fk(X)易于计算（当k和X已知时）。②X=f-1k(Y)易于计算（当k和Y已知时）。③X=f-1k(Y)计算上是不可行的（当Y已知但k未知时）。因此，研究公钥密码算法就是要找出合适的陷门单向函数。公钥密码算法应满足的要求30和单钥密码体制一样，如果密钥太短，公钥密码体制也易受到穷搜索攻击。因此密钥必须足够长才能抗击穷搜索攻击。然而又由于公钥密码体制所使用的可逆函数的计算复杂性与密钥长度常常不是呈线性关系，而是增大得更快。所以密钥长度太大又会使得加解密运算太慢而不实用。因此公钥密码体制目前主要用于密钥管理和数字签字。对公钥密码算法的第2种攻击法是寻找从公开钥计算秘密钥的方法。目前为止，对常用公钥算法还都未能够证明这种攻击是不可行的。对公钥密码体制的攻击31还有一种仅适用于对公钥密码算法的攻击法，称为可能字攻击。例如对56比特的DES密钥用公钥密码算法加密后发送，敌手用算法的公开钥对所有可能的密钥加密后与截获的密文相比较。如果一样，则相应的明文即DES密钥就被找出。因此不管公钥算法的密钥多长，这种攻击的本质是对56比特DES密钥的穷搜索攻击。抵抗方法是在欲发送的明文消息后添加一些随机比特。对公钥密码体制的攻击32强力攻击(对密钥)密钥不能太短，防止密钥穷举但也不能太长，以免影响速度公开密钥算法本身可能被攻破赖以安全的基石----数学难题被破解可能报文攻击(对报文本身的强力攻击)对所有可能报文加密，直到与截获密文相同对公钥密码体制的攻击33RSA算法是1978年由罗纳德·李维斯特（RonRivest）、阿迪·萨莫尔（AdiShamir）和伦纳德·阿德曼（LeonardAdleman）提出的一种用数论构造的、也是迄今为止理论上最为成熟完善的公钥密码体制，该体制已得到广泛的应用。它既可用于加密、又可用于数字签字。RSA算法的安全性基于数论中大整数分解的困难性。RLRivest,AShamir,LAdleman,OnDigitalSignaturesandPublicKeyCryptosystems,Communicationsof