课时：18周 上课时间: 周二3-4节，周四3-4节 考试成绩：考试与作业 上课时间: 周二3-4节，周四3-4节 考试成绩：考试与作业 课程网站：http://course.sdu.edu.cn/G2S/crypto.cc 参考资料： [1]《密码学导引》，冯登国、裴定一 编著， 科学出版社，1999. [2] Cryptography - Theory and Practice, 3/E, Douglas Stinson, 2009. [3] Cryptography and Network Security: Principles and Practices, 6/E, William Stallings, 2014.

第一章 引论 魏普文 山东大学密码技术与信息安全 教育部重点实验室

历史发展 密码学（Cryptology）是一门古老而又年轻的 科学，其发展历史可划分为三个阶段 第一阶段：古代～1949， 朴素的古典密码 直觉和经验 古希腊斯巴达 密码器(405BC) 高卢战争 恺撒密码(100BC)

历史发展 16世纪晚期，法国外交家Blaise de Vigenère提出了一种多 表密码加密算法 ——维热纳尔密码 破解Vigenère cipher 19世纪50年代，英国巴贝奇（Charles Babbage) 1863年，普鲁士少校卡西斯基（ Friedrich Kasiski）

历史发展 中国古代军队使用的密码 虎符：最早出现于春秋战国时期，铜制的虎形令牌，作 为中央发给地方官或驻军首领的调兵凭证 阴书：古代兵书《六韬》记载，所谓“阴书”，实际上 是一种军事文书，其方法是：先把所要传递的机密内容 写在一个竹简或木简上，然后将这个竹简或木简拆开、 打乱分成三份，称“一合而再离” 一半交给将帅，另一半由皇帝保存，只有两个虎符同时使用，才可以调兵遣将

历史发展 二战时期的密码 德国Enigma密码机 日本“紫密” 印第安纳瓦霍土著语言

历史发展 破解Enigma的英雄 Marian Adam Rejewski Alan Turing Bombe

历史发展 第二阶段：1949～1975 1949年，Shannon 发表《保密系统的信息理论》 70年代初期，IBM技术报告 建立了私钥密码系统的理论基础 密码学成为一门科学 70年代初期，IBM技术报告

Rivest、Shamir与Adleman 历史发展 第三阶段：1976至今 DES 加密成为标准（1977） Diffie和Hellman 《密码学的新方向》（1976） Rivest、Shamir、Adleman提出RSA密码体制（1977） Rivest、Shamir与Adleman

历史发展 关注信息安全 关系国家安全和国家发展 Post-Snowden 关系人民群众工作生活 隐私泄露、电信诈骗 爱德华·斯诺登（Edward Snowden），曾是CIA（美国中央情 报局）技术分析员，后供职于国防项目承包商Booz Allen Hamilton 2013年6月将美国国家安全局关于PRISM监听项目的秘密文 档披露给了《卫报》和《华盛顿邮报》，随即遭美国政府通 缉 关系人民群众工作生活 隐私泄露、电信诈骗

“网络安全和信息化是事关国家安全和国家发展、事关广大人民群众工作生活的重大战略问题” 历史发展 “网络安全和信息化是事关国家安全和国家发展、事关广大人民群众工作生活的重大战略问题”

密码学基本概念 密码学（Cryptology）是研究密码系统或通信安全 的科学，包括两个分支 密码编码学（Cryptography） 寻求保证消息保密性与认证性的方法 密码分析学（Cryptanalytic） 研究加密消息的破译或消息的伪造

密码学基本概念 基本概念 明文（plaintext）：被隐蔽的消息 密文（ciphertext）：隐蔽后的消息 发送者（sender）：生成并发送密文 接收者（receiver）：接收并解密密文 Alice , Bob and Eve

密码学基本概念 加密（encryption） 解密（decryption） 加密算法（encryption algorithm） 将明文变换成密文的过程 解密（decryption） 由密文恢复出原明文的过程 加密算法（encryption algorithm） 发送者对明文进行加密时所采用的规则

密码学基本概念 解密算法（decryption algorithm） 密钥（key）： 接收者对密文进行解密时所采用的规则 加密与解密通常在一组key（encryption key; decryption key）控制下进行 明文 加密算法 解密算法 加密 秘钥k1 解密 秘钥k2 密文

密码体制的分类 根据密钥(Key)将密码体制分为两类 根据加密方式的划分 对称密码(Symmetric cipher): Key1=Key2 也称为私钥(private key)密码 非对称密码(Asymmetric cipher): Key1≠Key2 也称为公钥(public key)密码 根据加密方式的划分 流密码 分组密码 注意：“分组密码”(block cipher)通常指的是“对称密 码”、“私钥密码”

关于攻击（Attack）——方法 攻击类型 被动与主动 攻击者已具备的前提条件 被动攻击：监听，截获密文后分析 主动攻击：串扰系统，删除，更改，增填，重放，伪造 攻击者已具备的前提条件 唯密文攻击（ciphertext-only attack） 已知明文攻击（known plaintext attack） 选择明文攻击 (chosen plaintext attack) 选择密文攻击 (chosen ciphertext attack) “安全”与“攻击”的关系

关于攻击（Attack）——目的 以加密算法为例 加密算法（密码系统）可破：如果通过密文或明密 文能够迅速的确定key或目标明文（针对加密） 注意：通常假设敌手已知所使用的密码系统 (Kerckhoffs假设) 不应该把密码系统的安全性建立在敌手不知道密码算法 的前提下 密码系统安全性依赖于key 在Kerckhoff假设下达到安全性 破译、破解、攻击

安全的两个方面——保密性与认证性 保密性 保护信息的机密性 系统即使达不到理论上是不可破的，也应当是实际 上不可破的 (Kerckhoffs)系统的保密性不依赖于对加密算法的保密, 而依赖于key 加密与解密算法适用于所有密钥空间中的元素 系统即易于实现又便于使用

安全的两个方面——保密性与认证性 认证性 注意：某些情况下要求消息的发送者对所发送消 息不能抵赖 使消息接收者能够识别与确认消息的真伪 议定的接收者能够检验和证实消息的合法性与真实 性 除合法发送者外，其他人不能伪造合法的消息 注意：某些情况下要求消息的发送者对所发送消 息不能抵赖

古典密码学 移位密码 仿射密码 维吉尼亚密码 希尔密码

古典密码学 密码体制(P,C,K,E,D) P 所有可能的明文组成的有限集 C 所有可能的密文 组成的有限集 对每一个k, 都存在一个加密规则ek 和相应的解密规则 dk, 并且每对ek ∈E 、dk ∈D ，满足条件：对每个明文x ,都 有dk(ek(x))=x

移位密码 移位密码 A B C D E F G H I J K L M 1 2 3 4 5 6 7 8 9 10 11 12 N O P Q 1 2 3 4 5 6 7 8 9 10 11 12 N O P Q R S T U V W X Y Z 13 14 15 16 17 18 19 20 21 22 23 24 25

移位密码 例题：k=5, 明文字母happy 明文数字：7, 0, 15, 15,24 密文数字：12,5,20,20,3 密文字母：mfuud A B C D E F G H I J K L M 1 2 3 4 5 6 7 8 9 10 11 12 N O P Q R S T U V W X Y Z 13 14 15 16 17 18 19 20 21 22 23 24 25 26种 A B C D E F G H I J K L M N O P Q R N O P Q R S T U V W X Y Z A B C D E

仿射密码 仿射密码 特例：移位密码，乘法密码 26×phi(26)

仿射密码 单表代换密码 例如，移位密码，乘法密码，仿射密码 代换总数 多表代换密码 例如，维吉尼亚密码，希尔密码

维吉尼亚密码(Vigenère Cipher)

维吉尼亚密码(Vigenère Cipher) 例题 密钥是CIPHER. 即K = (2, 8, 15, 7, 4, 17). 明文是以下字符串 “thiscryptosystemisnotsecure” A B C D E F G H I J K L M 1 2 3 4 5 6 7 8 9 10 11 12 N O P Q R S T U V W X Y Z 13 14 15 16 17 18 19 20 21 22 23 24 25

维吉尼亚密码(Vigenère Cipher) 例题1 Plaintext THISCRYPTOSYSTEMISNOTSECURE Ciphertext VPXZGIAXIVWPUBTTMJPWIZITWZT 19 7 8 18 2 17 24 15 14 4 21 23 25 6 22 18 19 4 12 8 13 14 2 15 7 17 20 1 9 22 25 20 17 4 2 8 15 22 25 19

维吉尼亚密码(Vigenère Cipher)   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 例题2 密钥 W H I T E 明 文 d i v e r t o p s a g 密 文 Z P D X V A S L B K M N

希尔密码(Hill Cipher) 利用线性变换 例题

希尔密码(Hill Cipher) 希尔密码 注意：T为可逆线性变化

Probabilities of Occurrence of the 26 Letters 古典密码体制分析 Probabilities of Occurrence of the 26 Letters letter probability A .082 N .067 B .015 O .075 C .028 P .019 D .043 Q .001 E .127 R .060 F .022 S .063 G .020 T .091 H .061 U I .070 V .010 J .002 W .023 K .008 X L .040 Y M .024 Z 穷举密钥搜索 密钥空间足够大 频率统计 单表代换： 移位密码 仿射密码 多表代换 维吉尼亚密码

Vigenère Cipher分析 第一步：确定密钥长度 第二步：确定密钥字相对位移 第三步：穷举搜索密钥字

Vigenère Cipher分析 第一步：确定密钥长度 方法一：Kasiski测试法 方法二：重合指数法 原理：密文中出现两个相同字母组，它们所对应的明 文字母组未必相同，但相同的可能性很大。这样的两 个字母组对应相同字母间的距离可能为密钥长度的整 数倍 方法二：重合指数法 原理：自然语言（英语）的重合指数约为0.065，且 单表代换不会改变该值 关键词 W H I T E 明 文 d i v e r t o p s a g 密 文 Z P D X V A S L B K M N

Vigenère Cipher分析 重合指数定义 设x=x1x2…xn是含有n个字母的串，则在x中随机选择 两个元素且这两个元素相同的概率为 其中fi为26个字母中第i个字母出现的次数

Vigenère Cipher分析 自然语言（英语）重合指数 利用英文字母频率表 注意：单表代换不改变该值，即用相同密钥字加密 的密文应服从该值 提取相同密钥字加密的密文，测试其重合指数 假设密钥长度为d 如果假设正确，则重合指数值接近0.065 否则，字符串表现得更为随机，一般在0.038（1/26 ）～0.065之间

Vigenère Cipher分析 Vigenère密码例题 Kasiski测试法：位置1，166，236，286，距离165，235， 285，公因子5 重合指数法：分别尝试d=1,2,3,4,5 C H R E V O A M T B I X W N P S Q U K G J F Z L D Y   Kasiski测试法：位置1，166，236，286，距离165，235，285，公因子5

重合指数法：分别尝试d=1,2,3,4,5 d 重合指数 1 0.045; 2 0.046, 0.041; 3 0.043, 0.050, 0.047; 4 0.042, 0.039, 0.046, 0.040 5 0.063， 0.068, 0.069, 0.061, 0.072

Vigenère Cipher分析 确定密钥字 重合互指数定义

Vigenère Cipher分析 考虑不同密钥字加密后密文串的重合互指数 注意，明文为自然语言

Expected Mutual Indices of Coincidence Vigenère Cipher分析 移位表 Expected Mutual Indices of Coincidence Relative shift Expected value of MIc 0.065 1 0.039 2 0.032 3 0.034 4 0.044 5 0.033 6 0.036 7 8 9 10 0.038 11 0.045 12 13 0.043 \sigma p_h*p_{h+t}=\sigma p_h*p_{h-t},相对位移是t和26-t的MIC是一样的

Vigenère Cipher分析 猜测不同密钥字的相对位移s (猜测范围0~25) 如果s猜对，则该值应接近0.065 这意味着找到了不同密钥字加密的相同的明文字母 ，即找到了密钥字之间的相对位移

Vigenère Cipher分析 相对移位表 k1-k2=9, k1-k5=16, k2-k3=13, k2-k5=7, j Value of MIC(Ci, Cj) 1 2 .028 .027 .034 .039 .037 .026 .025 .052 .068 .044 .043 .041 .051 .045 .042 .036 3 0.39 .033 .040 .053 .048 .029 .056 .050 .032 .031 .055 .024 4 .038 .049 .047 .035 5 .046 .030 .019 .070 .067 k1-k2=9, k1-k5=16, k2-k3=13, k2-k5=7, k3-k5=20, k4-k5=11 16 13

Vigenère Cipher分析 相对移位表 k1-k2=9, k1-k5=16, k2-k3=13, k2-k5=7, j Value of MIC(Ci, Cj) 2 4 .046 .034 .043 .044 .031 .040 .045 .048 .033 .024 .028 .042 .039 .026 .050 .035 .032 .056 5 .036 .018 .080 .029 .037 .027 .041 .030 3 .038 .060 .058 .053 .051 .025 .052 .072 .061 16

Vigenère Cipher分析 穷搜密钥字 确定密钥字之间关系式基础上，穷举搜索

参考资料 Cryptography: Theory and Practice, Douglas R. Stinson http://en.wikipedia.org/ The Code Book, Simon Singh 密码学导引，科学出版社，冯登国, 裴定一