密码学认识(初识+迪菲赫尔曼秘钥交换)

在某些情况下，我们在沟通时，并不想让这个资讯让他人截获。比如男女主人公约会时，会说老地方见(除了他们俩，鬼知道老地方是哪里)；两个山寨头子第一次见面时，先对一下暗号，“天王盖地虎，宝塔镇河妖”等等。

于是自然而然就有了密码学最开始的状态。

两千年前，古罗马名将恺撒为了防止敌方截获情报，将罗马字母建立一张对应表，这样如果不知道密码本，即使截获一段信息也看不懂。
这种编码方式史称“恺撒密码”。

如对应表如下：

明文字母表：ABCDEFGHIJKLMNOPQRSTUVWXYZ
密文字母表：DEFGHIJKLMNOPQRSTUVWXYZABC

使用时，加密者查找明文字母表中需要加密的消息中的每一个字母所在位置，并且写下密文字母表中对应的字母。需要解密的人则根据事先已知的密钥反过来操作，得到原来的明文。例如：

明文：THE QUICK BROWN FOX JUMPS OVER THE LAZY DOG
密文：WKH TXLFN EURZQ IRA MXPSV RYHU WKH ODCB GRJ

但是这种简单的对照表，只要多截获一些一些情报，就可以破解出来。比如B字母出现的概率为4.5%，那么概率在其上下浮动的密文字母就很有可能指向B。

所以电视剧里面那些，根据一组数字，这些数字对应圣经/康熙字典的页码和位置的加密方式，是很容易通过统计学的方法破译出来的。

好的密码必须要做到，根据已知明文和密文的对应推断不出新的密文内容。即无法用统计的方式找到明文和密文之间的转换规律。

从数学的角度讲，加密的过程可以看做是一个函数的运算，解密的过程是反函数的运算。明码是自变量，密码是函数值。好的密码就是不应该通过一组自变量和函数值就能推导出函数。

密码的最高境界是，地方在截获密文后，对我方所知没有任何增加，用信息论的专业术语讲，就是信息量没有增加。

现代密码学基于信息论的理论基础，不只关注信息保密问题，还同时涉及信息完整性验证（消息验证码）、信息发布的不可抵赖性（数字签名）、以及在分布式计算中产生的来源于内部和外部的攻击的所有信息安全问题。

密码学主要有三个分支：哈希密码，对称密码，非对称密码。

又称对称秘钥算法，私钥加密，共享秘钥加密。
这类算法在加密和解密时使用相同的密钥，或是使用两个可以简单地相互推算的密钥。事实上，这组密钥成为在两个或多个成员间的共同秘密，以便维持专属的通信联系。

常用的对称加密算法有：DES、3DES、AES、Blowfish、IDEA、RC5、RC6

对称加密过程

M：明文
E：加密函数
K：秘钥
C：密文
D：解密函数

注：对称加密也分为很多的门派，有兴趣的同学可以看这篇博客

对称加密算法的优点是算法公开、计算量小、加密速度快、加密效率高。

对称加密算法的缺点是在数据传送前，发送方和接收方必须商定好秘钥，然后使双方都能保存好秘钥。其次如果一方的秘钥被泄露，那么加密信息也就不安全了。另外，每对用户每次使用对称加密算法时，都需要使用其他人不知道的独一秘钥，这会使得收、发双方所拥有的钥匙数量巨大，密钥管理成为双方的负担。

所以在远距离传输消息时，秘钥该如何交换呢？没有秘钥怎么加密？不加密怎么安全的传输秘钥？这是一个先有鸡还是先有蛋的问题。

那么该怎么解决这个难题呢？

在此之前，我们要先了解一下什么是单向函数。

单向函数wiki百科：对于每一个输入，函数值都容易计算（多项式时间），但是给出一个随机输入的函数值，算出原始输入却比较困难（无法在多项式时间内使用确定性图灵机计算）。
单向函数是否存在仍然是计算机科学中的一个开放性问题。

我们先假定，A色值混合B色值，可以得到C色值，但是只知道A和C，无法推导出B的色值，即这是一个单向函数。

1.甲、乙两个人约定一个公开的色值A
2.甲混合A、B色值，得到X，传给乙；乙混合A、C色值，得到Y，传给甲
3.这是甲得到Y，混合B得到Z；乙获得X，混合C同样可以获得Z。

这是一个比较简单的数学问题，即 :
A + B = X;
A + C = Y;
则： X + C = Y + B = A + B + C = Z;

而第三者可以获取的信息是 A、X、Y，根据单向函数的定义，无法反推出Z

这就是迪菲赫尔曼秘钥交换的原理所在，在数学上找到单向函数是主要突破点。

目前主流的方法，是使用离散对数作为单向函数。

离散对数：基于同余和原根的对数运算

离散对数至今没有比较好的办法去解决，使用穷举法的话，复杂度为 $O(2^n)$ ,n这里是群的大小的二进制表示的长度，也可以理解为key的二进制长度。如果用1024位的key,这个复杂度在目前的计算速度下基本可视作无法解决。
(天河二号运算速度3.39亿亿次/s)

所以我们会把离散对数问题认为是一个“很难”的问题，即它是一个单向函数。

迪菲赫尔曼秘钥交换通过单向函数的特性，给出了一种秘钥交换解决方案。

但是另一个问题又浮出水面了。如果我们全部使用对称加密的方式，那跟n个人聊天，就要保存n-1个秘钥，进行n-1次秘钥交换；而且一旦对方被突破，双方就都没有什么信息安全可言了。

非对称加密应运而生。具体请看我的下一篇博客。