huangx607087学习离散对数的笔记 1

0.简介

一个~~密码学废物的学习笔记，很菜，别看，以后会定期补充~~

这两天学完了 $\text{An Introduction to Mathematical Cryptography}$那本书的第$2$章离散对数内容，做一点点笔记，~~顺便水一篇博客~~。

1.离散对数引入

概念1：离散对数就是解决形如$g^x\equiv h \pmod p$的一类指数同余方程，最后的结果可以记作$\dfrac{\ln(h)}{\ln g}$,例如，$3^2 \equiv 2 \pmod 7$,所以有$\dfrac{\ln(2)}{\ln3}\equiv 2 \pmod 7$。离散对数虽然是在有限域中进行的，但是它在有限域中的运算性质与正常实数范围内的运算性质一样，比如$\dfrac{\ln(a)}{\ln g}+\dfrac{\ln(b)}{\ln g}=\dfrac{\ln(ab)}{\ln g}$

概念2：本原元：本原元是指使得$g^x\equiv 1 \pmod p$的最小非零$x$值等于$p-1$的数字。具体内容可见博客中NumberTheory 4[2021.1.22] 中的部分内容

2.离散对数在密码学中的应用

EXP 1. Diffie-Hellman密钥交换

Step 1：双方选定一个本原元$g$和一个大素数$p$

Step 2：Alice计算$A\equiv g^a \pmod p$，Bob计算$B\equiv g^b \pmod p$，其中$a,b$分别为Alice和Bob秘密随机选取的数字

Step 3：Alice把$A$发送给Bob，同时Bob把$B$发送给Alice

Step 4： Alice，Bob分别计算$B^a$和$A^b$，由于$A^b=B^a=g^{ab}$，因此可以完成密钥交换

该密钥交换过程中，公钥为$g,p,A,B$，私钥为$a,b$。

在这个应用中，离散对数仅仅用于交换密钥，因此这并不是一个完整的加密算法

EXP 2.Elgamal 加密算法

生成密钥：

Step 1：选取一个本原元$g$和一个大素数$p$

Step 2：选取$a\in[1,p-1]$，计算$A\equiv g^a \pmod p$，公布$A$

加密：

Step 3：选择明文$m$和私钥$k$，计算$c_1=g^k,c_2=mA^k$

解密：

Step 4：计算$c^{-a}_1c_2$

Elgamal加密，由$2$个密文确定$1$个明文

3.计算离散对数的方法

PART 1 暴力枚举，时间$O(N)$

~~很low的方法~~

PART 2 Baby Step Giant Step

要先求出$\mathrm{ord}(g)=N$，复杂度为$O(\sqrt N \ln N)$

Step 1：设$n=1+\sqrt N$，然后构造两个序列$L_1=1,g,g^2,g^3,…,g^n$和$L_2=h,hg^{-n},hg^{-2n},hg^{-3n},…,hg^{-n^2}$

Step2：寻找$g^a=hg^{-bn}$，则$x=a+bn$

上一下代码：

from Crypto.Util.number import *
from gmpy2 import iroot
def BSGS(G,H,P,N):
    L1,L2=[],[]
    for i in range(N+1):
        L1.append(pow(G,i,P))
    for i in range(N+1):
        tmp=H*inverse(pow(G,i*N,P),P)%P
        L2.append(tmp)
        if tmp in L1:
            a=L1.index(tmp)
            b=i
            return b*N+a
p=17389
g=9704
h=13896
n=1242
print(BSGS(g,h,p,iroot(n,2)[0]+1))
# 1159

PART 3 Pohilg Hellman算法

该算法利用中国剩余定理解决，如果$p-1$非常光滑（比如只有几十光滑，也就是$p-1$的最大素因数只有几十甚至十几），那么这个算法可以在极短时间内求出离散对数的值。不过该算法的复杂度也接近于$O(\sqrt N \ln N)$，$O(\sqrt N \ln N)$也是目前以来求解离散对数的最快的时间复杂度

首先先分解$p-1=\Pi (q^e)$，其中$q$为素数，$e$为指数，然后通过枚举法（$\ln N$级别的枚举），求解每个素数及其对应的指数的$(g^{\frac{p-1}{q^e}})^x=(h^{\frac{p-1}{q^e}})^x$，得到最终答案$X \equiv x \pmod {q^e}$，最后使用中国剩余定理即可。

上一下代码：

from Crypto.Util.number import *
def solve(p,oriex,cntex,product,rnd,g,h,mod):
    if(rnd==oriex+1):
        return product
    tmpg=pow(g,pow(p,oriex),mod)
    tmph=pow(h*inverse(pow(g,product,mod),mod),pow(p,cntex),mod)
    tmpans=0
    for i in range(p):
        if(pow(tmpg,i,mod)==tmph):
            tmpans=i
            break
    return solve(p,oriex,cntex-1,product+tmpans*p**rnd,rnd+1,g,h,mod)
print(solve(5,3,3,0,0,5448,6909,11251))
#511

说明：调用填写参数的时候，代码中的p是模数减去$1$后的因数，oriex,cntex两个都填$q^e$中的$e$减去$1$的值，product和rnd都填$0$，g,h,mod分别填原来的$g,h$和模数，例如，上面是计算$5448^x\equiv6909\pmod {11251}$的结果，注意到$\text{ord}(5448)=5^4$，但是填入的第二个和第三个参数均为$4-1=3$。观察代码也不难发现，枚举确实是$\ln$级别的，并且$p-1$越光滑，耗时越短！