如果离散对数问题是困难的，怎么会有不安全的椭圆曲线？

Question

离散对数问题是数学陷阱门函数托换椭圆曲线密码学。如果很难从陷阱门爬回来，怎么会有不安全的椭圆曲线呢？

任何答案对我来说都是最有益的，如果这是可能的话，如果它对数学没有影响的话。

Answer 1

椭圆曲线上的离散对数在以下意义上是困难的:在$n$-位曲线上，求解DL的代价是$2^{n/2}$。因此，这是不可行的，只要$n$是足够大，使成本抑制。256位曲线足够大，60位曲线不够大.

此外，有些曲线具有特殊的结构，可以更快地计算DL。值得注意的是：

• 如果曲线阶不是素数或没有大素数因子，则DL更容易(同样适用于正常的非曲线DL)。
• 一些曲线具有较低的嵌入度，使得在有限域扩张的乘法子群中将曲线上的DL转换成一个相对容易的DL。这在数学上很重。如果曲线有些减弱但不太大，那么当允许计算配对时，它仍然是安全的，这是一种代数运算，对于一些复杂的密码协议(例如基于身份的加密)是有用的。
• 一些曲线使得安全地实现它们变得更容易，例如，不通过侧通道泄漏秘密信息。

生成一条新的曲线需要尝试方程参数，并检查得到的曲线不是已知的“坏情况”之一。在实践中，非素数阶是最常见的情况；对于256位曲线，在得到具有素数级的曲线之前，您需要尝试大约100条曲线。低嵌入度的曲线是非常罕见的，而且易于检查。

Answer 2

托马斯的回答很好。我要补充的是，在形式上，说“我们假设离散日志问题很难”这样的话是没有意义的。更确切地说，我们必须提到一个特定的组(或组族)，并假定这些组中的问题很难解决。这是因为它在某些群(例如，$\mathbb{Z}_p$上的加法群)中非常容易，而在另一些群中则被认为很难。因为每条曲线都定义了一个不同的组，所以肯定会有一些曲线并不难。

Answer 3

为了放大Yehuda Lindell的答案，即使在一个群体中，这里有一个2046位模数$p$的例子，其中$(\mathbb /p\mathbb Z)^^乘以$中的离散日志，就像标准模乘Diffie-Hellman中的那样，非常容易计算：

0x2465a7bd85011e1c9e0527929fff268c82ef7efa416863baa5acdb0971dba0ccac3ee4999345029f2cf810b99e406aac5fce5dd69d1c717daea5d18ab913f456505679bc91c57d46d9888857862b36e2ede2e473c1f0ab359da25271affe15ff240e299d0b04f4cd0e4d7c0e47b1a7ba007de89aae848fd5bdcd7f9815564eb060ae14f19cb50c291f0bbd8ed1c4c7f8fc5fba51662001939b532d92dac844a8431d400c832d039f5f900b278a75219c2986140c79045d7759540854c31504dc56f1df5eebe7bee447658b917bf696d6927f2e2428fbeb340e515cb9835d63871be8bbe09cf13445799f2e67788151571a93b4c1eee55d1b9072e0b2f5c4607f.

2046位模块应该是安全的，对吗？没关系，您请。首先，如果它们是素数(或者至少如果您不知道它们的素因式分解，但是对于公共DH或DSA参数，您希望了解它们的这类事情)，这会有所帮助。这个数$p$不是素数；相反，它是除2以外的前232个素数的乘积。因此，在给定固定$h$的情况下，要求解$x$的$$g^x \equiv \pmod $$，只需计算离散日志( $x_3$、$x_5$、$x_7$等)，满足条件。

开始{x_3}和\equiv \pmod 3，\ g^{x_5}和\ 5，\&vdots\结束{对齐*}

独立地，然后用中国剩余定理将它们组合成$x$的一个解：

开始{align*}x &\equiv x_3 \pmod{phi(3)}，\x&equiv x_5 \pmod{phi(5)}，\ &\vdots \结束{align*}

其中$\phi(3) =3-1$，$\phi(5) =5-1$等，因为它们都是素数。

这个算法非常便宜，你可以在几个小时内用教科书长除法和教科书乘法用笔和纸来完成它。但是这个算法的简单性并不意味着在$(\mathbb /q\mathbb Z)^\$中计算离散日志是多么简单或困难，其中$q$是RFC 3526组#14模。

0xffffffffffffffffc90fdaa22168c234c4c6628b80dc1cd129024e088a67cc74020bbea63b139b22514a08798e3404ddef9519b3cd3a431b302b0a6df25f14374fe1356d6d51c245e485b576625e7ec6f44c42e9a637ed6b0bff5cb6f406b7edee386bfb5a899fa5ae9f24117c4b1fe649286651ece45b3dc2007cb8a163bf0598da48361c55d39a69163fa8fd24cf5f83655d23dca3ad961c62f356208552bb9ed529077096966d670c354e4abc9804f1746c08ca18217c32905e462e36ce3be39e772c180e86039b2783a2ec07a28fb5c55df06f4c52c9de2bcbf6955817183995497cea956ae515d2261898fa051015728e5a8aacaa68ffffffffffffffff.

使用中国余数定理的相同算法不起作用，因为$q$是素数，所以不能独立地解决问题的所有因素，然后将结果重新组合成一个解。

场、曲线形状、曲线参数等参数的选择对椭圆曲线离散对数计算的方便性和难度的影响与模量的选择对模乘离散对数计算的方便或困难有着同样的影响。