Cado-nfs使用

CADO-NFS是C / C ++中数字字段筛选（NFS）算法的完整实现，用于分解整数并计算有限字段中的离散对数。它包含与算法所有阶段相对应的各种程序，以及可能在计算机网络上并行运行它们的通用脚本。

Cado-nfs安装可以参考这篇博客

1. Cado分解大整数

命令非常简单，直接加上大整数即可

1	./cado-nfs.py [大整数]

举个栗子

1	./cado-nfs.py 90377629292003121684002147101760858109247336549001090677693

输出结果：

1	260938498861057 760926063870977 588120598053661 773951836515617

2. Cado计算离散对数

举个小栗子，比如如下的一个DH密钥交换过程：

$p=223456789012345678301234567890123456789012345678901234568071\\ g=173111254804046301125\\ p-1=2 * 5 * 22345678901234567830123456789012345678901234567890123456807\\ h=g^x(modp)=49341873303751285095603174930981210164964894155978049874920\\ k=g^y(modp)=11470107855035656763776670242237886083319963338170205350339$

我们的目标就是求解处x或者y即可，主要分为以下几步

计算$log_{g’}h$（注意这里是 g‘ 不是上述的g，g’ 是运算过程的另一个基）
计算$log_{g’}g$
计算$x = log_g h = \cfrac{log_{g’}h}{log_{g’}g}$
计算$g^{xy}(mod p)$

思路还是非常清晰的，下面是实操部分

1.首先计算$log_{g’}h$，输入如下命令（其中ell指定p-1的最大素因子）

./cado-nfs.py -dlp -ell 22345678901234567830123456789012345678901234567890123456807 target=49341873303751285095603174930981210164964894155978049874920 223456789012345678301234567890123456789012345678901234568071

所以我们得到

$log_{g’}h = 11068439637671712943054178216756460395598012657532627052040(mod \; ell)$

2.紧接着我们来计算$log_{g’}g$，根据上条命令的提示，执行如下命令

1	./cado-nfs.py /tmp/cado.mh5ibmt3/p60.parameters_snapshot.0 target=173111254804046301125

于是我们得到

$log_{g’}g = 3530519402410479200105864241268884715421920798974159890934$

3.然后我们就能计算$x = log_g h = \cfrac{log_{g’}h}{log_{g’}g}$，这里使用sagemath计算就可以了

p = 223456789012345678301234567890123456789012345678901234568071
R = GF(p)
g = R(173111254804046301125)
gx = R(49341873303751285095603174930981210164964894155978049874920)
gy = R(11470107855035656763776670242237886083319963338170205350339)
ell = 22345678901234567830123456789012345678901234567890123456807
log_h = 11068439637671712943054178216756460395598012657532627052040
log_g = 3530519402410479200105864241268884715421920798974159890934
temp = log_h * inverse_mod(log_g, ell) % ell
print(temp)
print(g^temp)
print(gx)  # 验证一下
print(gy^temp)  # g^xy

于是我们很顺利的得到了口令为3333333333333333333333333333333333333333（但是有时并不能直接得到，我们得到的是$log_g h(mod \; ell)$，而我们需要的其实是$log_g h(mod \; ell)$，所以验证环节非常有必要！下面就是一个栗子）

令$s = 3333333333333333333333333333333333333333$我们来求一下$log_g s$，同样的思路

1.计算$log_{g’}s$（命令参数需要自己修改）

1	./cado-nfs.py /tmp/cado.mh5ibmt3/p60.parameters_snapshot.2 target=3333333333333333333333333333333333333333

2.计算$x = log_g s = \cfrac{log_{g’}s}{log_{g’}g}$

p = 223456789012345678301234567890123456789012345678901234568071
R = GF(p)
g = R(173111254804046301125)
gx = R(49341873303751285095603174930981210164964894155978049874920)
gy = R(11470107855035656763776670242237886083319963338170205350339)
s = R(3333333333333333333333333333333333333333)
ell = 22345678901234567830123456789012345678901234567890123456807
log_h = 11068439637671712943054178216756460395598012657532627052040
log_g = 3530519402410479200105864241268884715421920798974159890934
log_s = 7415243246095171081154394907486947430598565788895011470017
temp = log_s * inverse_mod(log_g, ell) % ell
print(temp)
print(g^temp)
print(s)  # 验证一下

验证失败，所以我们需要穷举一下$temp + i*ell (mod\;p-1)$

p = 223456789012345678301234567890123456789012345678901234568071
R = GF(p)
g = R(173111254804046301125)
gx = R(49341873303751285095603174930981210164964894155978049874920)
gy = R(11470107855035656763776670242237886083319963338170205350339)
s = R(3333333333333333333333333333333333333333)
ell = 22345678901234567830123456789012345678901234567890123456807
log_h = 11068439637671712943054178216756460395598012657532627052040
log_g = 3530519402410479200105864241268884715421920798974159890934
log_s = 7415243246095171081154394907486947430598565788895011470017
temp = log_s * inverse_mod(log_g, ell) % ell
max_range = (p-1)//ell
for i in range(max_range):
    if g^(temp + i * ell) == s:
        print(temp + i * ell)
        break

输出结果为72539767398269887557126589783723994511315343694684641940317，说明$log_g s = 72539767398269887557126589783723994511315343694684641940317$，所以要记得简单验证一下！