サーバの証明書で使われる楕円曲線暗号について調べた

Jul 11, 2021 23:25 · 2060 words · 5 minute read Security

ふとこのブログの証明書情報を見ていたら、公開鍵のアルゴリズムとして楕円曲線暗号を使っていました。

このブログはnetlifyで公開しており、netlifyでは自動でLet’s Encryptを使った証明書の設定をしてくれます。

楕円曲線暗号・・・なんだったっけ？
昔受けた情報処理の試験で見た覚えはあるのですが、「楕円曲線の数式を使った暗号だよね？」くらいしか覚えていません。
というわけで、下記の論文と「暗号技術のすべて」という書籍で楕円曲線暗号のメリットやRSAとの違いについて学びました。

日本銀行金融研究所公開鍵暗号を巡る新しい動き：RSAから楕円曲線暗号へ (PDF)

暗号技術のすべて /翔泳社/ＩＰＵＳＩＲＯＮ

posted with カエレバ

楽天市場で見る

Amazonで見る

「暗号技術のすべて」では、シーザー暗号のような古典暗号から、共通鍵暗号や公開鍵暗号など、様々な暗号について数式を交えながら詳しく解説されています。
暗号に関して疑問がでたときに手元にあると便利な一冊です。

前置きが長くなりましたが、この記事では論文を読んだ中で「なるほど」と思った内容のメモを残しておきます。

RSA暗号
- 推奨鍵長
- RSA暗号の問題点
楕円曲線暗号のメリット
暗号の安全性
楕円曲線暗号の攻撃手法
- 指数計算法って？
最後に
参考資料

RSA暗号

楕円曲線暗号の話に入る前に、現在多くのWebサイトで使われているRSA暗号について書きます。

2021年7月現在では、多くのWebサイトの証明書の公開鍵でRSA暗号が使われています。
RSA暗号では、「数学的に解くことが困難である」ということを暗号の安全性の根拠にしており、鍵の長さが長くなるほど答えを導く計算量が膨大になります。
しかし、現代ではコンピュータの計算能力がどんどん向上しており、「安全だ」と言えるRSA暗号の鍵の長さは年々長くなっています。

推奨鍵長

NIST（アメリカ国立標準技術研究所）とCRYPTREC（Cryptography Research and Evaluation Committees）が出しているRSA暗号の推奨鍵長は下記の通りです。

NIST

2030年までの利用を想定する場合は、2048bitの鍵長を推奨
Recommendation for Key Management (PDF)

CRYPTREC5

1024bitの暗号が解読可能になる時期として2010年から20年間を推定
2048bit以上の鍵長を推奨
SSL/TLS 暗号設定ガイドライン (PDF)

内閣サイバーセキュリティセンター（NISC）でも、2013年度末までに各省庁で利用するシステムを2048bitのRSAに移行したようです。

RSA暗号の問題点

RSA暗号において、「数学的計算量の観点から安全である（現実的な時間内に解くことができない）」と言える鍵長はどんどん長くなっています。
前述の通り、2021年7月現在では2048bitを推奨している機関が多いようです。

しかし、鍵の長さが長くなるにつれて、計算に必要な処理能力や計算資源も増大していきます。そうなると、ICカードや組み込み機器といった計算能力が乏しい環境において、RSAの利用が難しくなることが予想されます。

楕円曲線暗号のメリット

そこで楕円曲線暗号のメリットが活きてきます。
楕円曲線暗号では、RSAの1/10程度の鍵長で、同程度の安全性を確保することができます。
データサイズが小さくて済むので処理効率が良いとされています。
また、楕円曲線暗号の仕様により、RSAと比較して管理者の鍵管理ミスも発生しにくくなっています。

画像引用元: NICT News 暗号の安全性評価

暗号の安全性

暗号の安全性は数学的な計算量によって保証されています。
暗号化に用いた方式が、数学的に「現実的な時間で解くことができない（全力で計算してもとんでもない年月がかかる）」場合、「安全である」とされます。

計算量には3のカテゴリがあり、指数関数時間と準指数関数時間の場合は「計算量的に安全」とされています。

カテゴリ	特徴
指数関数時間	鍵長に比例して、必要計算量が指数関数的に急増する。
準指数関数時間	指数関数時間と多項式時間の中間の計算量。
多項式時間	鍵長に比例して、計算量は多項式関数と同じくらいに緩やかに増える。指数関数時間と比較すると圧倒的に小さい。