背景
楕円曲線暗号ついて理解したことを自分の言葉で整理しておきたい。
opensslを使いこなせるようになっておきたい。
※セキュリティの一般的な知識で、当たり前のことを改めて残しているだけです。
参考文献
参考文献1：
暗号技術入門 秘密の国のアリス
参考文献2：
暗号強度要件(アルゴリズム及び鍵長選択)に関する設定基準
参考文献3：
クラウドを支えるこれからの暗号技術
楕円曲線暗号とは
・楕円曲線暗号（Eliptic Curve Cryptography : ECC）
・楕円曲線と呼ばれる曲線を使った暗号技術（楕円曲線を用いた公開鍵暗号/デジタル署名/鍵交換）全般のこと
楕円曲線暗号の特徴
公開鍵暗号の中でも、短い鍵でも強い。
参考文献2の「表 2 公開鍵暗号の推定セキュリティ強度」には、セキュリティ強度毎のアルゴリズムで必要な鍵長が記載されている。
例えば以下の方程式で表される曲線になる。
y^2 = ax^3 + bx^2 + cx + d
楕円曲線上の演算
「楕円曲線上の加算」：加算対象の点Aと点Bを通る直線と、楕円曲線との交点をx軸に関して対称の位置に移動した点
「楕円曲線上の二倍算」：点Aで接する直線と楕円曲線の交点をx軸に関して対称の位置に移動した点
「楕円曲線上の符号反転演算」：点Aをx軸に関して対称の位置に移動した点
楕円曲線上にある点同士に対して、「演算」を定義し、その「演算」を使って暗号技術に必要な計算を行う。
点が与えられているとき、「数xから点xGを求める問題」は難しくないが、
逆に「点xGから数xを求める問題」は非常に難しい。
この問題が楕円曲線暗号で使う「楕円曲線上の離散対数問題」である。
例
y^2 = x^3 + x + 1
実数体R上で楕円曲線を考えると以下のようにグラフになります。
一方、楕円曲線暗号では有限体上で楕円曲線を考えるらしい。
※有限体：体の中でも要素の数が有限個しかないもののこと
あるpという素数を決め、0,1...p-1というp個からなる整数の集合に対して加減乗除の演算を定義したもの。
同じ楕円曲線を有限体（p=23）で考えるときには以下のようになる。
y^2 ≡ x^3 + x + 1 (mod 23)
※左辺と右辺の計算結果を「23で割った余り」が等しい。（23を法として合同）
これをグラフ上に表すと以下のようになる。
楕円曲線上の「演算」を使って2G、3G...を求めると以下のようになる。
ここで、「楕円曲線上の離散対数問題」というのは、GとxGからxを求めること。
つまり、点G=（0,1）, 点14G=(4,0)から、14を求めることが難しいということです。
ここまでは参考文献1の内容だが、
有限体のグラフ上でxを求めることのむずかしさがイマイチ理解できない。。
参考文献2で理解した内容を以下から記載する。
RPGの世界地図を例に説明されているが、ゲームの世界地図は実は浮き輪型になっていて、トーラス（ドーナツ型）の世界と呼ぶらしい。
（FF8で、召喚獣のエデンを手にいれるためにマップを行き来した覚えがある。。）
n倍の計算はべき乗の計算と同様にバイナリ法を使い、効率よく求められる。
FF8でいうと、
スコールの一歩がPだとすると、最初のバラムガーデンから、10^100歩歩いた場所は容易に計算できるが、
現在地と自分の一歩から、スコールが何歩歩いたか計算するのは難しい。
ということらしい。
楕円曲線DSA（ECDSA）
アリス→ボブ間で、署名生成、署名検証を実施する例：
送信（アリス）側：
(1) アリスは乱数rとベースポイントGから点rG=(x,y)を求める。
(2) アリスは、乱数rと、メッセージmのハッシュ値h、プライベート鍵aから、s= h+ax / r を計算する。
(3) 最後にアリスは、ボブにメッセージmと、点rG = (x, y)と、sを送る。
点rG と s がデジタル署名となる。
受信（ボブ）側：
(4) ボブは、メッセージmと、点rG = (x,y) と、sを受け取る
(5) ボブは、メッセージmからハッシュ値hを求める
(6) ボブはアリスの公開鍵aGを使って、
( h / s ) * G + ( x / s ) * aG
を計算し、rGと比較する。
→比較結果が一致すれば、署名検証OK！
openssl ecdsa 署名検証
参考にしたサイト
opensslマニュアル(ecparam)
opensslマニュアル(ec)
shota@ ecdsa % openssl ecparam -genkey -name prime239v2 -out key-pair.pem
shota@ ecdsa % openssl ec -in key-pair.pem -pubout -out public.pem
read EC key
writing EC key
shota@ ecdsa % openssl ec -in key-pair.pem -out private.pem
read EC key
writing EC key
shota@ ecdsa % cat public.pem
-----BEGIN PUBLIC KEY-----
MFUwEwYHKoZIzj0CAQYIKoZIzj0DAQUDPgAEaPFHM2VZPWEoX7JmckNYfp7/gEma
F3ZeJzd8DqUjXiv+tszDsyFYEYnOKR5oKsnDHLmEjHLqWTgA1eJR
-----END PUBLIC KEY-----
shota@ ecdsa % cat private.pem
-----BEGIN EC PRIVATE KEY-----
MHECAQEEHiQSDWPdEsByKSJX02sJ8g46+gnpOYR2pWa/R1yE2qAKBggqhkjOPQMB
BaFAAz4ABGjxRzNlWT1hKF+yZnJDWH6e/4BJmhd2Xic3fA6lI14r/rbMw7MhWBGJ
zikeaCrJwxy5hIxy6lk4ANXiUQ==
-----END EC PRIVATE KEY-----
shota@ ecdsa % openssl dgst -sha1 -sign private.pem plain.txt > signature.dat
shota@ ecdsa % cat signature.dat
0?G????ڤE(M????j?𛂠??>???#I?W??NL?n)?ӴI??C??j?????'%
shota@ ecdsa % hexdump signature.dat
0000000 3f30 1e02 b11b bd47 b297 da87 45a4 4d28
0000010 fe00 fe1f 99f9 c36a 9bf0 a082 e883 9c3e
0000020 d6ad 1d02 4923 57cd e8f1 4c4e 6ee6 c029
0000030 b4d3 d549 43ef c1e5 ee6a dfcc ce08 edf1
0000040 0027
0000041
shota@ ecdsa % openssl dgst -sha1 -verify public.pem -signature signature.dat plain.txt
Verified OK