image.png
RSA数学原理
上世界70年代产生的一种加密算法。需要有两个密钥：公开密钥简称公钥(publickey)和私有密钥简称私钥(privatekey)。公钥加密，私钥解密；私钥加密，公钥解密。这个加密算法就是伟大的RSA
欧拉函数
说到欧拉函数，先要说到互质的概念？
互质概念
如果又两个正整数，除了1以外，没有其他公因数，我们就称这两个数是互质关系
欧拉函数特点
一、当n是质数的时候，φ(n)=n-1。
二、如果n可以分解成两个互质的整数之积，如n=AB则：
φ(AB)=φ(A)* φ(B)
根据以上两点得到：
如果N是两个质数P1 和 P2的乘积则
φ(N)=φ(P1)* φ(P2)=(P1-1)*(P2-1)
demo展示
计算这个值的方式叫做欧拉函数，使用：Φ(n)表示
如:
计算8的欧拉函数，和8互质的 1、2、3、4、5、6、7、8
φ(8) = 4
计算7的欧拉函数，和7互质的 1、2、3、4、5、6、7
φ(7) = 6
计算56的欧拉函数
φ(56) = φ(8) * φ(7) = 4 * 6 = 24
欧拉定理
如果两个正整数m和n互质，那么m的φ(n)次方减去1，可以被n整除。
image.png
费马小定理
欧拉定理的特殊情况：如果两个正整数m和n互质，而n为质数，那么φ(n)结果就是n-1
image.png
模反元素
如果两个正整数e和x互质，那么一定可以找到整数d，使得 ed-1 被x整除。
那么d就是e对于x的“模反元素”
另外又因为
image.png
image.png
所以可得出:
image.png
然后又因为:1*m ≡ m,所以有：
image.png
结合模反元素概念，可以得出：
e * d mod x ≡ 1;
e * d ≡ k * x + 1;
image.png
看一个加密的小例子
image.png
计算原理：
image.png
image.png
image.png
公钥：n和e
私钥：n和d
明文: m
密文: c
- n会非常大，长度一般为1024个二进制位。（目前人类已经分解的最大整数，232个十进制位，768个二进制位）
- 由于需要求出φ(n)，所以根据欧函数特点，最简单的方式n 由两个质数相乘得到: 质数：p1、p2
Φ(n) = (p1 -1) * (p2 - 1) - 最终由φ(n)得到e 和 d 。
总共生成6个数字：p1、p2、n、φ(n)、e、d
关于RSA的安全
除了公钥用到了n和e 其余的4个数字是不公开的。
目前破解RSA得到d的方式如下：
1、要想求出私钥 d 。由于e*d = φ(n)*k + 1。要知道e和φ(n);
2、e是知道的，但是要得到 φ(n)，必须知道p1 和 p2。
3、由于 n=p1*p2。只有将n因数分解才能算出。
操作演示
我使用的是mac电脑，mac电脑内置了OpenSSL(开源加密库),我们可以直接在终端上面操作：
OpenSSL中RSA算法命令主要有3个：
genrsa 生成并输入一个RSA私钥
rsault 使用RSA密钥进行加密，解密，签名等运算
rsa 处理RSA密钥的格式转换等问题
生成RSA私钥，密钥长度为1024个字节
➜ rsa openssl genrsa -out private.pem 1024
Generating RSA private key, 1024 bit long modulus
.......................................++++++
........................................++++++
e is 65537 (0x10001)
从私钥中提取公钥
➜ rsa openssl rsa -in private.pem -pubout -out public.pem
writing RSA key
Snip20200417_11.png
可以看到已经生成了两个文件
将私钥转换成明文
rsa -in private.pem -text -out private.txt
查看私钥 cat private.txt
-----BEGIN RSA PRIVATE KEY-----
MIICWwIBAAKBgQCrZgfFNOfxRoTdfsxkA5iDKo7pZHn6LLuQAcI4CoAdW8LZXJKA
FgVcXk5I73nPRJoOsA4BcSZ1LG/s2jrZea4G4cMAnQ7magE+f164O9ETAbDTYVze
51y8Lp/h7oEGt0ai7An+5Sby+Uaz4B4iKEqEPxpfMEY+LxV56TdnU4T9oQIDAQAB
AoGAc5Hin2ijFJ82K5u5+Z4rEhZ6MolbbgMHnXxyFxONez5KTgILjm5KwxObubYv
7kAVmN3BM9u10MBb39ruX4Gag1LW/p76Ml7AMoEEBieosIPeu/KYqXcl0D0StZ2F
B9BZUmfqCmVFEUvGDqSkFZKhKZdZ4t6GZ8a3hdp2TmgbEXkCQQDW4UOj6NtDuBgG
l/Dro5dRLyIFYIF/BzcpaFefnYXStBsZ45FSy8XBADUP8YDN5r2wyXfS2v1pImCN
N+EIeH03AkEAzDKpBZB9r8EYp2KemcTnZ4RezIshnJHFp8d/F1z9cxPjN+MZGYl4
64gAh5rchTVk7TAc+PVEhU1LnAAHg1yH5wJABiJyOui38cv8q5uE3kVSWZf94adq
qwS6t2zqK31kx6oqp+eOS43TvHnUCft8EOTIf5aQ3C0yVOENXpq8yvAdqwJANWd6
dQ4ZEQI7ZGuSdzzcGGKyOGSa4cvuGbc/MekMEDC/WDp4sgkWKuNi4BRMYDparv3K
VgIvbX2NrLsFPAHTOQJAXPnZ+y3eNJxYiwkHCQKhnh53xkQrQldRW+KxggijSVhe
P0v2PwOex4tjpwxpMfAH8CSw9HswwLEDL63nfR6oPQ==
-----END RSA PRIVATE KEY-----
通过公钥加密数据，私钥解密数据
➜ rsa vi message.txt
➜ rsa cat message.txt
Hello World
➜ rsa openssl rsautl -encrypt -in message.txt -inkey public.pem -pubin -out enc.txt
➜ rsa cat enc.txt
���$bd)}Ω�ї�Uj% ➜ rsa openssl rsautl -decrypt -in enc.txt -inkey private.pem -out dec.txt
➜ rsa cat dec.txt
Hello World
通过私钥加密数据，公钥解密数据
➜ rsa openssl rsautl -sign -in message.txt -inkey private.pem -out enc.txt
➜ rsa cat enc.txt
�c�a�Fb�#�T)�A�% ➜ rsa openssl rsautl -verify -in enc.txt -inkey public.pem -pubin -out dec.txt
➜ rsa cat dec.txt
Hello World
网友评论