密码学基础知识

密码学算法主要分为两种：对称加密和非对称加密。

对称加密就是使用了一样的密钥来加密，需要在只有通信的双方知道密钥的情况下才安全。

非对称加密

在非对称加密算法中，有公钥和私钥两种密钥，其中，公钥是公开的，不需要保密，私钥由个人持有，必须妥善保管和注意保密。加密和解密使用两种不同的密钥，用公钥加密，只有私钥能解密，用私钥加密，只有公钥能加密。RSA就是一种常见的，应用很广的非对称加密算法。

加密解密

A往B发送消息，A用B的公钥把消息加密，只有B的私钥能解密。然后A把加密后的消息发送给B，B用自己的私钥解密就能看到了，途中没有别人可以破解消息，因为别人只有B的公钥。然后B用自己的私钥加密消息，回复给A，A用B的公钥解密读取回复。

但是这样真的安全吗？如果传输过程中消息被人修改了怎么办？如果A加密使用的公钥不一定是B的公钥呢，只是他以为是B的公钥。

数字签名和数字证书

上面的问题可以用数字签名和数字证书解决。

数字签名可以解决消息被人修改的问题，数字签名是一个hash算法，A把要发送的消息通过hash算法计算出一个hash值，当做摘要，和消息一起传送，B把消息hash之后得到另一个摘要，是否和A传送过来的摘要相同。如果担心消息和hash摘要都被修改，可以把hash摘要用B的公钥加密，就不怕别人改了。

数字证书可以解决这个公钥是不是B的公钥，数字证书通过权威机构-证书管理机构发放的证书，如同现实中的身份证一样，是证明这个公钥是某人的，数字证书会把这个人的公钥，姓名，证书机构名称，有效期放在一起。

这样A就可以先请求B的公钥，然后B把数字证书给A看，就证明这个是B的公钥，A再拿这个B的公钥去发送消息。但是证书也可以伪造，中途被拦截了，修改成C的公钥，以及B的名字，这怎么办呢？

所以在证书机构办颁发证书的时候，会用数字签名给证书内容做个摘要，然后用机构的私钥加密这个摘要，这样就不怕别人篡改造假证书了。

现在的https协议就是基于非对称加密技术的，首先客户端往服务器发起加密请求，于是服务器会用自己的私钥加密网页，然后连同自己的数字证书（这个证书里包含证书颁发机构做的签名），然后客户端浏览器会查看操作系统认证的受信任的证书颁发机构查找公钥，验证证书是否被篡改，如果被篡改会发出警告。如果查找不到受信任的证书颁发机构，浏览器也会发出警告。

RSA

RSA是最流行的非对称加密技术，只要加密的越长，就越难以破解，因为没有可靠的破解方法。RSA的核心是欧拉定理，证明在之后给出。

RSA的过程可以参考博客RSA算法

中国剩余定理参考David Lin的回答 - 知乎

扩展欧几里德伪代码（手写未测试）:

void exgcd(int a, int b, int d, int x, int y){
    if(b == 0){
        d=a;
        x=1;
        y=0;
    }
    else{
        exgcd(b, a%b, d, x, y);
        int k = x;
        x = y;
        y = k - a/b*y;
    }
}

密码学哈希

密码学哈希算法主要是有MD5，以及SHA等算法，特点是不可逆以及没有 冲突（冲突概率极小），和普通的哈希算法很类似，和内存中的哈希表不同。

吐槽

简书不支持mathjax真是太糟糕了，没有打公式的欲望。