公开密钥加密
公开密钥加密，也称为非对称(密钥)加密，是指一对加密密钥与解密密钥，这两个密钥数学相关。用某用户密钥加密后所得的信息，只能用该用户的解密密钥才能解密。如果知道了其中一个，并不能计算出另外一个。因此如果公开了一对密钥中的一个，并不会危害到另外一个的秘密性质。称公开的密钥为公钥；不公开的密钥为私钥。
RSA
1977年在麻省理工学院工作的三位数学家Ron Rivest、Adi Shamir、Leonard Adleman一起提出了一种算法，以他们三人姓氏开头字母组成名称，即RSA算法。RSA加密算法是一种非对称加密算法，在公开密钥加密和电子商业中广泛使用。
给出两个大质数，计算它们的乘积非常方便，但要是想对这个乘积做因数分解则非常困难，这个性质决定了RSA算法的可靠性。今天还没有任何可靠的攻击RSA算法的方式，通过暴力破解可破解短密钥，最长被破解密钥为768位，这威胁到了1024位密钥的安全性。但长密钥如2048位则可以认为是不可被破解的。
预备知识
- 欧拉函数，在数论中，对正整数n，欧拉函数φ(n)是小于或等于n的正整数中与n互质的数的数目。例中要使用欧拉函数的几条性质：
- 如果n=1，则φ(1) = 1
- 如果n是质数，则φ(n)=n-1
- 如果n可以分解成两个互质的整数之积，如n = p1p2，则φ(n) = φ(p1p2) = φ(p1)φ(p2)
- 欧拉定理，是RSA算法的核心，如果两个正整数a和n互质，则a的φ(n)次方被n除的余数为1，即a^φ(n) ≡ 1 (mod n)
- 模反元素，如果两个正整数a和n互质，那么一定可以找到整数b，使得ab被n除的余数是1，即ab ≡ 1 (mod n)
以维基百科中一个实例说明RSA操作过程。
公钥与私钥的产生
假设Alice希望通过一个不可靠媒体接收Bob的一条私人信息
- Alice随机选取两个大的质数p和q，其中p!=q，N=pq
- 根据欧拉函数，求得r = φ(N) = φ(p)φ(q) = (p-1)(q-1)
- 选取小于r的整数e，e与r互质(e⊥r)，计算e与r的模反元素d，即ed ≡ 1 (mod φ(N))；经化简得ed - kφ(N) = 1，其中已知e和φ(N)，实际就是解二元一次方程的整数解，其中两个已知数还满足互质，可通过扩展欧几里得算法(辗转相除法的扩展)算出d和倍数k
- 将p与q销毁，此时仅剩数N、r=φ(N)、e、d
(N,e)是公钥，(N,d)是私钥。Alice将她的公钥(N,e)传给Bob，保留私钥(N,d)。这样产生的公钥和私钥可靠的原因是若要解密通信内容，需要知道d，若在有效保管d的条件下，想要通过e计算出d，则需通过
- ed ≡ 1 (mod φ(N))，要计算d需知道φ(N)
- φ(N) = φ(p)φ(q) = (p-1)(q-1)，若要知道φ(N)需知道p和q
- N = pq，也就是需要对N做因数分解，这是非常困难的
此时Bob知道Alice产生的N和e。假设Bob需要向Alice发送信息m
加密消息
Bob需使用预先与Alice协商好的格式将m转换为小于N的整数n，如将字符串每个字符转换为unicode码后连接为一个数字。因为需要n<N，若信息过长可分多片传输。通过公式
n^e ≡ c (mod N)
计算出c，c即为加密结果
解密消息
Alice接收到Bob发送的信息c，利用公式
c^d ≡ n (mod N)
计算出n，n即为信息内容
证明
为什么c^d ≡ n (mod N)可以解码密文？已知条件ed ≡ 1 (mod φ(N))可转换为ed = 1 + kφ(N)，证明的桥梁是c^d ≡ n^(ed) (mod N)，证明中需使用同余性质
- 整除性，
a ≡ b (mod m)，可转换为a - b = k * m - 传递性，
a ≡ b (mod m), b ≡ c (mod m)，则a ≡ c (mod m) - 基本运算，包括
a ≡ b (mod m), c ≡ d (mod m)，则a±c ≡ b±d (mod m), ac ≡ bd (mod m)a ≡ b (mod m)，则an ≡ bn (mod m), a^n ≡ b^n (mod m)
证明分两种情况
1) 若n与N互质, gcd(n, N)=1
由加密公式n^e ≡ c (mod N)，因为n^e和c关于模N同余，依照基本运算可得c^d ≡ (n^e)^d ≡ n^(1+kφ(N)) ≡ n*n^(kφ(N)) (mod N)，即需证明c^d ≡ n*n^(kφ(N)) (mod N)
n和N满足欧拉定理得n^φ(N) ≡ 1 (mod N)，因此c^d ≡ n*n^(kφ(N)) ≡ n (mod N)
2) 若n与N不互质, gcd(n, N)!=1
因为N=pq，因此gcd(n, N)=p或gcd(n, N)=q，其中要求n<N。
假设gcd(n, N)=p，则n=zp。因为n和q互质，依照欧拉定理，n^(q-1) ≡ 1 (mod q)，依照同余性质，n^[(q-1)(p-1)k]*n ≡ n (mod q)，此处k指ed = 1 + kφ(N)中的k，化简得n^(ed) ≡ n (mod q)；此时将n=zp代入，同时转换为等式得zp*[(zp)^(ed-1) - 1] = k'q，由此看出zp可整除k’q，k’是p的整数倍，即k'=lp，因此原式又可以写为n^(ed) = lpq + n，于是得到n^(ed) ≡ n (mod N)，通过桥梁c^d ≡ n^(ed) (mod N)和同余传递性得到结果c^d ≡ n (mod N)。
同理可证gcd(n, N)=q的情况
TLS/SSL
安全套接层(SSL)是一种安全协议，在网景公司推出首版Web浏览器的同时提出，目的是为网络通信提供安全及数据完整性保障，SSL在传输层中对网络通信进行加密。SSL采用公开密钥技术，在通信双方协商时可选择加密算法，而其中使用广泛的便是RSA算法。TLS是SSL标准化的产物，由IETF制定，从技术上讲，TLS1.0与SSL3.0的差异非常微小。
SSL协议的优势在于它是与应用层协议独立无关的。高层的应用层协议，如HTTP、FTP、Telnet等，能透明的建立于SSL协议之上。SSL协议在应用层协议通信之前就已经完成加密算法、通信密钥的协商以及服务器认证工作。在此之后应用层协议所传送的数据都会被加密，从而保证通信的私密性。
SSL工作方式
RSA等公开密钥加密技术效果好，但相比对称密钥加密，效率并不高。在实际应用中，SSL结合公开密钥和对称密钥实现功能：通信内容通过双方协商的会话唯一对称密钥加密提高效率，此对称密钥则通过服务器的RSA公钥加密提供安全传输。为了保证公钥和源的可信，服务器通过数字证书传递公钥以便客户端验证并使用。这些工作都在双方握手过程中完成
ClientHello，客户端向服务器发送ClientHello消息，信息内容包括
- 加密通信版本，如TLS1.0
- 一个客户端生成的随机数，用于随后生成会话密钥
- 支持的加密(cipher suite)和压缩算法
ServerHello，服务器向客户端发送ServerHello消息
- 确认使用的加密通信版本，若支持版本不一致则关闭通信
- 一个服务器生成的随机数，用于随后生成会话密钥
- 确认使用的加密方法和压缩算法
- 服务器端证书，其中包含协商确定的加密方法的公钥
- 若需客户端身份认证，则包含此项用于请求客户端证书(如网银要求连接U盾提供证书)
客户端回复，客户端接收ServerHello消息后验证服务器端证书，从证书中取出公钥；客户端需生成第三个随机数，称为pre-master key，然后利用已有的3个随机数生成会话密钥，之后回复消息
- 若需客户端验证，则发送客户端证书
- 利用公钥加密后的pre-master key
- 编码改变通知，即说明之后内容都通过加密传输
- 握手结束通知，是之前发送的所有内容的hash，用于校验
服务器回复，服务器收到信息后利用私钥解密得到pre-master key，利用所有3个随机数生成会话密钥，然后回复消息
- 若需客户端验证，且验证不通过，则关闭通信
- 编码改变通知，即说明之后内容都通过加密传输
- 握手结束通知，是之前发送的所有内容的hash，用于校验
使用3个随机数生成会话密钥，因为要保证每个对话都有不同的密钥，由双方独立生成的伪随机数可能并非真正随机，引入pre-master key增加自由度保证随机性可靠；因为之前两个随机数都是明文传输，通过加密传输pre-master key也保证会话密钥的安全
Cipher suite
TLS/SSL在握手过程中需要协商包括认证(authentication)、加密(encryption)、MAC(message authentication code)、密钥交换算法等安全设置，这些安全设置统称为Cipher suite。每一种Cipher suite算法都有一个名称
- key exchange algorithm，例如ECDHE_RSA，用于客户端和服务器确定是否或如何在握手阶段进行身份认证
- encryption，例如AES_128_GCM，用于加密信息
- MAC，例如SHA256，用于生成信息的摘要
- pseudorandom function，用于生成master key的各伪随机数生成函数
TLS/SSL握手阶段，客户端通过ClientHello发送支持的Cipher suite列表，服务器通过ServerHello返回从这个列表中选取的算法。
数论太神奇了