1、密码学基础（密码学基础（2）胡建斌胡建斌北京大学网络与信息安全研究室北京大学网络与信息安全研究室E-mail: http:/ 目目 录录1.数据加密标准数据加密标准2.公开密钥算法公开密钥算法数据加密标准数据加密标准（Data Encryption Standard,DES)背景背景发明人发明人：美国：美国IBM公司公司 W.Tuchman 和和 C.Meyer 1971-1972年研制成功年研制成功基础：基础：1967年美国年美国Horst Feistel提出的理论提出的理论产生：美国国家标准局（产生：美国国家标准局（NBS)1973年年5月到月到1974年年8月两次发布通告，月两次发布通告
2、，公开征求用于电子计算机的加密算法。经评选从一大批算法中采纳公开征求用于电子计算机的加密算法。经评选从一大批算法中采纳 了了IBM的的LUCIFER方案方案标准化：标准化：DES算法算法1975年年3月公开发表，月公开发表，1977年年1月月15日由美国国家标日由美国国家标 准局颁布为数据加密标准（准局颁布为数据加密标准（Data Encryption Standard），于），于 1977年年7月月15日生效日生效背景背景美国国家安全局（美国国家安全局（NSA,National Security Agency)参与了参与了美国国家标准局制定数据加密标准的过程。美国国家标准局制定数据加密标准的
3、过程。NBS接受了接受了NSA的的某些建议，对算法做了修改，并将密钥长度从某些建议，对算法做了修改，并将密钥长度从LUCIFER方案方案中的中的128位压缩到位压缩到56位位1979年，美国银行协会批准使用年，美国银行协会批准使用DES1980年，年，DES成为美国标准化协会成为美国标准化协会(ANSI)标准标准1984年年2月，月，ISO成立的数据加密技术委员会成立的数据加密技术委员会(SC20)在在DES基础上制定数据加密的国际标准工作基础上制定数据加密的国际标准工作DES概述概述分组加密算法：明文和密文为分组加密算法：明文和密文为64位分组长度位分组长度对称算法：加密和解密除密钥编排不同
4、外，使用同一算法对称算法：加密和解密除密钥编排不同外，使用同一算法密钥长度：密钥长度：56位，但每个第位，但每个第8位为奇偶校验位，可忽略位为奇偶校验位，可忽略密钥可为任意的密钥可为任意的56位数，但存在弱密钥，容易避开位数，但存在弱密钥，容易避开采用混乱和扩散的组合，每个组合先替代后置换，共采用混乱和扩散的组合，每个组合先替代后置换，共16轮轮只使用了标准的算术和逻辑运算，易于实现只使用了标准的算术和逻辑运算，易于实现DES加密算法的一般描述加密算法的一般描述输入输入64比特明文数据比特明文数据初始置换初始置换IP在密钥控制下在密钥控制下16轮迭代轮迭代初始逆置换初始逆置换IP-1输出输出6
5、4比特密文数据比特密文数据交换左右交换左右32比特比特 DES加密过程加密过程DES加密过程加密过程)(6416,2,1),(16,2,1)64(1616111100LRIPbitikRfLRiRLbitIPRLiiiiii密文输入码令令i表示迭代次数，表示迭代次数，表示逐位模表示逐位模2求和，求和，f为为加密函数加密函数DES解密过程解密过程令令i表示迭代次数，表示迭代次数，表示逐位模表示逐位模2求和，求和，f为为加密函数加密函数)(641,15,16),(1,15,16)64(0011111616LRIPbitikRfRLiLRbitIPLRiiiiii明文密文DES中的各种置换、扩展和替
6、代中的各种置换、扩展和替代初始置换初始置换IP和初始逆置换和初始逆置换IP1 IP和和IP12014MM1420MMIPIP1Li-1（32比特）比特）Ri-1（32比特）比特）Li（32比特）比特）48比特寄存器比特寄存器选择扩展运算选择扩展运算E48比特寄存器比特寄存器子密钥子密钥Ki（48比特）比特）32比特寄存器比特寄存器选择压缩运算选择压缩运算S置换运算置换运算PRi（32比特）比特）Li=Ri-1DES的的一轮迭代一轮迭代扩展置换扩展置换-盒盒32位扩展到位扩展到48位位扩展扩展压缩替代压缩替代S-盒盒48位压缩到位压缩到32位位共共8个个S盒盒S-盒1S-盒2S-盒3S-盒4S-
7、盒5S-盒6S-盒7S-盒8S-盒的构造盒的构造1 2 3 4 5 61 6262 3 4 521133 911001110019bbbbbbbbSbbbb行：-盒子 行 列列：值：14=1100S-盒的构造盒的构造DES中其它算法都是线性的，而中其它算法都是线性的，而S-盒运算则是非线性的盒运算则是非线性的S-盒不易于分析，它提供了更好的安全性盒不易于分析，它提供了更好的安全性所以所以S-盒是算法的关键所在盒是算法的关键所在S-盒的构造准则盒的构造准则S盒的每一行是整数盒的每一行是整数0，15的一个置换的一个置换没有一个没有一个S盒是它输入变量的线性函数盒是它输入变量的线性函数改变改变S盒的
8、一个输入位至少要引起两位的输出改变盒的一个输入位至少要引起两位的输出改变对任何一个对任何一个S盒和任何一个输入盒和任何一个输入X，S（X）和）和 S(X 001100）至少有两个比特不同（这里）至少有两个比特不同（这里X是长度为是长度为6的比特串）的比特串）对任何一个对任何一个S盒，对任何一个输入对盒，对任何一个输入对e,f属于属于0,1,S(X)S(X 11ef00)对任何一个对任何一个S盒，如果固定一个输入比特，来看一个固定输出比特的值，盒，如果固定一个输入比特，来看一个固定输出比特的值，这个输出比特为这个输出比特为0的输入数目将接近于这个输出比特为的输入数目将接近于这个输出比特为1的输入
9、数目的输入数目S-盒的构造要求盒的构造要求S-盒是许多密码算法的唯一非线性部件盒是许多密码算法的唯一非线性部件,因此因此,它的密码强度它的密码强度决定了整个算法的安全强度决定了整个算法的安全强度提供了密码算法所必须的混乱作用提供了密码算法所必须的混乱作用如何全面准确地度量如何全面准确地度量S-盒的密码强度和设计有效的盒的密码强度和设计有效的S-盒是分盒是分组密码设计和分析中的难题组密码设计和分析中的难题非线性度、差分均匀性、严格雪崩准则、可逆性、没有陷门非线性度、差分均匀性、严格雪崩准则、可逆性、没有陷门置换置换p-盒的构造盒的构造p-盒的构造准则盒的构造准则P置换的目的是提供雪崩效应置换的目
10、的是提供雪崩效应明文或密钥的一点小的变动都引起密文的较大变化明文或密钥的一点小的变动都引起密文的较大变化 k1 （56 位）(48 位)ki （56 位）（48 位）64 位 密 钥置 换 选 择 1 C0（28 位）D0（28 位）循 环 左 移循 环 左 移 C1（28 位）D1（28 位）循 环 左 移循 环 左 移 Ci（28 位）Di（28 位）置 换 选 择 2置 换 选 择 2密 钥 表 的 计 算 逻 辑循 环 左 移：1 1 9 12 1 10 23 2 11 24 2 12 25 2 13 26 2 14 27 2 15 28 2 16 1DES中的子密钥的生成中的子密钥的
11、生成密钥置换算法的构造准则密钥置换算法的构造准则设计目标：子密钥的统计独立性和灵活性设计目标：子密钥的统计独立性和灵活性实现简单实现简单速度速度不存在简单关系：不存在简单关系：(给定两个有某种关系的种子密钥给定两个有某种关系的种子密钥,能预测它们轮子密能预测它们轮子密钥之间的关系钥之间的关系)种子密钥的所有比特对每个子密钥比特的影响大致相同种子密钥的所有比特对每个子密钥比特的影响大致相同从一些子密钥比特获得其他的子密钥比特在计算上是难的从一些子密钥比特获得其他的子密钥比特在计算上是难的没有弱密钥没有弱密钥Li-1（32比特）比特）Ri-1（32比特）比特）Li（32比特）比特）48比特寄存器比
12、特寄存器选择扩展运算选择扩展运算E48比特寄存器比特寄存器子密钥子密钥Ki（48比特）比特）32比特寄存器比特寄存器选择压缩运算选择压缩运算S置换运算置换运算PRi（32比特）比特）Li=Ri-1DES的的一轮迭代一轮迭代DES加密算法的一般描述加密算法的一般描述DES的工作模式的工作模式电子密码本电子密码本 ECB(electronic codebook mode)ECB(electronic codebook mode)密码分组链接密码分组链接 CBC(cipher block chaining)CBC(cipher block chaining)密码反馈密码反馈 CFB(cipher f
13、eedback)CFB(cipher feedback)输出反馈输出反馈 OFB(output feedback)OFB(output feedback)iKiiKiC=E(P)P=D(C)电子密码本电子密码本ECBECB的特点的特点简单和有效简单和有效可以并行实现可以并行实现不能隐藏明文的模式信息不能隐藏明文的模式信息 相同明文相同明文生成生成相同密文，相同密文，同样信息多次出现造成泄漏同样信息多次出现造成泄漏对明文的主动攻击是可能的对明文的主动攻击是可能的 信息块可被替换、重排、删除、重放信息块可被替换、重排、删除、重放误差传递：密文块损坏误差传递：密文块损坏仅仅对应明文块损坏对应明文块损
14、坏适合于传输短信息适合于传输短信息密码分组链接密码分组链接CBCiKii-1iKii-1C =E(PC)P=D(C)CCBC的特点的特点没有已知的并行实现算法没有已知的并行实现算法能隐藏明文的模式信息能隐藏明文的模式信息 需要共同的初始化向量需要共同的初始化向量IVIV 相同明文相同明文生成生成不同密文不同密文 初始化向量初始化向量IVIV可以用来改变第一块可以用来改变第一块对明文的主动攻击是不容易的对明文的主动攻击是不容易的 信息块不容易被替换、重排、删除、重放信息块不容易被替换、重排、删除、重放 误差传递：密文块损坏误差传递：密文块损坏两两明文明文块块损坏损坏安全性好于安全性好于ECBEC
15、B适合于传输长度大于适合于传输长度大于6464位的报文，还可以进行用户鉴别位的报文，还可以进行用户鉴别,是大多系统的标准如是大多系统的标准如 SSLSSL、IPSecIPSec密码反馈密码反馈CFB CFB:CFB:分组密码分组密码流密码流密码假定：假定：SiSi 为移位寄存器为移位寄存器,传输单位为传输单位为jbitbit 加密加密:C Ci i=P=Pi i(E EK K(S(Si i)的高的高j j位位)S Si i+1+1=(S=(Si ij)|Cj)|Ci i 解密解密:P Pi i=C=Ci i(E EK K(S(Si i)的高的高j j位位)S Si i+1+1=(S=(Si i
16、j)|Cj)|Ci i密码反馈密码反馈CFB加密加密Ci=Pi(EK(Si)的高的高j位位);Si+1=(Sij)|Ci 密码反馈密码反馈CFB解密解密Pi=Ci(EK(Si)的高的高j位位);Si+1=(Sij)|Ci CFB的特点的特点分组密码分组密码流密码流密码没有已知的并行实现算法没有已知的并行实现算法隐藏了明文模式隐藏了明文模式需要共同的移位寄存器初始值需要共同的移位寄存器初始值IVIV对于不同的消息，对于不同的消息，IVIV必须唯一必须唯一误差传递：一个单元损坏影响多个单元误差传递：一个单元损坏影响多个单元输出反馈输出反馈OFB OFB:OFB:分组密码分组密码流密码流密码假定：假
17、定：SiSi 为移位寄存器为移位寄存器,传输单位为传输单位为jbitbit 加密加密:C Ci i=P=Pi i(E EK K(S(Si i)的高的高j j位位)S Si i+1+1=(S=(Si ij)|j)|(E EK K(S(Si i)的高的高j j位位)解密解密:P Pi i=C=Ci i(E EK K(S(Si i)的高的高j j位位)S Si i+1+1=(S=(Si ij)|j)|(E EK K(S(Si i)的高的高j j位位)输出反馈输出反馈OFB加密加密Ci=Pi(EK(Si)的高的高j位位);Si+1=(Sij)|(EK(Si)的高的高j位位)输出反馈输出反馈OFB解密解
18、密Pi=Ci(EK(Si)的高的高j位位);Si+1=(Sij)|(EK(Si)的高的高j位位)0FB的特点的特点分组密码分组密码流密码流密码没有已知的并行实现算法没有已知的并行实现算法隐藏了明文模式隐藏了明文模式需要共同的移位寄存器初始值需要共同的移位寄存器初始值IVIV对于不同的消息，对于不同的消息，IVIV必须唯一必须唯一误差传递：一个单元损坏只影响对应单元误差传递：一个单元损坏只影响对应单元对明文的主动攻击是可能的对明文的主动攻击是可能的 信息块可被替换、重排、删除、重放信息块可被替换、重排、删除、重放安全性较安全性较CFBCFB差差多重多重DES两重两重DES三重三重DESDES的安
19、全性的安全性 F F函数函数(S-Box)(S-Box)设计原理未知设计原理未知 密钥长度的争论密钥长度的争论 DES DES的破译的破译 弱密钥与半弱密钥弱密钥与半弱密钥DES密钥长度密钥长度关于关于DES算法的另一个最有争议的问题就是担心实际算法的另一个最有争议的问题就是担心实际56比特的密钥长度不足以抵御穷举式攻击，因为密钥量只比特的密钥长度不足以抵御穷举式攻击，因为密钥量只有有 个个 早在早在1977年，年，Diffie和和Hellman已建议制造一个每秒能测已建议制造一个每秒能测试试100100万个密钥的万个密钥的VLSI芯片。每秒测试芯片。每秒测试100100万个密钥的万个密钥的机
20、器大约需要一天就可以搜索整个密钥空间。他们估计机器大约需要一天就可以搜索整个密钥空间。他们估计制造这样的机器大约需要制造这样的机器大约需要2000万万美元美元1756102DES密钥长度密钥长度在在CRYPTO93上，上，Session和和Wiener给出了一个非常详细给出了一个非常详细的密钥搜索机器的设计方案，这个机器基于并行运算的密的密钥搜索机器的设计方案，这个机器基于并行运算的密钥搜索芯片，所以钥搜索芯片，所以16次加密能同时完成。花费次加密能同时完成。花费10万万美元，美元，平均用平均用1.5天左右就可找到天左右就可找到DES密钥密钥美国克罗拉多洲的程序员美国克罗拉多洲的程序员Vers
21、er从从1997年年2 2月月18日起，用了日起，用了96天时间，在天时间，在Internet上数万名志愿者的协同工作下，成上数万名志愿者的协同工作下，成功地找到了功地找到了DES的密钥，赢得了悬赏的的密钥，赢得了悬赏的1万美元万美元DES密钥长度密钥长度19981998年年7 7月电子前沿基金会（月电子前沿基金会（EFFEFF）使用一台）使用一台2525万美圆的电万美圆的电脑在脑在5656小时内破译了小时内破译了5656比特密钥的比特密钥的DESDES19991999年年1 1月月RSARSA数据安全会议期间，电子前沿基金会用数据安全会议期间，电子前沿基金会用2222小小时时1515分钟就宣
22、告破解了一个分钟就宣告破解了一个DESDES的密钥的密钥破译破译DES19901990年，以色列密码学家年，以色列密码学家Eli BihamEli Biham和和Adi ShamirAdi Shamir提出了提出了差分密码分析法，可对差分密码分析法，可对DESDES进行选择明文攻击进行选择明文攻击线性密码分析比差分密码分析更有效线性密码分析比差分密码分析更有效 弱密钥与半弱密钥弱密钥与半弱密钥弱密钥弱密钥:E EK K E EK K=I=I ，DESDES存在存在4 4个弱密钥个弱密钥 即：即：半弱密钥半弱密钥:E EK1K1=E=EK2K2 ，至少有，至少有1212个半弱密钥个半弱密钥 即：
23、即：()kkpE E P12()()kkC E PE P其它常规分组加密算法其它常规分组加密算法Triple DES IDEA RC5 RC6 AES其他一些较实用的算法，如其他一些较实用的算法，如Blowfish，CAST，以及，以及RC2等等使用常规加密进行保密通信使用常规加密进行保密通信易受攻击的位置易受攻击的位置电话公司电话公司市话局市话局接线盒接线盒链路加密和端到端加密链路加密和端到端加密存储转发通信的加密覆盖范围存储转发通信的加密覆盖范围各种加密策略包含的内容各种加密策略包含的内容链路层加密链路层加密对于在两个网络节点间的某一次通信链路对于在两个网络节点间的某一次通信链路,链路加密
24、能链路加密能为网上传输的数据提供安全保证为网上传输的数据提供安全保证所有消息在被传输之前进行加密所有消息在被传输之前进行加密,在每一个节点对接收在每一个节点对接收到的消息进行解密到的消息进行解密,然后先使用下一个链路的密钥对消然后先使用下一个链路的密钥对消息进行加密息进行加密,再进行传输再进行传输链路层加密的优点链路层加密的优点由于在每一个中间传输节点消息均被解密后重新进行由于在每一个中间传输节点消息均被解密后重新进行加密加密,因此因此,包括路由信息在内的链路上的所有数据均包括路由信息在内的链路上的所有数据均以密文形式出现。这样以密文形式出现。这样,链路加密就掩盖了被传输消息链路加密就掩盖了被
25、传输消息的源点与终点的源点与终点由于填充技术的使用以及填充字符在不需要传输数据由于填充技术的使用以及填充字符在不需要传输数据的情况下就可以进行加密的情况下就可以进行加密,这使得消息的频率和长度特这使得消息的频率和长度特性得以掩盖性得以掩盖,从而可以防止对通信业务进行分析从而可以防止对通信业务进行分析链路层加密的缺点链路层加密的缺点链路加密通常用在点对点的同步或异步线路上链路加密通常用在点对点的同步或异步线路上,它要求先对在链路两端它要求先对在链路两端的加密设备进行同步的加密设备进行同步,然后使用一种链模式对链路上传输的数据进行加然后使用一种链模式对链路上传输的数据进行加密。这就给网络的性能和可
26、管理性带来了副作用密。这就给网络的性能和可管理性带来了副作用在一个网络节点在一个网络节点,链路加密仅在通信链路上提供安全性链路加密仅在通信链路上提供安全性,消息以明文形消息以明文形式存在式存在,因此所有节点在物理上必须是安全的因此所有节点在物理上必须是安全的,否则就会泄漏明文内容否则就会泄漏明文内容在传统的加密算法中在传统的加密算法中,用于解密消息的密钥与用于加密的密钥是相同的用于解密消息的密钥与用于加密的密钥是相同的,该密钥必须被秘密保存该密钥必须被秘密保存,并按一定规则进行变化。这样并按一定规则进行变化。这样,密钥分配在链密钥分配在链路加密系统中就成了一个问题路加密系统中就成了一个问题,因
27、为每一个节点必须存储与其相连接的因为每一个节点必须存储与其相连接的所有链路的加密密钥所有链路的加密密钥,这就需要对密钥进行物理传送或者建立专用网络这就需要对密钥进行物理传送或者建立专用网络设施。而网络节点地理分布的广阔性使得这一过程变得复杂设施。而网络节点地理分布的广阔性使得这一过程变得复杂,同时增加同时增加了密钥连续分配时的费用了密钥连续分配时的费用节点加密节点加密节点在操作方式上与链路加密是类似的节点在操作方式上与链路加密是类似的:两者均在通信链路上为两者均在通信链路上为传输的消息提供安全性传输的消息提供安全性;都在中间节点先对消息进行解密都在中间节点先对消息进行解密,然后然后进行加密。因
28、为要对所有传输的数据进行加密进行加密。因为要对所有传输的数据进行加密,所以加密过程对所以加密过程对用户是透明的用户是透明的然而然而,与链路加密不同与链路加密不同,节点加密不允许消息在网络节点以明文节点加密不允许消息在网络节点以明文形式存在形式存在,它先把收到的消息进行解密它先把收到的消息进行解密,然后采用另一个不同的然后采用另一个不同的密钥进行加密密钥进行加密,这一过程是在节点上的一个安全模块中进行这一过程是在节点上的一个安全模块中进行节点加密要求报头和路由信息以明文形式传输节点加密要求报头和路由信息以明文形式传输,以便中间节点能以便中间节点能得到如何处理消息的信息。因此这种方法对于防止攻击者
29、分析得到如何处理消息的信息。因此这种方法对于防止攻击者分析通信业务是脆弱的通信业务是脆弱的端到端加密端到端加密端到端加密允许数据在从源点到终点的传输过程端到端加密允许数据在从源点到终点的传输过程中始终以密文形式存在中始终以密文形式存在采用端到端加密采用端到端加密(又称脱线加密或包加密又称脱线加密或包加密),),消息在消息在被传输时到达终点之前不进行解密被传输时到达终点之前不进行解密,因为消息在整因为消息在整个传输过程中均受到保护个传输过程中均受到保护,所以即使有节点被损坏所以即使有节点被损坏也不会使消息泄露也不会使消息泄露端到端加密的优点端到端加密的优点端到端加密系统的价格便宜些端到端加密系统
30、的价格便宜些,与链路加密和节点加密相与链路加密和节点加密相比更可靠比更可靠,更容易设计、实现和维护更容易设计、实现和维护端到端加密避免了其它加密系统所固有的同步问题端到端加密避免了其它加密系统所固有的同步问题,因为因为每个报文包均是独立被加密的每个报文包均是独立被加密的,所以一个报文包所发生的所以一个报文包所发生的传输错误不会影响后续的报文包传输错误不会影响后续的报文包从用户对安全需求的直觉上讲从用户对安全需求的直觉上讲,端到端加密更自然些。单端到端加密更自然些。单个用户可能会选用这种加密方法个用户可能会选用这种加密方法,以便不影响网络上的其以便不影响网络上的其他用户他用户,此方法只需要源和目
31、的节点是保密的即可此方法只需要源和目的节点是保密的即可端到端加密的缺点端到端加密的缺点通常不允许对消息的目的地址进行加密通常不允许对消息的目的地址进行加密,这是因为每一个这是因为每一个消息所经过的节点都要用此地址来确定如何传输消息消息所经过的节点都要用此地址来确定如何传输消息由于这种加密方法不能掩盖被传输消息的源点与终点由于这种加密方法不能掩盖被传输消息的源点与终点,因因此它对于防止攻击者分析通信业务是脆弱的此它对于防止攻击者分析通信业务是脆弱的目目 录录1.数据加密标准数据加密标准2.公开密钥算法公开密钥算法公开密钥算法公开密钥算法 公开密钥算法是非对称算法，即密钥分为公钥和私钥，公开密钥算
32、法是非对称算法，即密钥分为公钥和私钥，因此称双密钥体制因此称双密钥体制 双钥体制的公钥可以公开，因此也称公钥算法双钥体制的公钥可以公开，因此也称公钥算法 公钥算法的出现，给密码的发展开辟了新的方向。公钥公钥算法的出现，给密码的发展开辟了新的方向。公钥算法虽然已经历了算法虽然已经历了2020多年的发展，但仍具有强劲的发展势多年的发展，但仍具有强劲的发展势头，在鉴别系统和密钥交换等安全技术领域起着关键的作头，在鉴别系统和密钥交换等安全技术领域起着关键的作用用公开密钥算法的提出公开密钥算法的提出公钥密码学是公钥密码学是1976年由年由Diffie和和Hellman在其在其“密码学新方密码学新方向向”
33、一文中提出的，见文献：一文中提出的，见文献：W.Diffie and M.E.Hellman,New Directrions in Cryptography，IEEE Transaction on Information Theory,V.IT-22.No.6,Nov 1976,PP.644-654公开密钥算法的提出公开密钥算法的提出RSA公钥算法是由公钥算法是由Rivest,Shamir和和Adleman在在1978年提出年提出来的来的参见参见Communitions of the ACM.Vol.21.No.2.Feb.1978,PP.120-126该算法的数学基础是初等数论中的该算法的数
34、学基础是初等数论中的Euler（欧拉（欧拉)定理，并定理，并建立在大整数因子的困难性之上建立在大整数因子的困难性之上加密与解密由不同的密钥完成加密与解密由不同的密钥完成 加密：加密：解密：解密：知道加密算法，从加密密钥得到解密密钥在计算上是不可知道加密算法，从加密密钥得到解密密钥在计算上是不可行的行的两个密钥中任何一个都可以作为加密而另一个用作解密两个密钥中任何一个都可以作为加密而另一个用作解密（不是必须的）（不是必须的）公开密钥算法的基本要求公开密钥算法的基本要求:()KUXY YEX:()()KRKRKUYX XDYDEX基于公开密钥的加密过程基于公开密钥的加密过程用公钥密码实现保密用公钥
35、密码实现保密 用户拥有自己的密钥对用户拥有自己的密钥对(KU,KR)公钥公钥 KU公开，私钥公开，私钥KR保密保密 :()bKUAB YEX:()()bbbKRKRKUB DYDEXX基于公开密钥的鉴别过程基于公开密钥的鉴别过程用公钥密码实现鉴别用公钥密码实现鉴别 条件：两个密钥中任何一个都可以用作加密而另外一个条件：两个密钥中任何一个都可以用作加密而另外一个用作解密用作解密鉴别：鉴别：鉴别保密鉴别保密:():()()aabaKRKUKUKRAALL YEXALL DYDEXX:():()baabKUKRKUKRAB ZEDXB EDZX公开密钥算法公开密钥算法公钥算法的种类很多，具有代表性的
36、三种密码：公钥算法的种类很多，具有代表性的三种密码：基于整数分解难题（基于整数分解难题（IFPIFP）的算法体制）的算法体制 基于离散对数难题（基于离散对数难题（DLPDLP）算法体制）算法体制基于椭圆曲线离散对数难题（基于椭圆曲线离散对数难题（ECDLPECDLP）的算法体制）的算法体制Diffie-Hellman密钥交换算法密钥交换算法单向陷门函数函数单向陷门函数函数 满足下列条件的函数满足下列条件的函数f f：(1)给定给定x，计算，计算y=f(x)是容易的是容易的 (2)给定给定y,计算计算x使使y=f(x)是困难的是困难的 (3)存在存在z，已知，已知z 时时,对给定的任何对给定的任
37、何y，若相应的，若相应的x存存 在，则计算在，则计算x使使y=f(x)是容易的是容易的所谓计算所谓计算x=x=f-1(Y)(Y)困难是指计算上相当复杂，已无实际意困难是指计算上相当复杂，已无实际意义义单向陷门函数说明单向陷门函数说明仅满足仅满足(1)、(2)两条的称为单向函数；第两条的称为单向函数；第(3)条称为陷门性，条称为陷门性，z 称为陷门信息称为陷门信息当用陷门函数当用陷门函数f作为加密函数时，可将作为加密函数时，可将f公开，这相当于公公开，这相当于公开加密密钥，此时加密密钥便称为公开钥，记为开加密密钥，此时加密密钥便称为公开钥，记为Pkf函数的设计者将函数的设计者将z保密，用作解密密
38、钥，此时保密，用作解密密钥，此时z称为秘密钥称为秘密钥匙，记为匙，记为Sk。由于设计者拥有。由于设计者拥有Sk，他自然可以解出，他自然可以解出x=f-1(y)单向陷门函数的第单向陷门函数的第(2)条性质表明窃听者由截获的密文条性质表明窃听者由截获的密文y=f(x)推测推测x是不可行的是不可行的Diffie-Hellman密钥交换算法密钥交换算法Diffie和和Hellman在其里程碑意义的文章中，虽然给出了密在其里程碑意义的文章中，虽然给出了密码的思想，但是没有给出真正意义上的公钥密码实例，也码的思想，但是没有给出真正意义上的公钥密码实例，也既没能找出一个真正带既没能找出一个真正带陷门陷门的单
39、向函数的单向函数然而，他们给出单向函数的实例，并且基于此提出然而，他们给出单向函数的实例，并且基于此提出Diffie-Hellman密钥交换算法密钥交换算法Diffie-Hellman密钥交换算法的原理密钥交换算法的原理基于有限域中计算离散对数的困难性问题之上：设基于有限域中计算离散对数的困难性问题之上：设F为有为有限域，限域，gF是是F的乘法群的乘法群 F*=F0=，并且对任意正整，并且对任意正整数数x，计算，计算gx是容易的；但是已知是容易的；但是已知g和和y求求x使使y=gx，是计算，是计算上几乎不可能的上几乎不可能的这个问题称为有限域这个问题称为有限域F上的离散对数问题。公钥密码学中上
40、的离散对数问题。公钥密码学中使用最广泛的有限域为素域使用最广泛的有限域为素域FPDiffie-Hellman密钥交换协议描述密钥交换协议描述Alice和和Bob协商好一个大素数协商好一个大素数p，和大的整数，和大的整数g，1gp，g最好是最好是FP中的本原元，即中的本原元，即FP*p和和g无须保密，可为网络上的所有用户共享无须保密，可为网络上的所有用户共享Diffie-Hellman密钥交换协议描述密钥交换协议描述当当Alice和和Bob要进行保密通信时，他们可以按如下步骤来做：要进行保密通信时，他们可以按如下步骤来做：(1)Alice选取大的随机数选取大的随机数x，并计算，并计算 X=gx(
41、mod P)(2)Bob选取大的随机数选取大的随机数x，并计算，并计算 X =gx (mod P)(3)Alice将将X传送给传送给Bob；Bob将将X 传送给传送给Alice (4)Alice计算计算K=(X )X(mod P);Bob计算计算K =（X)X (mod P),易见，易见，K=K =g xx (mod P)由由(4)知，知，Alice和和Bob已获得了相同的秘密值已获得了相同的秘密值K双方以双方以K作为加解密钥以传统对称密钥算法进行保密通信作为加解密钥以传统对称密钥算法进行保密通信RSA 算法算法Euler 函数函数 所有模所有模m和和r同余的整数组成剩余类同余的整数组成剩余类
42、r 剩余类剩余类r中的每一个数和中的每一个数和m互素的充要条件是互素的充要条件是r和和m互素互素 和和m互素的同余类数目用互素的同余类数目用(m)表示，称表示，称m的的Euler函数函数 当当m是素数时，小于是素数时，小于m的所有整数均与的所有整数均与m互素，因此互素，因此(m)=m-1对对n=pq,p和和q 是素数，是素数，(n)=(p)(q)=(p-1)(q-1)Euler 函数函数举例举例 设设p=3,q=5,那么那么 （15）=（3-1）*（5-1）=8 这这8个模个模15的剩余类是的剩余类是：1，2，4，7，8，11，13，14 RSA算法的实现算法的实现 实现的步骤如下：实现的步骤
43、如下：Bob为实现者为实现者 (1)Bob寻找出两个大素数寻找出两个大素数p和和q (2)Bob计算出计算出n=pq 和和(n)=(p-1)(q-1)(3)Bob选择一个随机数选择一个随机数e(0e(n)，满足，满足(e,(n)=1 (4)Bob使用辗转相除法计算使用辗转相除法计算d=e-1(mod(n)(5)Bob在目录中公开在目录中公开n和和e作为公钥作为公钥密码分析者攻击密码分析者攻击RSA体制的关键点在于如何分解体制的关键点在于如何分解n。若分。若分解成功使解成功使n=pq，则可以算出，则可以算出(n)（p-1)(q-1)，然后由公，然后由公开的开的e，解出秘密的，解出秘密的dRSA算
44、法编制算法编制 参数参数T=NT=N；私钥私钥SK=DSK=D；公钥公钥PK=EPK=E；设：明文设：明文M M，密文，密文C C，那么：，那么：用公钥作业：用公钥作业：M ME E mod N=C mod N=C 用私钥作业：用私钥作业：M MD D mod N=M mod N=MRSA算法举例算法举例设设 p=7,q=17,n=7p=7,q=17,n=7*17=119;17=119;参数参数T=n=119;T=n=119;(n)=(7-1)(17-1)=96;(n)=(7-1)(17-1)=96;选择选择e=5,gcde=5,gcd(5,96)=1;(5,96)=1;公钥公钥pkpk=5;
45、=5;计算计算d,(dd,(d*e)mod 96=1;d=77;e)mod 96=1;d=77;私钥私钥sksk=77;=77;设设:明文明文m=19m=19 加密：（加密：（1919）5 5 mod 119=66mod 119=66 脱密：（脱密：（6666）7777 mod 119=19mod 119=19RSA算法的安全性分析算法的安全性分析密码分析者攻击密码分析者攻击RSA体制的关键点在于如何分解体制的关键点在于如何分解n若分解成功使若分解成功使n=pq，则可以算出，则可以算出(n)（p-1)(q-1)，然，然后由公开的后由公开的e，解出秘密的，解出秘密的d若使若使RSA安全，安全，p
46、与与q必为足够大的素数，使分析者没有必为足够大的素数，使分析者没有办法在多项式时间内将办法在多项式时间内将n分解出来分解出来RSA算法的安全性分析算法的安全性分析建议选择建议选择p和和q大约是大约是100位的十进制素数位的十进制素数模模n的长度要求至少是的长度要求至少是512比特比特EDI攻击标准使用的攻击标准使用的RSA算法中规定算法中规定n的长度为的长度为512至至1024比特比特位之间，但必须是位之间，但必须是128的倍数的倍数国际数字签名标准国际数字签名标准ISO/IEC 9796中规定中规定n的长度位的长度位512比特位比特位RSA算法的安全性分析算法的安全性分析 为了抵抗现有的整数
47、分解算法，对为了抵抗现有的整数分解算法，对RSA模模n的素因子的素因子p和和q还有还有如下要求：如下要求：(1)|p-q|很大，通常很大，通常 p和和q的长度相同；的长度相同；(2)p-1 和和q-1分别含有大素因子分别含有大素因子p1和和q1 (3)P1-1和和q1-1分别含有大素因子分别含有大素因子p2和和q2 (4)p+1和和q+1分别含有大素因子分别含有大素因子p3和和q3RSA算法的安全性分析算法的安全性分析为了提高加密速度，通常取为了提高加密速度，通常取e为特定的小整数为特定的小整数如如EDI国际标准中规定国际标准中规定 e2161ISO/IEC9796中甚至允许取中甚至允许取e3这时加密速度一般比解密速度快这时加密速度一般比解密速度快10倍以上倍以上
