密碼學 - ECDSA 演算法

上一頁
下一頁

橢圓曲線數字簽名演算法 (ECDSA) 是最複雜的公鑰密碼加密技術之一。橢圓曲線密碼學生成的金鑰比數字簽名方法生成的金鑰更小。一種稱為橢圓曲線密碼學的公鑰加密利用了有限域上橢圓曲線的代數結構。

橢圓曲線密碼學主要用於建立偽隨機數和數字簽名等。數字簽名是一種身份驗證機制，它使用公鑰對和數字證書來驗證資訊接收者或傳送者的身份。

什麼是橢圓曲線數字簽名演算法？

ECDSA 執行與任何其他數字簽名相同的函式，但效率更高。這樣，ECDSA 與其他數字簽名演算法一樣，可以使用更小的金鑰提供相同的安全級別。ECDSA 用於建立 ECDSA 證書，這是一種用於驗證證書所有者的電子文件。證書包含有關用於建立證書的金鑰、證書所有者和發行者簽名的資訊，發行者簽名是一個經過驗證的可信實體。

這個可信的發行者通常是具有已簽名證書的證書頒發機構，該證書可以透過信任鏈追溯到原始的發行者證書頒發機構。

ECDSA 透過分析橢圓曲線並在曲線上選擇一個點來操作。該點乘以另一個數，在曲線上產生一個新點。

即使原始點可用，也很難在曲線上找到新點。ECDSA 的複雜性意味著它比當前的加密破解方法更安全。除了對當前攻擊方法更安全之外，ECDSA 還具有許多其他優點。

ECDSA Algorithm

金鑰和簽名大小

ECDSA 認為所需的私鑰的位大小大約是安全級別（以位為單位）的兩倍，這與一般的橢圓曲線密碼學類似。例如，在 80 位的安全級別下，ECDSA 私鑰的大小約為 160 位，這需要攻擊者執行大約 280 次操作才能發現私鑰。

但是，DSA 和 ECDSA 的簽名大小相同：大約 4t 位，其中 t 是公式 2t 中的指數，用於 80 位安全級別，即大約 320 位，或 280 次操作。

簽名生成

假設 Alice 想給 Bob 傳送一條簽名的訊息。他們必須首先就曲線的引數達成一致 (CURVE, G, n)。除了曲線的域和方程之外，還需要基點 G（曲線上素數階的基點）；n 是點 G 的乘法階。

引數

  • CURVE - 用於橢圓曲線的方程和域。
  • G - 橢圓曲線的基點；曲線上產生大素數階子群 n 的一個點。
  • n - G 的整數階，這表示 n x G = O，其中 O 是單位元。
  • dA - 隨機選擇的私鑰。
  • QA - 公鑰 dA x G（橢圓曲線計算）
  • m - 要傳輸的文字

起點 G 的階 n 必須是素數。事實上，Z/nZ 必須是一個域，因為我們假設環的每個非零元素都是可逆的。這意味著 n 必須是一個素數。

Alice 生成一對金鑰，包括公鑰曲線點 QA = dA x G 和私鑰整數 dA，後者是從區間 [1, n-1] 中隨機選擇的。標量的橢圓曲線點乘法用符號 x 表示。

簽名訊息

Alice 為了簽名訊息執行以下步驟：

  • 確定 e = HASH(m)。（這裡，HASH 指的是將輸出轉換為整數的密碼雜湊演算法，例如 SHA-2。）
  • 令 z 表示 e 的最左邊的 Ln 位，其中 Ln 表示群階 n 的位長度。（請注意，z 不長於 n，儘管它可以是。）
  • 選擇 k，一個來自 [1, n-1] 的密碼安全的隨機整數。
  • 計算曲線點，其中 k x G = (x1, y1) = 0。
  • 透過取 x1 mod n 來計算 r。如果 r = 0，請參考步驟 3。
  • 必須計算 S = k-1 (z + rdA) mod n。如果 s = 0，請參考步驟 3。
  • 這對 (r, s) 就是簽名。此外，(r, -s mod n) 也是有效的簽名。

如果 k 由不可靠的隨機數生成器產生，則 ECDSA 簽名可能會洩露私鑰的另一種方法。2013 年 8 月，Android 比特幣錢包的使用者由於隨機數生成錯誤而損失了資金。

您可以透過從訊息和私鑰派生 k 來生成確定性簽名，從而完全避免隨機數的建立，並確保 k 對於每次通訊都是唯一的。

使用 Python 實現 ECDSA

基本上，我們將使用 Python 的 ecdsa 庫，它提供了處理 ECDSA 演算法的功能。我們還將使用 hashlib 庫將給定的訊息轉換為雜湊形式。以下是使用 ecdsa 和 haslib 庫的 ECDSA 的簡單 Python 實現：

示例

from ecdsa import SigningKey, VerifyingKey, SECP256k1
import hashlib

# Create a new private key
private_key = SigningKey.generate(curve=SECP256k1)

# Derive the public key from the private key
public_key = private_key.verifying_key

# Some message to sign
message = b"Hello, Tutorialspoint!"

# Hash the message
hash_message = hashlib.sha256(message).digest()

# Sign the hashed message with the private key
signature = private_key.sign(hash_message)

# Verify the signature using the public key
is_valid = public_key.verify(signature, hash_message)

if is_valid:
   print("Signature is valid.")
else:
   print("Signature is not valid.")

以下是上述示例的輸出：

輸入/輸出

執行以上程式碼需要安裝Python的hashlib和ecdsa庫。可以使用`pip install 'libraryName'`安裝這些庫。將程式碼儲存到檔案中，然後使用`python ecdsa_implement.py`執行此程式碼。這裡我們的檔名是ecdsa_implement.py。檔案的輸出如下：

Signature is valid.

ECDSA的安全性

雖然RSA是一種非常安全的加密方法，但ECC可能更有效。

理論上，量子計算機可以透過有效解決RSA的基礎——因式分解問題來破解RSA。關於這何時會發生存在很多爭議。但可以肯定的是，與RSA相比，由於其複雜性，ECC對量子計算攻擊更具抵抗力。

抵抗力有多強？在一篇研究論文中，一位荷蘭數學家將破解加密方法比作燒水。目標是確定破解特定加密演算法所需的能量以及可以用該能量燒開的開水量。

換句話說，破解228位ECC金鑰可以燒開地球上所有的水，而破解228位RSA金鑰所需的能量卻比燒開一茶匙水還要少。要達到與RSA相同的安全級別，需要2380位的金鑰大小。

ECDSA的弱點

根據現有資訊，橢圓曲線數字簽名演算法的弱點分析如下：

  • 實現複雜性 - ECDSA 的正確實現比 RSA 更困難，這可能會增加實現錯誤的可能性。實現不當的橢圓曲線數字簽名演算法可能會危及安全性。
  • 輸出長度 - 對於相同的安全級別，ECDSA 比 RSA 產生的輸出長度更短。3072 位 RSA 簽名等於 256 位 ECDSA 簽名的安全級別。較短的輸出長度可能會使 ECDSA 簽名更容易受到暴力攻擊。
  • 橢圓曲線的選擇 - 橢圓曲線很重要，因為某些曲線允許攻擊者進行暴力破解加密。選擇能夠防止攻擊者找到離散對數問題的多項式時間實現的橢圓曲線至關重要。
  • 扭曲攻擊 - “扭曲攻擊”是一種潛在的弱點，攻擊者向訊息接收者傳送一組精心選擇的橢圓曲線點進行加密。如果訊息接收者的演算法實現不當，攻擊者可能會能夠從密文中提取私鑰。
  • 安全性與實現複雜性 - ECDSA 的實現難度會影響其安全性。確保安全實現對於避免漏洞至關重要。

ECDSA 的用途

  • 安全的通訊協議 - ECC 用於許多安全的通訊協議中，以實現加密、數字簽名和金鑰交換。例如，用於安全網路通訊的虛擬專用網路 (VPN)，用於安全遠端登入的安全外殼 (SSH) 以及用於安全線上瀏覽的傳輸層安全 (TLS)。
  • 區塊鏈技術和加密貨幣 - 比特幣、以太坊和萊特幣等多種加密貨幣使用橢圓曲線密碼學來建立公鑰和私鑰對以及簽名交易。ECC 提供了保護數字資產和保證區塊鏈網路完整性所需的加密保護。
  • 智慧卡和嵌入式系統 - ECC 常用於保護電子護照、支付系統、訪問控制系統以及其他需要小型安全加密解決方案的應用程式。
ECDSA Usage

ECDSA 的優點

  • 2005 年制定了新的標準。
  • 標準化減少了駭客時間，因此時間更短。
  • 其複雜性和新穎性使其不易受到攻擊。
  • 對於新興的公鑰密碼學協議來說是一個理想的替代方案。

ECDSA 的缺點

  • 實現複雜，可能導致錯誤的實現。
  • RSA 於 1995 年標準化，擁有更悠久的歷史。
  • 由於其悠久的歷史，RSA 仍然是最廣泛使用的方法。
  • RSA 更易於設定，部署障礙更少。
列印頁面
上一篇
下一篇
廣告