暗号の歴史

暗号の歴史

• 参考書：「暗号解読（上・下）」サイモン・シン 著 青木薫 訳（新潮文庫）
• ウィキペディア 暗号史
• 自己紹介
  • 菊地時夫
  • 高知大学教育研究部自然科学系理学部門(長い)
  • 高知大学理学部応用理学科情報科学コース 担当
  • 高知大学大学院総合人間自然科学研究科修士課程理学専攻応用理学コース情報科学分野 担当 (長い)
  • 地球環境情報学 (画像処理論, 情報ネットワーク論)

スキュタレー暗号

• スキュタレー＝木製の巻き軸
• ひも状の革を巻き付けて、文書を書く
• 革ひもをほどいて（ベルトのようにみせかけて）伝令が運ぶ
• 受け取った革ひもをスキュタレーに巻き付けて読む
• 紀元前５世紀、スパルタ（対ペルシャ）

スキュタレー

転置式暗号

• 文書に書いた文字の順番を変える
• スキュタレー暗号
• レールフェンス暗号
  • 上段、下段に交互に文字を書く

解いてみよう

• しおろてやがぎみさつんいかたら
  • しろやぎさんからおてがみついた
• くさよたろんまべやたずたぎらに
• わみいうびつたみのみきかしはみのをしのかみひなむ

シーザー暗号

• 『ガリア戦記』
• ABCDEF... -> DEFGHI...
• 敵に包囲されて降伏寸前の味方に、伝令を送った
• 槍に手紙を付けて投げ込んだ
• 「すぐに行くからがんばれ！」
  • （こんなものでも暗号にするんですね）

換字式暗号

• 平文の各文字を別の文字で置き換える
• シーザー暗号は 3文字ずらす
• ずらす数を変えれば 25通りの暗号ができる
• どのように置き換えてもよければ 26! 通り
  • 26! = 403,291,461,126,605,635,584,000,000

解いてみよう

• （以下はシーザー暗号 ずらした文字数は 6以下）
• ERBV EH DPELWLRXV ( 次の行をドラッグ )
  • BOYS BE AMBITIOUS (3)
• YNRJ NX RTSJD
• PSWX XMQI MW RIZIV JSYRH EKEMR

暗号の方式と鍵

• スキュタレー暗号 ... 何文字で一周するスキュタレーを使うか
• シーザー暗号 ... 何文字ずらすか
• シーザー暗号に 限らない 換字式暗号なら、鍵が 400x1兆x1兆 (四百しorじょ:禾扁に予)
• 総当たりでは解けない

換字式暗号の鍵

• 鍵の作り方（例）
• "Yes we can" -> YESWCAN + N の次から
• ABCDEFGHIJKLMNOPQRSTUVWXYZ
  =>
  YESWCANOPQRTUVXZBDFGHIJKLM

暗号化の例

• There is not a black America and a white America, there's the United States of America
  =>
  GOCDC PF VXG Y ETYSR YUCDPSY YVW Y JOPGC YUCDPSY GOCDCF GOC HVPGCW FGYGCF XA YUCDPSY

換字式暗号を解く

• イスラム帝国アッバース朝（750-1258）
• 暗号通信を多用
• 暗号解読技術も発達
• 400x1兆x1兆 もの総当たりは不可能
• 文字の出現頻度を調べる
  • ETAOIN SHRDLU

英語の文字出現頻度

暗号文

IHF YV L RLAEOA DOVDO KO NLV VWF COCYNLFO  KO NLV VWF NWVDONALFO  KO NLV
VWF TLRRWK  FTYD EAWHVC FTO IALJO SOV RYJYVE LVC COLC KTW DFAHEEROC TOAO
TLJO NWVDONALFOC YF GLA LIWJO WHA XWWA XWKOA FW LCC WA COFALNFFTO KWARC
KYRR RYFFRO VWFO VWA RWVE AOSOSIOA KTLF KO DLP TOAO IHF YF NLV VOJOA
GWAEOF KTLF FTOP CYC TOAO YF YD GWA HD FTO RYJYVE ALFTOA FW IO COCYNLFOC
TOAO FW FTO HVGYVYDTOC KWAU KTYNT FTOP KTW GWHETF TOAO TLJO FTHD GLA DW
VWIRP LCJLVNOCYF YD ALFTOA GWA HD FW IO TOAO COCYNLFOC FW FTO EAOLF FLDU
AOSLYVYVE IOGWAO HD  FTLF GAWS FTODO TWVWAOC COLC KO FLUO YVNAOLDOC
COJWFYWV FW FTLF NLHDO GWA KTYNT FTOP ELJO FTO RLDF GHRR SOLDHAO WG
COJWFYWV FTLF KO TOAO TYETRP AODWRJO FTLF FTODO COLC DTLRR VWF TLJO CYOC
YV JLYV  FTLF FTYD VLFYWV HVCOA EWC DTLRR TLJO L VOK IYAFT WG GAOOCWS
LVC FTLF EWJOAVSOVF WG FTO XOWXRO IP FTO XOWXRO GWA FTO XOWXRO DTLRR VWF
XOAYDT GAWS FTO OLAFT

頻度解析

  108 O    74 F    57 T    56 W    56 L
   51 A    41 V    37 C    35 Y    28 D
   27 R    18 K    17 N    17 G    16 J
   15 H    15 E    11 I     9 X     9 S
    7 P     3 U

First Try

• OFT -> eta

IHt YV L RLAEeA DeVDe Ke NLV VWt CeCYNLte  Ke NLV VWt NWVDeNALte  Ke NLV
VWt aLRRWK  taYD EAWHVC tae IALJe SeV RYJYVE LVC CeLC KaW DtAHEEReC aeAe
aLJe NWVDeNALteC Yt GLA LIWJe WHA XWWA XWKeA tW LCC WA CetALNttae KWARC
KYRR RYttRe VWte VWA RWVE AeSeSIeA KaLt Ke DLP aeAe IHt Yt NLV VeJeA
GWAEet KaLt taeP CYC aeAe Yt YD GWA HD tae RYJYVE ALtaeA tW Ie CeCYNLteC
aeAe tW tae HVGYVYDaeC KWAU KaYNa taeP KaW GWHEat aeAe aLJe taHD GLA DW
VWIRP LCJLVNeCYt YD ALtaeA GWA HD tW Ie aeAe CeCYNLteC tW tae EAeLt tLDU
AeSLYVYVE IeGWAe HD  taLt GAWS taeDe aWVWAeC CeLC Ke tLUe YVNAeLDeC
CeJWtYWV tW taLt NLHDe GWA KaYNa taeP ELJe tae RLDt GHRR SeLDHAe WG
CeJWtYWV taLt Ke aeAe aYEaRP AeDWRJe taLt taeDe CeLC DaLRR VWt aLJe CYeC
YV JLYV  taLt taYD VLtYWV HVCeA EWC DaLRR aLJe L VeK IYAta WG GAeeCWS
LVC taLt EWJeAVSeVt WG tae XeWXRe IP tae XeWXRe GWA tae XeWXRe DaLRR VWt
XeAYDa GAWS tae eLAta

検証

• tae が多いね
• the じゃないの？

修正

• OFTW -> etha

IHt YV L RLAEeA DeVDe Ke NLV Vat CeCYNLte  Ke NLV Vat NaVDeNALte  Ke NLV
Vat hLRRaK  thYD EAaHVC the IALJe SeV RYJYVE LVC CeLC Kha DtAHEEReC heAe
hLJe NaVDeNALteC Yt GLA LIaJe aHA XaaA XaKeA ta LCC aA CetALNtthe KaARC
KYRR RYttRe Vate VaA RaVE AeSeSIeA KhLt Ke DLP heAe IHt Yt NLV VeJeA
GaAEet KhLt theP CYC heAe Yt YD GaA HD the RYJYVE ALtheA ta Ie CeCYNLteC
heAe ta the HVGYVYDheC KaAU KhYNh theP Kha GaHEht heAe hLJe thHD GLA Da
VaIRP LCJLVNeCYt YD ALtheA GaA HD ta Ie heAe CeCYNLteC ta the EAeLt tLDU
AeSLYVYVE IeGaAe HD  thLt GAaS theDe haVaAeC CeLC Ke tLUe YVNAeLDeC
CeJatYaV ta thLt NLHDe GaA KhYNh theP ELJe the RLDt GHRR SeLDHAe aG
CeJatYaV thLt Ke heAe hYEhRP AeDaRJe thLt theDe CeLC DhLRR Vat hLJe CYeC
YV JLYV  thLt thYD VLtYaV HVCeA EaC DhLRR hLJe L VeK IYAth aG GAeeCaS
LVC thLt EaJeAVSeVt aG the XeaXRe IP the XeaXRe GaA the XeaXRe DhLRR Vat
XeAYDh GAaS the eLAth

さらに検証

• aa とか ta とか変じゃない？
• oo, to じゃないの？

さらに修正

• OFTWL -> ethoa

IHt YV a RaAEeA DeVDe Ke NaV Vot CeCYNate  Ke NaV Vot NoVDeNAate  Ke NaV
Vot haRRoK  thYD EAoHVC the IAaJe SeV RYJYVE aVC CeaC Kho DtAHEEReC heAe
haJe NoVDeNAateC Yt GaA aIoJe oHA XooA XoKeA to aCC oA CetAaNtthe KoARC
KYRR RYttRe Vote VoA RoVE AeSeSIeA Khat Ke DaP heAe IHt Yt NaV VeJeA
GoAEet Khat theP CYC heAe Yt YD GoA HD the RYJYVE AatheA to Ie CeCYNateC
heAe to the HVGYVYDheC KoAU KhYNh theP Kho GoHEht heAe haJe thHD GaA Do
VoIRP aCJaVNeCYt YD AatheA GoA HD to Ie heAe CeCYNateC to the EAeat taDU
AeSaYVYVE IeGoAe HD  that GAoS theDe hoVoAeC CeaC Ke taUe YVNAeaDeC
CeJotYoV to that NaHDe GoA KhYNh theP EaJe the RaDt GHRR SeaDHAe oG
CeJotYoV that Ke heAe hYEhRP AeDoRJe that theDe CeaC DhaRR Vot haJe CYeC
YV JaYV  that thYD VatYoV HVCeA EoC DhaRR haJe a VeK IYAth oG GAeeCoS
aVC that EoJeAVSeVt oG the XeoXRe IP the XeoXRe GoA the XeoXRe DhaRR Vot
XeAYDh GAoS the eaAth

さらにさらに検証

• eaAth って何？
• earth じゃないの
• AatheA -> rather なんてのもあるし

さらにさらに修正

• OFTWLA -> ethoar

IHt YV a RarEer DeVDe Ke NaV Vot CeCYNate  Ke NaV Vot NoVDeNrate  Ke NaV
Vot haRRoK  thYD EroHVC the IraJe SeV RYJYVE aVC CeaC Kho DtrHEEReC here
haJe NoVDeNrateC Yt Gar aIoJe oHr Xoor XoKer to aCC or CetraNtthe KorRC
KYRR RYttRe Vote Vor RoVE reSeSIer Khat Ke DaP here IHt Yt NaV VeJer
GorEet Khat theP CYC here Yt YD Gor HD the RYJYVE rather to Ie CeCYNateC
here to the HVGYVYDheC KorU KhYNh theP Kho GoHEht here haJe thHD Gar Do
VoIRP aCJaVNeCYt YD rather Gor HD to Ie here CeCYNateC to the Ereat taDU
reSaYVYVE IeGore HD  that GroS theDe hoVoreC CeaC Ke taUe YVNreaDeC
CeJotYoV to that NaHDe Gor KhYNh theP EaJe the RaDt GHRR SeaDHre oG
CeJotYoV that Ke here hYEhRP reDoRJe that theDe CeaC DhaRR Vot haJe CYeC
YV JaYV  that thYD VatYoV HVCer EoC DhaRR haJe a VeK IYrth oG GreeCoS
aVC that EoJerVSeVt oG the XeoXRe IP the XeoXRe Gor the XeoXRe DhaRR Vot
XerYDh GroS the earth

こんなふうに、、、

• OFTWLAVCYDR -> ethoarndisl

IHt in a larEer sense Ke Nan not dediNate  Ke Nan not NonseNrate  Ke Nan
not halloK  this EroHnd the IraJe Sen liJinE and dead Kho strHEEled here
haJe NonseNrated it Gar aIoJe oHr Xoor XoKer to add or detraNtthe Korld
Kill little note nor lonE reSeSIer Khat Ke saP here IHt it Nan neJer
GorEet Khat theP did here it is Gor Hs the liJinE rather to Ie dediNated
here to the HnGinished KorU KhiNh theP Kho GoHEht here haJe thHs Gar so
noIlP adJanNedit is rather Gor Hs to Ie here dediNated to the Ereat tasU
reSaininE IeGore Hs  that GroS these honored dead Ke taUe inNreased
deJotion to that NaHse Gor KhiNh theP EaJe the last GHll SeasHre oG
deJotion that Ke here hiEhlP resolJe that these dead shall not haJe died
in Jain  that this nation Hnder Eod shall haJe a neK Iirth oG GreedoS
and that EoJernSent oG the XeoXle IP the XeoXle Gor the XeoXle shall not
Xerish GroS the earth

完成

• OFTWLAVCYDRKNGJHEIXSPU -> ethoarndislwcfvugbpmyk

but in a larger sense we can not dedicate  we can not consecrate  we can
not hallow  this ground the brave men living and dead who struggled here
have consecrated it far above our poor power to add or detractthe world
will little note nor long remember what we say here but it can never
forget what they did here it is for us the living rather to be dedicated
here to the unfinished work which they who fought here have thus far so
nobly advancedit is rather for us to be here dedicated to the great task
remaining before us  that from these honored dead we take increased
devotion to that cause for which they gave the last full measure of
devotion that we here highly resolve that these dead shall not have died
in vain  that this nation under god shall have a new birth of freedom
and that government of the people by the people for the people shall not
perish from the earth

もっと難しい暗号へ

• ルイ14世の大暗号
• ヴィジュネル暗号
• エニグマ

ルイ14世の大暗号

• ロシニョール父子 (1600年代)
• 字を単位にではなく、音節（対字）を単位にする
• 字に換えるのでなく、数字（３桁）に換える
  • 124-22-125-46-345 => les en-ne-mi-s (敵)
• バズリー (1890年頃) 解読に成功
  • 「鉄仮面」の秘密(?)

ヴィジュネル暗号

• ヴィジュネル方陣
  

ヴィジュネル暗号の例

• 鍵を KING とすると
• KIN GK ING KINGKIN GK
• but he has nothing on (でも、なんにも着てないよ)
• LCG NO PNY XWGNSVT UX

ヴィジュネル暗号の解読法

• チャールズ・バベッジ
  • 「階差機関」を設計、「解析機関」を構想（今日の計算機の原型）
• 繰り返し現れる文字列に注目
• その文字数から「鍵」の長さを推定
• 鍵の文字毎に暗号文中の文字の頻度分布をみる

教訓

• 暗号文が長い (長い間同じ鍵を使う) と解読しやすい
• 鍵を長く／乱雑な文字列にすると解読できない
  • が、実用的でない
• -> 暗号を作る機械の発明

エニグマ

• 第二次世界大戦 (1939-1945) ドイツ軍で使用
  

エニグマの機構

• スイッチ -> ローター（換字盤） -> リフレクター -> ローター -> ランプ（文字表示）
• ローターは 1文字毎に回転
• リフレクターはプラグボード（配線を変えられる）
• ローターの種類・初期位置、プラグボードの配線が鍵

エニグマの機構（図）

使い方 (ドイツ軍の)

• 日ごとに鍵を決めておく (日鍵)
• メッセージ毎にローターの初期位置を変える (メッセージ鍵)
• メッセージ鍵を日鍵を使って送る
• 鍵が合っていることを確かめる ... 最初に 3文字x2回の繰り返し

エニグマ暗号の解読

• 換字式 400x兆x兆
• ローター(3個)がわかれば
  • ローターの順 = 3! = 6
  • 各ローターの初期位置の組み合わせ = 26x26x26 =17576

エニグマ暗号の解読

• マリヤン・レイェフスキ (ポーランド)
• アラン・チューリング (イギリス)
• 鍵を見つけるための機械 (計算機) Bombe(a)
• スパイを泳がせニセ情報
• コードブックを奪取 (Uボート を捕獲)

現代の暗号

• 電子計算機が誰でも使える
• 共通鍵暗号と公開鍵暗号
• 文字種を多くする
• 26 文字 -> 鍵の数は最大 400x兆x兆 個
• DES 暗号 = 56bit = 8文字分
• 2⁵⁶ = 72,057,594,037,927,936 種類の文字 -> 鍵の最大数はその階乗
  • 実際には印字できる文字(94)が8文字 = 94⁸ = 6,095,689,385,410,816

まとめ

• 暗号には「方式」と「鍵」がある
• 使える鍵の数が多いと、破られにくい
• 同じ鍵を使い続けると、破られやすくなる
  • One Time Pad (乱数で生成) を使う方法もある
• 暗号化、解読の道具の進化
• 数学（統計）-> 機械 -> 計算機

ということで

• 次の講座に続きます