Avatar image Harlan V. Wei (aka. Wei Chen)

ElGamal 模运算加密与椭圆曲线加密的类比

• Photo credits: FlyD on Unsplash

Hero image for ElGamal 模运算加密与椭圆曲线加密的类比

This post is only available in Chinese at this moment.

Diffie 和 Hellman 在《密码学的新方向》(New Directions in Cryptography)这篇论文中提出了非对称加密的思想,即利用陷门函数来生成公私密钥。陷门函数指的是这样一类函数:假设有函数 y=f(x),很容易从 x 计算到 y,但很难使用现有的计算技术在可预见的时间内计算出 x。我们可以利用陷门函数的这一特性生成公钥,公钥可以在不安全信道上进行传输,并且不会威胁到密文本身的安全性质。Diffie-Hellman 框架的思想,简单来说就是:参与安全通信的所有人生成公钥和私钥,A 向 B 发送消息时使用 B 的公钥来加密明文,B 获取密文后使用自己的私钥解密来获取明文;公钥和私钥之间的纽带通过陷门函数来建立。

ElGamal 根据这个思想完整地提出了基于离散对数的加密系统。这一系统中的陷门函数即模函数,其陷门性质来源于离散对数困难性假设。简单地说,Alice 和 Bob 两人想要进行加密通信。Alice 在密钥空间中按照均匀分布选取一个密钥 $K_A$,根据密钥生成公钥:$(P_A = \alpha^{K_A} \mod p, \alpha, p)$;Bob 按照同样的方式生成公钥和私钥。Bob 向 Alice 发送消息 m 时,随机地从 $[0, p-1]$ 的正整数内选取一个临时密钥 k,向 Alice 发送:

$$ c_1 = \alpha^k \mod p\newline c_2=Km\mod p\newline K = P_A^k\mod p $$

Alice 要解密,首先需要知道 $c_2$ 中的 K,而 $K=P_A^k=\alpha^{K_A k}=c_1^{K_A}$,因此很容易可以解得 m。而对于攻击者来说,计算出 m 要首先计算 $K_A$,这实际上是在解离散对数问题。

对于连续可导函数来说,我们可以使用泰勒展开来计算对数,然而对于离散函数来说,目前尚无已知的有效计算对数的方法,尤其是 ElGamal 加密系统实际上还利用了模运算形成循环群,这使得计算出实际的密钥 k 变得更加困难(困难之处在于:对于 $y=x\mod A$,一个 y 对应了很多 x)。这也就是说,通过寻找这类离散对数难计算的群,我们可以形成各种新的加密系统方案。

椭圆曲线加密算法实际上同样也是 Diffie-Hellman 体系内的算法。对比于 ElGamal 算法来说,前者是在使用模运算来保证密钥的安全,而后者使用椭圆曲线,运算更加复杂,因此能够保证更高的安全性(在知道椭圆曲线参数的前提下,选定点 A,计算 kA 可以利用一系列数学方法来加速运算,然而反过来计算 k 具体是多少就非常困难)。对于攻击者来说,无论是 ElGamal 还是椭圆曲线算法,实际上解决的都是离散对数问题,都是需要从离散的点中逆推用于加密的函数的参数(密钥等)。

椭圆曲线运算的困难性一方面是提升了加密的安全性,另一方面也能够用于缩短密钥的长度。实际上是因为椭圆曲线加密算法相当于在二维空间中生成密钥,而模运算只是一个一维空间的操作。对于通信双方,他们可以利用已知的函数关系将二维空间内的点串联起来,而攻击者想要在二维空间内寻找规律就变得更加困难;我们就可以在达到同样安全性要求的前提下使用更短的密钥,从而提高加密运算和密钥传输的效率。

More Content on This

推荐观看 Computerphile 的这个视频。(这个视频中也有一处错误,在 7:32 处 Mike 说坐标中的 xy 中我们只使用其中一个是因为这样做就足够安全,实际上只是因为其中一个就已经包含了所有必要的信息。)