<4C332DBCD3C3DCCBE3B7A8BACDC3DCC2EBBCBCCAF550312E BBCE6C8DDC4A3CABD5D>

Size: px

Start display at page:

Download "<4C332DBCD3C3DCCBE3B7A8BACDC3DCC2EBBCBCCAF550312E BBCE6C8DDC4A3CABD5D>"

龟通
5 years ago
Views:

1 专业特色选修课网络信息安全 En/Decryption Algorithms and Cryptology 嵩天北京理工大学计算机学院

2 本节大纲密码学的基本概念对称密钥密码算法 2

3 密码学是一门历史悠久的学科 Cryptology,Cryptography,from Greek 密码技术是研究数据加密解密及变换的科学, 涉及数学计算机科学电子与通信等学科加密是把数据和信息转换为不可识别的密文的过程解密是恢复数据和信息本来面目的过程 3

4 密码学早在公元前 400 多年就已经产生希腊人把奴隶的头发剃光, 把秘密刺在头上, 等头发长起来了再派他上路斯巴达人采用羊皮条和木棍进行加密周朝六韬, 兵符, 藏头诗中国古代的江湖黑话挂彩蹓狗豆儿总瓢把子流月汪则中 4

5 古罗马 : 凯撒密码 (Caesar 密码 ) 字母表对应密文明文密文 ABCDEFGHIGKLMNOPQRSTUVWXYZ DEFGHIGKLMNOPQRSTUVWXYZABC Caesar was a great soldier Fdhvdu zdv d juhdw vroglhu CAESAR 密码 : c=( m+ 3) Mod 26 5

6 美国南北战争时期输入方向输出方向 C A N Y O U U N D E R S T A N D 明文 : Can you understand 密文 : Codtaueanurnynsd 6

7 第二次世界大战, 德国恩尼格玛 (Enigma) 密码机, 谜由 ArthurScherbius 于 1919 年发明,1925 年生产 3 万台 7

8 具有连线的三转子机器恩尼格玛 (Enigma) 密码机, 谜 8

9 艾伦图灵 (AlanTuring) 二战期间成功地破译了纳粹德国密码系统 Enigma 1912~1954, 英国数学家, 一生对智能与机器之间的关系进行着不懈探索, 被誉为计算机科学之父 1931~1934, 剑桥大学国王学院 ;1937~1938, 普林斯顿大学 1936 年,24 岁的图灵提出图灵机的设想机器会思考吗? 的论文提出了用于判定机器是否具有智能的试验方法, 即图灵试验, 被誉为人工智能之父 9

10 艾伦图灵 (AlanTuring) 1948 年, 奥运会马拉松项目银牌得主 1954 年 6 月 8 日, 服毒自杀,42 岁 1966 年, 美国计算机协会以他的名字命名了计算机领域的最高奖图灵奖 2000 年, 姚期智 Andrew Chi-Chih Yao 10

11 现代密码学随着电子计算机的诞生, 以语言学为基础的密码方法失效现代密码方法主要在二进制字串上进行密码方法所基于的问题只要被证明无法有效解出, 就是安全现代密码学的主要威胁 : 暴力破解的速度量子计算的发展 11

12 密码学的基本概念基本术语明文 :plaintext, 原有的信息密文 :ciphertext, 明文经过加密变换后的内容加密函数 :Encryption, 用来加密的数学函数解密函数 :Decryption, 用来解密的数学函数加密密钥 k 解密密钥 k -1 明文 P plaintext 加密函数 C=E K (P) 密文 C ciphertext 解密函数 P=D K -1 (C) 明文 P plaintext 12

13 密码算法的分类古典密码算法和现代密码算法根据算法和密钥是否分开来区分古典密码算法密码体制的安全性依赖于算法本身的保密性算法存在以下限制不适合大规模生产不适合较大的或者人员变动频繁的组织用户无法了解算法的安全性 13

14 密码算法的分类古典密码算法种类代码加密 : 代码指专有词汇或者特殊用语, 黑话替换加密 : 用一组密文字母代替一组明文字母, 但保持明文的顺序, 例如 : 凯撒密码变位加密 : 对明文字母作重新排序一次性加密 : 利用代码本, 结合上述方法, 用代码本上每一页加密明文的一个片段 14

15 密码算法的分类现代密码算法把算法和密钥分开密码算法可以公开, 密钥保密密码系统的安全性依赖于密钥的保密性优点包括 : 密码算法可以经过充分论证, 安全性有保证对密码系统的管理简单可应用于大规模场景 15

16 密码算法的分类对称密钥密码和非对称密钥密码根据加密和解密是否使用相同的密钥来区分对称密钥密码也成单钥体制,k=k -1 算法优点 k = k -1 加密速度快, 使用简单算法缺点 P C=E K (P) C P=DK -1 (C) P 密钥分配 : 必须通过保密通道进行密钥个数 :n 个用户需要 n(n-1) 个密钥 16

17 密码算法的分类非对称密钥密码公开密钥密码体制 (PKI-Public Key Infrastructure) 加密和解密使用不同的密钥 (k, k -1 ) 把加密密钥公开 ( 公钥 ), 解密密钥保密 ( 私钥 ) 对于每一个用户, 形成公私密钥对算法优点密钥分配 : 不必保持信道的保密性 k 密钥个数 :n 个用户需要 n 个密钥算法缺点 P C=E K (P) C k -1 P=DK -1 (C) P 算法速度 : 比对称密钥算法慢 10 倍左右 ( 软件 ) 17

18 密码算法的分类混合加密体系结合对称密钥密码和非对称密钥密码体系采用对称方法进行通信, 采用 PKI 体系进行密钥交换 P C=E K (P) C P=D K -1 (C) P k k -1 = k C=E PK (P) P=D PK -1 (C) pk -1 pk -1 18

19 密码算法的分类分组密码和序列密码根据每次操作的数据单元是否分块来区分分组密码 (BlockCipher) 一次加密或解密操作作用于一个数据块, 比如 64bit 数据块之间加密是独立的序列密码 (StreamCipher) 一次加密或解密操作作用于一位或者一个字节前部分密文参与后部分明文的加密, 数据块之间加密不独立 19

20 密码算法的分类双向加密和单向加密根据明文加密后是否需要还原来区分双向加密明文加密后, 需要解密, 目的是信息的交换单向加密明文加密后, 不需要解密, 目的验证数据的完整性 20

21 密码算法的分类古典密码算法和现代密码算法根据算法和密钥是否分开来区分对称密钥密码和非对称密钥密码根据加密和解密是否使用相同的密钥来区分分组密码和序列密码根据每次操作的数据单元是否分块来区分双向加密和单向加密根据明文加密后是否需要还原来区分 21

22 密码分析什么是密码分析? 未知密钥, 利用数学方法恢复明文, 或者推导出密钥对密码进行分析的尝试称为攻击或者破解对密码体系的攻击方法包括 : 暴力破解 : 对密钥进行穷尽搜索已经明文攻击 : 利用一段已知明文和密文的对应关系选定明文攻击 : 设法让对手加密一段选定的明文, 获得加密结果选定密文攻击 : 设法让对手回复一段的密文, 获得明文结果选定密钥攻击 : 用于分析密码算法和体系 22

23 密码分析其他密码攻击方法可以针对人机系统的弱点进行攻击, 而不是攻击密码算法本身欺骗用户密码 ( 技术手段或者社会工程学 ) 在用户输入密钥时, 窥视或者偷窃密钥内容利用密码系统实现中的缺陷或者漏洞妨碍用户正确使用密码系统让口令的另一方透露密钥和信息威胁用户交出密钥 23

24 密码分析密码算法的安全性如果破解算法的代价大于被加密数据本身的价值, 或者在信息的生命周期内无法破解, 那么算法可能是安全的如果一个密码算法用可得到的资源不能被破解, 则称该算法是计算上安全的处理复杂性 : 计算量 CPU 时间数据复杂性 : 所需输入的数据量存储复杂性 : 计算所需要的存储空间 24

25 本节大纲密码学的基本概念对称密钥密码算法 25

26 对称密钥密码算法常用的对称密钥密码算法 DES 3DES IDEA CAST-128 RC2 RC4 RC5 Blowfish 加密密钥 k AES 秘密通道分配密钥解密密钥 k 明文 P plaintext 加密函数 C=E K (P) 密文 C ciphertext 解密函数 P=D K -1 (C) 明文 P plaintext 26

27 DES 算法 DES,DataEncryptionStandard 20 世纪 70 年代,IBM 公司为美国国家标准局研制 1977 年成为美国国家标准,1998 年废弃 2001 年,DES 算法被安全性更强的 AES 算法所取代 DES 算法是一个分组加密算法, 以 64bit 为一个分组 DES 算法使用标准的算术和逻辑运算 27

28 DES 算法 DES 的总体框架明文分成 64bit 为单位的块 m 异或对于每个 m, 执行如下操作 : DES(m)=FP T 16 T T 2 T 1 IP(m) 初始置换 (Initial Permutation), IP 16 轮迭代,T i, i=1,2, 16 末置换 (Final Permutation),FP 28

29 DES 算法 DES 的初始置换和末置换 DES(m)=FP T 16 T T 2 T 1 IP(m) IP * FP = I, 即 FP = IP 1 对 m 中 64 个位置进行置换输入 :m = m 1 m 2 m 64 29

30 DES 算法 DES 的初始置换和末置换 m = m 1 m 2, m 62 m 63,m 64 IP(M) m =m 58 m 50, m 23 m 15,m

31 DES 算法每次迭代 32b L i-1 32b R i-1 E- 盒置换 48 S- 盒代替 K i ( 48bits) P- 盒置换 31 L i =R i-1 32b R i =L i-1 f (R i-1,k i ) 32b

32 DES 算法 E- 盒置换将 32 位扩展成 48 位目的 : 输入的一位影响下一步的两个替换, 使得输出对输入的依赖性传播得更快, 密文的每一位都依赖于明文的每一位

33 DES 算法 S- 盒置换将 48 位压缩成 32 位 S i 输入 6 位, 查表输出 4 位 E 48 bits R i-1 (32 bits) K i ( 48bits) S 1 S 2 S 3 S 4 S 5 S 6 S 7 S 8 33

34 DES 算法 P- 盒置换 32 位输入 32 位输出仅置换位置

35 DES 算法 DES 的解密过程 m = DES 1 (c) = IP 1 T 1 T 2...T 15 T 16 IP(c) DES 的解密过程与加密过程十分相似不同是, 将 16 次迭代的顺寻颠倒可以证明 DES 1 (DES (m) )=m 35

36 DES 算法 DES 的安全性 1976 年, 耗资 2000 万美元的计算机, 可以在一天中找到密钥 1993 年, 设计 100 万美元的计算机 3.5 小时用穷举法找到密钥 2006 年,1 万美元的计算机可以用 6.4 天可以找到密钥 DES 安全性不足源自于密钥太短 36

37 Triple DES 算法 TripleDES 算法 3DES 算法, 密钥长度是 112 比特,k=k 1 k 2 密钥数量 :2 112 m DES DES -1 DES c c k 1 k 2 k 1 DES -1 DES DES -1 m 37 k 1 k 2 k 1

38 DES 算法的硬件实现商业 DES 芯片 VLSI 公司的 VM009 芯片 1993 年制造,200M Bytes/s 2009 年, 采用 FPGA 技术, 速度可达到 750M Bytes/s 软件实现采用双核服务器, 速度约 19M Bytes/s 38

39 对称密钥密码算法算法密钥长度迭代次数数学操作应用 DES XOR,S-Box 3DES 112or XOR,S-Box PGP,S/MIME IDEA XOR,+, PGP BlowFish 最大 XOR,S-Box,+ RC5 最大 2048 <255 +,,XOR CAST ,,S-Box PGP 39

40 RC4 算法算法历史 RC4 是 RSA 算法发明人 Ronald Rivest 在 1987 年设计 2002 年图灵奖获得者 Ron s Code 4 (Rivest Cipher 4), RC2, RC5, RC6 密钥长度可变的流加密算法簇其核心部分的 S Box 长度可为任意, 但一般为 256 字节该算法速度是 DES 算法的 10 倍 40

41 RC4 算法算法思想 RC4 产生一个伪随机 bit 流, 与输入流明文逐位异或解密时, 用密文与伪随机 bit 流逐位异或产生明文异或操作具有对称性 : 0 x 1 x 1 = 0 ; 0 x 0 x 0 = 0; 1 x 1 x 1 = 1 ; 1 x 0 x 0 = 1 RC4 算法关键是根据密钥产生伪随机 bit 流使用了一个 256 位的转换器 (S BOX) 两个指针 41

42 RC4 算法密钥的使用 ( 密钥调度算法 ) 对于变长密钥, 应用它置换 S BOX 伪代码, 其中 S 为一个字节数组 42

43 RC4 算法伪随机流产生算法 RPGA: pseudo random generation algorithm 每周期 i 增加 1, j 增加 S[i], 每次运算可输出一个 Byte 43

44 RC4 算法伪随机流产生算法 44

45 本节小结经过本节的学习, 我们知道密码学悠久的历史密码学的分类对称密钥密码算法 DES 3DES RC4 算法请大家复习课件内容 45

幻灯片 1

幻灯片 1 背景介绍与复习移位密码仿射密码课堂练习 2 信息加密的重要性战场商业竞争日常生活 3 藏头诗芦花丛里一扁舟俊杰俄从此地游义士若能知此理反躬逃难可无忧 4 反清复明 5 列宁的六个墨水瓶 6 凯撒密码恺撒大帝 7 凯撒密码 L O R Y H X 密文 I L O V E U 明文 A B C D E F G H I J K L M N O P Q R S T U V W X Y Z