セキュリティ

暗号プリミティブのパフォーマンス比較

Takami Torao #RSA #ECDSA #Schnorr #BLS
  • このエントリーをはてなブックマークに追加

Table of Contents

  1. 公開鍵アルゴリズム
  2. 電子署名アルゴリズム
    1. 署名作成と署名検証
    2. バッチ検証
    3. 署名集約

公開鍵アルゴリズム

Algorithm Private Key \(S_k\) Public Key \(P_k\) Gen KeyPair
RSA (2048/SHA256/PKCS1v15) 1,191B 270B 74,347.359[μs] 📓
ECDSA (NIST P-256) 32B 65B 173.135[μs] 📓
ECDSA (secp256k1) 32B 65B 58.266[μs] 📓
Ed25519 32B 32B 16.507[μs] 📓
EC-Schnorr (ed25519 variant) 64B 32B 17.573[μs] 📓
BLS12-381 G2 32B 48B 204.005[μs] 📓
Table 1. Ubuntu 20.04 LTS (WSL) - AMD Ryzen 9 3900XT 12C/24T @ 3.79GHz
Algorithm Private Key \(S_k\) Public Key \(P_k\) Gen KeyPair
RSA (2048/SHA256/PKCS1v15) 1,190B 270B 71,646.098[μs] 📓
ECDSA (NIST P-256) 32B 65B 184.976[μs] 📓
ECDSA (secp256k1) 32B 65B 57.306[μs] 📓
Ed25519 32B 32B 18.665[μs] 📓
EC-Schnorr (ed25519 variant) 64B 32B 18.096[μs] 📓
BLS12-381 G2 32B 48B 216.754[μs] 📓
Table 2. macOS 10.15 - Intel i7-8569U 4C/8T @ 2.80GHz

電子署名アルゴリズム

署名対象のメッセージ \(m\) の長さは 0 バイトとしている。現実的には署名前のハッシュ適用のためにメッセージ長に比例した性能劣化が加算される。

時間性能は使用している実装にも大きく依存する点に注意。

署名作成と署名検証

Algorithm Signature \(\sigma\) Sign Verify
RSA (2048/SHA256/PKCS1v15) 256B 1,285.915[μs] 146.216[μs] 📓
ECDSA (NIST P-256) 64B 193.348[μs] 354.158[μs] 📓
ECDSA (secp256k1) 64B 73.570[μs] 124.267[μs] 📓
Ed25519 64B 21.949[μs] 52.792[μs] 📓
EC-Schnorr (ed25519 variant) 64B 21.632[μs] 50.846[μs] 📓
BLS12-381 G2 96B 2,089.379[μs] 3,668.689[μs] 📓
Table 3. Ubuntu 20.04 LTS (WSL) - AMD Ryzen 9 3900XT 12C/24T @ 3.79GHz
Algorithm Signature \(\sigma\) Sign Verify
RSA (2048/SHA256/PKCS1v15) 256B 1,531.483[μs] 182.418[μs] 📓
ECDSA (NIST P-256) 64B 219.805[μs] 393.421[μs] 📓
ECDSA (secp256k1) 64B 91.812[μs] 112.293[μs] 📓
Ed25519 64B 27.610[μs] 145.638[μs] 📓
EC-Schnorr (ed25519 variant) 64B 34.297[μs] 79.182[μs] 📓
BLS12-381 G2 96B 2,621.035[μs] 4,548.877[μs] 📓
Table 4. macOS 10.15 - Intel i7-8569U 4C/8T @ 2.80GHz

バッチ検証

電子署名のバッチ検証は複数の署名 \(\sigma_i\) をまとめて検証する手法。いくつかの公開鍵暗号スキームで提案や実装が行われているが、一般的に署名をひとつづつ検証するよりも時間効率が良い。以下のそれぞれがすべて「バッチ検証」と呼ばれているため、アルゴリズムが目的の用途のものであるかを確認する必要がある。

  1. 異なる公開鍵 \(P_i\) を使って異なるメッセージ \(m_i\) で生成した署名 \(\sigma_i\) の検証: \({\sf batch\_verify}(P_i,\sigma_i,m_i)\)
  2. 異なる公開鍵 \(P_i\) を使って単一のメッセージ \(m\) で生成した署名 \(\sigma_i\) の検証: \({\sf batch\_verify}(P_i,\sigma_i,m)\)
  3. 単一の公開鍵 \(P\) を使って異なるメッセージ \(m_i\) で生成した署名 \(\sigma_i\) の検証: \({\sf batch\_verify}(P,\sigma_i,m_i)\)

アルゴリズム上は \(n\) 個の署名に対して \(O(1)\) の時間効率であったとしても、現実的な適用では \(m_i\) をそれぞれハッシュ関数に適用する必要があるため線形増加 \(O(n)\) の傾向 (個別検証より緩やかではあるが) となる。

Rust 実装では Ed25591 の ed25519-dalek, schnorrkel でバッチ検証を行うことができる。ともにバッチサイズに対して検証時間は線形増加だが、1 署名の検証が約 70[μs] に対して 1,000 署名で (70[ms] ではなく) 18[msec] に抑えられていることから個別検証よりも時間効率が良いことが分かる。

署名集約