现代密码学初探

本博文是学习斯坦福-密码学课程的笔记，参考视频：【完整版-斯坦福-密码学】全13讲

在这个仓库里Crypto_Implement，我使用C++对密码学基本算法进行了实现。

01-绪论

课程目标

• how crypto primitives work
• how to use them correctly and reason about security

偏理论的一门课程

密码学无处不在

• 安全通信
  • web通信：HTTPS(SSL)
  • 无线通信：802.11i WPA2（WiFi），GSM（手机流量），Bluetooth（蓝牙流量）
• 加密磁盘上的文件
  • EFS，TrueCrypt
• 内容保护(e.g. DVD Blu-ray)
  • CSS（DVD使用的加密)）内容混淆系统，易破解
  • AACS（蓝光碟使用的加密）
• 认证

安全通信

HTTPS，SSL，TLS

1. 无法窃听
2. 无法篡改

TLS

两个主要部分，使用的是公钥技术

保护磁盘上的文件

可以看做今天的Sam和明天的Sam进行通信，安全通信和安全文件从哲学上讲是一样的。

对称加密

以分组(Building Block)的形式保护流量的技术叫做对称加密(sym. encryption)

在对称加密中，只有密钥是不公开的。要注意，加解密算法都是公开的，并且经过业界长时间检验。启示是：坚持标准算法，摒弃私有算法。私有加密算法被逆向之后很容易分析破解。

密钥类型(Use Case)

• 一次密钥
  • 密钥只去加密一条信息
    • 加密邮件：每个邮件都生成一个新的key
• 多次密钥
  • 密钥去加密多条信息
    • 加密文件：很多文件使用相同的key
  • 需要更多机制确保加密系统是安全的

Things to remember

Cryptography is:

• A tremendous tool
• The basis for many security mechanisms

Cryptography is not:

• The solution to all security problem
  • 软件有bug
  • 社会工程攻击（攻击者欺骗用户去做会伤害到用户自己的事情）
• 实现不正确，密码学将不起作用（e.g. WEP）
• something you should try to invent yourself
  • many many examples of broken ad-hoc（临时的，特定的，自组织的） designs

什么是密码学

Crypto Core

• 密钥建立
  • 协议最后，达成共享的密钥K
  • 通信的对象应该知道双方是谁
  • 攻击者监听会话，无法得知共享的密钥
• 安全通信
  • 达成密钥之后使用密钥来安全地交换信息
  • 加密机制提供了confidentiality and integrity（保密性，完整性）
  • 攻击者无法篡改，一经篡改即被监测到

一些例子

• 数字签名
  • 原理上是手写签名的类似，现实中手写签名总是保持一致的，不同文件签同样的字。
  • 但区别是攻击者获得文档的数字签名后他可以复制粘贴到本人不想签字的文档上。所以一般数字签名对于不同文档通常不一样。
  • 数字签名是待签内容的一个函数值，所以攻击者单纯复制签名将无法成功，通不过新文件签名函数的检验。
• 匿名通信(mix net)
  • 经过一系列代理让服务器无法得知客户端的真实身份。
  • 通信的双方也不知道对方的身份。
  • 代理也不知道真实通信的双方的身份。
  • 有趣的一点是双方不知道身份，但是通信的过程是双向的。
• 匿名数字现金
  • 花掉数字货币但是不知道花掉人的真实身份。
  • 如何阻止复制的数字货币被double spend（重复花费）。
  • 某些情况下，安全和匿名是相悖的。
  • 匿名数字货币的处理方法是：如果只花费一次，那就是匿名的，但是如果重复花费，个人信息就会暴露。

协议

• 选举系统
  • 要解决进行选举，但是不必知道每个人投票具体是什么这样的问题。
  • 解决方法是：设置一个选举中心，来计算选举结果，但是保密投票结果，从而个人投票是保密的。
  • 同时选举中心需要对投票者进行检验。
• 私密拍卖
  • 采用Vickrey拍卖，中标者为出价最高者，但付的钱是第二高的出价。
  • 规则：最高价格保密，个人信息保密。需要知道的只有第二高的价格和最高出价的人是谁。
  • 需要设置一个拍卖中心，拍卖中心完成计算。
  • 这是一个更广泛的问题，叫做安全多方计算。
• 安全多方计算（Security multi-party computation）
  • 目标是从多方收集输入，通过函数计算之后输出结果，但是要对输入保密。
  • 方法一：引入一个可信任的第三方，收集输入并公布结果。
  • Thm: “anything the can done with trusted auth. can also be done without” 意思是，在系统中去掉可信任第三方，使用某些协议相互通信，在协议的最后，函数值突然被大家所知，除此之外没有任何信息泄露。

Crypto magic

有些密码学应用很难进行分类。

• 私有外包计算
  • 以google搜索作为例子，用户将搜索加密后发送给google，由于加密机制的特性，google可以在加密后的值上运算，无需知道原文是什么，可以在加密请求上运行庞大的搜索算法。并得到加密的结果，返回给用户后解密后就会得到搜索结果了。
  • 神奇的是google只能看到请求的加密形式，所以google并不知道用户搜的是什么。
  • 比较新的技术，允许加密数据上的计算，尽管不知道加密的内容。（仅是理论结果）
• 零知识（证明）
  • 质数相乘很好计算，但是质因数分解具有困难性，来构造公钥密码系统。
  • 
  • 用户可以在不告诉服务器质因数p和q是什么的情况下，证明自己知道N的两个质因数分解。
  • 可以向别人证明你知道一些问题的解，及时别人不知道具体解是什么，但是可以信任你知道这个问题的解。

A rigorous Science（严谨的科学）

会反复使用的这三步：

• 在引入一个原型时，需要准确描述威胁模型是什么，以数字签名为例，需要讲清楚攻击者如何攻击数字签名，伪造签名的目的何在
  • 先定义数字签名的作用：防伪，然后定义威胁模型
• 提出架构：定义签名不可伪造的意义，比如如果有人可以破解这个架构，他也可以用他的破解方法来解决因子分解的问题。（找出架构的等价数学问题）
• 证明任何攻击者在这个威胁模型下，可以攻击这个架构的攻击者，也可以用来解决根本性的问题。意思是，如果问题很难，就证明了攻击者无法在威胁模型下，破解这个架构。

密码学历史

对称密码

历史上的例子（all badly broken）

替换式密码[罗马时期]

• 秘钥是一张替换表，字母的一个映射关系。

• Casear Cipher（no key）凯撒密码

  • 凯撒密码没有key，所以凯撒密码不是密码

替换式密码如何破解

• 密钥空间有多大，一共有多少个不同的密钥。
  • 一个替换表形式的密钥就是26个字母的一个排列。即26的阶乘，约为2的88次方。即一个替换密钥需要88位。即每个密钥用88位的一个二进制数来表示。
  • 完美安全的密钥空间大概也是这个范围。
  • 使用字母的频率来进行破解。在英文文献中，字母E的出现频率最高
• 如何破解一个替换式密码？
  • 使用英文字母的频率，
    • e出现的频率大约在12.7%，t出现的概率大约在9.1%。a出现的概率大约在8.1%。
  • 使用字母配对的概率（digrams）
    • he, an, in, th等叫做二合字母，接着可以推出三合字母。
    • 使用唯密文攻击即可攻破，并且还原原文。所以替换式密码没有什么用，因为攻击者可以轻易的攻破。

Vigener cipher[文艺复兴时期]

• 秘钥是一个单词，例如k=crypto，将k拓展到和明文一样长，然后相加，就可以得到密文。同时将结果模上26。
• 
• 解码就是加密的逆过程，即用密文减去拓展后的k。

如何破解Vigener cipher

• 首先假设知道k的长度，如上图为6。然后对密文进行分组。对每一组内相同位置的字母进行统计研究，即可知道E加密后的字母是什么，即可倒推出加密的K是什么。
• 需要注意的是假定知道了密钥的长度。如果不知道密钥的长度，可以枚举密钥长度的值，然后进行解密。最后最通顺的句子就是正确的密钥长度和密钥。所以还是唯密文攻击。

Rotor Machines（轮轴机）[电气化时代]

• Hebern machine
  • 碟片其实是密钥，碟片编码了一张替换表。每一次按键碟片会转动一格。
  • 
  • 只要密文够多，直接还原密钥和明文并不难。破解方法还是统计字母频率，和配对频率和三合字母频率即可破解。同时还是唯密文攻击。
• Enigma
  • Enigma是一种复杂的轴轮机。使用了3,4或5个轴轮，Enigma有多个版本。
  • Enigma的密钥是轴轮的初始设定。每个轴轮的情况有26个不同密钥。在打字机打字时，这些轴轮以不同的速率旋转。在打字时，轴轮旋转，输出合适的字母即密文。这时密钥数位26的轴轮个数次方。约为2的18次方，密钥空间比较小。
  • 
  • Bletchley Park对Enigma发起了唯密文攻击，对二战的胜利起到了作用。

Data Encryption Standard（1974）

• DES，IBM提出，成为一个联邦数据加密标准。
  • DES的密钥空间为2的56次方，现在看起来已经很小了。
  • 这个加密标准一次加密64位，也就是8个字母。
  • 因为DES的密钥空间很小，现在可以进行暴力搜索破解。所以现在DES是不安全的，工程项目汇总已经不能使用了。
• 现在的加密标准：AES（2001），Salsa20（2008），等等
  • AES使用的128位密钥

离散概率

经过数年，许多自然的密码学机制被发现是不安全的。因此，现代密码学是一门严谨的科学，其中的机制总是有其安全性证明。用来证明的语言依赖于离散概率。这个维基百科介绍的更加详细一些。

概率分布

• 均匀分布
  • 集合中每一个元素的概率都是相同的。即每个元素的概率都是元素个数分之一。
• 点分布
  • 把所有权重放在一个点上，其他的权重赋值为0。
• 因为U是有限集，所以可以写出U集合中每一个元素的权重。表现出向量的形式。
• 

事件

并集上界

并集上界可以用来估算概率的上界。

随机变量

随机变量是比较直观的，但是随机变量的形式化定义不是很好理解。

说实话没太听懂这张ppt在讲什么。后来又看了一下ppt，感觉讲的是随机变量是一个函数，可以完成一个集合到另一个集合的映射。

均匀随机变量

讲的应该是r是一个特殊的随机变量，指的是在U上的一个均匀分布的随机变量。

讲的还是随机变量的特性。

随机算法

算法分为确定算法和随机算法。

• 确定算法

  • 给定一个输入，输出总是确定的，可以看做一个函数

• 随机算法

  • 除了一个输入以外，还有一个隐形参数R，每次算法运行时会对R重新取样，所以计算出的结果是不确定的。

  • 可能在讲解一次一密的加密过程。

  • 给定一个特定的输入信息M，就定义了一个随机变量，即定义了所有的这个算法可能输出集合的一个分布。

独立性

如果两个事件是独立的，当且仅当P（A and B） = P（A）* P（B）

• 当你知道A发生时，并没有告诉你B有没有发生的信息。
• 用乘法来表示概率的联结。

同时独立性可以作用在两个随机变量上，设有两随机变量x和y，它们从集合V中取值。

证明独立性可以对两个并集的概率使用乘法性质进行检验。

异或

二进制下的异或就是二进制的加法并对2取模。所以异或操作其实是逐位使用模2加法。本节课需要大量的异或运算，一个笑话是密码学家只会玩异或运算。

下面是异或的一些性质：

若两个随机变量X和Y，X是分布均匀的，正常情况下，Y也是均匀分布，这样异或后的结果Z也将是均匀分布。在一些情况下，Y是恶意的分布，当X和Y异或之后的结果Z的分布将还是均匀的。这是一个重要的性质。使得异或在密码学中非常有用。

这个简单原理就是异或在密码学中如此重要的原因。

生日悖论

如果在一个集合中取样集合的大小的平方根次，那么很有可能出现两次取样重复的情况。这个问题刚开始是在一个房间里至少有多少人就可以使得两个人的生日日期相同。这个问题的答案就是1.2*365的平方根。大于等于24人。这样两个人生日相同的概率就大于二分之一了。之所以叫做悖论，是因为24比人预期低得多。

有意思的是，人们的生日分布并不平均，生日的分布有偏向于9月份。

形象的看一下生日悖论的分布，当样本容量在10的6次方的范围的时候，概率很快就收敛到1。当取样2200次时，两次取样相同的概率大约是90%。3000次的时候基本上就是1了。

02-对称密码

密码的定义

密码是由两个算法组成的，分别是加密算法和解密算法。事实上，定义这样一个三元组，（K，M，C）。这个三元组某种意义上定义了密码的环境。密码本身是一对算法E和D，（E，D）。

• K指的是密钥空间，是全体可能的密钥的集合。
• M是全体明文的空间。
• C是全体密文的空间。
• E是加密算法，E输入密钥和明文输出密文。
• D是解密算法，D输入密钥和密文输出明文。

密码要满足一致性方程。每个密码都要满足它，否则将会无法解密。一致性要求指的是对于m∈M，k∈K，D(k,E(k,m)) = m。

• 有效打了引号，不同的人理解不同。
  • 如果倾向于理论，多项式时间的算法就算是有效的。算法E和D必须在多项式时间内完成，不同的输入范围时间不同。
  • 如果倾向于应用，必须在特定时间内完成才算有效。
• E常常是一个随机算法，D常常是一个确定算法。
  • E是随机算法指的是，当加密信息时，算法E自己生成随机二进制数，并使用这个随机二进制数来加密给定的明文信息。
  • D是确定算法指的是，密钥和密文输出总是一致的，算法不依赖任何随机性。

一次性密码本

第一个“安全”密码的例子，又叫做Vernam密码。

• 明文空间和密文空间是全体n位二进制字符串的集合，密钥空间和明文空间是一样的，也是全体n位二进制字符串的集合。
• 一次性密码本的密钥就是一个随机字符串，是一随机的二进制序列。密钥与待加密的明文等长。
• 密文就是密钥和明文异或的结果，（异或就是模2加法）。
• 解密的明文就是密钥和密文异或的结果

之后需要证明满足一致性要求，如果满足一致性要求，就可以确定一次性密码本确实是密码。

但是没有解释其安全性。一个问题，如果给了m和c，可以轻易的还原出k，只需将m和c进行异或即可。

从性能来看，一次性密码本可以在极快的速度异或密钥和信息得到密文。可以加解密很长的信息。

但在现实中这个方法很难使用，因为密钥需要和明文等长。并且如果A想要和B安全通信的话需要在明文前传输一段和明文等长的密钥，如果A有办法安全的传给B一个密钥，那他同样可以使用这种方法传输明文。所以密钥和明文一样长是很有问题的，一次性密码本在实际中很难用。

信息安全论

一次性密码本是安全的吗？什么是安全的密码，什么让密码变得安全？

• 香农信息论中分析了一次性密码本，香农定义的安全基本想法为：
  • 如果你得到密文了，从中你的不出一点关于明文的信息。即密文不揭露任何明文的信息。
• 香农形式化的定义了明文的信息
• 
• 意思是，如果攻击者截获了一段密文c，密文c是m0加密结果的概率和是m1加密结果的概率是严格相等的。所以如果有一个截获的密文c，将无从得知是从m0来的还是m1来的。其中k是K上的一个均匀分布。
• 即对于完美安全的密码，任何唯密文攻击都是无效的。

一次性密码本完美安全证明

• 如果密钥空间作为分母，对于任意的m, c 来说，E(k, m ) = c 的 k的个数是一个常数，那么密码就是完美安全的。即概率是均等的。
• 对于一次性密码本来说，c = m 异或 k，即 k = m 异或 c。即对于一对确定的m和c来说，k的取值唯一，即上文中的常数为1，所以一次性密码是完美安全的。
• 同时可知，对于一次性密码本，唯密文攻击无效。（但是还有别的攻击可能：比如如果密钥不换，两次c异或就会消去k）
• 一个问题是，对于密钥分配来说，如果有办法安全的分配和明文等长的密钥，那么就可以用相同的方法传递明文。

香农的结论

• 如果一个密码是完美安全的，那么存在|K| ≥ |M|。密钥长度不小于明文长度。
• 很难用，因为没有告诉我们如何分配密钥。

流密码

• 在流密码中，密钥不是完全随机的。将使用一种伪随机密钥。
• 伪随机数生成器（PRG）：是一个函数G()，输入是一个长度为s的种子，输出是长度为n的比特串，n远远大于s。
• 一个简单的思路是，将s作为密钥k，加密算法c = E(k, m) := m 异或 G(k)。解密算法D(k, c) := c 异或 G(k)。
• 流密码不是完美安全的。
• PRG需要具备的一个性质叫做：不可预测性。可预测性是指，对于给出前i位的伪随机数，可以预测出第i+1位。这样的流密码是不安全的。一个例子是，如果知道了明文的一部分前缀n，则将n与c异或，则可以得到k的一个前缀，则k即可被预测。
• 可预测性的定义为：如果存在一个高效函数A，对于存在的一个位置i在1到n之间，A（伪随机数的前i位）= 伪随机数的第i+1位的 概率 ≥ 二分之一加常数ε。不可预测指的是对于任意的位置i，都不存在这样的高效函数A。

脆弱的PRG例子

• 线性同余的例子：r[i] = a * r[i - 1] + b (mod p)。具有过于良好的统计学性质，不应当使用。

• glibc库里的随机生成函数。不满足密码学中的随机性。

• 实用派的可预测的常数定义：

  • 大于2的30次方分之一，加密1GB数据会出现一次。
  • 小于2的80次方分支一，概率小到不会发生。

• 理论派的可预测的常数定义：

  

  • 是一个安全参数相关的函数。如果函数值经常大于1除以多项式的值，那么是不可忽略的。反之可忽略。
  • 即ε (λ)下的分母是一个比多项式高阶的函数，则是可忽略的，反之则不可忽略。

针对一次性密码本的攻击

• 两次密码本攻击：如果密钥不换，两次c异或就会消去k，得到两个明文的异或，就可以分别拿到两个明文。（不要使用两次相同的密钥）

• 例子：MS-PPTP，客户端和服务器的双工通信中，使用了相同密钥。802.11b WEP 将密钥的后102位和前26位进行拼接之后得到密钥。密钥中大部分重复。

• 对于每一帧都改变密钥的改进方法是，将同意密钥产生的PRG字符串进行分割，后给后每帧使用。

  

• 另一个例子就是可修改性，对于m通过加密之后的密文m异或k，可以附加一个异或p，在进行解密时无法发现信息是否被篡改。即对密文的异或都会对明文产生影响。

• 老的例子：RC4，产生的随机序列并不均匀。

• 混淆系统（CSS）：DVD的加密算法。CSS是基于硬件线性反馈移位寄存器（LFSR）。

  

• 以上的加密算法都是基于LFSR实现的，但是均被破解了。

  

• 破解方法是：前20字节明文是固定的，和密文异或得到密钥的前20字节K。暴力枚举17位LFSR的所有可能，并使用K的前缀反推25位LFSR的内容，反推出后接着生成密钥和K的后缀做对比验证。从而获取正确的LFSR的初始值即完整的5字节K。

好的流密码

• 例如eStream提供的5种流密码算法（2008年），将PRG中的参数设置为密钥k和一个新鲜值r。

  

• 其中一个例子就是Salsa20：

  

• 通过改变序号i就可以源源不断的产生随机序列。其中函数h是一个映射表。

PRG安全性定义

• 伪随机分布应该和均匀随机分布无法区分。

  

• 可以定义一个测试A（x），考虑这样几个指标：

  • 所有0和1的个数的差值。
  • 连续两个0在x中出现的概率和n/4的差值。
  • 0的最大游程。

• 定义一个随机数发生器的优势：

  • 如果一个随机数发生器的统计测试优势接近1，叫做该统计测试破解了发生器G。
  • 如果一个随机数发生器的统计测试优势接近0，即该统计测试无法区分发生器和真随机数。

  

  

• 对于上述的例子，可以说A以1/6的优势破解了随机数发生器G。

• 所以安全PRG算法的定义是：找不出一个有效统计测试A，使得A对于算法G的优势是不可忽略的。但是不能反证，因为反证等价为P=NP命题。所以无法严格的证明某个PRG是安全的。
• 得到结论：一个PRG是不可被预测的。
• PRG的安全性和PRG的不可预测性是等价的。

流密码的安全性

• 定义安全常常从攻击者可以干什么的角度进行定义。
• 定义1：从密文无法推得密钥。（并不是好的安全定义，可能泄露所有的明文）
• 定义2：从密文难以还原整个明文。（并不是好的安全定义，可能泄露部分明文）

• 香农的定义：从密文学习不到任何明文的内容。（定义过于强，难以实现）等价为两个密文的分布是不可区分的。
• 定义3：两个密文的分布是计算上不可区分的。（定义还是很强，难以实现）可以缩小一下范围，将任意两个明文改为攻击者可能想到的明文范围。（选择明文攻击下也是安全的）

• 语义安全的定义：如果对于所有有效的攻击者，优势可以忽略。即在计算上是不可区分的。

证明：流密码是语义安全的。

1. 构造试验E(0)和E(0.1)分别表示攻击者区分使用G(k)和R加密m0，攻击者不可区分。（PRG的安全性）
2. 构造试验E(0.1)和E(0.2)分别表示攻击者区分使用R加密m0和m1，攻击者不可区分。（一次一密具有语义安全性）
3. 构造试验E(0.2)和E(1)分别表示攻击者区分使用G(k)和R加密m1，攻击者不可区分。（PRG的安全性）
4. 从而得到E(0)和E(0.1)计算上不可区分，E(0.1)和E(0.2)计算上不可区分，E(0.2)和E(1)计算上不可区分，由传递性可知E(0)和E(1)在计算上不可区分，得证。

所以由PRG构造的流密码是语义安全的。

03-分组密码

3DES

• 由一个K产生多个k，明文经过轮函数和各个密钥产生操作，经过n轮轮函数，即可得到加密结果。在3DES中n等于48。

• 分组密码比流密码慢很多。

PRPs 和 PRFs 的安全性

• 伪随机函数（PRF）指的是一个函数，对于一个K来说，一个输入空间X可以计算出对应的输出空间Y。只需保证可计算即可。
• 伪随机置换（PRP）指的是一个函数E（K，X），输出结果空间也为X，即E是建立在X上的一个双射。对应的函数E（K，X）也应该是可逆的，逆函数为D（K，X）。
• 简单来说，PRP是PRF的特例，因为X=Y，你可以高效的对E求逆。

如何证明PRP或者PRF的安全性呢，我们还是和流密码相同，定义一个优势Adv，比较给定的PRP或者PRF和真随机函数或真随机置换之间的优势，若优势可忽略，则该PRP或者PRF是安全的。

Feistel网络

• 将多个轮函数连在一起就可以构成一个Feistel网络，Feistel网络是一种构造可逆函数的好方式。DES就使用了Feistel网络。但是AES没有使用。

• 关于Feistel的一个定理是：如果使用了一个安全的PRF，那么使用PRF的三轮Feistel也是一个安全的PRF。

• DES的结构是，一个16轮的PRF函数，每一轮的函数都会有一个秘钥，其中这个每轮的秘钥是通过一个主秘钥扩充得到的。

• 其中的PRF函数就是DES中的S盒。 其中S盒需要有一些性质：

  • S盒不能是线性的。
  • S盒是DES中唯一非线性的部分。
  • 设计出的S盒和线性函数差距很远。

• 不要使用自己设计的分组算法，因为会有以下类型的攻击：

  • 通过学习解密密文的时间可以学习出秘钥。
  • 通过学习解密时的功耗来破解秘钥。（差分功耗攻击）
  • 通过观察多核的缓存缺失来推测出秘钥。（以上都是旁道攻击）
  • 错误攻击：让解密或加密时的某个处理器异常工作，输出错误的数据，进行分析。理论上说，出现一次错误计算，秘钥就已经泄露了。

  所以不要尝试设计自己的密码，也不要尝试自己做密码的实现。

对DES的攻击

• 线性差分攻击：因为第五个S盒设计的有些接近线性函数，所以对整个算法产生了影响。

  线性差分攻击只需2的42次方次就可以破解秘钥。

• 量子攻击：使用量子计算机来用平方根的时间复杂度来找到一个秘钥。即只需秘钥空间大小的平方根次即可。

  所以对于128位的秘钥也将变的不安全，只能使用256位的秘钥。

  AES算法

• 在一个分组加密算法中，秘钥越长，密码越安全，但是也会更慢。

• AES中一些步骤可以通过预计算来减少AES运行的时间。

  针对AES的攻击：

• 最好的攻击可以比穷举算法快4倍，这样是可以接受的。

• AES-256算法在秘钥扩张的设计上有缺点。会导致一个2的99次方复杂度的攻击，这样的攻击也是可以接受的。

使用PRG来构造PRF

• 对于定义的F来说，如果G是一个安全的PRG，那么F是一个安全的PRF。

• 构造一个将G的两个输出后面接上两个新的G，这样的G1，就可以得到一个两位的PRG。

• 将该函数如此使用N次，就可以构造一个 GGM PRF。输出为定义在2的n次方大小的空间上的函数。这就构造一个安全的PRF函数。但是效率会很慢。

安全PRF定义

• 设计了一个实验，基于输出的EXP(b)的概率定义了观测者A对于F的优势，如果A对F的优势是可以忽略的，即区分真随机和F的优势可忽略，则说明该PRF函数F是安全的。
• PRP同理。可以看PRP的一个例子：

• 该例子中由于k是随机的，所以两种可能是相等的，和随机函数一致。

安全PRP的例子：

• 3DES，AES等。
• AES对于2^80量级的运算，攻击者A对于AES的优势小于2^-40。
• 对于刚才那个例子，如果不是PRP，而是PRF，那么将是不安全的。

• 导致这一问题的关键在于X太小了，使得PRP不是一个PRF。

• 一个重要的引理是：一个安全的PRP也是一个安全的PRF，前提是PRP的X集合要足够大。

• 课程建议忘掉AES和3DES的内部原理只需要记住这是两个安全的PRP即可（好耶），然后看如何使用他们

一次性密码来使用分组密码（ECB）

• 电子密码本（ECB）已经被完全破解了！即使用相同的秘钥，但是把明文分组，对于不同的分组使用相同的密钥进行加密。
• 一个问题是，如果明文分组中有两组的明文完全相同，则不需要知道密钥即可知道这两组明文是相同的。然而这是不应该的。
• 我们要达到的目的是一次密钥的语义安全性。对于攻击者A来说，无法分别出通过加密算法加密明文m0或m1的加密结果的明文到底是m0还是m1。

• 对于ECB来说，攻击者如果想，总能区分出m0和m1，所以ECB不是语义安全的。得到的结论是，不要使用ECB加密超过一个的分组。

计数器模式（CTR）

• 一种新的模式是计数器模式（CTR），使用安全的PRF即AES或则3DES，可以生成伪随机密钥，这个伪随机密钥和明文异或生成的流密码就是安全的。

• 以上是一个简单的图像证明，证明计数器模式是语义安全的。
• Q:但是对于m0和m1中出现重复的情况下，加密后得到的c还是有部分相同？
• A:并不会，对于PRF来说是可能的，对于流密码来说是不成立的。

选择明文攻击的语义安全性（CPA）

• 攻击者的能力：选择明文攻击（CPA）。
• 在选择明文攻击下定义语义安全，需要两个实验。和之前的实验相同的部分是，b=0的实验和b=1的实验分别代表加密者加密了m0或者m1。
• 不同的部分是：攻击者可以重复上述实验最多Q次，加密者对于每次请求返回的实验类型相同，即都是实验0进行的加密或者实验1进行的加密，攻击者需要综合Q次实验分辨出自己处于实验0还是实验1。
• 这个实验对于攻击者来说，如果想要知道选择的明文M的加密，只需在第J次询问时将两个明文m0和m1都设置为M即可。 （这就是选择明文攻击的意思）

• 这个实验的设计使得游戏是满足选择明文攻击的定义的。

对于选择明文攻击来说，一次性密码和计数器模式在选择明文攻击下都是不安全的。

• 所以对于选择明文攻击来说，需要相同的明文输出的密文也不同才可以保证安全性。 即，这样的加密对于相同的输入来说输出完全相同。（只有在相同的明文输出的密文也不同的情况下挑战者才能赢得游戏）。
• 两个场景来说：1.如果硬盘上加密了两个相同的文件，攻击者可以在不解密的情况下知道这两个文件是相同的，但是这不应该让攻击者学习到。2.对于加密传输的两个网络包来说，如果两个加密包是相同的，攻击者也可以通过选择明文攻击的方式得知这两个加密包是相同的。

基于新鲜值的加密

• 解决这一问题有两种方法：

  • 随机加密的方法：对于加密算法来说，一个特定的明文m0会被加密映射到一个集合中，解密时也会将该集合中的所有元素解密到m0的映射。

    这样的影响是：密文的长度将比明文长，因为随机值的信息被编码进密文中了。 将会加大加密的开销。

    我们设计这样一个E(k,m) = [r <- R, output (r, F(k,r)异或m)] 。可以说，这样的一个加密是安全的，只要R的空间足够大，以至于r的选择不会碰撞即可。

  • 基于新鲜值的加密：对于加密函数来说，除了密钥之外，还需要提供一个唯一的新鲜值。这个新鲜值只需要保证对于明文来说是唯一的即可。新鲜值可以随机产生，也可以使用计数器隐形的维护。

    如果新鲜值是随机产生的，那么就变成了随机加密的方式。

• 所以需要讨论基于新鲜值的选择明文攻击的安全性，如果对于维护计数器的值来说，由于新鲜值是攻击者提供的，所以攻击者可以选择攻击某个特定的明文，例如第15个明文。但是对于加密者来说，不会接受两个新鲜值相同的明文的加密请求，这要求攻击者必须保证新鲜值的不同。

• 我们常说基于新鲜值的加密是针对于选择明文攻击是安全的。

• 因为对于真随机函数来说也无法区分基于新鲜值的加密的选择明文攻击的不同处，所以通过PRFs加密的也是安全的。

  密码分组链接模式（CBC）

• 密码分组链接模式（CBC）是一种对于CPA安全的密码模式。

• 首先是基于随机向量IV（意思是初始向量）的密码分组链接模式：

• 注意，IV应该是和密钥K在一起，而不是密文的一部分。

• CBC在针对CPA的安全性：

• 保证CBC的安全性只需保证后面加的误差项是可忽略的即可。

• 这告诉我们不同的密钥的使用寿命，使用多少次之后秘钥就是不安全的了，而且可以看出，AES的安全性要比3DES要好，这是因为明文空间大小导致的。
• 一点值得注意的是，IV向量最好是不可被预测的，这点很重要。

• 如果IV可以被预测，则这样的加密系统就是不安全的。

然后是基于新鲜值的CBC模式：

• 对于这个模式中的新鲜值一定要使用单独的k1来进行加密，并且k1不能等于k。

• 如图在OpenSSL中iv没有被加密，而是使用了用户提供的IV，如果你的IV不随机，则该CBC对于CPA是不安全的。

• 如果明文分组的长度不够，则需要填补明文来保证是分组长度的倍数。

随机计数器模式

• 对于这种模式，加密是可以并行运算的，对于CBC模式，每一条密文的产生依赖前一条密文，所以只能串行计算，但是对于随机计数器模式，可以进行并行运算。

还有一种是基于新鲜值的计数器模式：

• 将IV变成新鲜值和计数器相结合。

• 现在大多数都从CBC转向了CTR。

• Q:CTR的加密会出现异或的值被改变的情况，这在传输过程中无法被防范。

• A：是的，现在讨论的安全性是CBC和CTR在防窃听场景下的安全性，而不是防篡改的场景。所以需要加上完整性防护之后才可以使用。

04-信息完整性

• 保证完整性，但是不保证私密性。
  • 系统文件。
  • 广告。
• 信息完整性机制：消息验证码（MAC）。

• 经常容易忽视的一点是：人们常常会忽视密钥K。对于一个没有密钥的MAC函数，例如循环冗余验证码CRC，攻击者很容易破坏完整性。
• 考虑如果攻击者直接删除CRC生成的验证码，并将正确明文m0替换成自己构造的明文m1，并且生成m1的循环冗余验证码，那么对于验证者来说无法区分这条明文是否被篡改过。（CRC是为检测随机错误而设计的，并非针对恶意错误的。）
• 对于使用密钥k的MAC来说，如果攻击者不知道密钥k，则不能产生正确的消息验证码。

MACs的安全性

• 攻击者的能力：选择信息攻击。
• 攻击者的目标：存在性伪造。
  • 即试图产生某些有效的标签，不同于选择信息攻击里获得的q个信息标签对。
  • 给定一个信息标签对(m,t)，攻击者不能产生一个合法信息对(m,t’)并且t不等于t’。

• 以上是对MAC安全性游戏的定义，并且定义攻击者的优势，只有攻击者的优势是可忽略的，这样的MAC才是安全的。
• 例子：系统中的文件被用户密码产生的k 所加密的MAC函数保护。对于恶意攻击者来说，无法创造满足MAC校验的文件，即可保护电脑中的文件不被损坏和增添。

一类安全的MACs

• 很显然的是，一个安全的PRF，是一个安全的MAC，只需将加密的密文c作为标签t即可。
• 一个坏的例子是：将信息通过k操作之后得到一个10位的标签Y，这样的MAC是不安全的，因为Y的空间太小了。
• 得到一个推论是：对于使用PRF构造的MACs，攻击者的优势是PRF的优势加上1/|Y|。所以当标签空间很大时，优势可忽略。
• 因为AES是一个安全的PRF，所以由AES构造的MACs被认为是安全的。但是AES只有16字节，如何求大量数据的MAC呢？
  • CBC-MAC（常用于银行间的支票完整性确认）
  • HMAC （常用于因特网中的协议）
• 一个很有用的引理是：对于一个安全的PRF，只输出前k位，结果依然是安全的PRF。大PRF对于任意输入的固定N位输出可以截断取前t位，这前t位依然是安全的。（但是t也有一个下界，大概是64位）

CBC-MAC和NMAC

• 最后一步的加密很重要，没有加密的过程叫做原CBC，这样的CBC并不是一个安全的MAC。
• 另一个MACs构造是NMAC，即对MAC进行嵌套。

• 第二种构造在最后一个F之前的绿色部分叫做级联，级联也是不安全的，需要经过最后一个k1的加密之后得到的tag才是安全的。属于X或者属于K其实就是消息的长度是X的大小还是K的大小。其中这些F产生的都是K。

对原CBC和NMAC级联的攻击

• 对于NMAC来说，可以进行拓展攻击，对于一个已经知道的m的tag0，可以伪造出一个m||w的tag1，因为已经知道了 tag0，那么对于新附加的信息w，计算密钥位tag0的F函数值tag1，即为合法的攻击。拓展攻击是针对级联攻击的唯一一种攻击，所以需要最后一个加密进行保护。
• 对于原CBC来说，拓展攻击比较困难。因为知道了原始的tag0之后，对于拓展的信息w，可以知道异或值，但是并不知道CBC的密钥，所以说无法计算出拓展了w之后的tag值。
• 但是可以考虑这样一个攻击，对于一个长度为单个分组的信息m，计算原CBC标签t，可以构造这样一个合法信息w = (m, m xor t)，该信息具有两个分组长度，使其和m共用一个合法标签t。

​

• 以上是对CBC-MAC和NMAC的安全性分析定理，只需要保证这些误差是可忽略的即可。
• 对于这个定理的应用可以告诉我们在什么时候可以更换密钥了。这个值对于AES来说是2^48。 对于3DES是2^16。
• 对于ECBC和NMAC来说具有的一个共同性质就是，构造x和y的碰撞之后，x||w和y||w也是一对碰撞。
• 由生日悖论可知在总量的平方根那么多的样本中取样时，就很有可能出现总量中的碰撞了。
• 因为CBC-MAC是基于明文空间的，所以常常使用AES来实现，NMAC是基于密钥空间的，AES不能适应密钥的经常变换，所以一般不适用AES来进行实现。

MAC填充

• 将讨论信息长度不是分组长度的整数倍时该怎么办。

• 答案是补齐信息。思考：如果单纯的在不到整数倍的分组后面补充0可以吗？不可以，因为可以构造出新的信息在之前的信息前补0，并且新的信息的tag和之前的信息tag相同。

• ISO给出的方法是：

  

• CMAC 构造：使用了三密钥结构：key = (k, k1, k2)。其中k是用于CBC-MAC加密的。k2和k3仅用于最后一个分组的补齐。

• 这个标准可以省去在无需补齐的分组后面加上一个假的分组1000…

并行计算的MAC

• PMAC：一种可以并行计算的MAC机制。

• 其中每个分组的值都可以并行计算，值得注意的是，p函数的作用是保证各个分组之间的顺序，若没有p，则无法保证整体信息的分组之间的次序。

• 并且对于填充部分，PMAC和CMAC的填充思路相同。

• 其安全性要求也是|X|的平方次是安全的。

  如果F是一个PRP，那么PMAC是增量的。我们可以算出F的逆，从而对于之前明文的某个分组的修改可以很快的计算出新的tag值。

一次性MAC

• 即任何密钥只能用于一条信息的完整性。
• 可以想到，一次性MAC是安全的，就像一次性密码本一样，对无限强力的攻击者都是安全的。而且由于一次性MAC是一次性的，所以不需要很复杂的函数，不需要PRF的构造。例如：

• 需要注意的是，如果两条信息使用同一个key进行签名，那么这个密钥将会完全泄露。即密钥是一次性的。
• CW-MAC：是一个基于一次性MAC的多次MAC机制，密钥是一个新鲜值r，明文异或一个PRF求新鲜值的结果作为明文。

• CW-MAC的验证：

• 在因特网中一个使用很频繁的MAC叫做HMAC，即基于hash的MAC。
• 思考：MAC和数字签名和数字摘要的区别是什么？数字摘要无法保证不被恶意篡改，MAC无法保证发送方污蔑接收方是接收方伪造的消息，因为一个MAC加密的信息无法区分是接收方构造的还是发送方构造的。

05-抗碰撞

使用抗碰撞函数构造MACs

• 定义一个防碰撞的函数H，如果没有一个有效的方法A使得构造H的碰撞的优势是不可忽略的，那么这个函数H是防碰撞的。
• SHA-256就是一个输出为256位的一个防碰撞函数，无法有效的构造碰撞。
• 于是我们可以定义一个MACs构造：

• hash函数的另外的作用是可以校验软件是否被篡改，即下载的软件是否完整，只需在服务器上设置一个只读的hash列表，等待软件下载完成之后计算hash检验即可。其应用场景是如何快速检查在互联网上的一个文件是否是恶意的。

针对防碰撞的通用攻击

• 生日攻击：

• 对于独立同分布，并且是均匀分布的集合B中，只需要n=1.2*|B|的平方根次抽取，抽到两个相同元素的概率将大于二分之一。并且均匀分布是最差的情况，若分布不是均匀分布，将小于n次。以下是生日悖论的证明：

• 当n=1.2*|B|的二分之一次方时，概率就是0.53。即有0.53的概率抽到两个相同的元素。
• 哈希碰撞的强度对比：

• 其中SHA-1算法已经不安全了，2的51次方次运算对于一个家用计算机来说可能几个月也就可以构造一个碰撞。

Merkle-Damgard机制

C.R. 是指 collision resistance（碰撞避免）

• 第一步：给一个短消息的CR函数，可以得到一个长消息的CR函数。

• 这就是Merkle-Damgard机制，可以将一个短消息的CR函数转换成一个长消息的CR函数。可以通过反证法来证明：

• 由右下小方块的结论可得知，一直往前推，总有一个小的h中的参数不一样，就找到了一个小h的hash碰撞，所以得证h是CR的H也是CR的。
• 使用分组密码构造 令h(H, m) = E(m, H) xor H。E是一个分组密码。这种构造叫做：Davies-Meyer构造。
• 如果不xorH的后果，构造H’ = D(m’, E(m, H))。此时E(m’, H’) = E(m, H)，就构造出了一组碰撞。

• 使用分组密码构造h的方法有很多，除了最后一个以外都是安全的。同时，异或一个H是很重要的，不然将很轻易构造出一个碰撞。
• SHA-256就是使用Merkle-Damgard方法和Davies-Meyer构造方法的加密函数，其中使用的h分组加密函数是SHACAL-2函数，输入为512bit。

可证明的压缩函数

• 一些压缩函数的原理是建立在数论困难问题上的，和这些困难问题等价，所以是安全的。

• 其基础是一个离散对数困难问题。但是计算很慢，所以一般不用。

  HMAC

• 如果H是一个CR的Merkle-Damgard 哈希函数，考虑能否使用H(k || m)作为MAC函数S(k, m)？

• 不可以，因为攻击者可以方便的在后面添加一个新的字段。给了H(k||m)可以计算出H(k||m||w)对于任意的w。

• 一个标准的方法叫做HMAC（Hash-MAC）

• 用图展示的话就是如上图的过程。如果将上面第一个h的输出看做k1，下面第一个h的输出看做k2，则可以发现这是一个NMAC机制。
• 同样的安全性能分析，假设h是安全的PRF，可以证明HMAC也是安全的，在TLS中就使用了HMAC，其h函数是SHA-1，虽然SHA-1是不安全的，但是因为SHA-1是PRF，所以并没有什么问题。

MAC的计时攻击

• 对于Python实现的一个验签的函数来说，判断相等是通过循环来判断，当出现某字节不相等时退出。

• 攻击者通过测试每一个字节的返回时间，来判断该字节是否正确，从而实验出所有的字节，从而得到明文m的签名。 解决方法是测试完所有的字节后统一返回。
• 但是需要注意编译器可能会“帮助”你优化完成找到不同才返回。
• 还有一种防御方式是，将正确的mac计算出来之后，将正确mac和sig_bytes都再求一遍HMAC，之后对比这两个值。
• 启发是，即使专家也会出错，同时自己不要实现密码，因为极有可能实现的密码对于旁道攻击是脆弱的。请使用标准库。

06-认证加密

回顾

• 私密性：加密使信息获得语义安全性来对抗选择明文攻击。只提供了对抗窃听的安全性。攻击者不会篡改数据包。需要对抗可以篡改信息的攻击者。
• 完整性：消息本身不是私密的，只确保信息在传输过程中没被修改。信息验证码MAC算法对选择信息攻击提供了不可存在性伪造的性质。
• 本章需要将私密性和完整性机制组合起来。来对抗更加强大的攻击者，即攻击者可以修改网络通信内容，感染数据包，封锁特定数据包等等。
• 目标是对抗上述攻击者，仍要保持私密性，即攻击者无法学习到明文内容，无法修改密文。

一个简单的攻击例子

• 攻击者通过修改随机的IV值，将数据包中的端口号更改为25，服务器之后将该数据包解密之后转发给Bob。Bob作为攻击者就可以看到数据包中的明文。

• 因为CBC模式加密，加密者会将密文和随机向量IV一起发送给解密者。所以攻击者只需修改随机向量IV即可修改第一个组的明文的值。

  

• 这个例子说明，如果没有完整性，一个CPA安全的加密也不可能提供私密性。

• CPA安全加密只能在攻击者只能窃听数据这一假设下，提供私密性。攻击者不能在途中修改密文。

• 本章中的许多攻击例子被叫做主动攻击，攻击者可以修改途中的通信。所以CPA安全对于主动攻击者不能保证安全。不仅不能保证完整性，而且连私密性都无法保证。

• 如果只需要完整性，则MAC即可。如果同时需要私密性，则需要一个认证加密模式。

认证加密

• 认证加密在存在主动攻击者的情况下也能保持安全。一个认证加密系统的解密会产生明文信息或者底（⊥），若⊥出现则表示该信息应该被抛弃。其中底不在明文空间中。

  

• 密文完整性的定义为以下攻击挑战游戏：

  

• 于是我们定义认证加密（AE）：

  • 是语义安全的。
  • 具有密文完整性。

• 一个反面例子就是使用随机IV的CBC加密，因为这种加密模式不会输出⊥，攻击者输入什么总会得到一些输出信息。一些随机的密文会被解密成某些不是符号⊥的东西。

• 加密认证的影响：

  • 影响一：认证。攻击者无法欺骗接受者Bob认为一条信息是Alice发送的。（认证加密无法抵抗重放攻击）

  • 影响二： 认证加密可以抵抗选择密文攻击。

  

选择密文安全（CCA）

• 攻击者的能力：选择明文攻击（CPA）和选择密文攻击（CCA）

  • 攻击者可以获得任意选择信息的加密。
  • 攻击者可以解密他选择的任意密文。（在现实生活中攻击者欺骗解密者解密特定的密文，但不是所有的密文）

• 攻击者的目标是：破坏语义安全。

  

• 攻击者在q轮询问中，可以选择CPA询问，或者CCA询问。需要注意的是，攻击者在CCA询问中不可以询问在CPA询问中获得的密文。

• 这个攻击者十分强大，如果攻击者可以获得除了挑战密文以外的所有密文也无法区分自己处于试验0还是试验1的话。那么我们可以说密码是CCA安全的。

• 一个反例就是CPA安全的密码不是CCA安全的，以基于随机IV的CBC密码为例：

  

认证安全是CCA安全的

• 如果一个密码可以提供认证加密，那么这个密码就是CCA安全的。以下是图片证明：

  

• 所以左上和左下在概率上也是相同的，攻击者不能区分左上和左下。

• 所以认证加密保证了可以对抗解密一部分密文的攻击者，使明文具有私密性，但是还有一些局限：

  • 不能抵御重放攻击。
  • 解密者不能透露更多的信息（旁道攻击），比如时间，或者为什么返回⊥等信息。

使用MACs和加密构建认证加密

• 认证加密第一次被突出是在2000年的一篇论文中，之前的人们已经开始尝试组合CPA安全的加密和MAC在一起了。但是没有一个组合是满足认证加密的。以下是结合MAC和加密来实现CCA安全的一些例子：

  

• 对于例子3（加密且MAC），MAC签名算法是为完整性设计的，一些MAC签名算法的输出会泄露明文中的一些位，所以最后不是CPA安全的。

• 对于例子2（先加密后MAC），这种是推荐的。因为无论使用什么加密和MAC的组合，组合总能提供认证加密。

• 对于例子1（先MAC后加密），在一些病态的例子中，一些MAC和加密会有一些互动，导致没有起到认证加密的效果。

• 定理：

  • 先加密后MAC，总能达到认证加密的效果。

  • 先MAC后加密，可能可以对抗CCA。随机VI的CBC加密和随机CTR加密中线MAC后加密是能起到认证加密效果的。

    

  • 在一些情况下，使用一次安全的MAC和随机CTR加密实现先MAC后加密可以提高效率。

• 以下是一些认证加密标准：

  

• 以上的所有模式叫做：带相关数据的认证加密（AEAD）。是认证加密的拓展，意思是，只有部分是加密的，但是全部都是被认证的，这在网络协议中被广泛使用。比如说IP包，包含报文头和封装数据，其中报文头不被加密，被加密的是封装数据。 但是报文头会被认证。

• 以下是在OpenSSL中一个接口的示例：

  

MAC安全性回顾

• 为什么MAC安全性需要实现给定明文，标签对（m，t）不能产生（m，t‘）？
• 这样就会造成一个不安全的先加密后MAC模式。保证不了密文的完整性。
• 如果MAC不再安全，则先加密后MAC模式也将不再安全。

OCB算法和性能对比

• OCB是可以并行的，每个分组可以被单独加密。

  

• OCB是一个高效的算法，但OCB没被应用的主要原因是专利等限制。

  

• 以上是各个加密算法的速度和性能的比较。GCM的性能在代码大小不受限制和设备性能不受限制的情况下表现很好。OCB的性能也很好。

• 如果要使用加密，一定要使用认证加密，并且使用推荐的GCM，CCM或者EAX标准中的一个。不要自己实现认证加密。

认证加密的例子

TLS

加密

• 双方持有单项秘钥，对于用户和服务器持有两个单向秘钥。这两个秘钥还是对称加密的密钥。
• 基于状态的加密，即双方持有一个计数器，对于每一个接收到的包，计数器都会增长。目的是防止重放攻击。
• TLS是先MAC后加密的。

解密

• 如果没有通过验证，会向服务器发送一个bad_record_mac警告，并断开连接，如果需要重新发送，需要重新协商出新的秘钥。
• 如果发生了重放攻击，在tag中的计数器的值将通不过验证。
• TLS提供了认证加密，只有在解密时没有信息泄露才是。
• 解密时不应该泄露密文被拒绝的原因，不然将不是认证加密。

问题

• 当IV可以被预测的时候，加密是CPA不安全的。这种IV叫做链式IV。TLS1.1中将链式IV升级为显性IV，每一个TLS记录都有一个随机的IV值。
• 在早版本的TLS中，加密过程中的补齐出错的返回和其他错误的返回是不同的，攻击者可以观察返回的错误提示来得知密文的补齐是否有效。在1.1版本中将不再报告解密失败的原因。
• 一个经验是：如果解密失败，不要告诉为什么解密失败。（在密码学和网络协议中不一样，在网络协议中常常会告诉失败的原因，但是在密码学中很可能会造成一个攻击。）

802.11b WEP

问题

• IV是重复的，于是可以进行二次密码本攻击。
• 秘钥的关系比较紧密，这是IV和K的连接，K不变，IV在变。

攻击

• CRC是线性的，如果想要知道CRC（m xor p）则计算CRC（m）和F（p）的异或即可。
• 可以对转发端口号处进行攻击，使得80异或一个值XX等于特定的值比如25，并将该修改改变的tag通过CRC异或一个F改变成正确的tag。

针对认证加密系统的攻击

回顾

• 认证加密等于CPA安全性加上密文完整性。
• 有主动攻击者的情况下，攻击者不能以任何形式修改密文且不被检测到。
• 认证加密可以阻止强大的选择密文攻击。
• 局限：不能承受不好的实现，如果不正确的实现认证加密，那么实现对主动攻击仍将是脆弱的。
• 标准：GCM，CCM，EAX。
• 一般情况下：先加密后MAC。

针对TLS的攻击（当使用CBC加密时）

解密步骤

• CBC通过K_enc解密TLS包。
• 检查补齐，不合格就拒绝。
• 检查由MAC产生的tag，不合格就拒绝。
• 于是存在两种错误，即补齐错误和tag错误。重要的是不要告诉攻击者发生了哪种错误。

攻击

• 针对这样的攻击叫做Padding oracle（补齐神谕）
• 攻击者可以通过向服务器发送不同的TLS包来检查补齐的后缀是什么，这将帮助攻击者获取一些信息。
• 在改进后的SSL中，虽然返回的错误类型是相同的，但是返回所需要的时间是不同的。这导致了还是存在补齐神谕告诉出错的原因。

• 在上述图片的攻击中，通过猜测每一个明文分组的末尾的值，从而想办法构造出合法的TLS包，若通过了服务器中补齐的检测。则可以得知任意处的明文的值。
• 因为0x01代表一个已此分组作为结尾的正确的补齐。
• 通过将猜测分组的上一个分组的末尾的值异或上猜测的g和0x01来凭借CBC解密的特性通过补全测试。
• 在得到字节的值之后，可以使用相同的方法来得到倒数第二个字节的值。使用(02,02)来对上一个分组的倒数两个字节进行异或，并异或猜测的值。直到通过补齐测试。
• 因为CBC中一个分组是16个字节，则通过256*16次测试就可以得到这个分组的全部值了。
• TLS针对这个攻击的防御措施是，如果收到错误MAC警告之后就断开连接并重新协商秘钥。

IMAP

• IMAP的底层是TLS实现的。
• 客户端会每5分钟登录一次服务器来检查是否有新的邮件，等于攻击者每5分钟就获得一个同样信息的加密。那么攻击者每5分钟就可以猜一次包含密码的分组。
• 防御攻击的方法是让检测补全和检测MAC所花的时间相同，从而避免计时攻击。

启示

• 如果先加密后MAC，则不会出现针对这样的攻击。因为如果MAC是错误的，分组将直接丢弃，而不会进入到检测补齐的环节。
• MAC之后CBC提供认证加密当且仅当不提供其他信息的时候可以。因为补齐神谕的存在破坏了认证加密的性质。

提问

• 如果使用MAC之后CTR加密的形式，补齐神谕的攻击是否有效？
• 答案是无效，因为CTR不进行补齐。
• TLS也支持CTR加密，CTR加密将不会受补齐神谕攻击的影响。

SSH二元数据包协议

介绍

• SSH是一个标准的安全远程shell应用。
• SSH使用加密并且MAC，（此处的MAC是明文的MAC而不是密文的MAC）

攻击

• SSH协议中，会首先将发送的密文的第一个block解密，这个意味着整个密文c的长度。
• 则攻击者只需将想要解密的block发送给服务器，然后数接下来向服务器发送了多少个block即可得出想要解密的block的值。

启示

• 错误一：解密不是原子操作。解密算法不取整个数据包作为输入。服务器部分的解密了密文。
• 错误二：在正确认证之前就使用了长度域。

提问

• Q：如何进行最小的修改使得SSH可以满足安全性？
• A：以明文的形式发送长度域，和TLS一样。这样就避免了攻击者的选择密文攻击。
• A：或者对长度域进行单独计算MAC，这样长度域被解密时需要先进行认证。

07-零碎

如何通过一个key推出所有key

背景

源秘钥的来源

• 硬件随机数生成器
• 秘钥交换协议

需要很多key来保证安全交流

• mac的key，IV等。

目标

• 生成许多key通过一个源key。
• 使用KDF函数（密钥推导函数）来生成。

均匀分布的SK

• 其中sk是源密钥，ctx是上下文信息，L是长度。

• 此处需要保证sk是在密钥空间K中均匀的一个密钥。

• CTX是一个和应用相关的string。不同的应用会有不同的CTX

不均匀分布的SK

• 密钥交换协议中生成的高熵的key并不是在K中均匀的。
• 硬件随机数生成器生成的key也可能不均匀。

先提取后拓展KDF

提取均匀随机的key

• 提取出伪随机中的k，并加上盐来使得随机不可以被区分，这个盐是公开的。
• 使得得到的结果是均匀分布的K空间。

拓展出均匀随机的key（HKDF为例）

• 使用HMAC，以高熵的SK为信息，加上盐加密得到提取的密钥k。
• 然后使用HMAC算法作为PRF扩展k。

基于密码的KDF（PBKDF）

• 从key中推导出密码：
  • 不要使用HKDF：对于字典攻击来说是脆弱的。
• PBKDF的定义：使用盐和慢hash函数

• 慢hash的意思是这个hash操作会执行很多次。
• 慢hash的作用是抵御字典攻击，对于字典攻击者来说每试一个字典中的key都需要执行c次哈希。

确定性加密系统

• 在这个系统中，数据库是完全不知情的。所发送和处理的信息都是密文形式。

问题

• 这样的系统不是选择明文安全的，即不是CPA安全的。
• 如果攻击者看到了相同的密文两次，就可以知道被加密的明文也是相同的。换句话，通过看密文，攻击者可以学习到对应明文的信息。
• 在现实中，特别是如果明文空间M很小的情况下。

回顾

• 确定性的加密是不可能赢得CPA安全的。可以回顾之前的攻击。
• 即攻击者能学习比他应该知道的更多的信息。

解决

• 永远不要使用单个密钥来加密同样的明文信息。换句话说，信息秘钥对总是不同的（k，m）。
• 选择信息随机地从巨大的消息空间中，例如key
• 消息结构确保了唯一性，例如用户id。

确定性加密的CPA安全

• 通过这个定义的CPA安全游戏，即要求发送的消息每次不能相同来确保了确定性CPA安全。

使用带固定IV的CBC加密

• 第一组可以很容易得被区分出来。
• 所以使用带固定IV的确定性CPA是不安全的。

确定性加密是需要的

• 加密数据库索引记录就需要。
• 确定性加密是不可能选择明文攻击安全的。
• 于是定义了确定性选择明文安全的定义。

机制一：合成IV

• 通过明文来推导出随机性。然后使用这个随机性来加密信息。
• 同时CTR的SIV是DAE（确定性认证加密）的。

• 其中的IV用于密文的解密，并且解密后得到的明文会重新通过F来得到IV，进行验证。这样就保证了密文安全性。保证不会产生合法的其他密文可以通过IV的测试。
• 这个SIV-CTR模式适合明文比较长的场景，（因为是流密码加密）。对于更短的明文可以使用机制二。

机制二：直接使用PRP

• 当明文小于16字节直接使用AES就可以保证确定CPA安全（因为对于16字节来说，AES是PRP的）。但是没有保证完整性。
• 对于大于16字节长度的加密算法EME也可以实现确定CPA安全。通过小的PRP来构造大的PRP。

• 但是十分的麻烦，一倍慢与SIV算法。
• 对于PRP的认证加密，在尾部附着若干个0即可。在解密完成之后检查尾部是否有规定个数的0即可。

• 这个认证加密起作用的前提是PRP和足够多的0。因为加密和解密使用的是真随机，所以解密后尾部有规定个0的密文被伪造的概率是可忽略不计的。

微调加密

硬盘加密问题

• 硬盘加密是另一个确定性加密问题。
• 要实现加密不扩展的情况，即密文空间和明文空间一样大。那么密文的大小将和明文一样大。同时只能选择使用确定性加密，因为密文和明文一样大，没有多余的空间来存储随机性。所以最严格的也就是确定性CPA安全。
• 满足这样的加密方案只能是PRP，就是上文中机制二。

• 避免确定性CPA的问题，如果扇区1和3使用相同的k，则会出现CPA问题，若1和3中都为0，则攻击者可以知道1和3都为空。
• 以上问题可以通过1和3使用不同的密钥来解决。但是还有一个问题是，如果1经过修改之后又撤销，原状态和撤销状态会相同，同样会给攻击者泄露相关信息。
• 方案就是通过主k来生成每一个扇区的k，通过一个PRF来对第t个扇区的密钥做生成操作。

• 定义一个微调函数，对于每一个微调T，可以生成一个PRP，使得X在PRP上可逆。

• 定义这个博弈，与普通的PRP不同的是，普通PRP博弈是与一个置换进行交互。但是这个是和T个置换进行操作。
• 如果T个置换和T和随机函数不可区分，则微调函数是安全的。

• 图中显示的是块级的PRP而不是扇区级的PRP。
• XTS提供了扇区级的确定性CPA安全。
• 这些都是窄分组方案，为16字节的分组提供了微调分组密码。EME比XTS慢两倍，因为灭有缓存N。

保格式加密

• 常用来加密银行卡号。
• 16位信用卡号的前6位叫做BIN，确定了开卡银行的信息。后9位为卡号。最后一个为校验和。
• 即端到端加密，从加密端到解密端，信息的格式不发生变化。中间传输过程中密文也是16位的数字。

• 我们的做法是将卡号映射到一个大小为s的集合上，并通过一个PRP加密，之后将加密结果映射回卡号集合中。
• 最好的方法其实就是截断，之后补齐放入AES中，并将结果截断。另一个方法是：

• 首先，将n位明文空间映射到t位空间中。

• 第二步，一直使用E直到x的结果落到给定区间中，即得到y。这一操作可逆。
• 并且这一操作的平均开销为2次。
• 这里可以取得的安全性是确定性CPA安全。

08-密钥交换

密钥管理

• 如果有n个人想要互相通信，在基础情况下，每个人需要存储n个秘钥。

可信第三方（TTP）

• 那么如果A和B想要交流的话，怎么产生一个密钥KAB呢？

• 上图是通过可信第三方进行秘钥交换的过程。这个过程对于窃听是安全的。
• 这个TTP如果被攻陷，则所有的密钥将都不安全。
• 这个是一个玩具协议。
• 这个协议对于重放攻击是无效的。即对主动攻击是不安全的。如果攻击者重放A和B的会话中的一部分。A或B无法确定是否由本人发出。

Merkle Puzzles

• 通过对称密码学可以得到不借助可信第三方的密钥交换协议，不过得到的协议十分的低效。

• 通过上述的过程，A和B获得了一个共享的秘密Kj。至此密钥交换完成。
• 这样攻击者获得密钥Kj的难度要很大。攻击者需要完成破解所有的n个加密信息的工作才可以拿到密钥kj。
• 复杂度分析：A需要花O（n）的时间产生谜题，B需要花O（n）的时间解决谜题。攻击者需要花O（n^2）的时间进行攻击。
• 这样对于2^128这个规模的安全计算量来说，A和B可能需要规定n的大小为2^64。这个大小将可能是不是所有人都可以接受的。
• 已经有论文证明了平方鸿沟是我们可以达到的最好结果了。

公钥密码学

Diffe-Hellman协议

• 我们在寻找一个指数鸿沟，在参与者和攻击者之间。

协议内容

• 看起来很简单的一个协议，交换参数p和g，并且A和B之间交换两个参数A和B，就可以得到一个公共秘密g^ab。
• 这个协议是一个基于代数的协议，开启了密码学的新纪元。

安全性

• 破解DH函数所需要的时间复杂度是exp（O(n^(1/3))），不是严格的指数级的时间复杂度。

• 所以对于需要交换很长密钥的场景下，DH函数选用的模就很大（因为立方根的作用）。
• 如果将DH协议从质数模的设定转化成椭圆曲线的设定时，计算会更加的困难。这样需要选用的指数的位数就不用很大。

中间人攻击

• 如果存在一个中间人可以截获A和B的所有消息的话，并向A和B发送伪装的消息，那么中间人将会控制整个消息交换的流程。

DH协议的非互动性

• 对于公开的参数，只要两者通过计算，就可在没有两者交互的情况下得到一个共享密钥。
• 对于n=2的情况下，就是DH密钥交换协议。对于n大于2的情况下，就是多方如何生成一个共享密钥的问题。

公钥加密

• 公钥加密由三个算法构成，分别是G（），E（）和D（）。
• G用来生成公私钥，E通过公钥加密，D通过私钥解密。

获得共享密钥

• 这个过程有严格的先后顺序，必须由Alice发起，不能由Bob直接发送。和DH协议中的无交互性不同。

安全性

• 对于随机M和x来说在分布上无法区分，则可以说明是安全的。

中间人攻击

• 这个和DH协议类似，会有中间人模仿A，从而获得交换的密钥x。

09-公钥密码学中的数学

GCD和EXGCD

• gcd是两个数的最大公约数。
• 存在a和b使得ax+by=gcd(x,y)。
• 如果gcd等于1，则两数互素。
• EXGCD的时间复杂度为O(logn)^2。

模下的逆

• x在N为模下的逆y使得xy=1(modN)。
• 什么情况下逆存在？
  • X与N互质，即gcd(x,N) = 1的情况下存在。
  • 证明：如果gcd(x,N) = 1，则存在ax + bN = 1，对等式两边对N取模，则存在ax = 1 (mod N)，则x的逆就是a。
  • 例子，如果gcd(x,N) = 2，则说明x和N都是偶数（因为2是x的因子），则不存在ax = 1(mod N)，因为ax是偶数。即ax + bN != 1。移项之后可得ax != bN + 1。
• 定义Z_n*为在Z_n中，所有gcd(x,N) = 1的x组成的。
• 对于给定的x和N，可以通过EXGCD来快速找到x的逆。

线性同余方程

• 通过解得a的逆，就可以解出x的值。

费马小定理

• 对于质数p来说，存在x^(p-1) = 1 (mod P)。
• 所以可推出x * x^(p-2) = 1 (mod P)，从而得出x的逆为 x^(p-2)。这是一个计算质数模的逆的好方法。
• 这个方法的时间复杂度比EXGCD的复杂度要高，为O(logn)^3。
• 通过费马小定理可以用来寻找一个大素数，在一个很大的范围里寻找素数，并尝试计算x^(p-1) = 1 (mod P)是否成立。若成立则p很有可能是一个真素数，因为费马小定理是素数的必要不充分条件，并不是充要条件。但是这个数是假素数的概率很小。
  • 通过几百次迭代，就十分可能找到这个素数了。（17世纪的数学，费马）

Z_p*的结构

• Z_p*是一个循环群。
• 对于一个p来说存在一个生成元g，使得从0到p-2为g的次方可以得到Z_p*的所有元素。并且指数从p+1之后值会循环。（18世纪的数学，欧拉）

阶

• Z_p*中，对于一个给定的g，g的所有幂组成的集合叫做g的生成群<g>。
  • 定义：g在Z_p中的生成群的元素的个数叫做g在Z_p\里的阶。
  • 也可以认为最小使得g^a=1的整数a就是生成群的阶。
• 拉格朗日定理：对于Z_p*中的g模p的阶来说，这个阶始终整除p-1，即阶始终是p-1的因子。（19世纪的数学，拉格朗日|更高级的密码学使用到了20世纪的数学。）

欧拉定理

• 定义：φ(N)=|Z_N*|。即为Z_N*中元素的个数。
  • φ(p)=p-1。
  • 对于N=pq，pq为素数，φ(N)=N-p-q-1=(p-1)(q-1)。
• 欧拉定理：任意x在Z_N*中，x^φ(N)=1。
  • 这是费马小定理的推广，费马小定理是N为素数的特殊情况。
  • 重要的是欧拉定理适用于合数。
  • 欧拉定理是RSA密码系统的基础。

模二次方程

• 对于x在Z_p中，x^e=c在Z_p中，叫做X是C的e次方根。
  • e次方根不总是存在的。
• 给定gcd(e, p-1) = 1。即e和p-1互质。那么在Z_p*中的所有c，c的e次方根存在Z_p中，并且容易找到。
  • 证明：d是e在Z_p-1的逆，那么c的e次方根等于c的d次方。

• 一个困难的情况是e和p-1不互质。比如说一个奇素数p和2，则gcd(2,p-1)!=1。
• 定义如果x在Z_p中，有平方根，则叫x是在Z_p中的平方剩余。否则叫做平方非剩余。
  • 对于一个奇素数来说，Z_p中平方剩余的个数为(p-1)/2+1个（包括0）。因为有一半的元素没有原像，每两个映射到一个像上。
• 如何判断一个数是否是二次剩余呢？
  • 欧拉定理：在Z_p中x是二次剩余当且仅当 x^(p-1)/2 = 1 (mod p)。
  • 定义x^(p-1)/2叫做勒让德符号。
  • 但是欧拉定理是判定性的定理，而不是构造性的定理。
• 对于一些特定的p可以有公式计算出c的平方根

• 其中p = 3(mod 4) 指的是p同余3模4，我们还没有很好的方法来计算c的平方根。

• 可通过上图来求解Z_p上的二次方程。其中式子中的平方根可由之前的平方根算法求得。
• 计算合数模的二次方根和分解合数一样困难。如果合数可以质因数分解之后，每个质因数的e次方根都较为容易计算。

大整数模

• 加法时间复杂度O(n)
• 乘法时间复杂度最好情况为O(nlogn)，更一般的算法是O(n^2)
• 带余数除法时间复杂度O(n^2)
• 大整数幂，重复平方法计算，将幂次进行二进制拆分。之后进行若干次乘法运算。时间复杂度为O(n^2*logn)，小于O(n^3)。

模运算难题

• 在模运算中，存在许多更加困难的问题。但是也有很多简单的问题。比如说，使用EXGCD算法求x的逆元。使用多项式复杂度的算法来求方程的根等。

离散对数问题

• Dlog 表示离散对数，即规定一个以质数p为模的循环群Z，g为生成元，阶数为q。计算某数以p为模，以g为底的对数。
• 一个需要注意的是，在这个群上定义的需要进行隐藏的信息x，是有范围的，范围就是这个选定群的阶数q-2以内。
• 我们没有很好的方法来计算一个数的指数，是一个困难的问题。
  • 一个经典的例子是Z_p*群，这个循环群是DH提出的。
  • 还有一个例子是离散的椭圆曲线群，这个群上计算离散对数也是困难的。
  • 同时在椭圆曲线上进行计算离散对数要更加的困难。比Z_p*群上的离散对数更加的困难，困难的多。
  • 那么在椭圆曲线上可以选择更小的参数，因为椭圆曲线加密的效率更高。

• 可以看到椭圆曲线计算离散对数的时间复杂度是比整数群上的离散对数要大得多，所以只需要很小的参数就可以保证安全。

• 一个简单的应用就是计算哈希，这样计算出来的哈希可以归结到离散对数困难问题。即找不到这样的一个碰撞，或者说，找到这样的碰撞是困难的。（但是这个方法有点慢，所以不咋使用）

合数模问题

• 一个是计算两个n位的质数相乘的积为合数的质因子分解。
• 一个是计算两个n位的质数相乘的积为合数的群下高次函数的解，这是RSA加密算法困难性的来源。

10-公钥密码学

安全的公钥密码学的定义

• 密钥对指公钥和私钥，两个的总和叫做一个密钥对。

公钥系统的定义

• 公钥系统的两个很重要的应用会话建立和非互动应用：
  • 会话建立：指A和B通过使用公钥系统来交换一个接下来的会话中的非对称密钥。监听者除了听到了公钥和会话密钥x加密后的密文外没有得到其他任何信息。
  • 非互动应用：在B不和A互动的情况下，通过CA获取A的真实公钥，并通过这个公钥来对A发送信息，比如说email。
• 公钥密码学由三个函数构成G,E,D。G是密钥生成算法，可以生成公钥和私钥，通常有一个输入叫做安全参数，来指定密钥生成算法将要生成的密钥的大小。E和D分别是加密和解密算法，分别使用公钥和私钥，分别将明文和密文加密或解密。
• 一致性原则指的是加密或解密之后明文不变。

抗窃听的安全性

• 和对称密码的防窃听安全类似（左边的的是挑战者，右边的是攻击者）。只要攻击者辨认加密的c的优势可以忽略不计，那么就是防窃听安全的。
• 抗窃听安全分为密钥使用一次和密钥使用多次（CPA）两种。如果在CPA安全下，相同明文多次加密不能是相同的结果才能保证挑战者赢得游戏。
• 结论：在公钥加密中，不需要关注更复杂的防窃听安全，因为公钥是公开的，攻击者可以自己去使用公钥加密许多的明文。

选择密文安全

• 公钥的选择密文安全（IND-CCA）。
• 需要注意并且PPT中没有标清楚的是，挑战过程中选择的m0和m1不能是CCA过程1中得到的明文。

• 攻击者拥有改变密文，并且使得改变的密文通过预言机解密的能力。这样就可以解密原密文中隐藏的部分的信息了。
• 所以对于CCA安全，挑战者需要判断密文是否被改变，若被改变，则输出错误即可抵御这种攻击。

陷门置换

陷门函数

• 这个陷门函数需要是单向陷门才行（必须需要sk才可以计算出函数的逆）。
• 安全陷门的定义就是攻击者在没有sk的情况下计算出x逆的优势忽略不计。

• 一套公钥加密系统。这个陷门系统是使用对称加密的。

• 在这种情况下的系统是选择密文安全的。这种加密系统方案被记录在ISO标准中。

• 错误使用陷门函数的例子，直接对明文进行加密，这样的加密甚至不是CPA安全的，因为加密没有随机性。

RSA陷门函数

回顾：合数模

• 对于N=pq构造的群，其中随机选取一个元素大概率是可逆的。
• 注意欧拉定理只在对和N可逆的元素中有效。

过程描述

• 同样的RSA公钥加密可以适用于之前的ISO公钥加密方案。
• 值得注意的是RSA加密也不要直接加密明文，和之前的一样。

• 安全的RSA公钥加密方案。

攻击

• 通过拆分k，就可以实现一个中间相遇攻击。所以说直接对k加密是不安全的，应该过一个哈希才对。

PKCS1

• PKCS1是一种公钥密码学标准，指定了RSA的标准。
• 02是加密模式，其中v1.5版本的PKCS1遭到了攻击。因为在v1.5版本中，

• 攻击者通过判断开头是否是02，对预言机进行了攻击。预言机神谕对PKCS1进行了解析。从而可以反推出任何想要解密的密文。

• 对于这种情况，经历n次左右即1000到2000次就可以得到加密c的明文内容了。进行左移操作。

RSA-OAEP

• 这个优化使得传输的密文的长度变短了。不用带上后面的一段随机数。是一段更好的填充方法。
• 同时有一个叫做SAEP的改进，也是针对RSA的填充问题的。

RSA是单向函数吗？

• 换言之，如果不知道RSA的陷门，求RSA的逆真的这么困难吗？

• RSA问题的根本问题是整数N的分解问题，上面一张在讨论的是整数N分解问题和立方根问题之间的关系，即能否以立方根的时间复杂度计算大整数分解问题。

P与NP（Wikipedia）

• 决定性问题：
  一个决定性问题(decision problem)是指其输出，只有“是”或“否”的问题。例如，搜索问题为询问 x 是否出现在一个集合 A 中?若有则输出“是”，否则输出“否”。
• P问题：
  当一个决定性问题存在一个能在多项式时间内找出解的算法时，则称此问题落在P 的集合中。
• NP问题：
  当一个决定性问题的解能在多项式时间内被验证时，则称此问题落在NP 的集合中。

所以P与NP的区别是是多项式时间验证还是多项式时间求解。大整数分解是多项式时间验证，所以是NP问题。

私钥位数

• 若私钥对于N来说小于图中的范围，则RSA系统会被认为是不安全的。

• 上图是对这个攻击的证明，通过枚举k/d并通过上述的约束，就可以找到d。

RSA应用

• RSA的加密要比解密快的多，一般会快10到30倍，但是ElGamal算法就没有这个性质，ElGamal的加密和解密基本一样快。

• RSA的模大小和AES密钥长度之间的关系。
• 还有很多攻击，比如说，RSA加解密的一点计算错误就会完全的泄露私钥，所以现在的加密都会对解密出的明文进行重新加密计算，看能否回到密文状态。
• 启示：不要自己实现密码学套件，应该始终使用标准密码学库，来防止中间出现的错误。

• 在一个侧道攻击中，一个问题是如果服务器的防火墙刚启动时就生成的p可能是熵不够的，导致大量服务器共同选择的N可能会存在共同的因子p。这样就不安全了。

11-DH公钥加密

非交互密钥交换

• 除了在SSL中交换会话密钥以外，常常还存在非交互情境下的密钥交换。比如说邮件加密或者文件加密系统中。

• 或者使用第三方的契约服务，即他人的修改是通过第三方契约服务进行的。

ElGamal加密系统

• 基于DH协议的加密系统是另一组公钥系统。这些公钥系统又叫做ElGamal公钥加密系统。
• 我们选择加密系统的目标是：选择密文安全（CCA）

回顾DH密钥交换

• DH密钥交换是定义在一个循环群上的。确定生成元g和阶数n。
• 椭圆曲线群也是一个循环群。

ElGamal公钥加密

• ElGamal加密是随机加密算法，Bob每次发送密文都更换一个随机的b。

• 以上就是ElGamal的全流程。

• ElGamal的效率加解密的速度是不一致的，一般情况下，若接收方会经常发生变化，即g和h会经常发生变化，那么加密往往要比解密慢一倍。
• 但是一个好的方法就是如果确定的接受方，可以预先的计算出g和h幂次表，这样在加密的时候可以加速这个过程，直接从表中查询即可。可以有3倍以上的加速作用。
• 并且如果加解密速度成为瓶颈的话可以考虑RSA加密，RSA加密速度要比ElGamal快。

ElGamal公钥加密的安全性证明

CPA安全

• 一个分析DH的假设叫做CDH假设，这个假设没有HDH假设更强。

• HDH假设是将u和v哈希之后产生的K和R对比，如果两者在概率上是无法区分的，那么可以证明是安全的。
• CDH如果是在G上容易的，那么也可以推出HDH是容易的。所以HDH比CDH更困难一些。所以HDH是一个更强的假设。
• 可以这样理解，即使CDH是困难的，但是选择的不好的H使得左边的开头都是0，右边开头是0和1的概率一半一半，那么也会导致攻击者有1/2的优势赢得这个游戏，所以说HDH是更加困难的。
• 基于这个假设，就可以证明在HDH假设下的ElGamal是CPA安全的。

CCA安全

• 为了解决这个问题，提出了IDH假设，即可交互的DH假设。
• 这个假设允许攻击者不断地提问挑战者。

• 于是我们知道的这些条件，ro指的是随机神谕，即哈希是完全随机的。

• 问题是，我们能否基于CDH证明CCA安全，能否证明CCA不依赖随机神谕而是具体的哈希函数（SHA等）。

• 对于第一个问题，有一种办法是证明CDH和IDH在一个循环群上是等价的，（在双线性群上是等价的）。还有一个方法，就是将ElGamal系统进行等价，得到一个孪生ElGamal系统就可以得到证明。

• 我们修改一下ElGamal协议，将sk变为两个，此时k的计算需要哈希三个值。
• 这样得到的协议可以通过CDH来证明是CCA安全的。

• 可以使用没有随机神谕的哈希函数来证明CCA安全吗？

单向函数

基于陷门函数代表的密码（RSA）和基于DH协议的密码遵循一个更一般的原理：单向函数。

• 单向函数并不是不可逆函数，单向函数是反向计算困难的函数，即反向问题是NP问题的函数。（一些单向函数的反向问题存在快速的解，即陷门函数）。
• 而不可逆函数指的是类似cosx之类的无法找到函数值的原像或原像有很多个的函数。
• 所以单向函数可能是可逆的，但是不可逆函数可能并不是单向函数。
• 为什么cosx不能当做单向函数？
  • 单向函数的反向函数是计算困难的NP问题，例如f(x) = 0，很容易就可以计算出一个原像x满足f(x) = 0。

• 但是单向函数不能形式化定义，因为这实际上是要证明单向函数是否存在。这个问题的实质是：证明单向函数的存在即证明了P不等于NP，即求单向函数的反过程没有多项式的解算法。
• NP问题提供了一个数学上的天然鸿沟，使得验证可以多项式，但是求解不能多项式。

• 随机数函数就是一个单向函数。以上是证明，主要来源于PRG的证明，即不存在一个函数A来找到随机数种子。
• 但是这个函数没有什么特别的性质，比较难用于密钥交换，其中一个密钥交换的例子是Merkle谜题。

• 这个是DLOG单向函数的例子，在这个例子中，f有一个性质，这个性质就可以被用于公钥加密中。
• 这个性质又被叫做同态性质。

• 第三个例子就是RSA单向函数，这个单向函数的性质是存在陷门函数（即欧拉定理，可以找到一个逆来求出c的离散对数的底数）。
• 这个性质被叫做陷门性质。

总结

课程总结

• 课程通过PRG入手讲解安全的随机数生成。
• 之后拓展到安全的随机函数和随机过程从而得到流密码和分组密码。（机密性）
• 之后进入到如何保护信息的完整性。
• 在后面通过陷门函数和DH交换引出了公钥加密和密钥交换，同时也提及了密码学的认证。

可以关注斯坦福Dan Boneh老师的主页。课程质量看起来很高，有很多密码学高级课程。

个人总结

• 本课程侧重讲解可证明安全，通过设计game来讲解为什么安全。
• 数学部分讲的可以，例子很直观。
• 体系需要自己梳理，常常会跳着讲。
• 体系没建立的时候常常不知道为什么这么组织课程和知识，还是需要多总结多思考。（或者说提前看下总结和脉络图再学）