第4章公钥密码算法

1第4章公钥密码算法一、公钥密码体制概述二、公钥加密算法RSA、ElGamal、椭圆曲线密码、Diffie-Hellman密钥交换算法2公钥密码体制概述•1976年Diffie和Hellman的“Newdirectionsincryptography”导致了密码学上的一场革命，开创了公钥密码学的新纪元。他们首次证明了在发送端和接收端无密钥传输的保密通信是可能的。•1977年Rivest，Shamir和Adleman提出了RSA公钥密码算法。•90年代逐步出现椭圆曲线密码等其他公钥算法。公钥密码体制，又称为双钥或非对称密码体制密码系统有两个密钥，即加密密钥和解密密钥不同，从一个难于推出另一个。这两个密钥一个是公开的，一个是秘密的，分别称为公开密钥和私有密钥，公开密钥是对外公开的，即所有的人都可知，私有密钥是只有特定的用户方能拥有。3公钥密码体制概述•公钥密码体制与私钥密码体制的最大不同点就是：加密密钥和解密密钥不同，从一个难于推出另一个。在公钥密码体制中，将这两个不同的密钥区分为公开密钥PK(PublicKey)和私有密钥SK(SecreteKey）。•六个组成部分：–明文、密文；公钥、私钥；–加密算法、解密算法4公钥密码体制模型A加密B解密A加密B解密明文明文明文密文密文加密模型认证模型B的公钥B的私钥A的私钥A的公钥明文5公钥密码体制的特点•加密和解密能力分开。•可以实现多个用户加密的消息只能由一个用户解读（用于公共网络中实现保密通信）。•可实现只能由一个用户加密消息而使多个用户可以解读（可用于认证系统中对消息进行数字签字）。•无需事先分配密钥。•重要特点–仅根据密码算法和加密密钥来确定解密密钥在计算上不可行。•有些算法如RSA还具有：两个密钥中的任何一个都可用来加密，另一个用来解密。•优点：能很好解决私钥加密中由于密钥数量过多导致的管理难和费用高等问题，也不用担心传输中的私钥泄漏，保密性能优于私钥加密。•缺点：加密算法复杂，加密速度难以达到理想状态。6公钥密码体制依赖的基础•传统的对称密码体制依赖的基础是替代和置换两种转换思想。与对称密码体制不同的是，公钥密码体制依赖的基础是数学上的某类问题的求解困难。•经典的公钥密码算法RSA、椭圆曲线密码算法ECC等都是依赖某类数学问题的，它们共同的特点是基于某个单向陷门函数。单向陷门函数y=fk(x)是指同时满足下列条件的一类可逆函数：7公钥密码体制依赖的基础•⑴函数是一一映射关系，也就是说，对于每个函数值y，只有唯一的一个原象x与之对应；•⑵给定x与关键参数k,函数y=fk(x)很容易计算；•⑶给定y，存在某个关键参数k’，在未知k’时，由y计算出x非常困难，即在未知k’的条件下，逆函数x=f-1k’(y)的计算相当复杂，实际上是不可行的；在已知k’时，对给定的任何y，则逆函数x=f-1k’(y)很容易计算；•⑷给定y和参数k，无法从函数y=fk(x)推导出影响其逆函数f-1的关键参数k’。•设计任何一种公钥密码方案，所要做的工作就是寻找这样的单向陷门函数，其中陷门信息就是私钥，也就是上面所列举的关键参数k’。8公钥密码系统的特征根据密码系统的组成以及公钥密码体制自身的特点，一个公钥密码系统可以表示为：加密算法E、解密算法D、公钥/私钥(PK/SK)对、明文M、密文C六个元素，且各元素必须要满足以下条件：9公钥密码系统的特征•⑴密钥。要满足两点要求：公钥/私钥(PK/SK)对容易产生，且私钥除了生成密钥的用户自己知道之外，其他任何人都不可知；已知公钥PK，无法计算出私钥SK，即公钥密码系统所要满足的基本条件之一是从公开密钥无法通过计算得到私有密钥。10公钥密码系统的特征•⑵加密算法E。要满足两点要求：已知公钥PK，对任何明文M，由E计算出密文C非常容易，即C=EPK(M)易计算，或者已知私钥SK，对任何信息M，由E计算数字签名也非常容易，即C=ESK(M)易计算。•⑶解密算法D。要满足两点要求：已知私钥SK，对任何密文C，由D容易计算出明文M，或者已知公钥PK，对任何用SK所做的数字签名C，容易通过D计算，得到签名前的信息；但是已知公钥PK、密文C，以及解密算法D，无法由三者推导出明文M或者私钥SK。即由公钥、密文和解密算法，推导明文和解密密钥都是计算不可行的。•一个设计良好的密码系统，加密算法E和解密算法D应该都是公开的，该原则同样适用于公钥密码系统，公钥密码系统中唯一需要保密的就是私钥SK。11公钥密码体制加解密过程假设网络上的两个用户Alice和Bob需要进行秘密通信，为了防止攻击者Eve窃听信息，Alice和Bob选择使用公钥密码体制加密传输的信息。Alice是信息的发送方；Bob是信息的接收方。12公钥密码体制加解密过程•⑴Alice与Bob产生公钥/私钥对：PKA/SKA，PKB/SKB。•⑵Alice与Bob通过某种机制公布各自的公钥PKA与PKB，例如将公钥放到一个公共的服务器，供其他用户查询。•⑶Alice通过查询公共服务器获得Bob的公钥PKB。如果Alice欲给Bob发送报文M，他就用Bob的公钥PKB加密报文。已知待加密的明文M以及Bob的公钥PKB，Alice很容易通过加密算法E计算出密文，即C=EPKB(M)。•（4）接收方Bob收到Alice发送的信息之后，使用自己的私钥SKB解密报文。已知密文C和私钥SKB，Bob很容易通过解密算法计算出明文M，即M=DSKB(C)。假设攻击者Eve窃听到Alice发送的报文，虽然Eve可查询获得Bob的公钥PKB，但从PKB确定Bob的私钥SKB在计算上是不可行的，因此Eve无法获知Bob的私钥SKB；仅知道公开密钥和密文，无法计算出明文M。因此攻击者Eve无法得到Alice发给Bob的密码信息。13公钥密码体制•公钥密码技术的主要价值是解决下列问题：–1）密钥分发；–2）大范围应用中，数据的保密性和完整性；–3）实体鉴别；–4）不可抵赖性；•公钥密码体制的应用可分为3类：–a）加密/解密：发送方用接收方的公钥对消息加密。–b）数字签名：发送方用其私钥对消息签名。签名可以对整条消息加密或对消息的一个小的数据块加密来产生，其中该小的数据块是整条消息的函数。–c）密钥交换：通信双方交换会话密钥。有几种不同的方法可用于密钥交换，这些方法都使用了通信一方或双方的私钥。14公钥密码体制•有些算法可用于上述三种应用，而其他一些算法则只适用其中一种或两种应用。算法加密/解密数字签名密钥交换RSA是是是椭圆曲线密码是是是Diffie-Hellman否否是DSS否是否15公钥密码体制自1976年提出公钥密码系统以来，密码专家们已设计出多种公钥密码算法，这些算法的共同点都是基于某类数学难题，通过找到该类问题的某个单向陷门函数实现对数据的加密和解密。依据所依赖的数学难题类别划分，主要有以下3类系统：◆基于大整数因子分解问题的公钥系统，典型代表是RSA算法；◆基于有限域椭圆曲线离散对数问题的公钥系统，典型代表是ECC算法；◆基于有限域离散对数问题的公钥系统，典型算法是DSA。16若干较有影响的公钥加密算法•RSA算法：基于大整数素因子分解问题，目前认为是安全的。•Merkle-Hellman背包体制：基于子集和问题，已证明不安全。•McEliece体制：基于余代数编码中的线性解码问题，目前认为是安全的。•ElGamal体制：基于有限域上的离散对数问题，目前认为有一定安全性。•Chor-Rivest背包体制：基于子集和问题，目前认为是安全的。•椭圆曲线密码：基于椭圆曲线上的离散对数问题，是对ElGamal体制的改进，目前认为是安全的。•有限自动机密码：基于有限自动机的求逆问题，目前认为有一定安全性。17RSA算法1976年Deffie和Hellman提出公钥密码系统思想之后，1977年麻省理工学院的RonRivest、AdiShamir和LenAdleman三位学者研制了RSA(Rivest-Shamir-Adleman)公钥密码方案，该方案于1978年首次发表，从那以后至今，RSA算法是被使用最多的公钥密码方案。18RSA算法依赖的数学问题•RSA算法基于“大整数质因子分解”非常困难这一数学难题，这里大整数通常有几百位长。RSA算法依赖以下几个数论定理：•⑴模运算的性质：–正整数n是素数，集合Zn={0，1，2….，(n-1)}表示小于n的所有非负整数集合，则对于集合Zn中的每一个非零整数wZn，均存在一个z，满足公式w×z=1modn，我们称z是w的乘法逆元，且n是它们的模。19RSA算法依赖的数学问题•⑵费马定理：–如果p是素数，a是不能被p整除的正整数，则：ap-1≡1modp•例如：P=7，a=2，则27-1=26=64，64mod7=120RSA算法依赖的数学问题•⑶欧拉函数：正整数n的欧拉函数是指小于n且与n互素的正整数个数，通常记为Ø(n)。•对于任一素数p，显然有：Ø(p)＝p–1，•例如：–设p=3，小于3且与3互素的正整数为1，2，因此Ø(3)=2；类似地，当p=7时，小于7且与7互素的正整数为1，2，3，4，5，6，因此Ø(7)=6。•假定有两个不同的素数p和q，n是p与q之积，即n=p×q，则有如下公式关系：Ø(n)=Ø(pq)=Ø(p)×Ø(q)=(p-1)×(q-1)•例如：–取n=21，Ø(21)=Ø(3)×Ø(7)=(3-1)×(7-1)=2×6=12，其中这12个整数是{1，2，4，5，8，10，11，13，16，17，19，20}。21RSA算法依赖的数学问题•⑷欧拉定理：–任何两个互素的整数a和n，有如下关系：aØ(n)≡1modn•例如：a=3；n=8；由(3)欧拉函数的定义，Ø(8)=4；则aØ(n)=34=81=10×8+1≡1mod8≡1modn22RSA算法依赖的数学问题•（５）欧几里德(Euclid)算法：–该算法主要的思想是：用一个简单的方法确定两个正整数的最大公因子，并且如果这两个整数互素，通过扩展该算法能确定它们各自的乘法逆元。23欧几里德(Euclid)算法设ａ≥ｎ，求ａ和ｎ的最大公因子（ａ，ｎ）以及（ａ，ｎ）＝ｓａ＋ｔｎ中的ｓ与ｔ。–令r0=a,r1=n，利用辗转相除法可得：r0=r1q1+r2,0≤r2r1r1=r2q2+r3,0≤r3r2…rm-2=rm-1qm-1+rm,0rmrm-1rm-1=rmqm+rm+1,rm+1=0(a,n)=(r0,r1)=(r1,r2)=…=(rm-1,rm)=(rm,0)=rm.–由上述关系式可以得到（ａ，ｎ）＝ｓａ＋ｔｎ中的ｓ与ｔ24欧几里德(Euclid)算法25欧几里德(Euclid)算法26欧几里德(Euclid)算法27欧几里德(Euclid)算法28RSA算法密钥产生过程•⑴随机选择两个秘密的大素数p与q，且p×q=n。为了增强算法的安全性，避免攻击者通过数学攻击的方法找到n的欧拉函数Ø(n)，从而攻破RSA密码方案，RSA算法的设计者建议：1.p与q长度应该只差几个数字，这样对于1024位的密钥来说，p与q都应该约位于区间[1075,10100]内；2.p-1与q-1都应有一个大的素因子；3.gcd（p-1，q-1）应该较小。另外，已经证明，若en且dn1/4,则d很容易被确定。•⑵计算n的欧拉函数值：Ø(n)=(p-1)×(q-1)。29RSA算法密钥产生过程•⑶随机选择一个大的正整数e，e满足小于n且与Ø(n)互素的条件，即e与Ø(n)的最大公因子是1。•(4)根据e，Ø(n)，计算另外一个值d，d是e的乘法逆元，且Ø(n)是它们的模，由模运算及乘法逆元的性质，d×e=1modØ(n)。•则两个二元组(e,n)、(d,n)构成RSA的密钥对，选择其中任意一个二元组作为公钥，则另外一个就为私钥，在此，我们定义(e,n)为公钥，(d,n)为私钥。30RSA算法密钥产生过程•例如：•1)令p=7，q=11，则n=77；•2)计算n的欧拉函数值Ø(n)=(7-1)×(11-1)=60；•3)选