質問: EdDSA による暗号化は、アルゴリズム的には RSA の上位互換ですか? 具体的には、 * 暗号を破るための計算を行う際の計算量クラスは RSA 以上で * 同等のセキュリティを提供するために必要な暗号鍵の長さは RSA 以下で * 実際に署名の verification などを行う際の計算量クラスは RSA 以下 であれば、上位互換と言えるかな、と考えているのですが、これは真でしょうか?逆に、この中で RSA の方が優れた性質を示す項目はありますか?
回答: sshに関係なく公開鍵暗号一般での話と考えた場合、それぞれの方式で行える事は * RSA: 暗号化と署名 * EdDSA: 署名のみ なので、上位互換とは言えないでしょう。 SSHでの公開鍵認証で考えた場合、利用するのは署名のみとなります。 以下はSSHでの公開鍵認証に絞った話となります。 > > 同等のセキュリティを提供するために必要な暗号鍵の長さは RSA 以下で > > > これは何を基準にするかによって答えが変わると思います。 ECDSAやEdDSAは利用する曲線により強度が変わります。 SSH で使われる Ed25519 の場合は Curve25519 という曲線を使い、この場合の鍵長は 256 bit です。 RSA で同等の強度と言われているのは 3072 bit なので、これを元にすれば Ed25519 の方が鍵長は短いと言えます。 この辺りの詳細については"等価安全性"で検索してみて下さい。 一方、RSA 4096 bit を元に考えた場合、Ed25519 は RSA 3072 bit 相当でしかないので、そもそも同等のセキュリティを提供するのは不可能という事になります。 2020/05/07追記: 見逃していたのですが、2020/02/25にRFC8709 が出た事によりSSHで使えるEdDSAとしてEd448が追加されました。これにより、RSA 4096bitよりも強度が高いEdDSA署名が使える事になります。 ただし、以下の問題は残ります。 * 現状ではEd448をサポートした実装がほぼ無い * RSAのようにbit数が可変ではなく、256bit(Ed25519), 448bit(Ed448) の二種類しか無い SSH の公開鍵認証の場合、併用するハッシュ関数の強度も問題になりますが、詳細については省きます。 > > 暗号を破るための計算を行う際の計算量クラスは RSA 以上で > > 実際に署名の verification などを行う際の計算量クラスは RSA 以下 > > > 計算量オーダーはソートのように対象データが一定でない場合の比較には便利ですが、SSH の公開鍵認証、特に Ed25519 のように鍵長が一定で、署名対象のデータの長さもほぼ一定という状況のように、パラメータが一定の場合は計算量オーダーで比較するのはあまり意味がないと思います。 2020/05/07追記: 計算量オーダーで比較するのはあまり意味がないというのは、パラメータが固定なのだから実際の速度で比べた方がいいという意味です。 一例として手元の環境で`openssl speed`コマンドで比較してみました。 ``` % openssl speed rsa3072 ed25519 Doing 3072 bits private rsa's for 10s: 2551 3072 bits private RSA's in 9.86s Doing 3072 bits public rsa's for 10s: 128817 3072 bits public RSA's in 9.87s Doing 253 bits sign Ed25519's for 10s: 238724 253 bits Ed25519 signs in 9.87s Doing 253 bits verify Ed25519's for 10s: 71419 253 bits Ed25519 verify in 9.85s OpenSSL 1.1.1d-freebsd 10 Sep 2019 built on: reproducible build, date unspecified options:bn(64,64) rc4(8x,int) des(int) aes(partial) idea(int) blowfish(ptr) compiler: clang sign verify sign/s verify/s rsa 3072 bits 0.003865s 0.000077s 258.7 13055.1 sign verify sign/s verify/s 253 bits EdDSA (Ed25519) 0.0000s 0.0001s 24193.7 7249.5 ``` 傾向としては、署名生成に関してはEd25519の方が圧倒的に速いですが、署名検証はRSA 3072 bitの方が速いという事になると思います。 この点からも上位互換とは言えないと思います。