小皮博客 | Xiaopi's Blog

RSA算法验证过程及在PKI各个环节中应用原理介绍

概述

非对称加密
(1)乙方生成两把密钥(公钥和私钥)。公钥是公开的,任何人都可以获得,私钥则是保密的。
(2)甲方获取乙方的公钥,然后用它对信息加密。
(3)乙方得到加密后的信息,用私钥解密。

RSA加密算法

RSA加密算法简史

  RSA是1977年由罗纳德·李维斯特(Ron Rivest)、阿迪·萨莫尔(Adi Shamir)和伦纳德·阿德曼(Leonard Adleman)一起提出的。当时他们三人都在麻省理工学院工作。RSA就是他们三人姓氏开头字母拼在一起组成的。

公钥与密钥的产生

  假设Alice想要通过一个不可靠的媒体接收Bob的一条私人讯息。她可以用以下的方式来产生一个公钥和一个私钥:

随意选择两个大的质数p和q,p不等于q,计算N=pq。
根据欧拉函数,求得r = (p-1)(q-1)
选择一个小于 r 的整数 e,求得 e 关于模 r 的模反元素,命名为d。(模反元素存在,当且仅当e与r互质)
将 p 和 q 的记录销毁。
(N,e)是公钥,(N,d)是私钥。Alice将她的公钥(N,e)传给Bob,而将她的私钥(N,d)藏起来。

加密消息

  假设Bob想给Alice送一个消息m,他知道Alice产生的N和e。他使用起先与Alice约好的格式将m转换为一个小于N的整数n,比如他可以将每一个字转换为这个字的Unicode码,然后将这些数字连在一起组成一个数字。假如他的信息非常长的话,他可以将这个信息分为几段,然后将每一段转换为n。用下面这个公式他可以将n加密为c:

  n^e ≡ c (mod N)

计算c并不复杂。Bob算出c后就可以将它传递给Alice。

解密消息

Alice得到Bob的消息c后就可以利用她的密钥d来解码。她可以用以下这个公式来将c转换为n:

  c^d ≡ n (mod N)

得到n后,她可以将原来的信息m重新复原。

实例应用(加密解密)

图1 加密解密

构造密钥

P=3, Q=17
N= 3 * 17 = 51
R=(P - 1) * (Q - 1) = (3 - 1) * (17 - 1) = 32
此时,小于32且和32互质的数有 3, 5, 7, 9, 11, 13, 15, 17 …
选定E = 13, 则 5 * 13 (mod 32) = 65 (mod 32) = 1, 求出D = 5
此时得到一组密钥, 其中公钥 (13, 51), 私钥(5, 51)。

加密数据

先将明文 “ABC” 数字化,这个过程可以叫做编码,对应将 A~Z等26个字母转换为 1~26个数字, 则明文 M = ABC
表示为 M1 = 1, M2 = 2, M3 = 3
C1 = (1 ^ 13) (mod 51) = 1
C2 = (2 ^ 13) (mod 51) = 8192 mod 51 = 160  余 32
C3 = (3 ^ 13) (mod 51) = 1594323 mod 51 = 31261 余数 12
则密文C = 1, 32, 12

解密数据过程(使用私钥5, 51)

M1 = (1 ^ 5) (mod 51) = 1
M2 = (32 ^ 5) (mod 51) = 33554432 mod 51 = 657930 余数 2
M3 = ( 12 ^ 5) (mod 51) = 248832 mod 51 = 4879 余数 3
显然,根据逆运算已经得出了 明文 M = 123,即根据编码规则可以还原出 ABC

实例应用(数字签名)

图2 数字签名

结合这里使用的特殊hash算法的特点(摘要之后,少量修改就会带来签名结果很不一样,所以可以用来验证明文是否被修改过,抗抵赖和保证完整性)。使用私钥进行加密之后(身份鉴别,一般情况下,私钥在使用时还需要输入一个使用密码,类似于U盾这样的,保证证书即使丢失,也具有安全性。U盾一般5次输错密码就永久销毁了)得到签名S。

数字签名过程

密钥仍然使用上面环节的

 
明文ABC : M对应为123  
通过32位以内的Fibonacci哈希算法(实际应用过程中可能是MD5等,这里为了便于计算) 

H = M * 40503 >> 14;  
图例中 H1 = 2, 4, 7  
S1 = (2 ^ 5) mod 51 = 0 余数 32
S2 = (4 ^ 5) mod 51 = 1024 mod 51 = 20 余数 4
S3 = (7 ^ 5) mod 51 = 16807 mod 51 = 329 余数  28
则可将原文 123, 及原文产生的签名 32, 4, 28发给使用者。

此时,使用者拿到发送者使用独一无二的私有密钥签名过的 32, 4, 28这个数字签名了。如果使用任何其他密钥签名都无法得出这一串数字。从而论证了发起者的身份,而原文1,2,3做了任何修改,得出的哈希值都会有很大不一样,发起者无法抵赖,一旦修改,得出的哈希值变化了,产生的数字签名也会对应的变化。并且保证了数据的完整性。
注意,如PPT所说一样,这里并不能保证不让其他人看到原文信息。

验证签名

图3 验证签名


使用者使用原文M=123,通过同样的哈希算法(算法公开,很容易计算出哈希值,但是不容易通过哈希值来推断或者伪造原文)(如果加上原文中时间戳,则更有不可抵赖的效果了)可以得出
H= 2, 4, 7
而使用者同时根据S=32, 4, 28,使用公钥(13, 51)可以还原哈希H如下
(32 ^ 13) mod 51 = 2
(4 ^ 13) mod 51 = 67100864 mod 51 = 4
(28 ^ 13) mod 51 = 7
则验证签名成功。

版权声明

本文标题:RSA算法验证过程及在PKI各个环节中应用原理介绍

文章作者:盛领

发布时间:2017年03月25日 - 14:38:25

原始链接:http://blog.xiaoyuyu.net/post/4b5ea3c6.html

许可协议: 署名-非商业性使用-禁止演绎 4.0 国际 转载请保留原文链接及作者。

如您有任何商业合作或者授权方面的协商,请给我留言:sunsetxiao@126.com

盛领 wechat
欢迎您扫一扫上面的微信公众号,订阅我的博客!
坚持原创技术分享,您的支持将鼓励我继续创作!