首页 > 代码库 > RSA算法笔记
RSA算法笔记
注意：只是笔记，可能有不正确的地方
RSA是目前用的最广泛的不对称加密算法，即采用公钥、密钥两部分，公钥用来加密，私钥用来解密。公钥是公开的。
RSA算法的可靠性基于数学难题：对大数做因式分解很难。
目前还没有快速算法，以目前计算机的计算能力，求解需要很长时间。数越大需要的时间越长，RSA算法也越安全。
由于RSA算法解密运算量大，所以通常RSA算法用来加密一个对称加密算法（比如AES、DES）的密钥，实际数据加密解密过程使用对称加密算法进行。
公钥、密钥生成过程：
1、找到两个比较大的质数p、q
2、计算他们的乘积n，n=p×q。
在实际中用二进制表示的n的位数即RSA密钥长度，1024位RSA密钥，就是说n有1024位。n越大越安全，到2010年被分解的最大的数是768位，但密钥越长，解密运算量也越大，所以为了平衡目前通常密钥在1024到2048位之间。
3、选取一个整数e
这个整数需要满足的条件：
1<e<φ(n)，φ(n)是欧拉函数，比如如果n=8，那么φ(n)=4。
e与φ(n)互质
在实际情况中e不计算，只选取一个固定的质数，通常为质数65537。
4、计算整数d，d为e对于φ(n)的模反元素
5、公钥为n、e，私钥为n、d
使用公钥、密钥加解密：
1、使用公钥(n、e)加密：
如果需要加密的整数为m，且m<n，那加密后的结果为：
c=(m^e)%n，^代表乘方运算，如2^3=2*2*2，%为求模运算，比如5%3=2
2、使用密钥(n、d)解密：
原整数m=(c^d)%n
示例：
1、选两个质数p=61，q=53
2、计算乘积n=p×q=61*53=3233
3、选取整数e=17
4、计算整数得d=2753
5、获得公钥（3233,17），私钥（3233,2753）
6、将整数m=65加密：
c=(m^e)%n=(65^17)%3233=2790
7、解密：
m=(c^d)%n=(2790^2735)%3233=65
由示例可以看出解密过程的计算量是很大的，比如如果直接计算2790^2735，对CPU要求高，计算很耗时。实际使用中两个数比现在更大，直接运算是不合适的。但(c^d)%n这种运算被称为模幂运算(Modular exponentiation)，有一些的优化计算方法，比直接运算占用内存小速度快，但仍然运算量不小。
实际应用中通常再计算以下三个数exponent1、exponent2、coexponent并和私钥保存在一起，用于优化解密过程，虽然如此解密还是很占用CPU的。
由于公钥是公开的，实际中公钥也会保存在私钥中。
比如查看一个由openssl生成的私钥：
生成1024位rsa私钥，保存为pem格式：
openssl genpkey -out key.pem -algorithm rsa
查看私钥内容：
openssl pkey -in key.pem -text -noout
输出：
Private-Key: (1024 bit)
modulus:
00:bd:c0:10:ae:26:12:c3:82:2c:56:d1:bb:26:42:
38:47:3d:ca:c5:ae:a4:c8:de:27:4f:a1:61:e5:f3:
2e:ce:d7:48:62:20:1f:76:47:c2:cf:6b:43:d2:b4:
b6:b4:eb:21:21:d6:f4:d8:c8:09:ab:cd:c5:ce:65:
48:56:43:d6:d2:f4:0c:e4:66:ef:34:33:bd:9d:1d:
d3:23:af:39:63:51:4c:b5:88:ea:b5:92:7e:4e:e0:
6f:cd:50:7f:06:49:ea:dc:80:59:12:d4:59:86:6e:
79:a5:b7:d9:c0:b0:c8:cd:12:4b:6c:49:7e:33:5f:
b4:f7:6b:37:8e:18:42:3c:ed
publicExponent: 65537 (0x10001)
privateExponent:
3f:4f:d5:80:f5:ed:2e:d4:c1:4c:9a:a0:32:4c:c8:
10:65:3a:c2:28:da:8c:b7:2b:30:b3:ad:41:97:99:
97:a4:57:5f:7e:4e:61:1d:e2:8f:68:bf:f1:8f:20:
a3:4f:0c:f8:08:8c:1b:c4:eb:0d:2b:14:84:20:61:
39:7f:5b:2e:e6:84:87:2f:0f:e1:b2:a6:ec:6a:19:
33:c7:44:c9:86:ca:66:9d:ad:d4:a3:70:f2:a7:99:
da:fe:1a:c2:8e:21:01:bb:4d:14:48:16:67:d0:59:
4a:25:0a:0c:2c:73:3a:47:05:d6:de:b9:d1:a5:67:
b8:98:03:fe:e9:ae:3d:75
prime1:
00:ed:ca:a8:af:62:70:84:c2:53:bf:6e:61:cd:ac:
24:7e:4c:cd:16:28:f3:f0:b8:10:bb:b5:9f:f5:49:
fd:98:e7:28:44:d4:82:8c:9c:14:69:07:79:49:0e:
b8:fd:8d:0c:d8:74:5a:06:f3:8c:9f:f4:39:f2:57:
ce:31:57:50:9f
prime2:
00:cc:47:ab:3b:77:12:e9:43:9f:cd:61:ba:05:22:
83:89:d1:b4:f5:97:32:7c:4d:ff:63:03:d4:df:cb:
1c:9b:4a:88:aa:a7:e9:8e:92:66:3f:2c:34:b7:b3:
f0:ec:86:00:30:d9:01:17:34:96:7c:35:c9:c1:8b:
87:80:35:8a:f3
exponent1:
37:08:02:b7:ec:21:3c:28:38:f7:81:95:32:e3:16:
e2:ff:e5:2a:ae:b9:9d:c9:0b:5e:55:af:3a:36:30:
71:75:75:b5:50:35:12:53:80:c9:b9:c8:10:e7:4e:
5a:a7:8d:04:7f:10:e2:b0:f4:a7:83:fe:f1:1d:ef:
03:2e:40:e3
exponent2:
00:8a:21:70:24:ce:98:88:08:c5:16:e0:9d:23:79:
ba:0e:48:32:1f:da:f4:35:5f:9c:70:3c:98:06:17:
d6:a9:1f:16:18:a7:5f:e3:9b:14:ee:64:9a:e5:19:
14:b1:2a:cf:18:38:b4:67:17:95:26:3a:4c:c9:c5:
ea:83:04:31:87
coefficient:
6e:09:3a:c8:dd:44:2e:1c:e0:e3:e7:a3:44:7e:c3:
56:fe:6c:a9:22:44:11:63:92:91:90:80:f4:86:6e:
e5:03:c0:ea:2e:c1:83:8c:5b:74:82:8b:5d:22:6e:
6f:2b:9c:d2:84:29:60:12:dc:06:3a:5f:65:bd:66:
6a:aa:fb:d9
各项内容代表意义：
来源（http://stackoverflow.com/questions/22078801/creating-pem-pfx-from-private-modulus）
RSAPrivateKey ::= SEQUENCE {
version Version,
modulus INTEGER, -- n
publicExponent INTEGER, -- e
privateExponent INTEGER, -- d
prime1 INTEGER, -- p
prime2 INTEGER, -- q
exponent1 INTEGER, -- d mod (p-1)
exponent2 INTEGER, -- d mod (q-1)
coefficient INTEGER, -- (inverse of q) mod p
otherPrimeInfos OtherPrimeInfos OPTIONAL
}
参考：
RSA算法原理（一） http://www.ruanyifeng.com/blog/2013/06/rsa_algorithm_part_one.html
RSA算法原理（二） http://www.ruanyifeng.com/blog/2013/07/rsa_algorithm_part_two.html
wiki: http://en.wikipedia.org/wiki/RSA_(cryptosystem)
exponent1、exponent2、coexponent作用： http://www.di-mgt.com.au/crt_rsa.html
RSA密钥生成速度参考： https://wiki.strongswan.org/projects/strongswan/wiki/PublicKeySpeed
模幂运算 Modular exponentiation ： http://en.wikipedia.org/wiki/Modular_exponentiation
RSA算法笔记