浅谈RSA2加密原理

RSA2加密解密原理分析

一、相关定义

RSA2签名

签名主要包含两个过程：摘要和非对称加密，首先对需要签名的数据做摘要（类似于常见的MD5）后得到摘要结果，然后通过签名者的私钥对摘要结果进行非对称加密即可得到签名结果。加密是为了防止信息泄露，签名是为了防止信息被篡改。

加密与签名

发送双方A-B 都有一套公钥和私钥，公钥拿对方的，私钥拿自己的。A发送消息给B时，用B的公钥进行加密，加密可以防止信息泄露。然后用自己的私钥签名，签名防止信息被篡改。B收到消息之后，用公钥进行验签，验证信息是否篡改，用私钥解密获取原始信息。

摘要

生成一个定长128位，不可逆的数字。同一个数据，两次摘要，结果必然相同。收集明文对应的摘要，则有很大机率破译。
摘要知识用于验证数据完整性和唯一性 。

非对称加密

指加密和解密用的不是同一套密钥。针对对称加密的缺点，而产生的非对称加密。通过公钥加密，则公钥任何人都可以获取，通过私钥解密，私钥只有自己拥有。

RSA和RSA2签名算法区别

RSA2强制要求密钥长度为2048
RSA则推荐长度为2048
足够大的质数也是由对应的开源库随机产生
长度过短，则通过暴力破解的方式可以短时间内破解
而2048的长度依靠现在的算力至少需要300万亿年，当然量子计算机出现获取可以实现倒推明文

PKCS1与PKCS8格式的小知识

PKCS1 ：里面包含了RSA加密、解密、签名验签等所有的内容，当然也包含了私钥的格式。
PKCS8：专门用来存储私钥的文件格式规范。
PKCS1优先于PKCS8出现，在当时RSA算是最先进的非对称加密技术。随着加密算法的发展才有了PKCS8出来专门做存储密钥这样一件事情
需要注意的是 Java中使用RSA私钥格式必须为PKCS8否则报错

algid parse error, not a sequence

签名类型划分

Attach签名：其特点是将原文、签名证书、签名算法、签名数据 封装成签名结果。
Detached签名：签名证书、签名算法、签名数据 封装为签名结果
Raw签名： 只将签名数据封装成签名结果

国密

国家自己研制出的一套加密算法。

二、加密原理

1.求幂再求余

假设要发送的一个字母c，为了方便计算我们用十进制，a就是1，b就是2，c就是3 …
假设公钥里是（7，33），私钥里是（3，33）。
我们对3^7%33 得到的9 就是密文。
拿到密文之后进行解密
解密和加密操作一样
我们对9^3%33 得到了 3 就是我们的明文数据了。
如图

公钥私钥的由来

通过刚刚的求幂和求余，应该大致了解了加密的过程，你一定很惊讶，也可以发现关键之处在于公钥和私钥。
下面聊一聊公钥私钥的制作过程
质数：是指在大于1的自然数中，除了1和它本身以外不再有其他因数的自然数。

互质是：公约数只有1的两个整数，叫做互质整数。公约数只有1的两个自然数，叫做互质自然数
任意两个质数构成的是互质关系。一个数是质数，另一个数只要不是前者的倍数，两只之间就构成互质的关系。如果两个数之间叫大的书是质数，则两者构成互质关系。

欧拉函数：在数论，对正整数n，欧拉函数是小于或等于n的正整数中与n互质的数的数目（因此φ(1)=1）。 例如φ(8)=4，因为1,3,5,7均和8互质。

因为质数,除了1和它本身以外不再有其他因数的自然数,那么质数的欧拉函数就是本身减一
φ(5)=sum（1，2，3，4）=（5-1）=4

1. 首先需要选出两个互质的数， 我们选 3 和 11
2. 让两个质数相乘 n = 3*11
3. 计算n的欧拉函数，T = φ(n)
4. 公钥 质数；1<公钥<T;不是T的因子 E=（3，n）
5. 私钥D 通过这个算式算出（D*E）%T = 1 D=（7，33） 如图

欧拉函数

通过上面分析，了解了公钥私钥的生成方式，得出要想的到私钥，就要倒退得到 E,T,N。其中非常关键的一个地方就是第三步的欧拉函数。我们可以尝试再往下聊聊欧拉函数。
说到欧拉函数，就必须要说到一个人，皮埃尔·德·费马
费马提出过一个 费马小定理

如果p是一个质数，而整数a不是p的倍数，则有a^（p-1）≡1（mod p）。

a^（p-1）≡1（mod p）就是说a的p-1次幂和1对于p求余结果相等。

费马很调皮，只是给出了结论，然后说字不够了，让大家去证明。

接下来主角出现，欧拉，欧拉在证明费马的话时，发现确实成立。但是不够广泛，因此就想能不能扩大一下要求的范围，后来发现，a和p只要都是整数，且互质就可以满足这个定理。证明过程如图

证明过程中用到φ(m*n)=φ(m)*φ(n)，是因为欧拉函数还是一个积性函数，可以自行证明

总结

本文仅仅简单介绍了RSA2相关的名词和基本运算规则，使用RSA2加密能使我们安全的进行数据的传输。