かけ算仲間の逆は、難しい！
このページはマス旅の一部です。
共通鍵暗号（DES、AESなど）は「かきまぜを戻すのが難しいこと」が暗号の根拠でした。
公開鍵暗号（RSAなど）は「かけ算の逆」としての「素因数分解の難しさ」が暗号の根拠でした。
「かけ算自体を拡張すること」で、難しさのバリエーションを増やそうというのが今回のテーマです。
１．ウォーミングアップ
かけ算の逆と言えば、ふつうは割り算ですね。
かんたんな割り算にしても、子どもの頃一番苦労するのが割り算のやり方です。
大人になると、今度は商体、商空間、正規部分群、微分係数、微分方程式。。。
もとはと言えば、対象が広がっただけで、
みな「割り算仲間」です。
数学や暗号学的な定義はともかく、
「行きはよいよい帰りは怖い」
これが、かけ算の逆戻しの本質だと思います。
RSA暗号で学んだように、私たちは掛け算の計算（順方向）は一瞬でできても、
素因数分解という「掛け算する前の元（素数）にたどり着く（逆方向）」探索が
途方もなく困難であることを利用していました。
＜離散対数問題＞
「かけ算の逆戻し」が難しいならば、「かけ算を拡張」してみよう。
そうすると、「逆戻しの難しさ」も拡張できるでしょう。
さて、同じ数のかけ算を繰り返すことが「指数表現」でした。
これも立派な「かけ算仲間」です。
これの逆は「対数」ですね。
さらに、ただ掛け算を繰り返すだけでなく「剰余（mod）をとる」という制限を加えます。
すると、その逆算は「余り付きの対数問題」、すなわち整数論における「離散対数問題」へと進化します。この離散対数問題の難しさを利用したのが、
「ディフィ・ヘルマンの鍵交換」や「エルガマル暗号」といった公開鍵暗号です。
また、「かけ算の拡張」といえば、「楕円曲線でのｎ倍」がありますね。
無限遠点を付け加えた y^2 = (xの3次式) の形の方程式である楕円曲線上では、不思議な「点の足し算」が定義できました。点の足し算ができるなら、同じ点をn回足す「点のn倍（かけ算）」も定義できます。
「出発点の点 P」を n回足して「到着点Q」を求めるのは簡単（順方向）ですが、「点 Pと 点Q」だけを見せられて「何回足したか（nはいくつか？）」を当てる（逆方向）のは、まさに途方もない難しさになります。これが「楕円曲線上の離散対数問題」であり、現代暗号の最高峰「楕円曲線暗号（ECC）」の基盤です。
従来のRSAやエルガマル暗号では2048ビットもの巨大な鍵が必要だったのに対し、楕円曲線暗号ではたった256ビットで同等以上の安全性を実現できるようになりました。
この「逆戻しの途方なさ」は単なる数学者のロマンではありません。
現代のスマートフォンやSSL/TLS通信、
ブロックチェーンなどを陰で支える現実の技術なのです。
２．エルガマル暗号
＜ディフィ・ヘルマン暗号＞
ディフィとヘルマンは絵描きさんのような発想で暗号を作りました。
絵をかく絵具の色はだれでも同じものが手に入ります。公開されています。
その混ぜ具合が絶妙であれば、その人しか出せない色というものが可能です。
それを数値で考えるのです。
公開されたものをまぜるだけで秘密の色合いが出せるのです。
そんなイメージの暗号がディフィ・ヘルマンの鍵交換です。
公開された値gがあります。
Aさんが秘密の値aを、Bさんが秘密の値bを選びます。
次にAはA=g^aを公開、BさんはB＝g^bを公開します。
それぞれ、相手の公開値を自分の秘密値乗します。
Aは（B)^a=(g^b)^a=g^baになり、Bは(A)^b=(g^a)^b=g^abとなります。
この値Uは等しくなりますね。
U=g^ba=g^ab
Uを共有鍵として共通鍵暗号を使って秘密の通信ができるのです。
しかし、g^a,g^bのもとになる「かけ算の定義」が2人で共通していなければ、
計算結果の意味も不明で、g^ab=g^baになる保証もありません。
また、「かけ算の定義」が通常のもであれば、A=g^aのAもgも公開されているので
対数計算でaが逆算できてしまいますね。暗号になりません。
そこで、「かけ算の定義」に剰余をからめたものを共有します。
ｘ＊y＝(x×y) mod pとすれば、指数計算a^x=bを逆算をしてx=log_a bを求める問題、
「離散対数（discrete logarithm)問題」が
暗号攻撃者の前に立ちふさがります。
このような手法を、ディフィ・ヘルマンの鍵交換（配送）と言われます。
公開情報を交換しただけ秘密情報を共有できるなんて面白いですね。
＜エルガマル暗号＞
エルガマル暗号は、ディフィ・ヘルマンの鍵交換（配送）の仕組みに「使い捨ての秘密鍵」をからめます。
AさんとBさんがそれぞれ公開情報A,Bを作るところまではいっしょです。
B（送信者）は
・「使い捨ての秘密鍵ｒ」で使い捨ての公開情報R＝g^rを作る。
・V=（A)^r＝g^arを鍵にして平文Mにかける。C=MV。
・暗号文（R,C）のペアをAに送る。
A（受信者）は秘密鍵aで復号する。
・U=R^a=g^ra=g^ar=Vを求める。
このVとC＝MVから、Mがわかる。
面白いのは、使い捨ての秘密鍵rのことはAにはまったくわかりませんが、
公開情報Rにその作用が入っているため、自分の秘密鍵aだけで、
Bの作った鍵Vと同じ鍵Uが作れるわけです。
共通の秘密鍵ができたということですね。
暗号攻撃をする側からすると、rが確率的な鍵であれば、
同じ平文Mの暗号Cがころころ変わるということになり強い秘匿性が生まれますね。
３．楕円曲線暗号（ECC)
ミラーとコブリッツは楕円曲線EC（Elliptic Curve）のかけ算を、
離散対数問題が難しい「かけ算」として暗号に使えることを発見しました。
楕円曲線で作る暗号を楕円曲線暗号といいますが、エルガマル暗号も実現できます。
楕円曲線上での計算を思い出すと、２点ｘ、ｙを通る線が自分と交わる点のｘ軸対称点ｚ＝ｘ＋ｙの点でした。
無限遠点Oがゼロ元で、対称点は逆元を表します。
3点の和は結合の順番によらず同じ点にいきつくのでした。
そんなわけで、楕円曲線上の点のたし算が作る点集合はアーベル加群と同型になるのでしたね。
くわしくはこちら（楕円曲線上の加算）
さらに、2点ｘ、ｙを通る線のｘとｙが同一ならば、点ｘにおける接線となるから、
接線の交点の対称点ｚが2x＝ｚとなる。こうして、ｎR＝O（無限遠点）となるｎを見つけることで、
Rが生成元のｎ次の巡回群と同型になる点群を見つけることがきたね。
くわしくはこちら（[楕円曲線上のスカラー倍）
＜楕円曲線離散対数問題 (ECDLP)＞
楕円曲線暗号の安全性に基盤になるのが「楕円曲線離散対数問題」だ。
これは、
３より大きい素数に対して、有限体F_p上の楕円曲線E:y^2=x^3+ax+bを考える。
素数位数rの楕円曲線の点 S=(x_S, y_S)を固定し、Sを生成元とする点群のうちの点T=(x_T, y_T)でT=dSを満たす整数dを見つけることだ。
整数dから楕円曲線の点T=dSは(約log(r))回の楕円曲線で演算を行えばかけ算の点Tはきまるけれど、
dを逆算するには、素数Pの大きさを 160 ビット程度に選ぶと、
スーパーコンピューターレベルで効率アルゴリズムを使っても、現実的な時間内に解答不能だという。
効率的と言われるρ法でECDLPに攻撃をしかけたとしても、160ビット〜256ビット程度の適切な群サイズを突破するのに約1.3×10^23(年）かかるそうだ。
＜楕円曲線暗号（ECC)の実装としくみ＞
有限体F_p上の楕円曲線f(x,y):y^2=x^3+ax+bの
有理点の集合E(F_p)＝{(x,y)in F_p^2|f(x,y)}∪{O}で、単位元はO=(∞,∞)
ただし、a,bは4a^3+27b^2 mod p ≠0とする。
#PとQの和（P＝Qの場合は2P)の定義は、
P(x_1,y_1),Q(x_2,y_2)に対して、
λ=if(P=Q, {3(x_1)^2+a}/(2*y_1), (y_2-y_1)/(x_2-x_1))とするとき、
R=P+Q＝(x_3,y_3)で、
x_3=λ^2-(x_1+x_2)
y_3=λ(x_1-x_3)-y_1
で求められる。
これで、点加算と点2倍算ができるね。
#また、集合E(F_p)の個数size=#E(F_p)はハッセの定理から
p+1-2√p以上p+1+2√p以下だ。
暗号を作るにはsize=fN(Nが大きな素数、fが小さな整数）と分解する。
#点のスカラー倍の計算では、RSA暗号のべき剰余演算で使うバイナリー法やラダー法のような、
繰り返し演算が必要になる。
この中に点加算と点2倍算を埋め込むことでスカラー倍の計算は実現できるね。
#また、座標計算をするときには、アフィン座標のままやるか、
無限遠点を軸として追加した射影座標系でやるかという選択が必要になる。
#そして、計算の高速化のためには「2進数展開」が必要になり、剰余計算では「pを法とする平方根」を求める関数も用意しなければいけません。
#当然ですが、メッセージの数値m(整数）を楕円曲線上の点Mに変換する必要があります。
mとMの相互変換の関数も用意しなければなりませんね。
＜ECC（楕円曲線エルガマル暗号）の使い方＞
集合E(F_p)の個数size=#E(F_p)。生成元はGです。
E, Gをユーザ全体で共有します。楕円曲線暗号では1個の曲線をシステムパラメータとして多くユーザが共有可能です。SECG (http://www.secg.org/)などから安全なおすすめ曲線が入手できます。
ECCの具体的手順は、さっきのエルガマル暗号と同様です。
#鍵の生成
{0, 1, 2, …, size-1} から選んだ秘密鍵sに対して、Q=sGを公開鍵とします。
#暗号化
楕円曲線 (a, b, p) 上の点 M （平文）がある。
G, 乱数r(0以上size-1以下), 公開鍵Qを利用して、暗号化 します。
C1 = rG,
C2 = rQ + Mを行い(C1,C2) を暗号文として送ります。
#復号化
暗号文(C1,C2) を得た人は、秘密鍵sで復号できます。
C2 - sC1
= (rQ + M) - s(rG)
= (r(sG) + M) - rsG
= M
（※ -sC1は、y座標の符号を反転させた点sC1の逆元を足し合わせる操作です。
C1の対称点にsをかけた点とC2を加算した点がMだね。
素晴らしい。自分の秘密鍵sだけで復号できました。
４．振り返り
曲線と数の対応がまだピンと来ないかもしれませんが、
数のかけ算をする代わりに、
コンピュータの中で「楕円曲線」という多様体の点の座標操作と群の演算が動いてくれているのです。
暗号のユーザーは、
裏でどんな高度な代数幾何学が動いているのかをまったく意識しなくても、安全な通信を享受できます。
それはまるで、私たちが毎日歩いている道路の下に水道・ガス・地下鉄の管が張り巡らされ、
日常の平和と安全を静かに支えてくれているのと同じ感覚ですね。
課題：楕円曲線上の点のスカラー倍をgeogebraで視覚化する。
タイトルは「楕円曲線 y^2 = x^3 + 1上の点のスカラー倍」
#楕円曲線E
E: y^2 = x^3 + 1
#生成元R
R=(2,3)
#スカラーdは秘密鍵でアニメーション
d=Slider(1,6,1)
#無限遠点は表示のため(10,10)とする。
O=(10,10)
Rs={(2,3),(0,-1),(-1,0),(0,1),(2,-3),O}
#暗号Xの色は赤
X=Element(Rs,d)
#スカラー倍の結果を文字で表示する太字でサイズを大きくする。
text0="生成元R="+ R
text1="X="d+"R="+dR
#メッセージ
text2="RとXだけから、秘密鍵dを当てられますか?"