破解橢圓曲線算法中的NSA秘密種子

美國國家安全局故意選擇弱算法而產生的安全隱患是可怕的，而找到用于生成橢圓曲線加密算法種子的原始文本則可幫助業界消除擔憂。

近日，密碼學專家FilippoValsorda宣布，在多位密碼學和網絡安全業界知名人士參與和資助下，發起一項破解NIST橢圓曲線算法種子的挑戰賽：為首位能夠破解NIST橢圓曲線算法種子并找出生成它們的原始文本的人提供12288美元的懸賞。如果獲獎者選擇將金額捐贈給慈善機構，懸賞金額將增至36864美元。

一同參與發起該挑戰賽的知名安全專家包括：約翰·霍普金斯大學教授MattGreen、PKI和Chromium貢獻者RyanSleevi、瀏覽器安全專家ChrisPalmer、“Logjamattack”開發人員DavidAdrian以及AWS加密工程師ColmMacCárthaigh。

密碼學的根基

橢圓曲線加密算法（ECC）是一種基于橢圓曲線數學的公開密鑰加密算法。ECC的主要優勢是它相比RSA加密算法使用較小的密鑰長度并提供相當等級的安全性。ECC的另一個優勢是可以定義群之間的雙線性映射，后者已經在密碼學領域得到廣泛應用，例如基于身份的加密。

在現代密碼學領域，橢圓曲線加密（ECC）起著至關重要的作用，是目前最流行的公鑰加密算法，而美國國家標準與技術研究院（NIST）的橢圓曲線算法在這方面占據著核心地位。

構建現代IT和互聯網的三大基礎安全技術：TLS（安全傳輸層協議）、PGP（基于RSA的郵件加密系統）和SSH（安全外殼協議），以及比特幣等數字貨幣加密技術都采用了橢圓曲線加密算法。

NSA的秘密種子

橢圓曲線加密算法依賴于定義在有限字段上的橢圓曲線的數學概念，以生成相對短但安全的密鑰。使用曲線確保對于選定的點（在曲線上），不可計算出用于生成點的倍數（標量），從而為加密提供基礎。

在橢圓曲線加密算法中，種子是用作加密算法或過程的初始輸入的值或值集，用于產生加密密鑰。最終用戶和開發人員不必直接與這些種子交互，而是使用所選加密協議中的曲線參數。真正對種子的起源感興趣的是那些關心系統完整性和安全性的人。

NIST橢圓曲線算法（P-192,P-224,P-256,P-384,和P-521），首次在2000年通過NIST的FIPS186-2（關于“數字簽名標準”）引入，并在1997年使用由美國國家安全局（NSA）提供的種子生成。這些曲線由它們的參數和一個隨機種子值指定，而派生密鑰的確定性過程是透明的且可驗證的，以減輕隱藏漏洞的擔憂。

但是目前，沒有人知道原始種子具體是如何生成的，有傳言和研究表明，它們是NSA提供給JerrySolinas的（五個）英語句子的哈希值（下圖）。Solinas據信使用了一個哈希算法（可能是SHA-1）來生成種子，并可能永遠忘記了這些短語。

Valsorda在博客中提到：“NIST橢圓曲線是大部分現代加密技術的基礎，它們是在90年代末通過哈希NSA提供的種子生成的。但種子具體是如何生成的呢？有傳言說它們是英語句子的哈希值。由于Solinas博士已經在2023年初去世，留下了一個密碼學謎題和很多陰謀論，但這也促成了一個歷史性的密碼破解挑戰。”

FilippoValsorda在社交媒體X上宣稱：任何擁有足夠GPU能力和密碼短語暴力破解經驗的人都可能破解（假定的）SHA-1哈希值并推導出原始句子。

安全社區的擔憂

多年來，密碼學社區對橢圓曲線加密算法始終憂心忡忡，起初是關于Dual_EC_DRBG的爭議，聲稱NSA在算法中設置了后門。最令人擔憂的質疑是NIST曲線算法中是否故意嵌入了漏洞，因為這將使解密敏感數據成為可能。盡管這些質疑缺乏實質性的證據，但橢圓曲線種子的起源仍然是未知的，這在社區中制造了恐懼和不確定性。

挑戰的意義

考慮到NIST橢圓曲線加密算法在現代密碼學中的基礎地位，破解橢圓曲線加密算法種子的挑戰賽具備重大的歷史意義和現實意義。美國國家安全局故意選擇弱曲線算法而產生的安全隱患是可怕的，而找到用于生成算法種子的（五條）原始句子可一勞永逸地消除這些擔憂。

同時由于橢圓曲線加密算法種子本身是密碼學界多年的懸疑，這給整個事件增添了神秘色彩。