論文翻訳: High-speed high-security signatures

Daniel J. Bernstein¹, Niels Duif², Tanja Lange², Peter Schwabe³, and Bo-Yin Yang⁴

Abstract

この論文ではセキュリティレベル \(2^{128}\) の楕円曲線上で $390 の大衆市場向けクアッドコア 2.4GHz Intel Westmere (Xeon E5620) CPU が 1 秒あたり 109,000 署名を生成し、71,000 署名を検証することができることを示している。これらのパフォーマンスの数値にはソフトウェアサイドチャネル攻撃に対する強力な防衛が含まれている。秘密鍵からの配列インデックスや分岐条件へのデータフローは存在しない。

Table of Contents

1. Abstract
2. 1 導入
   1. 過去の ECC 研究との比較
   2. 他の署名システムとの比較
3. 2 署名システム
   1. EdDSA パラメータ
   2. EdDSA 鍵と署名
   3. 弱い鍵
   4. 展性
   5. 曲線の選択
   6. \(r\) の擬似ランダム生成
   7. 過去の ElGamal 変種との比較
4. 3 モジュロ \(2^{255}-19\) の高速計算
   1. Nehalem CPU での乗算
   2. Radix-\(2^{64}\) 表現
   3. Radix-\(2^{51}\) 表現
   4. 乗算と平方演算
   5. 加算、減算および反転
5. 4 メッセージ署名
   1. 高いレベルの戦略
   2. 低レベル, パート1: 表検索
   3. 低レベル, パート2: 楕円曲線加算
   4. テンプレート攻撃
   5. 結果
6. 5 署名の検証
   1. 高速復元
   2. 高速単一署名検証
   3. 高速バッチ検証
   4. 高速マルチスカラー乗算
   5. 結論
7. References
8. 翻訳抄

• ¹ Department of Computer Science, University of Illinois at Chicago, Chicago, IL 60607–7053, USA djb@cr.yp.to
• ² Department of Mathematics and Computer Science, Technische Universiteit Eindhoven, P.O. Box 513, 5600 MB Eindhoven, the Netherlands nielsduif@hotmail.com, tanja@hyperelliptic.org
• Department of Electrical Engineering, National Taiwan University, 1, Section 4, Roosevelt Road, Taipei 10617, Taiwan peter@cryptojedi.org
• ⁴ Institute of Information Science, Academia Sinica, 128 Section 2 Academia Road, Taipei 115-29, Taiwan by@crypto.tw

1 導入

この論文ではいくつかの魅力的な機能を備えた公開鍵署名のソフトウェアを紹介する:

高速な単一署名の検証

ソフトウェアは Intel が広く展開している Nehalem / Westmere CPU ラインで署名を検証するのに 273,364 サイクルしかかからない (このパフォーマンス測定は短いメッセージの場合である; 非常に長いメッセージに対しては、ハッシュ化処理時間に依存する)。Nehalem と Westmere は 2008 年から 2010 年にリリースされた全ての Core i7, i5 および i3 CPU と、同じ期間中にリリースされたほとんどの Xeon CPU を含んでいる。

さらに高速なバッチ検証

ソフトウェアはわずか 855 万サイクルで 64 の個別の署名検証をバッチ実行 (64 個の公開鍵の下で 64 個のメッセージの 64 この署名を検証) 実行する。つまり、1 署名あたり 134,000 サイクル未満である。ソフトウェアは L1 キャッシュに容易に収まるためコア間の競合は無視できる。クアッドコア 2.4GHz Westmere は最大の検証遅延を 4 ミリ秒未満に保ちながら 1 秒間に 71,000 署名を検証する。

非常に高速な署名

ソフトウェアはメッセージの署名に 87,548 サイクルしかかからない。クアッドコア 2.4GHz Westmere は 1 秒間あたり 109,000 メッセージに署名する。

高速な鍵生成

鍵の生成は署名と同程度に高速である。オペレーティングシステムから安全な乱数を取得する僅かなペナルティが存在する。Linux での /dev/urandom のコストは約 6,000 サイクルである。

高いセキュリティレベル

このシステムには \(2^{218}\) のセキュリティターゲットを持つ; これを破るには NIS P-256 や \(\approx\) 3000 ビット鍵を持つ RSA、強力な 128 ビットのブロック暗号などを破るのと同等の難易度を持つ (同じ手法でも他のセキュリティレベルでは速度が向上する)。既知の最良の攻撃は実際には平均で \(2^{140}\) ビット操作以上のコストがかかり、ビット操作の数が減るに従って成功確率は二次的に低下する。

フールプルーフセッション鍵

この論文の署名は決定論的に生成される; 鍵生成は新しいランダム性を消費するが、新しい署名では必要がない。これは速度機能だけではなくセキュリティ機能でもあり、最近の Sony PlayStation 3 のセキュリティシステム崩壊に直接関連している。詳細についてはセクション 2 を参照。

衝突回復力

ハッシュ関数の衝突がこのシステムを破壊することはない。これにより、選択ハッシュ関数の脆弱性に対する防衛レイヤーが追加される。

秘匿の配列インデックスなし

ソフトウェアは RAM 上の秘匿アドレスにデータの読み書きを行うことはない; アドレスのパターンは完全に予測可能である。従って、ソフトウェアはキャッシュタイミング攻撃、ハイパースレッディング攻撃および CPU キャッシュを介したアドレス漏洩によるその他のサイドチャネル攻撃の影響を受けない。

秘匿の分岐条件なし

ソフトウェアは秘匿データに基づいて条件分岐を実行することはない; ジャンプのパターンは完全に予測可能である。従って、ソフトウェアは分岐予測ユニットを介した情報の漏洩によるサイドチャネル攻撃の影響を受けない。

小さな署名

署名は 64 バイトに収まる。これらの署名は実際には長い署名の圧縮バージョンである; 圧縮と展開の時間は前述のサイクル数に含まれている。

小さな鍵

公開鍵は 32 バイトのみを消費する。同様に圧縮と展開の時間が含まれている。

公のベンチマークのために我々のソフトウェアを eBATS プロジェクト [15] に提出し、再利用性を最大化するためにこのソフトウェアを public domain に配置した。上記で示した 87,548 と 273,364 の数値は Westmere CPU (Intel Xeon E5620, hydra2) 上での我々のソフトウェアの eBATS レポートからのものである。

我々の署名は楕円曲線署名であり、セキュリティを損なうことなく高い速度性能を実現するために設計と実装のレベルで慎重にエンジニアリングされている。セクション 2 は署名システムを特定する; セクション 3 は有限体演算に使用する手法について説明する; セクション 4 では高速署名について説明する; セクション 5 では高速検証について説明する。

過去の ECC 研究との比較

一般的な Intel CPU シングルコアでわずか 134,000 サイクルで高セキュリティの楕円曲線署名検証を達成することは前例のないことである。次のパラグラフでは過去の研究について説明する。

読者は ECC (elliptic-curve cryptography) のパフォーマンス結果を比較するときのいくつかの困難に注意する必要がある。第一に、高速 ECC に関するほとんどの論文は ECDH (可変基点単一スカラー乗算; variable-base-point single-scalar multiplication) に限定されており ECC 署名検証を実装していない。ただし例外は確かにある。例えば [21] は検証が ECDH より 1.33× 遅いことを報告しており、[34] は検証が ECDH より 1.36× 遅いことを報告している。第二に、ほとんどの実装は秘匿した配列インデックスと分岐予測を使用しており、従って [23] で成功した OpenSSL 攻撃で示されるようにサイドチャネル攻撃によって破ることができると想定する必要がある; これは公開鍵の署名検証の問題ではなく署名と ECDH の問題である。第三に、ほとんどの論文は少数の CPU での結果のみを報告しているため、同じ CPU にアクセスできない人たちはある CPU から別の CPU へのエラーが発生しやすい外挿を行う必要がある; これは eBATS ベンチマークに含まれているシステムの問題ではないが、eBATS に含まれていない最近の 2 つの ECC 実装 (後述) を認識している。

Intel の "Turbo Boost" と AMD の "Turbo Core" は新しい CPU にさらなる複雑さを加えた。典型的なベンチマークのフレームワークはシングル CPU コア上でのパフォーマンスを計測する。Turbo Boost はこれらのフレームワークの大部分を欺いて過度に低い Westmere サイクルカウントを報告する。その速度は気の利いたワークロードが全てのコアをビジー状態に保ったとしても CPU が実際には達成できない。eBATS の報告には Turbo Boost に関する明示的な警告が含まれている。この壊乱は hydra2 では発生しない: そのコンピュータでは Turbo Boost が無効になっている。

この論文より前で eBATS で最も近いシステムは ecdonaldp256、NIST P-256 楕円曲線を使用する ECDSA 署名だった。このシステムは hydra2 上で鍵生成に 1,690,936 サイクル、署名に 1,790936 サイクル、検証に 2,087,500 サイクルかかる。より良い速度が ECDH について報告されている:

• 3 位は Bernstein の Curve25519 の Gaudry と ThomEé [35] による curve25519 実装だった。
• 2 位は Curve25519 と同等のセキュリティ特性を持つエドワーズ曲線上の ECDH の Hisil [40] による gcfp256e 実装での 307,180 サイクルだった。
• 1 位は準同形性を持つエドワーズ曲線上の ECDH の Galbraith, Lin および Scott [34] による gls1271 実装での 278,256 サイクルだった。

最近の論文 [38] と [44] では、いくつかの ECC ベースのプロトコルにおける準同形性のセキュリティ問題を指摘しているが、これらのセキュリティ問題は ECDH 出力の標準ハッシュによる ECDH とは関係がなく、ECC 署名には関係が無いと言える。

[51] において Longa and Gebotys は、ecfp256e に類似した曲線上の ECDH に対して Core 2 Duo E6750 (C2 65nm) 上で 281,000 サイクル、gls1271 に類似した曲線上の ECDH に対して 229,000 サイクルを主張した。[51] のソフトウェアは eBATS ベンチマークには含まれておらず、見たところ公開されていないため、我々は Westmere でベンチマークすることができなかった。より最近の [46] の Käsper は Core 2 Duo E8400 (C2 45nm) の NIST P-224 曲線で side-channel-protected ECDH に対して 457,813 サイクルを報告している。このソフトウェアは OpenSSL に統合されているが eBAT にはまだ登録されていない。

比較を支援するために、我々の署名ソフトウェアと同じサイドチャネル保護 (秘匿配列インデックスなし、秘匿分岐条件なし) を備えた ECDH、特に curve25519 も実装した。我々はこの ECDH ソフトウェアを eBATS に提出し、ソフトウェアが可変起点の単一スカラー乗算に対して hydra2 で 226,872 サイクルを使用することを報告した。これはパブリックな ECDH ソフトウェアの速度新記録、サイドチャネル保護 ECDH (上記の論文のうちサイドチャネル保護について報告しているのは [12] と [46] のみ) の速度新記録、そして準同型のない ECDH に対する速度新記録である。

我々は curve25519 が eBATS 状で現在の位置を維持するとは主張していない: 多くのプラットフォームで準同型を持つ (特にサイドチャネル保護のない) ECDH が準同型を持たない ECDH よりも幾分速いと予想している。この期待は Hu, Longa, and Xu によるごく最近の論文 [42] により裏付けられているようである: [42, Table 2] は Intel Core 2 Duo E6750 上で準同型を持つ曲線に対して 194,000 サイクルを主張し、付随するウェブサイト [42, reference 18] は Intel Core i5 540M (Westmere) 上で 182,000 サイクルを主張している。ただし、[51] のソフトウェアと同様に [42] のソフトウェアも一般には公開されていないようである。その結果としての検証可能性の欠如は正確性に関して疑問を提起する。前述の Turbo Boost の問題を考慮すると Westmere の速度に関する主張は特に懐疑的である。この段落を書いた後に先のウェブサイトが更新され、別の Westmere CPU 上の同じソフトウェアに対して 250,000 サイクルを主張するように更新された。

我々の 225,872 サイクル ECDH 速度や、[21] と [34] で報告されている ECDH から検証までの速度低下、鍵と署名の圧縮解除にかかる追加のコストを考慮すると、検証速度は 400,000 サイクルに近いと予想される。我々はいくつかの理由でこれより良い結果を出しているが、最も重要な理由は我々がバッチ化を使用していることである。これには本稿で後述するように署名システムの慎重な設計を必要とする: ECDSA は DSA や他のほとんどの署名システムと同様に高速バッチ検証と互換性がない。

他の署名システムとの比較

eBATS ベンチマークは、様々なサイズの RSA、DSA、ECDSA、超楕円曲線署名、および多変数二次署名を含む 42 の異なる署名システムを対象としている。この論文は、それらほとんどすべての署名時間と検証時間 (および一部のアプリケーションで問題となる鍵生成時間) を 2 倍以上上回っている。唯一の例外は次の通り:

• 多変量二次署名は速度において競争力がある。例えば sflashv2 では署名に 124,740 サイクル、検証に 165,884 サイクルがかかり、mqqsig256 は署名に 4,212 サイクル、検証に 134,900 サイクルがかかる; より小さな mqqsig バージョンはさらに高速である。しかしながら sflashv2 は [30] で Dubois, Fouque, Shamir, and Stern によって破られている。昨年 [36] で導入された mqqsig のセキュリティ評価については認識していないが、mqqsig256 は 789,552 バイトの公開鍵を持っているという単純な理由から放置している。
• donald512 (512 ビット DSA) は検証に 334,508 サイクルがかかる。これは我々の単一署名の検証速度に匹敵するが、バッチ検証速度よりもはるかに低速である。これはまたはるかに低いセキュリティレベルであり、約 260 の簡単な操作で解読可能である。
• RSA タイプのシステムにはより高速な検証を提供するものもあるが、この利点はセキュリティレベルが高くなるに連れて減少し、多くのアプリケーションでははるかに遅い署名とはるかに大きな鍵がこの利点を上回る。例えば rwb0fz1024 (1024 ビット Rabin-Williams) は検証に 12,304 サイクルを使用するが、署名に 1,751,284 サイクルと公開鍵サイズに 128 バイトを使用する; ronald3072 (1024 ビット RSA) は検証に 60,300 サイクルを使用するが、署名に 2,171,124 サイクルと公開鍵サイズに 384 バイトという驚くべきサイクル数を使用する。この論文では (バッチ) 検証に 134,000 サイクル、署名に 87,548 サイクル、公開鍵サイズに 32 バイトを使用する。

RSA 検証は ECC 検証よりもはるかに高速であるため、それぞれの署名が何度も検証されるアプリケーションでは RSA 署名の方が ECC 署名よりもはるかに優れているというのが一般的な考え方である。我々の ECC 速度の結果はこの従来の通念に疑問を投げかけている。同じセキュリティレベルで RSA の検証速度に勝るものはないと主張しているわけではないが、[70] のような検証集約型のアプリケーションであっても ECC を魅力的なオプションとするのに十分な速度であると主張している。

2 署名システム

このセクションでは、本論文で使用する署名システムと、楕円曲線のほかの選択と共に使用できる一般化された署名システムである EdDSA を規定する。

ElGamal により [33] で導入された古典的な署名システムには様々な変種の文献が存在する; 注目すべき変種には Schnorr 署名システム [72]、DSA、および ECDSA があり、我々の一般化されたシステムはこれらの変種とは別のものである。我々が使用する個々の改変のいずれについても新規性を主張することはないが、改変の適切な組み合わせを選択することが重要であることを強調する。もっとも明らかな修正はワイエルシュトラス曲線 (Weierstrass curves) ではなく捻れエドワーズ曲線 (twisted Edwards curves) を使用していることである。これは名前として EdDSA (Edwards-curve Digital Signature Algorithm) を選択した理由である。

EdDSA パラメータ

EdDSA には次の 7 つのパラメータが存在する: 整数 \(b \ge 10\); \(2b\) ビットの出力を生成する暗号論的ハッシュ関数 \(H\); 4 を法とする 1 に一致する素数 \(q\); 有限体 \({\bf F}_q\) の元の \((b-1)\) ビットエンコーディング; \({\bf F}_q\) の非正方元 \(d\); いかに説明する追加の制約を満たす \(2^{b-4}\) から \(2^{b-3}\) の間の素数 \(\ell\); そして集合 \[ E = \{(x,y) \in {\bf F}_q \times {\bf F}_q: -x^2 + y^2 = 1 + dx^2y2\} \] の要素 \(B \neq (0,1)\) である。\(d\) が正方でないという条件は \(d \not\in \{0,-1\}\) であることを意味するため、この集合 \(E\) は [13] で Bernstein, Birkner, Joye, Lange, and Peters によって導入された捻れエドワーズ加算則 \[ (x_1,y_1) + (x_2,y_2) = \left( \frac{x_1 x_2 + x_2 y_1}{1 + dx_1 x_2 y_1 y_2}, \frac{y_1 y_2 + x_1 x_2}{1 - d x_1 x_2 y_1 y_2} \right) \] の下で単位元 \(0 = (0,1)\) を有する群を形成する。加算則の完全性 ─ 分母 \(1 \pm d x_1 x_2 y_1 y_2\) が非ゼロであるという事実 ─ は [13, Section 6] で説明されている: (\(q\) が 4 を法とする 1 に一致することから) -1 は \({\bf F}_q\) の正方であるため、この \(E\) の加算則は、エドワーズ曲線 \(x^2 + y^2 = 1 - d x^2 y^2\) のエドワーズ加算則と \({\bf F}_q\) 同型であり、\(-d\) は \({\bf F}_q\) の正方ではないため、[14, Theorem 3.3] によって完全となる。後者は \({\bf F}_q\) において \(d\) が非正方であり \(-1\) が正方であることに由来する。上記の追加の制約は \(\ell B = 0\) である。ここで \(nB\) はこの群での \(B\) の \(n\) 番目の倍数を意味する。

我々は \({\bf F}_p\) のエンコーディングを使用していくつかの体元を負として定義する: 具体的には \(x\) の \((b-1)\) ビットエンコーディングが辞書的に \(-x\) の \((b-1)\) ビットエンコーディングより大きい場合、\(x\) は負である。もし \(q\) が奇数素数でエンコーディングが \(\{0,1,\ldots,q-1\}\) のリトルエンディアン表現ならば、\({\bf F}_q\) の負の元は \(\{1,3,5,\ldots,q-2\}\) である。

元 \((x,y) \in E\) は \(b\) ビット列 \(\underline{(x,y)}\) としてエンコーディングされる。つまり、\(y\) の \((b-1)\) ビットエンコーディングの後に符号ビットが続く; 署名ビットは、もし \(x\) が負であれば 1 である。このエンコードは直ちに \(y\) を決定し、式 \(x = \pm \sqrt{(y^2-1)/(dy^2+1)}\) によって \(x\) を決定する。

EdDSA 鍵と署名

EdDSA 秘密鍵は \(b\) ビットの列 \(k\) である。ハッシュ \(H(k) = (h_0,h_1,\ldots,h_{2b-1})\) は整数 \[ a = 2^{b-2} + \sum_{3 \le i \le b-3} 2^i h_i \in \{ 2^{b-2}, 2^{b-2}+8,\ldots,2^{b-1}-8\} \] を決定し、これは \(A = aB\) を決定する。対応する EdDSA 公開鍵は \(\underline{A}\) である。ハッシュのビット \(h_b, \ldots,h_{2b-1}\) は次に説明するように署名の一部として使用される。

この秘密鍵 \(k\) の元でのメッセージ \(M\) の署名は以下のように定義される。\(r = H(h_b,\ldots,h_{2b-1}) \in \{0,1, \ldots,2^{2b}-1\}\) を定義する; ここでリトルエンディアンの \(2b\) ビット列を \(\{0,1,\ldots,2^{2b}-1\}\) の整数として解釈する。\(R = rB\) を定義する。\(S = (r + H(\underline{R},\underline{A},M) a) \bmod \ell\) を定義する。この時 \(k\) による \(M\) の署名は \(2b\) ビット列 \((\underline{R},\underline{S})\) である。ここで \(\underline{S}\) は \(S\) の \(b\) ビットリトルエンディアンエンコーディングである。\(\ell\) を \(b-3\) ビットに収めるためにデータを最後の隅々までパックしたいアプリケーションは、署名の最後の 3 ビットが常に 0 であることに注意する必要がある。

メッセージ \(M\) に対する疑わしい署名の検証は、公開鍵の下で次のように機能する。検証者はある \(A \in E\) に対して鍵を \(\underline{A}\) として解析し、またある \(R \in E\) と \(S \in \{0,1,\ldots,\ell-1\}\) に対して疑わしい署名を \((\underline{R},\underline{S})\) として解析する。検証者は \(H(\underline{R},\underline{A},M)\) を計算し、\(E\) の群方程式 \(8SB = 8R + 8H(\underline{R},\underline{A},M) A\) を確認する。検証者は解析が失敗したり群方程式が成り立たない場合、疑わしい署名を拒否する。

署名が検証に倒閣することを確認するには、\(B\) に式 \(S = (r + H(\underline{R},\underline{A},M)a) \bmod \ell\) を乗算し、\(\ell B = 0\) という事実を利用して \(SB = rB + H(\underline{R},\underline{A},M)aB = R + H(\underline{R}, \underline{A},M)A\) を確認する。検証者はこのより強力な方程式をチェックし、その方程式が成り立たない場合に疑わしい署名を拒否することができる。ただしこれは必須ではない; \(8SB = 8R + 8H(\underline{R},\underline{A},M)A\) が十分なセキュリティであることは確認している。

弱い鍵

\(A\) が \(B\) の既知の倍数であれば偽造は容易である。例えば \(A=37B\) と知っている攻撃者は \(r\) を選び \(S = (r + 37H(\underline{R},\underline{A},M)) \bmod \ell\) を計算することができる。さらに極端な例として \(A=0B\) と知っている攻撃者は \(r\) を選び \(M\) に関係なく \(S = r \bmod \ell\) を計算することができる。我々はこのような 2 つの "攻撃" によって \(0B\) と \(37B\) が "壊れ"、ユーザはこれらの "弱い鍵" をチェックし拒否する必要がある; しかし同様の混乱したロジックは全ての暗号システムの全ての鍵を拒否する必要があり、署名セキュリティの標準定義とは無関係である。

不正のないユーザは \(A=aB\) を選択し \(a\) はランダムなシークレットである; \(H(k)\) からの \(a\) の導出により適切なランダム性を保証することができる。これらのユーザは攻撃者が標的とする特定の \(B\) の倍数を生成できる可能性はほとんどない (特に \(0B\) を生成することはない)。攻撃者がランダムに \(a\) を推測する可能性は、攻撃者が既知の離散対数アルゴリズムによって \(a\) を計算する可能性よりもはるかに小さい。標準的な楕円曲線のセキュリティ基準は、後者のアルゴリズムが妥当な時間内に成功する可能性がほとんどないように設計されている。

展性

また "展性" (malleability) と署名セキュリティの標準的な定義との関連性も見られない。例えばシステムをわずかに変更した場合、\(S\) を \(-S\) に、\(A\) を \(-A\) に置き換えると ([75] の "攻撃" のわずかな変形)、新しい公開鍵の元で、ある有効な署名が同じメッセージの別の有効な署名に変換される; しかし攻撃者の目標、すなはちターゲット公開鍵の下で新しいメッセージに署名を偽造することはいまだに達成できない。そのような変更の一つは、ハッシュから \(\underline{A}\) を省略することである; もう一つの同様な変更は \(A\) ではなく \(|A|\) だけをエンコードする \(\underline{A}\) を持つことである。

曲線の選択

EdDSA に推奨される曲線は [12] の Curve25519 曲線と双有理的に等価な捻れエドワーズ曲線である。効率的に計算可能ないかなる双有理等価性 (birational equivalence) も ECDLP の困難性を維持するため、Curve25519 に対する ECDLP の周知の計算困難性は直ちにこの曲線の ECDLP の計算困難性を暗示する。この曲線の選択では EdDSA に対して Ed25519 という名前を使用する。

特に Ed25519-SHA-512 は次のパラメータを持つ EdDSA である: \(b=256\); \(H\) は SHA-512; \(q\) は素数 \(2^{255}-19\); \({\bf F}_{2^{255}-19}\) の 255 ビットエンコーディングは通常のリトルエンディアン符号化であり \(\{0,1,\ldots, 2^{255}-20\}\); \(\ell\) は [12] より素数 \(2^{252}+27742317777372353535851937790883648493\); \(d = −121665 / 121666 \in {\bf F}_q\); そして \(B\) は \(x\) が正である一意の点 \((x,4/5) \in E\) である。

[12] の Curve25519 は同じ体 \({\bf F}_q\) 上のモンゴメリ曲線 (Montgomery curve) \(v^2 = u^3 + 486662u^2 + u\) である。Bernstein と Lange は [14, Section 2] の中で、Curve25519 はエドワーズ曲線、特に \(x^2 + y^2 = 1 + (121665 / 121666) x^2 y^2\) と双有理的に等価であると指摘している; 等価性は \(x = sqrt{486664}u / v\) と \(y = (u-1)/(u+1)\) である。上記のように -1 は \({bf F}_q\) の平方であるため、このエドワーズ曲線は \(-x^2 + y^2 = 1 - (121665/121666)x^2 y^2\) と同形である。ここでの基点 \(B\) の選択は [12] での \(u=9\) の選択に相当する。

\(r\) の擬似ランダム生成

ECDSA は他の多くの署名システムと同様に、単にランダムな長期秘密鍵を生成するだけではなく、署名されるメッセージごとに新しいランダムな秘密セッション鍵 \(r\) も生成するようにユーザに要求する。\(r\) が公開された場合、\(H(\underline{R},\underline{A},M) \bmod \ell \neq 0\) と仮定すると、長期秘密鍵 \(a\) は単純に \(a = (S - r) / H(\underline{R},\underline{A},M) \bmod \ell\) として計算できる。ElGamal が [33, Note 2] で述べたように、もし同じ値 \(r\) が 2 つの異なるメッセージで使われるなら秘密鍵も計算することができる。後者のケースは PlayStation 3 のコード署名に関する Sony の ECDSA 実装で発生した障害であり、ただちに Sony の長期秘密鍵が明らかになったことが [24] で報告されている。

さらに、たとえセッション鍵が公開または再利用されなかったとしても、ECDSA のセッション鍵はランダム性からわずかに逸脱する長期鍵よりもはるかに耐性が低いことが良く知られている。例えば Nguyen と Shparlinski は [61] で格子法を使って数百の署名のわずか 3 ビット程度の \(r\) の知識から長期 ECDSA 鍵を計算するアルゴリズムを示した。この知識がサイドチャネル攻撃から得られたものか、それとも \(r\) が取得される分布の不均一さから得られたものかは無関係である。

EdDSA では \(r = H(h_b,\ldots,h_{2b-1},M)\) を生成することでこれらの問題を回避する。これによりメッセージが異なると予測困難な \(r\) の値を導く。メッセージごとのランダム性は消費されない。ランダムな署名を秘密裏に決定論的な方法で生成し、特に長期秘密鍵を入力メッセージとともにハッシュ化することで疑似ランダム性を得るというこのアイディアは、[9] でBarwood により; 独立して [79] で Wegley により; 数か月後に特許出願 [57] で Naccache, M'Raïhi, and Levy-dit-Vehel により; その後 [55] で M'Raïhi, Naccache, Pointcheval, and Vaudenay により; そしてさらに後に [47] で Katz and Wang により提案された。この特許出願は 2003 年に放棄された。

標準的な PRF 仮説は、この疑似ランダムセッション鍵 \(r\) は各 \(M\) ごとに独立して生成された真の乱数列と区別ができないため、セキュリティの損失がないことを意味する。良く知られている伸長特性 (length-extension properties) は secret-prefix SHA-512 が PRF であることを妨げるが、\(r\) が攻撃者からは見えないため、Ed25519-SHA-512 のセキュリティを脅かすことをはない。残りのすべての SHA3 候補は明示的に PRF として設計されており、SHA-3 が標準化された後に Ed25519-SHA-3 を推奨することは躊躇しない。もちろん、AES のような暗号と、長い入力をサポートする標準的な PRF ストレッチングメカニズムを組み合わせて \(r\) を生成することも安全である; ただしハードウェア実装で領域を節約するために \(H\) を再利用したいと考えている。

区間 \([0, 2^{2b}-1]\) からの EdDSA サンプル \(r\) により、\(\ell\) を法とする分布がほぼ均一であることが保証される。ガイドライン [2, Section 4.1.1, Algorithm 2] では、区間が少なくとも \([0, 2^{b+61}-1]\)、すなはち \(\ell\) より 64 ビット大きいサイズであることが規定されている; Ed25519 の場合は 259 ビットが追加される。

過去の ElGamal 変種との比較

オリジナルの ElGamal システム [33, Section III] は楕円曲線暗号よりも前のものであり、代わりに乗算群 \({\bf F}^*_q\) を使用している。ElGamal は大きな非素数 \(\ell\)、特に \(\ell = q-1\) を取り、素数 \(q\) の場合に焦点を当てた。ElGamal の署名は \({\bf F}^*_q\) で \(B^{H(M)} = A^R R^S\) を満たす \(0\) から \(q-2\) までの整数ペア \((R,S)\) である。[33, question (3)] 参照。また \(H\) の導入については [33, Attack 6] 参照。\(M\) が与えられた署名者は \(\ell\) に対して互いに素な乱数 \(r\) を生成し \((R,S)\) を計算する。ここで \(R=B^r\)、\(S=r^{-1}(H(M)-Ra) \bmod \ell\) である。

Schnorr は [72] で位数 \(\ell\) の部分群 \({\bf F}^*_q\) では \(q\) より遙かに小さい素数 \(\ell\) でも問題なく動作でき、\(S\) に対してより多くの空間を節約できることを指摘している。また Schnoor は ElGamal システムに以下で説明するような他のいくつかの改善を導入した。

ElGamal の検証式は群 \({\bf F}^*_q\) の元として \(R\) とスカラーとして \(A\) の指数が含まれている。より一般的な群では群の元をスカラー値にマッピングする関数 \(x\) が必要である。ECDSA は次のように機能する: \({\bf F}^*_q\) を \({\bf F}_q\) 上の楕円曲線の位数 \(\ell\) の部分群に置き換え、\(x(R)\) を \(R\) の x 座標として定義する。また ECDSA は \(A\) を \(-A\) に置き換え、署名の減算を加算に変更し、検証式 \(H(M) B + x(R) A = SR\) を得ている。ECDSA は、\(S\) が \(\ell\) を法とする可逆式とする対価を払って、この 3 スカラー方程式を等価な 2 スカラー方程式 \(S^{-1}H(M)B + S^{-1}x(R)A=R\) に置き換える; 署名者と検証者の両方がここで逆を計算することに注意。

Schnorr は \(x\) に暗号論的ハッシュ関数を使用した。これによりコストを最小化し、それと比較して単純な関数 \(x\) の数学的構造に関するあらゆる懸念を排除している。Schnorr はまた群の元 \(R\) をスカラー \(x(R)\) に圧縮した: Schnorr 署名は \((R,S)\) ではなく \(x(R),S)\) である。圧縮された署名 \((x(R),S)\) が与えられると、検証者は \(R\) を \(S^{-1}H(M)B+S^{-1}x(R)A\) を計算し、\(x(R)\) が一致しているかを確認する; この時点で検証者は有効な非圧縮署名 \((R,S)\) を知っているため、圧縮によってセキュリティが低下することはない。

Schnoor はまた \(R\) のハッシュと \(M\) のハッシュをマージした。このマージを理解する一つの方法は、\(S\) を \(x(R)S\) に置き換えて追加の制約 \(x(R) \neq 0\) を課して検証式 \(x(R)^{-1}H(M)B+A=SR\) を得ることである。ここで \(x(R)S^{-1}H(M)\) の乗法構造を知る必要はない。代わりに署名者は \(S\) を \(r^{-1}(H(\underline{R},M)+a) \bmod \ell\) として得るために検証式 \(H(\underline{R},M)B+A=SR\) を使用することができる。Schnorr は実際に式 \(SB=R+H(\underline{R},M)A\) を使用し、署名者と検証者の両方の逆位を排除した。これは明らかな利点であり処理時間とコードサイズの縮小に繋がる。

ハッシュ関数への入力として \(R\) が存在することは衝突耐性を提供する。攻撃者は単にハッシュの衝突を発見するだけでは Schnorr のシステムを破ることはできない。[60] の Noven, Smart, and Warinschi は衝突耐性を利用して \(b/2\) ビットのみを出力するような \(H\) を選択し、圧縮された署名のサイズを 25% 削減することを提案した。しかし同じ提案が実際には 20 年前に同じ提案が Schnorr の原著論文 [72, Section 2] に掲載されていた。

Schnorr システムの実用化は特許 (2008年に失効) によって妨げられていたが、\(R\) のハッシュ化により様々なセキュリティ証明が可能になったため、このシステムは広く理論家に知られることになった。いくつかの証明では "分岐補題" (forking lemma を使用して Schnoor システムに対する一般的なハッシュ攻撃 (すなはち任意の関数 \(H\) に対して作用する攻撃) が多項式で制限された DLP アルゴリズムに変換できることを示しているが、多くの場合は非常に重大な効率低下を伴う。\(H\) に関する緩やかな仮定の下で、一般的な群の攻撃 (generic-group attack) (すなはち任意の群に対して作用する攻撃) に対する効率低下が異なる定理と、一般的な群の一般ハッシュ攻撃 (generic-group generic-hash attack) に対して効率が低下しない定理も存在する。例えば [67], [74], [11], [60] を参照。"証明可能なセキュリティ" の現実世界における妥当性を誇張するつもりはないが、Schnorr のシステムが保守的でよく研究された署名システムであることは明かである。

我々の検証式はハーフサイズのハッシュの代わりにダブルサイズのハッシュを使用し、また \(\underline{A}\) をハッシュの追加入力とし、そして \(R\) の Schnorr 圧縮を行わない Schnorr 検証式と同じである。これらの変更は明らかにセキュリティを損なうものではない。ダブルサイズのハッシュ値の使用はハッシュ関数のセキュリティに関する懸念を軽減するのに役立つ。\(\underline{A}\) の使用は一部の公開鍵が同時に攻撃される可能性があるという懸念を軽減する安価な方法である。またセクション 5 で説明するように圧縮を回避することで検証速度の大幅な高速化が可能となる。またダブルサイズのハッシュ値を再利用して前述のような nonce ランダム性に関する懸念を軽減する。

3 モジュロ \(2^{255}-19\) の高速計算

このセクションではソフトウェアが体 \({\bf F}_{2^{255}-19}\) の元をどのように表すか、およびソフトウェアが体に対して効率的な演算を実行する方法について説明する。ソフトウェアで使用される機械命令は全て 64 ビット Intel および AMD CPU で使用できるが我々は Intel の Nehalem/Westmere CPU を対象としている。

Nehalem CPU での乗算

体の乗算 (および二乗) はほとんどの CPU での楕円曲線パフォーマンスの主要なボトルネックである。高速な体乗算の最も重要なツールは高速 CPU 乗算命令である。Nehalem CPU は高速な体演算に使用できる 3 つの乗算命令を提供している:

• mulpd 命令はサイクルごとに SIMD 方式で 2 つの倍精度浮動小数点乗算を実行できる。より新しい Sandy Bridge CPU はサイクルごとに最大 4 つの倍青銅浮動小数点乗算を実行できる vmulpd が含まれているが、この命令は対象の CPU では使用できない。
• mul 命令は 2 サイクルごとに 2 つの 64 ビット符号なし整数を乗算して 128 ビットの結果を生成できる。
• pmuldq/pmuludq 命令は 32 ビット整数の 2 つの乗算を実行し、サイクル事に 64 ビットの結果を生成できる。pmuldq 命令は符号付き乗算を実行し、pmuludq 命令は符号なし乗算を実行する。

乗算とエドワーズ曲線演算には mulpd と pmuldq で活用できるデータレベル並列化が含まれているが、このアプローチでは、例えば [28] や [59] で説明されているようにレジスタにデータを配置するのに必要なシャッフル命令のオーバーヘッドが発生する。いくつかの独立した計算が並列して実行される場合、このオーバーヘッドは解消されるが、基本的に各サイクルごとの 2 つの 64 ビット結果が 2 サイクルごとの 1 つの 128 ビット結果よりも優れているわけではない。従って体の乗算を 64 ビット符号なし整数の乗算に分解する。

Radix-\(2^{64}\) 表現

255 ビット値を 64 ビットのリム (limb) に分割する標準的な方法は 4 リムの radix-\(2^{64}\) 表現である。体のそれぞれの元 \(x\) は \(x=\sum_{i=0}^3 x_i 2^{64i}\) となる \((x_0,x_1,x_2,x_3)\) として表される。2 つの元 \(x\) と \(y\) の乗算は 64 ビット符号なし整数の 16 乗に分解される; 128 ビットの結果が加算され 8 リム \(r_0,\ldots,r_7\) の結果が生成される。\(2^{255}-19\) を法とする削減で \(2^{256} \equiv 38\) であるため、\(r_0\) には \(38 \cdot r_4\) が加算され、\(r_1\) には \(38 \cdot r_5\) が加算されるという事実を利用したものである。

この表現の注目に値する詳細は 256 ビットを使用して 255 ビットの体の元を表すことである。我々はこの一つの余分なビットを使い、常に \(2^{255}-19\) を減らすのではなく、\(2^{256}-38\) を減らす。同様の表現については例えば [17] で有用であることが示されている。

この体の元の表現に基づく署名方法の実装により AMD K10 や 65nm Intel Core 2 プロセッサのような多くのマイクロプロセッサで高いパフォーマンスを得られる。ただしターゲットプラットフォームである Intel Nehalem/Westmere CPU ではこの表現が深刻なボトルネックを引き起こす。mul 命令の各 128 ビットの結果は 2 つの 64 ビットレジスタに生成される。これらの 2 つの結果を加算するには 2 つの追加の命令が必要である。体の乗算では、これらの加算のほとんどが繰り上げ (carry) を生成する; このキャリービットは後の加算で処理する必要がある。Intel Nehalem と Westmere CPU はサイクルごとに 3 つの加算を行うことができるが、これは直前の加算 (add 命令) からのキャリービットを処理しなくてもよい場合に限る。キャリー付きの加算 (adc 命令) は 2 サイクルに 1 度しか実行できない; つまりキャリービットの発生は加算のスループットを 6 倍減衰させる。このボトルネックは体の乗算と平方だけではなく加算の内部でも発生する。

Radix-\(2^{51}\) 表現

高価な adc/subc 命令の数を減らすため、代わりに \({\bf F}_{2^{255}-19}\) の元 \(x\) を \(x = \sum_{i=0}^4 x_i 2^{51i}\) となるような \((x_0,x_1,x_2,x_3,x_4)\) として表す。

この 5 つのリムは符号なし整数である。我々は各 \(x_i \in [0,\ldots,2^{51}-1]\) で体 \({\bf F}_{2^{255}-19}\) のそれぞれの元を表すことができる。実際、我々の実装では比較を除いてこれらの境界を強制していない。乗算は各リムが最大 54 ビットの入力を受け入れ、各リムが \(2^{51}\) よりわずかに大きいだけの結果を生成する。

乗算と平方演算

それぞれが 5 つの符号なし整数で表される 2 つの元 \(x\) と \(y\) の教科書的な乗算は 25 mul インタラクションを取る。結果は再び 2 つの 64 ビット整数レジスタに生成されるが、両方の入力は最大 54 ビットしか持たないため、上位の結果レジスタの値は最大 44 ビットしか持っていない。ここで 2 つの乗算結果を加算するには 1 つの adc 命令と 1 つの adds 命令のみが必要である。さらに乗算と同時に減算を実行することができる。例えば我々は係数 \(r_5\) を計算しない。mul 命令の結果が \(r_5\) に属する場合、たとえば \(x_2 \cdot y_3\) の乗算では、入力のいずれかに 19 を乗算し、その結果を \(r_0\) に加算する。同様に、\(r_6,r_7,r_8,r_9\) は計算しないが、直接 \(r_1,\ldots,r_4\) に加算する。1 つの入力に 19 を掛けると 64 ビット未満の結果が得られるため、これらの乗算にはより高速な imul 命令を使用することができる。5 つの結果の係数は 10 個の 64 ビットレジスタを必要とするが AMD64 アーキテクチャにはこのようなレジスタが 15 個あるため、計算を通して結果の係数をレジスタ内に保持できる。

乗算後、最大でも \(2^{51}\) よりわずかに大きい係数の結果を得るために、我々は 5 つの係数を削減 (繰り上げ) する必要がある。同様に、係数 \(r_1\) を保持するレジスタを \(r_0 = 2^{64} r_{01} + r_{00}\) となるような \(r_{00}\) および \(r_{01}\) として表記する。最初に \(r_{00}\) を左に 13 ビットシフトし、\(r_{00}\) の最上位ビットをシフト (shld 命令) してから \(r_{00}\) を \(2^{51}-1\) で論理積を計算する。同じ操作を \(r_{10}\) と \(r_{11}\) で行い、\(2^{51}-1\) の論理積計算の後で \(r_{01}\) を \(r_{10}\) に加算する。我々は係数 \(r_2,\ldots,r_4\) に対してこの方法で進める; レジスタ \(r_{41}\) は \(r_{00}\) に加算する前に 19 倍される。これで 5 つの係数全てが 64 ビットレジスタに収まるが、それでも別の乗算への入力として使用するには大きすぎる。従って \(r_0\) から \(r_1\) へ、\(r_1\) から \(r_2\) へ、\(r_2\) から \(r_3\) へ、\(r_3\) から \(r_4\) へ、最後に \(r_4\) から \(r_0\) へ繰り上げする。これらそれぞれの繰り上げは 1 つのコピー、51 による一つの右シフト、\(2^{51}-1\) による一つの論理積演算と一つの加算で行われる。

平方演算に必要なのは 51 mul 命令だけである。一部の入力は 2 が掛けられ、これは可能であれば 19 で乗算する。二乗した後の係数の削減は乗算の場合と同じである。

乗算と平方は別々の関数として実装されているが、これらの関数の呼び出しは反転 (下記参照) にのみ使用される。エドワーズ曲線演算は点の加算と倍積にインライン関数を使用する。

加算、減算および反転

加算の結果を乗算の入力として使用する場合は、加算の結果を減らす必要はない。係数が 64 ビットより大きくなるような長い加算のシーケンスは問題となるが、我々はそのような加算のシーケンスを持っていない。従って体の加算は繰り上げなしの 5 つの整数加算 (add 命令) に過ぎない。符号なし係数を使用するため減算は若干高価である。したがってまず \(q\) の倍数を加算してから減算を実行する。これには 5 つの追加命令と 5 つのサブ命令が必要である。

反転は指数 \(q-2\) の累乗として実装される。[12] と同じ 255 の二乗と 11 の乗算シーケンスを使用する。

4 メッセージ署名

署名の生成には 3 つのステップがある: (1) \(r=H(h_b,\ldots,h_{2b-1},M)\) を計算する; (2) \(R = rB\) を計算する; (3) \(S = (r + H(\underline{R},\underline{A},M)a) \bmod \ell\) を計算する。

我々の主な関心事は短いメッセージ \(M\) であり、これは所定のボリュームのデータに食い下がるサーバにとっての最大の関心事である; 長いメッセージは署名ごとに多くのサイクルを必要とするが、バイト単位のサイクルは遙かに少なくなる。\(H\) の計算は短いメッセージに対しては無視できる時間である。\(\ell\) を法とする削減も標準ブランチレス技法 (standard branchless techniques) では無視できる時間を要する。このセクションの残りの部分では、主な署名のボトルネック、つまり \(r\) が与えられた \(rB\) の計算に焦点を当てる。

高いレベルの戦略

我々はまず 253 ビット整数 \(r \bmod \ell\) の計算から始める。次に \(r \bmod \ell\) を \[ r_i \in \{-8, -7, -6, -5, -4, -3, -2, -1, 0, 1,2,3,4,5,6,7\} \] となるような \(r_0 + 16r_1 + \ldots + 16^{63} r_{63}\) で記述する。各 \(i\) について、事前に計算された表で \(16^i |r_i|\) B\) を計算し、条件付きで \(16^i |r_i| B\) を反転して \(16^i r_i B\) を得る。最後に \(\sum_i 16^i r_i B\) として \(rB\) を計算する。

このレベルの計算には新しいものはない。事前計算された断片の合計として \(rB\) を計算することは [64] で Pippinger によって公開された標準スカラー乗算アルゴリズムの特殊なケースである (その後 [50] と [19] で再発明された)。負の係数を許可することは標準的な調整である。問題は下位レベルの詳細にあり、最適な基数 16 を選択し、\(16^i r_i B\) および \(\sum_i 16^i r_i B\) を可能な限り効率敵に計算する。これらの詳細については以下で説明する。

低レベル, パート1: 表検索

サイドチャネルの防衛策として秘匿の配列インデックスを禁止していることを述べた。特に配列インデックスとして \(|r_i|\) を使用することはできない。代わりに全てのテーブルエントリ \(0B\), \(16^iB\), \(2\cdot 16^8B\), \(3\cdot 16^iB\), \(4\cdot 16^iB\), \(5\cdot 16^iB\), \(6\cdot 16^iB\), \(7\cdot 16^iB\), \(8\cdot 16^iB\) をロードし分岐なしで算術演算を使用してテーブルエントリを \(16^i |r_i| B\) に結合する。同様に算術演算を使用して \(16^i |r_i| B\) と \(-16^i |r_i| B\) から \(16^i r_i B\) を計算する。

我々は実際には 4 回の楕円曲線の重複を犠牲にして \(i \in \{0,2,4,\ldots,62\}\) に対してのみテーブルエントリを格納する。この場合、テーブルには曲線上の (保存されていない \(0B\) 以外の) \(8 \cdot 32 = 256\) 個の点が含まれる。それぞれの点は \(2^{255}-19\) を法とする 3 つの整数 (下記参照) として表され、各整数は 5 つの 8 バイトワードとして表される。テーブル全体では 30kB の RAM を消費する。

代わりに 32 以上の基数を使用することもできる。基数 32 ではテーブルエントリを全て読み込むため、テーブルのロード数が倍になり、テーブルエントリを結合するために倍の算術演算を必要とするが、楕円曲線の追加が少ないという利点がこれらのコストを上回る。より深刻な懸念はテーブルのサイズが倍となり 30kB ではなく 60kB を消費することである。これはターゲットの CPU においての一般的な暗号化速度テストでは些細な問題に過ぎないが (Nehalem/Westmere 各コアにはシーケンシャルロードを効率的に処理する独自の高速 256kB L2 キャッシュが存在する)、複数の異なるサブルーチンを L2 キャッシュに組み込む必要がある大規模なアプリケーションでは明らかに 30kB の方が適している。

反対に、さらに 8 回の倍積を犠牲にしてテーブルを半分に刻むことができる。また基数 8, 4 または 2 に切り替えることもできる。これらの変更により遙かに小さい CPU でもかなり高速な署名が可能になる。

低レベル, パート2: 楕円曲線加算

Hisil, Wong, Carter, and Dawson が [41] で提案しているように捻れエドワーズ曲線 \(-x^2 + y^2 = 1 + dx^2y^2\) の拡張座標を使用する。これらの座標は \(x = X/Y\) と \(y = Y/Z\) を表す \(XY = ZT\) による \((X:Y:Z:T)\) である。[41, Section 3.1] の加算式はこの曲線に対して完全であり 9 フィールドの乗算のみを使用してテーブルエントリ \((x_0,y_0)\) を \((X:Y:Z:T)\) に追加する。これらの数式は \(-x^2\) の \(-1\) に依存していることに注意。これが EdDSA が \(-1\) 捻れを使用する理由である。

体の乗算の一つは \(d=-121665/121666\) による乗算である。これを [13, Section 6] のように 121665 と 121666 の少ない数の乗算に置き換えることができるが、現在の我々のソフトウェアはコードサイズを節約するために \(d\) を汎用的な体の元として扱う。我々は小さな整数 \(d\) を使用して新しい曲線に切り替えることを検討したが (素数に近い群位数を持った 646 など; Curve25519 の捻れセキュリティは必要ないことに注意)、結果として得られた高速化は既存の曲線からの逸脱を正当化するには小さすぎると判断した。

乗算を保存する別の方法は [41, Section 3.2] の二重加算式を保存することである。ただしこれらの数式は完全ではない。計算の中間結果を詳細に分析し、中間的な加算が数式の例外的なケースを引き起こすかを調べる必要がある。

代わりに、事前に計算された点 \((x_0,y_0)\) を \((y_0-x_0, y_0+x_0, 2dx_0y_0)\) として表す。これらの値は \(x_0\) と \(y_0\) のみに依存し、通常は拡張座標の加算の最初の部分で計算される。それらを事前計算の一部として提供すると、ストレージ要件が 1.5 倍になる対価に \(d\) による乗算、乗算 \(x_0 y_0\) および 2 フィールドの加算が節約される。

テンプレート攻撃

ハードウェア実装では、このタイプの事前計算が同じ事前計算された点の複数の利用を関連づけようとするテンプレート攻撃にさらされる情報を低減させることに言及しておく。

例えば、メモリが非常に限られているデバイスの消費電力を攻撃者が監視していると仮定する。デバイス設計者は、多くの倍増を犠牲にして前述のテーブルを単純に \(B, 2B, \ldots, 8B\) と縮小し、テーブル項目を単に \((x_0,y_0)\) として格納することでより多くのメモリを節約したと仮定する。このとき加算式は \(y_0-x_0\), \(y_0+x_0\), etc. を計算することによって開始する。もし後に同じテーブルエントリが再度使用されると、全く同じ減算、加算、etc. が再び実行され、全く同じ電力トレースが得られる。従って、攻撃者はロードされた点を (多くても) 16 の異なるグループに分割し、[31, Section 5.1.2] で論議されているように平均で 55 ビットの情報を取得することができる。

\(y_0-x_0\), \(y_0+x_0\) などを事前計算することにより、(これらの加算式に対して) 事前に計算された点を含む全ての演算が、同じテーブルエントリを使用するたびに予測できないほど変化する中間の点も含むことが保証される。フィールド演算をよく見ると Karatsuba 法の予備的な追加など、1 つの入力だけに依存する低レベルの演算が明らかになることがある。これらの捜査の結果も同様に事前計算される。

もちろん、ハードウェアのサイドチャネル攻撃への対策についてはさらに多くのことを述べる必要がある。単独の対策で十分であるとは主張していない。ソフトウェアの状況は、攻撃者にさらされるサイドチャネルが遙かに限られているためより単純である。

結果

全体としてメインの署名ループの各反復、つまり 1 つのテーブル検索と 1 つの楕円曲線混合加算に 1,000 サイクル未満を費やしている。また計算の最後に約 21,000 サイクルを費やして \(Z\) を反転する。ショートメッセージの完全な署名手順には 87,548 サイクルがかかる。

5 署名の検証

高速署名検証は 2 つの理由から高速署名生成よりもかなり厳しいように思われる。第一に、検証者は圧縮された点 \(\underline{A}\) と \(\underline{R}\) から楕円曲線上の点 \(A\) と \(R\) に戻す必要がある。第二に、\(SB=R+H(\underline{R},\underline{A},M)A\) を確認することは、固定ベースのスカラー乗算 \(SB\) だけではなく、より高価な変数ベースのスカラー乗算 \(H(\underline{R},\underline{A},M)A\) も必要だろう。このセクションではこれらの問題に対処するためのいくつかの手法について説明する。

高速復元

点 \(R=(x,y)\) を符号化した \(\underline{R}\) は \(y\) の直接的なエンコーディングを含むが、\(x\) の符号ビットのみが含まれていることを述べた。従って式 \(s = \pm \sqrt{(y^2-1)/(dy^2+1)}\) を用いて \(x\) を復元する必要がある。\(-d\) が平方ではないため \(dy^2 + 1 \neq 0\) であることに注意。ここでの除算と平方根には 2 つのべき乗が関係しているようで、通常のワイエルシュトラス曲線の復元の約 2 倍のコストである。

もちろんモンゴメリのトリック (Montgomery's trick) を使って 2 点の復元に関係する 2 つの除算をマージすることもできるが、2 つの平方根と除算は依然として 2 つのワイエルシュトラス曲線の復元よりも高価だえる。64 バイトの鍵と 96 バイトの署名を扱うことをいとわないアプリケーションでは圧縮と復元をスキップすることもできるが、我々は 32 バイトの鍵と 64 バイトの署名の法が遙かに魅力的だと考えている。

時間節約のために \({\bf F}_q\) における平方根の標準計算をより詳しく調べる。素数 \(q=2^{255}-19\) は 8 を法とする 5 に一致するため任意の平方 \(\alpha \in {\bf F}_q\) は \(\alpha^2=\beta^4\) を満たす。ここで \(\beta=\alpha^{(q+3)/8}\)、つまり \(\pm \alpha = \beta^2\) である。標準的な計算は \(\beta\) を計算するための単一の指数関数であり、\(\beta^2=-\alpha\) の場合 \(\beta\) を \(\sqrt{-1}\) で迅速に乗算する。

復元のコンテキストでは与えられた \(\alpha\) を分数 \(u/v\) として考える。ここで \(u=y^2-1\) と \(v=dy^2+1\) である。\(\alpha\) を計算する代わりに除算を平方根演算とマージする: \[ \beta = (u/v)^{(q+3)/8} = u^{(q+3)/8} v^{q-1-(q+3)/8} = u^{(q+3)/8} v^{(7q-11)/8} = uv^3 (uv^7)^{(q-5)/8} \] 我々は \(v\beta^2=-u\) を確認することで \(\beta^2=-\alpha\) かどうかをチェックし、そうであれば \(\beta\) を \(\sqrt{-1}\) で乗算する。\(u\) と \(v\) で始まる \(\sqrt{u/v}\) の計算全体は単一のべき乗よりも数回の乗算だけで済む。言い換えるとエドワーズ曲線の復元はワイエルシュトラス曲線の復元と同程度に低コストである。

高速単一署名検証

我々は単一の署名を検証するために倍積スカラー乗算の標準的な手法を使用して \(SB-H(\underline{R},\underline{A},M)A\) を計算し、その結果が \(R\) と同じかをチェックする (結果のエンコードが \(R\) のエンコードと同じかを実際にチェックして \(R\) の復元をスキップできるようにする)。エドワーズ曲線の加算速度、特に \(-1\) 捻れにおいてこれらの手法は特に効率的であり、セクション 4 で説明した表を使用しても何の利点もないように思われる。この計算は非常に小さなスペースに収まる。

我々は Antipa, Brown, Callant, Lambert, Struik, and Vanstone が [7] で提案した方法についても検討したが、我々は非常に効率的な楕円曲線演算を行うため、この方法では余計な圧縮復元とユークリッド計算のオーバーヘッドが発生し非常な手間となる。以下で論じるバッチ処理のコンテキストでは [7] の方法の唯一のオーバーヘッドはユークリッド計算となるだろうが、メリットも遙かに小さくなるだろう。

高速バッチ検証

署名検証がボトルネックとなっているシステムでは、問題は一度に一つの署名を検証することではなく、多数の署名を可能な限り早く検証することである。

Naccache, M'Raïhi, Vaudenary, and Raphaeli は [58, Section 2.2] で方程式のランダムな線形結合を検証することにより線形署名方程式をバッチ検証することを提案した。この手案は ElGamal, DSA, Schnorr ECDSA 等には直接適用できない。これらのシステムは全て、線形関数を単純に検証するだけではなく、(\(R\) を計算するために) 線形関数を計算する必要があるからである。しかし [58] で提案されているように \(H(\cdots)\) の代わりに \(R\) が送信されている場合、この問題は解消される。

残念ながら [58] における検証アルゴリズムは非常に遅く、[58, Table 1] は非常に疑わしい \(2^{20}\) セキュリティレベルで同じ署名者からの \(n\) 個の署名を検証する "\(29n\)" 乗算を報告した。同じ技術を ECDSA に適用しセキュリティレベルを \(2^{128}\) に上げると、同じ署名者からの署名に対して 200 近くの楕円曲線の追加が必要となる。これは各署名を個別に検証するより若干高速だがそれほど多くはない。

Bellare, Garay, and Rabin によるフォローアップ論文 [10] は、例えば 100 のべき乗を検証するために 3,200 の乗算、または 100 DSA 署名を検証するために 6,480 の乗算 (双方のケースで標準以下の \(2^{60}\) セキュリティレベル) を使用するより複雑な検証方法を提案した。[10, Appendix A.1] 参照。署名ごとの乗算の数はバッチサイズが 1,000 に近づくにつれて低下し始める ([10, Figure 3] 参照) が、このような大量のバッチは一般的な CPU のキャッシュには収まらない。

これらのバッチ検証技術の印象的ではない理論的性能は [58] と [10] で使用されている単純なべき乗アルゴリズムに直接由来している。[58] のようなランダムな線形の組み合わせと、最先端のスカラー倍積法を併用することで遙かに優れた結果が得られる。

具体的には \((M_i,A_i,R_i,S_i)\) のバッチから開始する。ここで \((\underline{R_i},\underline{S_i})\) は鍵 \(\underline{A_i}\) の元で申し立てられた \(M_i\) の署名である。独立した一様乱数の 128 ビット整数 \(z_i\) を選択し、\(H_i = H(\underline{R_i},\underline{A_i},M_i)\) を計算し、マルチスカラー倍積法により方程式 \[ \left( - \sum_i z_i S_i \bmod \ell \right) B + \sum_i z_i R_i + \sum_i (z_i H_i \bmod \ell) A_i = 0 \] を検証する。スカラー倍積法には [64] の Pippenger 法と [27, Section 4] で報告されている Bos-Coster 法がある。我々はより少ないストレージに納めるために Bos-Coster 法を使用する。詳細は下記参照。\(z_i\) は秘密ではないのでサイドチャネルの保護は必要ないことに注意。

ここでのスカラー数は \(2n+1\) である。スカラー値の半分は 253 ビットで、残りの半分は 128 ビットである。公開鍵が繰り返し現れる場合、[58] と [10] で考慮されている状況では、253 ビットのスカラー値をマージすることで時間を節約できる。このマージは 128 ビットスカラー値のマージだけを可能にする同様の署名式 \(SB = A + H(\underline{R},\underline{A},M)R\) を使わない理由も説明している。我々のソフトウェアは任意の鍵を使用した汎用目的の検証に焦点を当てている。

検証が成功すれば、我々はそれぞれの \(i\) に対して \(8S_iB = 8R_i + 8H_iA_i\)、つまり各所名が有効であることを確信できる。この理論は単純である。差 \(P_i = 8R_i + 8H_iA_i - 8S_iB\) は素数位数 \(\ell\) の巡回群の元であり、\(\sum_i z_i P_i = 0\) を満たすことが検証されているが、この方程式は全てが \(P_i=0\) でない限り \(2^{-128}\) を超える確率で成り立つことはない。例えば、もし \(P_4\) が非ゼロであれば \(z_1\), \(z_2\), \(z_3\), \(z_5\), \(z_6,\ldots\) の選択は \(\sum_i z_i P_i = 0\) を満たす \(z_4\) の選択肢を一つだけ決定し、\(z_4\) がその選択しに一致する可能性はたかだか \(2^{-128}\) である。

検証が失敗した場合、少なくとも 1 つの無効な署名が存在する必要がある。このとき我々はフォールバックし各署名を個別に検証する。バッチに含まれている少数の無効な署名を識別するためのいくつかの技術があるが、既知の方法は全て無効な署名の数が増加するにつれて個別の検証方法よりも遅くなる。個別の検証はサービス拒否攻撃に対する最善の防衛となる。

高速マルチスカラー乗算

前述の Bos-Coster 法は \(n_1 \ge n_2 \ge \ldots\) となるように \(n_1P_1+n_2P_2+\ldots\) を計算し、再帰的に \((n_1-n_2)P_1 + n_2(P_1+P_2)+\ldots\) を計算する。例えば \(2^{k+1}n_2 \gt n_1 \ge 2^k n_2\) のように \(n_1\) が \(n_2\) より遙かに大きい場合、代わりに \((n_1-2^kn_2)P_1+n_2(2^kP_1+P_2)+\ldots\) を再帰的に計算することで速度を得ることができるが、これが起きるのは非常に希であるためチェックする価値はないことが分かっている。

2 つの最も大きいスカラー値を簡単に識別できるように、我々はスカラー値 \(n_i\) をヒープ (二分木) 上に保持する。ヒープのルートを置き換える通常の方法は、トップダウンでルートから開始し可変ステップ数になるようにスワッピングする。我々はその代わりに [48, Exercise 5.2.3-18] で述べられている (しばしば [25] と [78] に誤ってクレジットされている) Floyd 1964 のボトムアップアルゴリズムを使用する。これは比較の数を幾分減らす利点と、特にバランスの取れたヒープの場合に枝の数を大幅に減らすというあまり知られていない利点を持っている。

結論

バッチサイズ 64 での完全な検証手順は 1 署名あたり 134,000 サイクル未満である。我々のバッチ検証ソフトウェアはまだベンチマークされていないが一般の eBATS ベンチマークフレームワークに含まれている。

バッチサイズを 128 に倍積すると L1 キャッシュに収まらなくなるが、ターゲット CPU のパフォーマンスは向上して署名あたり 125,000 サイクル未満で済む。大規模なバッチでは L2 キャッシュに適合したまま署名ごとに 114,000 サイクル未満がかかる。我々のソフトウェアは復元に約 44,000 サイクルを費やすため、非圧縮公開鍵 (追加 32 バイト) を用いた非圧縮署名 (別の追加 32 バイト) の検証は、バッチサイズ 128 で約 81,000 サイクルしかかからず署名よりもさらに高速である。しかしこの論文ではあまり多くの空間を使用せずに得られる性能を強調した。

References

1. (no editor), 17th annual symposium on foundations of computer science, IEEE Computer Society, Long Beach, California, 1976. MR 56:1766. See [64].
2. (no editor), Technical guideline TR-03111, elliptic curve cryptography (2009). URL: https://www.bsi.bund.de/SharedDocs/Downloads/DE/BSI/Publikationen/TechnischeRichtlinien/TR03111/BSI-TR-03111_pdf.pdf?__blob=publicationFile. Citations in this document: §2.
3. (no editor), SPEED: software performance enhancement for encryption and decryption, 2007. URL: http://www.hyperelliptic.org/SPEED. See [35].
4. (no editor), Proceedings of the 6th ACM symposium on information, computer and communications security, Hong Kong, March 22–24, 2011, Association for Computing Machinery, 2011. ISBN 978-1-4503-0564-8. See [70].
5. Michel Abdalla, Paulo S. L. M. Barreto (editors), Progress in cryptology-LATINCRYPT 2010, first international conference on cryptology and information security in Latin America, Puebla, Mexico, August 8–11, 2010, proceedings, Lecture Notes in Computer Science, 6212, Springer, 2010. ISBN 978-3-642-14711-1. See [59].
6. Masayuki Abe (editor), Advances in cryptology— ASIACRYPT 2010, 16th international conference on the theory and application of cryptology and information security, Singapore, December 5–9, 2010, proceedings, Lecture Notes in Computer Science, 6477, Springer, 2010. ISBN 978-3-642-17372-1. See [38].
7. Adrian Antipa, Daniel R. L. Brown, Robert P. Gallant, Robert J. Lambert, René Struik, Scott A. Vanstone, Accelerated verification of ECDSA signatures, in SAC 2005 [69] (2006), 307–318. MR 2007d:94044. URL: http://www.cacr.math.uwaterloo.ca/techreports/2005/tech_reports2005.html. Citations in this document: §5, §5.
8. Vijay Atluri, Trent Jaeger (program chairs), Proceedings of the 10th ACM conference on computer and communications security, ACM Press, 2003. ISBN 1-58113-738-9. See [47].
9. George Barwood, Digital signatures using elliptic curves, message 32f519ad.19609226@news.dial.pipex.com posted to sci.crypt (1997). URL: http://groups.google.com/group/sci.crypt/msg/b28aba37180dd6c6. Citations in this document: §2.
10. Mihir Bellare, Juan A. Garay, Tal Rabin, Fast batch verification for modular exponentiation and digital signatures, in Eurocrypt ’98 [62] (1998), 236–250. URL: http://cseweb.ucsd.edu/~mihir/papers/batch.html. Citations in this document: §5, §5, §5, §5, §5.
11. Mihir Bellare, Gregory Neven, Multi-signatures in the plain public-key model and a general forking lemma, in CCS 2006 [45] (2006), 390–399. URL: http://cseweb.ucsd.edu/~mihir/papers/multisignatures.html. Citations in this document: §2.
12. Daniel J. Bernstein, Curve25519: new Diffie-Hellman speed records, in PKC 2006 [81] (2006), 207–228. URL: http://cr.yp.to/papers.html#curve25519. Citations in this document: §1, §1, §2, §2, §2, §2, §3.
13. Daniel J. Bernstein, Peter Birkner, Marc Joye, Tanja Lange, Christiane Peters, Twisted Edwards curves, in Africacrypt 2008 [77] (2008), 389–405. URL: http://eprint.iacr.org/2008/013. Citations in this document: §2, §2, §4.
14. Daniel J. Bernstein, Tanja Lange, Faster addition and doubling on elliptic curves, in Asiacrypt 2007 [49] (2007), 29–50. URL: http://eprint.iacr.org/2007/286. Citations in this document: §2, §2.
15. Daniel J. Bernstein, Tanja Lange (editors), eBACS: ECRYPT Benchmarking of Cryptographic Systems, accessed 19 September 2011 (2011). URL: http://bench.cr.yp.to. Citations in this document: §1.
16. G. R. Blakley, David Chaum (editors), Advances in cryptology, proceedings of CRYPTO ’84, Santa Barbara, California, USA, August 19–22, 1984, proceedings, Lecture Notes in Computer Science, 196, Springer, Berlin, 1985. ISBN 3-540-15658-5. MR 86j:94003. See [32].
17. Joppe W. Bos, High-performance modular multiplication on the Cell processor, in WAIFI 2010 [39] (2010), 7–24. Citations in this document: §3.
18. Gilles Brassard (editor), Advances in cryptology— CRYPTO ’89, 9th annual international cryptology conference, Santa Barbara, California, USA, August 20–24, 1989, proceedings, Lecture Notes in Computer Science, 435, Springer, Berlin, 1990. ISBN 3-540-97317-6. MR 91b:94002. See [72].
19. Ernest F. Brickell, Daniel M. Gordon, Kevin S. McCurley, David B. Wilson, Fast exponentiation with precomputation (extended abstract), in Eurocrypt ’92 [71] (1993), 200–207; see also newer version [20]. URL: http://cr.yp.to/bib/entries.html#1993/brickell-exp. Citations in this document: §4.
20. Ernest F. Brickell, Daniel M. Gordon, Kevin S. McCurley, David B. Wilson, Fast exponentiation with precomputation: algorithms and lower bounds (1995); see also older version [19]. URL: http://research.microsoft.com/~dbwilson/bgmw/.
21. Michael Brown, Darrel Hankerson, Julio López, Alfred Menezes, Software implementation of the NIST elliptic curves over prime fields (2000); see also newer version [22]. URL: http://www.cacr.math.uwaterloo.ca/techreports/2000/corr2000-56.ps. Citations in this document: §1, §1.
22. Michael Brown, Darrel Hankerson, Julio López, Alfred Menezes, Software implementation of the NIST elliptic curves over prime fields, in CT-RSA 2001 [56] (2001), 250–265; see also older version [21]. MR 1907102.
23. Billy Bob Brumley, Risto M. Hakala, Cache-timing template attacks, in Asiacrypt 2009 [53] (2009), 667–684. Citations in this document: §1.
24. “Bushing”, Hector Martin “marcan” Cantero, Segher Boessenkool, Sven Peter, PS3 epic fail (2010). URL: http://events.ccc.de/congress/2010/Fahrplan/attachments/1780_27c3_console_hacking_2010.pdf. Citations in this document: §2.
25. Svante Carlsson, Average-case results on heapsort, BIT 27 (1987), 2–17. Citations in this document: §5.
26. Neil Costigan, Peter Schwabe, Fast elliptic-curve cryptography on the Cell Broadband Engine, in Africacrypt 2009 [68] (2009), 368–385. URL: http://cryptojedi.org/users/peter/#celldh. Citations in this document: §3.
27. Peter de Rooij, Efficient exponentiation using precomputation and vector addition chains, in Eurocrypt ’94 [28] (1995), 389–399. MR 1479665. Citations in this document: §5.
28. Alfredo De Santis (editor), Advances in cryptology— EUROCRYPT ’94, workshop on the theory and application of cryptographic techniques, Perugia, Italy, May 9–12, 1994, proceedings, Lecture Notes in Computer Science, 950, Springer, Berlin, 1995. ISBN 3-540-60176-7. MR 98h:94001. See [27], [58].
29. Yvo Desmedt (editor), Advances in cryptology— CRYPTO ’94, 14th annual international cryptology conference, Santa Barbara, California, USA, August 21–25, 1994, proceedings, Lecture Notes in Computer Science, 839, Springer, Berlin, 1994. ISBN 3-540-58333-5. See [50].
30. Vivien Dubois, Pierre-Alain Fouque, Adi Shamir, Jacques Stern, Practical cryptanalysis of SFLASH, in Crypto 2007 [54] (2007), 1–12. URL: http://eprint.iacr.org/2007/141. Citations in this document: §1.
31. Niels Duif, Smart card implementation of a digital signature scheme for Twisted Edwards curves, M.A. thesis, Technische Universiteit Eindhoven, 2011. URL: http://www.nielsduif.nl/2011_05_20_report_final.pdf. Citations in this document: §4.
32. Taher ElGamal, A public key cryptosystem and a signature scheme based on discrete logarithms, in Crypto ’84 [16] (1985), 10–18; see also newer version [33]. MR 87b:94037.
33. Taher ElGamal, A public key cryptosystem and a signature scheme based on discrete logarithms, IEEE Transactions on Information Theory 31 (1985), 469–472; see also older version [32]. ISSN 0018-9448. MR 86j:94045. Citations in this document: §2, §2, §2, §2, §2.
34. Steven Galbraith, Xibin Lin, Michael Scott, Endomorphisms for faster elliptic curve cryptography on a large class of curves, in Eurocrypt 2009 [43] (2009), 518–535. URL: http://eprint.iacr.org/2008/194. Citations in this document: §1, §1, §1.
35. Pierrick Gaudry, Emmanuel Thomé, The mpFq library and implementing curvebased key exchanges, in SPEED [3] (2007), 49–64. URL: http://www.loria.fr/~gaudry/papers.en.html. Citations in this document: §1.
36. Danilo Gligoroski, Rune Steinsmo Odegøard, Rune Erlend Jensen, Ludovic Perret, Jean-Charles Faugère, Svein Johan Knapskog, Smile Markovski, The digital signature scheme MQQ-SIG (2010). URL: http://eprint.iacr.org/2010/527.pdf. Citations in this document: §1.
37. Eu-Jin Goh, Stanislaw Jarecki, Jonathan Katz, Nan Wang, Efficient signature schemes with tight reductions to the Diffie-Hellman problems, Journal of Cryptology 20 (2007), 493–514. URL: http://www.cs.umd.edu/~jkatz/papers.html. See [47].
38. Robert Granger, On the static Diffie–Hellman problem on elliptic curves over extension fields, in Asiacrypt 2010 [6] (2010), 283–302. URL: http://eprint.iacr.org/2010/177. Citations in this document: §1.
39. M. Anwar Hasan, Tor Helleseth (editors), Arithmetic of finite fields, third international workshop, WAIFI 2010, Istanbul, Turkey, June 27–30, 2010, proceedings, Lecture Notes in Computer Science, 6087, Springer, 2010. ISBN 978-3-642-13796-9. See [17].
40. Hüseyin Hisil, Elliptic curves, group law, and efficient computation, Ph.D. thesis, Queensland University of Technology, 2010. URL: http://eprints.qut.edu.au/33233. Citations in this document: §1.
41. Hüseyin Hisil, Kenneth Koon-Ho Wong, Gary Carter, Ed Dawson, Twisted Edwards curves revisited, in Asiacrypt 2008 [63] (2008), 326–343. URL: http://eprint.iacr.org/2008/522. Citations in this document: §4, §4, §4.
42. Zhi Hu, Patrick Longa, Maozhi Xu, Implementing 4-dimensional GLV method on GLS elliptic curves with j-invariant 0 (2011). URL: http://eprint.iacr.org/2011/315. Citations in this document: §1, §1, §1, §1.
43. Antoine Joux (editor), Advances in cryptology— EUROCRYPT 2009, 28th annual international conference on the theory and applications of cryptographic techniques, Cologne, Germany, April 26–30, 2009, proceedings, Lecture Notes in Computer Science, 5479, Springer, 2009. ISBN 978-3-642-01000-2. See [34].
44. Antoine Joux, Vanessa Vitse, Elliptic curve discrete logarithm problem over small degree extension fields. Application to the static Diffie–Hellman problem on \(E({\bf F}_{q^5})\) (2010). URL: http://eprint.iacr.org/2010/157. Citations in this document: §1.
45. Ari Juels, Rebecca N. Wright, Sabrina De Capitani di Vimercati (editors), Proceedings of the 13th ACM conference on computer and communications security, CCS 2006, Alexandria, VA, USA, October 30–November 3, 2006, Association for Computing Machinery, 2006. See [11].
46. Emilia Käsper, Fast elliptic curve cryptography in OpenSSL, in 2nd Workshop on Real-Life Cryptographic Protocols and Standardization (RLCPS 2011), to appear (2011). Citations in this document: §1, §1.
47. Jonathan Katz, Nan Wang, Efficiency improvements for signature schemes with tight security reductions, in CCS 2003 [8] (2003), 155–164; portions incorporated into [37]. URL: http://www.cs.umd.edu/~jkatz/papers.html. Citations in this document: §2.
48. Donald E. Knuth, The art of computer programming, volume 3: sorting and searching, 2nd edition, Addison-Wesley, Reading, 1998. ISBN 0-201-89685-0. Citations in this document: §5.
49. Kaoru Kurosawa (editor), Advances in cryptology— ASIACRYPT 2007, 13th international conference on the theory and application of cryptology and information security, Kuching, Malaysia, December 2–6, 2007, proceedings, Lecture Notes in Computer Science, 4833, Springer, 2007. ISBN 978-3-540-76899-9. See [14].
50. Chae Hoon Lim, Pil Joong Lee, More flexible exponentiation with precomputation, in [29] (1994), 95–107. Citations in this document: §4.
51. Patrick Longa, Catherine H. Gebotys, Efficient techniques for high-speed elliptic curve cryptography, in CHES 2010 [52] (2010), 80–94. Citations in this document: §1, §1, §1.
52. Stefan Mangard, François-Xavier Standaert (editors), Cryptographic hardware and embedded systems, CHES 2010, 12th international workshop, Santa Barbara, CA, USA, August 17–20, 2010, proceedings, Lecture Notes in Computer Science, 6225, Springer, 2010. ISBN 978-3-642-15030-2. See [51].
53. Mitsuru Matsui (editor), Advances in cryptology— ASIACRYPT 2009, 15th international conference on the theory and application of cryptology and information security, Tokyo, Japan, December 6–10, 2009, proceedings, Lecture Notes in Computer Science, 5912, Springer, 2009. ISBN 978-3-642-10365-0. See [23].
54. Alfred Menezes (editor), Advances in cryptology— CRYPTO 2007, 27th annual international cryptology conference, Santa Barbara, CA, USA, August 19–23, 2007, proceedings, Lecture Notes in Computer Science, 4622, Springer, 2007. ISBN 978-3-540-74142-8. See [30].
55. David M’Raïhi, David Naccache, David Pointcheval, Serge Vaudenay, Computational alternatives to random number generators, in SAC ’98 [76] (1999), 72–80. URL: http://www.di.ens.fr/~pointche/Documents/Papers/1998_sac.pdf. Citations in this document: §2.
56. David Naccache (editor), Topics in cryptology— CT-RSA 2001: the cryptographers’ track at RSA Conference 2001, San Francisco, CA, USA, April 2001, proceedings, Lecture Notes in Computer Science, 2020, Springer, 2001. ISBN 3- 540-41898-9. MR 2003a:94039. See [22].
57. David Naccache, David M’Raïhi, Fran¸coise Levy-dit-Vehel, Patent application WO/1998/051038: pseudo-random generator based on a hash coding function for cryptographic systems requiring random drawing (1997). URL: http://www.wipo.int/pctdb/en/ia.jsp?IA=FR1998000901. Citations in this document: §2.
58. David Naccache, David M’Raïhi, Serge Vaudenay, Dan Raphaeli, Can D.S.A. be improved? Complexity trade-offs with the digital signature standard, in Eurocrypt ’94 [28] (1994). Citations in this document: §5, §5, §5, §5, §5, §5, §5.
59. Michael Naehrig, Ruben Niederhagen, Peter Schwabe, New software speed records for cryptographic pairings, in Latincrypt 2010 [5] (2010), 109–123. URL: http://cryptojedi.org/users/peter/#dclxvi. Citations in this document: §3.
60. Gregory Neven, Nigel P. Smart, Bogdan Warinschi, Hash function requirements for Schnorr signatures, Journal of Mathematical Cryptology 3 (2009), 69–87. URL: http://www.zurich.ibm.com/~nev/papers/schnorr.html. Citations in this document: §2, §2.
61. Phong Q. Nguyen, Igor Shparlinski, The insecurity of the elliptic curve digital signature algorithm with partially known nonces, Designs, Codes and Cryptography 30 (2003), 201–217. Citations in this document: §2.
62. Kaisa Nyberg (editor), Advances in cryptology— EUROCRYPT ’98, international conference on the theory and application of cryptographic techniques, Espoo, Finland, May 31–June 4, 1998, proceedings, Lecture Notes in Computer Science, 1403, Springer, 1998. ISBN 3-540-64518-7. See [10].
63. Josef Pieprzyk (editor), Advances in cryptology— ASIACRYPT 2008, 14th international conference on the theory and application of cryptology and information security, Melbourne, Australia, December 7–11, 2008, Lecture Notes in Computer Science, 5350, 2008. ISBN 978-3-540-89254-0. See [41].
64. Nicholas Pippenger, On the evaluation of powers and related problems (preliminary version), in FOCS ’76 [1] (1976), 258–263; newer version split into [65] and [66]. MR 58:3682. URL: http://cr.yp.to/bib/entries.html#1976/pippenger. Citations in this document: §4, §5.
65. Nicholas Pippenger, The minimum number of edges in graphs with prescribed paths, Mathematical Systems Theory 12 (1979), 325–346; see also older version [64]. ISSN 0025-5661. MR 81e:05079. URL: http://cr.yp.to/bib/entries.html#1976/pippenger.
66. Nicholas Pippenger, On the evaluation of powers and monomials, SIAM Journal on Computing 9 (1980), 230–250; see also older version [64]. ISSN 0097-5397. MR 82c:10064. URL: http://cr.yp.to/bib/entries.html#1976/pippenger.
67. David Pointcheval, Jacques Stern, Security arguments for digital signatures and blind signatures, Journal of Cryptology 13 (2000), 361–396. URL: ftp://ftp. di.ens.fr/pub/users/pointche/Papers/2000_joc.pdf. Citations in this document: §2.
68. Bart Preneel (editor), Progress in cryptology— AFRICACRYPT 2009, second international conference on cryptology in Africa, Gammarth, Tunisia, June 21–25, 2009, proceedings, Lecture Notes in Computer Science, 5580, Springer, 2009. See [26].
69. Bart Preneel, Stafford E. Tavares (editors), Selected areas in cryptography, 12th international workshop, SAC 2005, Kingston, ON, Canada, August 11–12, 2005, revised selected papers, Lecture Notes in Computer Science, 3897, Springer, 2006. ISBN 3-540-33108-5. MR 2007b:94002. See [7].
70. Jothi Rangasamy, Douglas Stebila, Colin Boyd, Juan González Nieto, An integrated approach to cryptographic mitigation of denial-of-service attacks, High-speed high-security signatures 23 in ASIACCS 2011 [4] (2011). URL: http://www.douglas.stebila.ca/files/research/papers/RSBG11.pdf. Citations in this document: §1.
71. Rainer A. Rueppel (editor), Advances in cryptology— EUROCRYPT ’92, workshop on the theory and application of cryptographic techniques, Balatonfüred, Hungary, May 24–28, 1992, proceedings, Lecture Notes in Computer Science, 658, Springer, Berlin, 1993. ISBN 3-540-56413-6. MR 94e:94002. See [19].
72. Claus P. Schnorr, Efficient identification and signatures for smart cards, in Crypto ’89 [18] (1990), 239–252; see also newer version [73]. Citations in this document: §2, §2, §2.
73. Claus P. Schnorr, Efficient signature generation by smart cards, Journal of Cryptology 4 (1991), 161–174; see also older version [72]. URL: http://www.mi.informatik.uni-frankfurt.de/research/papers.html.
74. Claus P. Schnorr, Markus Jakobsson, Security of discrete log cryptosystems in the random oracle + generic model (2000). URL: http://www.mi.informatik.uni-frankfurt.de/research/papers.html. Citations in this document: §2.
75. Jacques Stern, David Pointcheval, John Malone-Lee, Nigel P. Smart, Flaws in applying proof methodologies to signature schemes, in Crypto 2002 [80] (2002), 93–110. Citations in this document: §2.
76. Stafford Tavares, Henk Meijer (editors), Selected areas in cryptography, 5th annual international workshop, SAC98, Kingston, Ontario, Canada, August 17–18, 1998, proceedings, Lecture Notes in Computer Science, 1556, Springer, 1999. ISBN 3-540-65894-7. See [55].
77. Serge Vaudenay (editor), Progress in cryptology— AFRICACRYPT 2008, First international conference on cryptology in Africa, Casablanca, Morocco, June 11–14, 2008, proceedings, Lecture Notes in Computer Science, 5023, Springer, 2008. ISBN 978-3-540-68159-5. See [13].
78. Ingo Wegener, Bottom-up-heapsort, a new variant of heapsort, beating, on average, quicksort (if n is not very small), Theoretical Computer Science 118 (1993), 81–98. Citations in this document: §5.
79. John Wigley, Removing need for rng in signatures, message 5gov5d$pad@wapping.ecs.soton.ac.uk posted to sci.crypt (1997). URL: http://groups.google.com/group/sci.crypt/msg/a6da45bcc8939a89. Citations in this document: §2.
80. Moti Yung (editor), Advances in cryptology— CRYPTO 2002, 22nd annual international cryptology conference, Santa Barbara, California, USA, August 18–22, 2002, proceedings, Lecture Notes in Computer Science, 2442, Springer, 2002. ISBN 3-540-44050-X. See [75].
81. Moti Yung, Yevgeniy Dodis, Aggelos Kiayias, Tal Malkin (editors), Public key cryptography— 9th international conference on theory and practice in public-key cryptography, New York, NY, USA, April 24–26, 2006, proceedings, Lecture Notes in Computer Science, 3958, Springer, 2006. ISBN 978-3-540-33851-2. See [12].

翻訳抄

楕円曲線暗号アルゴリズムの一種であるエドワーズ曲線デジタル署名 (EdDSA; ed25519, ed448) の速度やセキュリティ優位性に関する 2011 年の論文。

1. Daniel J. Bernstein, Niels Duif, Tanja Lange, Peter Schwabe, Bo-Yin Yang. High-speed high-security signatures. Journal of Cryptographic Engineering 2 (2012), 77–89. Document ID: a1a62a2f76d23f65d622484ddd09caf8. URL: https://cr.yp.to/papers.html#ed25519. Date: 2011.09.26.