开始学习密码学，这是一套不错的课程。官方课程链接Online Cryptography Course。教材A Graduate Course in Applied Cryptography，Coursera上的链接为密码学 I。

下面记录第一周的学习笔记。

Course Overview

密码学无处不在，DVD使用的是CSS加密，Blu-ray使用的是AACS加密。

常用的HTTPS底层用的是SSL/TLS。安全的交流中间是没有偷听和篡改的。

对称加密系统使用的是同一个key。加密算法是公开的，永远不要使用一个专有的加密算法。

密码学不是所有安全问题的解决方案，例如软件漏洞或者工程上的攻击。

What is cryptography?

Crypto core

密码学的核心建立密钥，保证交流的可靠和完整性。

But crypto can do much more

密码学可以应用在匿名交流中，上图中的匿名是相互的，Alice不知道对方是谁，Bob也不知道对方是谁。

密码学应用在匿名电子货币，类似于我们去商店消费，不想让商店知道我们的身份，同时在网络中，要保证电子货币不能重复消费。

Protocols

在选举或者私有拍卖的例子中，有受信的第三方来进行公布结果。这里有一个重要的理论，任何可以使用受信第三方完成的事也可以不用第三方就能完成。

Crypto magic

A rigorous science

密码学是一门严谨的学科，要遵循以上三个步骤。

History

替换式加密的密钥空间很大，是26个字母的全排列。

破解替换式加密的方法是利用了英语字母出现的频率，字母e出现的频率最高，那么我们可以对截获到的密文统计出现的频率，出现频率最高的字母就对应于字母e。接着再利用二合字母出现的频率。

当我们知道key中加密字母的长度时，就很好破解。

Discrete Probability

这部分详细介绍见https://en.wikibooks.org/wiki/High_School_Mathematics_Extensions/Discrete_Probability。

Events

The union bound

Random Variables

The uniform random variable

Randomized algorithms

Independence

XOR

异或中重要的一个定理是，Y是一个随机变量，X是一个独立的均匀分布变量，Y与X异或之后是一个均匀分布变量。

The birthday paradox

当$n=1.2 \times \sqrt{|U|}$时，$U$ 中存在两个变量相等的概率大于等于$1/2$。常识认为可能是$|U|/2$，因此也叫做悖论。

The One Time Pad

key和要加密的消息的长度一样长。

key也可以算出来，是m和c的异或。

什么是安全的加密呢？香农的定义是，不能从密文中得到任何关于原文的信息。

用概率来定义 perfect secrecy，也就是从密文中无法区分任意两个原文，得到两个不同message的概率是相同的。

OTP是有perfect安全性的。

OTP是没有惟密文攻击，但是有其他攻击。

Pseudorandom Generators

用伪随机key代替随机key。

永远不要在加密中使用glibc中的random()函数。

Negligible vs. non-negligible

可忽略的：意思是比多项式的逆下降地还要快。

Attacks on OTP and stream ciphers

不能两次使用相同的PRG(k)。

客户端到服务端与服务端到客户端应该使用不同的key。

中间可以加入p，然后进行篡改。

Real-world Stream Ciphers

PRG Security Defs

一个安全的PRG是不可预测的。

反过来也成立，一个不可预测的PRG是安全的。

用到了前面定理(Yao’82)的逆否命题。不安全的PRG是可预测的。

更一般的定义，computationally indistinguishable。

Semantic security

前两个定义都太强了，需要一个弱一些的定义，找到存在的 $m_0$ 与 $m_1$。

这里给出了semantically secure 的定义。

OTP是 semantically secure 的。

Stream ciphers are semantically secure