公钥密码系统课件

公钥密码系统一、基本概念对称密码体制的缺陷公钥密码学思想安全性1对称密码体制的缺陷public-key/two-key/asymmetric包括两个密钥:公开密钥(apublic-key),可以被任何人知道,用于加密或验证签名私钥(private-key),只能被消息的接收者或签名者知道,用于解密或签名公钥与私钥不同，但又相互对应，并且由公钥不能推导出对应的私钥。加密或验证签名者不能解密密文或生成签名.选择某种算法（可以公开）能做到：用公钥加密的数据只有使用与该公钥配对的私钥才能解密。基本概念（续）公钥加密算法的核心——单向陷门函数，即从一个方向求值是容易的。但其逆向计算却很困难，从而在实际上成为不可行。定义1.设是一个函数，如果对任意给定的

,计算,使得是容易计算的，但对于任意给定的，计算，使得是难解的，即求的逆函数是难解的，则称是一个单向函数。基本概念（续）定义2.设是一个函数，是与有关的一个参数。对于任意给定的，计算，使得是容易的。如果当不知参数时，计算的逆函数是难解的，但当知道参数时，计算函数的逆函数是容易的，则称是一个单向陷门函数，参数称为陷门。2公钥密码学思想定义7.1.1一个公钥密码体制是这样的一个5元组{M,C,K，EK，DK}，且满足如下的条件：1.M是可能消息的集合；2.C是可能的密文的集合；3.密钥空间K是一个可能密钥的有限集；4．对每一个k={K1，K2}∈K，都对应一个加密算法EK1

∈E,EK1:M→C和解密算法DK2

∈D,DK2:C→M,满足对于任意的m∈M,都有c=EK1（m）,m=DK2(c)=DK2(EK1（m）)=m；5．对于所有的k，在已知E的情况下推出D是计算上不可能的；对每一个k∈K，函数EK1和DK2都是多项式时间可计算的函数。EK1是一个公开函数,K1称作公钥；而DK2是一个秘密函数，K2称作私钥，由用户秘密地保存。由私钥及其他密码信息容易计算出公开密钥(apolynomialtime(P-time)problem)由公钥及算法描述,计算私钥是难的(anNP-timeproblem)因此,公钥可以发布给其他人(wishingtocommunicatesecurelywithitsowner)密钥分配问题不是一个容易的问题(thekeydistributionproblem)3.公钥的安全性依赖于足够大的困难性差别类似对称算法,穷搜索在理论上是能够破解公钥密码exhaustivesearch

但实际上,密钥足够长

(>512bits)，计算上不可行。一般基于一些已知的困难问题(hardproblem）要求足够大的密钥长度

(>512bits)多为大数运算，导致加密速度比对称算法慢二、RSA简介RSA算法内容RSA参数选择RSA理论举例

1.RSA(Rivest,Shamir,Adleman)简介基础大数分解和素性检测——将两个大素数相乘在计算上很容易实现，但将该乘积分解为两个大素数因子的计算量是相当巨大的，以至于在实际计算中是不能实现的。

RSA算法表述：

假定用户A欲送消息给用户B，则RSA算法的加/解密过程为：①首先用户B产生两个大素数p和q（p、q是保密的）。②B计算和（是保密的）。③B选择一个随机数e（），使得，即e和φ互素。④B通过计算得出d，使得（即在与n互素的数中选取与

互素的数，可以通过Eucliden算法得出。d是B自留且保密的，用作解密密钥）。⑤B将n及e作为公钥公开。⑥用户A通过公开渠道查到n和e。⑦对m施行加密变换，即。⑧用户B收到密文c后，施行解密变换：。3。RSA参数选择需要选择足够大的随机素数

p,q(~100digit)通常选择小的加密指数e,且与ø(N)

互素e

对所有用户可以是相同的最初建议使用e=3现在3太小常使用

e=216＋1=65537

解密指数比较大5。RSA举例选素数p=47和q＝71，得n=3337,

(n)=46×70＝3220；2.选择e=79，求得私钥d=e-1

1019(mod3220）。3.公开n=3337和e=77.4.现要发送明文688，计算：68879(mod3337)=15705.收到密文1570后，用私钥d＝1019进行解密：

15701019（mod3337)=6886，离散对数密码体制D-H密钥分配方案Diffie-Hellman

密钥交换算法

Diffie

和Hellman

并没有给出公钥密码实例，也既没能找出一个真正带陷门的单向函数。然而，他们给出单向函数的实例，并且基于此提出D-H密钥交换算法。这个算法是基于有限域中计算离散对数的困难性问题之上的：对任意正整数x，计算gx

是容易的；但是已知g和y求x使y=gx，是计算上几乎不可能的。这称为有限域上的离散对数问题。公钥密码学中使用最广泛的有限域为素域FP

。D-H密钥交换算法拥有美国和加拿大的专利。第五章

密码学的应用D-H密钥交换协议：A和B协商一个大素数p和大整数g，1<g<p，g最好是FP中的本原元，即gx

modp可生成1~p-1中的各整数，例：2是11的本原元。p和g公开。当A和B按如下步骤进行保密通信：(1)A取大的随机数x，并计算X=gx

(modP)(2)B选取大的随机数y，并计算Y=gy

(modP)(3)A将X传送给B；B将Y