离散对数问题

Marcus

2024-09-08

密码学

这节先讲$\mod p$的离散对数问题，还有一个椭圆曲线版本的下次讲。上节讲了，关于非对称密钥的提出是由
Diffie 和 Hellman提出的。而第一个公钥也是，它基于有限域$F_p$中的离散对数问题。其中$F_p$是一个具有$p$个元素的域，$p$是素数。其次，对于一个域$\mathrm{Z}/p\mathrm{Z}$也是具有$p$个元素的，所以我们有时会交替使用，那么涉及到$F_p$时，我们使用等号，提及$\mathrm{Z}/p\mathrm{Z}$时，我们使用同余符号。

令$p$是素数，则存在一个本原元素$g$，将使得$F_p$上的元素都是$g$的幂次。特别的，由费马小定理可知，$g^{p-1} = 1$。而$F_p$的乘法群是一个只有$p-1$个元素的域。即：

$\begin{aligned} 1,g,g^2,g^3,\cdots,g^{p-2}\in F^*_p \end{aligned}$

定义：离散对数问题（DLP）

令$g$是$F_p$的本原根且令$h$是$F_p$的非零元素。则离散对数问题(DLP)是指找一个指数$x$使得

$\begin{aligned} g^x\equiv h \mod p \end{aligned}$

的问题。数字$x$称为$h$的离散对数。它是以$g$为底的，我们记为$\log_g(h)$

注意1： 离散对数问题是一个良定义问题(well-posed problem)。即找到整数$x$使得$g^x = h$。另一方面，若$x$被我们找到了一个解，则这意味着存在无穷多个解：由费马小定理，$g^{p-1} \equiv 1\mod p$，若$x$是一个$g^x=h$的解，则$x+k(p-1)$也是另一个方程的解，注意

$\begin{aligned} g^{x+k(p-1)} = g^x\cdot (g^{p-1})^k \equiv h\cdot 1^k \equiv h \mod p \end{aligned}$

不难验证，$\log_g$给出了一个良定义的函数。

$\begin{aligned} \log_g:F^*_p \to \frac{\mathrm{Z}}{(p-1)\mathrm{Z}} \end{aligned}$

有时为了具体说明，我们将离散对数称为满足同余式$g^x\equiv h \mod p$且位于$0$和$p-2$之间的整数x。

例子

$p = 56509$是素数，我们可以验证$2$是$\mod p$的一个原根（理论上说，域$F_{56509}$存在$56508$个元素）。若我们想计算$h = 38679$的离散对数，一种显而易见的方法就是计算：

$\begin{aligned} 2^2, 2^3,\cdots \mod 56509 \end{aligned}$

直到得到$38679$的幂。就别用你那个破纸在那画了，用计算机，我们得到$\log_p(h) = 11235$。

我们转化为群论的一般结论：

定义：群$G$上的DLP

令$G$是群，则$G$上的DLP问题指的是对$G$中的任意两个元素$g,h$，求整数$x$满足：

$\begin{aligned} \underbrace{g\cdot g\cdot g\cdots}_{x\text{次}}=h. \end{aligned}$

Diffie-Hellman密钥交换

D-H密钥交换解决了下述问题：

爱丽丝和鲍勃想要共享一个用于对称密码的密钥，但他们的通信方式是不安全的。则交换的每条信息都能被他们的对手伊娃看到，那么爱丽丝和鲍勃两人如何在共享密钥的同时不被伊娃发现呢。D-H的绝妙见解是，$F^*_p$上的离散对数问题提供了一个可能的解决方案。

第一步，爱丽丝和鲍勃取一个较大的素数$p$和$\mod p$的非零整数$g$。然后他们将$p$和$g$的值公开，例如可以发到自己的个人博客上。所以伊娃也可以看到。当然，选择$g$的时候最好是一个较大的素数。

下一步，爱丽丝将选择一个不向任何人透露的秘密整数$a$，同时鲍勃选择一个私密的整数$b$。然后分别用这两个私密整数计算

$\begin{aligned} \underbrace{A\equiv g^a\pmod{p}}_{\text{爱丽丝}}\quad\text{和}\quad\underbrace{B\equiv g^b\pmod{p}}_{\text{鲍勃}}. \end{aligned}$

接着鲍勃和爱丽丝交换他们计算出来的值，注意的是，伊娃也可以看到这些值。这是我们一开始的假设。接着将用私密整数计算

$\begin{aligned} \underbrace{A'\equiv B^a\pmod{p}}_{\text{爱丽丝负责的部分}}\quad\text{和}\quad\underbrace{B'\equiv A^b\pmod{p}}_{\text{鲍勃负责的部分}}. \end{aligned}$

如果正确，那实际上计算出来的值是一样的，注意到

$\begin{aligned} A'\equiv B^a\equiv(g^b)^a\equiv g^{ab}\equiv(g^a)^b\equiv A^b\equiv B'\pmod{p}. \end{aligned}$

总结一下：

D-H密钥交换流程

选择大素数$p$和在关于素数$p$的域$F_p^*$中的具有大阶数的$g$
然后爱丽丝和鲍勃各自选择一个私密整数$a,b$，然后计算$A\equiv g^a \mod p$和$B\equiv g^b\mod p$
接着，爱丽丝将$A$发送给鲍勃，鲍勃将$B$发送给爱丽丝。
最后爱丽丝计算$B^a \mod p$，鲍勃计算$A^b\mod p$。注意共享值是$B^{a}\equiv(g^{b})^{a}\equiv g^{ab}\equiv(g^{a})^{b}\equiv A^{b}\pmod{p}.$

例子

现在我们选择素数$p = 941$和本原根$g =627$，爱丽丝选择$a =347$，则$A = 390 \equiv 627^{347}\mod 941$，类似的，鲍勃选择$b=781$并计算$B = 691 \equiv 627^{781}\mod 941$。接着爱丽丝给鲍勃发送$390$，鲍勃给爱丽丝发送$691$。而且我们应该将$A,B$视为公开发送的。$a,b$是保密的。然后，理论上说，爱丽丝和鲍勃都能计算到数字

$\begin{aligned} 470\equiv627^{347\cdot781}\equiv A^b\equiv B^a\pmod{941}, \end{aligned}$

则$470$是他们共享的密钥。

若此时伊娃想破解这个秘密，只要能解决其中任何一个问题，他就能解出爱丽丝和鲍勃的的密钥：

$\begin{aligned} 627^a \equiv 390 \mod 941 或者 627^b \equiv 691 \mod 941 \end{aligned}$

这是伊娃在没有爱丽丝和鲍勃帮助的情况下得到秘密共享值的唯一方法。

上述例子选择的$p$比较小，所以计算机可以在很短的时间给出答案。总的来说，伊娃的困境在于，若知道$A,B$，所以他也知道$g^a$和$g^b$的值，如果伊娃有能力解决DLP，则他可以找到$a$和$b$。之后就能很简单的计算出爱丽丝和鲍勃共享的私密值$g^{ab}$。因此，若伊娃无法解决DLP，那么鲍勃和爱丽丝就安全了。而该安全性实际上取决于以下可能更简单的问题。

定义 Diffie-Hellman Problem(DHP)

令$p$是素数，$g$是整数，则$DHP$指的是根据已知的$g^a\mod p$和$g^b\mod p$计算$g^{ab}\mod p$的问题。

这和我们之前提到的非对称密码是很相似的，区别在于本质上还是一个对称密码。即可以通过自己的私钥去解密别人发送过来的密文。回到问题上来，显然的是$DHP$并不比$DLP$难，若伊娃可以解决DLP，则解决DHP是容易的，但反过来就不一定了。如果伊娃有一个可以有效解决DHP的方法，但能不能解决DLP是尚未清楚的事实。