离散对数

第一个被Diffie和Hellman公布的公钥密码系统就是基于离散对数的。在接下来的内容，首先说明我们会继续使用
记号$\mathbb{F}_p$或者是$\mathbb{Z}/p\mathbb{Z}$来表示p域，用$\mathbb{F}_p$表示时我们使用等号，
用$\mathbb{Z}/p\mathbb{Z}$表示时我们使用同余号。
首先我们复习原根，我们知道对于一个大素数p，存在原根g，使得$\mathbb{F}_p$中的每个非零元素都由g的幂
产生。等价地，如下列表：

$$1, g, g^2, g^3, \dots, g^{p-2} \in \mathbb{F}_p^*$$

是$\mathbb{F}_p^*$在某顺序下的所有元素。

::: Definition
Definition 1.
我们设g是$\mathbb{F}p$的一个原根并且设h是$\mathbb{F}_p$的一个非零元素。那么解决离散对数问题就是去
找到一个指数x使得 $g^x = h$
成立。x就叫做h相对于g的离散对数，记为$\log{g}(h)$。
:::

::: Remark
Remark 2.
在数论中，离散对数也被称作索引，记为$ind_g(h)$。这个术语到现在在数论中也很常用。
:::

::: Remark
Remark 3.
*离散对数问题是一个适定的问题，即去找到一个整数指数使得$g^x = h$。然而，如果存在一个解，那么就一定存在
无穷多个解，因为费马小定理告诉我们$g^{p-1} \equiv 1 (mod\ p)$。那么如果有一个x使得$g^x = h$，于是
$x + k(p-1)$也是其解，因为：

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

所以说得到一个解之后就加上$p-1$的倍数即可。换句话说，$\log_g(h)$是定义在模$p-1$上的。不难验证
$\log_g(h)$给出了一个定义良好的函数：

$$\log_g : \mathbb{F}_p^* \to \frac{\mathbb{Z}}{(p-1)\mathbb{Z}}$$

简单解释一下，h是$\mathbb{F}_p$中的非零元素，被映射到$\frac{\mathbb{Z}}{(p-1)\mathbb{Z}}$上，也就是
$p-1$的同余类，模$p-1$都同余。有时，为了具体，我们求解的x一般指0到$p-2$之间的满足方程的解。*
:::

::: Remark
Remark 4. *不难证明一个小性质：

$$log_g(ab) = log_g(a) + log_g(b) \ for\ all\ a, b \in \mathbb{F}_p^*$$* ::: ::: Example **Example 1**. *给定数$p = 56509$是一个素数，并且我们可以验证$g = 2$是模p的一个原根。那么我们如何计算出关于$h = 38679$ 的离散对数呢？最显然的办法就是去按照顺序计算， $$2^2, 2^3, 2^4, \dots (mod\ 56509)$$

用计算机，可以得到$\log_2(h) = 11235$你可以去验证，确实是正确的。*
:::

::: Remark
Remark 5.
我们刚才对离散对数问题的陈述，假设了基g是模p的一个原根，但是这并不是严格必要的。一般来说，对于任何
$g \in \mathbb{F}_p^$和任何$h \in \mathbb{F}_p^$，离散对数问题都是找到是否存在一个x使得$g^x = h\ (mod\ p)$。
更一般地说，我们不是取有限域$\mathbb{F}_p$中的非零元素并将它们相乘或求幂，而是可以取任何群中的元素
并且使用群的运算律代替乘法。这样就定义了离散对数问题的最一般的形式。
:::

::: Definition
Definition 6.
设G是一个群，G的群法则我们用$\star$。对于G的离散对数问题定义为，任意两个给定G中元素g,
h，存在x满足 $\underbrace{g\star g\star g\star \cdots}_{x个} = h$
:::

Diffie—Hellman Key Exchange

Diffie—Hellman Key Exchange算法解决了下面的窘境。
Alice和Bob想分享在使用的对称加密系统中的密钥，但是他们唯一的通信方式是不安全的。他们交换的每一条信息
都可以被Eve观察到。那么他们使用怎样的办法才可能交换密钥并且不被Eve观察到呢？乍一看这是一个不可能解决的问题，
于是这要归功于Diffie和Hellman的深刻洞察力，他们发现使用$\mathbb{F}_p^$域下的离散对数问题来解决是可行的。
Alice和Bob的第一步是先对一个大素数p和模p下的一个非零整数g达成一致。Alice和Bob将p和g公开，他们可以将
这两个信息发布在网站上，所以Eve也将看到它们。由于后面要讨论的各种原因，它们最好选用的g要满足它在
$\mathbb{F}_p^$域中的阶为一个大素数。
下一步Alice将选择一个秘密整数a，并不公开。同时Bob也选择一个整数b作为密钥。Alice和Bob用他们各自的
密钥分别计算

$$\underbrace{A \equiv g^a (mod\ p)}_{Alice}\ and\ \underbrace{B \equiv g^b (mod\ p)}_{Bob}$$

然后他们交换这些计算之后的信息。Alice将A发送给Bob，Bob将B发送给Alice。注意Eve是可以看到A和B的，
因为他们仍然在不安全的信道上发送。
最后，Bob和Alice用他们各自的整数密钥分别去计算

$$\underbrace{A^{'}\equiv B^a (mod\ p)}_{Alice}\ and\ \underbrace{B^{'}\equiv A^b (mod\ p)}_{Bob}$$

看起来$A^{‘}$和$B^{‘}$是分别计算的，其实他们的值相同。因为

$$A^{'}\equiv B^a \equiv (g^b)^a \equiv (g^a)^b \equiv A^b \equiv B^{'} (mod\ p)$$

所以说Diffie—Hellman key exchange可以概括成下表所示： 略。
一般来说，Eva的困境在于，她知道A,
B的值，所以她也就知道$g^a$和$g^b$的值，她也知道g，p的值，所以
如果她能够解出离散对数问题（DLP），她也就找到了a和b的值。之后，她就可以用这两个值来计算Alice和Bob
秘密交换的$g^{ab}$。所以Alice和Bob是否安全，看起来要假设Eve不能够解出DLP问题，但这也并不完全正确。
虽然说唯一能算出Alice和Bob的秘密交换的值的办法是解决DLP，但对Eve来说也不是最准确的。
Alice和Bob最终交换的信息的安全性依赖于下面的问题，一个可能稍微容易一些的问题。

::: Definition
Definition 7. 设p是一个素数，g是一个整数。我们说 $Diffie–Hellman$
Problem(DHP)是从已知的$g^a(mod\ p)$和$g^b(mod\ p)$
情况下，去计算$g^{ab} (mod\ p)$。
:::

显然DHP要比DLP容易一些。Eve只需要计算a或者b就可以了。但是这个问题反过来就不那么清楚了，假设Eve有
一个解决DHP问题的高效办法，那么她能够使用去解决DLP吗？答案是不确定的。

The Elgamal Public Key Cryptosystem

这一节我们来看一个Elgamal公钥加密系统。这个新的公钥加密系统和Diffie—Hellman系统有很大的关联，同样也是
基于$\mathbb{F}_p^$域的离散对数问题。特别地，我们会在后面讨论一个基于椭圆曲线的Elgamal公钥加密系统。
对于the Elgamal
PKC，Alice需要一个大素数p，使得求解$\mathbb{F}_p^$域中的离散对数问题变得很困难。
并且Alice需要一个g，在模p的情况下阶很大。
Alice选择一个a作为她的私钥，然后去计算 $A \equiv g^a (mod\ p)$
当然这个系统和Diffie—Hellman系统的相似之处就是Alice公布了A, g,
p，将a作为私钥。
现在假设Bob想使用Alice的公钥a来加密一条消息，我们将假设Bob的消息m是一个介于2和p之间的整数。
为了加密m，Bob首先随机选择另一个数字$k(mod\ p)$。
Bob使用k加密一个且只是一个消息，然后他丢弃了k。我们把k叫做随机元素，它存在的唯一目的是加密单个消息。
Bob取出他的明文信息m，他的随机元素k，和Alice的公钥A，然后用它们来计算这两个量

$$c1 \equiv g^k (mod\ p)\ and\ c2 \equiv mA^k (mod\ p)$$

然后Bob把他加密而得的密文对($c_1$, $c_2$)，发送给Alice。
那么Alice如何解密呢，其实只需要一些简单的步骤如下： $\begin{aligned} &x \equiv c_1^a (mod\ p)，\\ &x \equiv c_1^a \equiv g^ka \equiv (g^a)^k \equiv A^k (mod\ p)。\\ &(c_1^a)^{-1} \cdot c_2 (mod\ p)\\ &(c_1^a)^{-1} \cdot c_2 \equiv (A^k)^{-1} \cdot c_2 (mod\ p)\\ &c_2 \equiv mA^k (mod\ p)\\ &(A^k)^{-1} \cdot c_2 \equiv m (mod\ p)\\ \end{aligned}$

::: Remark
Remark 8.
在Elgamal公钥加密系统中，明文是一个2和p-1之间的整数m，而密文包含和m相同范围的两个整数$c_1$和$c_2$。
也就是写下一个明文m，得到两个密文c。写下密文的次数是写下明文的两倍，我们称Elgamal公钥加密系统有2比1
的消息扩展。
:::