一.理论
如果需要理解RSA的加密原理,需要理解以下理论:
(1)如果两个正整数除了1以外没有其他公因子,则这两个数称为互质关系。(比如5和9)
(2)给定一个正整数n,在小于等于n的正整数中,与n形成互质关系的数的个数计为(n),(n)称为欧拉函数。(比如在1到8之间与8形成互斥关系的数为1、3、5、7,则(8)=4)
(3)对于一个质数n来说,(n)=n-1
(4)如果n可以分解为两个互质的整数之积,即n=p1p2,p1与p2互质,则满足公式:(n) = (p1p2) = (p1) (p2) = (p1-1) (p2-1)
(5)如果a与b互质,则满足公式: 1( mod b),即a的(b)次方除以b的余数为1
(6)如果a与b互质,则存在n使得an 1(mod b),n称为a的模反元素
二.如何生成一对公私钥
(1)选择两个不相等的质数p,q。如(p=13,q=17)
(2)将p与q相乘的到n。n=1317=221
(3)计算n的欧拉函数,即(n)=(221)=(p-1)(q-1)=192
(4)在1到(221)之间选择一个与(221)互质的数e,如选择e=23
(5)我们可以求得e对于(n)的模反元素d,即 ed 1(mod (n))
等同于求一元二次方程 23 * d + 192 * y = 1
可以求得其中一解为(d=167,y=-20)
至此就完成了所有的计算
(6)将计算出来的值封装为公钥(n,e)和私钥(n,d)
对于上述例子的到公钥(221,23)和私钥(221,167)
三.RSA的可靠性
在上述的计算过程中一共用到了
- 两个质数p,q
- p与q的乘积n
- 欧拉函数(n)
- 一个小于(n)并与之互质的数e
- e对于(n)的模反元素d
上面用到的数中只有公钥部分是公开的,即(221,23)。那么我们是否可以通过公钥来推到出私钥部分,即已知n和e,推到出d?
(1)ed 1(mod (n)),只有知道(n)才能解出d
(2)(n)=(p) (q)= (p-1)(q-1),只有知道p和q才能得到(n)
(3)n=pq,就需要对n进行因式分解
那么如果可以对n因式分解就可以求出d,也就意味着私匙被破解
那么RSA加密的可靠性就在于对n因式分解的难度,而现在对一个整数n做因式分解并没有巧妙的算法,只有通过暴力破解计算。在实际应用中的n取值通常在1024位以上,而公开已知的可因式分解的最大数为768位。所以现阶段来说RSA加密是可靠的。
四.加解密过程
现在我们就可以进行加密和解密了
(1)使用公钥(n,e)加密
我们使用上面生成的公钥(221,23)来加密。如果我们需要加密的信息是m(m必须为整数并且m要小于n),m取56,可以用以下公式求出加密串c:
c (mod n)
10 (mod 221)
可以求出加密后的结果c为10
(2)使用密钥(n,d)解密
密钥为(221,167),加密结果c=10,可以使用以下公式求出被加密的信息
m (mod n) 即加密结果的d次方除以n的余数为m
56 (mod 221)
五.RSA加密的三种填充模式
RSA加密属于块加密算法,总是在一个固定长度的块上进行操作。如果被加密的字符串过长,则需要对字符串进行切割,如果字符串过短则需要进行填充。
填充方式 | 输入 | 输出 |
---|---|---|
RSA_PKCS1_PADDING | 必须比RSA钥模长至少短11位以上 | 与RSA钥模长一样长 |
RSA_PKCS1_OAEP_PADDING | 必须比RSA钥模长至少短41位以上 | 与RSA钥模长一样长 |
RSA_NO_PADDING | 可以和RSA钥模长一样长 | 与RSA钥模长一样长 |
以下主介绍一下RSA_PKCS1_PADDING填充模式以及RSA_NO_PADDING模式
(1)RSA_PKCS1_PADDING填充模式
此填充模式是最常用的填充模式,在此填充模式下输入的长度受加密钥的长度限制,输入的最大长度为加密钥的位数k-11。如果公钥的长度为1024位即128字节,那么输入的长度最多为128-11=117字节。如果长度小于117就需要填充。如果输入T的长度为55字节,填充后的块为EM,则EM格式如下:
EM= 0x00 || BT || PS || 0x00 || T
首字节填充0x00,确保加密块的大小小于加密钥(可见第四部分加密要求)
BT仅一个字节,并只有三种选项0x00,0x01,0x02。其中0x02表示公钥加密,0x00,0x01表示私钥加密
PS表示填充字段,根据BT类型有不同的情况。1.对于公钥加密的情况(即BT=0x02),PS为随机生成的且不含0的数。2.BT=0x00,PS填充的值为0x00(只有输入T不以0x00开头时,BT才为0x00,否则会有歧义)。3.BT=0x01,PS填充0xFF。PS的长度为128-3-len(T)=70字节,所以PS随机数长度至少为8个字节
而后填充0x00用于区分填充字段和输入信息
-
T为实际的输入
以上内容可在RFC 2313 第8.1章节找到
(2)RSA_NO_PADDING填充模式
在此填充模式下,输入的长度最多和RSA公钥长度一样长,如果小于公钥长度则会在前面填充0x00。如果公钥长度是128字节,输入T的长度为55字节,填充后的块为EM,则EM格式如下:
EM=P || T
- 如果T长度为55字节,则P为73字节0x00
- T为实际输入
参考:
http://www.ruanyifeng.com/blog/2013/06/rsa_algorithm_part_one.html
http://www.ruanyifeng.com/blog/2013/07/rsa_algorithm_part_two.html
https://my.oschina.net/3pgp/blog/749195