密钥交换算法

① DH密钥交换（Diffie–Hellman key exchange）算法笔记

注意：只是个人理解，可能有不正确的地方
下文中 代表乘方运算，例如2 3=2 2 2=6，参考： http://zh.wikipedia.org/wiki/%E5%86%AA
%代表模运算，例如5%3=2，参考： http://zh.wikipedia.org/wiki/%E6%A8%A1%E9%99%A4
DH密钥交换算法的作用是使通信双方可以在不安全的通道中建立一个相同的密钥，用于加密通信。
基本原理示例：
1、通信方A和通信方B约定一个初始数g，g是公开的，如g=5
2、A生成一个随机数a，a是保密的，如a=6
3、A计算g a发送给B，g a=5^6
4、B生成一个随机数b，b是保密的，如b=15
5、B计算g b发送给A，g b=5^15
6、A接收到g b后，再使用保密的a，计算(g b) a=g (a b)=5^(6 15)
7、B接收到g a后，再使用保密的b，计算(g a) b=g (a b)=5^(6 15)
8、这样通信方A和B得到一个相同的“密钥”g (a*b)=5 (6 15)
整个通信过程中g、g a、g b是公开的，但由于g、a、b都是整数，通过g和g a得到a还是比较容易的，b也是如此，所以最终的“密钥”g (a b)还是可以被计算出来的。所以实际的过程还需要在基本原理上加入新的计算—— 模运算 ：
1、通信方A和通信方B约定一个初始数g，如g=5，一个质数p，如p=23，g和p是公开的
2、A生成一个随机数a，a是保密的，如a=6
3、A计算g a%p发送给B，g a%p=5^6%23=8
4、B生成一个随机数b，b是保密的，如b=15
5、B计算g b%p发送给A，g b%p=5^15%23=19
6、A接收到g b%p后，再使用保密的a，计算(g b%p) a%p=19 6%23=2
7、B接收到g a%p后，再使用保密的b，计算(g a%p) b%p=8 15%23=2
8、这样通信方A和B得到一个相同的密钥：2
(g b%p) a%p=(g a%p) b%p的证明：
如果a=2：
(g b%p) a%p=(g b%p) 2%p=(g b-n*p) 2%p=(g (2*b)-2*g b n p+(n p) 2)%p=g (2 b)%p
可以看出(g b-n*p) 2展开后除g (2*b)外，其它都是p的倍数，所以整个算式的结果是g (2 b)%p
同理对(g^b-n p) a展开后除g (a b)外，其它都是p的倍数，所以整个算式的结果是g^(a b)%p
同样可以得出(g a%p) b%p=g^(a b)%p
所以(g b%p) a%p=(g a%p) b%p
整个通信过程中g、p、g a%p、g b%p是公开的，这时通过g、p、g a%p得到a比较难，同样通过g、p、g b%p得到b比较难，所以最终的密钥是比较安全的。
以g=5、p=23、g^a%p=8计算a为例，a=log(5, (8+23 n))，这个只能将n的可能值逐个带入公式试验才能得到a的值。如果a、p是比较大的数那么计算更加困难。
如果注意的是，为了防止应用优化算法计算上述问题， 质数p不是随便选择 的，需要符合一定的条件。 随机数a、b的生成算法也必需注意 ，应使结果尽可能随机，不能出现可预测的规律，否则会使破解变的容易。
通过上述计算过程也可以看出DH算法不仅可以应用在2方通信的情况，如果 多方通信 ，也可以使用该算法。
DH密钥交换算法 无法验证对方身份 ，所以DH密钥交换算法 不能抵御中间人攻击 （MITM，Man-in-the-middle attack）。
参考：
wiki： http://en.wikipedia.org/wiki/Diffie%E2%80%93Hellman_key_exchange

原文链接: https://my.oschina.net/u/1382972/blog/330456

② 通信安全：哈希、加密、证书、签名、密钥协商、ECDH、TLS、DTLS

哈希也叫散列，是把任意长度的输入通过散列算法变换成固定长度的输出，该输出就是散列值，也叫摘要（Digest）。

这种转换是一种 压缩映射。 也就是，散列值的空间通常远小于输入的空间，不同的输入可能会散列成相同的输出，所以不可能从散列值来确定唯一的输入值，但如果输出的位数足够，不同输入散列成相同输出的概率非常非常小。

简单的说， 散列就是一种将任意长度的消息压缩到某一固定长度的消息摘要的过程 。

散列是不可逆的 ，也就是无法通过输出还原输入，此特性常被用于密码保存。

SHA-512、MD5等都是着名的散列函数，MD5生成的散列码是128位，甚至MD5就是哈希的同名词，你可以通过网站：https://passwordsgenerator.net/sha512-hash-generator/ 在线计算哈希。

散列有什么用？

加密就是把 明文变成密文的过程，解密就是反方向把密文变成明文 。

比如着名的 凯撒密码 ，就是把每个字对应到另一个，这样的话，只要有密码本，就能对照完成加解密。比如最简单的，对于英文26个字母，每个字母右移3个，abc变成def，这也是一种加密，当然这种加密很简单，很容易被破译。

而诸如AES（高级加密标准）、3DES（三重数据加密算法）则被公认为很难破解，不过山东大学女教授王小云很厉害，破解了MD5和SHA-1，迫使加密标准升级，最终当上了院士。

对称加密

对称加密就是加解密的密钥是一样的，优点是快，这也是传统的加密方式，像AES、3DES都是对称加密。

非对称加密

非对称加密用于加解密的密钥不一样，有2个密钥，公钥和私钥，公钥可以公开，私钥妥善保管。RSA、ECC（椭圆曲线加密算法）、DH（密钥交换算法）这些都是非对称加密。

非对称加密很慢，有多慢？相比对称加密慢1000倍，因为慢，所以它常用于密钥协商（Handshake），协商出会话密钥后，再用对称密钥加密通信数据。

1976年，Whitfield Diffie和Martin Hellman首次提出了非对称加密的概念，该算法被称为Diffie-Hellman密钥交换。然后在1978年，麻省理工学院的Ron Rivest，Adi Shamir和Leonard Adleman发表了RSA 算法。这些都可以被视为非对称加密的基础。

非对称加密也称为公钥基础结构，又称PKI。 非对称加密的提出是密码学上的一次革命，影响深远。

非对称加密算法用私钥加密，用公钥解密，或者用公钥加密，用私钥解密。

证书就是为了证明我是我，比如你要访问中国银行网站，但中行官网如何证明它是中行官网呢？答案就是数字证书。

CA是数字证书中心，服务器需要找CA做认证，让CA给自己颁布数字证书，数字证书内一般包含服务的一些信息、以及服务器的公钥，通过CA的私钥加密后，产生的数字证书，因为CA的权威性，且它的公钥天下皆知，所以，如果你能用CA的公钥解开证书，那便可证明该证书一定是CA颁发的，要不然它不会有CA的私钥，也便没法产生可用CA公钥解密的证书。

所以，由此可见，数字证书用到了非对称加密。

日常生活中也有签名，每个人的笔迹是不一样的，你刷卡消费后在账单签上大名，服务员校验过之后保存下来，你哪天赖账，便可以有签名为证，因为别人写的字跟你的笔迹终有差别。

那数字签名是什么呢？比如a发一封email，接收方怎么证明这封信是a写的？

本质上，数字签名也是利用了非对称加密。

前面讲了，非对称加密有公钥和私钥，如果发生方用私钥加密，然后接收方用发送方的公钥可以解密，那便可以证明是从某发送方发送的，因为别人拿不到你的私钥，也便无法用你的私钥加密，你不能抵赖。

数字签名通常先对内容算哈希，产生内容摘要，再用私钥加密，得到签名。

下面举一个例子来说明这几个问题：

张三有2把钥匙，一把公钥，公告天下，一把私钥，妥善保管，只有自己知道，很明显，非对称加密。

李四给张三写信，写完之后，用张三的公钥加密，通过邮局寄给张三，即使邮递员拆开信封看，他也看不懂，因为内容是密文，只有张三的密钥才能解密。

张三收到信后，用私钥解密，可以正常阅读。

现在张三要给李四回信，写完后，用hash函数生成摘要digest。

然后张三，再用私钥对摘要加密，生成数字签名signature。

然后把签名附在信的下面，一起发给李四。

过程是：信明文 -> hash -> digist -> 私钥加密 -> signature。

李四收到回信后，用张三的公钥对数字签名解密，得到摘要，由此证明，信确实是张三发出的，为什么？因为如果不是张三发的，那写信的人就没有张三私钥，用别的私钥加密得到的签名，是无法用张三的公钥解开的。

李四，再对信的内容做hash，得到摘要，与上一步得到的摘要对比，如果一致，则证明信的内容没有被修改过，信的内容是完整的。

复杂的情况出现了。

王五，用自己的公钥替换李四保存的张三的公钥，也就是王五欺骗了李四，李四误把王五的公钥当张三的公钥，这样一来，王五就能冒充张三给李四写信（王五用自己的私钥加密）。

问题是什么？问题是李四不能确信自己保存的公钥真的是张三的公钥。如果客户端电脑上存的工商银行官网的公钥，实际上是骗子公司的公钥，那就麻烦大了。

怎么破？让张三去认证中心CA（Certificate Authority），为公钥做认证，怎么做呢？CA中心用自己的私钥，对张三的公钥和其他相关信息一起加密，生成数字证书（Digital Certificate）。

张三拿到数字证书后，以后给李四回信，在签名的同时，附带上数字证书。

李四收到信之后，从CA的公钥解开数字证书，取出张三的公钥（一定是真的），然后就能放心的愉快的按之前的流程解开签名了。

数字证书加入后，核心区别就是张三的公钥不再保存在李四处，而是通过数字证书下发。

为什么数字证书里的张三的公钥一定是真的呢？因为CA是权威机构，假设全世界就一家（其实不止，但也不多），它的公钥天下尽知，就是固定的串，所以能用CA公钥解开的证书，一定是CA颁布的，因为CA用它的私钥加密产生的证书。很明显，非对称加密能用于证明我是我。

密钥交换算法

着名的DH密钥交换算法，这个算法很有意思，也很巧妙，简而言之，就是通信双方交换一点信息（不怕被偷看到），然后就在两端，分布产生出一个相同的密钥，神奇啊。

有一个很有意思的例子。

Alice和Bob要协商出一个公共的颜色，他们可以交换信息，但交换的信息，可以被偷看到，怎么办？既能协商出公共颜色，又不能让别人知道呢。

密钥交换算法的原理跟这个差不多，网上有大量的资料讲述这个问题，我觉得理解了上面的例子，再看ECDH便也不难了。

众所周知http是互联网协议，但是它不够安全，所以后面有改进版的https，其实就是多了一个TLS，这个是传输层加密，本质上，就是通过handshake，协商出一个会话密钥，后面的数据传递，都用这个密钥做对称加解密。

我们经常讲安全通道，其实也就是协商出一个会话密钥，他并不神秘。胡乱放几张图片吧。

为了减少这几个RTT，又想了各种办法，然后复用连接的话，就可以做到0RTT，1RTT了。

就说这些吧，最后抛几个名词，有兴趣自行网络学习：DTLS，HMAC，AEAD，重放攻击，放大攻击，是不是很高端？

③ 什么是dh算法

DH算法是一种密钥交换协议。

DH算法，全称为Diffie-Hellman密钥交换算法，是一种在公开网络上安全地生成共享密钥的协议。它是非对称加密算法的一种应用，由Whitfield Diffie和Martin Hellman在1976年提出。其核心思想是通过构造一个公开的共享密钥来确保在不安全的通信环境中，双方能够安全地建立一个共享的密钥，进而确保通信的安全性。这种算法广泛应用于网络通信中的密钥交换场景。

DH算法的工作原理如下：

DH算法基于离散对数运算的单向性特点来实现密钥交换。简单来说，离散对数是一种特殊的数学运算，它使得从一个数推算出其对应的原始数非常困难。在DH算法中，双方各自拥有一个私有密钥和公开密钥。算法通过特定的数学运算规则生成共享密钥，这个共享密钥由双方的公钥和私有密钥共同决定。这种密钥交换协议的特点是，即使通信双方在网络中是匿名的，也能安全地生成一个共享的密钥。由于这个密钥是由双方共同生成的，所以攻击者很难预测或窃取这个密钥。通过这种方式，DH算法保证了通信的安全性。

DH算法的应用场景：

DH算法广泛应用于各种需要安全通信的场景中，如网络上的数据加密传输、身份验证协议等。特别是在虚拟世界的场景中，网络通信的安全性和隐私保护至关重要。DH算法提供了一种有效的手段来确保通信双方在不安全的网络环境中安全地建立共享密钥，从而确保通信的安全性和隐私保护。此外，由于其强大的安全性表现，DH算法也被广泛应用于许多加密货币和区块链技术中，以确保交易的安全性和匿名性。

④ 简要介绍DH密钥交换算法

姓名：朱睿琦

学号：15180288015

参考：https://ke..com/item/Diffie-Hellman/9827194?fr=aladdin

http://blog.csdn.net/fw0124/article/details/8462373

【嵌牛导读】：随着互联网络的高速发展，计算机运算能力的提升，对信息的保密也有了更近一步的要求——不仅信息要保密，密钥也要保密。DH(Diffie-Hellman)算法就提供了使密钥安全通过不安全网络的方法。

【嵌牛鼻子】：DH算法，密钥，网络信息安全

【嵌牛提问】：DH算法是用来保护什么在网络中的通信安全？DH密钥交换的基本原理是什么？

【嵌牛正文】：(1)、算法描述

离散对数的概念：

原根 ：如果 a 是素数 p 的一个原根，那么数值：

a mod p ， a^ 2 mod p ，…， a^( p-1) mod p

是各不相同的整数，且以某种排列方式组成了从 1 到 p-1 的所有整数。

离散对数 ：如果对于一个整数 b 和素数 p 的一个原根 a ，可以找到一个唯一的指数 i ，使得：

b =（ a的i次方） mod p 其中 0 ≦ i ≦ p-1

那么指数 i 称为 b 的以 a 为基数的模p的离散对数。

Diffie-Hellman算法的有效性依赖于计算离散对数的难度，其含义是：当已知大素数 p 和它的一个原根 a 后，对给定的 b ，要计算 i ，被认为是很困难的，而给定 i 计算 b 却相对容易。

Diffie-Hellman算法：

假如用户A和用户B希望交换一个密钥。

取素数 p 和整数 a ， a 是 p 的一个原根，公开 a 和p。

A选择随机数XA< p ，并计算YA= a^ XA mod p。

B选择随机数XB< p ，并计算YB= a^ XB mod p。

每一方都将X保密而将Y公开让另一方得到。

A计算密钥的方式是：K=(YB) ^XA mod p

B计算密钥的方式是：K=(YA) ^XB mod p

证明：

(YB)^ XA mod p = ( a^ XB mod p )^ XA mod p

= ( a^ XB)^ XA mod p = ( a^ XA) ^XB mod p (<-- 密钥即为 a^(XA*XB) mod p )

=( a^ XA mod p )^ XB mod p = (YA) ^XB mod p

由于XA和XB是保密的，而第三方只有 p 、 a 、YB、YA可以利用，只有通过取离散对数来确定密钥，但对于大的素数 p ，计算离散对数是十分困难的。

例子：

假如用户Alice和用户Bob希望交换一个密钥。

取一个素数 p =97和97的一个原根 a =5。

Alice和Bob分别选择秘密密钥XA=36和XB=58，并计算各自的公开密钥：

YA= a^ XA mod p =5^36 mod 97=50

YB= a^ XB mod p =5^58 mod 97=44

Alice和Bob交换了公开密钥之后，计算共享密钥如下：

Alice：K=(YB) ^XA mod p =44^36 mod 97=75

Bob：K=(YA) ^XB mod p =50^58 mod 97=75

(2)、安全性

当然，为了使这个例子变得安全，必须使用非常大的XA, XB 以及 p ， 否则可以实验所有的可能取值。(总共有最多97个这样的值, 就算XA和XB很大也无济于事)。

如果 p 是一个至少 300 位的质数，并且XA和XB至少有100位长， 那么即使使用全人类所有的计算资源和当今最好的算法也不可能从a, p 和a^(XA*XB) mod p 中计算出 XA*XB。

这个问题就是着名的离散对数问题。注意g则不需要很大, 并且在一般的实践中通常是2或者5。

在最初的描述中，迪菲－赫尔曼密钥交换本身并没有提供通讯双方的身份验证服务，因此它很容易受到中间人攻击。

一个中间人在信道的中央进行两次迪菲－赫尔曼密钥交换，一次和Alice另一次和Bob，就能够成功的向Alice假装自己是Bob，反之亦然。

而攻击者可以解密（读取和存储）任何一个人的信息并重新加密信息，然后传递给另一个人。因此通常都需要一个能够验证通讯双方身份的机制来防止这类攻击。

有很多种安全身份验证解决方案使用到了迪菲－赫尔曼密钥交换。例如当Alice和Bob共有一个公钥基础设施时，他们可以将他们的返回密钥进行签名。