connecting...
Google translation for articles :
6 NEMBER donated to you!!

【数学】この計算に覚えあり(後編)

nem11.29xem (6) 151 11 2

 


暗号技術
に応用される 数学 についてご紹介。今回は後編です。

 

前編:みんなが日常的にやっている剰余計算 

後編:剰余計算を使って、チョー難しい計算問題を作る!(今回)



前回の記事で、剰余計算と、素数が支配する世界を考えました。
例えば、素数 5 が支配する世界では、0,1,2,3,4 という五つの数字しか存在せず、

 

1 + 1 = 2

2 + 3 = 0

3 + 3 = 1

2 - 4 = 3

1 - 2 = 4

4 × 4 = 1

という、摩訶不思議な計算が繰り広げられるのでした。この計算は、
「計算結果が 0~4 以外だったら、5 を足したり引いたりして、0~4 までの数字にする」というルールで
成り立っているのでしたね。例えば、通常ルールなら、4 × 4=16ですが、計算結果が0~4 以外になったので、
16 -5-5-5=1 で、4 × 4 = 1 とする、ということでした。

そして、素数が支配する世界では、割り算ができるということもご紹介しました。これは、
0 以外の数字には、必ず逆数が存在するという意味でした。例えば、5 が支配する世界では、

1 × 1 = 1,
2 × 3 = 1,
3 × 2 = 1,
4 × 4 = 1.


なので、0 以外の数字 1,2,3,4 は、ある数字を掛け算すると、1になります。このとき、
11 の逆数、32 の逆数、23 の逆数、44 の逆数です。

5 が支配する世界において、3 ÷ 2 というのは、3 に 「2 の逆数」を掛け算するという意味でした。
なので、3 ÷ 2 =3 × (2の逆数) = 3 × 3 = 4 となります。

以上のような計算のことを、剰余計算と呼びました。世界を支配する数字 5 を、法と呼びました。

 

わざと難しくするんです!



素数が支配する世界を利用して、解くのがめちゃくちゃ難しい問題を量産することができます。
そして その問題が、暗号に利用されるのです。

目指せ北海道さんの記事で、このお話が出ています。同記事では、


q = 57896044618658097711785492504343953926634992332820282019728792003956564819949


という超巨大素数が支配する世界が考えられています。なんじゃこりゃ!

この q が本当に素数なのか、計算機を使って確かめてみました。



OK でーす!


同じ記事で、121665/121666 という分数が出てきていますね。q が支配する世界では、
121665÷121666は、121665に、「121666の逆数」を掛け算する、という意味でした。

なので、「121666の逆数」を頑張って計算しなきゃいけないのですが、
ワタクシ、ユークリッドの互除法と計算機を使って、頑張って計算しました!

法 q における「121666の逆数」は、

37095705934669439343138083508754565189542113879843219016388785533085940283556

です!チョー疲れたー!これは本当に「121666の逆数」なのか、再び計算機で確かめてみます。
この 37095... から始まる数字と 121666 を掛け算して、1 になることを確かめればいいわけです。

 

OKでーす!


この「121666の逆数」を121665に掛け算することで、


121665/121666
=121665 × 37095705934669439343138083508754565189542113879843219016388785533085940283556
=20800338683988658368647408995589388737092878452977063003340006470870624536394


という数字に辿りつきます。マイナスをつけると、

-121665/121666
= -20800338683988658368647408995589388737092878452977063003340006470870624536394

ですが、これに 法である超巨大素数 q を足すことで、

-121665/121666

= 37095705934669439343138083508754565189542113879843219016388785533085940283555


となります。見事、北海道さんの記事でも紹介されている数にありつきました。扱っている数が大きいため、
計算がとても大変です。だけど、それで良いんです!だって、この大変さを利用して、暗号を作るんですから!


ハッキングしたいなら、この問題を解きたまえ!

 


17という素数が支配する世界を考えてみましょう。

例えば、4 という数字を 3乗すると、通常の算数のルールなら

(4の3乗) = 4 × 4 × 4 = 64


ですが、この計算結果は17を超えているので、17を引けるだけ引いて、64-17-17-17 = 13、よって、


(4の3乗) = 4 × 4 × 4 = 13


となります。このように、

「素数が支配する世界で、a を b 乗したら何になりますか?」

というような問題は、簡単に計算することができます。

ただ、次のような問題を解きなさいと言われたらどうでしょう?

問題17が支配する世界では、2 を 何乗したら、9 になりますか?

 

難しいですよね。この問題の正解は 7 です。

先ほども言いましたが、「17が支配する世界で、2 を 7 乗したら 何になりますか
という問題は、簡単に計算することができます。答えは 9 です。

だけど、これを「17が支配する世界では、2 を 何乗したら 9 になりますか
という問題に置き換えた瞬間、難易度がグググーーンっとあがるのです。

このような問題のことを、離散対数問題(りさんたいすうもんだい)と言います。


離散対数問題の作り方はとっても簡単。テキトーに、2, 7 という数字を選んできて、
2 の 7 乗を計算し、9 という答えを出す。この計算は簡単。

あとは、7 の部分を虫食いにすることで、「17が支配する世界では、2 を 何乗したら 9 になりますか
という問題を作るだけ。この問題が作られるまでの過程を知らない人にこれを出題すれば
「いや、解けないよ!」ってなるわけです。

問題を作るのは簡単」だけど「第三者がその問題を解くのは、とても難しい」。
そんな問題を、「素数が支配する世界」を考えることで、作り出すことができるのです。



※)「素数が支配する世界」を考えなくても、「2 を何乗したら 9 になりますか?」という問題を
考えることはできますが、これは log_2 9 と、log (対数)を使うことで、簡単に答えが
求まってしまいます。 「素数が支配する世界」を考えることで、log が通用しない難しい問題
が作られるのです。対数の問題を、整数 1,2,3,4,...  という離散的な世界で考えるため、
離散対数問題という名前が付けられています。


問題をもっと難しくしたい場合は、北海道さんの記事に出てきたような、超巨大な素数を考えて、同じような問題を
作ればいいのです。

問題57896044618658097711785492504343953926634992332820282019728792003956564819949
が支配する世界では、4214という数字を何乗したら、29271873004104383894907871047312166076282882275913089206714692811628377422126
になりますか?


ね、こんなの求めるの無理でしょ。ちなみに答えは 321 です!

このことを応用して、暗号を作り出すことができます。

① 僕が、Aさんにメッセージを送ることを考えます。このメッセージは、Aさん以外誰にも
知られたくないものだとします。A さんには、予め 321 という秘密の数字を教えておきます。

誰にも知られたくないメッセージ(例えば、『麻生久美子さん大好き』)を、適当な方法で、
意味不明な数字に暗号化します。万が一このメッセージの送信がハッキングされても、ハッキング
した人間が目にするのは、暗号化された意味不明な数字のみです。

③ この暗号は、上記のような 問題 を解かないと、解読できないようになっています。321という数字を知らない
第三者は、コンピュータでも解くのが難しいような問題を解かないといけないわけです。つまり、
第三者が暗号を解除して、元のメッセージ(例えば、『麻生久美子さん大好き』)を見るのは、
ほぼ不可能だということ。321という数字を知っている僕とAさんだけはメッセージを解読する
ことができるようになっている、

こんなロジックです。僕が年上好きだという事実も、誰にもバレずに済みました。



Nemを守るのはもっと難しい問題!



Nem を守る「楕円曲線暗号」と呼ばれる暗号は、もっと難しい問題を出題してきます。
上記の超巨大素数が支配する世界と、「楕円曲線」という曲線の理論を組み合わせて作られる
問題を出してくるのです。



超巨大素数?楕円曲線?難しいよ!


そう思いますか?さっきも言いましたよね。それでいいんです!暗号なんですから!



超巨大素数?楕円曲線?やってやろうじゃねえか!Nemのシステムを破壊してやる!


そう思いますか?そんなあなたは、クラッカーと、数学者の素質ありです!



楕円曲線のお話も、できたら記事にしてみたいと思います。


今日はここまで!



注意)離散対数問題を利用した暗号のことを ElGamal暗号(エルガマルあんごう)と言います。 
ただ、この暗号を利用するためには、離散対数問題を作るために選ぶ二つの数字
(本文中の例だと、2, 9 )を、特別なものに選ぶ必要があるみたいです。
ここら辺は、僕は不勉強なので、詳しく書かないことにします。

Why don't you get crypt currency 'nem' by posting your blog article?

nemlog is blog posting service which has donation feature by crypt currency nem.
nemlog was launched to create environment which can be donated nem among NEMbers via blog articles.
Let's get nem by posting good blogs.

Nem prize event is being held frequently, Please join us on this opportunity!

nemlog registration from here
Register
Comments from NEMber
やってみよう
2019-04-16 20:54:30ID:104628

>>やそ::さん

ありがとうございます!そう言ってもらえてうれしいです。

素数を使った別の暗号で、RSA暗号と呼ばれるものがあります。
これは、「37 × 31 = 1147」を計算するのは簡単だけど、
「1147 を素因数分解せよ」を解くのは難しいというような数字の性質
を使った暗号です。今回の記事に出てくる暗号も、RSA暗号も、
数字の性質を上手に活かしてるなって思います。

やそ
2019-04-16 18:13:04ID:104506

良くいろいろなところで暗号通貨のセキュリティが素数がどうのという話を聞きますが、
このお話を読んでどういうことが理屈はわかりました!
わかりやすい説明ありがとうございました!

やってみよう
2019-04-16 10:26:37ID:104287

>>えっさん&小梅ちゃん🐾nemlogツアーコンダクター🐾::さん

難しいですよね!子守歌代わりになったら幸いですw
スヤスヤ眠ってるえっさん、かわいいです。

>>目指せ北海道::さん

僕も最初、マイナスに気づかなくて、「あれ、計算あわないかな?」て思ってたんですけど、
マイナスをつけたらぴったり計算が合いました!w 僕の記事を引用していただき、
ありがとうございます!

目指せ北海道
2019-04-16 08:22:36ID:104222

自分で確かめて無かったので不安でした。割り算にマイナスがついていたなんて!今まで気づいてなかったw。

やってみよう
2019-04-16 00:00:49ID:104026

>>tom::さん

今回は、かなり難しい話題を記事にしてしまいました。
それでも読んでくださって、ありがとうございます!

>>7zoesan::さん

ありがとうございます!
それでOKでーす!

やってみよう
2019-04-15 23:59:06ID:104025

>>mizinco::さん

ありがとうございます。
四則演算と素数を使って暗号を作っちゃおうという精神ですね。
数字の性質を上手に使うなぁって思います!

>>YUTO::さん

おっしゃる通り、離散対数問題や楕円曲線暗号は量子コンピュータで効率的に解かれちゃうみたいですね!
新しい暗号作りの研究が大急ぎで進められているようです。

tom
2019-04-15 23:25:04ID:103974

真剣に読んでもわかりませんでした(笑)

7zoesan
2019-04-15 22:13:09ID:103869

とりあえずNEMのセキュリティは高いってことはわかりました!!

mizinco
2019-04-15 21:26:02ID:103826

暗号ってこうやってできてくんですね…
興味深いですー

NEMber who posted this article

「やってみよう」は、プログラマであるタノウエと、数学を勉強しているカナクボが、共同で管理しているアカウントです。
勉強をして身に付けた NEM の知識や数学の話題を、随時投稿していく予定です。
20168
0

Why don't you read following articles?