はじめに

「楕円曲線①」では楕円曲線と数学的に困難な問題について記載しました。今回の記事では楕円曲線を使った暗号について解説します。

楕円ElGamal暗号の概要

楕円曲線上の離散対数問題（ECDLP）1985年にKoblitzとMillerによって解くのが難しいと考えられることを発見しました。2人は共同研究ではなく、それぞれ別にこの問題を発見しています。この問題をもとに構成されるのが楕円曲線暗号（ECC）です。

ECCにはデジタル署名（ECDSA）や鍵共有（ECDH鍵共有）などがありますが、暗号化のために使われるのが楕円曲線上の群の上でElGamal暗号を構成した楕円ElGamal暗号です。

楕円ElGamal暗号

楕円ElGamal暗号とは、前述の通り、楕円曲線上の群の上で構成したElGamal暗号を構成したものです。ElGamal暗号とは、位数が大きな群の離散対数問題が困難であることを安全性の根拠とした公開鍵暗号の一つです。

前回の記事では楕円曲線上の点 $G, P$ に対して $G=kP$ となるような $k$ を求める離散対数問題を紹介しました。この問題の困難性を応用して $G$ を公開鍵、$k$ を秘密鍵とした公開鍵暗号が楕円曲線暗号です。

次に、楕円ElGamal暗号を作る具体的なアルゴリズムをご紹介します。

①公開パラメータの設定

１．自然数$n$ 、$n$ ビットの素数 $q$ 、有限体 $F_q$ を定める。また $F_q$ 上の整数 $a, b$ を選び、それを係数とする楕円曲線 $E:y^2=x^3+ax+b$ を決定する

２．楕円曲線上の点 $P$ を基準点として選ぶ。$P$ の位数 $u$ を求める

３．$a, b, G, u$ を公開パラメータとして全ての利用者に共有する

②鍵生成

１．$u/2<k<u$ となるような自然数 $k$ を選び秘密鍵とする

２．$G=kP$ を計算し、$G$ を公開鍵として利用者に共有する

③暗号化

１．平文を $m\in E$ とする

２．乱数 $r$ を生成し、$C_1 = rP$ を計算する

３．$C_2=m+rG$ を計算する

４．$C = (C_1, C_2)$ を暗号文とする

④復号

１．$m=C_2-kC_1$ を計算して平文を計算する

楕円ElGamal暗号のメリット・デメリット

①メリット

楕円ElGamal暗号と同じく公開鍵暗号として代表的なRSA暗号と比較して優れている点は、格段に鍵が短い鍵長で同程度の安全性を実現できることです。RSA暗号では2048bitの鍵長の安全性が楕円曲線暗号では224bit程度で実現できます。これにより高速な処理が可能です。

この理由は楕円曲線の離散対数問題の方が（現時点では）よりときにくい問題だからです。RSA暗号は素因数分解問題には準指数関数時間（多項式時間と指数関数時間の間の計算量）で解くことができるアルゴリズムが存在します。一方で楕円曲線上の離散対数問題は現在見つかっているアルゴリズムを用いても、解くために指数関数時間要します。そのため短い鍵で安全性を担保することができます。

②デメリット

デメリットとされる一つは、位数を前述の通り位数が低い場合に一部の楕円曲線では多項式時間で離散対数問題を解くことができるものが存在します。これを避けるためには一般的には楕円曲線の位数（楕円曲線上の点の数）が大きなものを選ぶ必要があります。

楕円曲線の位数を求める方法の一つがハッセの定理です。

ハッセの定理

ハッセの定理（ハッセの境界）は有限体 $F_p$ 上の楕円曲線の点の個数（楕円曲線の位数）を評価するものです。楕円曲線上の有理点の個数を $\# E(F_p)$ とすると次の不等式が成り立ちます。

$$ |\# E(F_p)-(p+1)|≤2\sqrt{p} $$

これは楕円曲線の点の個数と $(p+1)$ との差が $2\sqrt{p}$ 以下で抑えられるということです。

また、$\# E(F_p)=p+1-t$ となる整数 $t$ が存在し、$t$ をトレースと呼びます。

この定理から位数の範囲を知ることができます。しかし、多くの場合には位数を直接求めるためSEA(Schoof-elkies-Atkin)法と呼ばれるアルゴリズムが用いられます。このアルゴリズムは一般的には計算量が $O(log(q)^{2\mu+2})$ 程度 ( $\mu$ には $2$ や $log_23$ が代入されます）になりますが、これは数学的に証明されたものではなく実験から得られた平均値です。最大値と最小値の差が大きくなるので場合によっては最大値を抑える工夫が必要です。

また、楕円曲線では基準点 $P$ を位数 $u$ が小さいものを選ぶことで鍵を小さくすることができます。しかしハッセの定理より $q$ が小さいと楕円曲線上の点の個数も少なくなります。これは楕円曲線暗号での平文は楕円曲線暗号上の有理点なので平文の取れる範囲が狭くなることを意味します。平文空間と鍵の大きさのバランスを見ながら $q$ の値を決定する必要があります。

安全性

前回のブログ記事の通り、楕円曲線上の離散対数問題を解くことは非常に難しいとされます。しかし位数が小さい場合には位数を素因数分解して小さな離散対数問題に帰着させるPHS法があります。PHS法の対策として位数を素数か約数に大きな素数が含まれるような数にすることが考えられます。

また、一部の特殊な楕円曲線にも効率的な攻撃方法が知られています。ここで「特殊」としているのはトレースが0~2の非常に小さい楕円曲線のことです。平方根法では、この特殊性を応用し他攻撃ではPHS法以上に効率的に計算することができます。そのため楕円曲線暗号を安全に使用するためには素数または素数に近い大きな位数の楕円曲線を選択することが必須です。

NISTやTLSなどでは楕円曲線のパラメータが規定されています。主要なものの一つとしてsecp256k1と呼ばれる楕円曲線があります。この場合は $y^2=x^3+7$ 、法とする素数は $2^{256}−2^{32}−2^9−2^8−2^7−2^6−2^4−1$ です。

楕円曲線を用いたデジタル署名（ECDSA）

楕円曲線上の離散対数問題の応用先としてデジタル署名もあります。デジタル署名とはメッセージの内容と署名者の正当性を保証するものです。これは署名者だけが秘密鍵を持ち、秘密鍵を用いて署名を作成します。利用者は公開鍵と署名者があらかじめ作ったハッシュ値を使ってその署名を検証することができます。

ECDSAが使われる代表的な例としてブロックチェーンがあります。ビットコインやイーサリアムなどのブロックチェーンでトランザクションの署名に使われています。ちなみに、ビットコインやイーサリアムで使われている楕円曲線の方式はsecp256k1です。

ECDSAは電子政府推奨暗号リストに掲載されている署名の一つです。

まとめ

ECDLPを利用し暗号処理の流れに落とし込むことで、楕円ElGamal暗号という暗号を実現できる
楕円ElGamal暗号はRSA暗号に比べて短い鍵長で安全性が担保される
ECDLPを使ったデジタル署名も存在し、安全な手法として推奨されている

参考文献

N. コブリッツ著 ; 櫻井幸一訳（1997）『数論アルゴリズムと楕円暗号理論入門』ュプリンガー・フェアラーク東京
IPUSIRON（2018）『暗号技術の全て』株式会社翔泳社
岡本龍明（2020）『現代暗号の誕生と発展』近代科学社
“楕円曲線暗号と RSA 暗号の安全性比較”, 富士通株式会社, 株式会社富士通研究所
Ivan Ristic著; 斎藤孝道訳(2021)『プロフェッショナルSSL/TLS』ラムダノート株式会社
電子政府における調達のために参照すべき暗号のリスト, デジタル庁・総務省・経済産業平成25年3月1日