密码学部分总结（不断更新）
这篇书评可能有关键情节透露
（注：公式会因为word格式问题而缺失，所以以图片形式来显示了）
Preface
其实，学习密码学一开始是出于喜欢。学习密码学给人一种了解解谜的快感，而我在暑假的那段时光突然喜欢上了一点推理电影，而密码学的气质和推理之类的是很契合的。但是后来发现密码学确实是信息安全里最重要的，也是一门古老的学科了。但是密码学可以说是信息安全里的一股清流了，我们常常说的安全，常常是建立在一系列复杂的机制、步骤之上，比如各种网络协议，但是密码学看上去是很简单的（如果你不去看具体的内部算法）。加密无非就是调用函数，解密也是。所以它封装的很好使得我们以为加密是简单的。后来我知道，加密、解密算法内部其实也很复杂。这个复杂为加密的安全性提供了保障。余甚愚哉，无法完全理解加密算法的步骤。所以我现在只能以差不多一个半旁观者的姿态去学密码学——对于忽略比较复杂的算法步骤。但是我需要做的也不简单，我需要理解除步骤以外的其他任何关于密码学的东西。
1加密基础（2018-8-xx）
2对称加密（2018-9-xx）
3非对称加密（2018-10-xx）
对称加密存在一个问题：如何做到密钥分发的安全？这个问题随着非对称加密的出现得到一定的解决。非对称加密也称为公开密钥加密。据传其最先是被英国政府通信总部在20世纪60-70年代发明的。但是我们公认Diffie-Hellman(-Merkle)为非对称加密做出了开创性贡献。同时也在2015年被授予图灵奖（没包括Merkle）。非对称加密算是密码学中比较新生的领域了。
什么是非对称加密？在对称加密系统中只有一个密钥，既用于加密也用于解密。而在非对称加密系统中，有公钥和私钥对。公钥是一个人，比如我们称之为A，给其他人看的，是公开的，私钥是A私藏的，并且和公钥配对的。当其他人要和A通信时，使用A发给大家的公钥加密数据M得到密文C，而只有A的私钥能够解密这个用A的公钥加密了的消息C。反过来，私钥加密了的消息也只能用公钥来解密。
但是虽然看似非对称加密比对称加密要高端，而且已经诞生近半个世纪了。但是非对称加密的方案实际上仍然很少，而其中获得广泛应用的更少。但对称加密相反却有大量的加密方案且获得了非常广泛的应用。因为每一个非对称加密的方案都基于非常特殊的数学结构，于是开发新的方案就会很难。
非对称加密方案基于单向陷门函数，也可以称为NPC问题（或者至少NP问题吧）。使得从一个方向向另一个方向计算容易，但是反过来困难。比如因式分解。
接下去我们考察几个非对称加密系统。
3.1背包加密
该方案首先由Merkle和Hellman提出。
故a序列是：(1,0,0,0,1,1,0)。其实是线性时间，O(N)的复杂度.
基于背包的加密系统其流程大致为：
（1） 生成一个超递增背包。
（2） 将这个超递增背包转化为常规背包。
（3） 公钥是常规背包。
（4） 私钥是超递增背包及转化因子。
但遗憾的是，这个背包系统在1983年被证明是不安全的，能被格基规约技术给攻破。因为实际上这个由超递增背包产生的常规背包不是真正的常规背包，事实上，它是一种高度结构化的背包，而格基规约攻击能够利用这种结构的特点比较容易地恢复出明文。
3.2 RSA
RSA=Rivest + Shamir + Adleman.这三位都是加密技术的大佬。而且早在2002年就获得了图灵奖，限于Diffie-Hellman。所以似乎看来RSA的重要性比非对称加密本身都要重要了。
RSA依赖的是大素数的因式分解问题。而这个问题，由于有大量聪明人已经充分关注但是还是尚未有人找到有效的解决方案，因此是安全的。
3.2.1 RSA加密算法
RSA安全的关键是素数p,q。如果我们得到了p,q，那就得到了密钥（包括私钥）。因此p,q要大èN要大。一般的N取1024位以上。这使得对于N因数分解找遍所有的p,q变得很难。
除了面对私钥的攻击，还有直接面对明文的攻击。攻击者可以使用前向检索攻击来对付这个密码系统：猜测明文消息M，然后用公钥对其加密，看是否和密文C相同，如果相同那就知道了明文M了，虽然私钥仍未暴露。防止此类攻击可以采取为消息附加随机的二进制位，比如PKCS#1v1.5填充模式。这里不展开。
3.2.2 RSA加速
RSA看似很好，但其实如果硬着头皮加密也还是很费时间的。意思是我自己加密一条消息都要费很多时间，因为要做指数运算：
。这里的M和e往往很大。针对大数及大的指数执行求幂运算是代价非常高昂的问题。如何来加速这个指数运算呢。有一种方法叫做重复平方法。
另外，对所有用户使用同一加密指数e（但解密指数不同），也可以加速RSA密码系统。比如通常选择e=3，比较小，这样对于中心服务器的加密负载比较小，但对用户的解密负载较大。
3.3 Diffie-Hellman密钥交换算法
这个密钥交换算法真的只是用来交换密钥的。这是用非对称加密方案来解决对称密钥加密中的密钥安全分发问题的算法。
DH算法的安全性建立在离散对数问题的计算难度。给定和，求k。这个问题其实不是NPC问题，而是一个NP问题，和因数分解问题一样。
DH的机制如下：
（1） 设定p为素数，g对于任何，都存在指数n，使得.这里p和g是公开的。
（2） 现在Alice秘密地选择指数a，Bob秘密地选择指数b，Alice计算并发给Bob，Bob秘密地计算并发给Alice。
（3） 于是Alice能够得到，Bob能计算得到.
（4） 就是共享秘密，或者是要分发的对称密钥。
（5） 攻击者Trudy就算截获了和，知道g和p也无法得到.它必须得到a或者b才能知道。
3.4 椭圆曲线加密
椭圆曲线加密（Elliptic Curve Cryptography, ECC）的优势在于要获得同样等级的安全性，需要的二进制位少。而且所有最近的非对称加密标准都基ECC，包括区块链里用的。而且ECC在资源受限的环境中尤其重要，比如在移动端。
这里的椭圆曲线方程和高中的圆锥曲线中的椭圆方程形式不同。表达为：
如上图所示P1,P2是某直线与曲线的交点，P3是该直线第三个交点相对x轴做对称映射得到的点。定义P3=P2+P1.
考虑椭圆曲线的模运算：
比如：
取5个x值:
得到以下几个点：(1,1)(1,4)(2,0)(3,1)(3,4)(4,0)
定义在椭圆曲线上的加法运算。这里略，就是将P3=P2+P1以详细的计算方式列出来。这样以来就能以这几个基本点，作加法运算得出新的、位于椭圆曲线上的点了。由于定义了加法运算，乘法可以通过累加来实现。
一个实例：基于椭圆曲线加密的DH密钥交换算法。其机制如下：
（1） 先确定一条椭圆曲线及该曲线上的一点，比如
和点(2,7)
（2） Alice和Bob各自确定一个秘密乘法因子，比如A=15，B=22.
（3） Alice计算A*(2,7)=15*(2,7)=(102,88)
Bob计算B*(2,7)=22*(2,7)=(9,43)
（4） 然后Alice将自己的结果发给Bob，而Bob也是。
（5） 于是有A*(9,43)=15*(9,43)=(131,140)
B*(102,88)=22*(102,88)=(131,140)
（6） (131,140)就是需要分发/共享的密钥。
（7） A*B*(2,7)=(A*B)*(2,7),满足结合律。而即使攻击者Trudy知道A*(2,7)和B*(2,7)也无法算出A*B*(2,7)。
椭圆曲线加密与之前的非对称加密手段相比好像是用了一种新版本的模运算（椭圆曲线上的加法、乘法、模运算）一样。这使得它比使用一般的模运算的非对称加密手段达到相同安全性所需要的密钥长度更短。
3.5应用
有一句话叫做，能用对称加密手段完成的任务，都可以用非对称加密来完成，只不过要慢一些。（也就是说对称加密的主要优势是效率）但非对称加密相对于对称加密也有2大优势。第一大优势是不需要建立共享密钥。第二大优势是非对称加密中的数字签名能给消息提供数据完整性保证。
我们先思考一下，能否把这两者的优势结合起来呢？明显是可以的。我们可以用这之前的密钥交换算法，基于非对称加密手段建立对称密钥，然后使用这个密钥来进行数据加密。
其次，我们介绍一下数字签名。因为A给大家发了自己的公钥，所以每个人都可以向A发生用A的公钥加密的消息。但是只有A自己拥有私钥。于是乎可以依靠这个条件来证明某消息是A发送的。如果A要公布一件事情，比方说一个消息M，它可以用自己的私钥来加密之，结果是大家都可以用公钥来解密之。因为大家知道只有A拥有私钥，所以能用公钥解密的消息，肯定是A用自己的私钥加密的。这种验证就像签名一样，故称之为数字签名。关于数字签名的具体内容见下一章的4.1节。
在实际使用中，我们先对消息M加密，得到密文C，在对密文C签名，先对密文做哈希运算，然后用私钥加密，得到签名S，所谓先加密后签名就是这个意思。
数字签名之所以还可以保证数据完整性是因为，如果消息M内容变化，则S也会改变。比如我们发送的完整消息是C+S,得到的消息确实C’+S，则进行验证{hash(C’)}≠S，说明消息体被篡改了。
3.6非对称加密的基础设施PKI
要实现非对称加密其实需要一些列的设施(Public Key Infrastructure)，简称为PKI.因为在非对称加密系统中的每个人，要接受来自外界的信息都需要有一对公钥和密钥，就像地址一样，其中公钥是要告诉别人的。
数字证书就是包含了用户名称及相关用户的公钥的东西，该证书本身也需要一些权威机构进行签名，以为其可靠性背书。这些权威机构称为证书权威机构，简称CA，如果CA是信得过的，则是可信第三方（TPP，Trusted Three Party）。所以数字证书中的每一个记录应该包含以下内容：（以Alice用户为例），其中S是CA使用CA自己的私钥的签名。
一般来说私钥和公钥对也是CA产生以后，并前面然后发给用户使用的。虽然我不知道为什么用户自己为什么不可自己生产出公私钥对以保证安全。毕竟别人给你的私钥没自己做的安全。
为什么需要CA呢？如果没有CA来为某些数字证书签名，我们就不知道某个公钥是否真的是某人的，比如Trudy把自己的公钥T公布，并假称其是Bob的公钥。于是想发消息给Bob的人就用之加密了。结果是，只有Trudy能看到消息内容。这很明显会造成安全问题。现在有了CA，CA不会对Trudy单方面发布的公钥条目：(‘’Bob”,T)签名，于是就不存在数字证书：。CA会默认Trudy只能拥有数字证书：。
当然，事实上，数字证书里还包含了其他的信息。这里不再列出。
但是数字证书里包含的消息越多，其消息的时效性也越强。意味着数字证书是会过期的。于是PKI还面临着另一个问题——数字证书的撤销。通常的数字证书都有有效期，因此到期之后不需要手动去撤销了。但也存在，私钥被攻破/泄漏，于是需要CA去手动撤销数字证书的情况。
PKI体系最重要的三个问题是密钥的生成与管理，数字证书的授权，数字证书的撤销。这三个都离不开CA。所以说CA其实是PKI系统中最重要的机构或者说是参与者了。
CA这种东西涉及到信任，有点区块链的感觉。所以说CA也有几种模型。
第一种是完全中心化的——垄断模型。只有一个CA，比如政府。其缺点在意这唯一的CA如果被攻破则整个PKI都会瘫痪。
第二种是多中心化的——寡头模型。这正是如今使用的模型。一个Web浏览器会配置上几十个CA的证书，我们可以自己选择信任哪些CA，也可以使用浏览器默认的信任设置。
第三种是完全去中心化的——混乱模型。每个人都可以产生密钥对、签发证书。这种方案在PGP里用到了，也就是所谓的信任网（Web of Trust）。
4哈希函数（2018-10-11）
密码学中的哈希函数和其他地方的hash是不一样的。虽然它们本质上是一样的。这可以从如下看出来，一个加密哈希函数必须具有以下特性：
（1） 压缩。对于任意长度的输入值x，输出值y=h(x)的长度都比较小，一般是固定长度，如160位。
（2） 高效。任意的x，h(x)的计算量/计算复杂度应该低，随着x的规模，h(x)总不能是O()。
（3） 抗弱碰撞性。给定x和h(x)，要找到任意的y，使得y≠x，且h(y)=h(x)，这是不可能的。
（4） 抗强碰撞性。要想找到任意的x和y，使得y≠x，且h(y)=h(x)，这是不可能的。
第三和第四条的意思就是我们不能够找到任何两个不同的输入使得其hash函数的输出是相同的。
但是，不得不承认的是，hash函数的输入空间远远大于输出空间，所以碰撞是一定存在的。一旦发生了碰撞，我们就称这个哈希函数被攻破了，于是这个哈希函数就不安全了。为什么发生碰撞就不安全了呢？看下面这个例子。
4.1数字签名
哈希函数一个很典型的应用场景就是非对称加密领域的数字签名。
其中h(M)表示对消息M作哈希运算。表示用Alice的私钥进行加密。一般来说，我们会先加密后前面。意味着消息M其实是被加密过的，即.
表示others的公钥。一般我们加密消息发送给某人，是用的这个人的公钥，而数字签名签上的是我们自己的私钥（对应的是我们发给别人用的公钥）。
故，综合而言，数字签名（Alice发给others的消息M后数字签名）的内容是：
现在，我们来考虑哈希函数被攻破（发生碰撞）会造成的后果。假设Trudy是想搞破坏的那个人，他构造了一条恶意的消息E，并且想得到Alice的数字签名来搞破坏。如果他最后获得了Alice对这条消息E的数字签名，那么我们就称他成功了。接下来看他打算怎么得到Alice的数字签名。
1. 假设Trudy能获得Alice对于一些无害消息的签名。比如消息I是Trudy作为Alice的下级，定期需要Alice签名的日常消息。比如：“今天，我Trudy来上班了.”
2. Trudy构造了多个和消息I含义相同的不同变体。如，=“我Trudy今天来上班了.”,=“我今天来上班了，我是Trudy.”于是乎，这些消息因为意义差不多，Alice都会签名。但是由于消息的值发生了变化，所以这么多消息的哈希值不同。
3. Trudy然后也构造出多个恶意消息E同含义不同形式的变体，,……
4. 对于,……和,……都实施哈希运算，企图找到一个碰撞使得h()=h().
5. 于是乎无害消息的Alice的数字签名是，这个数据是Trudy已经能得到的。而且它与有害消息的Alice的数字签名是的数值是一模一样的！于是，这就相当于Trudy最终获得了Alice对这条恶意消息E的数字签名，他成功了。
这就是哈希函数发生碰撞的后果！
6. 从计算而言，对于一生成n位二进制的哈希函数而言，必须要构造出个消息E和消息I才能一定找到碰撞。所以防止此类攻击的方法就是使得n足够大，以至于Trudy无法完成的哈希值的运算。
不过，n位二进制的哈希函数为什么需要个消息来发生碰撞呢？请看一个叫生日问题的例子。
4.2生日问题
一个高中排列组合问题：N个人中，存在2个人他们的生日是同一天的概率是多大？
答案是P=
令P=0.5，我们可以解出N=23.于是乎只要N大于23，就有超过一半的概率能找到2个同生日的人了。
为什么是23这个数量级的？因为不同人之间都要比较一次生日，于是乎N个人需要比较的次数为.而总共的可能性只有365个？所以，
既然如此，对于有N位二进制输出的哈希函数，有种情况。假如我们对大约个不同输入执行哈希运算，就有过半的概率能找到一次碰撞。所以说，hash函数虽然是存在碰撞，会被攻破，但是其实不存在捷径。你只能通过进行次哈希运算才能攻破。
4.3算法但不算法
哈希函数有很多种，最简单的有非加密的哈希，比如CRC校验。但是其易被攻击，不能用于加密。哈希函数都在追求一个特性，就是雪崩效应——输入值的微小变化也会引起输出的巨大变化。
可以用于加密的哈希，最有名的是MD5（Message Digest）,MD5前身是MD4，MD4前身是MD2，发明者是RSA的R，但是MD系列的早期算法都因为已经找到了碰撞而不再认为是安全的了。
而目前比较流行的是SHA-1（Safe Hash Algorithm），输出为160位长度。区块链中用得哈希算法就是它。SHA-1和MD5都以分组方式对消息实施哈希运算。
除此之外还有一个叫Tiger的不太有名但是比较结构化的哈希算法。
对于算法的具体内容，我们不展开，可以参考其他资料。
4.4应用
（1）数字签名.
如前所述。
（2）HMAC.
HMAC是MAC消息认证码的使用了哈希函数的版本。两者都是为了消息完整性。MAC就是采用CBC加密模式加密数据，然后丢弃最后一个分组之外的所有密文分组。这个最后的密文分组，即所谓的CBC剩余，起到MAC的作用。如果明文发生一丁点变化，MAC就会变化。计算所得到的消息的明文的MAC和该消息发送过来时附加的MAC就能知道数据是否完整。因为明文消息找那个的任何变化，几乎一定会传到最后一个分组。
但是HMAC其实和MAC大相径庭。其实应该就是叫MAC为CBCMAC，这样CBCMAC和HMAC我们就能一眼看出两者的区别了。
这里有一个问题，同样是涉及了消息和哈希，为什么要用HMAC，而不是直接用数字签名？因为，HMAC是用于对称加密的。而数字签名是非对称加密。如果你直接用密钥签名了，那因为是对称密钥，你的密钥其实就完全暴露了。
所以HMAC要解决的问题就是把密钥藏在MAC中但是不能被揭出来。比较蠢的方式是，将密钥K作为消息的一部分附加到消息中，然后对整个消息作hash运算：hash(K+M)或者hash(M+K)。但是这有捷径攻击，所以我们完全不能这样做了。
一种精妙的方法是：。（虽然我也不知道为什么精妙）。不过我可以看出来的是这里进行了2次哈希运算了。
总结一下：MAC/ HMAC/数字签名，都能用于保护消息的完整性，但是前两者用于对称加密，后者用于非对称加密。
这再一次证明了：任何能够用对称加密完成的任务也能用非对称加密实现，反之亦然。
5其他与加密相关的（2018-10-11）
5.1秘密共享
小时候我们常看到一些有关寻宝的故事，有一个宝藏，只有通过一张藏宝图才能找到它，但是藏宝图被分成几份，被不同的人所拥有。
在信息时代，这个宝藏就是信息——明文或者其他真实数字财产。而藏宝图就是密钥。而密钥如果被分成几份，就是秘密共享问题。这个概念由RSA中的S提出。
Alice和Bob想要共享一个秘密S。满足如下条件：（1）Alice和Bob单独无法确定S，只能瞎猜。（2）Alice和Bob在一起就能轻松确定S。
如何实际实现呢？其实只需要初中数学就行：两点确定一条直线。
把秘密做出一条直线，或者将秘密藏在直线中。给每个人一个点。于是2个人才能确定这一条直线。这个称为2 out of 2。而进行推广，m out of n，意思是一共有n个人，至少需要m个人合作才能恢复出这个秘密。
m out of n的实现机制也是两点确定一条直线的推广：次数为m-1的多项式被m个点唯一确定。这个设计被称为是决定安全的，似乎不会有比这个更好的方案了。
思考：其实这个秘密共享有点类似于区块链的分布式共识了。但是又有点不一样。
应用场景：视觉加密。所谓的视觉加密就是将一张图片分成2张，是一个2 out of 2的问题。其分开的办法是将每个像素按照一定的方式分开。大致如下图所示。其存在的问题是，图片合成以后，白色像素还是一半白一半黑。所以无法真正恢复出原图像。
5.2随机数
随机数在加密中很重要，比如RSA的密钥对是随机选取大素数生成的。但是加密技术中需要使用的随机数是需要真正随机的、不可预测的。而依靠软件是没有办法做到的。软件只能生成伪随机数。
这里有一个例子，就是网上打牌。事实上由于洗牌是靠软件的伪随机数，所以理论上势能完全知道每个人手里有什么牌的。但是有个问题是52张牌，是一个天文数字。但是如果用来生成伪随机数的种子数量有限，则实际牌的情况也不会超过种子数。比如种子若是32位的，则不会产生超过种牌况。
真正的随机数还是要靠硬件来产生。原理就是环境的不可预知的噪声。
5.3信息隐藏
信息隐藏类似于藏头诗。其应有一般有隐写术和数字水印等。
数字水印大致就是在正版文件里不令人注意的地方藏一些结构化信息，比如数字音乐里。水印有分类，鲁棒型和敏感型。鲁棒型就是随着盗版，水印不会消失，于是乎可以追踪盗版的源头。敏感型是被盗版后水印就会被破坏，防止盗版。
现在有的一种数字水印的设计方案有针对图像文件。图像的每一个像素都是(R,G,B)，比如(R,G,B)=(0x7E,0x52,0x90)，表示为##7E5290.如果只改变了RGB值的最后一位，则对图像影响不大。于是低位信息无关紧要，可以藏一些信息（可以是明文也可以是密文）到低位上。这有点类似于牺牲精度的感觉。
但是很明显这种方式是违背Kerckhoffs安全原则的。只要知道了原理，信息就被攻破了。于是乎，信息隐藏领域的基本问题就是找到一个遵守Kerckhoffs的设计方案。
