通信安全笔记

密钥交换协议

DH(Diffie-Hellman)密钥交换

• 双方以协商方式确定共同的密钥，密钥无需在信道中直接传输，用于对称加密。

双方约定共同的底数g和质数p（非质数的破解难度会大大降低），并以各自的私钥a, b作为g的幂再用p取模发送给对方。对收到的内容再做同样的操作，双方可得相同的结果，即得共同的密钥。

原理：

\[(g^a \mod p)^b\mod p=(g^b \mod p)^a\mod p=g^{ab}\mod p\]

其中最后一项可由商乘除数与模的和的二项式展开得到。

举例：

取g=2, p=7, 甲私钥a=10, 乙私钥b=20。则甲发送2^10 mod 7=2, 乙发送2^20 mod 7=4；之后甲计算4^10 mod 7=4，乙计算2^20 mod 7=4，得共同密钥。

RSA(Rivest–Shamir–Adleman)

RSA是目前最主流的非对称加密算法。非对称加密由公私钥构成，实现互逆的加解密操作。私钥无需传递，且每位用户仅需存储他人公钥即可实现加密通信。缺点是现有算法计算量远大于对称加密，因此常用于交换对称密钥或对哈希值数字签名。

为理解RSA算法原理，先介绍两个定理。

费马小定理(Fermat’s little theorm)

• 自然数的质数幂与自身对该质数同余

\[\forall m\in \mathbb N,\quad p\in \mathbb P,\quad m^p-m\mod p=0\]

证明：

根据二项式展开/杨辉三角，可知质数幂的展开式中，除首末项的其他项的系数含质数的组合数，故

\[(m+1)^p-m^p-1\mod p=0\]

而

\[[(m+1)^p-m^p-1]+[m^p-m]=(m+1)^p-(m+1)\]

即当定理对m成立时，对m+1也成立。易知定理对m=0成立，则由数学归纳法可知定理成立。此定理可推广得欧拉定理。

中国剩余定理

又称韩信点兵、物不知数等。以例子说明。

有物不知其数，三三数之剩二，五五数之剩三，七七数之剩二。问物几何？

解法：

三人同行七十希，五树梅花廿一支，七子团圆正半月，除百零五便得知。

即取模3的余数乘70，取模5的余数乘21，取模7的余数乘15，再加上105的整数倍即为通解。

其原理为，由于3, 5, 7互质，可取5, 7的倍数中模3余1的数(70)，同理取另两数。这三个数可视为正交地产生了三个余数，再加上3, 5, 7的公倍数即得通解。

由此可得推论：若两数对两质数p, q同余，则它们对pq同余。

两数具有相同的通解形式，易证。

---

下面介绍RSA算法原理

• 取两质数p, q, 对任意自然数m，可取两自然数d, e, m的de次幂与m对pq同余。

\[\forall m \in \mathbb N,\quad\exists p, q \in \mathbb P,\quad d, e\in \mathbb N,\quad m^{de}\equiv m\mod pq\]

取

\[\begin{align} de&=(p-1)(q-1)+1\\ \Rightarrow m^{de}&=mm^{(p-1)(q-1)}\\ &=m(kp+1)=m(kq+1),\quad k\in \mathbb Z^+\\ &=m\mod pq \end{align}\]

其中(3)来自费马小定理，(4)来自中国剩余定理。

取e为密钥，则当且仅当e与(p-1)(q-1)互质时d存在（模逆元），作为公钥。

实际上e的取值可更灵活，但原理一致。

对m^e取pq的模后发送，收方计算d次幂再取模实现解密。发送时取模不改变结果，原理参见DH算法

举例：

取p=5, q=17, e=5, d=13, m=10. m^5%85=40, 40^13%85=10.

使发送方将中间人的公钥误认为目标的公钥，则中间人可获知发送的信息。

数字证书(Public key certificate)

数字证书用于证明公钥的真实性。其中包含公钥及相关信息，及公钥所有者的身份信息，及签发者(Certificate Authority)的数字签名（计算证书摘要并用私钥加密）。签发者的公钥还可由其他签发者签名，构成证书链。

认证时发送证书并验证签名实现对公钥可靠性的确认。

安全协议

安全协议用于在不安全的网络中安全地传输信息，功能包括认证，加密及保证数据的完整和不可否认。

SSH(Secure Shell)

SSH是一种网络安全协议，通过加密和认证机制实现安全的访问和文件传输等业务。SSH基于客户端-服务器模式运作。建立SSH连接时，先进行版本和算法协商，再交换用于加密此次会话内容的密钥，之后实现用户认证。用户认证可由密码或密钥方式实现。