离散对数第 $i$ 比特问题描述
给定 $(p,\alpha,\beta,i)$ ,其中 $p$ 是素数， $\alpha$ 是模 $p$ 的一个本原元， $\beta$ 满足 $\beta=\alpha^a\ mod\ p$ ,求 $log_\alpha\beta$ ( 也就是 $a$ )的第 $i$ 个最低比特。 我们用 $L_i(\beta)$ 来表示这一问题。
求解最低位
先放结论：$L_1(\beta)$ 是可以被准确求解的。
求解最低比特问题实际上就是求要求 $log_\alpha\beta$ 的奇偶性。
解这个问题，我们需要用到二次剩余的知识，首先我们记模 $p$ 的二次剩余集合为 $QR(p)=${ $x^2\ mod\ p\ |x\in\ Z_p^*$ } ，则$|QR(p)|=\frac{p-1}{2}$ 。
由于 $\alpha$ 是本原元，就有$QR(p)=${ $\alpha^{2i}\ mod\ p\ |0\le i\le \frac{p-3}{2}$ } 。这个结论是显而易见的，把 $x^2\ mod\ p$ 中的 $x$ 替换成 $\alpha^i$ 即可，同时这 $\frac{p-1}{2}$ 个 $\alpha^i$ 又是各不相同的，故它们构成了 $QR(p)$ 。换句话说， $\alpha$ 的偶数次幂是模 $p$ 的二次剩余，而奇数次幂则不是，我们运用这个特性可以计算 $L_1(\beta)$ 。
现在问题就在于如何判断 $\beta$ 是不是模 $p$ 的二次剩余。这里我们用到了欧拉准则，如果 $\beta^{\frac{p-1}{2}}=\ 1\ mod\ p$ ，$\beta$ 是模 $p$ 的二次剩余。
综上所述，
$$
L_1(\beta)=\begin{cases}0\ \ \ \ \beta 是模p的二次剩余\\
1\ \ \ \ \beta 不是模p的二次剩余\end{cases}
$$
求解其他位
这个问题属于难但是不完全难的情况 首先，我们基本上不可能完全求出剩下的所有位，但是我们可以求出一部分，至于能求出几位，取决于我们的 $p$ 是什么结构。一般来说，$p$ 可以写成 $p-1=2^s*l(l为奇数)$ 的形式，而我们所能够求出的最多位就是 $s$ 。换句话说，问题 $L_i(\beta)\ 1\le i\le s$ 是可以被解决的。
接下来我们细🔒。我们来看一件事，既然 $L_1(\beta)$ 是比较容易求的，那么有没有一种办法可以把 $L_2(\beta)$ 问题转化为 $L_1(\beta)$ 问题。或者说，我们希望能够用归纳法解决这个问题。
再来观察 $\beta$ 的结构， $\beta=\alpha^a\ mod\ p$ ，我们现在已知 $a$ 的最后一位了，现在要想办法把它的倒数第二位变成最后一位，这个就很容易想到用 $a/2$ 来实现（二进制下除以二可以类比十进制除以十，直接把最后一位隐去了）。于是，我们想想到构建 $\alpha^\frac{a}{2}\ mod\ p$ 这样一个式子。
下一个问题是，$a/2$ 可能是一个小数，如何避免。这个也很简单，我们根据前面的求解已经得知 $a$ 的奇偶性，对于奇数的 $a$ ，我们只需要减一即可，这样显然不影响倒数第二位比特的值。
然后我们用幂运算实现这些操作
$$
\beta_1=\begin{cases}\pm\sqrt\beta\ mod\ p\ \ \ \ L_1(\beta)=0\\
\pm\sqrt\frac{\beta}{\alpha}\ mod\ p\ \ \ \ L_1(\beta)=1\end{cases}
$$
于是，$L_2(\beta)=L_1(\beta_1)$。
到此为止，还没有什么迹象表明求解这个问题有什么困难，那么为什么说我们最多只能求出 $s$ 位呢？问题就出现在开方这一步。众所周知，整数的平方根有两个，那么在模 $p$ 下也同理，并且有 $\sqrt\beta+(-\sqrt\beta)=0(p)$ 。接下来我们来看一件有趣的事：
假设 $\beta_1(\sqrt\beta)=\alpha^{a/2}\ mod\ p$ ，由于$\alpha^{\frac{p-1}{2}}=-1\ mod\ p$ ，所以有 $-\beta_1(-\sqrt\beta)=\alpha^{a/2+\frac{p-1}{2}}\ mod\ p$（这里 $a/2$ 是整除的意思）。而问题 $L_1(\beta_1)$ 和 $L_1(-\beta_1)$ 的解分别代表了 $a/2$ 和 $(a/2+\frac{p-1}{2})$ 的奇偶性。但是我们是无法区分 $\beta_1$ 和 $-\beta_1$ 的，这就给解决问题带来了麻烦，除非 $a/2$ 和 $(a/2+\frac{p-1}{2})$ 的奇偶性恰好一致。
现在问题就剩下了什么情况下二者奇偶性是一样的。我们先来复习一下小学数学：奇数+奇数=偶数；奇数+偶数=奇数；偶数+偶数=偶数。可以看出，一个数加减奇数会改变它的奇偶性。因此，我们希望 $\frac{p-1}{2}(=l*2^{s-1})$ 是一个偶数，即 $2^{s-1}\ge 2$ 或者说 $s\ge2$。
如果我们想要求解问题 $L_3(\beta)$ ,按照上面的方法，我们需要对 $\beta$ 开四次方，这在模 $p$ 下有四个 $\beta_2$ （需要注意，$\pm\beta_1$ 虽然看上去有一个是负数，但是实际上 $-\beta_1$ 等价于 $p-\beta_1$ 也是正数，是可以开方的），它们的分别对应指数 $(a/4),(a/4+\frac{p-1}{2}),(a/4+\frac{p-1}{4}),(a/4+\frac{p-1}{4}+\frac{p-1}{2})$ ，同样我们不能期望能够找到它们分别的对应关系，因此我们仍然只能寄希望于这四个指数的奇偶性完全一致。也就是说 $2^{s-2}\ge 2$。很容易看出，我们能够成功求解 $L_i(\beta)$ 的前提是 $2^{s-i}\ge 2$ ，即$i\le s$ 。总而言之，我们最多只能求解 $L_s(\beta)$ 。
求解更高位
可以证明，求解 $L_i(\beta)\ \ i>s$ 不比解决离散对数问题简单（我不会证） ，我们可以通过一个算法来体会一下。假设存在一个 Oracle，对于给定 $\beta$ ，Oracle会返回 $L_2(\beta)$ （这个差不多等于算出离散对数然后把倒数第二位反馈回来，因为没有什么算法能够直接算出 $L_2$）。前面提到，由于我们无法区分 $\beta$ 开方得到的两个数，导致了如果 $a/2$ 和 $(a/2+\frac{p-1}{2})$ 的奇偶性不一致，算法就没法继续，但是这里Oracle给我们了 $L_2(\beta)$ ，根据这个数据，我们可以确定出 $\pm\beta_1$ 哪一个对应 $a/2$ ，从而规避掉分类讨论的可能性，而对于奇偶性一致的情况，我们直接套用原算法即可。
可以看出，这个算法和原来的其实差不多，唯一区别就是Oracle，或者说，我们能否完整求解 $L_i(\beta)$ 问题取决于能不能找到这样一个Oracle，而找到Oracle的难度不比直接算出离散对数问题简单。
ElGamal体制的语义安全
首先复习一下简单的Elgamal密码体制:
$pk=(p,\alpha,\beta),\beta=\alpha^a\ mod\ p$ ，$sk=(a)$。
$e_k(x,k)=(y_1,y_2)$
$y_1=\alpha^k\ mod\ p$
$y_2=x*\beta^k\ mod\ p$
$d_k(y_1,y_2)=y_2(y_1^a)^-1\ mod\ p$
下面我们来考虑一件事。根据 $\beta=\alpha^a\ mod\ p$ 我们可以得到 $a$ 的奇偶性（$L_1(\beta)$）；根据 $y_1=\alpha^k\ mod\ p$ 我们可以得到 $k$ 的奇偶性（$L_1(y_1)$）。于是我们就可以得到 $ak$ 的奇偶性，这使得我们可以轻易判断出 $(\frac{\beta^k}{p})$ ，因为 $\beta^k=\alpha^{ak}\ mod\ p$ 。同时，$y_2$ 是已知的，那么 $(\frac{y_2}{p})$ 也是很好判断的。另外，我们还截获了两条明文消息 $x_1、x_2$ ，现在我们需要判断哪一条消息的加密是$(y_1,y_2)$ 。如果这两条消息很巧合其中一条比如 $x_1$ 是模 $p$ 的二次剩余 ,那么 $x_1$对应密文 $(y_1,y_2)$ 当且仅当 $(\frac{y_2}{p})=(\frac{y_2}{p})=\pm 1$。
也就是说，上述ElGamal密码体制在语义上不是绝对安全的。
整个好玩的
我们利用该算法做一下简单的离散对数问题。$p=256*3+1,\alpha=112,a=72,\beta=769$
1 | #asge |
还行吧。如果把 $a$ 改成72127233，结果就是：
1 | a_bin= 0b100010011001001001100000001 |
看得出来最后七八位还是一样的，但前面不一样了，这也就是这个算法的局限。
俺寻思能行
我在想能不能利用这个东西出一道离散对数加密但是 $a$ 高位泄露的题。