模为安全素数的整数组离散对数的比特强度

Question

预言片

设p是一个安全素数号码。让\mathbb{Z}_p^*成为整数乘法群模p。我们有\mathbb{Z}_p = \{\,a \in \mathbb{Z} \mid 1 \le a \lt p\,\}。

让g \in \mathbb{Z}_p成为原元\mathbb{Z}_p。让h成为\mathbb{Z}_p的一个元素。

我们定义了一组整数的离散对数问题--模安全素数(DLPS)：

k：找到整数\;\;1 \le k \lt p\;\;和\;\;g^k \equiv h \pmod p。

我们假设求解DLPS的最佳算法是离散对数的数域筛，它具有L_p\left[1/3, \sqrt[3]{64/9}\right] \,=\; e^{\textstyle \left(\sqrt[3]{64/9}+o(1)\right)\big(\ln p\big)^{1/3}\big(\ln \ln p\big)^{2/3}}的预期运行时间

问题

如果我们选择p为2048位安全素数，它至少等于2^{2047}，那么求解D22所需的算术操作的预期数大约等于：

e^{\textstyle \left(\sqrt[3]{64/9}+o(1)\right)\big(\ln 2^{2047}\big)^{1/3}\big(\ln \ln 2^{2047}\big)^{2/3}} \\ \approx \, e^{\textstyle \big(1.923\big)\big(1419\big)^{1/3}\big(7.258\big)^{2/3}} \\ \approx \, e^{\textstyle \big(1.923\big)\big(11.24\big)\big(3.749\big)} \\ \approx \, e^{\textstyle \big(81.00\big)} \\ \approx \, 2^{116.9}

这是正确的吗？

我应该确保(p+1)有一个很大的素因子吗？(使p成为强素数)

如果我没有弄错的话，这是显示p大小函数中的DLPS安全级别的图表：

编辑2019年6月7日:下面是我使用这个离散对数问题的上下文：

上下文

我正在创建一个在线大型多人电子游戏。在这个游戏中，玩家在角色周围移动，并在持久虚拟世界中执行动作。我用离散对数问题作为游戏中的货币.角色所做的每一个动作(四处走动，购买物品，投掷弹丸等)必须由有CPU时间的玩家支付。这样，我就不用花时间监视玩家来检测作弊者 (多个帐户，农业机器人等等)，因为作弊者通常在我的游戏中是明确允许的。

下面是它的工作原理:为了获得在虚拟世界中执行某个动作的权利，玩家请求对游戏服务器进行离散对数挑战。然后，服务器为生成器g和指数k生成随机值，计算结果h \equiv g^k \pmod p，并将g和h的值发送给播放器。然后玩家的客户端k并将其发送回服务器以获得学分。

p的值永远不会改变，g和k的值对于每个挑战都是不同的。玩家可以通过设置指数k值的位长上限来选择挑战的难度(学分的数量与CPU所花费的时间成正比)。

Answer 1

为了证明工作方案，您最好让p足够大，不必担心NFS (例如，2048位或更多)，或者使用椭圆曲线组(例如P256或Curve25519)。

相反，您可以调优一般攻击(例如，大步长-小步)是最佳攻击，并使用它来选择困难(k的范围)；如果求解者知道0 < k \le M，那么这些泛型搜索将采用\sqrt{M}组操作(模块乘法，椭圆曲线加法)，这是搜索者所能做的最好的(假设他对组结构没有任何进一步的洞察力--这就是我们试图通过使NFS不可行来确保的)。

现在，虽然这将作为“全面工作的证明”，但我不确定它是否真的满足了您的要求，因为具有大量并行性(例如僵尸网络场)的人可能能够显著加快计算速度。

一种更好的方法可能是让服务器发布整数g、k和复合n，并要求客户端计算g^{2^k} \bmod n；这种类型的操作不是非常可并行的(因为每一次平方操作都必须按顺序进行)，而服务器(谁知道n = pq的因式分解)可以通过由relation A \equiv g^{2^k \bmod p-1} \pmod p检查声称的答案A来验证这一点。