（一）公钥密码学
一、注意点
1、和以往的密码学的根本不同：不是基于置换和替代，而是基于数学函数
2、公钥密码和只使用一个密钥的传统密码学不同，它是非对称的，使用两个独立的密钥
3、公钥密码学仅限于用在密钥管理和签名中。
二、概念
1、非对称密钥：
2、公钥证书：
3、公钥密码（非对称密码）：
4、公钥基础设施：
三、密钥分配问题
Diffie Hellman算法
四、数字签名问题
五、公钥密码体制
1、公钥密码体制之——保密性
流程如下：A产生公钥和私钥，并把公钥发给B，B用公钥加密，并把密文发给A，A用私钥解密得到明文
即：B：Y = E(PUb, X) A：X = D(PRb, Y) 其中B产生PRb,PUb
2、公钥密码体制之——认证
流程如下：A向B发送消息前，先用A的私钥对消息进行加密，B则用A的公钥进行解密
数字签名原理：由于是用A的私钥对消息加密，所以只有A才能够加密，因此，整个加密后的消息就是数字签名
认证源和数据完整性：因为只有A的私钥才能产生上述的消息，因此该消息可以用于认证消息源和数据完整性
3、加密认证函数部分
只对认证符这一小块数据进行加密，它是整个消息的函数，确保对消息的任何修改都会引起认证符的变化
能防止对消息的修改，但是不能防止对消息的窃听
4、保密性和认证
发送方用自己的私钥对消息加密，得到数字签名，再用对方的公钥加密，得到保密性
这样就同时满足了保密性和认证。但是需要执行四次复杂的加密算法
5、公钥密码体制的应用
加解密
数字签名
密钥交换
6、四种常见的公钥密码
加解密 数字签名 密钥交换
RSA @ @ @
椭圆曲线(ECC) @ @ @
Diffie Hellman @
DSS @
7、对公钥密码的要求（凭什么人家无法解密破解）
有三点
1、已知公钥求不了私钥
2、已知公钥和密文求不了明文
3、加解密的顺序可交换（即，两个密钥都能成为公钥，另一个为私钥）
实现：
单向陷门函数 单向函数（求见数论部分）
8、攻击
1、穷举攻击（应对：可使用长密钥）
2、找出上述第二点的函数（反正现在还没找到）
3、密文匹配攻击：使用公钥加密所有可能的明文然后和密文匹配（明文后面加一个随机数你就凉了）
（二）RSA算法
一、注意
1、是分组密码
2、明文和密文都是0-n-1之间的整数，n通常问1024二进制，即n<2^1024
2、使用乘积（乘方）运算
二、求解过程
1、选择两素数p=17, q=11
2、计算 n=pq = 187
3、计算 φ(n) = (p-1)(q-1) = 160
4、选择 e 作为公钥，其中 e 要和 φ(n) 互素，这里选择 e=7
5、确定 d，其中de ☰ 1 mod 160
6、得到公钥：{e, n} 私钥：{d, n}
7、假设明文M= 88，则密文C = M^e mod n = 88^7 mod 187 = 11
其中如果p，q足够大，攻破是不可行的
三、攻击
穷举攻击：选择大位数的e，d即可
数学攻击：
计时攻击
基于硬件的故障攻击
选择密文攻击
四、证明
证明就是证M = C^d mod n (假设是用e加密）
C^d mod n
= (M^e)^d mod n
= (M^ed) mod n
因为φ(n) = (p-1)(q-1)
ed mod φ(n) = 1
所以有ed = kφ(n) + 1
原式 = M^(kφ(n)+1) mod n
= M^(k(p-1)(q-1)+1) mod n
= M^(k(p-1)(q-1)+1) mod pq
首先证明M^(k(p-1)(q-1)+1) mod p = M mod p
情况一：
M不和p互素，则式子两边的值都为0
情况二：
M和p互素
M^(k(p-1)(q-1)+1) mod p
= (M mod p)* ((M^(p-1))^k(q-1) mod p) mod p
由费马定理可知，当M 和 p 互素时M^(p-1) mod p = 1
= M mod p
所以M^(k(p-1)(q-1)+1) mod p - M mod p = 0
(M^(k(p-1)(q-1)+1) - M) mod p = 0'
同理(M^(k(p-1)(q-1)+1) - M) mod q = 0
所以(M^(k(p-1)(q-1)+1) - M) mod pq = 0
(M^(k(p-1)(q-1)+1) - M) mod n = 0
存在k，使得 (M^(k(p-1)(q-1)+1) - M) = kn
即M^(kφ(n)+1) mod n = M