Blog

home category

非对称加密算法RSA和应用I - RSA 和 TLS/SSL

21 Jun 2014

公开密钥加密

公开密钥加密,也称为非对称(密钥)加密,是指一对加密密钥与解密密钥,这两个密钥数学相关。用某用户密钥加密后所得的信息,只能用该用户的解密密钥才能解密。如果知道了其中一个,并不能计算出另外一个。因此如果公开了一对密钥中的一个,并不会危害到另外一个的秘密性质。称公开的密钥为公钥;不公开的密钥为私钥。

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返回从这个列表中选取的算法。

数论太神奇了

参看