密码学笔记(二)

作者: icfg66 | 来源:发表于2020-02-02 17:05 被阅读0次

二、非对称加密

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

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

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.JPG

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

量子2.JPG

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

量子3.JPG

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

量子4.JPG

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

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

参考资料：

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

密码学笔记(二)

二、非对称加密

1、RSA

2、ElGamal算法

3、ECC（Elliptic Curve Cryptography ）

三、量子密码学

参考资料：

相关文章

网友评论

延伸阅读

深度阅读

栏目导航

热点阅读