yjjnls/Notes

# 数字加密相关知识
- [数字加密相关知识](#%E6%95%B0%E5%AD%97%E5%8A%A0%E5%AF%86%E7%9B%B8%E5%85%B3%E7%9F%A5%E8%AF%86)
    - [非对称加密](#%E9%9D%9E%E5%AF%B9%E7%A7%B0%E5%8A%A0%E5%AF%86)
        - [椭圆曲线加密](#%E6%A4%AD%E5%9C%86%E6%9B%B2%E7%BA%BF%E5%8A%A0%E5%AF%86)
    - [公钥与私钥](#%E5%85%AC%E9%92%A5%E4%B8%8E%E7%A7%81%E9%92%A5)
    - [数字签名](#%E6%95%B0%E5%AD%97%E7%AD%BE%E5%90%8D)
    - [数字证书](#%E6%95%B0%E5%AD%97%E8%AF%81%E4%B9%A6)
    - [Merkle Tree](#merkle-tree)
- [Reference](#reference)


## 非对称加密

`对称加密`指加密和解密使用`相同密钥`的加密算法。它要求发送方和接收方在安全通信之前，商定一个密钥，泄漏密钥就意味着任何人都可以对他们发送或接收的消息解密。

每对用户每次使用对称加密算法时，都需要使用其他人不知道的惟一钥匙，这会使得发收信双方所拥有的钥匙数量呈几何级数增长，密钥管理成为用户的负担。同时，对称加密算法能够提供加密和认证却缺乏了签名功能，使得使用范围有所缩小。

具体算法：DES算法，3DES算法，TDEA算法，Blowfish算法，RC5算法，IDEA算法。

而`非对称加密`指加解密密钥不相关，典型如RSA、EIGamal、椭圆曲线算法。

### 椭圆曲线加密

公开密钥算法总是要基于一个数学上的难题。比如RSA 依据的是：给定两个素数p、q 很容易相乘得到n，而对n进行因式分解却相对困难。那椭圆曲线上有什么难题呢？

考虑如下等式：  

    K=kG  [其中 K,G为Ep(a,b)上的点，k为小于n（n是点G的阶）的整数]  

`不难发现，给定k和G，根据加法法则，计算K很容易；但给定K和G，求k就相对困难了。`  
这就是椭圆曲线加密算法采用的难题，我们把点G称为基点（base point）。  

现在我们描述一个利用椭圆曲线进行加密通信的过程：  

1.  用户A选定一条椭圆曲线Ep(a,b)，并取椭圆曲线上一点，作为基点G。
2.  用户A选择一个私有密钥k，并生成`公开密钥K=kG`。
3.  用户A将Ep(a,b)和点K，G传给用户B。
4.  用户B接到信息后 ，将待传输的明文编码到Ep(a,b)上一点M（编码方法很多，这里不作讨论），并产生一个随机整数r
5.  用户B计算点C1=M+rK；C2=rG。
6.  用户B将C1、C2传给用户A。
7.  用户A接到信息后，计算C1-kC2，结果就是点M。因为
    C1-kC2=M+rK-k(rG)=M+rK-r(kG)=M  
    再对点M进行解码就可以得到明文。

在这个加密通信中，如果有一个偷窥者H，他只能看到Ep(a,b)、K、G、C1、C2，`而通过K、G 求k 或通过C2、G求r 都是相对困难的`。因此，H无法得到A、B间传送的明文信息。

## 公钥与私钥

公开密钥与私有密钥是一对，如果用公开密钥对数据进行加密，只有用对应的私有密钥才能解密;如果用私有密钥对数据进行加密，那么只有用对应的公开密钥才能解密。  
通过公钥是无法（或极其困难）推算出私钥的。**注意这里公钥与私钥都可以用来加密，只是私钥是自己保存，而公钥是公开的。**

比如A发信息给B，就用B的公钥加密信息，然后发给B，B用自己的私钥解密，就可以看到信息内容。

## 数字签名

A把要加密的内容用hash函数生成摘要digest，再用自己的私钥对digest加密，生成数字签名signature。连同加密的内容一起发给B。  

B收到后，对**摘要（用A的公钥解密）**和**内容（用自己的私钥解密）** 都解密，再对内容使用相同hash，看得到的digest是否相同，相同，说明发送的内容没有被修改。  

同时，用A的公钥对digest进行解密还能验证这是不是A发来的内容，但是这里有个潜在的问题。  
>**如果B存储的A的公钥被C替换成了C的公钥，那么C就可以冒充A和B进行通信，而B却完全不知道。**

## 数字证书

证书中心用自己的私钥对`A的公钥和一些相关信息`一起加密，形成`数字证书`。  
A在发送内容的同时，在数字签名后再附上数字证书。  
B收到后，先用CA的公钥解密数字证书，得到A真正的公钥，再用A的公钥来验证签名是否是A的签名。  

B可以每次都到CA的网站上（或者什么别的官方途径）获得CA的公钥。

这么做的目的是为了验证：
1. 确认该信息确实是A所发；
2. 确认A发出的信息是完整的。

*  **公钥防泄漏,私钥防篡改**  
    *  B收到后，只有用B自己的私钥才能解密内容，别人是无法解密的。`防泄漏`  
    *  再用上述数字证书来验证数字签名是否来自A，发送内容有没有被篡改。`防篡改`  
数字证书一般挂靠在可信任的机构，无法篡改和伪造。

## Merkle Tree

默克尔树，又叫哈希树，由一个root节点，一组中间节点和一组叶节点组成。  
叶节点包含存储数据或者其哈希值，中间节点和root节点都是其孩子的hash值。  

![markle tree](./img/markle%20tree.jpg)

应用：
1\.  快速比较数据，两个默克尔树的根节点相同，那么其所代表的数据必然相同
2\.  快速定位修改，比如上面D1数据被修改，可通过root->N4->N1，快速定位到发生改变的D1
3\.  零知识证明，比如要证明某个数据中包含D0，那就构造一个默克尔树，公开root、N4、N1、N0，D0拥有者可以检测到D0存在，但不知道其他内容。（D0拥有者可以看到hash值，但看不到完整的数据内容）


# Reference
1. [数字签名是什么？](http://www.ruanyifeng.com/blog/2011/08/what_is_a_digital_signature.html)
2. [比特币背后的密码学原理](https://www.jianshu.com/p/225ff9439132)