移動式のブログ

ガジェット、アニメ、プログラミング、考えたことその他色々・・・特にこれといったテーマはないカオスなブログです。

楕円曲線など

楕円曲線とは

参考はこちら
www.atmarkit.co.jp


楕円曲線の考え方をゲームで例えると以下のようになる。

画面の右端に突入したら画面の左端からキャラクターが出てくるゲームを想像してみればわかりやすい。
例えば、マリオブラザースなど、のゲームで、画面の左端と右端が繋がっていて、右側に突き抜けると左側から、左側に突き抜けると左側から出てくるあのイメージだ。
f:id:idoushiki:20180408193932p:plain

まず、このゲームのフィールドは、6歩分の横幅があるとする。
キャラクターが1歩でp進めるとした場合、左端から3歩進んでも9歩進んでも「3」の位置にいるだろう。
そのため、キャラクターが「3」の位置にいることがわかっていても、何歩進んだのかを知ることができない。
なぜなら、左端から3歩、9歩、15歩、21歩、27歩と、「3」の位置にたどり着く歩数は無限にあるからだ。
f:id:idoushiki:20180408214716p:plain
現在位置をKとして、何歩進んだかがaで1歩につきいくつ進めるかがp、フィールドの幅がhだとすると、K=pa mod hとなる。

楕円曲線鍵共有

AさんとBさんがいた場合、

まずはPを決める
まずは、pを決めておく。

Aさんの鍵を決める
Aさんにしかわからない値のaを決めて、それを秘密鍵として持っておけば、Ka(pa mod h)を公開鍵として相手に公開することができる。
さっきの例のように、a(何歩進んだか)を確実に知ることはできないので、(キャラクターの立っている現在位置)Ka(pa mod h)を鍵として公開することができるからだ。

Bさんの鍵を決める
Bさんにしかわからない値のbを決めて、それを秘密鍵とする。そして、Kb(pb mod h)を公開する。このbもさっきのゲームの例のようなイメージで。


AさんのKa鍵とBさんの鍵Kb交換した後、共通鍵を作る


最後に、AさんはBさんの公開鍵Kb(bp mod h)とaでkba、
BさんはAさんの公開鍵Ka(pa mod h)とbでkabを作成する。

以上により、お互いの秘密鍵を知ることなく、お互いが同じ共通鍵、Kab(Kba)を作成することができる。

この方法によりKab=Kbaとなって、お互い自分自身の秘密鍵が相手やその他の人に知られることなく、AさんとBさんはAさんとBさんの二人だけの秘密の鍵をKab(Kba)共有することができる。


f:id:idoushiki:20180409002350p:plain
a=21,b=11,p=1,h=6の時、以上の図のように、Ka=3,Kb=5となり、共通鍵3が生成される。
そして、BさんはAさんから受け取った鍵Kaを、自分の持っている鍵bで複合する。
Kab mod h

AさんはBさんから受け取った鍵Kbを、自分の持っている鍵aで複合する。
Kba mod h

その結果、生成される共通鍵はKab mod h=Kba mod hとなる。





楕円ElGamal暗号

Aさんは値Pを決定してそれを公開する。
Aさんは秘密鍵aをランダムに決めて、公開鍵K=apを作る。

暗号化するには
rをランダムに決めて、平文mを暗号化する。
暗号文は、rpとm+rKの二つの値となる。


復号のやり方は、rK+m-arpとなる。


m=13 a=3 p=5 r=4
K=3・5=15
rp=4・5=20
m+rK=13+(4・15)=73

暗号文は20,73となる

復号のやり方は、rK+m-arpより、73-(3・20)=13となり、復号できる。