RSA算法概述

RSA算法是常用的非对称算法，应用广泛。比如常见的ssh连接，使用过gitlab的开发者都接触过，通过rsa算法可以生成一对证书，通过把公钥设置到gitlab上面，本地才可以通过ssh的方式下载代码。


root@keep-VirtualBox:~# ssh-keygen -t rsa -b 2048 -C "auth@xxx.com"
Generating public/private rsa key pair.
Enter file in which to save the key (/root/.ssh/id_rsa): /root/.ssh/id_rsa_auth
Enter passphrase (empty for no passphrase):
Enter same passphrase again:
Your identification has been saved in /root/.ssh/id_rsa_auth
Your public key has been saved in /root/.ssh/id_rsa_auth.pub
The key fingerprint is:
SHA256:jSLQwYvLcHx+ya2VkeOVy+jbuFqj4CcIuRVwvBqkRtQ auth@xxx.com
The key's randomart image is:
+---[RSA 2048]----+
|.o...            |
|.ooE..           |
|++.o..   . .     |
|+.*.o   +oo      |
|.B =...+SB..     |
|+ + ..+.* o      |
| + ... +o        |
|. ....oo.+       |
|    .oo.+o.      |
+----[SHA256]-----+

root@keep-VirtualBox:~# ls -la ~/.ssh/
总用量 48
drwx------  2 root root 4096 5月  16 17:48 .
drwx------ 18 root root 4096 5月  16 11:07 ..
-rw-------  1 root root 1876 5月  16 17:48 id_rsa_auth
-rw-r--r--  1 root root  394 5月  16 17:48 id_rsa_auth.pub
-rw-r--r--  1 root root 1332 3月  25 15:01 known_hosts

然后把id_rsa_auth.pub的内容设置到gitlab就ok了。

算法原理

RSA算法基于一个十分简单的数论事实：将两个大素数相乘十分容易，但是想要对其乘积进行因式分解却极其困难，因此可以将乘积公开作为加密秘钥。

密钥生成过程：

生成两个大的质数 p, q。如：p=7, q=19
得到n=pq, m = (p-1)(q-1)。如n=133, m=108
选取e使得e和m互质。如e=5
生成d，使得d*e mod m = 1。如d=65
最后丢弃p,q,m。公钥就是e, n; 私钥就是d, n。公钥(5, 133)，私钥(65, 133)

加密过程：

输入明文x通过计算得到y

1
2
3

y = x^e mod n

# x = 6, 则 y = 6^5 mod 133 = 62

解密过程：
输入密文通过计算得到x

1
2
3

x = y^d mod n

# x = 62^65 mod 133 = 6

RSA算法非常可靠，密钥越长，它就越难破解。根据已经披露的文献，目前被破解的最长RSA密钥是768个二进制位。也就是说，长度超过768位的密钥，还无法破解（至少没人公开宣布）。因此可以认为，1024位的RSA密钥基本安全，2048位的密钥极其安全。

RSA涉及到了一些数学的概念。

质数一个大于1的自然数，除了1和它本身外，不能被其他自然数整除（除0以外）的数称之为质数（素数）；否则称为合数。
互质若N个整数的最大公因子是1，则称这N个整数互质。
指数运算指数运算又称乘方计算，计算结果称为幂。
模运算让m去被n整除，只取所得的余数作为结果，就叫做模运算。

这些也就是RSA的基础。还有更深层次的欧拉定理就不讲了，感觉有些费脑了。

其他

前面使用ssh-keygen生成rsa的公钥密钥的时候，需要输入一个密码。其实这个密码本身跟RSA是没有关系的，只是为了密钥的安全，使用了对称算法对密钥进行了加密。只有知道这个密码的人才能使用这对密钥。

行动，才不会被动!

欢迎关注个人公众号微信 -> 搜索 -> fishmwei，沟通交流。

博客地址： https://fishmwei.github.io/
掘金主页： https://juejin.cn/user/2084329776486919

IT攻城狮小明

周谈(21)-浅谈RSA算法

RSA算法概述

算法原理

其他