一、非对称密码
1.基本介绍
- 又被称为公钥密码*或是双密钥密码*
- 基于数学函数而不是代替和换位操作
- 由两个密钥形成一个密钥对，其中一个密钥为密钥拥有者保管(私钥)，另一个密钥公开(公钥)。
- 支持数字签名，用两个密钥中的任何一个加密的内容，都可以用另一个解密。
- 速度比对称密码*慢
- 主要用于密钥管理和数字签名
2.公钥密码*要求
- 参与方B容易通过计算产生一对密钥（公开密钥 KU 和私有密钥 KR）
- 在知道公开密钥和待加密报文 M 的情况下，对于发送方A，很容易通过计算产生对应的密文 C：
C = E K U ( M ) C = E_{KU}(M) C=EKU(M)
- 接收方B使用私有密钥容易通过计算解密所得的密文，以便恢复原来的报文 M：
M = D K R ( C ) = D K R ( E K U ( M ) ) M = D_{KR}(C) = D_{KR}(E_{KU}(M)) M=DKR(C)=DKR(EKU(M))
- 敌对方即使知道公开密钥 KU，要确定私有密钥 KR 在计算上也是不可行的
- 敌对方即使知道公开密钥 KU 和密文 C ，要想恢复原来的报文 M 在计算上也是不可行的
- 两个密钥中的任何一个都可以用来加密，对应的另一个密钥用来解密（不是对所有的公钥*都适用，如DSA只用于数字签名）
M = D K R ( E K U ( M ) ( 机 密 性 实 现 ) M = D K U ( E K R ( M ) ) ( 数 字 签 名 实 现 ) M=D_{KR}(E_{KU}(M) \ (机密性实现)\\ M=D_{KU}(E_{KR}(M)) \ (数字签名实现) M=DKR(EKU(M) (机密性实现)M=DKU(EKR(M)) (数字签名实现)
2.单向陷门函数
单项陷门函数是满足下列条件的函数 f：
- 正向计算容易。即如果知道了公钥 PK和消息 x，容易计算密文 y = f P K ( x ) y = f_{PK}(x) y=fPK(x)
- 在不知道私钥 SK 的情况下，反向计算是不可行的。（所谓的计算不可行是指计算上相当复杂，在有限时间和成本范围内很难得到想要的结果，已无实际意义）。即如果只知道消息 y 二不知道密钥 SK ，则计算 x = f − 1 ( y ) x = f^{-1}(y) x=f−1(y) 是不可行的。
- 在知道私钥 SK 的情况下，反向计算是容易的。即如果同时知道消息 y 和密钥 SK，则计算 x = f S K − 1 ( y ) x = f^{-1}_{SK}(y) x=fSK−1(y) 是容易的。这里的密钥 SK 相当于陷门，和 PK 配对使用。
公钥加密*中的公钥用于单向陷门函数的正向（加密）计算，私钥用于反向（解密）计算。
- 仅满足上述前两条的函数称为单向函数，第三条称为陷门性，密钥 SK 称为陷门信息。
- 单向陷门函数 f是公开的
- 上述第二条性质表明，窃听者由截获的密文 y = f P K ( x ) y = f_{PK}(x) y=fPK(x) 推测消息的明文 x 是不可行的。
也就是说，对于单向陷门函数而言，它是指除非知道某种附加信息，否则这样的函数在一个方向上计算容易，在相反的方向上不能计算；有了附加信息，函数的逆就可以容易计算出来。
3.本原元和离散对数
- 本原元（生成元、基元或根元）
对于一个素数 q,如果数值 a m o d q ， a 2 m o d q ， ⋯ a q − 1 m o d q a mod q，a^2 mod q，\cdots a^{q-1} mod q amodq，a2modq，⋯aq−1modq 是各不相同的正数，并且以某种排列方式组成了从 1 到 q-1 的所有整数，则称整数 a 是素数 q 的一个本原元。本原元也成为生成元、基元或根元。(欧拉定理中的内容)
- 离散对数
对于一个整数 b ，和素数 q 的一个本原元 a ，可以找到唯一的一个指数 i ，使得
b
=
a
i
m
o
d
q
(
0
≤
i
≤
q
−
1
)
b = a^i mod q(0\leq i\leq q-1)
b=aimodq(0≤i≤q−1)
成立。则指数 i 称为 b 的以 a 为底的模 q 的离散对数。
对于给定的 a , i 和 q ，容易计算出 b；在最坏情况下需执行 i 次乘法，并且存在计算出 b 的有效算法。但是给定 b ，a 和 q ，计算出 i 一般非常困难，这就是离散对数问题的难解性。
二、RSA
1.算法描述
- 安全性建立在大整数因子分解的困难性问题之上，利用了单向陷门函数的原理。
- RSA密码*的 明文空间 M = 密文空间 C = Zn (表示 mod n 所组成的整数空间，即其取值范围为 0 ~ n-1)。
2.密钥生成
首先，选择两个互异的大素数 p 和 q（保密），计算 n = p q n = p q n=pq (公开)， φ ( n ) = ( p − 1 ) ( q − 1 ) \varphi (n) = (p-1)(q-1) φ(n)=(p−1)(q−1) (保密)，选择一个随机整数 e ( 0 < e < φ ( n ) ) e(0 < e < \varphi(n)) e(0<e<φ(n)) (公开)， 满足 g c d ( e , φ ( n ) ) = 1 gcd(e, \varphi(n)) = 1 gcd(e,φ(n))=1 。计算 d = e − 1 m o d φ ( n ) d = e^{-1} mod \varphi(n) d=e−1modφ(n) (保密)。 确定：公钥 KU = {e,n}, 私钥 KR = {d,p,q}, 或 KR = {d, n} 。
3.加密
已知：明文 M < n (因为所有明文和密文空间均为 Zn，即在 0 ~ n -1 的范围内；实际处理时对于 M >= n 的情形，则需要对大报文进行分组，确保每一个分组满足该条件) 和公钥 KU = {e,n}。计算密文：
C
=
M
e
m
o
d
n
C = M^e mod n
C=Memodn
4.解密
已知：密文 C 和私钥 KR = {d, n}。计算明文：
M
=
C
d
m
o
d
n
M = C^d mod n
M=Cdmodn
5.算法归纳
- 选择两个互异的大素数 p 和 q，为了保证安全性，通常要求每个素数均大于 10100 (即超过100位的十进制数)。
- 计算 n = p q n = p q n=pq (公开)， φ ( n ) = ( p − 1 ) ( q − 1 ) \varphi (n) = (p-1)(q-1) φ(n)=(p−1)(q−1) (保密)。
- 选择一个和 φ ( n ) \varphi (n) φ(n)互素的数，令其为 e。
- 计算 d = e − 1 m o d φ ( n ) d = e^{-1} mod \varphi (n) d=e−1modφ(n) (保密)
- 选好这些参数后，将明文划分成块，使得每个明文报文长度满足 M < n。加密 M 时，计算 C = M e m o d n C = M^e mod\ n C=Memod n，解密 C 时，计算 M = C d m o d n M = C^d mod \ n M=Cdmod n。由模运算的对称性可以证明，在确定的范围内，加密和解密函数是互逆的。为实现加密，需公开 {e, n} ，为实现解密需要 {d, n} 。