02现代密码学理论与实践--传统加密技术

1 .现代密码学理论与实践 第 2 章 传统加密技术 Fifth Edition by William Stallings 苗付友 mfy@ustc.edu.cn 2018 年 9 月

2 .Part One–Symmetric Ciphers Road Map for Part One Chp.2, Classical Encryption Techniques Chp.3, Block Cipher and the Data Encryption Standard Chp.4, Finite Fields Chp.5, Advanced Encryption Standard Chp.6, More on Symmetric Ciphers Chp.7, Confidentiality Using Symmetric Encryption

3 .主要内容 2.0 概述 2.1 对称密码系统模型 2.2 代换密码 (Substitution Ciphers ) 2.3 置换密码 ( Transposition Ciphers) 2.4 转轮密码机 (Rotor Machines) 2.5 破解 Enigma

4 .密码学近现代演变过程 (1) 1918, William Friedman’s The Index of Coincidence and its Applications in Cryptography William Frederick Friedman (Sept. 24,1891 – Nov. 12, 1969) 美国陆军密码专家。 1930 年代，他领导了陆军的一个研究部门 Signals Intelligence Service (SIS) ，其中一部分服务一直延续到五十年代。三十年代晚期，在他的指导下， Frank Rowlett 破解了日本人的 PURPLE 加密机 ( 紫密 ) ，截获了日本的大量外交和军事的秘密。

5 .密码学近现代演变过程 (2) 1948, Claude Shannon’s 发表“ The Communication Theory of Secrecy System” ，成为 现代密码学理论基础 Claude Elwood Shannon (Apr. 30, 1916 – Feb. 24, 2001), 美国电气工程师和数学家，被誉为信息论之父 "the father of information theory". 香农之著名在于他以 1948 年发表的那篇旷世论文而奠定了现代信息论基础。其实早在 1937 年 , 当 21 岁的香农还是 MIT 的硕士研究生时，他便在他的硕士论文中论述了布尔代数的电子实现和应用，可以构建和解决任何逻辑的和数字的关系，因此奠定了数字计算机和数字电路设计理论的基础。他的硕士论文一直被认为是迄今最重要的硕士论文。 1949-1967 ，密码学研究处于沉寂时期

6 .密码学近现代演变过程 (3) 1971, IBM 发明 Luciffer Cipher, 128 位密钥作分组加密。这项发明是 由密码学家 Horst Feistel (Jan.30, 1915–Nov.14, 1990) 领导，当时在 IBM 负责设计加密器，他的工作最终激发了 70 年代 Data Encryption Standard (DES) 的研发高潮 1976-1977 ，美国国家标准局正式公布实施 DES 1975, Whitfield Diffie 和 Matin Hellman, 发表 A New Direction in Cryptography, 首次提出适应网络保密通信的 公开密钥 思想，揭开现代密码学研究的序幕，具有划时代的意义

7 .密码学近现代演变过程 (4) 1977 － 1978 ， Ronald Rivest , Adi Shamir, Len Adleman 第一次提出公开密钥密码系统的实现方法 RSA 1981 ，成立 International Association for Cryptology Research 1985 ， Abbas El Gamal 提出概率密码系统 ElGamal 方法 1990 － 1992 ， Lai Xuejia and James: IDEA, The International Data Encryption Algorithm 2000, AES, Advanced Encryption Standard

8 .2004 年 8 月，王晓云 破译 MD5 、 HAVAL － 128 、 MD4 和 RIPEMD 等四个 著名哈希算法 2005 年 2 月 7 日，美国国家标准技术研究院发表申明， SHA － 1 没有被攻破，并且没有足够的理由怀疑它会很快被攻破，开发人员在 2010 年前应该转向更为安全的 SHA － 256 和 SHA － 512 算法。而仅仅在一周之后，王小云就宣布了破译 SHA － 1 的 消息。 。。。。 密码学近现代演变过程 (5)

9 .来自量子算法的挑战 1994 年，Peter Shor发明量子 算法（Shor 算法 ) 实现 整数 的质因数 分解 复杂度 O(( logN ) 3 ) Grover 量子搜索 算法能够 实现在未整理数据库中对满足条件的目标成功搜索，并使计算复杂度由经典搜索算法 的 O(N ) 降低为 O (N 1/2 ). 后量子 时代密码学 Hash-based Digital Signature Schemes Code-based cryptography Lattice-based Cryptography Multivariate Public Key Cryptography 。。。 密码学近现代演变过程 (6)

10 .密码编码学 (Cryptography) 密码编码系统根据以下三个独立方面进行分类 用于将明文转换为密文的操作类型：代换和置换 所使用的密钥的数量和方式： 对称密码体制 ( 单钥系统、秘密密钥系统 ) 非对称密码体制 ( 双钥系统、公开密钥系统 ) 明文的处理方式：分组加密和流加密 密码分析学 (Cryptanalysis) 密码分析：试图破译密文得到明文或试图获得密钥的过程为密码分析，密码破译的策略取决于 加密方法 及 可供破译者使用的信息。 穷举攻击：对密文尝试所有可能的密钥，直到把它转化为可读的有意义的明文，平均要尝试 1/2 所有可能的密钥。 Cryptology 密码学

11 .Cryptology( 保密学 ) ，源自希腊语 (Greek) Kryptós: hidden; logos: word, 是密码学和密码处理过程的研究 Cryptography: The Science and Study of Secret Writing ，密码编码学 Cryptanalysis: The Science and Study of Secret Breaking ，密码破译学 Cipher: A secret method of writing 加密方法 Encipher (encipherment), encryption: 将明文转换成密文的过程 Decipher (decipherment), decryption: 将密文还原成明文的过程 Plaintext (cleartext): 原始的可读数据，明文 Ciphertext (Cryptogram): 加密后的不可解读之文件，密文 Key: 密钥，对加密与解密过程进行控制的参数 E(m): Encryption Transformation 加密变换 D(c): Decryption Transformation 解密变换 密码学基本术语 Terminologies

12 .什么是密码？简单地说它就是一组含有参数 K 的变换 E 。设已知消息 m ，通过变换 E k 得密文 C ，这个过程称为加密， E 为加密算法， k 不同，密文 C 亦不同。传统的保密通信机制： Encipher Plaintext Ciphertext Keys Decipher C=E k (m) 发方 ： m 收方 ： m k k （公共信道） 加密 E 解密 D （秘密信道） 简单加密系统模型

13 .加密的基本概念 密码体制 加密系统采用的基本工作方式称为密码体制，密码体制的基本要素是密码算法和密钥。密码算法是一些公式、法则或程序；密钥是密码算法中的控制参数。 加密系统可以用数学符号来描述： S ＝ {P, C, K, E, D} P ：明文空间 C ：密文空间 K ：密钥空间 E ：加密变换 D ：解密变换 k∈K ， 则有 C ＝ E k (P) ， P ＝ D k (C) ＝ D k ( E k (P)) ， 或者 D k ＝ E k -1 ，且 E k ＝ D k -1 。

14 .理论安全，或无条件安全 Theoretical Secure (or Perfect Secure) 攻击者无论截获多少密文，都无法得到足够的信息来唯一地决定明文。 Shannon 用理论证明：欲达理论安全，加密密钥长度必须大于等于明文长度，密钥只用一次，用完即丢，即一次一密， One-time Pad ，大批量数据加密 - 不实用。 实际安全，或计算上安全 Practical Secure (or Computationally Secure) 如果攻击者拥有无限资源，任何密码系统都是可以被破译的；但是在有限的资源范围内，攻击者都不能通过系统的分析方法来破解系统，则称这个系统是计算上安全的或破译这个系统是计算上不可行 (Computationally Infeasible) 。 理论安全和实际安全

15 .对称密码体制 (Symmetric System, One-key System, Secret-key System) 加密密钥和解密密钥相同，或者一个密钥可以从另一个导出，能加密就能解密，加密能力和解密能力是结合在一起的，开放性差。 非对称密码体制 (Asymmetric System, Two-key System, Public-key System) 加密密钥和解密密钥不相同，从一个密钥导出另一个密钥是计算上不可行的，加密能力和解密能力是分开的，开放性好。 对称密码体制和非对称密码体制

16 .序列密码 如果密文不仅与最初给定的算法和密钥有关，同时也与明文位置有关 ( 是所处位置的函数 ) ，则称为序列密码体制。加密以明文比特为单位，以伪随机序列与明文序列模 2 加后，作为密文序列。 分组密码 如果经过加密所得到的密文仅与给定的密码算法和密钥有关，与被处理的明文数据在整个明文中的位置无关，则称为分组密码体制。通常以大于等于 64 位的数据块为单位，加密得相同长度的密文。 序列密码体制和分组密码体制

17 .确定型密码体制和概率密码体制 确定型：当明文和密钥确定后，密文也就唯一地确定了； 概率型：当明文和密钥确定后，密文通过客观随机因素从一个密文集合中产生，密文形式不确定，称为概率型密码体制。 单向函数型密码体制和双向变换型密码体制 单向函数型密码体制适用于不需要解密的场合，容易将明文加密成密文，如哈希函数； 双向变换型密码体制可以进行可逆的加密、解密变换。 其他加密体制

18 .加密算法的选择 公开发表的加密算法、政府指定的加密算法、著名厂家产品、专家推荐的加密算法 通信信道的加密 链路加密－点到点加密 高层连接加密－端到端加密 存储数据的加密 硬盘级加密和文件级加密 加密的应用

19 .现代密码学的基本原则 设计加密系统时，总是假定密码算法是可以公开的，需要保密的是密钥。一个密码系统的安全性不在算法的保密，而在于密钥，即 Kerckhoff 原则。 ? 对加密系统的要求 系统应该是 实际上安全 的 (practical secure) ，截获密文或已知明文－密文对时，要决定密钥或任意明文在计算上是不可行的。 加密解密算法适用于密钥空间中的所有元素。 系统易于 实现 ，使用方便。 系统的安全性 不依赖 于对 加密体制或加密算法的保密 ，而依赖于 密钥 。 系统的应用不应使通信网络的 效率 过分降低。 现代密码学基本原则及加密系统要求

20 .对称加密系统由以下五部分组成 Plaintext ： 明文 Encryption algorithm ：加密算法 Key ： 密钥 Ciphertext ：密文 Decryption algorithm ：解密算法 加密算法必须足够强大，使破译者不能仅根据密文破译消息 收发双方必须在某种安全的形式下获得密钥并必须保证密钥的安全 2.1 对称密码系统的模型

21 .传统密码的简化模型

22 .对称密码系统的要求 使用对称密码系统有两个基本要求 一个强加密算法 一个只有发送方和接收方知道的秘密密钥 Y = E K ( X ) X = D K ( Y ) 必须假定加密算法是公开的 因此必须有安全的途径或信道分发密钥

23 .传统密码体制的模型 Y = E k (X) X = D k (Y)

24 .对加密信息的攻击类型 唯密文攻击 only know algorithm and ciphertext 已知明文攻击 know/suspect plaintext and ciphertext 选择明文攻击 select plaintext and obtain ciphertext 选择密文攻击 select ciphertext and obtain plaintext CCA-I /CCA-II 选择文本攻击 select plaintext or ciphertext to en/decrypt

25 .

26 .穷举攻击 总是可以简单地尝试每一个可能的密钥 穷举攻击是最基本的攻击，难度与密钥长度成正比 平均来说要获得成功必须尝试所有可能密钥的一半

27 .代换法是将明文字母替换成其他字母、数字或符号的加密方法 如果把明文看成是二进制序列的话，代换就是用密文位串来代换明文位串 代换法改变明文内容的表示形式，保持内容元素之间相对位置不变 2.2 代换密码 (Substitution)

28 .代换密码 (Substitution) 最早的描述：“ Kama-Sutra ” ( “ The art of love ” ) by Brahmin scholar Vatsyayana –4 th century A.D. 64 arts: cooking, dressing, massage, perfume preparation… No.45 –secret writing: pair letters & substitute A-V D-X H-B I-G K-J M-C O-Q R-L S-N U-E W-F Y-P Z-T Meet at midnight --- CUUZ VZ CGXSGIBZ 已知最早应用于军事的代换密码是由 Julius Caesar 发明的恺撒密码 Caesar Cipher ， 用希腊字母代替罗马字母 (in his “Gallic Wars”) 对字母表中的每个字母用它之后的第 3 个字母来代换。（ in “Lives of the Caesars LVI” -2th Century A.D. ）例如： meet me after the toga party PHHW PH DIWHU WKH WRJD SDUWB

29 .2.2.1 Caesar Cipher Caesar 实际上是一种单表代换密码 明文字母用密文字母表中对应字母代替，例： 明文字母表 P ＝ {p 0 , p 1 , …, p i , …, p n-1 } 密文字母表 C ＝ {c 0 , c 1 ,…, c j , …, c n-1 } 密钥为正整数 k ，加密： i+k ≡ j (mod n) 解密： j-k ≡ i (mod n) Caesar Cipher { 0 － A ； 1 － B ； … ； 25 － Z} 加密： C = E(p)=( p+k ) mod 26 解密： p = D(C)=(C-k) mod 26