(博士課程で)足掻(くア)ライさん
@K9MmU7qClO9irZ3
今日は、「暗号の鍵を安全に共有する方法」についてお話するのだ。 まず最初に、暗号について軽く触れるのだ。 メッセージやデータを、そのままでは読めない・使えない状態に変換することを暗号化と言い、その逆の変換を復号というのだ。
2019-11-16 20:39:06
(博士課程で)足掻(くア)ライさん
@K9MmU7qClO9irZ3
そして暗号化・復号に使うデータのことを鍵というのだ。 鍵は暗号化と復号で同じものを使うこともあるし、違うものを使うこともあるのだ。 今回は、同じものを使う場合を考えるのだ。 暗号の簡単な例を挙げるのだ。次の暗号を、復号してみてほしいのだ。 暗号文：えれおせうのくめけちねふで 鍵：3
2019-11-16 20:40:14
(博士課程で)足掻(くア)ライさん
@K9MmU7qClO9irZ3
答えなのだ！ もとの文は「あらいさんにおまかせなのだ」なのだ。 五十音で3文字手前の字にずらすことで、復号できるのだ。 メッセージを暗号化したいときは、五十音で3文字後の字にずらせばいいのだ。
2019-11-16 20:44:00
(博士課程で)足掻(くア)ライさん
@K9MmU7qClO9irZ3
暗号を使って当事者間だけで情報をやりとりしたいとき、鍵の管理はとても重要なのだ。 もし鍵が第三者にバレてしまったら、その人は通信を傍受すれば 暗号文の中身を知ることができるのだ。
2019-11-16 20:45:13
(博士課程で)足掻(くア)ライさん
@K9MmU7qClO9irZ3
第三者に傍受されないような秘密の通信路を使えばいいと思うかもしれないが、もしそういうのがあるのなら、そもそも暗号化する必要がないのだ。 通信が傍受される危険性があるからこそ、暗号を利用しているのだ。
2019-11-16 20:46:56
(博士課程で)足掻(くア)ライさん
@K9MmU7qClO9irZ3
ここで、大きな問題が立ちはだかるのだ。 はじめましての人とやりとりするとき、どうやって鍵を共有すればいいのだ？ 暗号文は、そのままだと読めないのだ。読むためには鍵が必要なのだ。 でも、鍵のデータをそのまま相手に送るわけにはいかないのだ。 その通信が傍受されたら、鍵が漏れてしまうのだ。
2019-11-16 20:48:08
(博士課程で)足掻(くア)ライさん
@K9MmU7qClO9irZ3
かといって、鍵を暗号化して送るわけにもいかないのだ。 それを復号するための鍵はどうやって送るのだ？ 堂々巡りなのだ。 つまり、当事者は鍵を入手できるが、第三者は通信を傍受しても鍵を手に入れられない、 そんな一見矛盾してるかのような方法が必要になるのだ。
2019-11-16 20:49:26
(博士課程で)足掻(くア)ライさん
@K9MmU7qClO9irZ3
そのような方法の1つに、ディフィー・ヘルマン鍵交換(以下DH鍵交換)というものがあるのだ。 これが今日の本題なのだ！ DH鍵交換を理解するために、離散対数について話すのだ。
2019-11-16 20:50:27
(博士課程で)足掻(くア)ライさん
@K9MmU7qClO9irZ3
離散対数とは、「余りの世界における対数」のことなのだ。 余りの世界とは、ある数aを決めておいて、2つの整数をaで割った余りが等しければ、 それらは等しいとみなす世界のことなのだ。整数以外の数は考えないのだ。
2019-11-16 20:51:21
(博士課程で)足掻(くア)ライさん
@K9MmU7qClO9irZ3
例として、「7で割った余りの世界」を考えるのだ。 この世界では、1=8や3=-4が成り立つのだ。 足し算や掛け算もできるのだ。5+6=4で、4×3=5になるのだ。 常に7で割った余りに着目するのだ！
2019-11-16 20:52:19
(博士課程で)足掻(くア)ライさん
@K9MmU7qClO9irZ3
掛け算ができるから、累乗も考えられるのだ。 3の2乗は2で、4の3乗は1になるのだ。 そして累乗ができるなら、対数も考えられるのだ！ そして、ここがキモなのだが、累乗の計算は易しいが、対数の計算はとても難しいのだ！
2019-11-16 20:53:09
(博士課程で)足掻(くア)ライさん
@K9MmU7qClO9irZ3
DH鍵交換の手順を説明するのだ。アリスとボブが鍵を共有したいとするのだ。 まず、アリスは大きな素数pを選び、次いで「pで割った余りの世界」にて、 「p-1乗すると初めて1になる数α」を選ぶのだ。 例えば、p=7なら3か5を選べばいいのだ。
2019-11-16 20:54:15
(博士課程で)足掻(くア)ライさん
@K9MmU7qClO9irZ3
このpとαは、隠す必要はないのだ。堂々とそのままボブに伝えればいいのだ。 以降、計算は「pで割った余りの世界」で行うのだ。
2019-11-16 20:54:42
(博士課程で)足掻(くア)ライさん
@K9MmU7qClO9irZ3
次に、アリスは数aを選び、ボブは数bを選ぶのだ。これらは秘密にしないといけないのだ。 そして、アリスはαのa乗を計算し、ボブに伝えるのだ。 ボブも同じく、αのb乗を計算し、アリスに伝えるのだ。
2019-11-16 20:55:18
(博士課程で)足掻(くア)ライさん
@K9MmU7qClO9irZ3
最後のステップなのだ。 アリスはボブから受け取った数のa乗を計算し、ボブはアリスから受け取った数のb乗を計算するのだ。 これらはどちらも、αのab乗になるのだ。この数を鍵として使えばいいのだ！
2019-11-16 20:56:05
(博士課程で)足掻(くア)ライさん
@K9MmU7qClO9irZ3
安全性を確かめるのだ。 悪人イブが通信を傍受していたとすると、イブはp,α,αのa乗,αのb乗という4つの数を手に入れるのだ。 しかし、この4つの数から、αのab乗を計算するのは、とても難しいのだ。 だから、たとえ通信を傍受されても、鍵は漏れないと言えるのだ。
2019-11-16 20:56:55
(博士課程で)足掻(くア)ライさん
@K9MmU7qClO9irZ3
これでめでたしめでたし……とは簡単にはいかないのだ。 たしかに、DH鍵交換は傍受されるだけなら鍵は漏れないが、もっと狡猾な攻撃に対しては、安全とは限らないのだ。
2019-11-16 20:57:46
(博士課程で)足掻(くア)ライさん
@K9MmU7qClO9irZ3
例えば、悪人マロリーがアリスとボブの通信に割り込んできたら？ マロリーはボブのふりをして、アリスとやりとりし、他方アリスのふりをしてボブとやりとりするのだ。 アリスとボブはお互い相手と安全に鍵を共有できたと思っていても、実際にはマロリーに筒抜けなのだ！
2019-11-16 20:58:54
(博士課程で)足掻(くア)ライさん
@K9MmU7qClO9irZ3
このため、通信相手が確かに自分の通信したい相手であるかを確かめる、認証が必要になって来るのだ。
2019-11-16 20:59:16
(博士課程で)足掻(くア)ライさん
@K9MmU7qClO9irZ3
今日のお話はここまでなのだ。 質問・コメント・ツッコみ、もしあれば投げてほしいのだ。 お付き合い感謝なのだ！
2019-11-16 20:59:58
専攻がわかラナイさん
@ranaisanra
@K9MmU7qClO9irZ3 アリスとボブで物事を喩えるの、別の本でも見たことがあるのだ。どこかの分野での'常識'があるのだ？
2019-11-16 21:04:12
(博士課程で)足掻(くア)ライさん
@K9MmU7qClO9irZ3
@5f0zcHiur75F8lL 通信するときの登場人物は、たいていアリスとボブなのだ！ 3人目はチャーリーなのだ！ 盗聴者はeavesdropperからとったイブだし、メッセージの改竄までするような攻撃者はmaliciousからとったマロリーなのだ～
2019-11-16 23:12:01
(博士課程で)足掻(くア)ライさん
@K9MmU7qClO9irZ3
@DoctorArai ここでは抽象化してるが、単に数字だけ送ったのだとボブもどれがどれか分からないから、ちゃんとそれが何なのか認識できる形で送ってると思って欲しいのだ！
2019-11-16 23:13:19
元東大限界博士のアライさん
@DoctorArai
@K9MmU7qClO9irZ3 アルファがわかってれば、対数をとってa,bが分かり、アルファのabじょうがわかりそうなものなのだ
2019-11-16 21:58:22
(博士課程で)足掻(くア)ライさん
@K9MmU7qClO9irZ3
@DoctorArai ところが、αのa乗とαが分かっても、aが簡単に求まるとは限らないのだ。もちろん総当たりすればいつかは見つかるが、現実的ではないのだ。 「余りの世界における対数」を効率的に求めるアルゴリズムは、まだ見つかっていないのだ。
2019-11-16 23:21:22
(博士課程で)足掻(くア)ライさん
@K9MmU7qClO9irZ3
今夜は、「無限の大きさ比べ」のお話をするのだ。 無限にも色々あるということを知って、無限を扱う時は直感に反することが起きる不思議を楽しんでほしいのだ
2019-11-29 23:30:19
(博士課程で)足掻(くア)ライさん
@K9MmU7qClO9irZ3
まず、当たり前のことから始めるのだ。 A={n|nは10以下の正の整数} B={n|nは10以下の正の奇数} という2つの集合があるとき、どっちが大きいのだ？
2019-11-29 23:31:55
(博士課程で)足掻(くア)ライさん
@K9MmU7qClO9irZ3
もちろん、正解はAなのだ。AはBを真に含んでいるし、要素の数もAのほうが多いのだ。Aには10個の要素が属して、Bには5個の要素が属しているのだ
2019-11-29 23:34:18
(博士課程で)足掻(くア)ライさん
@K9MmU7qClO9irZ3
少し一般化するのだ。正の整数mを一つとって固定するのだ。 C={n|nはm以下の正の整数} D={n|nはm以下の正の奇数} という2つの集合があるとき、どっちが大きいのだ？
2019-11-29 23:36:02
(博士課程で)足掻(くア)ライさん
@K9MmU7qClO9irZ3
この場合も、やはり前者のCが大きいのだ。CはDを真に含んでいるし、要素の数もCのほうが多いのだ。 有限集合においては、集合X,Yに対して 「XがYを真に含む」ならば「Xに属する要素の数はYに属する要素の数より大きい」 が成り立つのだ。
2019-11-29 23:40:21
(博士課程で)足掻(くア)ライさん
@K9MmU7qClO9irZ3
では、mを無限に飛ばしたときを考えてみるのだ。 E={n|nは正の整数} F={n|nは正の奇数} という2つの集合があるとき、どっちが大きいのだ？
2019-11-29 23:41:56
(博士課程で)足掻(くア)ライさん
@K9MmU7qClO9irZ3
やっぱりこの場合も、前者のEは後者のFを真に含んでいるのだ。要素を具体的に列挙すると E={1,2,3,4,5,...} F={1,3,5,7,9,...} だから、Fの大きさはEの大きさの半分くらいな感じがするのだ。 ところが、EとFの大きさは同じなのだ！
2019-11-29 23:46:00
(博士課程で)足掻(くア)ライさん
@K9MmU7qClO9irZ3
このことを説明するために、無限集合の大きさをどうやって比べるのか、という話をするのだ。 鍵となる考え方は、 1対1の対応が作れるなら、大きさは等しい ということなのだ。
2019-11-29 23:49:00
(博士課程で)足掻(くア)ライさん
@K9MmU7qClO9irZ3
有限で考えてみるのだ。 右手と左手、それぞれに5本ずつ指があるが、この5という数を知らなくても、右手と左手に同じ本数の指があることが分かるのだ。なぜなら、右手の親指と左手の親指、右手の人差し指と左手の人差し指、というふうに、1対1の対応を作れるからなのだ。
2019-11-29 23:51:34
元東大限界博士のアライさん
@DoctorArai
@K9MmU7qClO9irZ3 一対一の関係がつくれて、かつ一対2の関係も作れるみたいな場合は本当にないのだ？ 簡単に証明できそうな気もするのだ
2019-11-30 00:09:00
(博士課程で)足掻(くア)ライさん
@K9MmU7qClO9irZ3
@DoctorArai 有限集合では起こりえないが、無限集合ではそういうことも起こりうるのだ。というか、1対1が作れたなら1対2も1対3も作れるのだ。 でもそのときも、「1対1が作れる」ということに注目するのだ。
2019-11-30 00:14:15
(博士課程で)足掻(くア)ライさん
@K9MmU7qClO9irZ3
別の例なのだ。 あるクラスで、先生が生徒に男女のペアを作るよう指示したとき、相手が見つからなかった男子も女子もいなければ、そのクラスには男女が同数いると分かるのだ。 このとき、ペアの作り方はなんでもいいのだ。ペア、つまり1対1の対応が作れるということが大事なのだ
2019-11-29 23:55:16
(博士課程で)足掻(くア)ライさん
@K9MmU7qClO9irZ3
では、さっきのEとFについて考えるのだ。 E={n|nは正の整数} F={n|nは正の奇数} EはFを真に含んでいるが、Eの要素とFの要素で1対1の対応が作れるのだ。例えば、 1∊Eと1∊F、2∊Eと3∊F、...、k∊Eと2k-1∊F、... という対応が作れるのだ
2019-11-29 23:58:16
(博士課程で)足掻(くア)ライさん
@K9MmU7qClO9irZ3
ここで、2つの考え方があると思うのだ。 1つは、「1対1の対応が作れたから、Eの大きさとFの大きさは等しい」 もう1つは、「『1対1の対応が作れるなら、大きさは等しい』という主張は、無限集合においては成り立たない」 現代数学においては、前者の考え方を採用しているのだ！
2019-11-30 00:01:43
(博士課程で)足掻(くア)ライさん
@K9MmU7qClO9irZ3
「1対1の対応が作れるなら、大きさは等しい」という考え方に基づくと、一見全然大きさが違うように見える集合、例えば以下のものが、実は全部大きさは同じだということが言えるのだ。 N={n|nは正の整数} S={n|nは平方数} Z={n|nは整数} Q={q|qは有理数} んん？ 無限集合は全部同じ大きさなのだ？
2019-11-30 00:06:06
(博士課程で)足掻(くア)ライさん
@K9MmU7qClO9irZ3
答えはNOなのだ！ ↑で挙げた集合よりも、"大きい"集合が存在するのだ！ ちょっと言葉を定義するのだ。 正の整数全体と同じ大きさを持つ、つまり正の整数全体と1対1の対応が作れる集合を「可算集合」、そうでない無限集合を「非可算集合」というのだ。 (誤字ってたので訂正ツイなのだ)
2019-11-30 00:15:11
(博士課程で)足掻(くア)ライさん
@K9MmU7qClO9irZ3
非可算集合の代表例が、実数全体の集合Rなのだ。これは、対角線論法という手法を用いて、背理法で示されるのだ。 ではやってみるのだ！ Rが可算集合だと仮定するのだ。つまり、正の整数全体Nと、1対1の対応が作れると仮定するのだ。
2019-11-30 00:17:23
(博士課程で)足掻(くア)ライさん
@K9MmU7qClO9irZ3
この対応関係を用いて、実数のリストを作るのだ。 k行目に、「kに対応する実数」が現れるような表を作るのだ。 ただしここで注意しないといけないのが、実数の十進表記は1通りとは限らないということなのだ。 1=0.9999...が代表例なのだ。 表記を一意に定めたいから、9は無限に現れないとするのだ
2019-11-30 00:20:41
(博士課程で)足掻(くア)ライさん
@K9MmU7qClO9irZ3
あ、いや、この言い方はまずいのだな。訂正なのだ。 「9が無限回連続して現れることはない」とするのだ
2019-11-30 00:21:40
(博士課程で)足掻(くア)ライさん
@K9MmU7qClO9irZ3
さて、実数のリストを作るのだが、実は実数全体のリストを作る必要はないのだ。 というのも、「0より大きく1未満の実数全体」と「実数全体」の間に、1対1の対応が作れるからなのだ。 y=tan(π*x-π/2)のグラフを思い浮かべてみてほしいのだ
2019-11-30 00:30:05
(博士課程で)足掻(くア)ライさん
@K9MmU7qClO9irZ3
今、「正の整数全体」と「実数全体」の間に1対1の対応が作れると仮定しているのだから、「正の整数全体」と「0より大きく1未満の実数全体」の間にも1対1の対応が作れるのだ。
2019-11-30 00:32:23
(博士課程で)足掻(くア)ライさん
@K9MmU7qClO9irZ3
では、「0より大きく1未満の実数全体」のリストを表記に気をつけて作ってみるのだ。例えば、1枚目の画像のようになるのだ。 ここで、2枚目の画像のように、対角線に着目するのだ！ pic.twitter.com/G2AafRNIr5
2019-11-30 00:34:00
拡大
拡大
(博士課程で)足掻(くア)ライさん
@K9MmU7qClO9irZ3
対角線上の数字から、実数を1つ作るのだ。といっても、そのまま数字をとって並べるのではないのだ。 対角線上の数字を順に見ていって、奇数なら2、偶数なら1を小数点以下に並べて、実数を作るのだ。 ↑の例だと、対角線上に34380...と並んでいるから、0.21211...という実数になるのだ。
2019-11-30 00:38:40
(博士課程で)足掻(くア)ライさん
@K9MmU7qClO9irZ3
こうやって作った実数αは、リストに載ってるどの実数とも等しくないのだ。 なぜなら、k行目の実数とは、少なくとも小数第k位が一致しないからなのだ。 一方、αは「0より大きく1未満の実数」だから、リストに載っているはずなのだ。 矛盾なのだ！
2019-11-30 00:42:24