操作流程

1. 客户端制作密钥对

   [root@host ~]$ ssh-keygen  <== 建立密钥对
   Generating public/private rsa key pair.
   Enter file in which to save the key (/root/.ssh/id_rsa): <== 按 Enter
   Created directory '/root/.ssh'.
   Enter passphrase (empty for no passphrase): <== 输入密钥锁码，或直接按 Enter 留空
   Enter same passphrase again: <== 再输入一遍密钥锁码
   Your identification has been saved in /root/.ssh/id_rsa. <== 私钥
   Your public key has been saved in /root/.ssh/id_rsa.pub. <== 公钥
   The key fingerprint is:
   0f:d3:e7:1a:1c:bd:5c:03:f1:19:f1:22:df:9b:cc:08 root@host
   

2. 服务器安装公钥
   将客户端上的*.pub复制到服务器中，将其内容追加到~/.ssh/authorized_keys，即：

   cat id_rsa.pub >> ~/.ssh/autorized_keys
   

3. 服务器SSH配置
   编辑/etc/ssh/sshd_config文件，进行如下设置：

   RSAAuthentication yes
   PubkeyAuthentication yes
   PermitRootLogin yes # 可选，设置是否允许root登录
   PasswordAuthentication yes # 可选，设置是否允许密码登录
   

   而后重启SSH服务：

   service sshd restart
   

4. （另一种方式）服务器分发私钥
   生成密钥对的过程也可以在服务器上进行，那么服务器需要将私钥下发给客户端。客户端在ssh时使用-i选项可以指定私钥文件，或者在sshd_config中加入配置指定私钥：

   IdentityFile ~/.ssh/id_rsa
   

认证过程

来自ssh 公钥私钥认证原理
以下表分别指代客户端和服务器的公私钥

符号	含义
Ac	客户端公钥
Bc	客户端密钥
As	服务器公钥
Bs	服务器密钥

认证之前，客户端已将公钥Ac上传至服务器，或者服务器已将私钥Bc下发给客户端。

1. 会话密钥生成
   1. 客户端请求连接服务器，服务器将 As 发送给客户端。
   2. 服务器生成会话ID(session id)，设为 p，发送给客户端。
   3. 客户端生成会话密钥(session key)，设为 q，并计算 r = p xor q。
   4. 客户端将 r 用 As 进行加密，结果发送给服务器。
   5. 服务器用 Bs 进行解密，获得 r。
   6. 服务器进行 r xor p 的运算，获得 q。
   7. 至此服务器和客户端都知道了会话密钥q，以后的传输都将被 q 加密。
2. 认证
   1. 服务器生成随机数 x，并用 Ac 加密后生成结果 S(x)，发送给客户端
   2. 客户端使用 Bc 解密 S(x) 得到 x
   3. 客户端计算 q + x 的 md5 值 n(q+x)，q为上一步得到的会话密钥
   4. 服务器计算 q + x 的 md5 值 m(q+x)
   5. 客户端将 n(q+x) 发送给服务器
   6. 服务器比较 m(q+x) 和 n(q+x)，两者相同则认证成功

RSA原理

来自RSA算法原理（二）

预备知识

1. 欧拉函数$\varphi(n)$代表小于n的正整数中，有多少个与n构成互质关系
2. 欧拉函数的运算律
   • $\varphi(1)=1$
   • $\varphi(n)=n-1$，若n为质数
   • $\varphi(p^k)=p^k-p^{k-1}=p^k(1-\frac{1}{p})$，若$p$为指数
   • $\varphi(n)=\varphi(p\times q)=\varphi(p)\times\varphi(q)$，若$n=p\times q$且$p,q$都为质数
   • $\varphi(n)=n(1-\frac{1}{p_1})\cdots (1-\frac{1}{p_r})$，若$n$可以分解为质数的积$n=p_1^{k_1} p_2^{k_2}\cdots p_r^{k_r}$
3. 欧拉定理：两个正整数$a,n$互质，则欧拉函数$\varphi(n)$满足：

$a^{\varphi(n)}\equiv 1\pmod{n}$

4. 模反元素：两个正整数$a,n$互质，那么一定可以找到整数$b$，使得$ab-1$被$n$整除。$b$叫做$a$的模反元素：

$ab\equiv 1\pmod{n}$

密钥生成过程

1. 随机选择两个不相等的质数$p$和$q$
2. 计算$p$和$q$的乘积$n=p\times q$
3. 计算$n$的欧拉函数$\varphi(n)=(p-1)(q-1)$
4. 随机选择一个整数$e, 1<e<\varphi(n)$, 且$e$与$\varphi(n)$互质
5. 计算$e$对于$\varphi(n)$的模反元素$d$
6. 密钥对生成完毕，公钥为$(n,e)$，私钥为$(n,d)$，其他中间变量$p,q,\varphi(n)$被销毁

破解RSA需要知道$d$，也即需要知道$\varphi(n)$，也即需要知道$p,q$，也即要对$n$做质因数分解。当n足够大时，这样的破解几乎无法做到。

加密和解密

1. 加密：对于信息$m$，根据公钥$(n,e)$可以进行加密：

$c = m^e \bmod n$

2. 解密：对于密文$c$，根据私钥$(n,d)$可以进行解密：

$m = c^d \bmod n$

注意被加密的信息$m$必须小于$n$

证明

加密的过程为

$c = m^e \bmod n$

那么$c$可以写成

$c = m^e - kn$

将其带入解密公式

$c^d = (m^e-kn)^d=m^{ed}-kn\times \sum_{i=0}^{d-1}C_d^i (m^e)^i (-kn)^{d-i} \\ c^d \equiv (m^{ed}-kn(\cdots))\equiv m^{ed} \pmod{n}$

由于$e$对于$\varphi(n)$的模反元素$d$

$ed \bmod \varphi(n) = 1$

所以

$ed = h\varphi(n)+1$

最终

$c^d\equiv m^{ed}\equiv m^{h\varphi(n)+1} \pmod{n}$

(1) 当$m$与$n$互质，根据欧拉定理

$m^{\varphi(n)}\equiv 1\pmod{n}$

那么将$m^{\varphi(n)}$写为$n$的乘积加一，再结合二项式定理可得

$m^{h\varphi(n)+1} \equiv ((tn+1)^h \times m) \equiv m \pmod{n}$

(2)当$m$与$n$不互质，由于$n$的因数只有$p,q$，因此$m=kp$或$m=kq$。$p,q$地位等同，不妨认为$m=kp$。

此时$k$与$q$互质（$k<q$且$q$为质数），根据欧拉定理

$(kp)^{q-1} \bmod q = 1 \\ (kp)^{q-1} = zq+1$

进一步

$m^{h\varphi(n)+1} \\ =kp^{h(p-1)(q-1)}\times kp \\ =(zq+1)^{h(p-1)} \times kp \\ =tq+kp$

其中$t$可被$p$整除（因为二项式分解后每项都乘以了$kp$）。再改写一下

$m^{h\varphi(n)+1} = t'pq+kp=t'n+m$

所以

$m^{h\varphi(n)+1} \equiv m \pmod{n}$