量子计算对椭圆曲线密码的有效性如何？

#1 楼

椭圆曲线密码术目前尚不易受量子计算的影响，因为没有足够大而可靠的量子计算机来解决问题。

但对于足够运行Shor算法的量子计算机来说，它将易受攻击。所有椭圆曲线密码术*都是基于难于找到一个秘密整数$ n $的困难，因为给定椭圆曲线上标量$ P $的标量$ Q = [n] P = P + \ cdots + P $， $ E / k \冒号y ^ 2 = x ^ 3 + 486662 x ^ 2 + x $其中$ k $是素数字段$ \ operatorname {GF}（2 ^ {255}-19）$，这是一条众所周知的曲线如Curve25519。†

在功能强大的量子计算机上，Shor算法将快速找到函数$（a，b）\ mapsto [a] P的周期$（\ delta，\ gamma）$- [b] Q $。任何这样的周期都满足$$ [a-bn] P = [a] P-[b] Q = [a + \ deltaP-[b + \ gamma] Q = [a + \ delta-（b + \ gamma ）n] P $$对于任何$ a $和$ b $包括零，因此$ 0 \ equiv \ delta-\ gamma n \ pmod \ ell $，其中$ \ ell $是$ P $的阶，从我们可以简单地恢复$ n \ equiv \ delta \ gamma ^ {-1} \ pmod \ ell $。

量子位的数量，门的数量以及运行时间来计算这很小顺序为$ \ ell $的位数的多项式函数，在典型的密码学中约为256。大部分量子电路将专门用于计算标量乘法，就像在经典计算机上计算标量乘法一样，花费$ O（\ operatorname {poly} \ log \ ell）$量子门，就像花费$ O（\ operatorname { poly} \ log \ ell）$在传统计算机上的时间和记忆；魔术发生在量子傅立叶变换中，以找到一个仅需$ O（\ log \ ell \ cdot \ log \ log \ ell）$量子门的周期。

今天的危险主要是面对未来的量子密码分析时，文件和对话的长期保密：例如，椭圆形Diffie-Hellman的TLS密钥协议可能会受到Shor算法的攻击，就像有限域Diffie-Hellman一样，启用TLS会话的追溯解密。 （如果对手可以破坏密钥协议密码，则DH的“前向保密”属性，或者实际上是所有相关方擦除会话密钥都没有用。） Ed25519签名，只要您拥有在具有Shor功能的量子计算机可行时更改签名方案的升级途径，危险就不会太大。


*我没有在解决基于等基因的密码学，例如SIDH或CSIDH或SIKE，它也涉及椭圆曲线，但都基于椭圆曲线离散对数以外的问题-即使具有Shor功能的量子计算机实用，这些问题也难以打破。

†这不是攻击椭圆曲线密码学的唯一方法。如SafeCurves中所述，还有许多其他问题值得担心。但是，在设计合理且曲线设计良好的协议中，打破密码术的最著名方法是计算离散日志。

#2 楼

如果可以用于密码分析，则从理论上讲，某些广泛使用的ECC密码系统，包括ECDSA和Ed25519，ECDH ..在理论上易受量子计算的影响。这些密码系统基于离散对数问题，并且变成次指数w.r.t。在量子计算假设下，未知指数的比特大小。

另一方面，存在为后量子安全性而设计的可靠的基于ECC的密码系统，例如SIKE。因此，ECC可能仍是主流的量子后非对称密码学，但它是另一种形式。

我们不知道何时会发生量子密码世代；或如何预测。到目前为止，量子计算机没有什么比经典计算机更好的，而且与密码分析无关。例如：模拟特定量子计算机所处的量子系统，或者（正在辩论中）找到针对一小类优化问题的良好解决方案。

#3 楼

当今使用的大多数公钥算法都是基于两个数学问题，即大数的因式分解（例如RSA）和离散对数的计算（例如DSA签名和ElGamal加密） ）。
两者具有相似的数学结构，并且可以通过Shor算法快速打破。基于椭圆曲线的最新算法（例如ECDSA）使用了对数离散问题的改进，使其与量子计算机相比同样弱。
有关更多详细信息，请参阅以下论文的第4节C小节，其中详细描述了上述声明：
https://arxiv.org/abs/1804.00200?context=cs