密码学简述

一、概述

1. 什么是密码学

​ 密码学（Cryptography）。是由希腊单词 Kryptos（隐藏）和 Graphin（写）派生出来的，最初代表的意思是用来隐秘的传递信息。隐藏和写就是隐写，在古典密码学的发展中就有一门称为隐写术的技术，比如说藏头诗就是一种隐写术。在《巨人的陨落》中，艾瑟尔和弟弟比利就是通过每隔两个单词就会加一个单词来作为加密后的密文，这也是隐写术的一个例子。隐写术发展到今天演变为数字水印技术，一般在文件中加一个标识信息（即数字水印），可以起到追踪溯源，防伪和版权保护的作用。

​ 密码学一开始的功能是在有恶意攻击者存在的环境下，保护双方通信安全，现在是用来保护信息安全的核心技术。开放的来说，密码学的基本目的是使得两个在不安全信道中通信的人，通常称为Alice和Bob,以一种使他们的敌手Oscar不能明白和理解通信内容的方式进行通信。这样的不安全信道在实际中是普遍存在的，例如电话线或计算机网络。Alice 发送给Bob的信息，通常称为明文(plaintext),例如英文单词、数据或符号。Alice 使用预先商量好的密钥(key)对明文进行加密，加密过的明文称为密文(eiphertext) , Alice将密文通过信道发送给Bob。对于敌手Oscar来说，他可以窃听到信道中Alice 发送的密文，但是却无法知道其所对应的明文:而对于接收者Bob,由于知道密钥，可以对密文进行解密，从而获得明文。

2. 密码学体制定义

密码体制：

  • 明文空间
  • 密文空间
  • 密钥空间
  • 加密算法
  • 解密算法

一个密码体制是满足以下条件的五元组（P，C，K，E，D）：

  1. P代表所有可能的明文组成的有限集；
  2. C代表所有可能的密文组成的有限集；
  3. K代表密钥空间，由所有可能的密钥组成的有限集；
  4. 对每一个k∈K，都存在一个加密规则ex∈E和相应的解密规则dx∈D。并且对每对ex:P→C，d:C→P满足条件：对每一个明文x∈P，均有d,(e())=x。

二、 古典密码学

​ 密码学届以1976年为界限，之前的密码学算法称为古典密码学，其基本都使用在军事机密和外交领域，它的特点就是加解密过程简单，一般用手工或机械就可以完成。

古典密码学中最经典的有三种算法：

  1. 凯撒移位密码
  2. 仿射密码
  3. 希尔密码

1. 凯撒移位密码

恺撒移位密码 因据说恺撒是率先使用加密函的古代将领之一，因此这种加密方法被称为恺撒密码。这是一种简单的加密方法，这种密码的密度是很低的，只需简单地统计字频就可以破译。 现今又叫“移位密码”。

加密时在一个特定的表中（一般为字母表）每一个元素向同一个方向移动相应的key位，然后通过数字对应（例如字母表对应的0-25），生成密文。其中key即为密钥。

2. 仿射密码

​ 仿射密码为单表加密的一种，字母系统中所有字母都藉一简单数学方程加密，对应至数值，或转回字母。 其仍有所有替代密码之弱处。所有字母皆借由方程

img

加密，b为移动大小。

​ 仿射密码是一种替换密码。他是一个字母对一个字母的。它的加密函数是$e(x) = ax + b (mod m)$，其中a和m互质，m是字母的数目。解码函数是$d(x) = a{-1}(x-b)(mod m) $，其中$a{-1}$是a在

img

群的乘法逆元。（乘法逆元，是指数学领域群G中任意一个元素a，都在G中有唯一的逆元a‘，具有性质a×a'=a'×a=e，其中e为该群的单位元。）

3. 希尔密码

​ 希尔密码（Hill Cipher）是运用基本矩阵论原理的替换密码。每个字母当作26进制数字：A=0，B=1，C=2…一串字母当成n维向量，跟一个n*n的矩阵相乘，再将得出的结果MOD 26.

​ 用作加密的矩阵必须是可逆的，否则就不可能解码。且只有矩阵的行列式和26互质，才是可逆的。

三、现代密码学

1. 现代密码学的起源

现代密码学主要有三个代表事件：

  1. 1976年：由 Diffie 和 Hellman 在《 密码学的新方向》（《New Directions in Cryptography》）提出了公钥密码学体制的思想
  2. 1977年：美国国家标准局颁布数据加密标准 DES（Data Encryption Standard）
  3. 1978年：第一个公钥算法 RSA 算法（由 Ron Rivest、Adi Shamir 和 Leonard Adleman 的姓氏首字母组成）

现代密码学的意义是让密码学成为一门课学，研究方向也从军事和外交走向了民用和公开。随着其历史的发展，现代密码学主要分为了三个方向：

  • 私钥密码（对称密码）
  • 公钥密码（非对称密码）
  • 安全协议

1. 对称加密

概念：

对称加密也叫私钥加密，是对文字的加密转换成对比特序列的加密（类似于古典密码的加密方式），用同一种密钥或者可以互推的密钥进行加密和解密操作，这个密钥发送方和接收方都是要保密的，所以称为私钥密码。

设计原则：

对称密码有两个设计原则：

  • 一个是扩散（Diffusion）：明文的统计结构被扩散消失到密文的长程统计特性，使得明文和密文之间的统计关系尽量复杂。
  • 另一个是混乱（confusion）：使得密文的统计特性与密钥的取值之间的关系尽量复杂。

代表算法：

  • DES算法
  • AES算法
  • 3DES（TripleDES）

优缺点：

  • 优点：加密速度快
  • 缺点：无法确保密钥被安全传递，安全性相对低

2. 非对称加密

概念：

又称为公开密钥算法。加密和解密使用不同的密钥，公钥传给对方，用于加密。自己对应的私钥用于解密。公钥可以由私钥生成，私钥可以推导出公钥，但是公钥无法推导出私钥。

加密原理：

加密和解密使用不同的密钥。每个人都有一个“公钥-私钥”对，公钥加密使用可以任意分享，私钥解密使用好好保护，使用公钥加密的信息只有对应的私钥才能解密。公钥和私钥之间不能互推。

代表算法：

  • RSA算法
  • DSA算法
  • ECC（椭圆曲线加密算法）

优缺点：

  • 优点：无需传输密钥，安全性高。
  • 缺点：算法复杂，加密解密速度慢。

3. Hash密码

定义：

一个Hash族是满足下列条件的四元组（X,Y,K,H）：

  1. X是所有可能的消息的集合；
  2. Y是由所有可能的消息摘要或认证标签构成的有限集；
  3. K是密钥空间，是所有可能的密钥构成的有限集；
  4. 对每个k∈K，存在一个Hash函数hx∈H。

加密原理：

将一段数据（任意长度）经过计算转换成一段定长的数据。

优缺点：

  • 优点：不可逆，几乎无法通过哈希的结果推导出原文，无碰撞性，两个不同原文哈希后的结果一定不同（这个说的太绝对了，不能说一定不同，还是有一定概率的，但是概率就和你暗恋的女神也暗恋你一样小）
  • 缺点：部分hash算法有极小概率的碰撞问题

常用算法：

  • MD5（2004年以后陆续发现其无法防止碰撞可能并且可以破解）
  • SHA256

4. 数字签名

起源：

​ 数字签名是针对非对称加密无法确认发送方的身份这个问题的，在非对称加密中，任何人都可以使用接收者的公钥进行加密，而接收者却无法知道发送方的真实身份，因此如果发送方进行身份伪造，非对称加密则毫无意义。这也就导致了数字签名的出现。

原理：

​ 数字签名的原理是发送方使用自己的私钥对发送内容的Hash摘要进行加密从而生成签名，接收方只需要使用发送方的公钥解密并和原文验证就能确认发送方的身份并且判断发送内容是否被第三方窃取修改。具体步骤如下（假设发送方A要给接收方B发送消息）：

  1. 发送方A对发送内容Data执行Hash运算得到hash值简称”摘要“h1。
  2. 然后使用自己的私钥对摘要h1进行加密，生成的东西叫做”数字签名“。
  3. 把数字签名附在发送内容Data后，一起发送给接收方B。（当然发送内容Data需要通过接收方的公钥加密，此处我们只是降解数字签名，因此不做论述）
  4. 接收方B在收到发送内容Data后首先使用发送方A的公钥对数字签名进行解密，解密成功则代表确认发送方为A。（成功后则可使用接收方B自己的私钥对发送内容Data进行解密）。
  5. 接收方B通过对发送内容Data执行hash运算获得摘要h2.
  6. 接收方B将数字签名解密后的摘要h1和自己Hash后的摘要h2进行比对，如果一致，则表示发送内容Data未被第三方修改。

5. 数字证书

起源：

​ 数字证书的起源是对数字签名的优化改进，是针对在接收方使用从服务器获取的发送方的公钥对签名进行解密的过程中发送方的公钥被篡改而设置的。而接收方并不知使用的公钥是否是发送方的真实公钥。

原理：

​ 数字证书的原理是通过一个绝对权威的机构来保证发送方的公钥没有被纂改。这个机构叫做”证书中心（certificate authority，简称CA）“。具体的过程如下：

  1. 发送方A找到CA并提交自己的公钥等身份认证信息。
  2. CA使用自己的私钥对发送方A的公钥等信息进行加密生成”数字证书“。（证书内容包括：签发者、证书用途、A的加密算法、A用的HASH算法、证书的到期时间、A的公钥、CA的私钥等）
  3. 发送方发送文件时在正文后附上数字签名外，同时附上数字证书。
  4. 接收方B收到文件后使用CA的公钥解密数字证书，获取A的公钥。
  5. 接收方B通过数字证书中A的公钥对数字签名进行解密。

数字证书的问题：

​ 数字证书的问题时加密验证中都无法避免的终极问题，即不存在绝对安全的事物。以上数字签名包括数字证书也都是在竭力降低这个问题发生的概率。

  • 假如数字证书被伪造怎么办？

    ​ 权威机构也并非绝对安全，因此数字证书也可能被伪造。因此，数字证书也经过了数字签名，之前提到数字签名的作用就是验证数据来源以及数据完整性。因此接收方B在收到文件后需要先验证数字证书的可靠性，通过后再验证数字签名。以此来降低可能存在的风险。

  • 假如有多个发送方$A_n$给接收方B发送文件，那么B是否就要多存储n份不同的CA公钥？

    并不是，CA认证中心可以给接收方B一份”根证书“，根证书中存储着所有的CA公钥，其可以验证CA颁发的所有的数字证书。

  • 如何验证根证书可靠性？

    这是个套娃的问题，还是之前的问题，不存在绝对的安全。我们只能从安全性和能效中做出权衡，找到其平衡点。保证其高安全性的同时也不忘初心（套那么多层娃干什么啊喂，明明只是为了保证一份小文件的安全，当然你要是有时间有金钱要无限接近绝对的安全可以把一个CA的数字证书找其他的CA继续认证，无限套娃！最后变成P2P安全认证！）。

应用：

  • HTTPS协议

Q.E.D.

If you don't come, I will snow.