Wait a moment...

【数学】鍵が印鑑になった

nem315xem (12)
703
8
2019-09-04 19:54:53
【数学】鍵が印鑑になった


前回は、暗号の記事を書きました。秘密鍵公開鍵という二種類のカギ(=大きな数字)を使うことで、
第三者に見られたくないメッセージを、ワケのわからない数字に変えてしまう、これが暗号化でしたね。

この種類の鍵を使うと、暗号化とは全く別の用途である、「電子データへの署名」を行うことができます。
今回は、これをご紹介します。


※暗号技術 初学者の人間が書いておりますので、不正確な記述があるかもしれません。
あくまで参考程度に!



 

しょ-めい【署名】 とは




何か紙に書かれた文書があったとき、それに自分の名前を書き込むことを署名と言いますよね。

例えば、何かしらの 契約書 に署名をすれば、署名した人は、その契約内容に同意したことになります。

署名された契約書を受け取った人は、「あぁ、これは、あの人の字だな」と言って、
その文書が、確かに本人によって署名されたことを確認します。誰の字か見分けがつかない場合は、
筆跡鑑定をすれば、確認が取れますね。筆跡だけで本人確認するのが不安なら、名前の隣に印鑑
押してやれば、さらに確実になります。


加えて、紙に書かれた文書は、改ざんするのがとても大変。消しゴムで消せないように、文字はインクで
書かれてるでしょうし、修正液なんか使ったら一発でバレます。


だから紙の文書における「署名」て、

①確かに、本人が名前を書いたものだと確認できる

②改ざんされづらい


という二つの長所があるんですよね。紙って優秀。



では、これを紙ではなく、電子データ上で行うとなると、どうでしょう? 

契約書を紙ではなく、pdf ファイルで作成して、それをメールでやり取りすれば、ペーパーレスを実現できますね。


でも。。


自分の名前をキーボードで打ち込むことで、電子データ上に名前を記入できますが、それでは本人の筆跡の
「クセ」が現れませんから、文書を受け取った人は、それが本当に本人が署名したものなのか、確認できません

電子データ上だと `修正液の跡'なんて残りませんから、改ざんも簡単です。






紙と違って、電子データへの「署名」て難しそう。




ところが!




秘密鍵公開鍵を使うことで、電子データへの署名(=電子署名)を成立させることができます。


つまり、データを受けとった人が、

① 確かに本人が署名したこと
② 送信の過程で、第三者によって改ざんされていないこと


を確かめることができるんです。


基本的な考え方としては、秘密鍵を使って、「その秘密鍵の所有者にしか作れない印鑑」を作り出し、
それをデータに押すことで、本人確認ができるようにしよう、というものです。


詳しく見ていきましょう。



ちょっと復習



 

前回と同様、「エルガマル暗号」と呼ばれる暗号を簡略化したものを例にとって、電子署名の原理を
見てみましょう。


ちょっとだけ復習してみます。A~Dさんからなる四人グループがあったとき、秘密鍵というのは、
一人一人に発行される秘密の数字のことでした。自分以外の誰にも知られてはいけません。





次に、ある数字をみんなで予め決めておきます。ここでは簡単のため、としておきましょう。
四人は、「の(自分の秘密鍵の数字)乗」を計算して、みんなに公開します。





公開する数字のことを、公開鍵と呼びました。ここまでは前回と一緒です。




「ハッシュ」って何ですか? ⇒ 名前の通りです!




今回は、「ハッシュ値(はっしゅち)」というのを使います。

「ハッシュ」は、英語で『ごたまぜ』とか、『めちゃくちゃ』という意味があります。


ハッシュ値というのは、文字列を、

ものすごーーーーーーーーーーーーーーーーーーーーーーーーーーーく


複雑な方法で、数字に変換した値のことです。


百聞は一見にしかず。こちらのサイトで簡単に具体例を確かめることができますよ。

「ここでSHA256ハッシュしたいテキストを貼り付けます」と書かれた欄に、好きな文字を打って、



青色の「SHA256ハッシュを生成!」ボタンを押すと、



というふうに、B860CD2907B..... という数字が出てきます。A~F のアルファベットが入ってて数字っぽく
ないですが、これは16進法を採用しているため。れっきとした数字です。


『ねむろぐ』という文字列が、ものすごーーーーーーーーーーーーく複雑な方法によって、

『B860CD2907B289DA3E6AAB88BE162EF6BA3048DA12E88E331B21C4FD7E8F75AA』

というハッシュ値に変換されました。



『ねむろぐ』を『ねむぐ』とちょっと変えて、ハッシュ値を出してみましょう。



ねむろぐ → B860CD2907B289DA3E6AAB88BE162EF6BA3048DA12E88E331B21C4FD7E8F75AA

ねむるぐ → 25E215514A8472D7B10E7966193C87211C97EB5C4078275634A471F93C7B84F5


↑のように、一文字変えただけで、ハッシュ値は全く違うものになってしまいます。
これはハッシュ値の特徴の一つです。



元の文章を、ちょっとでも改ざんしようものなら、とたんに全く違う数字になってしまうハッシュ値。
文書を改ざんしようとする悪い人間からしたら、暴れ馬のように厄介なものになります。


また、ひとたび文章をハッシュ値に変えてしまうと、元の文章を知らない人が、ハッシュ値から元の
文書を逆算するのは不可能です。これもハッシュ値の特徴です。まさに ハッシュ値 = 'めちゃくちゃな' 値。




※ハッシュ値にもいろいろ種類がありますが、今回は「SHA256ハッシュ」という名前のものを例にとります。





電子署名の作法

 

 


Aさん(本名アリス)が電子化された契約書に署名をし、Bさんにそれを確認してもらう状況を考えましょう。

契約書の内容は「百万円あげる アリス」というものだったとしましょう。この文章のハッシュ値を計算すると、


BED6D6F88198374AF8F243F075B4AE1371819ACA9293BFE4E9BD410424925664

となります。

が、こんなに大きな数字を扱うのは嫌なので、この記事内では、簡単のため、ハッシュ値が 2039 という数字
だったとしちゃいます。(16進法も面倒なので、10進法で 2039だったとします。)


Step1. Aさんは、乱数(ここでは簡単のため、4 としておく)を一つ選んで、次の ①, ② を計算する:

① みんなで決めた数字 34乗: 3^4 = 81.
② (ハッシュ値 2039 ) から (Aさんの秘密鍵 19)× (①の数字 81) を引き、
 更に乱数 4 で割る: (2039 - 19 × 81)÷ 4 = 125.



 


秘密鍵と乱数を使って、二つの数字 81, 125 ができました。この二つの数字のペアが、印鑑の役割を果たします。


Step2. 二つの数字 ①, ② を電子データに貼り付け、Bさんに送る。






今回は  暗号化  の場合と違って、文書は第三者に見られてもよいものを想定しています。
あくまで、「文書を改ざんされないようにする」のが目的。

なので、上図のように、文書の内容は剥き出しでそのまま送っちゃいます。



※)簡単のため、3, 4, 19 といった小さい数字を使っていますが、本来はもっともっと巨大な数字を使います。
万が一、この送信を悪いやつにハッキングされて二つの数字①, ②が覗かれてしまっても、
巨大な数字の計算の難しさ」のおかげで、Aさんの秘密鍵の数字 (今の設定では 19) は逆算されない
ようになっています。



Step3. 二つの数字①,② が貼り付けられた電子文書を受け取ったBさんは、次の二つの数字(I), (II) を計算する。

(I) 3^{ハッシュ値 2039}を計算
(II) 受け取った数字 ①, ② を使って、(Aさんの公開鍵)^{①} × ①^{②}を計算

先ほども言いましたが、文書の内容(「百万円あげる アリス」)は剥き出しのままなので、
受け取ったBさんは さっきの「ハッシュ値計算サイト」にアクセスして、「百万円あげる アリス」と
打ち込むことで、ハッシュ値 2039 を計算できるわけですね。 なので、Bさんは (I) を計算できます。

また、Aさんの公開鍵 はみんなに公開されていて、誰でも見られるようになっているのでした。
①、②の数字は送られてきた文書に貼り付けられているので、Bさんは(II)も計算できます。





トリックは次の項目でご紹介しますが、なんと、

・ Aさんがきちんと自分自身の秘密鍵19を使って印鑑(81,125)を作り、

・なおかつ文書が第三者によって改ざんされていないのみ


(I)=(II)

という等式が成立するようになっているんです(上図でも(I)=(II)となっている)。

秘密鍵19 を使って印鑑を作ることができるのは、19という数字を知っているAさんただ一人。
なので、 (I)=(II)が成り立つということは、Aさん本人が署名したことの証明になります。

(I)=(II)が成り立つことを確かめることで、「Aさん本人が文書に署名したこと」、
そして、「文書が改ざんされていないこと」を同時に確認する。これを「検証」(verify) と言います。



※厳密にいうと、秘密鍵が正しくなかったり、改ざんがなされていたとしても、
(I)=(II)が成り立つことはあるんですが、それはとてもとても低い確率で、ほぼ
起こらないと考えてよいということです。

 



(I)=(II)のからくり




前回も扱った指数法則を使います。まず、Aさんの公開鍵というのは、みんなで決めた数字 3
Aさんの秘密鍵 19 を使って、3^{19} と作られていたことを思い出しましょう。

 


次に、Bさんが受け取った数字 ① は、乱数 4 を使って、3^4 と作られていて、
数字 ② は、

(ハッシュ値 2039 - Aさんの秘密鍵 19 × ①) ÷ = (2039 - 19 × 3^4) ÷ 4


と作られていました。




さて、ここで指数法則を使います。これは、下のような等式のことでした(詳しくは前回の記事で):




これを使うと、




となり、後半の 3 の指数は、4 × (    ) ÷ 4 という形をしているので、4 がキャンセルされて



と、計算されます。最後にもう一回 指数法則




を使うと



となって、(I)と一致するわけですね。


こんなふうに、Step.1 で、しっかり秘密鍵 19 を使って数字②が計算されており、なおかつ文書も改ざんされていなければ

(I)=(II)

となるのです。万が一、秘密鍵19 以外の数字 (例えば 18) を使って数字②が計算されていると、


と、途中式が変わってしまいます。すると、

当然、計算結果も変わってしまうワケですね。なので、Aさん以外の人がAさんに なりすまして、
テキトーな秘密鍵を使って印鑑を作ると、(II)の計算結果が変わってしまい、(I)=(II)が
成り立たなくなってしまうんです。


また、文書が改ざんされてしまうと、ハッシュ値 2039 が全く違うものになってしまいます。
(一文字でも文書が変わると、ハッシュ値は全く違うものになってしまうんでしたね)

そのため、本来の(I) = 3^{ハッシュ値 2039} の値も、全く違うものになってしまいます。
なので、改ざんが行われると、今度は (I) の計算結果が変わってしまい、

(I)=(II)が成り立たなくなってしまうのです。










サトシ・ナカモトがやりたかったこと





サトシ・ナカモトの論文によると、ビットコインというのは、電子署名の連続です。

最後にそれについて触れておきます。

※(自分の理解が曖昧なところがあるので、正しくない部分があったらご指摘ください。)

※(原論文では、「この暗号・署名システムを使う!」と特定のものが宣言されているわけではありません。
今回ご紹介しているのは、現実でビットコインで使われている電子署名システムとは異なるものですが、
イメージを掴むのに役立てていただければと思います。)


Aさんが Bさんに コインを送って。受け取ったBさんが、Cさんにコインを送って。Cさんが、Dさんにコインを送って。

こういうやり取りを、電子上で行うとなると、

・不正送金が行われていないか?

というのが心配になります。


そこで、今回の電子署名を考えてみましょう。

電子署名において、文書の送り手に必要だったのは、

(i) 送りたい文書のハッシュ値となる数字、
(ii) 送り手の秘密鍵の数字、

の二つでしたね。今回の例では、この二つの数字(i), (ii)から、印鑑(=数字のペア(81,125))を
作り出しました。


それに従い、BさんがCさんにビットコインを送りたいとき、Bさんは、

(i)「直前の、AさんからBさんへのコインの送金の記録」のハッシュ値と、「Cさんの公開鍵」のハッシュ値
を合体させた数字、
(ii) 送り手であるBさんの秘密鍵の数字、

の二つを使って`印鑑'を作り出します。上で紹介した電子署名の方法の Step1. に従うと、以下のような感じです:






この印鑑をコインに貼り付け、Cさんに送ります。







コインを受け取ったCさんは、印鑑を見て、'検証' を行うことで、「確かにコインがBさんからコインが送られたこと
を確認できます。また、上の例では、「直前の、AさんとBさんの取引」のハッシュ値が使われているため、検証によって、
AさんとBさんの取引が改ざんされていないこと、まで証明されます。



コインを受け取った人が、他の誰かに送金する度に印鑑を押しますので、コインには次から次へと
印鑑が押印された記録が残っていくわけですね。


これで、誰かがBさんに なりすましてCさんにコインを送ったことにする、ということができなくなります


しかし、問題が残ります。


実は、1ビットコインだけを使って、二人の人間に1ビットコインを送金する、ということが、
案外、簡単にできてしまうんだそうです。1Xemだけ消費して、十人に1Xemずつ投げネムするようなもんです。
完璧な不正ですね。こういうのをコインの二重使用と言います。

確かに電子署名は、「Bさん本人がCさんにコインを送った」ことは証明できますが、
「BさんがCさんだけにしかコインを送っていない」ことは証明できないんです。
二重使用は防げない。

サトシ・ナカモトの論文が提案すること。それは、電子署名に加え、
ブロックチェーン」という技術を使うことで、二重使用も防げるようになるんだ、ということです。

今回ご紹介した電子署名の足りない部分をカバーするのが、ブロックチェーンなんですね。







暗号理論を勉強したおかげで、やっと、サトシ・ナカモトの論文のスタートラインに立てた気がします。
いったいどんなふうに二重使用を防ぐのか。わくわくしながら、論文の続きを読み進めてみたいと思います。


ということで今日はここまで!



参考文献
日本語で読むビットコイン原論文
ビットコイン論文徹底解説
ElGamal署名 のWikipedia



Comment
やってみよう
やってみよう
2019-09-13 21:38:20ID:147216

>>サバトラ::さん

お読みいただき、ありがとうございます!
後半は数式が出てきちゃいますね~^^;
前半の「署名と電子署名の違い」だけでも「なるほど」と
思っていただけたら、嬉しいです!

サバトラ
サバトラ
2019-09-13 21:02:48ID:147207

_φ(^-^)前半そうか!
_φ( ̄ー ̄; )…数式…/(^o^)\
またA.Bが…謎解きしたあとだから頭がーごちゃんこー
こんな感じだけど、経験積んできまーす。(^^)

やってみよう
やってみよう
2019-09-07 02:36:34ID:145572

>>BleRoom::さん

ありがとうございます!
偉大な理論や技術を勉強して「あ、そういうことか!」て理解できると、
楽しくなりますよね。今回の記事では、論文の「2.取引」の部分を紹介した感じです。
どうしてブロックチェーンで二重使用を防げるかを理解できていないので、
僕も3節以降を勉強してみたいと思いますー!

BleRoom
BleRoom
2019-09-07 00:27:41ID:145527

ハッシュがどういうものか理解できました!
ありがとうございます✨

そして論文をもう一度読む!勉強楽しい不思議www

やってみよう
やってみよう
2019-09-05 10:41:51ID:144743

>>二児の父::さん

暖かいコメントをありがとうございます!
数学系の話題って、ググってみると pdf ファイルが検索されたり、
わかりやすい解説本が見つかったりするんですよね。そういうのを読んでみると、
「あぁ、あの授業で先生が言ってたのはこういうことだったのか!」て良い復習になったりします。
気になる話題がありましたら、ぜひそういったものを活用して復習してみてください!

二児の父
二児の父
2019-09-05 03:48:02ID:144693

>>やってみよう::さん
最近、何でもかんでも数学系の授業でやった気がになって
もっとちゃんと勉強してたらなぁと後悔中です。

いつも、わかりやすい解説記事ありがとうございます。

やってみよう
やってみよう
2019-09-04 23:59:52ID:144644

>>YUTO::さん

乱数を入れることで秘密鍵がバレにくくなってたり、ハッシュ値を使うことで、ちょっとでも改ざんしたら
(I)=(II) が崩れるようになってたり、ものすごい工夫されてますよね(^^)
今回ご紹介したエルガマル署名の改良版である「DSA署名」は、現実の電子取引でも使われるみたいで、
数学ってこういうところでも使われるんだなぁと、僕自身勉強になりました。

YUTO
YUTO
2019-09-04 21:05:49ID:144602

このアルゴリズムを見つけた人、すごいですね!!

この記事を書いた人
数学関連の記事が多めです。