1、第二章现代密码学技术n本章提示q2.1分组加密技术q2.2公钥加密技术2.1 分组加密技术n本节提示q2.2.1基本概念q2.2.2标准算法的介绍nDES算法n国际数据加密算法（IDEA）nAES算法q2.2.3分组密码的分析方法q2.2.4分组密码的工作模式 2.2.1基本概念n密码学中常见的有两种体制:q对称密码体制(单钥密码体制)如果一个加密系统的加密密钥和解密密钥相同，或者虽然不相同，但是由其中的任意一个可以很容易地推导出另一个，即密钥是双方共享的,则该系统所采用的就是对称密码体制。q非对称密码体制(公钥密码体制)n分组密码是指将处理的明文按照固定长度进行分组，加解密的处理在固定长度密
2、钥的控制下，以一个分组为单位独立进行，得出一个固定长度的对应于明文分组的结果。属于对称密码体制的范畴。基本概念（续）n在分组密码的设计中用代替、置换手段实现扩散和混淆功能。n混淆 指加密算法的密文与明文及密钥关系十分复杂，无法从数学上描述，或从统计上去分析。n扩散 指明文中的任一位以及密钥中的任一位，对全体密文位有影响。经由此种扩散作用，可以隐藏许多明文在统计上的特性，增加密码的安全 2.2.2标准算法的介绍nDES算法 n国际数据加密算法（IDEA）nAES算法 DES加密算法的背景l发明人 美国IBM公司W.Tuchman 和 C.Meyer 1971-1972年研制成功。l基础 1967
3、年美国Horst Feistel提出的理论l产生 美国国家标准局（NBS)1973年5月到1974年8月两次发布通告，公开征求用于电子计算机的加密算法。经评选从一大批算法中采纳了IBM的LUCIFER方案。l标准化 DES算法1975年3月公开发表，1977年1月15日由美国国家标准局颁布为数据加密标准（Data Encryption Standard），于1977年7月15日生效。DES加密算法的背景n美国国家安全局（NSA,National Security Agency)参与了美国国家标准局制定数据加密标准的过程。NBS接受了NSA的某些建议，对算法做了修改，并将密钥长度从LUCIFER
4、方案中的128位压缩到56位。n1979年，美国银行协会批准使用DES。n1980年，DES成为美国标准化协会(ANSI)标准。n1984年2月，ISO成立的数据加密技术委员会(SC20)在DES基础上制定数据加密的国际标准工作。实现的设计原则n 软件实现的要求：使用子块和简单的运算。密码运算在子块上进行，要求子块的长度能自然地适应软件编程，如8、16、32比特等。应尽量避免按比特置换，在子块上所进行的密码运算尽量采用易于软件实现的运算。最好是用处理器的基本运算，如加法、乘法、移位等。n硬件实现的要求：加密和解密的相似性，即加密和解密过程的不同应仅仅在密钥使用方式上，以便采用同样的器件来实现加
5、密和解密，以节省费用和体积。尽量采用标准的组件结构，以便能适应于在超大规模集成电路中实现。简化的DESnSimplified DES方案，简称S-DES方案。n加密算法涉及五个函数：(1)初始置换IP(initial permutation)(2)复合函数fk1，它是由密钥K确定的，具有置换和替代的运算。(3)转换函数SW (4)复合函数fk2 (5)初始置换IP的逆置换IP-1 加密算法的数学表示 nIP-1*fk2*SW*fk1*IP 也可写为 密文=IP-1（fk2(SW(fk1(IP(明文)其中 K1=P8(移位(P10(密钥K)K2=P8(移位(移位(P10(密钥K)n解密算法的数学
6、表示：明文=IP-1（fk1(SW(fk2(IP(密文)对S-DES的深入描述（1）S-DES的密钥生成：设10bit的密钥为（k1,k2,k3,k4,k5,k6,k7,k8,k9,k10)置换P10是这样定义的P10(k1,k2,k10)=(k3,k5,k2,k7,k4,k10,k1,k9,k8,k6)相当于 P10=LS-1为循环左移，在这里实现左移1位。LS-2为循环左移，在这里实现左移2位。P8=按照上述条件,若K选为(1010000010),产生的两个子密钥分别为K1=(1 0 1 0 0 1 0 0),K2=(0 1 0 0 0 0 1 1)68911047253109876543
7、2191058473687654321 S-DES的密钥生成的密钥生成n 10-bit密钥密钥P10LS-1LS-1LS-2LS-2P8P8K18K255585(2)S-DES的加密运算的加密运算:初始置换用初始置换用IP函数函数:IP=1 2 3 4 5 6 7 8 2 6 3 1 4 8 5 7末端算法的置换为末端算法的置换为IP的逆置换的逆置换:IP-1=1 2 3 4 5 6 7 8 4 1 3 5 7 2 8 6易见易见IP-1(IP(X)=X 函数函数fk，是加，是加 密方案中的最重要部分，它可表示为：密方案中的最重要部分，它可表示为：fk(L,R)=(L F(R,S K),R)其
8、中其中L，R为为8位输入位输入,左右各为左右各为4位位,F为从为从4位集到位集到4位集位集的一个映射的一个映射,并不要求是并不要求是1-1的。的。SK为子密钥。为子密钥。对对 映射映射F来说：来说：首先输入是一个首先输入是一个4-位数（位数（n1,n2,n3,n4），第一步运算是），第一步运算是扩张扩张/置换（置换（E/P）运算：）运算：E/P 4 1 2 3 2 3 4 1 事实上，它的直观表现形式为：事实上，它的直观表现形式为：n4 n1 n2 n3 n2 n3 n4 n1 8-bit子密钥：子密钥：K1=(k11,k12,k13,k14,k15,k16,k17,k18),然后然后与与E/
9、P的结果作异或运算得：的结果作异或运算得：n4+k11 n1+k12 n2+k13n3+k14 n2+k15 n3+k16 n4+k17n1+k18把它们重记为把它们重记为8位位：P0,0 P0,1P0,2 P0,3 P1,0 P1,1P1,2P1,3上述第一行输入进上述第一行输入进S-盒盒S0，产生，产生2-位的输出；第二行位的输出；第二行的的4位输入进位输入进S盒盒S1，产生，产生2-位的输出。两个位的输出。两个S盒按盒按如下定义：如下定义：2313312001232301321032100S3012010331023210321032101S S盒按下述规则运算：盒按下述规则运算：将第将
10、第1和第和第4的输入比特做为的输入比特做为2-bit数，指示为数，指示为S盒的一个行；盒的一个行；将第将第2和第和第3的输入比特做为的输入比特做为S盒的一盒的一 个列。如此确定为个列。如此确定为S盒盒矩阵的（矩阵的（i,j）数。）数。例如：（例如：（P0,0,P0,3）=(00),并且并且(P0,1,P0,2)=(1 0)确定了确定了S0中的第中的第0行行2列（列（0，2）的系数为）的系数为3，记为（，记为（1 1）输）输出。出。由由S0,S1输出输出4-bit经置换经置换 P4 2 4 3 1它的输出就是它的输出就是F函数的输出。函数的输出。SW函数为左四位和右四位进行交换。函数为左四位和右
11、四位进行交换。DES算法描述n为二进制编码数据设计的，可以对计算机数据进行密码保护的数学运算。nDES使用56位密钥对64位的数据块进行加密，并对64位的数据块进行16轮编码。在每轮编码时，一个48位的“每轮”密钥值由56位的“种子”密钥得出来。nDES算法的入口参数有三个：Key、Data和Mode。qKey为8个字节共64位，是DES算法的工作密钥；qData也为8个字节64位，是要被加密或被解密的数据；qMode为DES的工作方式，有两种：加密或解密n64位明文变换到64位密文，密钥64位，实际可用密钥长度为56位。DES算法框图 DES算法描述（续）n初始换位的功能是把输入的64位数据
12、块按位重新组合，并把输出分为L0、R0两部分，每部分各长32位，其置换规则见下表：58 50 42 34 26 18 10 2 60 52 44 36 28 20 12 4 62 54 46 38 30 22 14 6 64 56 48 40 32 24 16 8 57 49 41 33 25 17 9 1 59 51 43 35 27 19 11 3 61 53 45 37 29 21 13 5 63 55 47 39 31 23 15 7n例：设置换前的输入值为D1D2D3.D64，则经过初始置换后的结果为：L0=D58D50.D8；R0=D57D49.D7。DES算法描述（续）n逆置换正
13、好是初始置的逆运算。【例】第1位经过初始置换后，处于第40位，而通过逆置 换，又将第40位换回到第1位，其逆置换规则如下表所示：40 8 48 16 56 24 64 32 39 7 47 15 55 23 63 31 38 6 46 14 54 22 62 30 37 5 45 13 53 21 61 29 36 4 44 12 52 20 60 28 35 3 43 11 51 19 59 27 34 2 42 10 50 18 58 26 33 1 41 9 49 17 57 25DES算法的一次迭代过程图DES算法描述（续）n扩展置换为:32 1 2 3 4 5 4 5 6 7 8 9
14、 8 9 10 11 12 13 12 13 14 15 16 17 16 17 18 19 20 21 20 21 22 23 24 25 24 25 26 27 28 29 28 29 30 31 32 1nP-盒置换为：16 7 20 21 29 12 28 17 1 15 23 26 5 18 31 10 2 8 24 14 32 27 3 9 19 13 30 6 22 11 4 25n在变换中用到的S1,S2.S8为选择函数，俗称为S-盒，是DES算法的核心。其功能是把6bit数据变为4bit数据。S1:14 4 13 1 2 15 11 8 3 10 6 12 5 9 0 7 0
15、 15 7 4 14 2 13 1 10 6 12 11 9 5 3 8 4 1 14 8 13 6 2 11 15 12 9 7 3 10 5 015 12 8 2 4 9 1 7 5 11 3 14 10 0 6 13 n在S1中，共有4行数据，命名为0，1、2、3行；每行有16列，命名为0、1、2、3，.，14、15列。现设输入为：DD1D2D3D4D5D6 令：列D2D3D4D5 行D1D6然后在S1表中查得对应的数，以4位二进制表示，此即为选择函数S1的输出。1 0 1 1 0 0 102 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 150 14 4 13
16、1 2 15 11 8 3 10 6 12 5 9 0 71 0 15 7 4 14 2 13 1 10 6 12 11 9 5 3 82 4 1 14 8 13 6 2 11 15 12 9 7 3 10 5 03 15 12 8 2 4 9 1 7 5 11 3 14 10 0 6 130 0 1 0输出4位使用选择函数S1的例子输入6位S1密钥Ki(48bit)的生成算法 DES的破解n DES的实际密钥长度为56-bit，就目前计算机的计算机能力而言，DES不能抵抗对密钥的穷举搜索攻击。n 1997年1月28日，RSA数据安全公司在RSA安全年会上悬赏10000美金破解DES，克罗拉多
17、州的程序员Verser在Inrernet上数万名志愿者的协作下用96天的时间找到了密钥长度为40-bit和48-bit的DES密钥。n 1998年7月电子边境基金会（EFF）使用一台价值25万美元的计算机在56小时之内破译了56-bit的DES。n 1999年1月电子边境基金会（EFF）通过互联网上的10万台计算机合作，仅用22小时15分就破解了56-bit的ES。DES算法的公开性与脆弱性nDES的两个主要弱点：q密钥容量：56位不太可能提供足够的安全性n 不过这些破译的前提是，破译者能识别出破译的结果确实是明文，也不过这些破译的前提是，破译者能识别出破译的结果确实是明文，也即破译的结果必须
18、容易辩认。如果明文加密之前经过压缩等处理，辩认即破译的结果必须容易辩认。如果明文加密之前经过压缩等处理，辩认工作就比较困难。工作就比较困难。qS盒：可能隐含有陷井（Hidden trapdoors）nDES的半公开性：S盒的设计原理至今未公布国际数据加密算法（IDEA）nIDEA（International Data Encryption Standard）由瑞士联邦理工学院的Xuejia Lai和James Massey于 1990年提出，分组长度为64-bit，密钥长度为128-bit。能抵抗差分密码分析，目前还没有发现明显的安全漏洞，应用十分广泛。著名的电子邮件安全软件PGP就采用了ID
19、EA进行数据加密。IDEA的混淆特性nIDEA的混淆特性是经由混合下述三种操作而成的：q以比特为单位的异或运算，用 表示。q定义在模 （mod65536）的模加法运算，其操作数都可以表示成16位整数，用表示这个操作。q定义在模 1（mod65537）的模乘法运算 。162162IDEA的混淆特性（续）n由于上面3个操作，基于以下的“非兼容性 “（Incompatible），当应用在IDEA时，可以充分发挥出混淆的特性。q三种中的任意两个，都不满足“分配律”，例如运算及，任意a，b，c ，则有：a(b c)（ab）（ac）q3个操作中的任意2个，都无法满足“结合律”。例如运算及，任意a，b，c
20、，a(b c)（ab）（ac）n 因此在IDEA的设计中，使用了这三种操作混合组合来打乱数据。攻击者无法用化简的方式来分析密文与明文及密钥之间的关系。162F162FIDEA的扩散特性nIDEA的扩散特性是建立在乘法/加法（MA）的基本结构上。该结构一共有4个16位的输入，两个16位的输出。其中的两个输入来源于明文，另两个输入是子密钥，源于128位加密密钥。Lai经过分析验证，数据经过8轮的MA处理，可以得到完整的扩散特性。图2.16 IDEA加密解密框架 第1 轮循环 P1 P2 P3 P4 16 16 第2 轮循环 W11 W12 W13 W14 16 W21 W22 W23 W24 第8
21、 轮循环 W71 W72 W73 W74 16 W81 W82 W83 W84 输出变换 16 C1 C2 C3 C4 Z1 Z6 Z7 Z12 Z43 Z48 Z49 Z52 加密子密钥产生器 Z1 Z52 解密子密钥产生器 U1 U52 第1 轮循环 C1 C2 C3 C4 16 第2 轮循环 V11 V12 V13 V14 V21 V22 V23 V24 第8 轮循环 V71 V72 V73 V74 V81 V82 V83 V84 输出变换 P1 P2 P3 P4 U1 U6 U7 U12 U43 U48 U49 U52 64 位明文P 64 位密文C 64 位密文C 64 位明文P 1
22、6 128 位密钥K MA基本结构n在IDEA中，扩散由被称为乘积/相加(MA)结构的算法基本构件提供。这个结构以两个从明文得到的16bit的数值和两个从密钥导出的子密钥作为输入并产生两个16bit的输出。已证明只需要使用4次这个结构就可以实现完全的扩散。F1F2G1G2Z5Z6子密钥（16位）明文输入（16位）明文输入（16位）子密钥（16位）输出（16位）输出（16位）（i）（i）IDEA算法描述nIDEA是由8轮相似的运算和随后的一个输出变换组成 n64位的明文分组在每一轮中都是被分成4份，每份从16位为一单元来处理 n每一轮中6个子密钥8输出变换4个子密钥52个子密钥 每一轮的运算又分
23、成两部分：每一轮的运算又分成两部分：n第一部分即变换运算。利用加法及乘法运算将4份16位的子明文分组与4个子密钥混合，产生4份16位的输出。这4份输出又两两配对，以逻辑异或将数据混合，产生两份16位的输出。这两份输出，连同另外的两个子密钥成为第二部分的输入。n第二部分即用以产生扩散特性的MA运算。MA运算生成两份16位输出。MA的输出再与变换运算的输出以异或作用生成4份16位的最后结果。这4份结果即成为下一轮运算的原始输入。子密钥的产生n首先将128位加密密钥以16位为单位分成8组，其中前6组作为第一轮迭代运算的子密钥，后2组用于第二轮迭代运算的前2组子密钥。n然后将128位密钥循环左移25位
24、，再分为8组子密钥，其中前4组用于第二轮迭代运算，后4组用作第三轮迭代运算的前4组子密钥，依此直至产生全部52个子密钥。n这52个子密钥的顺序为：Z1(1)，Z2(1)，Z6(1)；Z1(2)，Z2(2)，Z6(2)；Z1(8)，Z2(8)，Z6(8)；Z1(9)，Z2(9)，Z3(9)，Z4(9)，IDEA的解密 n本质上与加密过程唯一不同的是解密密钥子块Ki(r)是从加密密钥子块Zi(r)按下列方式计算出来的：n其中 表示的模（1）的乘法逆，亦即 ，表示 的模 的加法逆，亦即 =0 。1628,3,2)(,)(),(1)10(4)10(2)10(31)10(1)(4)(3)(2)(1rZZ
25、ZZKKKKrrrrrrrr9,1)(,)(),(1)10(4)10(3)10(21)10(1)(4)(3)(2)(1rZZZZKKKKrrrrrrrr8,2,1),(),()9(6)9(5)(6)(5rZZKKrrrr1Z16211ZZ ZZ162ZZIDEA的设计理念 nIDEA的设计主要考虑是针对16位为单位的处理器。因此无论明文、密钥都是分成16位为一个单元进行处理。nIDEA使用了三种简单的基本操作，因此在执行时可以达到非常快的操作。在33MHz386机器上运行，加密速度可以达到880kb/s。经过特殊设计的VLSI芯片，更可以达到55Mb/s的速度。nIDEA采用三种非常简单的基本
26、操作，混合运算，以达到混淆目的。而相对地，DES采用经过特殊设计的S-盒，而对这些S-盒的分析又不对外公开。相较之下，IDEA的安全性评估，较易被大家接受。nIDEA的整体设计非常规律。MA运算器及变换运算器重复使用在系统上。因此非常适合VLSI超大规模集成电路(Very Large Scale Integrated circuites)实现。2.2.3分组密码的分析方法n解密与密码分析q 解密是加密的逆过程，是指掌握密钥和密码算法的合法人员从密文 恢复出明文的过程。密码分析则是指非法人员对密码的破译，而且 破译以后不会告诉对方。q 共同点 “解密（脱密）”和“密码分析（密码破译）”都是设法将
27、 密文还原成明文。q 不同点 二者的前提是不同的，“解密（脱密）”掌握了密钥和密码体 制，而密码分析（破译）则没有掌握密钥和密码体制分组密码的分析方法(续）n根据攻击者掌握的信息，可将分组密码的攻击分为以下几类：q唯密文攻击：攻击者除了所截获的密文外，没有其他可利用的 信息。q已知明文攻击：攻击者仅知道当前密钥下的一些明密文对。q选择明文攻击：攻击者能获得当前密钥下的一些特定的明文所对应 的密文。q选择密文攻击：攻击者能获得当前密钥下的一些特定的密文所对 应的明文。分组密码的分析方法(续）n一种攻击的复杂度可以分为两部分：数据复杂度和处理复杂度。q数据复杂度是实施该攻击所需输入的数据量。q处理
28、复杂度是处理这些数据所需的计算量。n对某一攻击通常是以这两个方面的某一方面为主要因素，来刻画攻击复杂度。【例如】q穷举攻击的复杂度实际就是考虑处理复杂度；q差分密码分析其复杂度主要是由该攻击所需的明密文对的数量来确定。几种常见的攻击方法1.强力攻击强力攻击可用于任何分组密码，且攻击的复杂度只依赖于分组长度和密钥长度，严格地讲攻击所 需的时间复杂度依赖于分组密码的工作效率（包括加解密速度、密钥扩散速度以及存储空间等）。强力攻击常见的有：穷举密钥搜索攻击、字典攻击、查表攻击和时间-存储权衡攻击等。几种常见的攻击方法（续）2.差分密码分析基本思想通过分析明文对的差值对密文对的差值的影响来恢复某些密钥
29、比特 若给定一个r轮的迭代密码，对已知n长明文对为 和 ，定义其差分为 式中 表示集合中定义的群运算，为 在群中的逆元。密码分析者可随机选择具有固定差分的一对明文（只要求它们符合特定差分条件），然后使用输出密文中的差分，按照不同的概率分配给不同的的密钥。随着分析的密文对越来越多，其中最可能的一个密钥就显现出来了。这就是正确的密钥。XX1XXX1XX几种常见的攻击方法（续）3.线性密码分析本质：一种已知明文攻击方法。基本思想：通过寻找一个给定密码算法的有效的 线性近似表达式来破译密码系统。对已知明文密文和特定密钥，寻求线性表示式 式中，是攻击参数。对所有可能密钥，此表达式以概率 成立。对给定的密
30、码算法，使 极大化。为此对每一盒的输入和输出构造统计线性路线，并最终扩展到整个算法。xdybxadba,2/1LP2/1LP分组密码的工作模式n常用的分组密码工作模式有4种：1.电子密码本即ECB模式2.密码分组连接模式（CBC）模式3.密码反馈模式（CFB）模式4.输出反馈模式（OFB）模式。ECB(Electronic Code Book)DESp1DESDES加密过程DESDESDES解密过程cnc1c2pnp2p2pncnc2p1c1kkkkkkCBC（Cipher Block Chaining）DESDESDESDESDESDES加密过程解密过程kkkkkkp1pnp2pnp2p1c
31、1c1cncnc2c2IVIVCFB（Cipher Feed Back）移位寄存器IV（64-bits）DESk选择丢弃n bits|64-n bitsc1p1移位寄存器64-n bits|n bitsDESk选择丢弃n bits|64-n bitsc2p2移位寄存器64-n bits|n bitsDESk选择丢弃n bits|64-n bitscmpmcm-1DESk选择丢弃n bits|64-n bitsc1p1移位寄存器64-n bits|n bitsDESk选择丢弃n bits|64-n bitsc2p2移位寄存器64-n bits|n bitsDESk选择丢弃n bits|64-n
32、bitscmpmcm-1加密过程解密过程移位寄存器IV（64-bits）n bitsn bitsn bitsn bitsn bitsn bitsn bitsn bitsOFB（Output Feed Back）DESk选择丢弃n bits|64-n bitsc1p1移位寄存器64-n bits|n bitsDESk选择丢弃n bits|64-n bitsc2p2移位寄存器64-n bits|n bitsDESk选择丢弃n bits|64-n bitscmpmom-1DESk选择丢弃n bits|64-n bitsc1p1移位寄存器64-n bits|n bitsDESk选择丢弃n bits|6
33、4-n bitsc2p2移位寄存器64-n bits|n bitsDESk选择丢弃n bits|64-n bitscmpmom-1加密过程解密过程移位寄存器IV（64-bits）移位寄存器IV（64-bits）o1o1n bitsn bitsn bitsn bits2.3公钥加密技术n本节提示 2.3.1 基本概念 2.3.2 RSA公钥密钥算法 2.3.3 ElGamal算法 2.3.4 椭圆曲线算法对称密码体制的缺陷：1）密钥分配问题密钥分配问题 通信双方要进行加密通信，需要通过秘密的安全信道协商加密密钥，而这种安全信道可能很难实现；2）密钥管理问题密钥管理问题 在有多个用户的网络中，任何
34、两个用户之间都需要有共享的秘密钥，当网络中的用户 n 很大时，需要管理的密钥数目是非常大 2/)1(nn。3）没有签名功能：没有签名功能：当主体 A 收到主体 B 的电子文挡（电子数据）时，无法向第三方证明此电子文档确实来源于 B。2.3.1 基本概念n1976年，W.Diffie和M.E.Hellman发表了“密码学的新方向（New Directions in Cryptography)”一文，提出了公钥密码学（Public-key cryptography）的思想，在公钥密码体制（Public-key cryptosystem）中加密密钥和解密密钥是不同的，加密密钥可以公开传播而不会危及密
35、码体制的安全性。n 通信的一方利用某种数学方法可以产生一个密钥对密钥对，一个称为公钥公钥（Public-key)，另外一个称为私钥私钥（Private-key)。该密钥对中的公钥与私钥是不同的，但又是相互对应的，并且由公钥不能推导出对应的私钥。选择某种算法（可以公开）能做到：用公钥加密的数据只有使用与该公钥配对的私钥才能解密。n是密码学几千年历史中最有意义的结果公钥加密方案基本概念（续）n公钥加密算法的核心公钥加密算法的核心单向陷门函数，即从单向陷门函数，即从一个方向求值是容易的。但其逆向计算却很困一个方向求值是容易的。但其逆向计算却很困难，从而在实际上成为不可行。难，从而在实际上成为不可行。
36、n定义定义1.设 是一个函数，如果对任意给定的 ,计算 ,使得 是容易计算的，但对于任意给定的 ，计算 ，使得 是难解的，即求 的逆函数是难解的，则称 是一个单向函数。fxy xfyyx yfx1ff基本概念（续）n定义定义2.设 是一个函数，是与 有关的一个参数。对于任意给定的 ，计算 ，使得 是容易的。如果当不知参数 时，计算 的逆函数是难解的，但当知道参数 时，计算函数 的逆函数是容易的，则称 是一个单向陷门函数，参数 称为陷门。fftxy xfy tffftt公钥的安全性n依赖于足够大的困难性差别n类似与对称算法,穷搜索在理论上是能够破解公钥密码 exhaustive searchex
37、haustive search n但实际上,密钥足够长(512bits)n一般情况下,有一些已知的困难问题(hardhard problem）n要求足够大的密钥长度(512 bits)n导致加密速度比对称算法慢2.3.2 RSA公钥密码算法nRSA是Rivet，Shamir和Adleman于1978年在美国麻省理工学院研制出来的，它是一种比较典型的公开密钥加密算法。n基础 大数分解和素数检测将两个大素数相乘在计算上很容易实现，但将该乘积分解为两个大素数因子的计算量是相当巨大的，以至于在实际计算中是不能实现的。RSA公钥密码算法（续）n算法内容 (1)公钥 选择两个互异的大质数 和 ，使 ，是欧
38、拉函数，选择一个正数 ，使其满足gcd ，则将 作为公钥。(2)私钥 求出正数 使其满足 ，则将 作为私钥。(3)加密变换将明文 作变换,使 ，从而得到密文 。(4)解密变换将密文 作变换,使 ，从而得到明文 。pqpqn 11qpn)(ne 1,1,nneenKp,d 1,mod1nndeqpdKs,MnMMEKCepmodCC nCCDKMdsmodMRSA公钥密码算法（续）n如果A要发送信息M给B，A和B之间用以下方式进行通信：计算密文 发送C给B从A 接收C计算明文 .n一般要求p，q为安全质数，现在商用的安全要求为n的长度不少于1024位。n应用：PEM，PGP)(MEKCBp CD
39、KMBsRSA公钥密码算法（续）n算法的安全性分析算法的安全性分析 1.如果密码分析者能分解 的因子 和 ，他就可以 求出 和解密的密钥 ，从而能破译RSA，因此破 译RSA不可能比因子分解难题更困难。2.如果密码分析者能够不对 进行因子分解而求得，则 可以根据 求得解密密钥 ，从而破译RSA。因为 所以知道 和 就可以容易地求得 和 ，从而成 功分解 ，因此，不对 进行因子分解而直接计算 并不比对 进行因子分解更容易。npq ndn ndemod1d 1nnqpnqpqp42 nnpqnnn nRSA公钥密码算法（续）3.如果密码分析者既不能对n进行因子分解,也不能求 而直接求得解密密钥 ，
40、则他就可以计算 是 的倍数。而且利用 的倍数可以容易地分解出n的因子。因此直接计算解密密钥 并不比对n进行因子分解更容易。n注意问题qp和q的长度相差不能太多.qp-1和q-1都应该包含大的素因子。qp-1和q-1的最大公因子要尽可能小。ndd1,1eded n nRSA 参数选择n需要选择足够大的素数 p,q n通常选择小的加密指数e,且与(N)互素ne 对所有用户可以是相同的 n最初建议使用e=3n现在3太小n常使用 e=216-1=65535 n解密指数比较大RSA举例例子：例子：1.选素数选素数p=47和和q71，得得n=3337,(n)=46703220；2.选择选择e=79，求得私
41、钥求得私钥d=e-1 1019(mod 3220）。）。3.公开公开n=3337和和e=79.4.现要发送明文现要发送明文688，计算：，计算：68879(mod 3337)=15705.收到密文收到密文1570后，用私钥后，用私钥d1019进行解密：进行解密：15701019（mod 3337)=688RSA 安全性安全性 nRSA 安全性基于计算(N)的困难性 n要求分解模N RSA的实现问题的实现问题n需要计算模 300 digits(or 1024+bits)的乘法n计算机不能直接处理这么大的数n（计算速度很慢）n需要考虑其它技术，加速RSA的实现RSA 的快速实现的快速实现n加密很快
42、，指数小n解密比较慢，指数较大n利用中国剩余定理CRT，nCRT 对RSA解密算法生成两个解密方程（利用M=Cd mod R）n即:M1=M mod p=(C mod p)d mod(p-1)n M2=M mod q=(C mod q)d mod(q-1)n解方程 M=M1 mod p n M=M2 mod q n具有唯一解（利用CRT）：n:M=(M2+q-M1)u mod q p+M1n 其中 p.u mod q=1 2.2.3 ElGamal算法算法n该体制是由ElGamal在1985年提出的，其安全性是基于有限域上计算离散对数的困难性。n ElGamal提出了加密模型和认证模型两种体制
43、，加密模型没有被充分应用，而其认证模型是美国数字签名标准（DSS）的基础。2.2.3 ElGamal算法算法n算法内容1.选取大素数 ，是一个本原元，和 公开。2.随机选取整数 计算 是公开的加密密 钥，是保密的解密密钥。3.明文空间为 ，密文 空间为 4.加密变换为：对任意明 文 ，秘密随机选 取一个整数 ，则密文为 其中5.解密变换：对任意密 文 ，明文为p*pZp21,pddpdmodd*pZ*ppZZ*pZmk21pk21,ccc.mod,mod21pmcpckk*21,ppZZcccpccmdmod112ElGamal算法的安全性分析n有限域上的离散对数问题 定义 设 是素数，是一个
44、本原元，已知 和 ，求满足 的唯 一整数 ，称为有限域上的离散 对数问题。n现在要求在ElGamal密码算法的应用中，素数p按十进制表示至少应该有150位数字，并且p-1至少应该有一个大的素因子。ppZpZpnmodn20pn密钥建立n密钥生成：密钥生成：n选取一个大素数p及本原元a mod pn接收者 Bob有一个密秘钥 d n计算 =ad mod p n ElGamal 加密加密n为加密 M n发送者选择随机数k,0=k=p-1 n计算消息密钥 K:nK=k mod p n计算密文对:C=C1,C2 nC1=ak mod p nC2=K.M mod p n发送到接收者nk 需要永久保密 E
45、lGamal 解密解密n首先计算 message key K nK=C1d mod p=ak.d mod p n计算明文:nM=C2.K-1 mod p ElGamal Examplen选择 p=97 及本原根 a=5 nrecipient Bob 选择 秘密钥d=58&计算并发布公钥=558=44 mod 97 nAlice 要加密 M=3 to Bob n首先得到 Bob的公开密钥=44 n选择随机 k=36 计算:K=4436=75 mod 97 n计算密文对:nC1=536=50 mod 97 nC2=75.3 mod 97=31 mod 97 n发送 50,31 to Bob nBo
46、b 恢复 message key K=5058=75 mod 97 nBob 计算 K-1=22 mod 97 nBob 恢复明文 M=31.22=3 mod 97 2.2.4 椭圆曲线算法n1985年Koblitz和Miller提出在密码学中应用椭圆曲线的思想，使其成为构造公开密钥密码系统的一个有利工具。其安全性是基于椭圆曲线上的离散对数计算的困难性。n优点：椭圆曲线上离散对数的计算要比有限域上离散对数的计算更困难。与RSA相比，椭圆曲线密码体制能用较短的密钥达到较强的安全性，这样实现上能节省系统资源。椭圆曲线算法（续）n1.有限域上的椭圆曲线 设 表示一个有限域，是域 上的椭圆曲线，则 是
47、一个点的集合，表示为：其中 表示无穷远点。n在 上定义+运算，是过 的直线与曲线的另一交点关于x轴的对称点，当 时，是 点的切线与曲线的另一交点关于 轴的对称点。这样，构成可换群(Abel群)，O是加法单位元(零元)。KEKEERRQP,QP,QP RPx,E O,/,6423164223312KyxaaaaaaxaxaxyaxyayyxKEO椭圆曲线算法（续）n椭圆曲线离散对数问题（ECDLP）：给定义在 上的椭圆曲线 ，一个 阶的点 和点 ，如果存在1，确定整数1,0 1 n-1,。nRSA是基于因子分解，其算法的核心就是如何寻找大数的因子分解，但ECDLP是比因子分解难得多的问题。KEn
48、KEP/KEQ/PQ 1椭圆曲线中两种运算示意图椭圆曲线上的加法：PQR椭圆曲线上一点的2倍：PPR椭圆曲线算法（续）n2.椭圆曲线上的密码算法椭圆曲线上的密码算法q1985年N.Koblitz和Miller提出将椭圆曲线用于密码算法，分别利用有限域上椭圆曲线的点构成的群，实现了离散对数密码算法。q椭圆曲线数字签名算法ECDSA，由IEEE工作组和ANSI（Amercian National Standards Institute）X9组织开发。椭圆曲线算法（续）n3.椭圆曲线密码算法的发展椭圆曲线密码算法的发展nRSA的长密钥带来了运算速度慢和密钥存储与管理的问题。n由于其自身的优点，椭圆曲
49、线密码学被普遍认为将替代RSA成为通用的密码算法。n应用：数字签名，智能卡n研究：陶仁骥，陈世华基于有限自动机的公 开密钥加密方法:FAPKC0，FAPKC1，FAPKC2，FAPKC3。2.4 流密码技术n本节友情提示 2.4.1 流密码基本原理 2.4.2 二元加法流密码 2.4.3 几种常见的流密码算法2.4 流密码技术n在单钥密码体制中，按照加密时对明文处理方式的不同，可分为分组密码和流密码。n流密码亦称为序列密码，是将待加密的明文分成连续的字符或比特，然后用相应的密钥流对之进行加密，密钥流由种子密钥通过密钥流生成器产生。n密钥流可以方便地利用以移位寄存器为基础的电路来产生。n特点：实
50、现简单，加密速度快，错误传播低。2.4.1 流密码基本原理n原理 通过随机数发生器产生性能优良的伪随机序列（密钥流），使用该序列加密信息流（逐比特加密），得到密文序列。种子密钥K随机数发生器加密变换密钥流Ki明文流mi密文流Cin按照加解密的工作方式，流密码分为同步流密码和自同步流密码。n1.同步流密码 密钥流的产生完全独立于信息流。密钥流生成器ki种子密钥k安全信道cikiim解密变换密钥流生成器 ci公 开 信道加密变换种子密钥K),(),(),(),(1iiiiiiiiiickDmmkEckGkkF流密码基本原理（续）n2.自同步流密码q是一种有记忆变换的密码，每一个密钥字符是由前面n个
