什么是密码学
===

这篇文章也只是点到为止，也就是个整理笔记+科普性质

密码学这个学科基本目的和研究对象：

* 面对**攻击者Oscar**，在被称为**Alice（发送方）和Bob（接收方）的通信双方**应用不安全的信道进行通信时，设法保证通信安全。
* 简单来说，密码学研究**对通信双方之间要传输的信息以何种方式进行变换以防未被授权的第三方对信息的窃取**。
* 信息安全三大问题是保证信息的**完整性、机密性、可用性**

**研究密码学需要一些基础的数论知识**，密码学第一次将发展了几千年的数论变成了一门有用武之地的学科。当然掌握的数学知识自然是越多越好：

整除。同余。辗转相除法。
质数及其基本性质（小学知识了......）。
费马小定理。裴蜀定理。中国剩余定理。
对概率要有个基本概念，哪些是很大可能的，哪些是几乎不可能的。

**大概知道当今计算机的能力上限，也就是说哪些是可以很快算出来的。哪些是不现实的：**
拿分解质因数来说。你要知道什么样的数是当今计算机分解不了的。
就今天的计算机来说，大概:
2的40次方次运算是容易 (easy)。
2的56次方次运算是可做 (feasible)。
2的64次方次运算是勉强能做 (barely feasible)。
2的80次方次运算是不能做 (infeasible)。
2的128次方次运算是肯定不能做 (totally infeasible)。
所以：
    破解4096位RSA是困难的。——即使用超算也如此。
    破解256位AES是困难的。——即使用量子计算机也如此。

**现代密码学通过一些数学难题而实现了一些很反常识或者叫做难以想象的事情：**

1.Alice可以向Bob证明自己拥有一个密码，但是如果B是假冒的验证者，Alice不会透露关于密码的任何信息给Bob。——“零知识证明”
2.Alice可以和Bob比较自己持有的一个值的大小关系，而不泄露这个值给对方。——“百万富翁问题”
3.Alice可以给Bob发来的一段信息进行电子签名，而不知道信息的内容。——“盲签名”
4.Alice和Bob可以在没有公正第三人的情况下，进行等概率胜负的博弈。——“电子博弈”
5.邮件服务，如果不考虑法律风险的话，是可以做到让服务器看不到你的邮件内容的。——PGP
6.破解OTP系统是不可能的。——即使歌者文明来了也如此。
7.一个好的加密算法真的应该是公开的——它可以接受更多人的检验。
一个好的密码系统不一定是公开的——但是它应该按照可以公开除了密码之外的一切而依旧安全来设计。
8.可以实现这样的算法，使得班干部中的任何一个均可以以班委会的名义下达通知，且其他人，除了班长之外，都不知道具体下达者。
9.密码系统的安全性取决于最弱的一环
10.大多数密码系统都不是被正面攻破的，而是实现过程中出了差错

**衡量密码体制的安全性有三条：**
计算安全的：在计算能力上是不可能的或者较为不切实际的
可证明安全的：如果破译要依赖于一个经过深入研究的数学难题的解决
无条件安全的：即使攻击者拥有了无限的计算能力和时间也不可破解

**密码的破译：找出密钥或者加密算法**

惟密文攻击：只有一段密文
已知明文攻击：知道一段密文以及相对应的明文
选择明文攻击：不仅知道一些密文以及相对应的明文，还可以选择特定的明文消息进行加密
选择密文攻击：知道一些不同的密文以及对应的明文信息
统计攻击：通过密文出现频率进行破译
边信道攻击：针对加密电子设备在运行过程中的时间消耗、功率消耗或电磁辐射之类的侧信道信息泄露而对加密设备进行攻击的方法
物理攻击：不多解释了

一些常用的密码算法
===

**古典密码**是现代密码学的基础，以现在的眼光去看都比较容易破解。如棋盘密码，位移密码，维吉尼亚加密法，希尔密码，置换密码，代换密码等，这里不展开了。

**分组密码**

* 对固定长度的一组明文进行加密的一种加密算法，这一固定长度称之为分组长度
* 一般分组为64位或者128位
* 现代密码学的重要组成部分
* 又被称作块密码

**DES算法**
* 64位为一组
* 密钥长度为64位，但是每个字节的第八位被用作奇偶校验，等于没用，实际上只有65位
* 加密过程

1. 初始IP置换，将64位明文分为左右各32位，仅仅加密开始进行置换，之后不再进行此操作
1. 对得到的64位序列进行16轮被F函数进行加密运算
1. 末尾IP置换，左右两部分合在一起成为密文
1. f函数：
a. 密钥序列位移
b. 口占置换成48位后与轮密钥进行异或运算
c. 通过8
d. 通过8个S盒替换成一个32位的序列
e. 队32位的序列应用P盒进行置换

**AES算法**

* DES的改进，叫做高级数据加密标准
* 加密算法的执行过程如下

1. 每组长度为128位，称为x，将其按照一定的规则赋值给消息矩阵State
1. 消息矩阵State与相对应的轮密钥矩阵Roundkey进行异或运算AddRoundKey(State,Roundkey)
第一轮开始
1. 除最后一轮以外，每一轮会进行如下操作
1. 对消息x应用s盒进行一次字节代换（操作）ByteSybs（State）
1. 对消息矩阵State进行行位移操作ShiftRow（State）
1. 对消息矩阵State进行列混合操作MixColumns（State）
1. 消息矩阵State与相对应的轮密钥矩阵Roundkey进行异或运算AddRoundKey(State,Roundkey)
1. 最后输出的消息矩阵State为密文y
1. 关于加密过程中用到的几个内置函数
1. 密钥异或运算AddRoundKey(State,Roundkey)
1. 字节代换ByteSybs（State）
1. 行位移ShiftRow（State）
1. 列混合MixColumns（State）

**序列密码**

* 又称作流密码。一般使用随机序列生成器生成真随机或者伪随机的随机序列，作为密钥流，进行加密。
* 很基本的一种对称加密，一直是军事和外交领域使用的主要密码技术之一
* 加密和解密双方使用相同伪随机加密数据流（pseudo-random stream）作为密钥，明文数据每次与密钥数据流顺次对应加密，得到密文数据流。实践中数据通常是一个位（bit）并用异或（xor）操作加密。
* 该算法解决了对称加密完善保密性（perfect secrecy）的实际操作困难。“完善保密性”由克劳德·香农于1949年提出。由于完善保密性要求密钥长度不短于明文长度，故而实际操作存在困难，改由较短数据流通过特定算法得到密钥流。
* RC4就是流密码，已被破解

**哈希算法**

哈希（hash）算法将任意长度的二进制值映射为较短的固定长度的二进制值，这个小的二进制值称为哈希值。哈希值是一段数据唯一且极其紧凑的数值表示形式。如果散列一段明文而且哪怕只更改该段落的一个字母，随后的哈希都将产生不同的值。要找到散列为同一个值的两个不同的输入，在计算上是不可能的，所以数据的哈希值可以检验数据的完整性。

所以说哈希算法是不可逆的

例子：

**SHA家族**，尤其是sha2和sha3是最安全的hash算法，sha1和MD5被山大的王小云教授找到了快速碰撞的方法，碰撞步骤从步280减少到了263

**MD5**算法具有以下特点：
1、压缩性：任意长度的数据，算出的MD5值长度都是固定的。
2、容易计算：从原数据计算出MD5值很容易。
3、抗修改性：对原数据进行任何改动，哪怕只修改1个字节，所得到的MD5值都有很大区别。
4、强抗碰撞：已知原数据和其MD5值，想找到一个具有相同MD5值的数据（即伪造数据）是非常困难的。

* 生日问题（生日攻击）：一个班级里，当人数大于23时，就有大于50%的几率有两人生日是一天

因为第二个人不能跟第一个人有相同的生日（概率是364/365），第三个人不能跟前两个人生日相同（概率为363/365），依此类推。

用p(n）表示n个人中至少2人生日相同的概率
带入n=23可得当屋内有23个人时发生的概率大约是0.507。其他数字的概率用上面的算法也得出来： 

同理，想要保证碰撞概率极小，消息摘要的长度就要在128位以上，此时不同原文哈希出的摘要相同的概率是2^64分之1

应用：
* 验证一致性：对文件内容进行md5，每个文件的md5都不一样，这样接收方可以知道文件有没有被篡改

* 数字签名：和验证一致性差不多，如果有第三方机构来来管理证书，还可以让原作者承认这个是他写的

* 安全访问验证：我们一般使用的密码不是直接存在服务器的数据库里，存在数据库里的都是MD5加过密的值，而且还都加了盐。登录的验证过程需要把你输入的密码明文经过MD5加密后（包括加盐）与数据库里的值作对比（selec *from password where pass = 某个MD5值）。原因就是我们不希望提供服务的人知道自己账户的密码

关于MD5的实现和其缺陷，参考哈希扩展长度攻击

**公钥密码**

很典型且被经常使用的一种密码类型，概述如下

基本思想：把密钥分为两部分，公钥和私钥，任何人都可以获得公钥来进行加密，私钥只有解密一方有，用来解密
公钥密码算法要有如下几条基本要求

发送方Alice通过公钥加密明文在计算上是容易的
接收方Bob通过私钥解密密文在计算上是容易的
接收方Bob产生密钥对（公钥和私钥）在计算上是容易的
攻击者Oscar使用公钥对密文进行解密在计算上是不可行的
攻击者Oscar使用公钥求出对应密钥在计算上是不可行的
所以公钥密码体制一般的理论基础是某个尚未解决的数学难题上，如分解超大质因数等

**RSA算法**

RSA公钥加密算法是1977年由罗纳德·李维斯特（Ron Rivest）、阿迪·萨莫尔（Adi Shamir）和伦纳德·阿德曼（Leonard Adleman）一起提出的。1987年首次公布，当时他们三人都在麻省理工学院工作。RSA就是他们三人姓氏开头字母拼在一起组成的。
RSA是目前最有影响力的公钥加密算法，它能够抵抗到目前为止已知的绝大多数密码攻击，已被ISO推荐为公钥数据加密标准。
RSA算法基于一个十分简单的数论事实：将两个大质数相乘十分容易，但是想要对其乘积进行因式分解却极其困难，因此可以将乘积公开作为加密密钥。
随着计算力的发展，分解大数也变为了可能

背包算法：已被证明是不安全的

**数字签名**

* 解决的是信息的不可抵赖性，发送方Alice不能否认自己发送过某信息，是一种防止通信双方相互作弊的安全机制
* 起到类似于手书签名的作用
* 数字签名至少满足三个基本要求
* 签名人无法否认自己曾经签发的数字签名
* 守信者能够验证和确认收到的数字签名，任何人无法伪造别人的数字签名
* 当各方对数字签名的真伪产生争议时，需要通过可信的第三方进行裁决
* 数字签名体制一般包含两个部分
* 签名算法
* 验证苏研发
* 数字签名的特性
* 依赖性：数字签名必须依赖于被签名消息的具体比特模式
* 独特性：签名中必须包含能狗带表签名者特有的身份信息
* 可验证性：数字签名必须是可验证的，能够通过算法准确的验证数字签名的真伪
* 不可伪造性：计算或者拼接等方法伪造签名是不可能的
* 可用性：生成、识别和验证过程要相对简单

**在某软件当中的实际应用**

RC4-MD5
* RC4（来自Rivest Cipher 4的缩写）是一种流加密算法，密钥长度可变。它加解密使用相同的密钥，因此也属于对称加密算法。RC4是有线等效加密（WEP）中采用的加密算法，也曾经是TLS可采用的算法之一。由美国密码学家罗纳德·李维斯特（Ronald Rivest）在1987年设计的（对，就是那个RSA的R老哥）。由于RC4算法存在弱点，2015年2月所发布的 RFC 7465 规定禁止在TLS中使用RC4加密算法[1]。RC4由伪随机数生成器和异或运算组成。RC4的密钥长度可变，范围是[1,255]。RC4一个字节一个字节地加解密。给定一个密钥，伪随机数生成器接受密钥并产生一个S盒。S盒用来加密数据，而且在加密过程中S盒会变化。由于异或运算的对合性，RC4加密解密使用同一套算法。
* 速度最快
* 已经被破解
* 使用MD5进行校验

**Chacha20**
* chacha20是salsa20的改良
* 20 ： 20轮加密
* ietf ： chacha20算法的一个变种（某些参数调整）
* xchacha20 : 记忆中xchacha20比chacha20好
* poly1305 : 消息完整性校验方式
* ChaCha20-Poly1305 避开了现有发现的所有安全漏洞和攻击；
* ChaCha20-Poly1305 针对移动端设备大量使用的ARM芯片做了优化，能够充分利用 ARM 向量指令，在移动设备上加解密速度更快、更省电；
* 更加节省带宽，Poly1305 的输出是 16 字节，而 HMAC-SHA1 是 20 字节，可以节省 16% 的 overhead 消耗。
* 性能不强的设备（路由器）最好的加密算法

**Camellia**
具有和AES同等级的安全强度及运算量

**结论**：不推荐bf-cfb，chacha20、salsa20、rc4-md5，轻量级的设备用chacha20-iet。手机和PC上用AES、camellia是最好的