Edwards-curve Digital Signature Algorithm

no extension

ネットであちこち眺めていて気がついたのだが SP 800-57 第一部の Rev.5 最終版が2020年5月にリリースされていた。

私はセキュリティや暗号技術の専門家ではないし Rev.5 の変更点が（軽微なものも合わせて）67項目もあって全部は紹介しきれないので，ひとつだけ

In Section 2.2, EdDSA was added. Modified ECDSA.

について関連情報を覚え書きの形で記しておく。

RFC 8032: Edwards-Curve Digital Signature Algorithm (EdDSA)

EdDSA のオリジナルは2011年に公開された “High-speed high-security signatures ” らしい。 その後も改良版が出たり色々あって，2017年に RFC 8032 として標準化された。

EdDSA は以下の特徴を持っている。

  1. EdDSA provides high performance on a variety of platforms;
  2. The use of a unique random number for each signature is not required;
  3. It is more resilient to side-channel attacks;
  4. EdDSA uses small public keys (32 or 57 bytes) and signatures (64 or 114 bytes) for Ed25519 and Ed448, respectively;
  5. The formulas are “complete”, i.e., they are valid for all points on the curve, with no exceptions. This obviates the need for EdDSA to perform expensive point validation on untrusted public values; and
  6. EdDSA provides collision resilience, meaning that hash-function collisions do not break this system (only holds for PureEdDSA).

特に2番目が重要。

これまでの NIST 標準の（ECDSA を含む） DSA は署名の度にランダムな値をひとつ決めないといけないのだが，ここの実装をサボると，最悪の場合，秘密鍵の漏洩に繋がる。 更に言うと，かつて SP 800-90A に載っていた疑似乱数生成器 Dual_EC_DRBG に NSA の関与が疑われる欠陥が発覚し SP 800-90A を改訂する騒ぎにまで発展したこともある。

このように DSA の具体的な実装について常に懸念が付きまとっているため，より安全性が高いとされる EdDSA が注目されることとなった1。

EdDSA で使える楕円曲線にはかなりのバリエーションがある のだが， RFC 8032 に記載されているのは以下の2つである2。

楕円曲線名 鍵長（bytes） 強度（bits）
edwards25519 32 128
edwards448 57 224

生成した ECC 鍵を2031年以降も使い続けるにはセキュリティ強度にして128ビット以上必要だが，この2つの楕円曲線であれば十分であることが分かる。

NIST 標準としての EdDSA

EdDSA の RFC 化に伴い，以下の NIST 標準文書にも EdDSA が追加されることになった。 ただし今のところはまだドラフト版である。

ちなみに両方共パブリックコメントは2020年初に締め切られている。

FIPS 186-5 および SP 800-186 が正式リリースされれば，政府調達でもなんでも，大手を振って EdDSA を使えるようになる（笑）

【2023-02-04 追記】 FIPS 186-5 および SP 800-186 正式版がリリースされた

EdDSA の実装

OpenPGP と GnuPG

OpenPGP は RFC 6637 で正式に ECC を組み込んだが，この中に EdDSA は含まれていない。 ただし，次期 OpenPGP となる RFC 4880bis では EdDSA を組み込み済みで GnuPG の最新版では既に EdDSA 鍵を生成し使用することができる。

なお，最新の GnuPG では edwards25519 のみサポートしているようだ。

OpenSSH

OpenSSH では EdDSA/edwards25519 鍵を生成・使用できる。 鍵生成は

$ ssh-keygen -t ed25519

で可能。

OpenSSL

現在の OpenSSL は EdDSA をサポートしている。 edwards25519 および edwards448 を指定可能。

【おまけ】 量子コンピュータ耐性

現在，公開鍵暗号の主流である IFC (Integer Factorization Cryptosystems) および FFC (Finite Field Cryptosystems) の各アルゴリズムは量子コンピュータによる攻略法が既にあり，十分な性能を獲得すれば短時間で攻略可能になると考えられている。 ECC も FFC のバリエーションであり，これに含まれる。

しかし，2020年時点の性能では128ビット以上のセキュリティ強度であれば現実的な脅威には至っていないようだ。

例えば、量子コンピュータを用いて2048ビットRSA合成数の素因数分解を行う場合には、量子誤りが一切ないという理想的な環境下でも、4098量子ビットが必要であり、1012～1013回のゲート演算が必要であると見積もられています。また、量子誤りがあるという現実的な環境下では、2000万量子ビットが必要であるという見積もりもあります。
量子コンピュータの性能を測る上での指標（量子ビット数、量子誤りの大きさ、演算可能回数など）や、量子コンピュータの開発状況もあわせて考慮にいれると、近い将来に、2048ビットの素因数分解や256ビットの楕円曲線上の離散対数問題が解かれる可能性は低いと考えます。

ただし，量子コンピュータ開発は成長が著しい分野でもあり，今後も成り行きを注視していく必要がある。

【おまけ2】 CRYPTREC による EdDSA の評価

2021年に公開された「CRYPTREC Report 2020」に EdDSA に対する評価が載っていたので紹介する。

難しい話はすっ飛ばして総評だけつまみ食いすると

  • 総評：下記の観点から、EdDSA の構成に関わる安全性において、EdDSA が ECDSA に劣ると考えられる点は無いと思われると述べている。
    • Schnorr 署名をもとに EdDSA は構成されているため、ランダムオラクルモデルで安全性が証明されている Schnorr 署名に対する安全性評価を参考にすることができる。
    • Schnorr 署名との大きな違いはノンスの生成方法であるが、EdDSA におけるノンスの生成方法は、署名の内部乱数を弱い疑似乱数生成器に委ねることによる危険を排除し、現実的な脅威を回避するための配慮が施されている。
    • 比較対象となる ECDSA については、既存結果として generic group model でのみ安全性が証明されている。

とのこと。 ノンスの評価やサイドチャネル攻撃耐性など具体的な話は本文を参照のこと。

ブックマーク

参考図書

photo
暗号技術入門 第3版　秘密の国のアリス
結城 浩 (著)
SBクリエイティブ 2015-08-25 (Release 2015-09-17)
Kindle版
B015643CPE (ASIN)
評価     

SHA-3 や Bitcoin/Blockchain など新しい知見や技術要素を大幅追加。暗号技術を使うだけならこれ1冊でとりあえず無問題。

reviewed by Spiegel on 2015-09-20 (powered by PA-APIv5)

  1. DSA に対する懸念は，実装に必要な技術要素が多すぎる点にあるかもしれない。如何にシンプルな設計で要件を満たすかってのは安全性を考える上でも重要であるというよい事例になっていると思う。 ↩︎

  2. edwards25519 は Curve25519 と双有理同値である。ちなみに Curve25519 は ECDH 用の楕円曲線およびそのライブラリで，公有（public domain）のソフトウェアとして公開されている。 ↩︎