66260
ssh で利用される暗号化鍵には、長らく RSA が利用されてきました。RSA と比べれば最近になって、 EdDSA の暗号化方式が追加されたようです。

# 質問

EdDSA による暗号化は、アルゴリズム的には RSA の上位互換ですか？ 具体的には、

  * 暗号を破るための計算を行う際の計算量クラスは RSA 以上で
  * 同等のセキュリティを提供するために必要な暗号鍵の長さは RSA 以下で
  * 実際に署名の verification などを行う際の計算量クラスは RSA 以下

であれば、上位互換と言えるかな、と考えているのですが、これは真でしょうか？逆に、この中で RSA の方が優れた性質を示す項目はありますか？
CC BY-SA 4.0
2020-05-02T04:45:40.320
66196
2020-05-07T11:11:40.543
2020-05-02T05:41:33.860
754
754
question
アルゴリズム ssh 暗号理論 rsa
eddsa による暗号化は、 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](https://www.rfc-editor.org/rfc/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の方が速いという事になると思います。  
この点からも上位互換とは言えないと思います。
CC BY-SA 4.0
2020-05-03T20:48:07.247
66260
2020-05-07T11:11:40.543
2021-10-07T07:34:52.683
-1
12203
66196
answer