[经济学]计算机网络安全--第二章-密码技术课件

第第2章章密码技术密码技术1第2章密码技术1*Internet Internet在给人们带来各种便捷的同时，在给人们带来各种便捷的同时，网络上的种种不安全因素使得个人信息的安网络上的种种不安全因素使得个人信息的安全受到严重威胁全受到严重威胁.密码技术是应对网络安全威胁的有效手段密码技术是应对网络安全威胁的有效手段之一，多种密码技术的综合应用可以保证信之一，多种密码技术的综合应用可以保证信息的机密性、完整性和消息源的不可否认性息的机密性、完整性和消息源的不可否认性.同时密码技术也是身份认证的理论基础。同时密码技术也是身份认证的理论基础。第二章第二章 密码技术密码技术*Internet在给人们带来各种便捷的同时，网络上的种*本章内容提要本章内容提要:l密码技术概述密码技术概述l古典密码体制古典密码体制 l对称密码体制对称密码体制 l非对称密码体制非对称密码体制l椭圆曲线密码体制椭圆曲线密码体制 l密码技术应用案例密码技术应用案例l密码技术密码技术发展发展趋势趋势 第二章第二章 密码技术密码技术*本章内容提要:第二章 密码技术*2.1 2.1 密码技术概述密码技术概述 密码技术的最原始目的是秘密通信密码技术的最原始目的是秘密通信密码学早在公元前密码学早在公元前400400多年就产生了。多年就产生了。古人有意识地使用一些简单的方法来加古人有意识地使用一些简单的方法来加密信息，以确保他们通信的机密密信息，以确保他们通信的机密*2.1 密码技术概述 密码技术的最原始目的是秘密通*l l 密码技术概述密码技术概述密码技术概述密码技术概述 密码学概念密码学概念l 明文（消息）（明文（消息）（Plaintext）l 密文（密文（Ciphertext）l 加密（加密（Encryption）l 解密（解密（Decryption）l 加密算法（加密算法（Encryption algorithm）l 解密算法解密算法 l 密钥（密钥（Key）是作为加密输入的原始是作为加密输入的原始消息，即消息的原始形消息，即消息的原始形式式 明文经密码变换成的一种明文经密码变换成的一种隐蔽形式隐蔽形式 将明文变换为密文的过将明文变换为密文的过程程 加密的逆过程，加密的逆过程，即由密文恢复出即由密文恢复出原明文的过程原明文的过程 密码员对明文进行密码员对明文进行加密时所采用的一加密时所采用的一组规则组规则 接收者对密文进接收者对密文进行解密时所采用行解密时所采用的一组规则的一组规则 控制加密和解密算控制加密和解密算法操作的数据处理，法操作的数据处理，分别称为加密密钥分别称为加密密钥和解密密钥和解密密钥*密码技术概述 密码学概念 明文（消息）（Plain*l l 密码技术概述密码技术概述密码技术概述密码技术概述密码学是研究信息系统安全保密的科学，它包含密码学是研究信息系统安全保密的科学，它包含两个分支，即两个分支，即密码编码学（密码编码学（CryptographyCryptography）和和密密码分析学（码分析学（CryptanalyticsCryptanalytics）。密码编码学是对信息进行编密码编码学是对信息进行编码实现隐蔽信息的一门学问，码实现隐蔽信息的一门学问，以保护信息在传递过程中不以保护信息在传递过程中不被敌方窃取、解读被敌方窃取、解读 密码分析学则是研究分析破密码分析学则是研究分析破译密码的学问。密码分析学译密码的学问。密码分析学和密码编码学构成了信息安和密码编码学构成了信息安全的攻防体系全的攻防体系*密码技术概述密码学是研究信息系统安全保密的科学，它包含两*l l 密码技术概述密码技术概述密码技术概述密码技术概述 由信息安全的攻防两个方面共同构筑了信息保密系统由信息安全的攻防两个方面共同构筑了信息保密系统的模型，的模型，如图所示如图所示 密码系统密码系统双钥体制（非对称双钥体制（非对称密码体制或公钥体制）密码体制或公钥体制）单钥体制单钥体制(对称对称密码体制密码体制)流密码流密码分组密码分组密码*密码技术概述 由信息安全的攻防两个方面共同构筑了信*2.2 2.2 古典密码体制古典密码体制 现代密码的基本原理一般是基于复杂的现代密码的基本原理一般是基于复杂的数学运算或者数学难题的，而古典密码的两数学运算或者数学难题的，而古典密码的两个基本工作原理是代换和置换。代换是指通个基本工作原理是代换和置换。代换是指通过对于明文进行符号替换得到密文的加密方过对于明文进行符号替换得到密文的加密方法；而置换则是通过对于明文进行书写位置法；而置换则是通过对于明文进行书写位置交换而得到密文的加密方法。交换而得到密文的加密方法。虽然古典密码虽然古典密码技术很少独立应用于网络安全应用中，但这技术很少独立应用于网络安全应用中，但这些古典密码的基本手段仍是构造现代对称加些古典密码的基本手段仍是构造现代对称加密算法的核心技术。密算法的核心技术。*2.2 古典密码体制 现代密码的基本原理一*2.2 2.2 古典密码体制古典密码体制 l l 代换密码代换密码代换密码代换密码 l l 置换密码置换密码置换密码置换密码*2.2 古典密码体制 代换密码 置换密*l l 代换密码代换密码代换密码代换密码代换密码的思想代换密码的思想通过符号的简单替换而达到掩通过符号的简单替换而达到掩盖明文信息的目的，也就是将盖明文信息的目的，也就是将明文中的字母由其他字母、数明文中的字母由其他字母、数字或者符号取代的一种方法，字或者符号取代的一种方法，其中的替代方案就称为密钥。其中的替代方案就称为密钥。M M 称为明文空间，称为明文空间，C C 称为密文空间，称为密文空间，K K 称为密钥空间。称为密钥空间。为以为以k k为密钥将明为密钥将明文消息加密的函数文消息加密的函数，则为以则为以k k为密钥将密文解密的函数。为密钥将密文解密的函数。则加密和解密映射定义为则加密和解密映射定义为 *代换密码代换密码的思想通过符号的简单替换而达到掩盖明文信凯撒密码n历史上，凯撒大帝曾用此方法对重要的军事信息进行加密。n根据现有的记载，当时也没有任何技术能够解决这一最基本、最简单的密码。n现存最早的破解方法记载在公元9世纪阿拉伯的阿尔阿尔肯迪肯迪的有关发现频率分析的著作中。11凯撒密码历史上，凯撒大帝曾用此方法对重要的军事信息进行加密 n加密规则：位移量=3！凯撒密码12加密规则：位移量=3！凯撒密码12*l l 代换密码代换密码代换密码代换密码 【例例】设明文为设明文为Caesar cipher is a substitutionCaesar cipher is a substitution，取，取k k=3=3采用凯撒密采用凯撒密码进行加密变码进行加密变换，同时给出逆变换。换，同时给出逆变换。明文：明文：m=Caesar cipher is a substitution。加密：加密：c:，对应得到字母，对应得到字母F a:，对应得到字母，对应得到字母D e:，对应得到字母，对应得到字母H 其余字母加密运算类似。其余字母加密运算类似。经凯撒密码变换后得到的密文是：经凯撒密码变换后得到的密文是：CFDHVDU FLSKHU LV D VXEVWLWXWLRQ解密：解密代换是加密代换的逆变换，对于密文解密：解密代换是加密代换的逆变换，对于密文C执行解密变换可以得到对应的执行解密变换可以得到对应的明文明文m。F:，对应得到字母，对应得到字母CD:，对应得到字母，对应得到字母AH:，对应得到字母，对应得到字母E 如何破解？*代换密码 【例】设明文为Caesar cipher即使使用唯密文攻击，恺撒密码也是一种非常容易破解的加密方式。n两种情况：攻击者知道（或者猜测）密码中使用了某个简单的替换加密方式，但是不确定是恺撒密码；攻击者知道（或者猜测）使用了恺撒密码，但是不知道其偏移量。对于第一种情况，攻击者可以通过使用诸如频率分析或者样式单词分析的方法，马上就能从分析结果中看出规律，得出加密者使用的是恺撒密码。对于第二种情况，它的偏移量最多就是25因此可以通过穷举法，很轻易地进行破解 14即使使用唯密文攻击，恺撒密码也是一种非常容易破解的加密方式。穷举法：n方法是在表格中写下密文中的某个小片段n使用所有可能的偏移量解密后的内容称为候选明文。n分析表格中的候选明文是否具有实际含义，得出正确的偏移量，解密整个密文。n例如密文片段是：EXXEGOEXSRGI 可以很快看出其正确的偏移量是4 15穷举法：方法是在表格中写下密文中的某个小片段可以很快看出其正*l l 代换密码代换密码代换密码代换密码 1 1、单表代换密码（、单表代换密码（Monoalphabetic CipherMonoalphabetic Cipher）【例】简单的代换密码，设简单的代换密码，设M=C=，首先将，首先将26个英文字母与模个英文字母与模26的剩余类集合的剩余类集合0,1,2,25建立一一对应关系，所包含元素表示为建立一一对应关系，所包含元素表示为A=0，B=1，Z=25。将加。将加密算法密算法 定义为下面的定义为下面的 上的一个置换为上的一个置换为那么相应的解密算法那么相应的解密算法 为为明文消息明文消息“monoalphabetic cipher”加密为下面的密文消息：加密为下面的密文消息：Jkfkvdcpvmyowz zwcpyq 是指对于一个给定的加是指对于一个给定的加密密钥，明文消息空间密密钥，明文消息空间中的每一元素将被代换中的每一元素将被代换为密文消息空间中的唯为密文消息空间中的唯一元素一元素 凯撒密码就属于单表代凯撒密码就属于单表代换密码换密码 *代换密码 1、单表代换密码（Monoalphabeti*l l 代换密码代换密码代换密码代换密码 仿射密码，即定义代换密码系统仿射密码，即定义代换密码系统 *代换密码 仿射密码，即定义代换密码系统 *l l 代换密码代换密码代换密码代换密码 【例例】设密钥对为设密钥对为(7,2)，加密函数为，加密函数为7m+2(mod 26)，对于明文消息，对于明文消息happy进行进行加密变换，并给出相应的解密变换。加密变换，并给出相应的解密变换。加密变换如下：加密变换如下：首先转换明文字母首先转换明文字母h,a,p,p,y为对应的数字为对应的数字7,0,15,15,24。h7 加密：（加密：（77+2）mod 26=25 za0 加密：（加密：（07+2）mod 26=2 cp15 加密：（加密：（157+2）mod 26=3 dp15 加密：（加密：（157+2）mod 26=3 dy24 加密：（加密：（247+2）mod 26=14 o由此，得到明文消息由此，得到明文消息happy在在7m+2(mod 26)仿射加密变换下得到的密文为仿射加密变换下得到的密文为zcddo解密变换如下：解密变换如下：首先转换密文字母首先转换密文字母z,c,d,d,o为对应的数字为对应的数字25,2,3,3,14，根据仿射变换的定义，加，根据仿射变换的定义，加密密钥对密密钥对(7,2)相应的解密变换为相应的解密变换为 (c-2)(mod 26)，这里，这里 15(mod 26)。z25 解密：（解密：（25-2）15 mod 26=7 hc2 解密：解密：11（2-2）15 mod 26=0 ad3 解密：解密：11（3-2）15 mod 26=15 pd3 解密：解密：11（3-2）15 mod 26=15 po14 解密：（解密：（14-2）15 mod 26=24 y于是，得到解密后的消息为于是，得到解密后的消息为happy。*代换密码 【例】设密钥对为(7,2)，加密函数为7m+*l l 代换密码代换密码代换密码代换密码 2、多表代换密码、多表代换密码【例例】设起始密钥串是设起始密钥串是today，根据编码规则，根据编码规则A=0，B=1，Z=25，密钥串的数，密钥串的数字表示是（字表示是（19,14,3,0,24）。明文串）。明文串proceed meeting as agreed进行维吉尼亚加密进行维吉尼亚加密和解密运算。加密运算见下表和解密运算。加密运算见下表多表代换使用从明文字母到密文字多表代换使用从明文字母到密文字母的多个映射来隐藏字母出现的频母的多个映射来隐藏字母出现的频率分布，明文字符和密文字符的关率分布，明文字符和密文字符的关系是一对多的系是一对多的 表表 密钥串为密钥串为today对于明文串对于明文串proceed meeting as agreed的加密变换的加密变换 明文明文proceed meeting as agreed明文明文编码pi15,17,14,2,44,3,12,4,419,8,13,6,018,0,6,17,44,3密密钥编码ki19,14,3,0,2419,14,3,0,2419,14,3,0,2419,14,3,0,2419,14,3,0,24密文密文编码ci8,5,17,2,223,17,15,4,212,22,16,6,2411,14,9,17,223,17密文密文ifrccxr pecmwqg yl ojrcxr*代换密码 2、多表代换密码【例】设起始密钥串是t*2.2 2.2 古典密码体制古典密码体制 l l 代换密码代换密码代换密码代换密码 l l 置换密码置换密码置换密码置换密码*2.2 古典密码体制 代换密码 置换密*l l 置换密码置换密码置换密码置换密码 置换密码置换密码通过重新排列消息中元素的位置通过重新排列消息中元素的位置而不改变元素本身来变换一个消而不改变元素本身来变换一个消息的密码方案息的密码方案 无密钥换位密码无密钥换位密码 【例】无密钥换位密码的加解密运算，设明文消息为无密钥换位密码的加解密运算，设明文消息为proceed meeting as agreedproceed meeting as agreed。加密运算：对于明文消息按行书写（每行加密运算：对于明文消息按行书写（每行4 4列），得到列），得到 p r o c e e d m e e t i n g a s a g r e e d*逐列读出，即得到密文逐列读出，即得到密文peenaereeggdodtar*cmise*peenaereeggdodtar*cmise*，并将密文传输给信息的接收者。，并将密文传输给信息的接收者。*置换密码 置换密码通过重新排列消息中元素的位置而不改变*l l 置换密码置换密码置换密码置换密码 有密钥换位密码有密钥换位密码 【例】有密钥换位密码的加解密运算，设分组大小为有密钥换位密码的加解密运算，设分组大小为b b=4=4，密钥为，密钥为=(=(1)(1)，(2)(2)，(3)(3)，(4)=(2,4,1,3)(4)=(2,4,1,3)那么明文消息为那么明文消息为proceed meeting as agreed首先分为首先分为6个分组，每个分组个分组，每个分组4个字符为个字符为proc eedm eeti ngas agre ed然后可以变换然后可以变换-加密成下面的密文为加密成下面的密文为rcpoemedeietgsnagearde明文的解密密钥是明文的解密密钥是*置换密码 有密钥换位密码【例】有密钥换位密码的加*2.3 2.3 对称密码体制对称密码体制 对称密码又分为流密码和分组密码。对称密码又分为流密码和分组密码。流密码的中心思想是以尽可能简单的方流密码的中心思想是以尽可能简单的方式来生成一个伪随机性尽可能好的周期式来生成一个伪随机性尽可能好的周期序列。流密码体制以简洁、快速的特点，序列。流密码体制以简洁、快速的特点，成为新一代移动通信的主流加密算法；成为新一代移动通信的主流加密算法；分组密码是将明文序列划分成等长的分分组密码是将明文序列划分成等长的分组，对每一组用同一加密算法和同一密组，对每一组用同一加密算法和同一密钥进行加密。钥进行加密。*2.3 对称密码体制 对称密码又分为*2.3 2.3 对称密码体制对称密码体制 l l 分组密码概述分组密码概述分组密码概述分组密码概述 l l 数据加密标准数据加密标准数据加密标准数据加密标准DESDES l l 高级加密标准高级加密标准高级加密标准高级加密标准AESAES l l 分组密码工作模式分组密码工作模式分组密码工作模式分组密码工作模式 l l 流密码流密码流密码流密码*2.3 对称密码体制 分组密码概述 数*l l 分组密码概述分组密码概述分组密码概述分组密码概述 分组密码分组密码 主要任务是提供数据保密性。分主要任务是提供数据保密性。分组密码算法是将一些固定的置换作用组密码算法是将一些固定的置换作用于明文数据分组的加密算法。它将明于明文数据分组的加密算法。它将明文按一定的比特长度分组，由明文组文按一定的比特长度分组，由明文组和密钥组经过加密运算得到密文组，和密钥组经过加密运算得到密文组，密文组和密钥组经过解密运算还原成密文组和密钥组经过解密运算还原成明文组，其中解密运算通常为加密运明文组，其中解密运算通常为加密运算的逆运算算的逆运算。分组密码算法的设计分组密码算法的设计 扩散（扩散（DiffusionDiffusion）混淆（混淆（ConfusionConfusion）将明文组及密钥组的影响迅将明文组及密钥组的影响迅速地散布到输出的密文组中，速地散布到输出的密文组中，通常通过置换通常通过置换（Permutation）的方法来）的方法来实现扩散。实现扩散。使作用于明文的密钥和密文之间的使作用于明文的密钥和密文之间的关系复杂化，实现明文和密文之间，关系复杂化，实现明文和密文之间，密文和密钥之间的统计相关性的极密文和密钥之间的统计相关性的极小化，从而使统计分析攻击无法奏小化，从而使统计分析攻击无法奏效，通常通过代换（效，通常通过代换（Substitution）的方式实现混淆。的方式实现混淆。*分组密码概述 分组密码 主要任务是提供数*l l 分组密码概述分组密码概述分组密码概述分组密码概述 分组密码的两个参数分组密码的两个参数密钥长度密钥长度分组长度分组长度（表示密钥表示密钥k k对明文对明文m m加密，加密，表示密钥表示密钥k k对密文对密文c c的解密的解密 ）*分组密码概述 分组密码的两个参数密钥长度分组长度（*l l 分组密码概述分组密码概述分组密码概述分组密码概述 分组密码的设计要点分组密码的设计要点l分组足够长分组足够长l密钥长度要足够长密钥长度要足够长l算法足够复杂算法足够复杂l加密、解密算法简单加密、解密算法简单l便于分析便于分析分组密码算法的设计准则分组密码算法的设计准则简捷性简捷性有效性有效性透明性透明性灵活性灵活性加、解密相似性加、解密相似性*分组密码概述 分组密码的设计要点分组足够长分组密码算法*2.3 2.3 对称密码体制对称密码体制 l l 分组密码概述分组密码概述分组密码概述分组密码概述 l l 数据加密标准数据加密标准数据加密标准数据加密标准DESDES l l 高级加密标准高级加密标准高级加密标准高级加密标准AESAES l l 分组密码工作模式分组密码工作模式分组密码工作模式分组密码工作模式 l l 流密码流密码流密码流密码*2.3 对称密码体制 分组密码概述 数*l l 数据加密标准数据加密标准数据加密标准数据加密标准DESDES DESDES算法概述算法概述 DES加密算法原理加密算法原理 DES加密运算包括一个初始置换IP，16个轮运算以及一个末置换 ，最后得到64比特的输出。DES加解密初始置换加解密初始置换IP与末置换与末置换 初始置换初始置换IP的功能是将输入的的功能是将输入的64位数据分组按位重新组位数据分组按位重新组合，其置换规则如合，其置换规则如图图2.4所示。所示。DES算法的基本结构算法的基本结构如图所示如图所示,轮迭代中轮迭代中F运算的具体细节运算的具体细节如图所示如图所示。*数据加密标准DES DES算法概述 DES加密算法原理*l l 数据加密标准数据加密标准数据加密标准数据加密标准DESDES DES的轮迭代及的轮迭代及F函数函数 l明文扩展变换明文扩展变换E 48bitl轮函数轮函数F中的中的S盒盒32bit32bitl置换置换P 在轮函数F中输入的 是32比特，需要先经过一个变换E的作用，使其扩展为48比特，才能与48比特的子密钥进行异或运算。在轮函数F中，置换P用来将经过S盒变换产生的32位输出进行置乱交换 DES算法的轮函数F中一共8个S盒，每个S盒 都是将6比特的输入缩减为4比特的输出，这样8个S盒将48比特的输入缩减为32比特的输出。每轮64比特的处理：分一半 32bit*数据加密标准DES DES的轮迭代及F函数 明文扩展变*l l 数据加密标准数据加密标准数据加密标准数据加密标准DESDES 子密钥的生成子密钥的生成 解密过程是加密的逆运算解密过程是加密的逆运算，解密中的轮迭代解密中的轮迭代如图所示如图所示。在DES的子密钥生成算法中，缩减置换PC-1的作用是将64比特长的串缩减为56比特，PC-2的作用是将56比特的串缩减为48比特。PC-1缩减置换的具体规则缩减置换的具体规则如图所示如图所示。PC-2置换的具体规则置换的具体规则如图所示如图所示。DESDES解密运算解密运算 过程如图所示*数据加密标准DES 子密钥的生成 解密过程是加密的逆运*2.3 2.3 对称密码体制对称密码体制 l l 分组密码概述分组密码概述分组密码概述分组密码概述 l l 数据加密标准数据加密标准数据加密标准数据加密标准DESDES l l 高级加密标准高级加密标准高级加密标准高级加密标准AESAES l l 分组密码工作模式分组密码工作模式分组密码工作模式分组密码工作模式 l l 流密码流密码流密码流密码*2.3 对称密码体制 分组密码概述 数*l l 高级加密标准高级加密标准高级加密标准高级加密标准AESAES 高级加密标准高级加密标准AESAES算法概述算法概述在AES-128中，128比特的消息分组被分成16个字节，记为：。128比特的密钥分组则记为:。在在AESAES算法中，每轮变换的结果被称为状态，初始状态算法中，每轮变换的结果被称为状态，初始状态statestate也就是输也就是输入的明文消息。入的明文消息。AESAES加密算法示意加密算法示意如图所示如图所示。RijndaelRijndael算法在整体结构上采用算法在整体结构上采用SqureSqure结构结构 l非线性层非线性层l线性混合层线性混合层 l密钥加层密钥加层 进行S盒变换SubByte，起到混淆的作用 进行行移位变换ShiftRow和列混合变换MixColumn，以确保多轮之上的高度扩散。进行密钥加变换AddRoundKey，将轮密钥简单地异或到中间状态上。*高级加密标准AES 高级加密标准AES算法概述在AES*l l 高级加密标准高级加密标准高级加密标准高级加密标准AESAES 轮变换轮变换 主要包括三个代替和一个混淆：主要包括三个代替和一个混淆：轮密钥加变换轮密钥加变换AddRoundKeyAddRoundKey、字节代、字节代替变换替变换SubByteSubByte、行移位变换、行移位变换ShiftRowShiftRow以及以及列混合变换列混合变换MixColumnMixColumn。l轮密钥加变换轮密钥加变换AddRoundKeyAddRoundKeyl字节代替变换字节代替变换SubByte SubByte l行移位变换（行移位变换（ShiftRowShiftRow）l列混合变换列混合变换MixColumnMixColumn 轮密钥加变换是将轮密钥与状态进行逐比特异或。轮密钥是由种子密钥通过密钥调度算法得到的。SubByte变换也称S盒变换，它用于将输入或者中间状态的每一个字节通过一个简单的查表操作，将其映射为另一个字节值。在行移位（ShiftRow）变换中，状态矩阵中的每一行将以字节为单位，循环左移不同的位移量。4个字节构成的向量可以表示为系数在 上的次数小于4的多项式，多项式的加法就是对应系数相加*高级加密标准AES 轮变换 主要包括三个代*l l 高级加密标准高级加密标准高级加密标准高级加密标准AESAES 轮密钥生成轮密钥生成 密钥生成指从种子密钥得到轮密钥的过程。轮密钥生成算法由密钥生成指从种子密钥得到轮密钥的过程。轮密钥生成算法由密钥扩密钥扩展和轮密钥选取展和轮密钥选取两部分组成。两部分组成。基本原则：基本原则：l轮密钥的比特数等于分组长度乘以轮数加轮密钥的比特数等于分组长度乘以轮数加1l 字节种子密钥被扩展成为扩展密钥字节种子密钥被扩展成为扩展密钥 *高级加密标准AES 轮密钥生成 密钥生成指*l l 高级加密标准高级加密标准高级加密标准高级加密标准AESAES 解密解密 解密算法的结构与加密算法的结构相同，其中的变换为加密算法的逆解密算法的结构与加密算法的结构相同，其中的变换为加密算法的逆变换，且密钥调度稍有不同。变换，且密钥调度稍有不同。l解密轮变换中的解密轮变换中的AddRoundKey l解密轮变换中的解密轮变换中的InSubByte l解密轮变换中的解密轮变换中的InShiftRow l解密轮变换中的解密轮变换中的 InMixColumn*高级加密标准AES 解密 解密算法的结构与*2.3 2.3 对称密码体制对称密码体制 l l 分组密码概述分组密码概述分组密码概述分组密码概述 l l 数据加密标准数据加密标准数据加密标准数据加密标准DESDES l l 高级加密标准高级加密标准高级加密标准高级加密标准AESAES l l 分组密码工作模式分组密码工作模式分组密码工作模式分组密码工作模式 l l 流密码流密码流密码流密码*2.3 对称密码体制 分组密码概述 数*l l 分组密码工作模式分组密码工作模式分组密码工作模式分组密码工作模式 分组密码工作模式分组密码工作模式l电码本模式电码本模式 l密码分组连接模式密码分组连接模式 l输出反馈模式输出反馈模式 l密文反馈模式密文反馈模式 l计数器模式计数器模式 电码本模式是最简单的工作模式，该模式将输入的消息分成一定比特长度的分组（将最后的分组填充），使用秘密密钥加密每个分组。另一端在接收到加密的分组后，解密每个分组并得到初始消息 将前一组的加密结果反馈到当前组的加密，同时，当前组的加密结果被用来修改下一组加密。每组密文依赖于它前面的各组明文 输出反馈模式（OFB）是通过序列密码思想实现加密的模式，其思路是将OFB输出的数据串与明文消息进行异或运算以实现加密 密文反馈模式（CFB）在结构上与OFB模式类似，它们均适用于待加密的消息必须按字符处理。每次生成j比特的数据并与j比特的明文进行异或运算（按字符处理时，可以取j=8）计数器模式（CTR）的分组密码工作模式是通过对于一个计数器序列进行加密得到一次一密序列，并与数据进行异或运算而生成密文*分组密码工作模式 分组密码工作模式电码本模式是最简单的*2.3 2.3 对称密码体制对称密码体制 l l 分组密码概述分组密码概述分组密码概述分组密码概述 l l 数据加密标准数据加密标准数据加密标准数据加密标准DESDES l l 高级加密标准高级加密标准高级加密标准高级加密标准AESAES l l 分组密码工作模式分组密码工作模式分组密码工作模式分组密码工作模式 l l 流密码流密码流密码流密码*2.3 对称密码体制 分组密码概述 数*l l 流密码流密码流密码流密码 流密码流密码与分组密码不同，流密码的基本与分组密码不同，流密码的基本思想是加密和解密运算每次只处思想是加密和解密运算每次只处理一个符号，可以是一个字符或理一个符号，可以是一个字符或一个比特。一个比特。l 同步流密码同步流密码 同步流密码的模型同步流密码的模型如图所示如图所示 一个同步流密码的加密器分成一个同步流密码的加密器分成密钥流生成器和加密变换器密钥流生成器和加密变换器两两部分，其中加密变换记为，而解密变换是加密变换的逆变换部分，其中加密变换记为，而解密变换是加密变换的逆变换*流密码 流密码与分组密码不同，流密码的基本思想是加密和*l l 流密码流密码流密码流密码 l 密钥流生成器密钥流生成器 图 线性移位反性移位反馈寄存器的模型寄存器的模型图*流密码 密钥流生成器 图 线性移位反馈寄存器的模型*l l 流密码流密码流密码流密码 【例】设n=4，计算该四级线性反馈移位寄存器的输出序列。在这里c1=c2=0，c3=c4=1 则该线性反馈移位寄存器模型如下图所示。图 线性反性反馈移位寄存器移位寄存器于是该线性反馈移位寄存器的输出序列为：101111000100110 101111000100110 101111000100110，可见该序列具有周期，其周期是15。1 10 01 11 1计算开始于第5个数*流密码 【例】设n=4，*2.4 2.4 非对称密码体制非对称密码体制 非对称密码体制（非对称密码体制（Asymmetric CryptoSystem），也称为公钥密码体制（），也称为公钥密码体制（Public Key Cryptosystem），是现代密码学的重要组成部），是现代密码学的重要组成部分。公钥密码的思想在分。公钥密码的思想在1976年由年由Diffie和和Hellman在在其其密码学新方向密码学新方向一文中提出。一文中提出。Rivest、Shamir和和Adleman在在1978年提出了首个非对称密码体制，年提出了首个非对称密码体制，即著名的即著名的RSA公钥密码体制。非对称密码体制的发明公钥密码体制。非对称密码体制的发明是现代密码的具有里程碑意义的重要事件，它的出现是现代密码的具有里程碑意义的重要事件，它的出现标志着现代密码学的创立。标志着现代密码学的创立。*2.4 非对称密码体制 非对称密码体*2.4 2.4 非非对称密码体制对称密码体制 l l 非对称密码体制的基本概念非对称密码体制的基本概念非对称密码体制的基本概念非对称密码体制的基本概念 l l 非对称密码体制的原理非对称密码体制的原理非对称密码体制的原理非对称密码体制的原理 l l RSARSARSARSA算法算法算法算法 l l RSA RSA算法中的计算问题算法中的计算问题算法中的计算问题算法中的计算问题 l l RSA RSA算法的安全性算法的安全性算法的安全性算法的安全性 l l 非对称密码体制的应用非对称密码体制的应用非对称密码体制的应用非对称密码体制的应用*2.4 非对称密码体制 非对称密码体制的基本*l l非对称密码体制的基本概念非对称密码体制的基本概念非对称密码体制的基本概念非对称密码体制的基本概念非对称密码（公钥密码）与所有以前的密码方法的不同点非对称密码（公钥密码）与所有以前的密码方法的不同点 l基于的基本思想不同基于的基本思想不同l密钥的使用方式不同密钥的使用方式不同 公钥密码算法的密钥具有如下特点公钥密码算法的密钥具有如下特点 l 是加密密钥与解密密钥是本质上不同的是加密密钥与解密密钥是本质上不同的 l 是大多数公钥密码算法的加密密钥和解密密钥具有互换的性质，即两者是相对的是大多数公钥密码算法的加密密钥和解密密钥具有互换的性质，即两者是相对的*非对称密码体制的基本概念非对称密码（公钥密码）与所有以前的*2.4 2.4 非非对称密码体制对称密码体制 l l 非对称密码体制的基本概念非对称密码体制的基本概念非对称密码体制的基本概念非对称密码体制的基本概念 l l 非对称密码体制的原理非对称密码体制的原理非对称密码体制的原理非对称密码体制的原理 l l RSARSARSARSA算法算法算法算法 l l RSA RSA算法中的计算问题算法中的计算问题算法中的计算问题算法中的计算问题 l l RSA RSA算法的安全性算法的安全性算法的安全性算法的安全性 l l 非对称密码体制的应用非对称密码体制的应用非对称密码体制的应用非对称密码体制的应用*2.4 非对称密码体制 非对称密码体制的基本*l l非对称密码体制的原理非对称密码体制的原理非对称密码体制的原理非对称密码体制的原理非对称密码体制的正确运行需要满足以下要求非对称密码体制的正确运行需要满足以下要求 l通信的参与方通信的参与方B容易通过计算产生一对密钥，即公开密钥容易通过计算产生一对密钥，即公开密钥 和私有密钥和私有密钥 l信息的发送方信息的发送方A希望以秘密方式发送信息希望以秘密方式发送信息M给给B，在知道，在知道B的公开密钥的公开密钥 时，时，可以通过加密算法生成密文：可以通过加密算法生成密文：l接收方接收方B B使用私有密钥容易通过解密算法对密文进行解密，以恢复原来的明文使用私有密钥容易通过解密算法对密文进行解密，以恢复原来的明文 l从公开密钥从公开密钥PKPKB B推出私有密钥推出私有密钥 ，在计算上是不可行的，在计算上是不可行的*非对称密码体制的原理非对称密码体制的正确运行需要满足以下要*l l非对称密码体制的原理非对称密码体制的原理非对称密码体制的原理非对称密码体制的原理定义定义 单向陷门函数满足下列条件的函数单向陷门函数满足下列条件的函数f f:D DV V1 1）对于任意对于任意给定的给定的x xD D，计算计算y y=f f(x x)是是容易容易的。的。2 2）对于几乎所有任意对于几乎所有任意给定给定y yV V，计算计算x xD D使得使得y y=f f(x x)，在计算上是在计算上是困难困难的，即计算的，即计算 是困难的。这里所谓是困难的。这里所谓 困难是指在有意义的时间要求之内计算是不可行的。困难是指在有意义的时间要求之内计算是不可行的。3 3）存在存在陷门信息陷门信息t t，当已知，当已知t t时，对给定的时，对给定的任何任何y yV V，若相应的，若相应的 x x存在，则存在，则计算计算x x使使y y=f f(x x)是是容易容易的。的。*非对称密码体制的原理定义 单向陷门函数满足下列条件的函数*2.4 2.4 非非对称密码体制对称密码体制 l l 非对称密码体制的基本概念非对称密码体制的基本概念非对称密码体制的基本概念非对称密码体制的基本概念 l l 非对称密码体制的原理非对称密码体制的原理非对称密码体制的原理非对称密码体制的原理 l l RSARSARSARSA算法算法算法算法 l l RSA RSA算法中的计算问题算法中的计算问题算法中的计算问题算法中的计算问题 l l RSA RSA算法的安全性算法的安全性算法的安全性算法的安全性 l l 非对称密码体制的应用非对称密码体制的应用非对称密码体制的应用非对称密码体制的应用*2.4 非对称密码体制 非对称密码体制的基本*l lRSARSA算法算法算法算法算法算法 RSARSA密码体制密码体制密钥的生成：密钥的生成：用户用户AliceAlice为了生成为了生成RSARSA密钥执行以下步骤。密钥执行以下步骤。随机选择两个大素数随机选择两个大素数p p和和q q，计算，计算N N=pqpq和和(N N)=()=(p p1)(1)(q q1)1)；随机选择整数；随机选择整数e e，11e e(N N)，满足，满足gcd(gcd(e e,(N N)=1)=1，并计算整数，并计算整数d d满足满足eded1(mod1(mod(N N)；用户用户AliceAlice公开她的公钥公开她的公钥 PKPK=(=(N N,e e)，安全地销毁，安全地销毁p p,q q和和(N N)，并秘密保留她的私钥，并秘密保留她的私钥SkSk=(=(d d)。加密：加密：用户用户BobBob为了将消息为了将消息m mZNZN秘密地发送给秘密地发送给AliceAlice，BobBob首先获得首先获得AliceAlice的公开密钥的公开密钥PKPK=(=(N N,e e)，计算密文，计算密文 ，。将。将密文密文c c通过不安全信道发送给通过不安全信道发送给AliceAlice。解密：解密：用户用户AliceAlice接受到密文接受到密文c c后后，计算计算 ，得到消息，得到消息m m。*RSA算法算法 RSA密码体制*l lRSARSA算法算法算法算法【例例】RSA算法实例。算法实例。1）设通信方设通信方Alice选择两个素数选择两个素数p=7和和q=13，计算，计算N=713=91以及以及(N)=612=72。2）选择一个随机整数选择一个随机整数e=5，满足。，满足。3）由由欧拉辗转相除法欧拉辗转相除法，根据，根据e，(N)Alice计算得到计算得到d：72(2)+529=1，即，即529=1(mod 72)。于是，。于是，Alice计算得到的计算得到的d=29作为她秘密的解密密作为她秘密的解密密钥，钥，Alice公开公开(N,e)=(91,5)作为作为RSA体制的公开密钥。体制的公开密钥。4）设设Bob欲秘密发送明文欲秘密发送明文m=3给给Alice，Bob计算计算 ，即得到的密文是，即得到的密文是61。5）为了解密密文为了解密密文61，Alice利用自己的秘密钥利用自己的秘密钥d计算计算 ，即得到了明文即得到了明文m=3。利用扩展欧几里德定理利用扩展欧几里德定理如果如果gcd(a,b)=d,gcd(a,b)=d,那么一那么一定存在整数定存在整数x x，y y 满足满足a*x+b*y=da*x+b*y=d*RSA算法【例】RSA算法实例。利用扩展欧几里德定理*2.4 2.4 非非对称密码体制对称密码体制 l l 非对称密码体制的基本概念非对称密码体制的基本概念非对称密码体制的基本概念非对称密码体制的基本概念 l l 非对称密码体制的原理非对称密码体制的原理非对称密码体制的原理非对称密码体制的原理 l l RSARSARSARSA算法算法算法算法 l l RSA RSA算法中的计算问题算法中的计算问题算法中的计算问题算法中的计算问题 l l RSA RSA算法的安全性算法的安全性算法的安全性算法的安全性 l l 非对称密码体制的应用非对称密码体制的应用非对称密码体制的应用非对称密码体制的应用 不讲*2.4 非对称密码体制 非对称密码体制的基本*2.4 2.4 非非对称密码体制对称密码体制 l l 非对称密码体制的基本概念非对称密码体制的基本概念非对称密码体制的基本概念非对称密码体制的基本概念 l l 非对称密码体制的原理非对称密码体制的原理非对称密码体制的原理非对称密码体制的原理 l l RSARSARSARSA算法算法算法算法 l l RSA RSA算法中的计算问题算法中的计算问题算法中的计算问题算法中的计算问题 l l RSA RSA算法的安全性算法的安全性算法的安全性算法的安全性 l l 非对称密码体制的应用非对称密码体制的应用非对称密码体制的应用非对称密码体制的应用*2.4 非对称密码体制 非对称密码体制的基本*l lRSARSA算法的安全性算法的安全性算法的安全性算法的安全性 RSA的安全性是基于分解大整数的困难性假定，为了保证的安全性是基于分解大整数的困难性假定，为了保证RSA的安全的安全性，性，密钥长度应该介于密钥长度应该介于10242048比特比特。根据对已有的。根据对已有的RSA的攻击分析，的攻击分析，除了限制除了限制n的大小以保证安全性外，研究者还建议对于的大小以保证安全性外，研究者还建议对于p和和q做如下限制做如下限制：lp p和和q q在在长度上度上应该接近，例如，接近，例如，p p和和q q都都应在在 10107575到到1010100100的范的范围之内。之内。l(p p-1)-1)和和(q q-1)-1)都都应包含一个包含一个较大的素数因子。大的素数因子。lGcd(Gcd(p p-1,-1,q q-1)-1)应该比比较小。小。l选择时应使得使得 。可以。可以证明的是，如明的是，如果果 ，则d d可以很容易可以很容易地被猜测到。地被猜测到。*RSA算法的安全性 RSA的安全性是基于分解大*2.4 2.4 非非对称密码体制对称密码体制 l l 非对称密码体制的基本概念非对称密码体制的基本概念非对称密码体制的基本概念非对称密码体制的基本概念 l l 非对称密码体制的原理非对称密码体制的原理非对称密码体制的原理非对称密码体制的原理 l l RSARSARSARSA算法算法算法算法 l l RSA RSA算法中的计算问题算法中的计算问题算法中的计算问题算法中的计算问题 l l RSA RSA算法的安全性算法的安全性算法的安全性算法的安全性 l l 非对称密码体制的应用非对称密码体制的应用非对称密码体制的应用非对称密码体制的应用*2.4 非对称密码体制 非对称密码体制的基本*l l非对称密码体制的应用非对称密码体制的应用非对称密码体制的应用非对称密码体制的应用公钥密码系统的特点使其可以在信息安全的三个方面发挥作用公钥密码系统的特点使其可以在信息安全的三个方面发挥作用 l信息机密性的实现信息机密性的实现l不可否认性的实现不可否认性的实现 l密钥交换密钥交换 数字信封技术数字信封技术如图所示如图所示*非对称密码体制的应用公钥密码系统的特点使其可以在信息安全的*2.5 2.5 椭圆曲线密码体制椭圆曲线密码体制 RSARSA从体制上说是基于有限域上的数学困难问题从体制上说是基于有限域上的数学困难问题的，是安全的非对称密钥密码系统，而其中存在的一的，是安全的非对称密钥密码系统，而其中存在的一个问题是系统要求的密钥非常大。因为随着计算机处个问题是系统要求的密钥非常大。因为随着计算机处理能力的提高和集群技术的应用，使得短的理能力的提高和集群技术的应用，使得短的RSARSA密钥密钥会受到严重的安全挑战，而长的会受到严重的安全挑战，而长的RSARSA密钥又必然严重密钥又必然严重制约算法的效率。研究人员已经提出了更有前景的椭制约算法的效率。研究人员已经提出了更有前景的椭圆曲线密码系统（圆曲线密码系统（Elliptic Curve CrptygraphyElliptic Curve Crptygraphy，ECCECC），该密码系统的优越性是，在密钥较短的情况），该密码系统的优越性是，在密钥较短的情况下达到相同的安全级别，其安全性基于椭圆曲线离散下达到相同的安全级别，其安全性基于椭圆曲线离散对数问题的困难性。对数问题的困难性。*2.5 椭圆曲线密码体制 RSA从体*2.5 2.5 椭圆曲线椭圆曲线密码体制密码体制 l l 椭圆曲线椭圆曲线椭圆曲线椭圆曲线 l 有限域上的椭圆曲线有限域上的椭圆曲线 l l 椭圆曲线上的密码算法椭圆曲线上的密码算法椭圆曲线上的密码算法椭圆曲线上的密码算法 l l 椭圆曲线密码体制的安全性椭圆曲线密码体制的安全性椭圆曲线密码体制的安全性椭圆曲线密码体制的安全性*2.5 椭圆曲线密码体制 椭圆曲线 有*l l椭圆曲线椭圆曲线椭圆曲线椭圆曲线椭圆曲线方程的椭圆曲线方程的一般形式一般形式是是式式 其中，其中，a a,b b,c c,d d,e e是满足一些简单条件的实数。椭圆曲线是满足一些简单条件的实数。椭圆曲线的图形并非椭圆，只是其方程与计算椭圆周长的方程类似。的图形并非椭圆，只是其方程与计算椭圆周长的方程类似。椭圆曲线除了所有满足曲线方程的点之外还包括一个特殊的椭圆曲线除了所有满足曲线方程的点之外还包括一个特殊的点，即无穷远点，记为点，即无穷远点，记为O O。*椭圆曲线椭圆曲线方程的一般形式是式 其中，a,b,*2.5 2.5 椭圆曲线椭圆曲线密码体制密码体制 l l 椭圆曲线椭圆曲线椭圆曲线椭圆曲线 l 有限域上的椭圆曲线有限域上的椭圆曲线 l l 椭圆曲线上的密码算法椭圆曲线上的密码算法椭圆曲线上的密码算法椭圆曲线上的密码算法 l l 椭圆曲线密码体制的安全性椭圆曲线密码体制的安全性椭圆曲线密码体制的安全性椭圆曲线密码体制的安全性*2.5 椭圆曲线密码体制 椭圆曲线 有*l l有限域上的椭圆曲线有限域上的椭圆曲线有限域上的椭圆曲线有限域上的椭圆曲线定义定义 椭圆曲线上的加法：如果椭圆曲线上的三个点位于同一直线上，椭圆曲线上的加法：如果椭圆曲线上的三个点位于同一直线上，那么它们的和为那么它们的和为O O。从本定义导出一系列椭圆曲线上点的加法规则。从本定义导出一系列椭圆曲线上点的加法规则。O O为加法加法单位元，即位元，即对ECCECC上任一点上任一点P P，有，有P P+O O=P P。1 1）设P P1 1=(=(x x,y y)是是ECCECC上一点，加法逆元定上一点，加法逆元定义为P P2 2=-=-P P1 1=(=(x x,-,-y y)。2 2）P P1 1,P P2 2连线延延长到无到无穷远，得到，得到ECCECC上另一点上另一点O O，即，即P P1 1,P P2 2,O O三点共三点共线，所以有，所以有P P1 1+P P2 2+O O=O O，P P1 1+P P2 2=O O，P P2 2=-=-P P1 1，O O+O O=O O，O O=-=-O O。3 3）设Q Q,R R是是ECCECC上上x x坐标不同的两点，坐标不同的两点，Q Q+R R定义为：画一条通过定义为：画一条通过Q Q,R R的直线与的直线与ECCECC交于交于P P1 1（交点是唯一的，除非做的（交点是唯一的，除非做的Q Q,R R点的切线）。由点的切线）。由Q Q+R R+P P1=1=O O，得，得Q Q+R R=-=-P P1 1。椭圆曲线。椭圆曲线及及Q Q+R R的示意的示意如图所示如图所示。定义定义 点点Q Q的数量乘运算：在的数量乘运算：在Q Q点做点做ECCECC的一条切线，设切线与的一条切线，设切线与ECCECC交于交于S S，定义，定义2 2Q Q=Q Q+Q Q=-=-S S。类似可定义。类似可定义3 3Q Q=Q Q+Q Q+Q Q,*有限域上的椭圆曲线定义 椭圆曲线上的加法：如果椭圆曲线上的*l l有限域上的椭圆曲线有限域上的椭圆曲线有限域上的椭圆曲线有限域上的椭圆曲线【例例】设方程为设方程为 ，p=23，a=b=1，则有，则有 ，图形为连续图形。感兴趣的是在第一象限的整数点。设，图形为连续图形。感兴趣的是在第一象限的整数点。设 表示表示ECC上上点集点集(x，y)|0 xp,0yp，且，且x，y均为整数均为整数并上并上O，见下表。，见下表。表表 椭圆曲曲线上的点集上的点集(0,1)(0,22)(1,7)(1,16)(3,10)(3,13)(4,0)(5,4)(5,19)(6,4)(6,19)(7,11)(7,12)(9,7)(9,16)(11,3)(11,20)(12,4)(12,19)(13,7)(13,16)(17,3)(17,20)(18,3)(18,20)(19,5)(19,18)*有限域上的椭圆曲线【例】设方程为 *2.5 2.5 椭圆曲线椭圆曲线密码体制密码体制 l l 椭圆曲线椭圆曲线椭圆曲线椭圆曲线 l 有限域上的椭圆曲线有限域上的椭圆曲线 l l 椭圆曲线上的密码算法椭圆曲线上的密码算法椭圆曲线上的密码算法椭圆曲线上的密码算法 l l 椭圆曲线密码体制的安全性椭圆曲线密码体制的安全性椭圆曲线密码体制的安全性椭圆曲线密码体制的安全性*2.5 椭圆曲线密码体制 椭圆曲线 有*l l椭圆曲线上的密码算法椭圆曲线上的密码算法椭圆曲线上的密码算法椭圆曲线上的密码算法基于基于ECCECC的的Diffie-HellmanDiffie-Hellman密钥交换密钥交换 取一个大素数取一个大素数p p，两个参数，两个参数a a,b b，得到椭圆曲线，得到椭圆曲线 。取。取 的一个生的一个生成元成元 ，要求，要求G G的阶是一个非常大的素数（阶是满足的阶是一个非常大的素数（阶是满足nGnG=O O的最小正整数的最小正整数n n）。）。EpEp(a a,b b)和和G G公开。通信的双方公开。通信的双方A A和和B B密钥交换过程如下：密钥交换过程如下：l A A选小于选小于n n的整数的整数 作为秘密钥，并计算作为秘密钥，并计算 作为公钥。作为公钥。l B B类似选取自己的秘密钥类似选取自己的秘密钥 和公开钥和公开钥 。l A A和和B B分别计算分别计算 和和 产生共享的秘密钥。产生共享的秘密钥。*椭圆曲线上的密码算法基于ECC的Diffie-Hellma*