RSA and SSH

RSA加密算法详解

简介

RSA加密算法是1977年由Ron Rivest、Adi Shamir和Leonard Adleman共同提出的一种非对称加密算法，算法名称取自三位发明者姓氏的首字母。RSA是目前应用最广泛的公钥密码体制，广泛用于数字签名、密钥交换和数据加密等领域。

非对称加密是指加密者与解密者使用的是不同的密钥，反之对称加密是指加密者和解密者使用相同的密钥。对称加密要求加密者和解密者共同事先约定好密钥，但在网络上进行这个过程保证不泄密存在一定难度，这就是选择非对称加密的原因。

RSA算法的安全性基于大整数分解的困难性，即对于两个大素数的乘积，要分解出这两个素数在计算上是困难的。

算法原理

密钥生成

RSA密钥生成过程包括以下步骤：

选择两个大素数 p 和 q，通常长度为512位或更长。
计算模数 n = p × q
计算欧拉函数 φ(n) = φ(p)φ(q) = (p-1)(q-1)
选择公钥指数 e，一个素数满足 1 < e < φ(n) 且 gcd(e, φ(n)) = 1
计算私钥指数 d，满足 ed ≡ 1 (mod φ(n))

获得公钥为 (n, e)，私钥为 (n, d)。

加密和解密

将所要传递的消息按照双方约定好的格式转换为一个小于n的整数m (若消息太长可以分为多段)。

加密： 对每段消息m使用公钥(n, e)加密。

\[c = m^e \pmod{n}\]

解密： 对每段消息m使用公钥(n, e)加密。

\[m = c^d \pmod{n}\]

数学正确性证明

Theory： $(m^e)^d \equiv m \pmod{n}$

我们需要证明对于任意整数m，当p和q为不同素数，且e 和d为满足$ed \equiv 1 \pmod{\lambda(pq)}$ 的正整数时，有：

\[(m^e)^d \equiv m \pmod{pq}\]

根据Carmichael函数的定义，存在非负整数h和k，使得：

\[ed - 1 = h(p-1) = k(q-1)\]

为了证明 $(m^e)^d \equiv m \pmod{pq}$

根据中国剩余定理（CRT），只需分别证明：

\[(m^e)^d \equiv m \pmod{p}\] \[(m^e)^d \equiv m \pmod{q}\]

由于p和q是不同素数，若上述两个同余成立，则：

\[(m^e)^d \equiv m \pmod{pq}\]

模p的证明分两种情况讨论：

若m是p的倍数，等号两侧均为均为p的倍数。因此：
\[m^{ed} \equiv 0 \equiv m \pmod{p}\]
若m不是p的倍数，根据费马小定理，对于与p互质的m，有
\[\ m^{p-1} \equiv 1 \pmod{p} \\]
由于$ed - 1 = h(p-1) = k(q-1)$
我们得到：
\[m^{ed} = m^{ed-1} \cdot m = m^{h(p-1)} \cdot m = (m^{p-1})^h \cdot m\]
代入费马小定理 ( m^{p-1} \equiv 1 \pmod{p} )，有：
\[(m^{p-1})^h \equiv 1^h \equiv 1 \pmod{p}\]
因此：
\[m^{ed} \equiv 1 \cdot m \equiv m \pmod{p}\]

综合两种情况，均有：

\[m^{ed} \equiv m \pmod{p}\]

模q的证明同理。

根据中国剩余定理，存在唯一解使得：

\[(m^e)^d = m^{ed} \equiv m \pmod{pq}\]

证明完毕。

主要攻击方案与安全性分析

1. 小公钥指数攻击（低加密指数攻击）

当公钥指数 e 很小（如 e = 3）且明文 m 相对n也较小时，可能存在安全风险。

攻击原理：
攻击者可以直接计算：

\[c = m^e \pmod{n}\] \[m^e = c + kn\] \[m = (c+kn)^{1/e}\]

上述情况中，k就比较小，攻击者可以从小到大枚举k，依次开方直至开出整数为止。

明文长度与攻击的关系

假设明文 m 和模数 n 位数相同（如 2048 位，约 600 十进制位），即使 e = 3，计算暴力枚举复杂度极高（指数级），理论上不可行。但问题在于，实际明文往往远短于 n，例如一条短消息（如 128 位）。若直接加密短明，攻击者可轻松计算立方根。此外，短明文可能具有可预测的结构（如固定格式的协议消息），进一步降低攻击难度。

填充的作用

填充（Padding）通过在明文 m 前添加随机数据或结构化数据，使其长度接近或等于 n 的位数，并增加随机性，从而防止小公钥指数攻击。RSA 常用的填充模式包括：

RSA_PKCS1_PADDING：在明文前添加随机字节，确保总长度接近 n，并包含固定分隔符以验证解密正确性。
RSA_PKCS1_OAEP_PADDING：基于最优非对称加密填充OAEP，结合随机种子和哈希函数，生成高度随机的填充数据，安全性更高。
RSA_NO_PADDING：无填充，直接加密原始明文，极易受到小公钥指数攻击。

填充的具体作用如下：

增加明文长度：
填充使明文 m 的有效值接近或超过 n。
引入随机性：
填充（如 OAEP）通过随机种子和哈希函数使每次加密的 m 不同，即使原始消息相同，密文 c 也各异。这破坏了攻击者利用密文确定性（如预计算表）的可能性。
防止确定性攻击：
无填充（RSA_NO_PADDING）的明文若结构固定（如协议头），攻击者可通过选择明文攻击构建密文-明文对。填充引入的随机性和结构（如 OAEP 的哈希校验）使此类攻击失效。

块加密与填充

当明文长度超过 n 的位数时，需将其分割为多个块，每个块长度小于 n，分别填充后加密，称为块加密。这类似于对称加密的分组加密，但 RSA 的块加密仍是非对称加密。例如，2048 位模数 n 限制单块明文小于 2048 位，填充（如 OAEP）确保每块长度接近 n 且随机化。

结论

小公钥指数攻击的根源在于明文 m 过短或缺乏随机性，导致 m^e 不触发模运算或易于猜测。填充方案（如 RSA_PKCS1_OAEP_PADDING）通过拉长明文长度、引入随机性和验证结构，有效防止此类攻击。即使使用 e = 3，只要正确实施填充，RSA 加密仍可保持安全。然而，e = 65537 是更推荐的选择，因为它在效率和安全性之间取得了更好平衡，且在实践中已成为标准。

2. 共模攻击 (Common Modulus Attack)

当两个用户使用相同的模数 n 但不同的公钥指数 e_1 和 e_2 时，如果 gcd(e_1, e_2) = 1，攻击者可以在不知道私钥的情况下解密消息。

攻击过程：

设同一明文 m 被两个公钥加密：

$c_1 \equiv m^{e_1} \pmod{n}$ $c_2 \equiv m^{e_2} \pmod{n}$

如果 gcd(e_1, e_2) = 1，则存在整数 s 和 t （可以为负数，此时取逆元）使得：

\[s e_1 + t e_2 = 1\]

攻击者可以计算：

\[m \equiv c_1^s \cdot c_2^t \pmod{n}\]

数学证明：

\[c_1^s \cdot c_2^t \equiv (m^{e_1})^s \cdot (m^{e_2})^t \equiv m^{s e_1 + t e_2} \equiv m^1 \equiv m \pmod{n}\]

3. 广播攻击 (Håstad Broadcast Attack)

当使用小的公钥指数（通常 e = 3）向多个接收者发送相同消息时，攻击者可以利用中国剩余定理恢复明文。

攻击条件：

使用相同的小指数 e。
向至少 e 个不同的接收者发送相同消息。
各接收者使用不同的模数。

攻击过程：

设明文 m 被发送给 e 个接收者，得到密文：

$c_1 \equiv m^e \pmod{n_1}$ $c_2 \equiv m^e \pmod{n_2}$ $\vdots$ $c_e \equiv m^e \pmod{n_e}$

如果各模数互质，使用中国剩余定理可以求出：

\[x \equiv m^e \pmod{n_1 n_2 \cdots n_e}\]

因此可以枚举k来破解：

\[m = (x+kn_1 n_2 \cdots n_e)^{1/e}\]

4. 量子计算威胁

Shor 算法

Peter Shor 在 1994 年提出了一种量子算法，能够在多项式时间内分解大整数，这对 RSA 构成了根本性威胁。

算法原理：

将整数分解问题转化为寻找函数 f(x) = a^x mod n 的周期。
使用量子傅里叶变换找到周期 r。
如果 r 是偶数且
\[a^{r/2} \not\equiv -1 \pmod{n}\]
则 $gcd(a^{r/2} \pm 1, n)$ 给出 n 的非平凡因子。

时间复杂度：O((log n)^3)

虽然 Shor 算法在理论上可以破解 RSA，但目前的量子计算机还无法处理实际使用的 RSA 密钥长度。然而，随着量子计算技术的发展，这种威胁正在变得越来越现实。

总结

RSA算法作为最重要的公钥密码算法之一，在信息安全领域发挥着关键作用。虽然面临着各种攻击威胁，特别是量子计算的挑战，但通过合理的参数选择和安全实现，RSA仍然是当前最可靠的加密方案之一。随着后量子密码学的发展，未来可能需要新的算法来替代RSA。

参考文献

SSH技术解析

什么是 SSH？

SSH（Secure Shell）是一种加密的网络协议，用于在不安全的网络环境中实现计算机之间的安全通信和文件传输。它通过加密技术保障数据传输的安全性，广泛应用于远程登录、文件传输和端口转发等场景。SSH 的出现解决了早期互联网明文传输带来的安全隐患，为用户和服务器之间的通信提供了可靠的保护。

SSH 的起源

SSH 由芬兰学者 Tatu Ylönen 于 1995 年开发，最初版本为 SSH-1，旨在通过加密登录信息和传输内容来确保通信安全。Tatu Ylönen 将代码免费发布，引发了全球开发者的广泛关注和使用。随后，SSH协议不断演进，支持多种加密算法，并衍生出多种实现，其中由 OpenBSD 项目开发的 OpenSSH 是最流行的开源实现。你可以通过 OpenSSH 官方网站或 GitHub 仓库获取更多信息。

现今，OpenSSH 已内置于大多数 Linux 发行版中，Windows 从 Windows 10 版本 1809 起也默认支持 SSH。可以通过以下命令检查系统中是否安装了 SSH：

$ ssh

SSH 的工作原理

SSH 的核心在于通过加密算法保护数据传输安全，主要采用以下两种加密方式：

1. 对称加密

对称加密使用单一密钥在客户端（Client）和服务器（Server）之间加密和解密数据。SSH 的会话密钥即采用对称加密，因其加解密速度快，适合传输大量数据。然而，密钥需要在客户端和服务器之间共享，若密钥泄露，可能导致安全风险。

2. 非对称加密

非对称加密使用一对密钥：公钥和私钥。公钥用于加密数据，私钥用于解密。SSH 在用户认证阶段主要依赖非对称加密，其流程如下：

密码登录流程：
- 客户端发起 SSH 连接请求（不含密码）。
- 服务器发送公钥给客户端。
- 客户端使用公钥加密密码并发送回服务器。
- 服务器使用私钥解密，验证密码是否匹配。
- 服务器返回验证结果。
公钥登录流程（免密登录）：
- 客户端将公钥预存到服务器的 ~/.ssh/authorized_keys 文件中。
- 客户端发起登录请求。
- 服务器生成随机数 R，用客户端公钥加密后发送。
- 客户端用私钥解密 R，结合会话密钥生成摘要 Digest1 并发送。
- 服务器生成摘要 Digest2，与 Digest1 比对，验证通过后允许登录。

非对称加密的优点是私钥无需在网络中传输，安全性更高，公钥登录方式也免去了频繁输入密码的麻烦。

SSH 入门指南

基本登录

要通过 SSH 登录远程主机，只需以下命令：

$ ssh User@Host

User：远程主机的用户名。
Host：远程主机的 IP 地址或域名。

若用户名与本地相同，可省略 User@ 部分：

$ ssh Host

默认端口为 22，若需指定其他端口，可使用 -p 参数：

$ ssh -p 12345 User@Host

首次连接时，系统会提示主机真实性未验证，要求用户确认公钥指纹：

The authenticity of host '8.8.8.8 (8.8.8.8)' can't be established.
ECDSA key fingerprint is SHA256:/h8m94SK4xPttR+W5wZi+rQC8Dq3Rs6XSDhlzIKREI4.
Are you sure you want to continue connecting (yes/no/[fingerprint])?

输入 yes 后，SSH 会将主机公钥保存至 ~/.ssh/known_hosts，后续连接将自动识别。

密码登录

若未配置公钥登录，系统会提示输入密码：

Password:

输入正确密码即可登录。

公钥登录

公钥登录需先生成密钥对并将公钥上传至服务器：

生成密钥对：
1 $ ssh-keygen
默认生成 RSA 密钥对，存储在 ~/.ssh/id_rsa（私钥）和 ~/.ssh/id_rsa.pub（公钥）。可通过 -t 和 -b 参数指定算法和密钥长度：
1 $ ssh-keygen -t ecdsa -b 384

上传公钥：使用以下命令将公钥追加到服务器的 ~/.ssh/authorized_keys：

$ ssh-copy-id User@Host

在 Windows 系统或不支持 ssh-copy-id 的环境中，可手动操作：

  
$ scp -P <port> ~/.ssh/id_rsa.pub User@Host:~/.ssh/
$ ssh -p <port> User@Host
$ cat ~/.ssh/id_rsa.pub >> ~/.ssh/authorized_keys

设置权限（可选）：确保 authorized_keys 文件权限正确：
1 $ chmod 600 ~/.ssh/authorized_keys
验证配置文件：检查服务器的 /etc/ssh/sshd_config 文件，确保以下配置未被注释：
1 2 3 RSAAuthentication yes PubkeyAuthentication yes AuthorizedKeysFile .ssh/authorized_keys

完成以上步骤后，即可通过公钥免密登录。

配置文件

为简化登录流程，可在 ~/.ssh/config 文件中配置主机别名：

Host example
    HostName example.com
    Port 2222
    User myuser
    IdentityFile ~/.ssh/id_rsa

配置后，可通过以下命令快速登录：

$ ssh example

文件传输

SSH 提供 scp 命令用于文件传输。例如，将本地文件 test.cpp 上传至服务器的 /test/ 目录：

$ scp -P 12222 ./test.cpp User@8.8.8.8:/test/

端口转发

SSH 支持多种端口转发方式：

动态端口绑定：
1 $ ssh -D 8080 User@Host
将本地 8080 端口绑定到远程主机，实现 SOCKS 代理。
本地端口转发：
1 $ ssh -L 8080:host2:22 host3
将本地 8080 端口的数据通过 host3 转发至 host2 的 22 端口。
远程端口转发：
1 $ ssh -R 8080:host2:22 host1
将 host1 的 8080 端口数据通过 host3 转发至 host2 的 22 端口，适用于内网场景。

RSA & SSH | Vincent's Technical Reports (Vol. 3)

RSA and SSH

RSA加密算法详解

简介

算法原理

密钥生成

加密和解密

数学正确性证明

主要攻击方案与安全性分析

1. 小公钥指数攻击（低加密指数攻击）

明文长度与攻击的关系

填充的作用

块加密与填充

结论

2. 共模攻击 (Common Modulus Attack)

3. 广播攻击 (Håstad Broadcast Attack)

4. 量子计算威胁

Shor 算法

总结

参考文献

SSH技术解析

什么是 SSH？

SSH 的起源

SSH 的工作原理

1. 对称加密

2. 非对称加密

SSH 入门指南

基本登录

密码登录

公钥登录

配置文件

文件传输

端口转发

参考资料

RSA & SSH | Vincent's Technical Reports (Vol. 3)

RSA and SSH

RSA加密算法详解

简介

算法原理

密钥生成

加密和解密

数学正确性证明

主要攻击方案与安全性分析

1. 小公钥指数攻击（低加密指数攻击）

明文长度与攻击的关系

填充的作用

块加密与填充

结论

2. 共模攻击 (Common Modulus Attack)

3. 广播攻击 (Håstad Broadcast Attack)

4. 量子计算威胁

Shor 算法

总结

参考文献

SSH技术解析

什么是 SSH？

SSH 的起源

SSH 的工作原理

1. 对称加密

2. 非对称加密

SSH 入门指南

基本登录

密码登录

公钥登录

配置文件

文件传输

端口转发

参考资料

相关文章

How can we see a web page? | Vincent's Technical Reports (Vol. 5)

A Try on Reverse Engineering | Vincent's Technical Reports (Vol. 1)

Ocaml(1) | Vincent's Technical Reports (Vol. 2)