小组内部每周都会有人进行技术分享，这周leader安排到了我。想了很久给大家分享什么内容，但觉得都不怎么合适，感觉这些技术他们都已有所了解，且比我掌握的可能更深刻一些。思来想去最后我选了一个大家接触比较少且自己最近在这方面的看的又比较多的技术内容——公开密钥加密。这里将分享的内容整理为一篇文章记录在此。
内容提要如下：
- 基本的公开密钥加密方案
- 应用
- 真实世界的安全协议
基本的公开密钥加密方案
首先我们知道目前密文加密主要有两种方式，一种是对称加密，一种是非对称加密，也称公开密钥加密，其实从加密的性能和加密方法多样性的角度来看，对称加密要比公开密钥加密更为优秀，但是对称加密存在一个致命的问题：密钥分发的难题。对于在加密中最为重要的密钥来说，如果不可以保证它的安全性，那么整个加密方案也就没有存在的意义。而公开密钥加密利用一种称为单向陷门函数的方式，轻松解决了这个密钥分发的问题。
通常我们在加密传输时，多数选择的方案是对称加密和公开密钥加密同时使用，首先使用公开密钥加密将密钥安全的传输给对方，然后双方再使用该密钥进行对称加密传输真正的密文。这个方案简单完美的同时保证了加密的高效性和密钥分发的安全性。
单向陷门函数
单向陷门函数是指具有单向和陷门两个特性的一类特殊函数。
单向
单向简单的可以说是函数在一个方向上易于计算而反方向却难于计算。比如生活中的水往低处流、破镜难重圆等，都是一个单向函数的体现。
陷门
陷门是指一个可以对单向函数求逆的后门
对于普通的单向函数来说，原则上其没有可能可以从输出逆向反推输入，但是这个后门的存在，使得我们可以反向推导。
如：拆开表是一个很好的陷门单向函数的例子，我们将表拆成数百片小片非常容易，而把这些小片重新组装成能够工作的表则非常的困难，但我们如果通过秘密消息（表的装配指令），就可以很容易将表复原。这里的“表的装配指令”就是上述的陷门
背包加密算法
背包加密是最早被提出来的公钥加密体系之一，但是现在已经证实其不安全
背包加密算法基于的是子集和问题，可简单描述为下：
有 W0,W1,W2…Wn-1
要求找到
- 生成超递增背包
- 超递增闭包转换为常规背包
- 常规背包为公钥
- 超递增背包和转换因子为私钥
例子
生成的超递增背包：2，3，7，14
选取 乘数m 和模数n(大于所有数的和)，m和n互质==> m=11 n=27
计算常规背包为 22，6，23，19
明文： 1001
则密文 C：22+19=41
私钥为超递增背包 2，3，7，14 和 m-1 mod n = 5
解密 ：C * m-1 mod n = 41 * 5 mod 27 = 16
得 16 = 14 + 2
明文 => 1001
RSA
基于：大数的因式分解
例子：
大素数 p=3、q=11
N = p*q = 33
e 与 (p-1)*(q-1)=20 互素 e选择3
公钥 (N,e) = (33,3)
私钥d 为 e-1 mod (p-1)*(q-1) = 3 ^-1 mod 20 =7
设 明文 M = 15
则密文 C = M ^e mod N = 15 ^ 3 mod 33 = 9
解密： M = C ^d mod N = 9 ^7 mod 33 = 15
保障不被破解的关键：N无法被分解
即无法获取p、q的值，则不可以获取私钥d的值
Diffie-Hellman密钥交换算法
用于共享对称密钥
基于离散对数问题
给定g， x=g^k 求k, k = logg(x)
给定 g、p、g^k mod p
求k 很难
A 选择a 计算得到 g^a mod p
B 选择b 计算得到 g^b mod p
互换
A得到 g^ab mod p
B得到 g^ab mod p
椭圆曲线加密（ECC）
优势：获取同样的加密级别，需要的二机制位少
劣势：计算复杂