公钥密码

29 12月
  • RSA
  • (补充一)Diffie-Hellman 密钥交换
  • (补充二)有限域的椭圆曲线离散对数问题

1. 公钥密码(public-key cryptography)

公钥密码指在加密和解密时用不同的密钥,又称为非对称密码(asymmetric cryptography)

通常使用公钥加密,用私钥解密

公钥密码出现在20世纪70年代,现代计算机行业和互联网行业的安全体系很大程度上依赖公钥密码,堪称密钥学历史上最伟大的发明。

对称密码最大的问题是“密钥的配送”,因为加解密用相同的密钥,而且加密算法是公开的,如果加密后密文与密钥一起通过网络传给接收方,攻击者就能通过网络解获密文和密钥,根据加密算法反解密。所以通常密文和密钥不同时传输,而是分开传输:

  • 事先双方共享密钥:只局限在少数人时可以,但人数一多就不可行了。例如公司1000人,我要和其他999人通信,需要999个密钥,那整个公司需要事先准备 1000 * 999 / 2 = 499500 个密钥,不现实。
  • 通过密钥中心分发密钥:公司有个密钥分配中心(Key Distribution Center,KDC),员工A和员工B通信时,密钥中心会先用伪随机数生成器生成一个临时密钥,然后用员工A和员工B的工号(也可以是其他标识符)对临时密钥加密,并分发给双方。员工A获得密钥后用自己的工号对密钥解密后得到临时密钥,对明文加密。员工B获得密钥后用自己的工号对密钥解密后得到临时密钥,对密文解密。密钥分发中心缺点是机房负荷大,一旦出故障,整个公司的通信将瘫痪。
  • 通过 Diffie-Hellman 密钥交换:Diffie-Hellman密钥交换算法是1976年由Whitfield Diffie和Martin Hellman共同发明的一种算法。名字虽然叫密钥交换,但实际双方并没有真正交换密钥,而是通过算法生成一个相同的共享密钥,因此也被称为Diffie-Hellman密钥协商。双方在通信时,交换一些即使被攻击者窃取都没关系的信息,双方各自用这个信息来生成相同的密钥进行加密和解密。
  • 通过公钥密码:公钥密码用于加密,即使被攻击者窃取也没关系,这就根本上回避了密钥配送问题。私钥用于解密,传输过程中不传输私钥,攻击者无法获取到私钥。

公钥和私钥间有着密切的数学关系,无法单独生成。与对称密码不同,公钥密码中通信是由“接收者”发起的。

  1. 接收者生成一对公钥和私钥,私钥由接收者保存,公钥发送给消息的发送者
  2. 发送者用收到的公钥进行加密,将密文发送给接收者
  3. 接收者用本地的私钥进行解密

公钥密码从根本上解决了密钥的配送问题,但也不是完美的。缺点是:公钥在传输过程中虽不怕被窃取,但要防止被篡改,所以需要公钥认证,而且处理速度只是对称密码的百分之一,因此对称密码不会消失,现实场景中会在安全与速度间选取平衡。

1.1 RSA

密码学算法基于质数,例如分解大质数

欧拉,高斯,黎曼等前赴后继地研究质数,质数是宇宙留给人类的密码。

RSA(Rivest-Shamir-Adleman)由3位开发者Rom Rivest,Adi Shamir,Leonard Adleman的名字首字母命名,用于公钥算法,数字签名。

基石是借助 mod 运算,典型的模运算是钟表。例如从0点开始,时针前进3指向3点,前进15也指向3点,即在时针的运算是 mod 12。前进190指向几点?190 mod 12 = 10,时针指向10点。

RSA 加密:

  • 算法:密文 = 明文E mod N,即明文的E次方mod N的结果。相比对称密码算法,将比特位翻来覆去地xor,RSA算法是如此简洁。
  • 公钥:算法里的 E,N

RSA 解密:

  • 算法:明文 = 密文D mod N
  • 私钥:算法里的 D,N

其中 E,D,N这三个数就是生成密钥对,步骤如下:

第一步:求N

准备两个大质数p,q,质数小了容易被破解,所以通常p和q是512比特,即155位的十进制数(但别更大了,更大虽然更安全,但计算时间也相应会变长)。用伪随机数生成器生成两个512比特的数,再判断是否是质数,如非质数,重新生成。(判断是否是质数不是通过分解质因数的方式,而是用费马测试和米勒.拉宾测试来判断是否是质数)

N = p * q

PS:为何要512比特的随机质数?除了安全外,还有个重要的原因是因为容量。512比特能容纳的质数数量大约为10的150次方个,假设全球100亿人,每人每秒生成100亿个密钥对,要100亿年后才会出现撞车,两个人生成相同的随机密钥对,这就等价于绝对不可能出现两人生成的密钥对完全一致撞车的情况。

第二步:求L(L是近在生成密钥对过程中使用的数)

L 是 p-1 和 q-1 的最小公倍数(least common multiple,lcm),欧拉函数

L = lcm(p-1, q-1)

第三步:求E

E要满足以下关系:

1 < E < L // 用伪随机数生成器生成在 1~L 范围内的 E

gcd(E, L) = 1 // E和L的最大公约数(greatest common devisor,gcd)为1,即E了L互质,如果不满足,用伪随机数生成器重新生成 E。(最大公约数可以用欧几里得辗转相除法

第四步:求D

D,E,L之间要满足以下关系:

1 < D < L 

E * D mod L = 1 

举例 RSA 生成公钥和私钥,并加密和解密:

求N:假设准备两个小质数 p=17,q=19,则 N = 17 * 19 = 323 

求L:L = lcm(16, 18) = 144 

求E:gcd(E, 144) = 1 => E 有很多:5,7,11,13,17....,我们选 E = 5

// 现在公钥已经有了:(E, N) = (5, 323),可以任意公开

求D:5 * D mod 144 = 1 => D = 29

现在私钥已经有了:(D, N) = (29, 323),妥善保管,不要告诉别人

加密:假设明文是 123,公钥 (5, 323),1235 mod 323 = 225(密文)

解密:私钥是 (29, 323),22529 mod 323 = 123(明文)

PS:22529 太大,计算器无法运算,所以要拆解:22529 mod 323 = (22510 mod 323) * (22510 mod 323) * (2259 mod 323)

RSA 算法是公开透明的,只要能知道私钥D就能破解RSA。要知道私钥D就需要知道中间数L,要知道L就需要知道p,q。而公钥N是公开的,N = p*q,只要能对N进行分解质因数算出p,q,这样就能破解RSA?理论上是可能的,但目前还没有对大质数分解质因数的高效算法,这就是我们要求p,q都是155位的大质数的原因。如果哪天能发明高效的大质数的分解质因数的算法,那RSA就能被淘汰了。目前最近的成果是2004年 Alexander May 证明了“求D”和“对N分解质因数”在确定性多项式时间内是等价的。

RSA算法虽然极其可靠,但也不是没有缺点的。虽然没人对RSA算法本身进行攻击,但可以用中间人攻击(man-in-the-middle attack),即截获接收者发送给发送者的公钥,将其改成自己公钥。发送者用攻击者的公钥进行加密,攻击者用私钥就能顺利解密,并用正确的公钥加密后发送给接收者,神不知鬼不觉。

再次证明安全是一个体系,单靠强度高的密码算法是不够的,防止中间人攻击需要对公钥使用证书。

(补充一)Diffie-Hellman 密钥交换

假设有个攻击者正在窃听通信线路,那发送者和接受者如何共享对称密钥呢?

1.发送者先发送两个质数 P,G。P和G是相关的数,称为生成元(generator),这两个质数被窃听也没关系。生成元是数论中的概念,例如21 mod 13 = 2 … 212 mod 13 = 1,从21到212的值全都不一样,即2的乘方的结果中出现了1到12的全部整数,因此2被称为13的生成元。即P的生成元的乘方结果与1~P-1数字是一一对应的。对于任意质数P都一定存在生成元G,证明过程略,见群论中的拉格朗日定理与欧拉函数。

2.发送者本地生成一个 1 ~ P-2 间的随机整数A。(因为在本地,所以无法被窃听)

3.接受者本地生成一个 1 ~ P-2 间的随机整数B。(因为在本地,所以无法被窃听)

4.发送者将 GA mod P 的值发送给接收者,这个值被被窃听也没关系

5.接受者将 GB mod P 的值发送给发送者,这个值被被窃听也没关系

6.发送者本地计算出共享密钥:(GB mod P)A mod P = G(A * B) mod P

7.接收者本地计算出共享密钥:(GA mod P)B mod P = G(A * B) mod P

双方交换的数字共4个:P,G,GA mod P,GB mod P,攻击者窃听到这4个数,因为不知道A或B,所以无法计算出共享密钥。

那攻击者不能通过 P,G,GA mod P 计算出 A 吗?不能,已知P,G,求A的复杂度的问题是有限域(finite field)的离散对数问题。

举个例子:

1.发送者发送两个质数 P=13,G=2

2.发送者本地生成一个 1 ~ 11 间的随机整数 A=9

3.接受者本地生成一个 1 ~ 11 间的随机整数 B=7

4.发送者将 GA mod P 即 29 mod 13 = 5 发送给接收者

5.接受者将 GB mod P 即 27 mod 13 = 11 发送给发送者

6.发送者本地计算出共享密钥:(GB mode P)A mod P = 119 mod 13 = 8

7.接收者本地计算出共享密钥:(GA mode P)B mod P = 57 mod 13 = 8

(补充二)有限域的椭圆曲线离散对数问题

椭圆曲线密码密钥短但强度高,正在被广泛地使用,例如在SSL/TLS中就使用了椭圆曲线Diffie-Hellman密钥交换(ECDH,ECDHE),椭圆曲线DSA(ECDSA),比特币中也使用了椭圆曲线DSA(ECDSA)。

椭圆曲线方程E:y2 = ax3 + bx2 + cx + d。(a,b,c,d为系数)

例如当a=1,b=0,c=-2,d=4时椭圆方程:y2 = x3 – 2x + 4,这个函数的曲线如下:

因为方程中有 y2 项,因此曲线必然X轴对称。所以A点的负数,即-A,就是A点的X轴对称点:

加法是一切运算的基础,曲线上任意两点A,B的连线与曲线的交点,该交点关于X轴对称的点定义成 A + B

有了加法就可以推演出乘法,2A即A+A,用A点在曲线上的切线与曲线的交点,该交点在X轴对称的点就是2A。依次类推,可以求得3A(2A + A),4A,5A……xA

PS:A-A就是找过A点和-A点的直线与曲线的交点,但这个交点在“无限远”的地方,在图上画不出来,所以A-A=O,O表示无限远。

PS2:比特币的椭圆曲线方程:y2 = x3 + 7

有限域上的椭圆曲线运算:(有限域是指是对于给定的质数p,由0 ~ p-1共p个元素所组成的整数集合中定义的加减乘除运算)

例如给定椭圆曲线方程:y2 = x3 + x + 1:

当它位于有限域F23上时,E2:y2 mod 23 = (x3 + x + 1) mod 23,此时x,y都只能取0~23间的整数,(x,y)的取值在二维坐标轴上是一些不连续的点。图中每个坐标(x, y)都满足公式:y2 mod 23 = (x3 + x + 1) mod 23

椭圆曲线上的离散对数问题(Elliptic Curve Discrete Logarithm Problem,ECDLP):

已知:
    椭圆曲线方程E
    椭圆曲线方程E上的某点G
    椭圆曲线方程E上的某点xG(G的x倍)
求:
    x

例如上例有限域F23上时,椭圆曲线方程E2:y2 mod 23 = (x3 + x + 1) mod 23,取G=(0, 1)为基点,按椭圆曲线的运算规则计算2G,3G,4G,5G…的结果如下:

这里有限域23只是个很小的质数,当有限域质数非常大时,要解这个问题非常困难。总之记住两点即可:

1.有限域里椭圆曲线上的离散对数问题就是已知 G 和 xG,求x

2.求x非常困难

发表评论

电子邮件地址不会被公开。 必填项已用*标注