楕円曲線暗号（EC Elgamal）を実装する

少し前の記事でIUT理論に関する書籍を読んでいましたが，その中で楕円曲線の対称性を利用したという記述がありました．また，楕円曲線の持つ特殊性から暗号分野にも応用されていると．
恥ずかしながら私はRSA暗号・AES暗号あたりしか触ったことがなく，楕円曲線暗号の理論を知らなかったので，今回その基本機能を実装することにしました．最近javaを強いられていて心が疲弊しているので，久々にHaskellを使います．
今回は下記書籍が大変参考になりました．

暗号理論と楕円曲線数学的土壌の上に花開く暗号技術 | 森北出版株式会社
後ろの章で扱う定理や用語が大分前の章で使われるなど，ページをいったりきたりしたものの，
練習問題も多く，総じて学部以来ご無沙汰な人間にもとても分かりやすかったです．
その他参考にした文献は末尾にまとめました．

楕円曲線上の加算

楕円暗号は，RSA暗号での鍵長1024bitに相当する安全性を，わずか160bitで実現することができます．
$E : Y^2 = x^3 + aX + b$
の楕円曲線方程式上で，大きな素位数において巡回群となるよう
Eと $\mathbb{F}_p$ を選ぶことが出来れば，暗号実装の舞台は整います．
なお，以下ではすべて，pによる剰余類群上での話として扱います．
この際，楕円曲線上の点の数がほとんど素数であれば安全性が高いと言え，スクーフのアルゴリズムで計算可能です．ただ，今回は楕円方程式の探索は行っていないので詳しいことは資料を当たってください．
※ $\mathbb{F}_p$ :: $\mathbb{Z}/p\mathbb{Z}$ でpが素数の時， $\mathbb{Z}/p\mathbb{Z}$ は０を除いて逆元を有し有限個の元をもつ有限体を形成する．また，これを $\mathbb{F}_p$ と書く．通常，暗号では $\mathbb{F}_2$ が使用されるようです．本記事では書籍に則りp=31を使います．
楕円曲線暗号のアルゴリズムについては多くのwebサイトで開設されているのでそちらに譲りますが，剰余類楕円曲線上の加法演算についてはまとめておきます．

楕円曲線 $E$ 上の点 $P_1, P_2$ があるとき， $P_1 + P_2$ とは，単純に二点の座標を座標軸ごとに加算する方法は，楕円曲線上に乗りませんので成立しません．
そこでまず，この二点を結ぶ直線を考えます．( $P_2 = P_1$ の時は $P_1$ での接線となる)
すると，ベズーの定理より，全次数3のEと全次数1の直線は， $nm=3$ 個の点，すなわち， $P_1,P_2$ 以外にもう一点，直線と曲線が交わる点が存在します．この点と単位元Oを結ぶ直線も，[tex;E]ともう一点で交わります．この点を， $P_1+P_2$ と定めています．
このように定めると，座標の足し算は成立し，Oは単位元なので $P+O=P$ とならなければなりませんが，これが成立することも図を描けば誰でも容易に確認できます．なお，このOの存在性は有理数体上では難しいらしいのですが，暗号で扱う有限体上では必ず存在するそうです．ありがたい！
そして暗号理論では特に， $P_1 = P_2$ を利用しています．この時， $P_1 + P_2 = P_1 + P_1 = 2P_1$ の倍々算が可能となり，暗号計算の高速化が実現されます．
この倍算については以下でちらっと登場します．

※全次数 :: 方程式を構成する多項式中の単項式のうち，すべての変数の次数の和の最大値

暗号化と復号

今，
送信元の秘密鍵 ... a
送信先の秘密鍵...b
送信先の公開鍵 ... 楕円座標，計算の開始点（ベースポイント）P，B(=bP)
に関する情報が送信元に与えられたとします．

送信元

送信元は，メッセージ $M$ を公開鍵を使って暗号化されたメッセージ $M' = M+aB = M+abP$ を生成し，送信先に， $(M', A(=aP))$ を送信します．

送信先

$(M',A$ を受信した送信先は，自分の持っている秘密鍵を使って，
$bA = abP$ を得ます．これによってメッセージ $M_{rec}$ を
$M_{rec} = M' - bA = (M+abP) - abP = M$
として復元できるのです．

倍算による高速演算

上記，暗号復号で登場した， $aP$ や $bP$ の演算は，単純に実施するとa回の演算が必要となってしまいます．ここで，aをバイナリ展開し，
$aP = \Sigma_{i=0} a_i2^i(2^iP)$ とすることで，計算量を $\log 2 a$ に抑えることができます．
また，バイナリ展開では除算が多数必要となりますが，これを1回で済ませる手法として，射影座標を用いる加算方法も存在します．詳細は割愛しますが，これまで考えてきたアフィン座標を射影座標での形に換算する方法です．私もまだ理解し終えていないので，資料を当たってください．

実装

以上を実装していきます．
ソースコードはこちらに掲載していますので，一部のみ説明します．
なお，型の設計を頑張ったものの，全然スマートでないと思うのでご意見あればよろしくお願いします．

instance Num ResidueRingInteger where
    a + b = if getn a == getn b then ResidueRingInteger ((getv a+getv b) `mod` getn a) (getn a) else undefined
    a - b = if getn a == getn b then ResidueRingInteger ((getv a-getv b) `mod` getn a) (getn a) else undefined
    a * b = if getn a == getn b then ResidueRingInteger ((getv a*getv b) `mod` getn a) (getn a) else undefined
    negate a = ResidueRingInteger ((getn a)-(getv a)) (getn a)
    abs a = ResidueRingInteger (getv a `mod` getn a) (getn a)
    fromInteger v = undefined

instance Fractional ResidueRingInteger where
	a / b = ResidueRingInteger ((getv a * (getv $ revSrc b)) `mod` getn a) (getn a)
	recip = undefined
	fromRational = undefined

ここでは，剰余還上での演算ということで，加法・乗法が定義できます．また，逆元を有するために除算も定義可能です．
値は，自分自身の値と，その剰余系での法を情報としてもつと考え，ResidueRingInteger型を用意，これについて四則演算を定義しなおしています．
fromIntegerも，fromInteger p = ResidueRingInteger 0 p　として定義しても良いかもしれませんが，混乱を生みそうなので非実装としました．（このおかげで開発中，バグを回避できた）

つづいて，楕円曲線E上での暗号ですので，暗号系は，楕円と座標に関する情報を有します．

data ECCrypto = ECCrypto{x :: ResidueRingInteger, y :: ResidueRingInteger, curve :: ECurve} deriving Eq

暗号・復号に必要な加算を実装します．
今気づいたけど，めっちゃスペース入ってますね...いつもと違う環境で書いたから..

(+++) :: ECCrypto -> ECCrypto -> ECCrypto
a +++ b = a{x = x3, y = -lambda*x3 - nu} where
			x3 = if a == b
				then lambda*lambda-multi 2 (x a)
				else lambda * lambda -(x a) - (x b)
			lambda = if a == b
				then (multi 3 (x a)*(x a) + (get1 $ curve a) ) / (multi 2 (y a))
				else ((y b)-(y a)) /((x b)-(x a))
			nu = (y a) - lambda * (x a)

そして，二審展開による加法演算を実装します．

multiplyOnEC :: ECCrypto -> Integer -> ECCrypto
multiplyOnEC ec = fromJust.snd.foldl multiplyOnEC' (ec, Nothing).toBin where
	multiplyOnEC' :: (ECCrypto, Maybe ECCrypto) -> Integer -> (ECCrypto, Maybe ECCrypto)
	multiplyOnEC' (nP,result) 0 = (nP+++nP, result)
	multiplyOnEC' (nP,Nothing) 1 = (nP+++nP, Just nP)
	multiplyOnEC' (nP,Just result) 1 = (nP+++nP, Just $ result +++ nP)

最後に，暗号・復号を書き下します．

encrypto :: PublicKey -> Rank -> SecretKey -> [Integer] -> (ECCrypto, [Integer])
encrypto (_P,bP) rank secretkey message = (aP, map encrypto' message) where
	encrypto' = flip mod rank.( + (getv $ x abP))
	aP = multiplyOnEC _P secretkey
	abP = multiplyOnEC bP secretkey

decrypto :: (ECCrypto, [Integer]) -> Rank -> [Integer]
decrypto (aP, message) rank = map decrypto' message where
	decrypto' m = (m - (getv $ x abP)) `mod` rank
	abP = multiplyOnEC aP secretkey_b

非常に素直ですね．
参考にした書籍にあった関数と例題で，正常に動作することを確認しました．
ただ，素位数=41の巡回群でのサンプルなので，[0-41]の範囲しか扱えません．
参考資料3では，もっと大きい素数たちが使用されていますので参考にしてください．

攻撃

楕円曲線暗号の解読には完全指数時間要しますが，利用されている楕円曲線上離散対数の乗法巡回群（すなわち拡大体上の離散対数）へ変換して解読する手法があるようです．(MOV攻撃，FR攻撃)
ヴェイユペアリングがよく用いられるようですが，書籍によると超特異曲線でなければこの攻撃は回避でき，埋め込み次数を高くすればよいとのことです．

※埋め込み次数 :: 有限体を拡大する時に必要となる最小の拡大次数

また，暗号の本を読んでいてグレブナ基底が出てくるとは思っていませんでした．
量子コンピュータが実現されれば既存の暗号の多くは破られる見込みですが，これに対抗する暗号として期待されているのが多変数公開鍵暗号です．ただこの暗号についても，グレブナ基底を使って順繰りに多項式を正規化していく解読手法があります．複雑な多項式の構成方法や多項式の複雑さの評価などまだまだ調査不足ですので，既存のフレームワークで量子計算に耐えうるってめちゃめちゃ格好良くないですか？また取り組んでみたいと思います．

参考文献

1. 暗号理論と楕円曲線数学的土壌の上に花開く暗号技術 | 森北出版株式会社
2. Theory and Implementation of Eliptic Curve Cryptography
3. 楕円エルガマル暗号の実装

wvogel日記

自分用の技術備忘録が多めです．

楕円曲線暗号（EC Elgamal）を実装する

楕円曲線上の加算

暗号化と復号

送信元

送信先

倍算による高速演算

実装

攻撃

参考文献