ECC(楕円曲線暗号)についてまとめる

Introduction

有名な暗号化方式であるRSAがありますが，RSAは素因数分解の難しさを根拠としてセキュリティの安全性を担保していますが，この素因数分解という操作を簡単にするアルゴリズムの研究が進められている．（エラストテネスのふるい，Quadratic Sieve, 一般数体篩法）これらを用いることにより早く解くことができるそう，地球の集合知だ．．．

そこで，楕円曲線暗号（ECC）というものが登場する．ECCは楕円曲線の離散対数問題を基にしている．この離散対数問題は，素因数分解よりも難しいとされているそうで，まぁようは小さいbit数で安全性を確保できるそうな．具体的にはRSA2048 < ECD 256　でその差は20倍以上あるらしい．強いの大好き．ECC知りたい!!ということでこの記事

楕円曲線暗号の仕組み

楕円曲線の定義

楕円曲線とは，楕円のことではありません．えぇ！！以下の式で表されるのが楕円曲線です．

ワイエルシュトラウス型：y^2 = x^3 + ax + b (a not = 0, b not = 0)

モンゴメリ型：By^2 = x^3 + Ax^2 + x (B(A^2-4) not = 0)

楕円積分からくる曲線らしいのですが，まぁ，楕円ではないですね.

楕円曲線の加法

楕円曲線の加法は，2点を足すときに，まず直線を引いて交点を求めます．その後，この交点をy軸で反転させたものが答えです．

また，これに無限遠点を加えることで，すべての点が加法の対象となります。

この無限遠点は，楕円曲線上の特別な点であり，計算において重要な役割を果たします。（太陽みたいな点，平行光源であるという点において）

加法群

有限体での話

さて，実際に暗号として使うときには，実数ではなく有限体（例えば mod p）上で楕円曲線を扱います．つまり，x座標もy座標も「mod p」の世界で考える必要があります．

このとき，加法も有限体上での演算になります．普通の加算・乗算とは異なり，modを取るため，小数などは出てきません．

有限体上の楕円曲線は，点が有限個（でも結構たくさん）しか存在せず，この中で加法を定義していくことで暗号としての構造が生まれます．

離散対数問題

楕円曲線暗号の安全性の根拠となっているのが「楕円曲線離散対数問題（ECDLP）」です．

簡単に言うと，「Pという点を何回足したらQになるか？」を求める問題です．つまり，Q = kP のとき，PとQが分かっていてもkを求めるのがとても難しいというわけです．

この“とても難しい”という性質のおかげで，敵が秘密鍵を推測するのが極めて困難になるというわけですね．

実際の流れ

1. まず，送信者と受信者は共通の楕円曲線と基準点（Gと呼ばれる）を共有しておきます．

2. 受信者はランダムな秘密鍵 d を選び，公開鍵として Q = dG を計算し，相手に送ります．

3. 送信者は，メッセージを点に変換し，ランダムな値kを使って暗号化ペア (kG, Pm + kQ) を作成して送信します．

4. 受信者は秘密鍵 d を使って，kQ の部分を取り除いてメッセージを復元します（計算としては Pm + kQ - d(kG) = Pm になる）

要するに，ランダム性と離散対数の難しさを活用して，安全な通信を可能にしているのです．

楕円曲線暗号の実装

楕円曲線暗号は，公開鍵暗号の一種であり，公開鍵と秘密鍵を用いてデータを暗号化します．

まず，公開鍵と秘密鍵を生成します．公開鍵は，楕円曲線上の点であり，秘密鍵は整数です．

次に，データを暗号化するために，公開鍵を使用してデータを変換します．この変換は，楕円曲線上の点として表現されます．

最後に，秘密鍵を使用してデータを復号化します．この復号化は，楕円曲線上の点から元のデータを取得するプロセスです．

おわりに

楕円曲線暗号は，一見難しそうに見えますが，基本となるアイデアは「点の加算」と「難しい計算問題」に基づいています．

RSAと比較して軽量で，IoT機器やスマートカードなどのリソースが限られた環境でも強力なセキュリティを提供できるのが魅力ですね．

今後は，量子コンピュータによってこれらの暗号がどのように影響を受けるかも注目されています．ポスト量子暗号（PQC）との関係も気になりますね．