【现代密码学】笔记1.2 -- 对称密钥加密、现代密码学的基本原则《introduction to modern cryphtography》现代密码学原理与协议

写在最前面

参考：骆婷老师的PPT

《introduction to modern cryphtography》–Jonathan Katz, Yehuda Lindell（现代密码学——原理与协议）中相关章节

密码学复习笔记 这个博主好有意思

哈工大密码学课程 张宇老师的课件

B站视频 密码学原理《Introduction to modern Cryptography》

感谢一起复习的11位同学

初步笔记，如有错误请指正

考试范围

一、给一个简单的方案，判断是否cca安全

判断方式：要么证明是cca安全，要么找一个攻击方式去攻击

一样一个题

1、对称加密、

2、消息认证码MAC

3、哈希函数、

4、非对称的多样加密的方案

【数字签名不考，因为和mac功能和证明方式、实验都类似】

二、随机预言机模型之下的简单应用

随机预言机性质、随机预言机模型之下的简单应用

性质之下构造函数的性质

快速补充一些密码相关的背景知识

1 概述

1.2 对称秘钥加密的基本设置

对称密钥加密概述

在对称密钥加密系统中，通信双方共享一段密码信息，称为密钥（key）。当他们希望安全地通信时，会使用这个共享密钥。具体来说：

• 发送方 使用密钥来加密（或者“混合”）消息。
• 接收方 收到消息后，使用相同的密钥来解密（或者“去混合”）以恢复原始消息。

这里所说的消息本身称为明文（plaintext），而从发送方传输到接收方的经过加密处理的消息称为密文（ciphertext），如图 1.1 所示。在这种设置中，共享的密钥用来从所有潜在的窃听者中区分通信双方（这通常假设是通过一个公共信道进行传输的）。

对称密钥（Symmetric-Key）

在对称密钥加密中，"对称"指的是双方拥有相同的密钥来进行加密和解密。这意味着：

• 加密和解密使用的是相同的密钥。
• 密钥的分发和保密是对称密钥加密中的一个重要挑战，因为密钥必须在通信开始前在双方之间安全地共享。

加密的语法

1. 密钥产生算法 (Gen)

• 功能：Gen是一个概率算法，能够根据方案定义的某种分布选择并输出一个密钥k kk。
• 表达：G e n → k Gen \rightarrow kGen→k

2. 加密算法 (Enc)

• 功能：加密算法Enc，输入为密钥k kk和明文m mm，输出为密文c cc。使用密钥k kk加密明文m mm的过程记为E n c k ( m ) Enc_k(m)Enck(m)。
• 表达：E n c ( k , m ) → c Enc(k, m) \rightarrow cEnc(k,m)→c 或 E n c k ( m ) = c Enc_k(m) = cEnck(m)=c

3. 解密算法 (Dec)

• 功能：解密算法Dec，输入为密钥k kk和密文c cc，输出为明文m mm。使用密钥k kk解密密文c cc的过程记为D e c k ( c ) Dec_k(c)Deck(c)。
• 表达：D e c ( k , c ) → m Dec(k, c) \rightarrow mDec(k,c)→m 或 D e c k ( c ) = m Dec_k(c) = mDeck(c)=m

加密的基本要求

密钥空间（记为K \mathcal{K}K）是密钥产生函数输出的所有可能的密钥的集合。通常，Gen简单地从密钥空间中均匀随机地选择一个密钥。

明文空间（记为M \mathcal{M}M）是所有“合法”消息（即被加密算法支持的消息）的集合。

任何密文是通过使用密钥加密明文来获得的，因此K \mathcal{K}K和M \mathcal{M}M从一起定义了所有可能密文的集合。

一个加密方案可通过明确三个算法（Gen, Enc, Dec）和明文空间M \mathcal{M}M来完全定义。

对于任意加密方案的基本要求是：对于通过Gen输出的任意密钥k kk，每个明文消息m ∈ M m \in \mathcal{M}m∈M满足：

D e c k ( E n c k ( m ) ) = m Dec_k(Enc_k(m)) = mDeck(Enck(m))=m

这意味着解密一个密文（使用相应的密钥）会生成原来加密的原始消息。

在实际应用中，通信双方首先运行Gen获取共享的密钥k kk。当一方需要发送明文m mm给另一方时，他首先计算c : = E n c k ( m ) c := Enc_k(m)c:=Enck(m)，然后通过公共信道发送密文c cc给另一方。接收方接收到c cc后，计算m : = D e c k ( c ) m := Dec_k(c)m:=Deck(c)来恢复原来的消息。

攻击场景

密码学中的四种基本攻击类型，每种类型都有其特定的攻击场景和目的：

1. 唯密文攻击 (Ciphertext-only attack)：这是一种基础的攻击方式，其中攻击者只能获取到密文（可能是多个），并试图确定相应的明文。在这种攻击中，攻击者没有任何额外的信息，只能依赖密文本身。
   
2. 已知明文攻击 (Known-plaintext attack)：在这种情形下，攻击者已经知道一些使用相同密钥加密的明文和对应的密文。攻击者的目标是利用这些信息来破解其他的密文。这种攻击假设敌手能够获得至少一个明文-密文对。
   
3. 选择明文攻击 (Chosen-plaintext attack)：在此攻击模式下，攻击者能够选择特定的明文，并获取对应的密文。这种攻击检验了加密系统是否能抵御当敌手有能力获取特定明文的密文时的安全性。
   
4. 选择密文攻击 (Chosen-ciphertext attack)：这是一种更高级的攻击，其中攻击者不仅能选择密文，而且还能得到相应的明文。这种攻击测试了加密系统在面对能够选择密文并获取明文的敌手时的安全性。
   

这四种攻击类型中，

前两种（唯密文攻击和已知明文攻击）是被动的，即攻击者只能利用已有的信息（密文或明文-密文对）进行攻击。

而后两种（选择明文攻击和选择密文攻击）是主动的，攻击者可以选择性地获取加密或解密的信息。

每种攻击类型都对加密方案的安全性提出了不同的挑战，因此在设计和评估加密系统时，需要考虑这些不同的攻击场景。

现代密码学的基本原则

现代密码学的严格方法，通过定义明确的安全标准、精确陈述的假设和规约方法的安全证明，提供了一个比传统密码学更为科学和系统的方法论。

通过采用这些原则，现代密码学能够在理论上和实践上提供更为可靠和安全的加密方案，从而有效应对复杂和不断发展的安全挑战。

以下是现代密码学的三个主要原则：

原则 1: 严格且精确的安全定义

• 描述：解决任何密码学问题的第一步是公式化的表述，提供严格且精确的安全定义。
• 应用：安全定义通常采用以下通用形式：如果特定的敌手不能完成特定的攻击，则对给定任务的一个密码学方案是安全的。

这种定义不对敌手的策略进行任何假设。假设敌手的能力（例如，能够进行选择明文攻击而不是仅密文攻击），但不对敌手如何使用其能力进行假设。这被称为“任意敌手原则”，即安全必须确保抵御任意拥有特定计算能力的敌手。这一原则是重要的，因为敌手在攻击中将采用的策略是不可能预先知道的。

原则 2: 精确陈述的假设

• 描述：当密码学构造方案的安全性依赖于某个未被证明的假设时，这种假设必须精确地陈述，而且，所假设的要尽可能地少。
• 应用：这意味着在设计密码学方案时，应明确指出所依赖的假设，并尽量减少这些假设的数量。例如，某些方案可能基于“假设没有有效的因数分解算法”的前提。

原则2强调了精确陈述假设的必要性，不仅为了提高方案的可信度和可比较性，也为了方便进行有效的安全证明。

主要基于以下三个原因：

1. 假设的正确性

• 重要性：假设是未经证明但被推测为正确的陈述。为了强调其可信程度，必须对假设进行详尽的研究。假设越经得起严格检查且未出现反例，其可信度越高。
• 实施：对假设的研究能提供支持其正确性的证据，这些证据可能基于其他广泛接受的假设。如果假设没有精确陈述和展示，它无法被研究和（潜在地）被驳斥。因此，精确陈述假设内容是提高其可信度的先决条件。

2. 多个方案的比较

• 重要性：在密码学中，可能会比较两个都能满足特定安全定义的方案，但基于不同的安全假设。
• 实施：如果两个方案效率相同，应选择基于较弱假设的方案，因为较强的假设可能被证明是错误的，而较弱的假设仍然正确。如果两个方案使用的假设无法比较，则通常选择假设研究更彻底或更简单的方案。

3. 对安全证明的帮助

• 重要性：现代密码学的构造方法通常伴随着安全证明。如果方案的安全性不能无条件证明，即依赖于某个假设，则对于“如果假设正确，则方案是安全的”的数学证明必须基于精确的假设陈述。
• 实施：通常倾向于陈述更简单的假设，因为它们更容易研究和反驳。例如，某些数学问题难以解决的假设比假设一个加密方案符合复杂的安全定义更容易学习和使用。当简单的假设经过长时间研究且未被反驳时，可以更自信地认为它是正确的。此外，低层次的假设可以在多个构造方案中共享，如果特定的假设实例被证明是错误的，它可以被不同的假设实例替换。

原则 3: 严格的安全证明

• 描述：密码学构造方案应当伴随有严格的安全证明，这些证明应符合原则1的安全定义，并且与原则2陈述的假设有关（如果假设是需要的）。
• 应用：这要求密码学研究者不仅要提出新的方案，还需要提供对这些方案安全性的数学证明，以证明在原则1定义的安全标准和原则2中提出的假设下，其方案是安全的。

规约方法 （3.1.3节中详细介绍）

原则 3 在现代密码学中强调了规约方法的使用，这是对安全性证明的一个核心方法。

规约方法

• 定义：规约方法是现代密码学证明中常用的技术，用于展示如果某个给定假设是正确的，那么根据给定定义，构造方案是安全的。
• 实施：证明通常展示如何将假设X规约到攻破构造方案Y。这通常通过构造性论证实现，展示如何使用敌手攻破构造方案Y的方法来产生与假设X的冲突。这种方法将在3.1.3节中详细介绍。

严格方法与临时方法的比较

• 严格方法：现代密码学的严格方法基于以上三个原则，提供了一个系统化、科学的方法来设计和评估密码学方案。
• 临时方法：与之相反，经典密码学中的临时方法可能忽略这些原则。临时方法缺乏严格的安全定义、明确的假设陈述和规约方法来证明安全性。
• 影响：仍然有人在设计和应用临时方案，可能是因为对严格方法的不了解或是寻求快速、直接的解决方案。这种方法虽然简单，但通常缺乏足够的安全性和可靠性。

一些概念补充

哈工大密码学课程 张宇老师课件 的导论部分

在本节课程中，我们学习密码学导论，包括对称加密基本概念、古典密码学和现代密码学基本原则。我们通过学习这些可在直觉上被理解的，古典的加密方案和破解方法，建立对加密和安全的直观概念，从而理解现代密码学基本原则为什么是合理的和必要的。

密码学概念

• 密码学的英文单词来自两个希腊单词：kryptos，意为“隐藏，保密”，和graphin，意为“书写”，即秘写。
• 密码学在简明牛津字典中定义为书写或破解代码（code）的艺术。其中，Code（代码）是一个预先编排好的符号的系统，特别用于确保消息传输中的秘密。另外中文中“密码”相关的英文单词还包括password（口令）、cipher（加密方案）、key（密钥）。这些术语要注意区分。
• 现在密码学的开端在1980年代。那时在美国以DES、公钥密码学等为代表的成果相继出现，并且在美国密码学也从军用转变为民用。整个信息技术也是起步于上世纪八零年代的美国，包括个人计算机以及互联网。密码学的发展得益于个人计算机和互联网的发展。在互联网这个开放环境下安全通信的需求催生了密码学研究和大规模应用。
• 参考教材IMC中对现代密码学定义：用于保护数字信息，系统和分布式计算免于敌对攻击的数学技术的科学研究。本课程主要是学习如何保护信息。

什么是密码学？（思考）

• 漫画：在美国，密码学曾经被作为武器而被禁止出口
• 目前各国对密码学产品进出口都有严格限制
• 《中华人民共和国密码法》

• 第二条：本法所称密码，是指采用特定变换的方法对信息等进行加密保护、安全认证的技术、产品和服务。
• 第七条：核心密码、普通密码用于保护国家秘密信息，核心密码保护信息的最高密级为绝密级，普通密码保护信息的最高密级为机密级。核心密码、普通密码属于国家秘密。

私钥加密（private key encryption）设定

• 目标是构造一个加密方案，用于在预先共享了私钥（对称密钥）的双方之间进行保密通信。
• 隐含一个假设：存在某种方法，以保密的方式来分享一个密钥。
• 磁盘加密相当于同一个人在不同的时刻间通信。

6. Alice和Bob

• Alice和Bob是密码学领域最出名的人，他们首次出现在1978年的著名的RSA论文，《A Method for Obtaining Digital Signatures and Public-key Cryptosystems》（一种产生数字签名和公开密钥系统的方法）。有关Alice和Bob的参考资料。

加密的词法

• 什么是加密方案？下面是一个形式化的描述。其中的符号与表达比较符合直觉。
  
• 作为发送者的Alice，向作为接收者的Bob，发送一个消息。该消息使用一个对称密钥加密。敌手（Adversary）窃听密文（窃听者通常命名为Eve），尝试获得明文。
  
• key密钥k ∈ K k \in \mathcal{K}k∈K,plaintext (or message)明文或消息m ∈ M m \in \mathcal{M}m∈M,ciphertext密文c ∈ C c \in \mathcal{C}c∈C

• 用小写字母表示一个具体信息，用花体大写字母表示一个集合

• Key-generation Algorithm密钥生成算法k ← G e n k \gets \mathsf{Gen}k←Gen

• 用左箭头"← \leftarrow←"表示随机生成结果的赋值

• Encryption Algorithm加密算法c : = E n c k ( m ) c:= \mathsf{Enc}_k(m)c:=Enck(m)

• 用冒号加等号“: = :=:=”表示“deterministic assignment”（确定性赋值），类似程序设计中的等号

• Decryption Algorithm 解密算法 m : = D e c k ( c ) m:= \mathsf{Dec}_k(c)m:=Deck(c)
  
• Encryption scheme加密方案:Π = ( G e n , E n c , D e c ) \Pi = (\mathsf{Gen}, \mathsf{Enc}, \mathsf{Dec})Π=(Gen,Enc,Dec)

• 密钥生成算法也是加密方案的一部分！

• Basic correctness requirement基本正确性要求 :D e c k ( E n c k ( m ) ) = m \mathsf{Dec}_k(\mathsf{Enc}_k(m)) = mDeck(Enck(m))=m

• 对一个明文使用一个密钥加密后，再用同一个密钥解密，应该得到相同的明文。
• 等号“=”表示“相等”，“是”

8. 保护密钥还是隐瞒算法？（Kerchhoffs原则、香农箴言）

• 加密方案的“秘密”包括两部分：加密/解密算法和密钥，那么我们应该保密什么？
• 更容易维护一个短密钥的秘密
• 在密钥暴露的情况下，对于诚实方，更换密钥更容易
• 在许多人彼此通信的情况下，更容易采用相同算法，不同密钥
• Kerchhoffs原则 (柯克霍夫原则)：加密方法一定不必是秘密，即便落入敌手也必无不妥
• 香农箴言：敌人了解系统

9. 为什要“开放密码学设计”？

• 发表的设计经过公开检验会更强健（类似在提倡开源软件时，所给出的一个优点）
• 相对于被攻击者发现，由有道德的黑客来发现安全缺陷会更好
• 即便不公开，代码逆向工程（或被工业间谍泄漏）也构成了严重的安全威胁
• 使标准的建立成为可能
• 即使成为标准也不意味着安全：Dual EC是一个标准化的后门

• Dual EC曾经与其他算法一起被NIST, ANSI和ISO标准化来产生随机数
• 斯诺登披露，以及在关于Bullrun项目和SIGINT使能项目的报告中已经表明，Dual EC是NSA颠覆标准的系统化工作的一部分。
• 路透社报道，NSA在一笔交易中向RSA公司支付了1千万美元，用于将Dual EC设置为BSafe软件中优先或者缺省的数字生成方法。

10. 攻击场景

• 除了窃听密文（称为COA），敌手还有其它手段（敌手能力）
  
• Ciphertext-only (COA) 唯密文: 敌手只观察密文
  
• Known-plaintext (KPA) 已知明文: 敌手获知同一密钥下的若干明文/密文对
  
• Chosen-plaintext (CPA) 选择明文: 敌手有获得所选择明文加密（获得该明文的密文）的能力
  
• Chosen-ciphertext (CCA) 选择密文: 敌手有获得所选择的其它密文解密（获得该密文的明文）的能力
  
• 被动攻击: COA KPA，由于不是所有密文都是机密的
  
• 主动攻击: CPA CCA，当敌手能够加密/解密任何其所希望的信息
  

11. 历史上的加密方案及其密码分析（Cryptanalysis）

• 下面学习古典密码，目的是了解加密并没有想象的复杂，但设计安全的加密是很困难的。同时，理解一些密码学设计的基本原则，并思考一个问题：如何确定一个加密方案是安全的？
  
• 凯撒加密方案（Caesar’s Cipher）：凯撒将机密消息加密书写，这是将字母表中字母顺序改变使得没有一个单词可以被理解。若有人要解密，则他必须将字母表中第四个字母，即D，替换成A，并且对其它字母也这么做。
  
• E n c ( m ) = m + 3 m o d    26 \mathsf{Enc}(m)=m+3\mod 26Enc(m)=m+3mod26
  
• 例子：明文begintheattacknow，采用凯撒加密的密文是什么？
  
• 其弱点是什么？怎么改进？
  

12. 移位加密（Shift Cipher）

• E n c k ( m ) = m + k m o d    26 \mathsf{Enc}_k(m)=m+k\mod 26Enck(m)=m+kmod26
• D e c k ( c ) = c − k m o d    26 \mathsf{Dec}_k(c)=c-k\mod 26Deck(c)=c−kmod26
• 例子：解密EHJLQWKHDWWDFNQRZ
• 弱点: 是什么? 怎么改进？
• 充足密钥空间原则：任何安全加密方案必须具有一个经受住穷举搜索的密钥空间
• 问题：如何在穷举过程中自动化地确定密钥？

13. 重合指数（Index of Coincidence）方法（寻找密钥k kk）

• 如何自动确定解密出来的是英文原文？
  
• 重合指数I II是两个随机挑选（挑选后放回）字母相同的概率
  
• 令 p i p_ipi表示英文文本中第i ii个字母的概率
  I = def ∑ i = 0 25 p i 2 I \overset{\text{def}}{=}\sum_{i=0}^{25} p_i^2I=defi=0∑25pi2
  
• 例子：计算apple的重合指数？

• 先计算字符在字符串中出现的比例，a、l和e都是1/5，p是2/5
  
• 重合指数= 3 × ( 1 5 ) 2 + ( 2 5 ) 2 = 7 25 =3\times \left( \frac{1}{5}\right)^2 + \left( \frac{2}{5}\right)^2 = \frac{7}{25}=3×(51)2+(52)2=257
  

• 根据统计，对于足够长的英文文本，其重合指数为0.065。

• 当每个字母以相同频率出现时，重合指数为26 × 1 26 2 = 1 26 = 0.038 26 \times \frac{1}{26}^2 = \frac{1}{26} = 0.03826×2612=261=0.038
  
• 这里可以看出英文中字母频率分布是不均匀的
  

• 对于j = 0 , 1 , … , 25 j = 0, 1, \dotsc , 25j=0,1,…,25, 设q j q_jqj为密文中第j jj个字母的概率，定义一个带参数s ss的重合指数I s = def ∑ i = 0 25 p i ⋅ q i + s I_s \overset{\text{def}}{=}\sum_{i=0}^{25} p_i \cdot q_{i+s}Is=defi=0∑25pi⋅qi+s

• q i + s q_{i+s}qi+s 就是明文第 i ii 个字母被移位 s ss 个后所得到字母在密文中的概率

• 问题：当得到I s = 0.065 I_s = 0.065Is=0.065时就找到了密钥k kk？

• 当s = k s=ks=k为密钥时，重合指数最大，因为平方和大于乘积的和，a 2 + b 2 > 2 a b a^2 + b^2 > 2aba2+b2>2ab
• 例如，将凯撒密码当成k = 3 k=3k=3的移位密码，a被替换成D，D在密文中的概率与a在明文中的概率是一样的。当k = 3 k=3k=3时，p 0 p_0p0就是明文中a的概率，q 0 + 3 q_{0+3}q0+3就是密文中D的概率，此时，p 0 = q 3 p_0 = q_3p0=q3。

• 这不正是大数据（足够的英文）+人工智能（是否是英文）吗!?
  

14. 单表替换加密（Mono-Alphabetic Substitution）

• 思想：将每个字母以任意方式映射到一个不同字母
• 优点：密钥空间足够大 ≈ 2 88 \approx 2^{88}≈288。如何计算的？
• 缺点：是什么？怎么改进？
• 明文abcdefghijklmnopqrstuvwxyz
• 密文XEUADNBKVMROCQFSYHWGLZIJPT
• 明文tellhimaboutme ，密文是什么？

15. 利用统计模式来攻击

1. 将密文中字母的频率制表，得到每个密文字母的频率
2. 与英文文本中字符频率比较（英文文本中字母频率）
3. 猜测频率最高的字母对应e，如此猜测其他字母
4. 挑选“合理的”明文，但并不简单

16. 一个密文例子，人眼很难看出个所以然来
    
17. 一个频率分析的例子

• 计数，猜，试错

18. 一个频率分析出的明文，《金甲虫》小说片段
    
19. 维吉尼亚（多表移位）加密 (Vigenere (poly-alphabetic shift) Cipher)

• 思想：通过将明文中相同字母的不同出现映射到密文中不同字母，以此抹平密文中统计分布。
• 加密：c i = m i + k [ i   m o d   t ] c_i=m_i+k_{[i\bmod t]}ci=mi+k[imodt], t tt 是 k kk 的长度（周期）
• 密码分析：

• 需要发现 t tt；这曾经很难。
• 若 t tt 已知，则需要知道解密是否“合理”，但当t > 15 t > 15t>15时，蛮力破解 (2 6 t 26^t26t) 不可行；因为密钥中每一个字母都是移位加密的密钥，可以用重合指数来一个一个字母猜密钥。

20. Kasiski的方法（寻找周期t tt）

• 多表移位加密在2百多年内未被有效破解，直到…
• 识别出长度2或3的重复模式，猜想这些重复应该是由于相同的明文片段被相同密钥片段加密的结果；
• 那么，假设密钥中没有重复模式，则这些重复出现之间的距离应该是密钥长度 t tt 的倍数；
• 那么，假设明文中重复模式是随机的，则密钥长度 t tt 是所有重复出现间距离的最大公约数；
• 但重复出现也可能是巧合，有没有更有效的方法？

21. 重合指数法（寻找周期t tt）

• 对于 τ = 1 , 2 , … \tau = 1, 2, \dotscτ=1,2,… 作为猜测的周期，c 1 , c 1 + τ , c 1 + 2 τ , … c_1, c_{1+\tau}, c_{1+2\tau}, \dotscc1,c1+τ,c1+2τ,…，是密文中以τ \tauτ为固定间隔的字符集合；
  
• q i q_iqi 是该字符集合中第 i ii 个字母出现的概率，计算该以τ \tauτ为固定间隔字符集合的重合指数等于
  I τ = def ∑ i = 0 25 q i 2 I_\tau \overset{\text{def}}{=}\sum_{i=0}^{25} q_i^2Iτ=defi=0∑25qi2
  
• 若τ = t \tau = tτ=t, 那么I τ ≈ ? I_\tau \approx ?Iτ≈?

• 通过遍历 τ \tauτ 来寻找 t tt, 若 τ = t \tau = tτ=t, 则使用了同一个密钥的移位加密所得到的密文 c 1 , c 1 + t , c 1 + 2 t , … c_1, c_{1+t}, c_{1+2t}, \dotscc1,c1+t,c1+2t,…，其中相同的明文字母被映射为相同的密文字母，因此，重合指数I τ I_\tauIτ与明文的相同。

• 否则， 认为固定间隔字符集中字符的概率都是相同的，q i ≈ 1 26 q_i \approx \frac{1}{26}qi≈261并且I τ ≈ ∑ i = 0 25 ( 1 26 ) 2 ≈ 0.038 I_\tau \approx \sum_{i=0}^{25} \left(\frac{1}{26}\right)^2 \approx 0.038Iτ≈i=0∑25(261)2≈0.038

• 此时，假设所挑选出的密文是由明文字母被某个密钥中随机的字母映射所得到的，还假设密钥足够长且其中字母足够多样，则密文中每个字母出现是充分随机的，即出现概率为1/26，（在完美保密部分会进一步学习）。

• 确定周期后，再次使用重合指数法寻找密钥中每个位置 i ii 的字符 k i k_iki.
  
• 古典密码学最终都被破解说明一个道理：

• 任意敌手原则 (Arbitrary Adversary Principle)：对于一类具有指定能力的敌手们，对于其中任意一个敌手，安全必须被确保。换句话说，安全与否只考虑敌手能力，不受敌手具体策略左右。

22. 密码分析（作业）

• 在COA下，对密文的需求与密钥空间规模有关。多表移位 > 单表替换 > 移位
• 在KPA下，很容易破解。
• 通过古典密码学到的教训：

• 充分密钥空间原则
• 设计加密方案是一项艰巨的任务
• 复杂性不意味着安全
• 任意敌手原则

• 从上述古典密码学历史中可以认识到一个道理：从提出一个加密方案，到被该方案被破解，再到针对破解方法提出一个新加密方案，这种“打补丁式”的路线难以保证安全。那么，我们该如何研究密码学呢？

• 凯撒无密钥，增加密钥得到移位密码
• 移位密码密钥空间太小，增加替换变化程度得到单表替换
• 单表替换中字母频率不变，增加位置因素得到多表替换
• 多表替换中周期间隔的字母频率不变，怎么改造？

23. 现代密码学原则：定义，假设，证明

• 现代密码学原则：定义，假设，证明

1. 安全和威胁模型的严格定义的形式化
2. 当一个加密方案的安全依赖于无法证明的假设时，这个假设必须被精确地描述并且尽可能地小
3. 加密方案应该带有一个基于以上定义和假设对安全性的严格证明

24. 原则1，对精确定义的形式化

• 如何形式化私钥加密的安全？
• 已知密文，没有敌手能够找到密钥， E n c k ( m ) = m \mathsf{Enc}_k(m)=mEnck(m)=m
• 没有敌手能够找到与密文所对应的明文，E n c k ( m ) = m 0 ∥ A E S k ( m ) \mathsf{Enc}_k(m)=m_{0}\| \mathsf{AES}_k(m)Enck(m)=m0∥AESk(m)，其中m 0 m_0m0表示第一个比特
• 没有敌手能够确定与密文所对应的明文中任意字符，m = 1000 m=1000m=1000, 但有人能知道 800 < m < 1200 800 < m < 1200800<m<1200
• 没有敌手能够从密文中获得关于明文的任何有意义的信息，但如何定义“有意义”?

25. 原则1，如何定义

• 根据图灵对计算的定义，需要直觉，证明定义等价，用该定义来解决例子。
• 后面将学习很多密码学相关定义，大家体会。

26. 原则2，依赖于精确的假设

• 大多数密码学构造不能够被无条件的证明安全。
• 换句话说，当假设为真，则构造安全。
• 假设需要验证，方案需要比较，证明需要假设。
• 简单，低级的假设容易被研究，拒绝和修正。

27. 原则3，安全性的严格证明

• 安全性需要否定式证明，如何证明没有人能破解？如何证明“地球上没有龙”？
• 规约法（Reduction）：给定假设X很难是真，则根据定义构造Y是安全的。
• 证明：将难题X的问题规约到破解Y的问题。
• 这里X中每个问题都是难题，假设其无法解决。
• 规约的意思是，可以将每个X中的问题转换为一个破解Y的问题，并且若一个破解Y的问题有答案，则可以由此答案构造一个对X中该问题的解。这里试图证明对Y的破解问题比X中问题要难。假设X中问题无法解决，而破解Y比X中问题还难，则破解Y也不可能。

28. 总结

• 密码学保护信息、事务和计算安全
• Kerckhoffs原则，开放密码学设计
• 凯撒、移位、单表替换、多表替换
• 蛮力，字母频率，Kasiski方法，重合指数（IC）
• 充分密钥空间原则
• 任意敌手原则
• 严格证明安全