保密安全与密码技术密码学.ppt

保密安全与密码技术 第二讲密码学基础 密码学概论古典密码学现代密码学对称密码学非对称密码学单向散列数字签名数字信封 密码学基础 通信模型基本概念和术语密码算法分类密码发展历史密码分析密码技术的用途 密码学概论 通信模型 密码学一门研究通信安全和保护信息资源的既古老而又年轻的科学和技术密码编码学对信息编码以隐蔽信息的一门学问密码分析学研究分析破译密码的学问这二者既相互对立又相互促进 共同推动密码学的发展 基本概念 明文 plaintext 需要秘密传送的消息 M 密文 ciphertext 明文经过密码变换后的消息 C 加密 encrypt encryption 由明文到密文的变换 解密 decrypt decryption 从密文恢复出明文的过程 破译 非法接收者试图从密文分析出明文的过程 密钥 Key 加密和解密时使用的一组秘密信息 k 加密算法 EncryptAlgorithm 对明文进行加密时采用的一组规则 E M 解密算法 DecryptAlgorithm 对密文进行解密时采用的一组规则 D C C E M M D C D E M M 基本术语 定义 密码体制是一个五元组 M C K E D 满足条件 M是可能明文的有限集 明文空间 C是可能密文的有限集 密文空间 K是一切可能密钥构成的有限集 密钥空间 任意 有一个加密算法和相应的解密算法 使得和分别为加密解密函数 满足 基本概念和术语 注 1 Alice要将明文 在不安全信道上发给Bob 设X x1x2 xn 其中 Alice用加密算法ek作yi ek xi 1 i n结果的密文是Y y1y2 yn 在信道上发送 Bob收到后解密 xi dk yi 得到明文X x1x2 xn 2 加密函数ek必须是单射函数 就是一对一的函数 3 若M C 则ek为一个置换 4 好的密钥算法是唯密钥而保密的 5 若Alice和Bob在一次通信中使用相同的密钥 那么这个加密体制为对称的 否则称为非对称的 基本概念和术语 基本概念和术语 古典密码算法和现代密码算法按照算法和密钥是否分开对称密钥密码和非对称密钥密码加密和解密是否使用相同的密钥分组密码和序列密码每次操作的数据单元是否分块 密码算法的分类 古典密码和现代密码 古典密码代替密码 SubstitutionCipher 换位密码 transpositionCipher 代替密码与换位密码的组合古典密码 受限密码 的缺陷密码体制的安全性在于保持算法本身的保密性受限算法的缺陷不适合大规模生产不适合较大的或者人员变动较大的组织用户无法了解算法的安全性 现代密码算法把算法和密钥分开密码算法可以公开 密钥保密密码系统的安全性在于保持密钥的保密性 发送方 接收方 M M 加密E 解密D C Ek M M Ek C 密码分析 密钥分配 秘密信道 k k 古典密码和现代密码 对称密码算法和非对称密码算法 对称密钥密码算法 又称传统密码算法 秘密密钥密码算法加密和解密使用相同的密钥Ke Kd常用算法 DES IDEA Blowfish RC2等优点加密速度快 便于硬件实现和大规模生产缺点密钥分配 必须通过保密的信道密钥个数 n n 1 2无法用来签名和抗抵赖 没有第三方公证时 对称密码和非对称密码 非对称密码 又称公开密钥密码算法加密和解密使用不同的密钥 Kp Ks 把加密密钥公开 解密密钥保密 c EKp m m DKs c 常用算法 RSA DSA 背包算法 ElGamal 椭圆曲线等优点 密钥分配 不必保持信道的保密性密钥个数 n对可以用来签名和抗抵赖缺点加密速度慢 不便于硬件实现和大规模生产 分组密码和序列密码 分组密码 BlockCipher 一次加密或解密操作作用于一个数据块 比如64位序列密码 StreamCipher 一次加密或解密操作作用于一位或者一个字节 早在4000多年以前 古埃及人就在墓志铭中使用过类似于象形文字那样奇妙的符号公元前约50年 凯撒密码 一种简单的字符替换 被认为是最早的正式算法 双轨式密码 网格式密码 字典编号密码传统密码学 现代密码学 量子密码学 发展历史 密码分析 在未知密钥的前提下 从密文恢复出明文 或者推导出密钥对密码进行分析的尝试称为攻击攻击方法分类 根据已知信息量的多少 唯密文攻击已知明文攻击选择明文攻击自适应选择明文攻击选择密文攻击选择密钥攻击 密码算法的安全性如果破译算法的代价大于加密数据本身的价值 或者在信息的生命期内无法破解 那么你的算法可能是安全的 一个算法被称为是计算上安全的 如果一个算法用可得到的资源不能破解 处理复杂性 计算量 CPU时间数据复杂性 所需输入数据量存储复杂性 计算所需的存储空间 密码分析 密码技术的主要用途 数据保密 数据加密 解密数据加密 存储和传输 认证技术实体身份认证数据源发认证信息完整性保护数据在传输过程中没有被插入 篡改 重发 数字签名和抗抵赖 Non repudiation 源发抗抵赖交付抗抵赖 通信模型基本概念和术语密码算法分类密码发展历史密码分析密码技术的用途 密码学概论 分组学习现代密码学的各种密码算法内容 对称密码学 IDEA SDBI AES RC5 CAST 256非对称 DSA ECC D H单向散列 SHA1 RIPE MD要求 PPT报告 代表讲解 3 5分钟 第一次作业 古典密码学 古典密码学的起源早期的密码 隐写术代换密码术置换密码术古典密码学的优缺点 古典密码学的起源 战争 古罗马 Caesar密码 ABCDEFGHIGKLMNOPQRSTUVWXYZ DEFGHIGKLMNOPQRSTUVWXYZABC Caesarwasagreatsoldier 密码本 密文 Fdhvduzdvdjuhdwvroglhu 明文 密文 CAESAR密码 c m 3 Mod26 每一个加密函数ek和每一个解密函数dk都能有效地计算 破译者取得密文后 将不能在有效的时间内破解出密钥k或明文x 一个密码体制是安全的必要条件穷举密钥搜索将是不可行的 即密钥空间将是非常大的 古典密码学的起源 战争 美国南北战争 输入方向 输出方向 明文 Canyouunderstand密文 codtaueanurnynsd 古典密码学的起源 战争 转轮密码机ENIGMA 由ArthurScherbius于1919年发明 4轮ENIGMA在1944年装备德国海军 古典密码学的起源 战争 英国的TYPEX打字密码机 是德国3轮ENIGMA的改进型密码机 它在英国通信中使用广泛 且在破译密钥后帮助破解德国信号 古典密码学的起源 战争 一个简单的加密算法 异或 一个简单的加密算法 异或 已知明文 密文 怎样求得密钥 只知道密文 如何求得密文和密钥 定义 将秘密信息隐藏在其余信息中举例隐型墨水字符格式转换图像隐藏信息隐藏 古典密码学 隐写术 字母对数字ABCDEFGHIJKLMNOP0123456789101112131415QRSTUVWXYZ16171819202122232425破解 81114214241420 代换密码 移位密码 ShiftCipher ABCDEFGHIJKLMNOPQRSTUVWXYZDEFGHIJKLMNOPQRSTUVWXYZABC破解 FDHVDUZDVDJUHDWVROGLHU移位密码 令P C Z26 0 K 26 对于任意的x y在Z26内 有 Ek x x K mod26 以及Dk y y K mod26 称K是该加密方法的密钥 代换密码 例 假设移位密码的密钥为K 11 明文为Wewillmeetatmidnight 首先将明文中的字母对应于其相应的整数 得到如下数字串 224228111112441901912831386719然后将每一数都与11相加 再对其和取模26运算 可得 1571922222315154114231914241917184最后 再将其转换为相应的字母串 即得密文 HPHTWWXPPELEXTOYTRSE 要对密文进行解密 只需执行相应的逆过程即可 Bob首先将密文转换为数字 再用每个数字减去11后取模26运算 最后将相应的数字再转换为字母可得明文 移位密码 例设有如下密文串JBCRCLQRWCRVNBJENBWRWN 依次试验所有可能的解密密钥 可得如下不同字母串 iabqbkpqvbqumaidmavqvmhzapajopuaptlzhclzupulgyzozinotzoskygbkytotkfxynyhmnsynrjxfajxsnsjewxmxglmrxmqiweziwrmridvwlwfklqwlphvdyhvqlqhcuvkvejkpvkogucxgupkpgbtujudijoujnftbwftojofastitchintimesavesnine至此 已得出有意义的明文 相应的密钥K 9 平均来看 使用上述方法计算明文只需试验26 2 13次即可 上面的例子表明 一个密码体制安全的必要条件是能抵抗穷尽密钥搜索攻击 普通的做法是密钥空间必须足够大 但是 很大的密钥空间并不是保证密码体制安全的充分条件 移位密码 abcdefghijklmnopqrstuvwxyzXNYAHPOGZQWBTSFLRCVMUEKJDI请解密 MGZVYZLGHCMHJMYXSSFMNHAHYCDLMHA代换密码的一个密钥刚好对应于26个英文字母的一种代换 所有可能的置换有26 种 这个数值超过4 1026次方 是一个很大的数 因此 采用穷尽密钥搜索的攻击方法 即使使用计算机 也是计算上不可行的 但是 后面我们将看到 采用别的密码分析方法 代换密码可以很容易地被攻破 代换密码 代换密码分析 元音字母用得较多 其中e i较多 辅音中r t使用较多字母组合ere er等试分析下列密文 BMZALXLBYJBVALXZLRZBJHGKLJXSVZBZB5Z4A2L5X3J3V2BMZALXLBYJBVALXZLRZBJHGKLJXSVZBZIfthereisciphertextIcandecryptit密码表 ABCDEFGHIJKLMNOPQRSTUVWXYZHIJKLMNABCDEFGUVWXYZOPQRST 代换密码分析 对明文的所有字母都用一个固定的明文字母表到密文字母表的映射单表代换密码不能非常有效地抵抗密码攻击 因为语言的特征仍能从密文中提取出来移位密码 替换密码 仿射密码多表代换密码以一系列 两个以上 代换表依次对明文消息的字母进行代换的加密方法若待换序列是非周期的无限序列 则相应的密码称为非周期多表代换密码 这类密码 对每个明文字母都采用不同的代换表 或密钥 进行加密 称作一次一密密码 One timepadcipher 这是一种理论上唯一不可破的密码Vigen re 轮转机 Rotormachine 等 代换密码 保持明文字符未改变 但通过重排而更改他们位置 所以有时也称为换位密码 栅栏式密码美国南北战争时期 1861 1865年 军队中曾经使用过的 栅栏 式密码 railfencecipher 原理明文 sendhelp加密过程 snhledep密文 snhledep 置换密码 矩阵置换换位密码把明文按列写入 按行读出密钥包含3方面信息 行宽 列高 读出顺序key 5353142ciphertext SARATACETHNKITEplaintext SARATTRSAAACETHHEATCNKITEEINTKThereisanattack 置换密码 古典密码学 已经成为历史 但被传统密码学所借鉴加解密都很简单 易被攻破采用手动或机械的方式加解密 不适合大规模的数据传输 属于对称密钥学 对称密码学非对称密码学单向散列数字签名数字信封 现代密码学 原理加密和解密使用同一个密钥信息的发送方和接收方必须共享一个密钥示意图 对称密码学 主要算法DES 3DES IDEA SDBI AES RC5 CAST 256优缺点简单 速度快能力有限 密钥交换困难实例DES 对称密码学 DES加密算法的背景 发明人 美国IBM公司W Tuchman和C Meyer1971 1972年研制成功 产生 美国国家标准局 NBS 1973年5月到1974年8月两次发布通告 公开征求用于电子计算机的加密算法 经评选从一大批算法中采纳了IBM的LUCIFER方案 标准化 DES算法1975年3月公开发表 1977年1月15日由美国国家标准局颁布为数据加密标准 DataEncryptionStandard 于1977年7月15日生效 DES算法原理 DES是一种对称密钥算法 密钥长度为56bits 加上奇偶校验 通常写成64bits 是一种分组加密算法 64bits为一个分组基本思想 置乱 Confusion 和扩散 Diffusion 使用标准的算术和逻辑运算 DES加密过程 首先把明文分成以64bit为单位的块m 对于每个m 执行如下操作DES m IP 1 T16 T15 T2 T1 IP m 初始置换 IP16轮迭代 Ti i 1 2 16末置换 IP 1 数据加密标准DES 数据加密标准DES 初始换位 IP 初始换位 IP M m1m2 m62m63 m64 M m58m50 m23m15 m7 IP M 一轮迭代 Li 1 Ri 1 Li Ri 1 Ri Li 1f Ri 1 Ki Ki 48bits 32bits 32bits 32bits E 盒置换 S 盒代替 P 盒置换 32bits f 48 32 扩展置换 E 盒置换 将Ri从32位扩展到48位目的 输入的一位影响下一步的两个替换 使得输出对输入的依赖性传播得更快 密文的每一位都依赖于明文的每一位 1234 5678 1234 5678 32 48 321234545678989 31321 1234567891011121314 464748 S 盒置换 将48比特压缩成32比特 E S1 S2 S3 S4 S5 S6 Ri 1 32bits Ki 48bits 48bits S7 S8 S 盒置换 输入6比特 b1b2b3b4b5b6输出4比特 S b1b6 b2b3b4b5 S1 b1b2b3b4b5b6 举例 S1 100110 1000 P 盒置换 32比特输入 32比特输出 P 盒的输出 子密钥的生成 PC 1 C0 D0 LS1 LS1 C1 D1 LS2 LS2 C2 D2 LS16 LS16 C16 D16 PC 2 K1 48bits 密钥K 64bits 28 28 PC 2 K2 48bits PC 2 K16 48bits 子密钥生成 Ci Di 移位 LS 移位 压缩置换 PC Ci 1 Di 1 Ki 子密钥生成 拆分 56bits的密钥分成两部分 Ci Di 各28bits循环左移 根据迭代的轮数 分别左移一位或两位 压缩置换 置换选择 从56bits中选择48bits 末置换 末置换 初始置换 IP 1 IP M M DES解密过程 DES解密过程与加密过程完全相似 只不过将16次迭代的子密钥顺序倒过来 即m DES 1 c IP 1 T16 T15 T2 T1 IP c 可以证明 DES DES 1 m m DES的算法模式 电子密码本 ElectronicCodeBook ECB 密码分组链 CipherBlockChaining CBC 密文反馈 CipherFeedBack CFB 输出反馈 OutputFeedBack OFB 电子密码本模式 ECB 基本的DES算法就是ECB模式相同的输入永远产生相同的输出相当于加密 解密双方各有一个密码本 对于一个密钥 密码本有264个表项存在重放 Replay 类型的攻击 特别是对于结构化的报文 攻击者可以在不知道密钥的情况下修改被加密过的消息 密码分组链模式 CBC Ek Ek Pi 1 Pi Ek Pi 1 Ek Ci 1 Ek Ci 1 Ek Ci 1 Ci 1 Ci Ci 1 Pi 1 Pi Pi 1 IV DES的安全性和速度 弱密钥产生的子密钥相同 4个 如0000 00 11111 111 0101010101 01 101010 10半弱密钥用不同的密钥加密产生相同的密文 即用一个密钥加密的信息可以用其他密钥解开 12个密钥的长度1976年 耗资2000万美元的计算机 可以在一天中找到密钥 1993年 设计100万美元的计算机 3 5小时用穷举法找到密钥 DES的变形 三重DES加密 密钥长度为112比特 k k1k2 DES DES 1 DES DES 1 DES DES 1 m m c c k1 k2 k1 k1 k2 k1 密钥长度2112 软硬件实现的速度 硬件实现 商业DES芯片VLSI公司VM0091993年制造200MBytes s软件实现 80486 CPU66Hz 每秒加密43000个DES分组 336KBytes sHP9000 887 CPU125Hz 每秒加密196 000个分组 1 53MBytes s DES算法的公开性与脆弱性 DES的两个主要弱点 密钥容量 56位不太可能提供足够的安全性S盒 可能隐含有陷井 Hiddentrapdoors DES的半公开性 S盒的设计原理至今未公布报告表明S盒在次序上 内容上是最优的 DES算法存在的问题与挑战 强力攻击 255次尝试差分密码分析法 247次尝试线性密码分析法 243次尝试 对DES攻击结果及其启示 1997年1月28日美国RSA数据安全公司悬赏 秘密密钥挑战 竞赛48位的RC5313小时 3500台计算机1997年3月13日RockeVerser设计一个攻击程序 DESCHALL 参加的志愿者有78516个 第96天 6月17日晚10 39 MichaelSanders破译成功 获1万美圆奖金 搜索量为24 6 密钥长度 bit 穷举时间4078秒485小时5659天6441年7210 696年802 738 199年88700 978 948年96179 450 610 898年11211 760 475 235 863 837年128770 734 505 057 572 442 069年 DESCHALL搜索速度估算 其他密码算法 主要算法DES 3DES IDEA SDBI AES RC5 CAST 256优缺点简单 速度快能力有限 密钥交换困难实例DES 对称密码学 原理加密和解密使用不同的密钥一对密钥 公钥与私钥示意图 非对称密码学 主要算法RSA DSA EIGamal ECC D H优缺点复杂 速度慢密钥交换简单 可用于身份鉴别实例RSA 非对称密码学 RSA算法简介 RonRivest AdiShamir LeonardAdlemanRSA的安全性基于大数分解的难度RSA在美国申请了专利 已经过期 在其他国家没有RSA已经成了事实上的工业标准 在美国除外 数论基础 a与b的最大公因数 gcd a b gcd 20 24 4 gcd 15 16 1如果gcd a b 1 称a与b互素模运算moda qn r0 r n q a n x 表示小于或等于x的最大整数a a n n amodn r mmodn如果 amodn bmodn 则称a与b模n同余 记为a bmodn例如 23 8mod5 8 1mod7 数论基础 模运算是可交换的 可结合的 可分配的 a b modn amodn bmodn modn a b modn amodn bmodn modn a b modn amodn bmodn modn a b c modn a b modn a c modn 幂 模运算mamodn m2modn m m modn mmodn 2modnm4modn m2modn 2modnm8modn m2modn 2modn 2modnm25modn m m8 m16 modn 数论基础 欧拉函数 n n是正整数 n 是比n小且与n互素的正整数的个数 3 1 2 2 4 1 3 2 5 1 2 3 4 4 6 1 5 4 7 1 2 3 4 5 6 6 10 1 3 7 9 4 11 1 2 3 4 5 6 7 8 9 10 10如果p是素数 则 p p 1 比如 2 5 11 如果p q是素数 则 pq p q p 1 q 1 比如 10 数论基础 例如 m 3 n 10 10 4m n 34 8181mod10 1即 m n 34 81 1mod10m n 1 34 1 243 3mod10 欧拉定理 若整数m和n互素 则 等价形式 数论基础 推论 给定两个素数p q 两个整数n m 使得n pq 0 m n 则对于任意整数k 下列关系成立 mk n 1 mmodn RSA算法操作过程 密钥产生1 取两个大素数p q 保密 2 计算n pq 公开n 3 计算欧拉函数 n p 1 q 1 4 任意取一个与 n 互素的小整数e 即gcd e n 1 1 e n e作为公钥公开 5 寻找d 使得de 1mod n ed k n 1 d作为私钥保密 p 7 q 17 n 119 n 96 选择e 5 5d k 96 1 令k 4 得到求得d 77 RSA算法加密 解密过程 密钥对 KU KR KU e n KR d n 加密过程把待加密的内容分成k比特的分组 k log2n 并写成数字 设为M 则 C Memodn解密过程M Cdmodn 5 119 77 119 c m5mod119 m c77mod119 RSA加密过程举例 p 7 q 17 n 7 17 119 n 7 1 17 1 96选e 5 gcd e n gcd 5 96 1 寻找d 使得ed 1mod96 即ed k 96 1 取d 77公开 e n 79 119 将d保密 丢弃p q 加密 m 19195 66mod119 c 66解密 6677mod119 19 RSA算法的安全性 攻击方法蛮力攻击 对所有密钥都进行尝试数学攻击 等效于对两个素数乘积 n 的因子分解大数的因子分解是数论中的一个难题 因子分解的进展 RSA算法的性能 速度软件实现比DES慢100倍硬件实现比DES慢1000倍 Diffie Hellman密钥交换算法 第一个发表的公开密钥算法 1976用于通信双方安全地协商一个会话密钥只能用于密钥交换基于离散对数计算的困难性主要是模幂运算apmodn 其他公钥密码算法 DSA1991年 NIST提出了数字签名算法 DSA 并把它用户数字签名标准 DSS 只能用于数字签名算法的安全性也是基于离散对数的难度招致大量的反对 理由如下 DSA不能用于加密或密钥分配DSA是由NSA研制的 可能有后门DSA的选择过程不公开 提供的分析时间不充分DSA比RSA慢 10 40倍 密钥长度太小 512位 DSA可能侵犯其他专利RSA是事实上的标准 其他公钥密码算法 椭圆曲线密码系统有限域GF 2n 运算器容易构造加密速度快更小的密钥长度实现同等的安全性 主要算法RSA DSA EIGamal ECC D H优缺点复杂 速度慢密钥交换简单 可用于身份鉴别实例RSA 非对称密码学 原理 对要传输的数据作运算生成信息摘要 产生信息的数字 指纹 主要算法 MD2 MD5 SHA1 RIPE MD目的确保数据没有被修改或变化保证信息的完整性不被破坏特点输入信息长度任意 输出信息长度固定给定输入信息 计算输出容易不可预见 完全不可逆 单向散列 单向散列 Hash 哈希函数 杂凑函数 散列函数h H m H具有如下特性 1 可以操作任何大小的报文m 2 给定任意长度的m 产生的h的长度固定 3 给定m计算h H m 是容易的 4 给定h 寻找m 使得H m h是困难的 5 给定m 要找到m m m且H m H m 是计算上不可行的 6 寻找任何 x y x y 使得H x H y 是计算上不可行的 简单的散列函数 纵向的奇偶校验码 Ci bi1bi2 bim MD5算法简介 RonRivest设计 RFC1321经历过MD2 MD4不同的版本对任意输入均产生128bit的输出基于32位的简单操作 易于软件实现简单而紧凑 没有复杂的程序和大数据结构适合微处理器实现 特别是Intel MD5产生报文摘要的过程 报文m 1000 0 长度 Y0 Y1 Yq YL 1 MD5 MD5 MD