📝

【技術】楕円曲線暗号②

2023/6/14 11:002023/8/21 6:15

はじめに

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

楕円ElGamal暗号の概要

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

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

楕円ElGamal暗号

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

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

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

①公開パラメータの設定

自然数、ビットの素数、有限体を定める。また上の整数を選び、それを係数とする楕円曲線を決定する

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

を公開パラメータとして全ての利用者に共有する

②鍵生成

となるような自然数を選び秘密鍵とする

を計算し、を公開鍵として利用者に共有する

③暗号化

平文をとする

乱数 r を生成し、を計算する

を計算する

を暗号文とする

④復号

を計算して平文を計算する

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

①メリット

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

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

②デメリット

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

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

ハッセの定理

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

これは楕円曲線の点の個数ととの差が以下で抑えられるということです。

また、となる整数が存在し、をトレースと呼びます。

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

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

安全性

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

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

NISTやTLSなどでは楕円曲線のパラメータが規定されています。主要なものの一つとしてsecp256k1と呼ばれる楕円曲線があります。この場合は、法とする素数はです。