茶年 · 中文维基百科

椭圆曲线密码学

Wikipedia · 2026-03-24 维基百科 👁 0 阅读

椭圆曲线密码学（，缩写：）是一種基于椭圆曲线数学的公开密钥加密演算法。

ECC的主要优势是它相比RSA加密演算法使用較小的密鑰長度并提供相当等级的安全性。ECC的另一个优势是可以定义群之间的双线性映射，基于Weil对或是Tate对；双线性映射已经在密码学中发现了大量的应用，例如基于身份的加密。
歷史
椭圆曲线在密码学中的使用是在1985年由和分别独立提出的。椭圆曲线密码学的演算法是在2004年至2005年開始廣泛應用。
理論
針對密碼學應用上的椭圆曲线是在有限域（不是實數域）的平面曲线，其方程式如下：

: y^2 = x^3 + ax + b, \,

有一個特別的无穷远点（標示為∞）。座標會選定為特定的有限域，其特征不等於2或是3，也有可能是更複雜的曲線方程。

由椭圆曲线產生的集合是阿贝尔群，以无穷远点為單位元。此群的結構會繼承以下代数簇中除子的結構：

: \mathrm{Div}^0 (E) \to \mathrm{Pic}^0 (E) \simeq E, \,
密钥交换
椭圆曲线密码学的许多形式有稍微的不同，所有的都依赖于被广泛承认的解决「椭圆曲线离散对数」问题的困难性上，对应有限域上椭圆曲線的群。
伽罗瓦域
对椭圆曲线来说最流行的有限域是以素数为模的整数域（参见模运算）GF(p)，或是特征为2的伽罗瓦域 GF（2m）。后者在专门的硬件实现上计算更为有效，而前者通常在通用处理器上更为有效。专利的问题也是相关的。一些其他素数的伽罗瓦域的大小和能力也已经提出了，但被密码专家认为有一点问题。

给定一条椭圆曲线E以及一个域GF(q)，考虑具有(x, y)形式有理数点E(q)的阿贝尔群，其中x和y都在GF(q)中并且定义在这条曲线上的群运算"+"（运算"+"在條目椭圆曲线中描述）。然后定义第二个运算"" | Z×E(q)->E(q)：如果P是E(q)上的某个点，那么定义2P=P+P, 3P=2P+P=P+P+P等等。針對给定整数j和k，j(kP)=(jk)P=k(jP)。椭圆曲线离散对数问题（ECDLP）就是给定点P和Q，确定整数k使kP=Q。
--
一般认为在一个有限域乘法群上的离散对数问题（DLP）和椭圆曲线上的离散对数问题（ECDLP）並不等价；ECDLP比DLP要困难的多。

在密码的使用上，會選擇曲线E(q)和其中一个特定的基点G，並且公開這些資料。會再選擇一个随机整数k作为私钥；公布值為P=kG的公钥（注意假设的ECDLP困难性意味着k很难从P中确定）。如果Alice和Bob有私钥kA和kB，公钥是PA和PB，那么Alice能计算kAPB=(kAkB)G；Bob能计算同样的值kBPA=(kBkA)G*。

这允许一个“秘密”值的建立，这样Alice和Bob能很容易地计算出，但任何的第三方却很难得到。另外，Bob在处理期间不会获得任何关于kA的新知识，因此Alice的私钥仍然是私有的。

加密
基于这个秘密值，用来对Alice和Bob之间的报文进行加密的实际方法是适应以前的，最初是在其他组中描述使用的离散对数密码系统。这些系统包括：

  • 椭圆曲线迪菲-赫尔曼密钥交换（ECDH）
  • （ECMQV）
  • ElGamal离散对数密码体制（ECElGamal）
  • 椭圆曲线数字签名算法（ECDSA）

对于ECC系统来说，完成运行系统所必须的群操作比同样大小的因数分解系统或模整数离散对数系统要慢。不过，ECC系统的拥护者相信ECDLP问题比DLP或因数分解问题要难的多，并且因此使用ECC能用小的多的密钥长度来提供同等的安全，在这方面来说它确实比例如RSA之类的更快。到目前为止已经公布的结果趋于支持这个结论，不过一些专家表示怀疑。

ECC被广泛认为是在给定密钥长度的情况下，最强大的非对称算法，因此在对带宽要求十分紧的连接中会十分有用。

建议
美国国家标准与技术局和ANSI X9已经设定了最小密鑰長度的要求，RSA和DSA是最小2048位，ECC是最小224位，相应的對稱密鑰加密的密钥长度是最小128位，這樣的組合在2030年以前是安全的。

在2005年2月16日，NSA宣布决定采用椭圆曲线密码的战略作为美国政府标准的一部分，用来保护敏感但不保密的信息。NSA推荐了一组被称为Suit B的算法，包括用来密钥交换的橢圓曲線Menezes-Qu-Vanstone（ECMQV）和橢圓曲線Diffie-Hellman（ECDH），用来數字簽名的椭圆曲线数字签名算法。这一组中也包括AES和SHA。

安全性
旁路攻击
椭圆曲线密码学和其他的离散对数不同，在离散对数中可以用相同的程序處理平方以及乘法，但椭圆曲线上的加法在加倍（P = Q）和一般加法（P ≠ Q）上會因為使用的座標系統而有顯著的不同。因此有關旁路攻击（例如時間或能量分析）的防治就格外的重要。例如用固定模式窗口（fixed pattern window，也稱為comb）的方式（這不會增加運算時間）。另外也可以使用，這是一類特別的椭圆曲线，其中的加倍和加法可以用同一個運算完成。另一個ECC系統的疑慮是差別錯誤分析的風險，特別是在智慧卡上的應用。

後門
密碼學專家擔心，美国国家安全局（NSA）可能已在至少一個以椭圆曲线為基礎的偽亂數產生器中置入後門。前美國中央情報局（CIA）職員爱德华·斯诺登所洩漏的內部摘要暗示，NSA在双椭圆曲线确定性随机比特生成器標準中加入後門。微軟公司的研究人員針對此標準中一個的疑似後門進行分析，並得出結論：擁有此演算法私鑰的攻擊者，可以只根據32位元組的PRNG輸出，找到加密的密鑰。

密碼學家發起了「SafeCurves」計劃，整理並列出安全性易實現且設計過程完全公開可驗證的曲線，以減少曲線被植入後門的可能性。

量子計算攻擊
如果攻击者拥有大型量子计算机，那么他可以使用秀尔算法解决离散对数问题，从而破解私钥和共享秘密。目前的估算认为：破解256位素数域上的椭圆曲线，需要2330个量子比特与1260亿个托佛利门。相比之下，使用秀尔算法破解2048位的RSA则需要4098个量子比特与5.2万亿个托佛利门。因此，椭圆曲线会更先遭到量子计算机的破解。目前还不存在建造如此大型量子计算机的科学技术，但是密码学家已经积极展开了後量子密碼學的研究。

無效曲線攻擊
若ECC是在虛擬機器運作，攻擊者可以用無效的曲線來取得完整的PDH私鑰。

相關條目

  • （高效密碼學標準組）
  • 椭圆曲线数字签名算法
  • 橢圓曲線迪菲-赫爾曼金鑰交換
  • 公開金鑰加密
  • 抽象代数
  • 奇幻熊

*
*

  • 加密貨幣
  • Curve25519

*

  • DNSCurve
  • RSA加密演算法

*

  • 橢圓曲線迪菲-赫爾曼金鑰交換 (ECDH)
  • 椭圆曲线数字签名算法 (ECDSA)
  • EdDSA

*

  • 橢圓曲線的純量乘法

*
*
*

  • 公开密钥加密
  • 量子密碼學

*

参考文献

外部链接

#有限域 #公钥密码学 #橢圓曲線密碼學

评论 (0)

  • 还没有评论，来抢沙发吧。