密码学概述（分析算法必看文章）

薛-蓝狐

为什么会有密码在现代社会中，很多信息都存储在计算机里，这让信息的增删改查变得非常方便，信息可以通过多种方式传递给任何人。因此，保护好自己的秘密信息变得非常困难。为了解决这些问题，人们开发出形形色色的“密码技术”。
从密码、认证、应用技术三方面介绍。一、密码首先看一下历史上著名的密码，第一个是恺撒密码，恺撒密码是将明文中所使用的字母表按照一定位数平移得到密文。在我们得到一串密文之后，可通过穷举的方式进行暴力破解，因为恺撒密码的密钥空间为 26，很容易被破解出来。

还有简单替换密码，是将明文中所使用的字母表替换为另一套字母表。

Enjoy it while it lasts  ->  XNVBK JQ CTJGX JQ GWLQL
对应关系是不定的，所以如果用暴力破解的话，密钥空间为 26*25*.. 即使每秒遍历 10 亿个密钥，也要遍历 120 亿年，所以极难破解。但是使用频率分析法破解就非常容易，统计密文中字符出现的频率，从其他样文中寻找规律，比如一篇文章出现最多的字符是e，就可把密文中出现最多的字符替换为e。文中经常会出现 is  the this 这样的字眼，根据这些规律进行替换尝试。密文越长的话越容易被破解。
以上可知加密算法应要保证密钥空间强度，密文及密钥也不应有一定规律。
1、对称密码
对称密码又称共享密码，加密和解密密钥相同。1.1 一次性密码本
一次性密码本是将明文与一串随机的比特序列进行异或运算得到密文。明文的比特序列与一串随机的比特序列进行异或运算得到密文，密文再与密钥进行异或运算得到明文



一次性密码
一次性密码本为什么没有被使用，主要有以下几点：
1. 密钥如何发送给对方？
在一次性密码本中，密钥和原文是一样长度的，试想如果有办法能把密文安全的送达到对方，那么是否可以用这种方法把明文送达到对方呢？所以这是一个矛盾的问题。
2. 密钥保存是一个问题
一次性密码本的密钥长度和原文一样长，密钥不能删除也不能丢弃。丢弃了密钥相当于丢弃了明文。所以“加密保护明文”的问题被转换成了“如何安全的保护和明文一样长度的密钥”的问题，实际上问题还是没有解决。
3. 密钥无法重用
如果加密的原文很长，那么密钥也要相同长度，并且密钥每次还要不同，因为如果是相同的，密钥一旦泄露以后，过去所有用这个密钥进行加密的原文全部都会被破译。
4. 密钥同步难
如果密钥每次都变化，那么密钥如何同步也是一个问题。密钥在传递过程中不能有任何错位，如果错位，从错位的那一位开始之后的每一位都无法解密。
5. 密钥生成难
一次性密码本想要真正的永远无法破解，就需要生成大量的真正的随机数，不能是计算机生成的伪随机数。1.2、DESDES (Data Encryption Standard) 是 1977 年美国联邦信息处理标准(FIPS)中所采用的一种对称密码(FIPS 46-3)。DES 一直以来被美国以及其他国家的政府和银行所使用。
1997 年 DES Challenge I 比赛中用了 96 天破解了 DES 密钥，1998 年的 DES Challenge II-1 比赛中用了 41 天就破解了密钥。1998 年的 DES Challenge II-2 比赛中用了 56 个小时，1999 年的 DES Challenge III 比赛中只用了 22 小时 15 分钟。目前来说，DES 已经不再安全了。除了用来解密以前老的 DES 密文以外，不再使用 DES 进行加密了。
DES 是一种把 64 位明文加密成 64 位密文的对称加密算法。它的密钥长度为 64 比特，但是除去每 7 个二进制位会设置一个用于错误检测的位以外，实际上密钥为 56 比特。DES 会以 64 个二进制为一个分组进行加密。以分组为单位进行处理的密码算法成为分组密码。
DES 加密的基本结构是 Feistel 网络、Feistel 结构、Feistel 密码，这个结构不仅仅用在 DES 中，还用在其他的加密算法中。
在 Feistel 网络中，加密的各个步骤称为轮(round)，整个加密过程就是若干次轮的循环。DES 是一种 16 轮循环的 Feistel 网络。
64 位的输入被分为左右两侧的输入，右侧的 32 位直接向下得到右侧的数据，右侧数据和子密钥通过轮函数生成一串随机的比特序列，此串比特序列和左侧32位输入进行异或运算得到左侧密文。



一轮加密之后可以看到，左侧数据被加密了，右侧并没有，所以第二轮时左右两侧交换数据再次执行上图的步骤。
一个 3 轮的 Feistel 网络。3 轮网络有 3 个子密钥和 3 个轮函数，中间有 2 次左右对调的过程。注意：n 轮 Feistel 网络只交换 n-1 次，最后一次不用交换。
Feistel 网络的特点
加密的时候无论使用任何函数作为轮函数都可以正确的解密，无须担心无法解密。就算轮函数输出的结果无法逆向计算出输入的值也无须担心。Feistel 网络把加密算法中核心的加密本质封装成了这个轮函数，设计算法的人把所有的心思放在把轮函数设计的尽量负责即可。
加密和解密可以用完全相同的结构来实现。虽然每一轮只加密了一半的明文，放弃了加密效率，但是获得了可以用相同结构来实现，对于加密硬件设备设计也变得更加容易。


由于 Feistel 网络的这些优点，所以很多分组密码选择了它。比如 AES 候选算法中的 MARS、RC6、Twofish。不过最终 AES 定下的 Rijndael 算法并没有选择它，而是选择的 SPN 网络。1.3、三重DES
三重 DES (triple-DES) 是为了增加 DES 强度，所以将 DES 重复 3 次得到的一种算法。也称为 TDEA (Triple Data Encryption Algorithm)，通常缩写为 3DES。使用加密、解密、加密的步骤是为了兼容 DES，当三个密钥相同时就是普通的 DES 加密。

3DES 由于处理速度不高，除了兼容之前的 DES 以外，目前基本不再使用它了。1.4、AES
AES (Advanced Encrytion Standard) 是取代前任标准 DES 而成为新标准的一种对称密码算法。在全世界的范围内征集 AES 加密算法，最终于 2000 年从候选中选出了 Rijndael 算法，确定它为新的 AES。
1997 年开始征集 AES，1998 年满足条件并最终进入评审的有 15 个算法：CAST-256、Crypton、DEAL、DFC、E2、Frog、HPC、LOK197、Magenta、MARS、RC6、Rijndael、SAFER+、Serpent、Twofish。2000 年 10 月 2 日，Rijndael 并定位 AES 标准。AES 可以免费的使用。
Rijndael 的分组长度和密钥长度可以分别以 32 位比特为单位在 128 比特到 256 比特的范围内进行选择。不过在 AES 的规范中，分组长度被固定在 128 比特，密钥长度只有 128、192 和 256 比特三种。
AES 的加密也是由多个轮组成的，分为 4 轮，SubBytes、ShiftRows、MixColumns、AddRoundKey 这 4 步，即 SPN 网络。一般要进行10-14轮运算。
以 128 位分组长度为例，第一步字节替换，将 16 个字节依次和 s-box 里面的字节按照索引进行替换得到新的矩阵，第二步是行移位，除了第一行，其他行依次左移不同位数，第三部是列的矩阵相乘，最后一步是每一个字节和轮密钥进行异或运算，这是整个一轮的步骤。




1.5、分组模式由于 DES 和 AES 一次加密都只能加密固定长度的明文，如果需要加密任意长度的明文，就需要对分组密码进行迭代，而分组密码的迭代方式就称为分组密码的“模式”。
分组密码有很多模式，如果模式选择的不恰当就无法充分保障机密性。
分组密码(block cipher) 是每次只能处理特定长度的一块数据的一类密码算法，这里的“一块”被称为分组。一个分组的比特数称为分组长度。例如 DES 和 3DES 的分组长度都是 64 位。AES 分组长度为 128 位。分组密码处理完一个分组以后就结束，不需要记录额外的状态。
分组模式：ECB  CBC CFB OFB CTR XTS
ECB 模式是分组模式里面最简单的，也是最没有安全性的。所以使用的人很少。
ECB 模式全称“Electronic CodeBook”模式，在 ECB 模式中，将明文分组加密之后的结果直接就是密文分组，中间不做任何的变换。攻击者可以很容易的分析密文中的规律进行破解，即使不知道密钥，攻击者也可将密文分组进行顺序交换，从而使接收者获取不到正确的数据。
CBC 模式的全称是 Cipher Block Chaining 模式，密文分组链接模式。名字中也展示它的实质，像链条一样相互链接在一起。有一个随机的初始化向量 IV ，初始化向量首先和明文分组1进行异或运算，在进行加密，得到密文分组1，密文分组1和明文分组2进行异或，再进行加密得到密文分组2，依次执行。


2、非对称加密（公钥加密）
为了防止中间人截获密钥，安全的把密钥传递给通信对方。有以下 4 种方式：
1. 事先共享密钥
这种方法虽然有效，但是具有局限性。在一次性密码本中，我们说过，大国之间的热线是用这种方式加密的，但是密钥是靠特工押送过去的。如果通讯对方在附近，提前共享密钥还比较方便。如果通讯对方在世界各地，这种方式也就存在局限性了。
另外通讯量增大以后，密钥个数也会陡增。n 个人两两通讯，需要 n * (n-1) /2 个密钥。这点来看，也不现实。
2. 密钥分配中心
为了解决事先共享密钥的密钥增多的问题。于是有人想出了密钥分配中心(Key Distribution Center, KDC)的办法。每次加密的密钥由密钥中心进行分配，每个人只要和密钥中心事先共享密钥就可以了。
虽然这个方法解决了密钥增多的问题，但是又带来了新的问题。
密钥中心存储和记录了所有的密钥，一旦它出现故障或者被攻击破坏，那么所有的加密都会瘫痪。这也是集中式管理的缺点。
3. Diffie-Hellman 密钥交换
为了解决集中式管理的缺点，那么应该密钥的配送还是不能用集中式。于是有人想出了 Diffie-Hellman 密钥交换的方法。
在 Diffie-Hellman 密钥交换中，加密通信双方需要交换一些信息，而这些信息即便被窃听者窃听，也不会有任何问题。
根据交换的信息，双方各自生成相同的密钥。而窃听者无法生成相同的密钥。这种方式可行。不过这种方式不算是非对称加密，在本文中不详细讨论。
4. 公钥密码
非对称加密有一个公钥和一个私钥。公钥可以在网上传播，被窃听者拿到也没有关系，由于没有私钥，他也无法解开密文。私钥只要掌握在接收者手上就不会导致密文被窃听。
非对称加密：
非对称加密一般指的是具有公钥密钥(public-key cryptography)的加密算法。密钥分为加密密钥和解密密钥两种。发送者用加密密钥对信息进行加密，接收者用解密密钥对密文进行解密。可以公开出去的叫公钥(public key)，保存在自己手上不公开的叫私钥(private key)。
公钥和私钥是一一对应的。一对公钥和私钥统称为密钥对(key pair)。在数学的关系上，这两者不能单独生成。2.1、RSA
RSA 是一种公钥密码算法，它的名字是由它的三位开发者，即 Ron Rivest、Adi Shamir 和 Leonard Adleman 的姓氏的首字母组成的 (Rivest-Shamir-Adleman)。1983 年，RSA 公司为 RSA 算法在美国取得了权利。
RSA 可以被用于公钥密码和数字签名。
在 RSA 中，明文、密钥和密文都是数字。
加密过程公式：密文 = 明文^E mod N
解密过程公式：明文 = 密文^D mod N


暴力破解的可能性：512 比特能够容纳质数的数量大约为 10 的 150 次方。假设世界上有 100 亿人，每人每秒生产 100 亿个密钥对，那么经过 100 亿年生成的密钥对数量大概是 10 的 39 次方，远远小于 10 的 150 次方。
在 2009 年，公开记录的被成功分解的最长 RSA 数为 768 位。
在密钥长度足够的情况下，极难被破解。但是会有中间人攻击。例如 Charles 的抓包原理





其他公钥密码：ElGamal方式、Rabin方式、椭圆曲线密码。2.2、混合密码系统
公钥密码解决了配送问题，还有两个很大的问题：
1、公钥密码的处理速度远远低于对称密码；
2、公钥密码难以抵御中间人攻击；
所以就出现了混合密码系统，如图所示，基本原理是用对称密钥加密消息，用公钥加密对称密钥。结合对称密码和公钥密码的优势。




三、认证
密码保证了消息的机密性，但是无法保证消息的完整性、认证、不可否认性。所以有了“消息指纹”。3.1、单向散列函数
常见的单向散列函数：MD4、MD5、SHA、SHA-1、SHA-2、SHA-3等
单向散列函数具备的特性：
根据任意长度的消息计算出固定长度的散列值
能够快速计算出散列值
消息不同，散列值也不同
单向性
应用：检测软件是否被篡改、基于口令的加密、消息认证码、数字签名、伪随机数生成器、一次性口令。
单向散列函数无法解决的问题：
单向散列函数能够辨别出“篡改”，但是无法辨别出“伪装”。对于一条消息不仅需要确认消息的完整性，还需要确认这个消息发自于谁。这仅仅靠完整性检查是不够的，还需要进行消息认证。认证的技术包括消息验证码和数字签名。3.2、消息认证码
为什么需要消息认证码？
A 向 B 汇钱 100 万元。如果攻击者从中攻击，篡改这条消息，就可能变成 A 向攻击者汇钱 1000 万元。这里针对汇款消息，需要注意两个问题：消息的 “完整性” 和 “认证” 。
消息认证码(Message Authentication Code) 是一种确认完整性并进行认证的技术，简称 MAC。
使用消息认证码可以确认自己收到的消息是否就是发送者的本意，也就是说可以判断消息是否被篡改，是否有人伪装成发送者发送了这条消息。

使用现状：SWIFT（Society for Worldwide Interbank Financial Telecommunications---环球同业银行金融电讯协会) 是一个目的为国际银行间的交易保驾护航的协会。银行

加量不加价

学习一下

为你一人

学习学习

klklkkkkk

新出的所谓量子计算机算力可能导致密码学革命？

与时俱进

学习了，有这方面的电子书吗？

zhoujinjian

学习了  感觉密码好难啊

无夜滴滴

很高深.....

theName

挺好的一个知识，mark一下，已备以后使用，感谢楼主的无私的分享。大力地支持楼主谢谢楼主。

xiaoyxf

字好多啊，开始还好，看到后来就头晕眼花了。。。。。

HyeYum

虽然看不懂  支持一下楼楼~