首页 > 代码库 > 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算法笔记