RSA算法学习

2012年3月11日 | 分类: 日志 | 标签: , ,

From维基百科
RSA加密算法是一种非对称加密算法。在公钥加密标准电子商业中RSA被广泛使用。RSA是1977年罗纳德·李维斯特(Ron Rivest)、阿迪·萨莫尔(Adi Shamir)和伦纳德·阿德曼(Leonard Adleman)一起提出的。当时他们三人都在麻省理工学院工作。RSA就是他们三人姓氏开头字母拼在一起组成的。

RSA加密算法的可靠性基础是由对极大整数做因数分解的困难性。

  • 生成公钥和私钥
    1.随意选择两个大的质数p和q,p不等于q,计算N=pq。
    2.根据欧拉函数,不大于N且与N互质的整数个数为(p-1)(q-1)
    3.选择一个整数e与(p-1)(q-1)互质,并且e小于(p-1)(q-1)
    4.用以下这个公式计算d:(d * e) mod ((p-1)(q-1)) ≡ 1
    5.将p和q的记录销毁。
    (N,e)是公钥,(N,d)是私钥。
  • 加密
    首先需要注意的是,公钥和私钥是相对而言的,也就是说,明文c使用私钥(N,d)加密后的m_d可以被公钥(N,e)解密,反之明文c使用公钥(N,e)加密后的m_e可以被私钥(N,d)解密。openssl的rsa代码里#define RSA_F4    0x10001L 也就是65537,是常用的e的值。例如用私钥加密,则使用下公式
    {m^d} \equiv c(\bmod \,N)
    计算出m就是c加密后的密文了。
  • 解密
    用公钥解密
    {c^e} \equiv m(\bmod \,N)
    计算出的c就是密文m解密后的明文了。

加密与解密的算法其实是一样的,因为加密与解密本身也是相对的,具体算法可以参考维基百科或者其他资料,我数学水平不行,没搞明白……

关于签名
RSA可用于给消息签名,一般过程是:对消息生成摘要(比如MD5 SHA1 SHA512等算法),然后用私钥生成摘要的密文就是这个消息的签名了,签名时可能会需要对摘要按规则进行填充例如PKCS1方案。
验证签名:对方收到消息和签名后,用公钥对签名进行解密,得到加密前的明文,与消息的摘要进行对比,如果匹配则说明消息没有被篡改。
数字签名的作用:1.鉴权,确认发送者的身份,例如加上时间戳信息防止重放攻击;2.保证数据完整性;3.数字签名具有不可抵赖性,

针对RSA最流行的攻击一般是基于大数因数分解。一般建议使用长度为1024bits以上的密钥。
openssl带有rsa算法的相关的工具。生成key的工具openssl genrsa,处理key的工具openssl rsa

下面解释一下openssl生成的rsa密钥的一些解释。
openssl里可用openssl rsa命令查看生成的私钥,可以看到有下面几个部分:

$ openssl rsa -in test_key.pem -text
Private-Key: (2048 bit)
modulus:
    00:b2:3f:51:f8:7b:64:a7:b5:7b:29:3f:d0:c0:f8:
    8a:04:71:29:ba:3f:8e:f9:28:1e:48:5e:0d:04:46:
    a3:cd:47:93:1f:69:4b:b8:69:d3:70:ee:f7:71:03:
    d3:0b:71:0d:0d:fb:3a:e3:04:8b:79:ea:b8:cc:f8:
    41:4a:51:cb:68:92:f0:66:f8:61:1f:fb:e4:0c:5e:
    0d:f2:e6:82:db:91:c3:43:fe:4e:83:40:e3:9e:9a:
    ba:e3:fe:27:44:e3:07:02:27:01:04:07:fa:aa:e1:
    5f:b0:8d:d3:7f:4a:0e:27:b5:5e:4f:49:6f:f6:25:
    46:21:28:36:d3:44:71:b5:83:5f:b4:44:67:15:c1:
    c2:54:33:00:82:a7:dd:96:d3:92:4c:d0:2b:99:b8:
    94:81:9e:7c:19:18:78:62:ff:43:86:b5:95:80:39:
    2e:72:35:df:f9:41:30:27:78:92:f2:40:bc:a9:c8:
    25:9f:1f:ef:02:25:b1:e3:ec:3d:17:35:17:27:b9:
    dc:ad:fe:69:30:17:56:70:36:9b:f9:21:6b:57:5c:
    d4:ed:26:48:1c:31:a6:44:24:7a:26:85:b6:99:75:
    6e:6a:83:53:3e:cf:90:86:e1:17:2e:da:8b:31:ec:
    dc:7c:27:ba:ff:05:66:31:c6:fd:b0:e3:cd:9a:88:
    2c:75
publicExponent: 65537 (0x10001)
privateExponent:
    2d:09:80:bd:a6:f7:dc:c4:27:15:5a:11:75:e0:96:
    ……………………省略部分内容……………………
    b5:d1:71:73:73:89:c5:57:7b:f0:4e:8e:62:14:71:
    35
prime1:
    00:df:95:57:36:73:87:ee:ed:8c:bf:74:12:88:2b:
    ……………………省略部分内容……………………
    54:eb:0f:60:63:1a:2a:ab:97
prime2:
    00:cc:17:42:79:16:2c:7e:6c:a6:b4:c9:d2:4a:cc:
    ……………………省略部分内容……………………
    9e:df:03:7d:87:d5:9d:19:d3
exponent1:
    49:eb:f2:5d:ca:6c:d3:0e:2f:4e:cd:6d:a3:1f:e2:
    ……………………省略部分内容……………………
    fc:f1:a4:88:9f:8a:24:19
exponent2:
    00:a9:27:46:12:f2:0b:e2:a4:ce:ee:dc:af:8d:0b:
    ……………………省略部分内容……………………
    14:db:26:1b:6e:ef:df:8b:bd
coefficient:
    54:00:d2:f7:04:e5:46:85:8c:17:44:7b:b8:ba:b5:
    ……………………省略部分内容……………………
    de:39:c8:ed:cc:73:82:a1:0d:93:3e:78:67:4b:91:
    cc:63:0f:8d:df:fd:24:d4
writing RSA key
-----BEGIN RSA PRIVATE KEY-----
MIIEowIBAAKCAQEAsj9R+Htkp7V7KT/QwPiKBHEpuj+O+SgeSF4NBEajzUeTH2lL
uGnTcO73cQPTC3ENDfs64wSLeeq4zPhBSlHLaJLwZvhhH/vkDF4N8uaC25HDQ/5O
……………………省略部分内容……………………
ytHmckRi9SjPKZJkQmK4cM5fTHlqQteNKi5lTOxwLNwUGY4rZmlsd7sQ6PNEIVqG
C6hGB8LbC+kplctzmKinK945yO3Mc4KhDZM+eGdLkcxjD43f/STU
-----END RSA PRIVATE KEY-----

各个部分代表的意思:
modulus , n
publicExponent , e
privateExponent , d
prime1 , p
prime2 , q
exponent1 , d mod (p-1)
exponent2 , d mod (q-1)
coefficient , (inverse of q) mod p

 

暂时就写这么多吧……

  1. 2012年4月7日15:35

    霸气长存。最近收不到砖家的feed咯。

    [回复]

[cusFace:84] [cusFace:83] [cusFace:82] [cusFace:79] [cusFace:67] [cusFace:66] [cusFace:65] [cusFace:54] [cusFace:53] [cusFace:52] [cusFace:51] [cusFace:50] [cusFace:49] [cusFace:48] [cusFace:47] [cusFace:44] [cusFace:43] [cusFace:42] [cusFace:41] [cusFace:40] [cusFace:39] [cusFace:38] [cusFace:37] [cusFace:36] [cusFace:35] [cusFace:34] [cusFace:33] [cusFace:32] [cusFace:31] [cusFace:30] [cusFace:29] [cusFace:28] [cusFace:27] [cusFace:26] [cusFace:25] [cusFace:24] [cusFace:23] [cusFace:22] [cusFace:21] [cusFace:20] [cusFace:19] [cusFace:18] [cusFace:17] [cusFace:16] [cusFace:15] [cusFace:14] [cusFace:13] [cusFace:12] [cusFace:11] [cusFace:10] [cusFace:09] [cusFace:08] [cusFace:07] [cusFace:06] [cusFace:05] [cusFace:04] [cusFace:03] [cusFace:02] [cusFace:01] [cusFace:00]