是什么阻碍了巨型步长/婴儿步算法成功地解决一个用模块化算法实现的离散日志问题？

Question

基、指数和模的大小是阻碍了用模算法求解DLP中的大步长/步长算法，还是使用特定素数的性质作为模，还是其他什么？

Answer 1

一个固定的公共素数p和\Bbb Z_p^*中乘法阶q的生成器g的离散对数问题(即q是带有g^q\bmod p=1的最小正整数)要求，给定在[0,q)中的随机未知x作为y\gets g^x\bmod p得到的y，发现D10(这是唯一的)。

婴儿步长/巨型步长算法通过\mathcal O(\sqrt q)乘法模块p解决了这一问题，忽略了内存和内存访问的开销。一个乘法模p的成本增长略低于\mathcal O((\log(p))^2)。

因此，“阻止成功使用巨人步/婴儿步算法解决用模块化算法实现的离散日志问题”的主要是选择p和g，这样g的乘法阶q就足够大:至少是所需安全级别的两倍。比如说，128位电阻的256位.

评论更新：波利格-赫尔曼 DLP算法本质上分别攻击q的每个素因子。通过确保乘法阶q的至少一个素因子至少是所需安全级别的两倍来防止它。

此外，由于其他DLP算法(特别是GNFS)，p必须大大大于所需安全级别的两倍(2048位p现在应该是最小的)。

\Bbb Z_p^*中任何元素的乘法顺序总是p-1的除数。因此，确保q很大且具有较大素因子的一种方法是根据上述要求选择素数p，并且使(p-1)/2也是素数(即选择p作为安全素数)。它确保了q在\{1,2,(p-1)/2,p-1\}中，并且允许选择g，从而导致后面两个选项中的一个(这两个选项都在实践中使用)，从而为w.r.t提供了巨大的安全空间。婴儿一步/巨人一步(或波拉德的Rho)和波利格-赫尔曼的结合。

另一种选择是首先选择q (通常作为素数，至少是安全级别的两倍)，并将p构建为足够大(因此更大)的素数，以便q将p-1除以；然后构造乘法阶q的g。它构建了一个所谓的施诺尔群。它用于Schnorr签名和类似的签名，包括DSA，具有缩短签名的优点。

Answer 2

来自维基百科；

• 小步长算法是一种通用算法.它适用于每个有限循环群。

因此，考虑到算法的时间复杂度，必须考虑密钥大小；\mathcal{O}(\sqrt(n))

注意：数域筛具有更好的复杂性，而键长是基于此计算的。