無敵の暗号を解くカギは「分割統治」。あるいはコンピュータ科学を貫く大原則について。【暗号3】#81
Вставка
- Опубліковано 11 лип 2024
- 「暗号」シリーズの第3回です。「無敵のヴィジュネル暗号を解読したバベッジとは」「周期を特定するには単語で見ず算数を使え」「実用上無敵になれないヴィジュネルくん」など、ヴィジュネル暗号の解法について話しました。
【目次】
0:00 帰ってきたdivide and conquer
0:26 ヴィジュネル暗号をdivideしよう
3:51 ヴィジュネル暗号を解読したバベッジとは
8:38 周期を特定するために使うのは算数
19:51 言語学的に復号してみる？
22:55 コンピュータの父が導き出した解法とは？
29:57 実用上無敵になれないヴィジュネルくん
【参考文献】
〇暗号解読
amzn.to/46sW80V
〇暗号技術入門 第3版 秘密の国のアリス
amzn.to/3JJ3iVd
〇計算機の歴史
amzn.to/42AuhIW
【サポーターコミュニティ加入はこちらから】
yurugengo.com/support
【親チャンネル：ゆる言語学ラジオ】
/ @yurugengo
【実店舗プロジェクト：ゆる学徒カフェ】
/ @yurugakuto
【おたよりフォーム】
forms.gle/BLEZpLcdEPmoZTH4A
※皆様からの楽しいおたよりをお待ちしています！
【お仕事依頼はこちら！】
info@pedantic.jp
【堀元見プロフィール】
慶應義塾大学理工学部卒。専門は情報工学。WEBにコンテンツを作り散らかすことで生計を立てている。現在の主な収入源は「アカデミックに人の悪口を書くnote有料マガジン」。
Twitter→ / kenhori2
noteマガジン→note.com/kenhori2/m/m125fc452...
個人UA-cam→ / @kenhorimoto
【水野太貴プロフィール】
名古屋大学文学部卒。専門は言語学。
某大手出版社で編集者として勤務。言語学の知識が本業に活きてるかと思いきや、そうでもない。
Twitter→ / yuru_mizuno
【姉妹チャンネル】
◯ゆる音楽学ラジオ( / @yuruongaku )
◯ゆる民俗学ラジオ ( / @yuruminzoku )
◯ゆる天文学ラジオ ( / @yurutenmon )
◯ゆる書道学ラジオ ( / @yurushodo )
◯ゆる生態学ラジオ ( / @yuruseitai )
◯ゆる哲学ラジオ (open.spotify.com/show/7t8NNVq...)
#暗号 #ゆるコンピュータ科学ラジオ_暗号
![Мифы, в которые мы верим #17 [ПИРАТЫ]](http://i.ytimg.com/vi/nVWFOtzL7ok/mqdefault.jpg)
【参考文献】
〇暗号解読
amzn.to/46sW80V
〇暗号技術入門 第3版 秘密の国のアリス
amzn.to/3JJ3iVd
〇計算機の歴史
amzn.to/42AuhIW
【サポーターコミュニティ加入はこちらから】
yurugengo.com/support
【おたよりフォーム】
forms.gle/BLEZpLcdEPmoZTH4A
※皆様からの楽しいおたよりをお待ちしています！
最後の暗号文ですが、鍵は円周率ですね。31415…
暗号文中の何文字目かをnと表します。４文字目なら n=4 って感じで。
大文字の場合は 鍵+n 文字だけ逆順にずらします。
１文字目のAは鍵の１文字目が３なので 3+1=4 文字逆にずらします。z,y,x,wで「w」
２文字目のRは鍵の２文字目が1なので 1+2=3 文字逆にずらします。q,p,oで「o」
４文字目のFは鍵の４文字目が１なので 1+4=5 文字逆にずらします。e,d,c,b,aで「a」
小文字の場合は 鍵+2(n-1) 文字だけ逆順にずらします。
３文字目のuは鍵の３文字目が４なので 4+2(3-1)=8 文字逆にずらします。t,s,r,q,p,o,n,mで「m」
５文字目のaは鍵の５文字目が５なので 5+2(5-1)=13 文字逆にずらします。z,y,x,w,v,u,t,s,r,q,p,o,nで「n」
と言うわけで堀元さんがなりたかったのは woman です。エウレカ！！
まさかのＴＳ
38:42
堀元さんのXバー理論のシャツが
小細工の『工』に被って『丕』に見える貴重なシーン
ARuFaになりたかった堀本さんの純粋さ面白い
堀本さんのdivide and conquer欲を満たすためにゆるdivide and conquerラジオと称して過去あらゆるdivide and conquerの事例を紹介する回を見てみたい
05:38 水野さんの指摘が鋭い。さらに言うと、
そろばん : デジタル計算機
計算尺 : アナログ計算機
なんですよね。
本編あんまり関係ないけど、ハガレンでホークアイからマスタング大佐にカップを鳴らしてから次に鳴らすまでに出てきた人物名の頭文字から暗号を伝えるのおしゃ〜ってなったの思い出した
最後の暗号(？)を出した時の、
水野さんの満面の笑顔がスコですｗ
40:34〜の水野さんの堀本さんをいじれて満足そうな笑みがかわいい😂
17:09 ここで「約数か」って閃ける水野さんも相当凄い
これは流石にもっと早い段階で分かった
@@user-gi4zf6tf4cすごいねー
ひらめきを表す単位として「女神」が提唱されましたが、実は既にそれを表す単位ってすでにあるんですよ。
「ピカラット」って言うんですけど……
シリーズ物の時前回と次回に飛べるリンクはってほしいなぁ
queenをキーにすると暗号は解かれやすい。そうは言ってもqueenとかいう単語は頻発しないだろうと思って聞いてたのですが、暗号が使われた背景的には出ないわけがないのですね。すごい皮肉な偶然だ。
堀本さんが着てるX-bar Tシャツのせいで、偶に字幕にサーカムフレックスが付いてるようにみえる
同じ並びを見つける話から約数がなかなか出なかったり、周期が分かっても頻度分析が出なかったり、数学得意なはずの水野さんがやはり言語寄りの人だと認識する回。
最後の「26文字まるごどズラす」ってのは、ワロタ。
見方が360度変わるようなもんですね
楽しみに待ってました
久しぶり!
たのまち
バベッジ回、期待してます！
その昔、彼の名を冠した住所に住んでたので一方的に親近感があります。
小細工だけでも思いつけるのは結構すごいことだなぁと思います。
どこかで、僕の最強の暗号をお互いに作ってお互いに解いてみる、みたいなこともやってみてほしいですね。
正直解く方が難しいから、塩試合になりそう
ここまでデカルトみを推すこのチャンネル、カルトみを感じる
サムネ見た瞬間またディバコンかぁと思った俺はもうダメかもしれない
サムネからあふれるデカルト味
ディバコンって略すの面白いw
久しぶりにキブスン&スターリングの「ディファレンスエンジン」読みたくなったw
暗号 → 復号
ARuFaになりたい → 承認欲求を満たしたい
水野さん「もっと語数の多い文章を想定してたら解読法思いついたのに～」
インダス文字研究者「1文の語数が少なすぎて全然解読が進まないよ～」
12:25 この辺から水野さんはもうズレを解読しようとしてて、まだ周期を特定する段階なのを忘れてる
めちゃおもろい
各行ごとに頻度分析したあと、分布を見れば行ごとのずれも予測できるよね。
ずらし直して全部で頻度分析すれば精度上がりそう。
歴史というにはまだ早い、現代暗号のおもしろトピック回もいつかやってほしい
スノーデンの暴露後にインターネット上の暗号が強化された話とか、耐量子暗号の標準化とか
今回の結論はdivede and conquer
今回とconquerで韻を踏んでる
がんばってヴェノナを完全解読してほしい！
大道芸もしてるエンジニアとしてバベッジ氏の名前は覚えておかねば(使命感)と思いました😂
たのまち
頻度分析について、
［分かち書きしなくても分解可能］で［長さの一定でない］ような符号化を何かでみたけど、それを使えば上手く回避できるのかな
たとえば、8つのコード〈10, 010, 110, 0010, 0110, 1110, 00010, 00110〉は どう組み合わせても「10」の部分で区切ると一意に分解可能だから、
e→10，t→010，a→110，…
のように換えた上で、頭から3字ずつ区切ったものを
000→E，001→T，010→A，…
みたいに置換え直すと、まったく別の文になる、みたいなものです。
水野さんだからポンポンいく感じある
トライ&エラーじゃなくて、トライアル&エラーが正しいんじゃなかったでしたっけ
デカルトみ取られちゃった
久しぶり俺たちのデカルトみ
算盤は、計算器というより記憶装置って印象かな。計算自体は頭でやるわけだし、慣れてきて脳内イメージで算盤を再現すると暗算になるし。
映画『ドリーム』で、大量の計算を人間の手で行う職業も「コンピューター」って呼ばれていたことに気づいた。日本語に訳すと計算手になるが…。
そろばんのことを「これはね、東洋の計算機だよ」ってラピュタでドーラが言ってたな。
（この動画で興味を持ってフレッド・B・リクソンの『暗号解読事典』や英語版wikipediaを読んだんですが、以下はそれでも曖昧な情報です）
"ヴィジュネル暗号"は、実際にはヴィジュネルが発明したものではなく、トリミテウスさんが作ったアルファベット方陣をジョヴァン・ベラソさんが改良したものを、更にジロラモ・カルダーノさんが改良したものを、最後に改良したのがヴィジュネル……みたいな話だったと思います。
"ヴィジュネル暗号"には多くのバリエーションが存在して、初期の「1文字目は1段目で暗号化して、2文字目は2段目で暗号化して…」という鍵がないパターンや、「単語の繰り返しを鍵にするけれど、鍵の繰り返しをアレンジした」パターン、「冒頭だけ鍵で復元した後は、解読後の平文それ自体がそれ以降の鍵になる」パターン、それから「鍵を使ってアルファベットの方陣の中身自体をかき混ぜる（鍵が「YURU COMPUTER」なら、「ABCDEF…」が「YURCOMPUTEABDFG…」になる）」パターンなんかもあります。
その辺も全部総合すると、 25:50 で水野さんが話していたやり方が実は一番汎用的な女神が降りてきてますね。
The enemy know the system（要約）を言ったケルクホフスさんが発明した、スーパーインポジションという解読方法です。
外交で使われる暗号は確か暗号文と鍵が同じ長さの物を使うという話を聞いたことがあります。それは、独自に作った乱数表を互いに持っている状態でどこから始めるかを伝えて、使い終わった乱数表の前はもう使わないというものだったような気が…
ブルーバックスの暗号の数理にそのようなことが書いてあったように思います。
使い回したら、複数の暗号文の1文字目、2文字目、3文字目とそれぞれで頻度分析したら複合鍵が見つけられるということかな
@@jing7968 繰り返し周期ごとに暗号文の文字列を並べると、それは単替字暗号になっているので、頻度分析で対応可能ということ、それを避けるには暗号鍵を長くする必要があるという話です。そのために乱数表をお互いに持っておいて、その最初や読み方(例えば、1つ飛ばしやページの場所など)を伝えて暗号文を送る。使いまわしなどの重複があると周期ができる可能性があるので、2度と使わないということになっていると理解しています。
暗号と言語学に共通する分野として、古代文字の解読があると思います。
例えば西夏文字がどのようにして解読されたとか、興味あります。
今後の展開を期待しております。
ところで、一連の「ゆる・・・」シリーズ、友人知人に推薦しようと思ったことがあるのですが、いささかアレな表現が散見されるため、特に女性には勧めにくく、残念ながら寸前で思いとどまりました。
31:05 例えば、同じ長さの暗号鍵(鍵1)を更に暗号化(鍵2)して手紙を3通作成し、それぞれ2セット{(暗号文+鍵1+鍵2)×2}を目的地点でのみ集合するようにバラバラに送れば、密室で伝えるなんて危険かつ制約の多い方法を使わずに済むんじゃないだろうか。
2セット用意するのは、奪取流矢その他の理由で手紙が目的地点に到達しないリスクを下げるため。
どれか一つが到達せず復号できないリスクを下げるために3セット4セットと増やしていくことも可能だが、その分奪取による解読(ソーシャルハッキング?)への強度も低下する。
逆に、解読リスクを下げるために鍵3,鍵4と増やしていくことも可能。その分復号と配送のコストが増えてしまうが。
配送手段などが必要な分ある程度のリソースを用意できる状況じゃないと使えないことと、復号に掛かる時間が長いこと(より多くのリソース投入で短縮可能)が欠点だけど、その辺りは運用でどうにかできる範疇に思う。
少なくとも、(状況や目的にも依るが)暗号を使わなければいけない幾つかの主体(軍部や諜報機関や外交組織)が許容できないほどの労力・リソースではないと思う。
まぁ、元の発想に付け足しただけとはいえ素人が数分で考え付くような方法なんて、(自分が考え付く以上の)何らかのデメリットを持つか既に陳腐化(容易な解読方法考案済)しているかしていそうだけど。
ビジュネル暗号はエニグマのディスク一枚分に相当するのかな
開始7秒ワイ｢ディバコンやな｣
ディバコン回
プリンセスプリンシパルの映画で使われた暗号ってビール暗号っていうのか
モニアックは、フィリップスの経済モデルのやつかな?
詳しくは『物価とは何か 渡辺努』を
炎上上等的なところのある堀元さんが炎上絶対回避マンのA...(ネタバレ防止)に…というのは興味深い
今回のテーマ普通にディスカバディーチャンネルとかでやってほしい。やってる？？
Q.フーリエ変換のめちゃ速い計算法は？
A.D&C
あまりに頭の回転が良くて水野さんに嫉妬してしまう😭
鳩の巣原理かな？鍵の長さより多く出現する単語は、少なくとも一つ同じ変換がなされる
電卓が出てくる前は手回しのタイガー計算機だった。
バベッジやチューリング、ノイマンなど複数人がコンピューターの父と呼ばれますが
彼らは穴兄弟という事で良いでしょうか？
草
暗号って聞くと、サマーウォーズ出てくる
鼻血を出しながら暗号を解く主人公
いつのまにか日曜日の朝に見てる
引き算すれば1個のシーザー暗号になりますよね？
堀元さんちょっと鼻声だな
縦に積んで頻度云々のくだり、0.2女神どころか何も間違ってなくないか？
ジオストームのあれってビール暗号っていうのか
ちょっと違うか
25:50 ほぼ正解やん〜これで0.2女神は厳しくない？笑
31:14 このあたりの話、十分に長い乱数表を事前に作ってお互いに持っておくという方法は無理でしょうか？
ここでの堀元さんの話は「800桁の鍵を安全に渡せるなら、そもそも暗号にしなくても、800文字の平文を伝えればいいじゃん」ということだと思いますが、鍵を渡すタイミングと、メッセージを送りたいタイミングは別なのでは？メッセージは傍受される危険があるから暗号にするけど、鍵は事前に確実に安全な方法で渡しておくのだから、「鍵を安全に渡せるならそもそも暗号にする必要ないじゃん」という批判は当たらないと思いました。
暗号はそもそも文書を奪われた時のための対策です。文書を奪われた状況では当然鍵である乱数表も一緒に奪われてます。なので暗号を使うためには鍵を絶対に奪われないようにするために文書に残さずに記憶するわけです。そのためには鍵は短くないといけないんです。
事前に十分長い乱数表を共有できる場合はその方法が最強(数学的に解読不能であることが証明済み)です。
事前準備が面倒かつ不特定多数の人が相互に通信するインターネットのような環境で使えないため軍事用等に限定されますが
次回量子暗号との絡みで話題に上がるかも?
音声がちょっと低い（具体的には、堀元さんの声がいつもよりキーが1個低い）と思うんですが、
今回編集にあたって音声イジってたりします？
暗号の解析は長い間、言語学者の仕事だったけど、ちょうどバベッジの生きた19世紀から20世紀にかけて数学者の仕事に、そしてコンピュータエンジニアの仕事にシフトしてきたんですよね。
周期が発生しない無理数の√2=1.41421356...とかから
+1,+4,+1,+4,+2,+1,+3,+5,+6...の累計で文字をズラせば完璧か
√をかける数字は平方数でなければ何でもいいし、
10進数にしなくてもいい。この組み合わせで無限に鍵を作れる
ルート計算は多分怪しいですね。きちんと計算してないですが平方根は無理数で代数方程式（いわゆる二次方程式みたいなの）の解になるので、次の文字の遷移数が立式できるはずです。
難しいことは間違いないですし解法もぱっとは浮かびませんが、解けない暗号ではないです。
こういう可能性を否定するには超越数（π、e）を使う必要がありますが、暗号鍵に使えそうな数字は2種類くらいですから推測されやすいと思います。
@@seijim8912πの適当な桁から始めればいいのでは？
@@seijim8912a(e^n + π^m)とか、いくらでも作れそうな気がする
@@seijim8912
代数方程式の解になるのは思ったけど、最終的にn進数のmodが入るから大丈夫かと思ったがな...
√の0.5乗ではなく別の有理数乗にする
πではなくsinやcosなどにする
eを有理数のべき乗にする
等、ほかの小細工も使えるか...
暗号化する側も複合する側も鍵となる無理数を文字長分の桁まで計算しないといけないってのは、できなくはないだろうけどそれなりに大変そう
おもろ！
28:14 あれ、これヴィジュネル暗号2回かましたらステップ①が突破できなくないか？
その場合、例えば1度目の周期と2度目の周期の最小公倍数が最終的な周期になるので、より頑強にはなるけど解読は可能になります。
@@DoLikeHer ありがとうございます。ただ有限の文章に再現性のある文字列が発生する前提で分析を進めているので、２回とは言わずとも何回かかませばほぼ突破できなくなるほど頻度下がるのでは、なんて思ったり…
@@erosthanatos0963 その通りで、再現性のある文字列が出る確率や頻度は減らせると思います。再現性が減れば堀元さんが説明していたような方法での解読は困難になると思います。
@@DoLikeHer ありがとうございます。その場合、どうやって解決するんでしょうね。使い勝手も、堅牢さもより優れた暗号(RSAなど)にとってかわられたので、その世界線は存在していないような気もするのですが、、、興味は尽きませんね、、、
サンキュー女神
ビール暗号ってあれか、自来也がやったやつか
メガミ
ギガミ
テラミ
32:24 「800文字の鍵を伝えられるなら800文字の原文を伝えればいい」この辺ちょっと前提としている状況がわかりません。敵地に出発する前に暗号鍵を共有しておき、敵地で得た情報を送ってくるという状況をイメージしていたのですが。
その前提状況はほぼ書籍暗号ですね
通常は短い間隔で鍵を変更し、一つの文書が解読されても全ての文書は解読できないようにします
エニグマですら敵に機械本体を奪われる可能性を考慮して運用してますし、機械本体を奪われても長らく暗号解読はされませんでした
鍵の配送問題は常に生じ、暗号化の手法自体よりもある意味では研究が進んでいます
量子暗号も鍵配送問題に対する研究だったりします
@@aquacrown9654 ありがとうございます。敵地にいる状態で鍵を変更する状況と考えてよいのですね。そうかもとも思ったのですが、どういう方法を想定しているのかがわかりませんでした。
32:18 「鍵は秘密の2人だけの部屋で伝える」
とあったのですが、そんな状況が可能なら長い文も伝えられそうな気もしますし。
なんか今回の堀元さんの声低くない？
s = rot13(s)
s = rot13(s) #念のためもう一度
黒歴史をより黒くしてる気がする
後ろ髪がない上に前髪もぱっつんな女神だから水野さん微妙に掴みそこねてる
水野さんって、脳内将棋と脳内積分は、出来るの？
出来るなら、ヨビノリたくみさんと、勝負してほしい。
それはそれで、
最後の暗号の解読は、
Agent
Ruby
Factorist
では？
周期さえわかれば実質的に単一換字式になるって言ってるのに頻度なかなか出てこないの謎
ニーモニック認証とかだとパスワードを覚えやすい英単語に置き換えるとかありますよね。かなり長いものでも覚えられる。
ニーモニック＝ギリシア神話の記憶の女神ムネーモシュネーに由来する
タイガー
大道音楽家俺も嫌いだがら、実質バベッジや
ヒンディーは言語名で、宗教名はヒンドゥー教です。ヒンズー語とかヒンディー教という取り違いはしないようお気をつけて。
分割統治法（divide and conquer）って名前、
デカルトが言葉を借りるまでは、戦争や植民地支配を強行する（そして現地の伝統的コミュニティーを滅ぼす）文脈でつかわれてきた用語なので、
テクニカルタームとして無邪気に使われると非常にもやもやする…んですけど、しょうがないんですかね。
つい先日パレスチナ現代史を読んだばかりで、何でも感傷的になってるだけかもしれませんが。
MITのアルゴリズムのテキストでも頻出ですし、業界標準として仕方ないとは思います
堀元さんに対して苦言を呈するのはちょっと酷かなと
私は最近、分割統治と聞くと「正社員を既得権益のように印象づけて非正規の不満を煽り、労働者が団結するのを防いで搾取する経営者」を連想して暗い気持ちになります・・・
the bad sleep well
たぬき
おろしあ
内容自体には興味があるから見たいんだけど、水野さんの発言内容が酷すぎて苦痛すぎる。
他の人はなんとも思わんのか?