「Cryptography-Boneh」：Introduction
本系列是学习Dan Boneh教授的Online Cryptography Course。
这是Dan教授的第一讲：对密码学的一些Introduction。
What is cryptography?
Crypto core：安全通信
Secret key establishment (密钥的建立)：
Alice 和 Bob 会得到一个shared secret key，而且Alice 知道她是在和Bob通信，Bob也知道他是在和Alice通信。而attacker不能从通信中获取key。
Secure communication （安全通信）：
在通信中，Alice、Bob用key将信息加密，保证了通信的confidentiality（机密性）；同时attacker也无法篡改通信的信息，保证了通信的integrity（完整性）。
Crypto can do much more
密码学除了能保证安全通信，密码学还能做很多其他的事。
Digital signature & Anonymous
Digital signatures（数字签名）：
现实中，人们对不同的文档进行签名，虽然是不同的文档，但是签名的字是相同的。
如果这应用在网络的文档签名中，这会很危险的。攻击者只需要将签名进行复制、粘贴，就可以将你的签名签在你并不想签的文档中。
数字签名的主要思想：数字签名其实是代签内容的函数值，所以如果攻击者只是复制数字签名（原签名的函数值），那么攻击者得到的数字签名也是无效的（函数值不同）。
Anonymous communication（匿名通信）：
匿名通信的实现，有Mix network （wiki详细介绍）协议，这是一种路由协议，通过使用混合的代理服务器链来实现难以追踪的通信。
通过这些代理的不断加密解密可以实现：
Bob不知道与之通信的是Alice。
代理也不知道是Alice和Bob在通信。
双向通信：虽然Bob不知与之通信的是Alice，但也能respond。
Anonymous digital cash（匿名数字现金）：
现实中，我们可以去超市花掉一元钱，而超市不知道我是谁。
在网络中，如果Alice想去网上商店花掉数字现金一元钱，网上商店可以不知道是谁花掉的这一元钱吗？
这就是匿名数字现金需要解决的问题：
- 可以在匿名的情况下花掉数字现金吗？
如果可以，当Alice将这一元钱复制多次（数字现金都是数据串），得到了三元钱，再去把它花掉，由于匿名的原因，没人知道是谁花掉的这三元钱，商店找不到责任人。
这是匿名数字现金需要解决的第二个问题：
如何防止 double spending情况的发生？
可以用这样的机制去实现匿名数字现金：当Alice花费这一块 once时，系统保证Alice的匿名性；但当Alice花费这一块 more than once ,系统立即揭露Alice的全部信息。
Protocols
在介绍什么是Protocols之前，先介绍两种应用场景。
Elections
有5个人要进行投票选举0和1号候选人，但是需要保证：每个人除了知道自己的投票结果，互相不知道其他人的投票情况。在这种情况下怎么知道最后的winner是谁吗？
如上图，可以引入一个第三方——election center，第三方验证每一个人只能投一次，最后统计票数决策出最后的winner。
Private auctions
介绍一种拍卖机制，Vickery auction：对一个拍卖品，每个投标者在不知道其他人投标价格的情况下进行投标，最后的acution winner： highest bidder & pays 2nd highers bid。即是标价最高者得标，但他只需要付第二高的标价。
所以public知道的信息只有：中标者和第二高投标者的标价。
需要实现这种机制，也可以引入一个第三方——auction center。
但是引入第三方真的安全吗？安全第三方也不安全。
再看上面那个Election的例子，如果把上面四个人的投票情况作为输入，第三方的任务其实是输出一个函数 $f(x_1,x_2,x_3,x_4)$ 而不公开其他信息。
因为安全第三方也许并不安全，所以如果去掉第三方，上面四个人遵从某种协议，相互通信，最后能否得出这个 $f(x_1,x_2,x_3,x_4)$ 这个结果函数，而不透露其投票信息？
答案是 “Yes”。
有一个惊人的定理：任何能通过第三方做到的事，也能不通过第三方做到。
Thm: anythong that can done with trusted auth. can also be done without.
怎么做到？答案是 Secure multi-party computation（安全多方计算）。
在MPC专栏 有相关介绍。
Crypto magic
Privately outsourcing computation (安全外包计算)
Alice想要在Google服务器查询信息，为了不让别人知道她查询的是什么，她把search query进行加密。
Google服务器接收到加密的查询请求，虽然Google不知道她实际想查询什么信息，但是服务器能根据E[query]返回E[results]。
最后Alice将收到的E[results]解密，得到真正的results。
这就是安全外包计算的简单过程：Encryption、Search、Decryption。
Zero knowledge（proof of knowledge) (零知识证明)：
Alice 知道p、q(两个1000位的质数)相乘等于N。
Bob只知道N的值，不知道具体的p、q值。
Alice 给 Bob说她能够分解数N，但她不用告诉Bob N的具体因子是什么，只需要证明我能分解N，证明这是我的知识。
最后Bob知道Alice能够分解N，但他不知道怎么分解（不知道N的因子到底是什么）。
A rigorous science
在密码学的研究中，通常是这样的步骤：
Precisely specify threat model.
准确描述其威胁模型或为达到的目的。比如签名的目的：unforgeable（不可伪造）。
Propose a construction.
Prove that breaking construction under threat mode will solve an underlying hard problem.
证明攻击者攻击这个系统必须解决一个很难的问题（大整数分解问题之类的NP问题）。
这样也就证明了这个系统是安全的。
History
Substitution cipher（替换）
what is it
替换密码很好理解，如上图的这种替换表（key）。
比较historic的替换密码——Caesar Cipher（凯撒密码），凯撒密码是一种替换规则：向后移三位，因此也可以说凯撒密码没有key。
the size of key space
用$\mathcal{K}$ （花体的K）来表示密钥空间。
英语字母的替换密码，易得密钥空间的大小是 $|\mathcal{K}|=26!\approx2^{88}$ （即26个字母的全排列）。
这是一个就现在而言也就比较perfect的密钥空间。
但替换密码也很容易被破解。
how to break it
问：英语文本中最commom的字母是什么？
答：“E”
在英语文本（大量）中，每个字母出现的频率并不是均匀分布，我们可以利用一些最common的字母和字母组合来破解替换密码。
Use frequency of English letters.
Dan教授统计了标准文献中字母频率： “e”: 12.7% , “t”: 9.1% , “a” : 8.1%.
统计密文中（大量）出现频率最高、次高、第三高的字母，他们的明文也就是e、t、a。
Use frequency of pairs of letters (diagrams).（二合字母）
频率出现较高的二合字母：”he”, “an”, “in” , “th”
也能将h, n,i等破解出。
trigrams（继续使用三合字母）
……直至全部破解
因此substitution cipher是CT only attack！（唯密文攻击：仅凭密文就可以还原出原文）
Vigener cipher
Encryption
加密过程如上图所示：
- 密钥是 “CRYPTO”, 长度为6，将密钥重复书写直至覆盖整个明文长度。
- 将密钥的字母和对应的明文相加模26，得到密文。
Decryption
解密只需要将密文减去密钥字母，再模26即可。
How to break it
破解方法和替换密码类似，思想也是使用字母频率来破解。
这里分两种情况讨论：
第一种：已知密钥长度
破解过程：
将密文按照密钥长度分组，按照图中的话，6个一组。
统计每组的的第一个位置的字母出现频率。
- 假设密文中第一个位置最common的是”H”
- 密钥的第一个字母是：”H”-“E”=”C”
统计剩下位置的字母频率，直至完全破解密钥。
第二种：未知密钥长度
未知密钥长度，只需要依次假设密钥长度是1、2、3…，再按照第一种情况破解，直至破解情况合理。
Rotor Machines
Rotor: 轴轮。
所以这种密码的加密核心是：输入明文字母，轴轮旋转一定角度，映射为另一字母。
single rotor
早期的是单轴轮，rotor machine的密钥其实是图右中间那个圆圆的可以旋转的柱子。
图左是变动的密钥映射表。
变动过程：
- 第一次输入A，密文是K。
- 轴轮旋转一个字母位：看图中E，从最下到最上（一个圈，只相隔一位）。
- 所以第二次再输入A，密文是E。
- ……
Most famous ：the Enigma
Enigma machine是二战时期纳粹德国使用的加密机器，因此完全破解了Enigma是盟军提前胜利的关键。
左图中可以看出Enigma机器中是有4个轴轮，每个轴轮都有自己的旋转字母位大小，因此密钥空间大小是 $|\mathcal{K}|=26^4\approx2^{18}$ (在plugboard中，实际是 $2^{36}$)。
密钥空间很小，放在现在很容易被暴力破解。
plugboard 允许操作员重新配置可变接线，实现两个字母的交换。plugboard比额外的rotor提供了更多的加密强度。
对于Enigma machine的更多的具体介绍可以戳Enigma machine 的wiki链接。
Data Encryption Standard
DES：#keys = $2^{56}$ ,block siez = 64bits，一次可以加密8个字母。
Today：AES（2001）、Salsa20（2008）……
这里只是简单介绍。
Discrete Probability
- Background on discrete probability: [html]
Randomized algorithms
随机算法有两种，一种是Deterministic algorithm（也就是伪随机），另一种是Randomized algorithm。
Deterministic algorithm
$ y\longleftarrow A(m)$ ，这是一个确定的函数，输入映射到唯一输出。
Randomized algorithm
$y\longleftarrow A(m ; r) \quad \text { where } r \stackrel{R}{\longleftarrow}{0,1}^{n}$
output： $y \stackrel{R}{\longleftarrow} A(m)$ ，y is a random variable.
$ r \stackrel{R}\longleftarrow {0,1}^n $ :意思是r是n位01序列中的任意一个取值。R，random。变量r服从在 ${0,1}^n$ 取值的均匀分布。
由于随机变量r，对于给定m，$A(m;r)$ 是 ${0,1}^n$ 中的一个子集。
所以，对m的加密结果y，也是一个的随机变量，而且，y在 $A(m,r)$ 也是服从均匀分布。
因此，由于r的影响，对于给定m，加密结果不会映射到同一个值。（如上图所示）
XOR
XOR有两种理解：（ $x \oplus y $ ）
- 一种是：x,y的bit位相比较，相同则为0，相异为1.
- 另一种是：x,y的bit位相加 mod2.
异或在密码学中被频繁使用，主要是因为异或有一个重要的性质。
异或的重要性质：有两个在 ${0,1}^n$ （n位01串）取值的随机变量X、Y。X、Y相互独立，X服从任意某种分布，随机变量Y服从均匀分布。那么 $Z=Y\oplus X$ ，Z在 ${0,1}^n$ 取值，且Z服从均匀分布。
Thm: Y a rand. var. over ${0,1}^n$ , X an index. uniform var. on ${0,1}^n$
Then Z := Y $\oplus$ X is uniform var. on ${0,1}^n$ .
Proof：
当n=1
画出联合分布
Pr[ Z=0 ]=Pr[ (x,y)=(0,0)] + Pr[(x,y)=(1,1)]=1/2
每一bit位都服从均匀分布，可以容易得出 Z是服从均匀分布。
The birthday paradox（生日悖论）
更具体的分析见 Birthday problem 。
问题前提：一个人的生日在365天的任意一天是均匀分布的（实际当然不是，貌似更多集中在9月）。
根据信鸽理论（有N个鸽子，M个隔间，如果N>M，那么一定有一个隔间有两只鸽子），所以367个人中，以100%的概率有两个人的生日相同。但是，当只有70个人时，就有99.9%的概率，其中两人生日相同；当只有23人，这个概率可以达到50%。
其实这并不是一个悖论，只是直觉误导，理性和感性认识的矛盾。当只有一个人，概率为0，当有367人时，为100%，所以我们直觉认为，这是线性增长的，其实不然。
概率论知识：
设事件A：23个人中，有两个人生日相等。
$P\left(A^{\prime}\right)=\frac{365}{365} \times \frac{364}{365} \times \frac{363}{365} \times \frac{362}{365} \times \cdots \times \frac{343}{365}$ $P\left(A^{\prime}\right)=\left(\frac{1}{365}\right)^{23} \times(365 \times 364 \times 363 \times \cdots \times 343)$ $P\left(A^{\prime}\right) \approx 0.492703$ $P(A) \approx 1-0.492703=0.507297 \quad(50.7297 \%)$ 推广到一般情况，n个人(n<=365)中，有两个人生日相等的概率 $P=\frac{365\times 364 \times (365-n+1)}{365^n}$
通过泰勒级数的近似处理（wiki上还有很多种近似方法），可以画出函数图如上图，概率值爆炸增。
从生日问题可以推导到一个定理：
n个独立同分布的随机变量 $r_1,r_2,…r_n$ ,且随机变量的取值 $\in \text{U}$ ,那么当 n = $1.2\times|\text{U}|^{1/2}$ 时，有两个随机变量取值相等的概率大于等于1/2，即 Pr[ ∃i≠j: ri = rj ] ≥ 1/2。
Let $r_1$, …, $r_n$ ∈ U be indep. identically distributed random vars.
Thm: when n = $1.2\times|\text{U}|^{1/2}$ then Pr[ ∃i≠j: ri = rj ] ≥ 1/2
「Cryptography-Boneh」：Introduction
