作为离散对数模量，带有$ s $的安全质数$ p = 2 ^ k \ pm s $是否难于接受？

#1 楼

简短的答案：是的。

离散对数可以通过多种方式进行攻击：婴儿步巨型步（BSGS），Pollard的Rho，Pohlig-Hellman以及Index Calculus的多种变体，目前最好的是“数字字段筛”。

让$ n $成为我们字段$ \ mathbb {F} _p $的生成器的顺序；它是$ n = p-1 $。我们正在尝试在上述字段中找到给定$ a $和$ b = a ^ x $的$ x $。

Pollard的Rho和BSGS

在Baby-step Giant中步骤，我们试图找到$ i $和$ j $，使$ b（a ^ {-m}）^ i = a ^ j $，其中$ m = \ lceil \ sqrt {n} \ rceil $。一旦找到这样的对，则离散对数$ x = im + j $，如下所示：$ b（a ^ {-m}）^ i = a ^ j \ Leftrightarrow a ^ {x-mi} = a ^ j \ Leftrightarrow x \ equiv mi + j \ pmod {n} $。

为此，我们首先为所有$ j $直到$ m-1 $的表计算所有$ a ^ j $的表。然后我们迭代所有$ i $直到$ m-1 $，然后将$ b（a ^ {-m}）^ i $与$ a ^ j $进行比较。忽略算术成本，此方法的运行时间最多为$ 2（m-1）= O（\ sqrt {n}）$（具有相同的空间需求）。

由于空间需求大，BSGS在实践中很少使用。相反，我们转向Pollard的Rho。该方法的关键是找到冲突的非平凡对$（i，j）$和$（k，l）$，以使$ a ^ ib ^ j \ equiv a ^ kb ^ l $。因此，$ x = \ frac {ki} {lj} \ pmod {n} $，因为$ a ^ ia ^ {xj} = a ^ ka ^ {xl} \ Leftrightarrow a ^ {i + xj} = a ^ {k + xl} \ Leftrightarrow i + xj \ equiv k + xl \ pmod {n} $。

所以Rho很快就找到了一个碰撞。这可以通过各种算法来完成，弗洛伊德（Floyd）是最古老，最著名的算法。好消息是，我们可以在没有巨大桌子的情况下尝试找到碰撞；不好的消息是该算法是概率性的，尽管生日悖论告诉我们，我们应该在$ \ sqrt {n} $步骤中发生碰撞。

无论如何，这些攻击都不是对于安全的质数而言是很好的选择，因为在这种情况下，足够大的订单使得$ \ sqrt {n} $在计算上是不可行的。

Pohlig-Hellman

Pohlig-Hellman方法依赖于以下观察：从$ a $的组中的$ a $和$ b $的$ n $组到$ n $的子组存在同态$ \ phi $命令$ p_i ^ {e_i} $除以$ n $。通常，给定$ n = p_1 ^ {e_1} p_2 ^ {e_2} \ ldots p_m ^ {e_m} $，

$$
\ phi_ {p_i ^ {e_i}}（ a）= a ^ {n / p_i ^ {e_i}}
$$

这使我们能够计算$ \ phi_ {p_i ^ {e_i}}（a）的离散对数$和$ \ phi_ {p_i ^ {e_i}}（b）$，实际上是$ a $和$ b $的离散对数，取值$ p_i ^ {e_i} $。根据此观察结果，可以计算出所有$ n $的本数除数的对数模（使用上一节中的方法），然后使用中文余数定理将它们组合在一起。

如果$ n $具有许多小的素数除数，即，它很平滑，此方法比Rho或BSGS快得多。但是，在安全的情况下，情况并非如此，因为对于非常大的$ q $，订单$ n $是乘积$ 2q $。 Pohlig-Hellman在这里无济于事。

指数微积分

指数微积分是性能最佳的算法的基础，该算法可计算离散对数取模安全素数。假设我们知道$ 2 $和$ 3 $的对数；找到$ 12 $的对数很容易：$ \ log_a12 = 2 log_a2 + log_a3 $，因为$ 12 $分解为$ 2 ^ 2 \乘以3 $。

我们可以将此方法推广为任意元素。首先定义因子库，即所有素数，直至某些绑定的$ B $。然后，找到因子库所有元素的对数（这是棘手的部分）。最后，将$ b $分解为因子库，并简单地添加与找到的因子分解相对应的所有对数。如果$ b $不能完全纳入因数基数，则将$ b $乘以$ a $的某个已知指数，然后重试。

查找所有素数到$ B $的对数需要一些诡计。它有两个主要步骤：


对于[1..n] $中的$ k_i \，（通常通过筛分）至少找到将该因子完全计入因子库的$ \ pi（B）$元素$ a ^ k $。存储$ a ^ {k_i} $及其完整的因式分解。
现在我们有了线性系统（对$ n $取模）： e_ {1,1} \ log_a 2＆+＆e_ {1,2} \ log_a 3＆+＆\ ldots＆+＆e_ {1，{\ pi（B）}}＆=＆{k_1} \\
e_ {2,1} \ log_a 2＆+＆e_ {2,2} \ log_a 3＆+＆\ ldots＆+＆e_ {2，{\ pi（B）}}＆=＆{k_2} \\
&&&&& \\ ldots &&&& \\
e _ {{\ pi（B）}，1} \ log_a 2＆+ && e _ {{\ pi（B）}，2} \ log_a 3＆+ ＆\ ldots＆+＆e _ {{\ pi（B）}，{\ pi（B）}}＆=＆{k _ {\ pi（B）}} \\
\ end {eqnarray}
$$
解决上述线性系统使我们对因子基所需的对数。

该方法中，对于$ B $的适当选择的运行时，是$ \ EXP { （（2 + o（1）（（\ log n）^ {1/2}（\ log \ log n）^ {1/2}））} $。这不是严格的多项式，但对

数字字段筛子

数字字段筛子是目前整数分解和有限域上离散对数的最佳算法。对于离散对数，它是类似于上述索引x演算，并进行了一些重大修改：


我们正在研究数字字段$ \ mathbb {Q} [\ alpha] $和$ \ mathbb {Q} [\ beta] $而不是整数；但是，在某些情况下，存在从此类字段到整数的映射。数字字段由度数为$ d_1 $和$ d_2 $的多项式$ f_1 $和$ f_2 $定义；必须存在一个整数$ m $，使得$ f_1（m）= f_2（m）= 0 \ pmod {p} $。
因数基由两个$ \ mathbb {Q}中的质数形成。 \ alpha $$和$ \ mathbb {Q} [\ beta $$，直到边界$ B_1 $和$ B_2 $。
在筛分期间，我们寻找对$（x，y）$以使$ N_ {f_1}（x + \ alpha y）$和$ N_ {f_2}（x + \ beta y）$分别是$ B_1 $和$ B_2 $平滑，其中$ N_ {f_i} $由 $$
N_ {f_i}（x + \ alpha y）= y ^ {d_i} f_i（x / y）
$$

数字场筛的速度取决于查找的速度$（x，y）$和平滑范数$ N_ {f_i}（x，y）$。反过来，$ N_ {f_i}（x，y）$变得光滑的可能性与其大小有关：它越小，变得光滑的可能性越大。反过来，$ N_ {f_i}（x，y）$的大小由$ x $和$ y $（显然）决定，但也由$ f_i $的系数决定！当$ f_i $的系数非常小时，数字场筛的渐近速度从

$$
\ exp（（1.923 + o（1））（（\ log n）^ {1/3}（\ log \ log n）^ {2/3}）
$$

到

$$
\ exp （（1.526 + o（1））（（\ log n）^ {1/3}（\ log \ log n）^ {2/3}）。
$$

当我们选择非常接近$ 2 ^ k $的素数$ p $时，很容易找到根模为$ p $的稀疏多项式，在您的示例中，$ p = 2 ^ {2048}-1942289 $，我们可以找到度数$ 8 $多项式

$$
x ^ 8-1942289，

因为$ 2 ^ {2048}-1942289 = （2 ^ {256}）^ 8-1942289 $。此多项式的系数非常小，使得该字段中离散对数的数字字段筛选比用于2048位随机素数的要快得多。 >

评论

---

$ \ begingroup $
你是正确的，固定的。
$ \ endgroup $
–塞缪尔·内维斯（Samuel Neves）
13年3月25日在19:12

---

$ \ begingroup $
“ [更快]将会是随机的2048位素数” – hm，对于2048位$ n $，我仍然只能从177减到153，减少24位。（如果我计算得出$ O $正确。）因此，这听起来不像是更实际或更快速的攻击。
$ \ endgroup $
–催眠
2014年1月14日在16:38

---

$ \ begingroup $
“但是，在安全的情况下，情况并非如此，因为阶n是2q的乘积，对于一个非常大的q。Pohlig-Hellman在这里没有太大帮助。”我们不能尝试通过分解$ q-1 $来递归地解决计算$ q $的离散对数的问题。如果$ q-1 $是一个平滑数怎么办？
$ \ endgroup $
–卡尔马留斯
18-4-23在13:09

---

$ \ begingroup $
在这种情况下，您所拥有的是该顺序的顺序（当被视为有限乘法组时）是平滑的。这不会为您提供与您正在使用的组有关的可操作信息。
$ \ endgroup $
–塞缪尔·内维斯（Samuel Neves）
18年4月23日在16:25

---

#2 楼

几年前，我曾问过一个与Arjen Lenstra类似的问题：我正在研究三个汉明重量较轻的2048位素数：


$ p_1 = 2 ^ {2048}-2 ^ {1056} + 2 ^ {736}-2 ^ {320} + 2 ^ {128} + 1 $
$ p_2 = 2 ^ {2048}-2 ^ {1376} + 2 ^ {992} + 2 ^ {896} + 2 ^ {640}-1 $
$ p_3 = 2 ^ {2048}-2 ^ {2016} + 2 ^ {1984}-2 ^ {1856}-2 ^ {1824} + 2 ^ {1792}-2 ^ {1760} + 2 ^ {1696} + 2 ^ {1664} + 1 $

由于所有指数都是$ 32 $的倍数，因此可以进行快速算术（特别是模块化简化）。此外，$ p_1 = 2 ^ {128} q_1 + 1 $，$ p_2 = 2 q_2 + 1 $和$ p_3 = 2 ^ {1664} q_3 + 1 $，其中$ q_1 $，$ q_2 $和$ q_3 $是素数和由$ 2 $生成的子组的顺序分别是$ q_1 $，$ q_2 $和$ q_3 $的倍数。因此，在实现Diffie-Hellman（尤其是使用$ p_2 $，这是一个“安全素数”）或DSA（使用$ p_3 $）时，这些对性能而言看起来不错。但是，使用这种特殊质数的离散对数模可能比使用“普通”质数更容易，尤其是如果应用了特殊数域筛。

Lenstra本人不确定答案，但他提出了问题给其他人（我不知道是谁），谁回答了这个问题：


我简短地搜索了类似于SNFS的多项式，只是检查了2的零次方（使用LLL）无需担心偏斜。

对于$ p_1 $，可以得到：

f1(x)=309485009821345068724781056*x^8 - 75557863725914323419136*x^4
     + 2*x^3 - 37778931862957161709568*x
     + 340282366920938463463374607431768211457

和$ f_1（2 ^ {245}）= p_1 $。

对于2048位数字，它比GNFS好得多，但也比（通常的）SNFS差。也许通过检查偏斜多项式可以得到更好的多项式。
同样，对于$ p_2 $，存在以下9级多项式：

f2(x)=16*x^9 - 17179869184*x^6 + 332306998946228968225951765074280448*x^4
     + x^3 - 4611686018427387904

带有$ f_2（2 ^ {234}）= p_2 $和$ p_3 $：

f3(x)=170141183381241069254316454265464291329*x^9
     - 737869762914022326280*x^8
     + 130668428917922779575948702919181067091968*x^7
     + 2722258934733682407888030063919506653192

与$ f_3（2 ^ {228}）= p_3 $。

可能9级对于2048位数字太大，但是8级和7级多项式似乎也比GNFS多项式好。此外，通过更仔细地检查数字$ p_1 $，$ p_2 $或$ p_3 $，人们可能会发现更好的多项式，从而更接近SNFS的复杂性。

作为参考，我仅了解以下论文O. Schirokauer基本上完成了上面的构造。


底线：当$ p $具有权重小的特殊格式时，SNFS似乎至少部分适用，并且提供了比GNFS更快的DL算法。复杂度方面，当应用SNFS时，您需要一个2n $位的模数才能获得与仅GNFS的$ n $位随机素数相同的抵抗力。因此，为了安全起见，如果您想要一种特殊格式的$ p $（如您建议的格式或我调查过的格式），则需要将长度加倍（4096位模数，而不是2048位模数），这样可以取消另一方面，对于椭圆曲线的基本字段，特殊格式的素数$ p $似乎是合适的；

NIST曲线（例如P-256）使用此类特殊质数。

#3 楼

除了现有的答案以外，$ p $的任何巧妙选择都是有问题的。如果我们使用特殊的$ p $并广泛使用它，则攻击者可以一起攻击所有这些。计算Dlog的大部分工作仅取决于公共参数，而不取决于我们试图获得离散对数的个人价值。
我们甚至有理由相信，国家安全局已成功地针对常见的DH参数进行了此工作。
即使您发现具有快速模幂运算的特殊质数，也没有已知的算法可以加快Dlog的运行速度，但这仅是一个事实，那就是鼓励人们重用此特殊质数，而不是选择自己的质数来削弱它。重用这些特殊参数的连接数。