利用Cado-nfs来解决离散对数问题

-------------已经到底啦！-------------

最近在看椭圆曲线的一道挑战题最关键的一部分是私钥求解，这也是ECC加密里面保证安全性的核心算法，破译明文问题的关键就在于如何破解私钥——即解决ECDLP问题；

截取”问题描述”
$$
选择椭圆曲线上的一点
P = [0x4f1ecacc3b1e56066b02f6a6033f940fc5c9805, 0] \
Q_A = [n_A]P = [0xb50e2eb55cd84112077a5acca94b4623a8b020d7, 0],\
选择大素数 p = 0xb77902abd8db9627f5d7ceca5c17ef6c5e3b0969\任务就是求解私钥n_A啦\
‘nA = 0x9022802bb688656ee1914e6dd7f74e1ecd1d6780’
$$
把握一点就OK了，正常椭圆曲线加密里面私钥都通指采用离散对数算法形成加密，可以看作是
$$
n_A=log_PQ_A
$$

Cado-nfs安装

这里都是基于docker镜像的安装o

下载 mitchelldehaven/cado-nfs镜像

1	docker pull mitchelldehaven/cado-nfs

运行容器，打开交互界面

1	docker run -it mitchelldehaven/cado-nfs /bin/bash

编译

make

Cado-nfs使用

Cado可以分解大整数，也可以计算离散对数；不过目前测试下来cado的算力还是蛮鸡肋的，拆大整数的话如果因子分解库里有现成的就不要去算了吧，真的是

Cado分解大整数

和factor用起来差不多，几乎一样

Cado计算离散对数

1
2
3

MultiplicativeOrder[23, 10^30 + 57, 473245325750516889002351266535]

23^x ≡ 473245325750516889002351266535(mod 10^30+57)

不知道求离散对数有没有比较快的办法，网上普遍都是先把模数大整数P-1分解，很像Pollard-Rho算法(暂时还没学【看不懂】)

看一下关于该算法的描述

通过概率组合数的增加来提高算率

目标很简单，就是求出指数x，但如果离散对数计算真那么容易，也就没如果了啊
$$
23^x ≡ 473245325750516889002351266535
mod 1000000000000000000000000000057
$$

二话不说我们直接开分

其实这里存在一些分步运算的
$$
令g=23,h=473245325750516889002351266535
\x=log_gh=\frac {log_g’h} {log_g’g}\
g’ 是运算过程的另一个基
$$
那么上一步首先计算的是log_g’h

1	./cado-nfs.py -dlp -ell 454197539 target=473245325750516889002351266535 1000000000000000000000000000057

得到结果

这次就该算log_g’g了

跑出来结果是

还是蛮快滴，毕竟数不是很大，我们的Cado还是蛮争气的嘛

接下来用sagemath开始算x

p = 1000000000000000000000000000057
R = GF(p)
g = R(23)
gx = R(473245325750516889002351266535)
ell = 454197539
log_h = 151131208
log_g = 31054636
temp = log_h * inverse_mod(log_g, ell) % ell
print(temp) 
print(g^temp) #校验模余
print(gx) #模余