概述

非对称加密
(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
则验证签名成功。