二、非对称加密

对称密钥既可以用来加密,也可以用来解密,看上去很实用也很方便,但是每个有权访问明文的人都必须具有该密钥,如果一个粗心的用户泄露了密钥,那么就等于泄露了密文,因此密钥的发布成了新问题。针对这一问题的解决方案是,公钥加密算法,属于非对称加密。

这种加密算法有两个不同的密钥:一个用来加密,另一个用来解密。加密密钥可以是公开的,只有解密密钥是保密的。

1、RSA

假设Alice要给Bob发消息,Alice先利用Bob的公钥(全网公开)对消息加密,发送给Bob后,Bob用其私钥对消息解密。如果Bob需要反馈Alice,则Bob要利用Alice的公钥(不同于Bob的公钥)对消息加密,然后发送给Alice,最后Alice用她自己的私钥解密读取消息。

比如Alice给Bob发送消息“Hi”,该消息在ASCII中用16位进制表示为01001000 01011001,转化成十进制为72,105。然后Alice用Bob的公钥(139,253)加密:
$$
72^{139} \mod {253}=2,
105^{139} \mod {253}=101
$$
Bob接受到消息(2,101)通过私钥(19,253)解密:
$$2^{19} \mod {253}=72,101^{19} \mod {253}=105
$$
将两个数转换成二进制并查ASCII表得到消息“Hi”。那么私钥和公钥是如何得到的呢?

先选择两个素数,如$p=11,q=23$,确定$n=pq=253$,接下来确定私钥$d$,满足$d$与$(p-1)(q-1)=220$互质,这样的数很多,不妨取$d=19$。最后确定公钥的另一部分$e$,满足:
$$
19e \mod{220}=1
$$
解得$e=139$。这样公钥为(139,253),且全网公布,私钥(19,253)中的19只有Bob知道。

2、ElGamal算法

同样,比如Alice向Bob发送消息“Hi”,在ASCII表中对应十进制为72,105。然后Alice用Bob的公钥(p=13171,g=2,y=11852)加密,不同于RSA,这里一个明文会产生两个数组成的密文:(下面的$r_1,r_2$为随机数)

$$
c_1=g^{r_1} \mod p = 2^{31} \mod {13171}=4782
$$
$$
c'_1=m_1 y^{r_1} \mod p = 72×11852^{31} \mod {13171}=7565
$$
$$
c_2=g^{r_2} \mod p = 2^{16} \mod {13171}=12852
$$
$$
c'_2=m_2 y^{r_2} \mod p = 105×11852^{16} \mod {13171}=2072
$$
因此Alice将密文(4782,7565)、(12852,3898)发给Bob,Bob利用私钥$x=23$解密:
$$
(c'_1/c^x_1)\mod p=(7565/4782^{23})\mod {13171}=72
$$
$$
(c'_2/c^x_2)\mod p=(3898/12852^{23})\mod {13171}=105
$$
那么公钥和私钥是如何生成的呢?
1、找一个较大的素数$p$,例子中是13171;
2、找$g$,它是$Z_p^*$中的生成元,例子中是2;
3、选一个私钥$x$,小于$p-1$的整数,例子中是23;
4、确定公钥$y=g^x \mod p$,例子中是11852。
这样(p,g,y)为公钥,x为私钥。加密时还需要生成一个随机数,它对解密没有影响。

ElGamal加密法引入了一些新的特征,最显著的是引入随机数,这意味这相同的明文可以有不同的密文,提高了安全性。但是由于密文是明文的两倍大,从而增加了对存储空间的需求,降低数据传输的速度。

3、ECC(Elliptic Curve Cryptography )

椭圆曲线密码体系不像前两个算法一样直接,需要先具备一些数学基础,有一篇不错的科普文:椭圆曲线密码体制

先看一个具体例子吧,假设Alice要把消息“3”发给Bob:
1、Bob先选定一条椭圆曲线,并取椭圆曲线上一点作为基点G。比如$E_{29}(4,20)$,基点$G(13,23)$,基点G的阶数n=37。
$$
E_{29}(4,20):y^2=x^3+4x+20 \mod 29
$$
G点在椭圆曲线上:
$$
13^3+4×13+20 \equiv 23^2 \equiv 7 \mod 29
$$
阶数为n=37表示:
$$
37 G =O_{\infty}
$$
椭圆曲线上的加法和乘法规则可以参考: ECC椭圆曲线详解
2、Bob选择一个私钥k(k<n)比如25,并生成公钥K=kG=25G=(14,6)
3、Bob将E、K、G作为公钥传给Alice(全网公布)
4、Alice收到公钥后,将明文编码映射到E上一点,比如是横坐标为“3”,求得纵坐标为28,明文M=(3,28)。再产生一个随机数r,比如r=6
5、Alice对明文加密:
$$
C_1=M+rK=M+6K=(3,28)+6\times(14,6)=(6,12)
$$
$$
C_2=rG=6G=(5,7)
$$
(注意这里的加法和乘法不同于我们熟知的加乘法,其规则符合椭圆曲线上的加乘法,详见前文链接)
6、Alice将$C_1,C_2$发给Bob
7、Bob收到密文后,解密明文:
$$
M=C_1-kC_2=(6,12)-25\times(5,7)=(3,28)
$$
横坐标即为Alice传输的明文“3”。

比特币及中国二代身份证都采用256比特的椭圆曲线密码算法,因为它相对于RSA具有更高的安全性,160比特的椭圆曲线密钥与1024比特RSA密钥的安全度相当,其复杂度为全指数时间,RSA为亚指数时间。短密钥的好处在于加解密速度快、节约能源、带宽、存储空间。

三、量子密码学

我们前面介绍了AES算法,如果Alice现在要发送消息给Bob,她发现之前的密钥可能被盗取,希望换一个新密钥,那么如何将这个密钥告知Bob并不让黑客发现呢?这其实像一个悖论,如果可以安全的传输密钥,那么岂不是也能安全的传输明文,也就不用加密了。

山重水复疑无路,柳暗花明又一村

量子密码学恰恰提供了解决方案,而且它只能安全地传输随机数,但不能传输特定的明文,而随机数刚好可以用来作为密钥加密,完美对接!

那么该用什么样的媒介传输密钥,并且具有量子效应呢?光子!BB84协议就是使用光子,它能容易地在光纤链路中实现。它将二进制位0和1按光子地偏振(电场的方向)加密。光子可以在水平、垂直或对角线(+45°和-45°)发生偏振,如下图:
量子1

接下来的特性很关键,当光子输入不同的滤波器时,其输出会因为滤波器的不同而呈现不同的特点。滤波器有两种:水平垂直滤波器和斜线滤波器。当水平偏振光子通过水平垂直滤波器时,其状态不变;但通过斜线滤波器时,它将随机地变为+45°或-45°的偏振光,如图
量子2

在发送密钥之前,我们先定义“0”表示垂直或+45°方向偏振的光子,1表示水平或-45°方向偏振的光子,这一点很重要:
量子3

最后是见证奇迹的时候,假设Alice生成10个随机数:1101000100(这还不是最终的密钥),无序的光子可以通过-45°过滤器得到-45°的偏振光,即发送“1”,通过垂直的过滤器得到垂直偏振光,也发送“1”。Bob在接收端可以随机选择偏振过滤器(x为斜线,+为水平垂直方向),如:+xx__xxx+x,因此他得到的序列是1001010101。他再与Alice通电话(无惧偷听),确定Bob哪个滤波器是对的,比如这里是3、4、5、7、8、9位正确,这样他们就确定了密钥010010。详细过程如下:
量子4

这种方式可以防止黑客的窃听,如果他也用滤波器截取Alice的发送序列,那么会破坏其状态,能被Bob和Alice发现,而且黑客也不能复制Alice的光子,因为量子系统具有不可复制性。

量子密钥发布(Quantum key distribution。QKD)已经在实验室得到了实现,Los Alamos国家实验室在48km光纤上演示了QKD的过程。日内瓦大学构建的QKD实验中,光纤长达70km,速率为100Hz。2016年8月16日,墨子号量子卫星上天,光纤中的安全传输超过了200km,间隔100km的量子保密电话已经在技术上可行了,但还需要进一步工程设计才能商用。

参考资料:

《经典密码学和现代密码学》
计算机科学速成课-加密
你完全理解的量子信息
中国MOOC-电子科技大学-现代密码学

标签: 密码

添加新评论