区块链技术在社区疯狂讨论，掀起一番技术浪潮，挖矿，去中心化等在社区一直被讨论着，在这里了解一下区块链是如何工作的，已经涉及到的密码学知识。
挖矿
比特币是通过“挖矿”凭空产生的，挖矿就是不停地做hash计算，当找到某个值刚好满足条件，就算挖出矿了， 就会得到一部分比特币作为奖励。
最早的时候大家用CPU挖矿，后来发现GPU会快很多，最后干脆有人把hash算法集成到了芯片上（即ASIC，Application-specific integrated circuit），算力再次暴涨。
hash
hash函数具有如下一些性质
- 输入是任意长度，输出为固定长度（比如256bits）
- 计算起来很高效
- 输入改动一点点（哪怕只是一个bit），输出结果千差万别（血奔效应）
常用的Hash函数有MD5， SHA1， SHA256等。
hash函数三个特征
- Collision Free
- Hiding
- Puzzle Friendly
Collision Free
没有人能够找到两个不同的输入， 它们的hash输出是相同的， 即不能找到x != y但是H(x) == H(y)。
注意， 我们这里说的是“没有人能够找到”，而不是说不存在！大家仔细想想就会知道， 冲突（Collision）肯定是存在的。 为啥呢？因为我们说了输出是固定长度的， 比如256bits，那么输出空间大小就只有Math.pow(2, 256)种可能。而输入可以是任意长度，那输入空间远比输出空间要大。
如果说存在冲突的话，那hash不就有问题了么，这里我们必须认识到，冲突是必然存在，但是凭借现在计算机的算力，找到冲突实在是太长太长了，引用一句话：
把全人类从古自今曾经造出来过的电脑都拿来从宇宙一开始就计算，那么到今天为止找到冲突的概率依然很小很小， 有多小呢？比接下来的两秒钟地球被一块大流星撞毁的概率还小， 而这件事。。。。。。。（2s过去）。。。。并没有发生。
这两年hash算力有这么大的提升， 完全是由于比特币大涨， 人们为了在挖矿中占据优势， 开发了大量ASIC。我们之前说一个蚂蚁矿机S9的算力是13.5Thash/s， 而我的mac pro大概是2Mhash/s， 也就是一台S9在计算hash方面，相当于13.5T / 2M ~= 6.7M，670万台Mac Pro！
没有任何hash函数被“证明”是Collision Free的。只是有些hash函数人们花了大量时间去找， 但是还没有找到，所以暂时认为是collision free的，而有些曾经认为是collision free的hash函数被找到有效构造冲突的方法了，比如MD5，因此在安全性要求较高的场景就建议不再使用MD5了。比特币里使用的是sha256。
应用案例：消息摘要Message digests
Hash函数的输出， 可以作为信息摘要。
我们说“没有人能够”找到x != y使得H(x) == H(y)， 反过来也就是只要H(x) == H(y)，我们就可以认为x == y的。这样我们要比较两个文件是否一致， 不管这两个文件有多大， 我们只需要比较他们的hash输出即可，而hash输出只有256bits，比较非常快。
有个典型的应用是网盘的“秒传”功能。
文件摘要还有一个用处是验证下载的文件是否完整没有被篡改过。
Hiding
hash函数满足这样的性质：知道H(x)，不可能推算出x。
如果我们从一个满足high min-entropy的概率分布中选出一个秘密的值r， 则如果知道H(r || x)的情况下不能推算出x， 则我们说H函数满足Hiding性质。
high min-entropy大概意思是从一个很大的空间中随机选择一个值，每个值的概率基本是一样的。
拼接一个从很大空间中选出来的secret值r的目的就是为了让r || x的取值范围变得很大， 目的跟密码加盐再做hash差不多。
应用案例：承诺Commitments
我们来做一个游戏， 我想一个0-9的数， 你来猜， 猜对算赢。如果我只是“想”一个数的话， 你永远赢不了，因为哪怕你猜对了，我也可以说我想的是另外一个数。
因为我们可以找一个满足Collision Free和Hiding性质的函数H， 我想一个数字x， 然后把H(x)发出来给大家看到， 因为我们说H具有Collision Free性质， 所以我不可能事后说我写的数字其实是x1， 因为我找不到满足x1 != x并且H(x1) == H(x)的数字，所以我不能抵赖。但是你是可以把0-9都用H计算一遍， 然后跟H(x)对比，就能知道我想的x是多少了。
所以我还需要随机选择一个256bits的key， 然后把H(key || x)发出来，因为key的选择空间是Math.pow(2, 256)，你不可能去遍历所有可能的key来暴力计算所有的H(key || x)，因此就没办法知道key || x，也就没办法知道x了。同样，我还是不可能找到另一个不同的key1，使得key1 != key但是H(key1 || x) == H(key || x)的。这样就保证了我既不能抵赖，你也不能推算出x，对于你猜的数字y，只要事后我把key发出来，计算H(key || x)和H(key || y)，如果两者相等， 则认为x == y， 反之亦然。
Puzzle Friendly
对于n-bit的输出y，如果k是从一个high min-entropy的分布中选出来的，如果不可能在远小于Math.pow(2, n)的时间中找到x使得H(k || x) == y， 则我们说H具有Puzzle friendliness性质。
这个性质是说， 要想找到x， 使得H(k || x) == y， 没什么办法比随机乱猜更有效！
密码学
凯撒密码
将字母表依次往后移动几个位置。具体移动的数量n就是密钥了。
凯撒密码有个问题就是很容易破解， 因为总共只有26种可能（移动27个位置， 跟移动1个位置是一样的），很容易就暴力破解了。
简单替换
凯撒密码简单很容易破解， 原因是因为密钥空间（密钥的可选择范围）太小了， 因为当我们把A映射到B的时候， 其他字母的映射关系就全部决定好了。后来出现了一种变种， 可以任意指定字母之间的映射关系
我们可以知道这种加密方式的密码空间是26! = 4.0329146112660565e+26，这么巨大的密钥空间， 如果暴力破解的话是不实际的。
但是这种加密方式有一个问题， 就是同一个明文字符总是加密成同一个密文字符，比如把A替换成D，则所有的A都会替换成D。 于是出现了一种叫做频率分析的破解方法。 大概原理是：正常的语言中， 每个字符出现的频率是不一样的， 可以统计一下明文中的字符出现次数， 假设最高频的是A，再统计一下密文中最高频的字符，假设是D，则很有可能密文中的D是对应明文A。 一层层分析，就能实际破解这种加密方式了。
对称加密
对称加密就是加密密钥和解密密钥是一样的， 比如我们前面说的几种加密方式都是对称密钥。
因为所有的明文信息我们都能编码成二进制比特， 也就可以等价的转化成一个数字， 所以我们后面讲解的时候， 明文全部用一个数表示即可， 大家应该知道，这个数可以是对应一段文本， 也可以是一部电影。
对称加密主要有DES和AES。 目前DES已经不安全了，不建议使用。 1997年NIST（美国标准技术研究所）公开募集AES（Advanced Encryption Standard）算法， 全世界很多密码学家投递了很多算法， 最后经过各种严格的筛选， 最后于2000年10月2日， Rijndael算法获胜，被选为NIST的AES标准。NIST当时公开选拔AES的时候设定了条件：被选为AES的密码算法必须无条件地免费提供给全世界使用。正是这样， 我们现在才能免费使用AES。
说到这里很多人可能会说我自己也可以设计一个算法， 不要让别人知道就行了啊。 这种做法叫隐蔽式安全性(security by obscurity)，只是在一厢情愿地以为别人不能破解而已， 其实并没有经过真正的检验。要知道像AES这样通过竞争来实现的标准， 都是发动了全世界的密码学家去设计、尝试破解，最后得到一个很多专家都觉得安全的算法。 自己实现“秘密算法”，就好比为了锁门， 不是去买一个品牌商家的锁， 而是自己系一根绳子把门拴起来一样。
非对称加密
加密有一个很大的弊端， 那就是加密和解密必须是用同一个密钥。 那么问题来了， 怎么把密钥安全地交给接收方呢？ 显然， 用对称加密方法是没办法通过线上传递密钥的。 办法就是发送者和接受者线下碰头，当面商量好密钥。
后来密码学家们发明了非对称加密， 即加密密钥（也叫公钥， public key， 简写为pk）和解密密钥（也叫私钥， secret key， 简写为sk）不一样。
假设Alice要给Bob通信， 则通信过程变成了这样：
Alice: Bob我要给你说话， 你把公钥pk发给我。
Bob: 好的， 这是我的公钥pk。
Alice: 这是我用公钥加密后的内容pk(x)。
Bob: 我用sk解密看看， 哦， sk(pk(x))解密出来是x啊。
... 如果Bob要和Alice说话，同样需要得到对方的公钥
你可能发现了，公钥是可以在网络上传播的，用公钥加密的内容pk(x)只能用私钥解密， 即sk(pk(x)) === x。
广泛使用的非对称加密方法有RSA。
一般说来非对称加密算法比对称加密算法慢很多，可能有几百倍， 因此我们一般将对称加密算法和非对称加密算法联合起来一起使用。即用非对称加密算法先协商出对称加密的密钥， 然后用对称加密算法去传递信息。 因为密钥（可能就几百字节）相比信息本身（可能几百兆甚至更大）要小很多， 所以这种混合加密方式综合了两者优点。
由于用pk加密的内容，能用sk解密， 因此非对称加密算法还可以用于数字签名。A答应了B一件事情x， 则可以要求A用他的私钥sk对x进行加密， 得到sk(x)然后和x一起发送出来。 因为公钥是可以公开的， 任何人都可以拿到， 因此大家都可以用公钥pk去验证A的签名， 即只需要pk(sk(x)) === x既可以认为x这件事情是A说的。 因为没有人知道A的私钥sk， 所以不可能有其他人能编造出x和sk(x)，使得刚好pk(sk(x)) === x的。 对应到比特币里， x这件事可能就是“将pk地址（比特币地址是公钥pk取两次hash）里的钱转10块到pk1地址”， 然后附带上sk(x)， 则网络上其他节点会验证一下pk(sk(x)) === x， 如果为真， 则说明x这条转账记录是这笔钱的主人说的， 否则就拒绝这笔交易。
认证
非对称加密解决了对称加密的密码配送难题， 但是依然不能解决中间人攻击。所谓中间人攻击，是指第三方攻击者对Alice伪装成Bob， 对Bob伪装成Alice。
似乎又遇到了公钥配送的问题。解决方法是找一个可信的中间机构T， Bob将自己的公钥pkb发送给T， T用自己的私钥skt对B的公钥pkb进行签名skt(pkb)， 这样Alice收到B的公钥pkb，以及认证机构T的签名skt(pkb)，只需要用认证机构T的公钥pkt验证一下pkt(skt(pb)) === pkb是否为真即可， 为真则说明“Bob”提供的公钥真的是Bob的公钥。这样的中间机构T我们一般叫做CA，即Certification Authority。
可是这样中间人还是可以攻击啊，冒充中间机构不就好了，事情发展到这里，问题好像陷入了死胡同，没法解决了。这里涉及到公钥基础设施(Public-Key Infrastructure， 简写PKI)，有兴趣的可以深入了解。
我们也是可以自己导入证书到系统里面去的。 比如我们想抓包分析一个APP的接口， 如果APP跟服务端是用的https连接， 我们哪怕抓到包看到的也是乱码， 这时候可以把抓包工具（比如charles）的证书导入到系统里面，则这个抓包工具就可以发动“中间人攻击”，破解抓到的包了。