シーザー暗号
![](http://upload.wikimedia.org/wikipedia/commons/thumb/4/4a/Caesar_cipher_left_shift_of_3.svg/320px-Caesar_cipher_left_shift_of_3.svg.png)
シーザー暗号(しーざーあんごう、英語: Caesar cipher)は、暗号理論上、もっともシンプルで、広く知られた暗号のひとつである[1]。カエサル式暗号[2]、シフト暗号[3]とも呼ばれる。
概要
シーザー暗号は単一換字式暗号の一種であり、平文の各文字を辞書順で3文字分シフトして(ずらして)暗号文とする暗号である[4]。古代ローマの軍事的指導者ガイウス・ユリウス・カエサル(英語読みでシーザー)が使用したことから、この名称がついた[3]。
文字のシフト数は固定であるが、3に限る必要はない。たとえば左に3文字分シフトさせる場合、「D」は「A」に置き換わり、同様に「E」は「B」に置換される。
シーザー暗号はヴィジュネル暗号などの部品として使用されることがあるほか、現代でもシフト数を13にした方式としてROT13が使用されることがある[5]。シーザー暗号は他の単一換字式暗号と同様、容易に解読されるので、今日においては有効ではない[1]。
きわめて単純な暗号であるが、現代の暗号においても重要な、規則(アルゴリズム)および鍵という2つの要素が既に含まれている。
- 規則
- 特定の文字を、それよりも辞書順に特定の数だけ後ろ(または前)にある文字と置き換える。
- 鍵
- 辞書順にずらす文字数。カエサルが実際に用いたシーザー暗号の場合、鍵は3である。
歴史
スエトニウスによれば、カエサルは秘密を必要とする場合、各文字をシフトして暗号を作成したといわれた。この手法を用いたのはカエサルが初めて戦の時に使用したと記録されているが、他の換字式暗号はより古い時期から使用されていたことが知られている[6]。
彼(カエサル)は、何か秘密にしたいことがあれば、暗号を用いてそれを記した。その暗号とは、単語が意味をなさないようにするため、アルファベットの順番を変えることによって作られた。それを解読し、意味を知りたいのならば、AをDにするように、アルファベットの順番で4番目に置き換える必要がある。—スエトニウス、『皇帝伝』(英語版) 1章「ユリウス・カエサル」56
カエサルの甥である アウグストゥスもまた同様に暗号を使っていたが、彼の使用していた暗号化は右に1つシフトするものであり、またアルファベットの始めにローテーションしないものであった。
彼(アウグストゥス)が暗号を記す際は、AをB、BをC、というように隣の文字を用いた。Xを記す際はAAを使った[注釈 1]。—スエトニウス、『皇帝伝』(英語版) 2章「アウグストゥス」88
カエサルはより複雑な暗号を使用していた可能性があり[7]、 アウルス・ゲッリウスは、カエサルの暗号についての、現在は失われた論文について言及している。
カエサルの書簡の文章内の文字に隠された意味については、文法家プロブスによって書かれた素晴らしい論文が存在する。—アウルス・ゲッリウス、『アッティカの夜』17.9.1–5
シーザー暗号が使用されていた当時、どの程度効果的であったかは不明である。しかし、少なからず合理的な秘匿方法ではあっただろう。なぜなら、カエサルの敵対者の多くは文盲であったであろうし、そうでなかったとしてもそれは未知の言語で記されていたであろうからだ[8]。この単純な換字式暗号に対する解読方法について、使用当時の記録はない。現存する中でもっとも古い記録は、9世紀のアラブ世界における、キンディによる頻度分析の発見である[9]。
ユダヤ教では、メズーザーの裏に神の名(英語版)を記す際に、1つシフトしたシーザー暗号を用いる。これは、メズーザーを使っていなかった時代から続けられていると思われる。暗号化された名前は宗教的に意味深い「神の名」を示し、それはオーソドックスなユダヤ教において、悪の力を退けるものとされる[10]。
19世紀には、新聞の個人広告欄がシンプルな暗号によるメッセージのやりとりにしばしば使われた。デビッド・カーン(英語版)は、タイムズ紙上で恋人同士が行った、シーザー暗号を使った秘密のやりとりについて言及している[11]。また、1915年という比較的近年であっても、シーザー暗号は使われていた。当時のロシア陸軍は、兵士が習得するのに難しすぎるために、より複雑な暗号からシーザー暗号へと変更した。そのため、ドイツやオーストリアの暗号解読者は、暗号文をたやすく復号することができた[12]。
デコーダーリング(英語版)のように、2枚の回転盤を組み合わせる事で、シーザー暗号の暗号化や復号を行うことができる。今日では子供向けの玩具などに見ることができる。
ネットニュースなどでは、一見しただけで読めてほしくない、しかし読もうと思えば誰でも読める文章(パズルの答えなど)を投稿するのにシーザー暗号が使われることがあり、この場合、鍵は伝統的に13にし、ROT13とも呼ばれる[5][13]。シーザー暗号を解読するためのコマンド(caesar(6))が標準装備されているUNIXシステムもある[14][15]。
ヴィジュネル暗号は、文章の文字ひとつひとつに異なったシフト数のシーザー暗号を用いている。シフト数は暗号鍵の単語を繰り返して決められる。暗号鍵がメッセージと同じ長さのランダムな文字列で、誰にも知られることなく、二度と使われることがないのであれば、それはワンタイムパッドとなり解読不能となる。だが、これらの条件を満たすことは実際には非常に難しい。暗号鍵がメッセージよりも短い場合[注釈 2]、頻度分析を統計的に拡張することで暗号文に周期的なパターンが検出される[16]。
作成手順と使用例
暗号化には二つのアルファベット列を使用する。暗号化のためのアルファベットは、通常のアルファベットを左、または右にいくつか循環シフト(ローテーション)させる。下図は、左に3文字の循環シフトをした場合のアルファベット列である。これは、右に23文字の循環シフトをした場合と同じである。シフトの方向およびシフトさせた個数はこの暗号の鍵として使用される。
通常のアルファベット: ABCDEFGHIJKLMNOPQRSTUVWXYZ 暗号化アルファベット: XYZABCDEFGHIJKLMNOPQRSTUVW
暗号化する場合は、「通常のアルファベット」列から平文の文字を探し、対応する「暗号化アルファベット」列の文字を書き出す。
平文: THE QUICK BROWN FOX JUMPS OVER THE LAZY DOG 暗号文: QEB NRFZH YOLTK CLU GRJMP LSBO QEB IXWV ALD
復号したい場合は逆をおこなえばよい。すなわち、右に3つ循環シフトさせる。
この暗号化の手順は合同算術を使用して表現することもできる。その場合、A = 0, B = 1, ..., Z = 25 のように、文字を数字に変換しておく[17]。文字 x を n 個のシフトで暗号化する場合を数学的に表現すると、下記となる[18]。
同様に、復号は下記となる。
プログラミングで実装する場合、使用する言語によって剰余演算の定義が異なる場合がある。上記の場合、結果は0以上25以下の範囲となるが、そうでない場合、26を加算する、もしくは減算する必要がある。
シーザー暗号の場合、文字の交換方式はメッセージ全体を通して同一である。このような暗号を単一換字式暗号と呼ぶ。対して、文字ごとに交換方式を変えるものを多表換字式暗号と呼ぶ。
シーザー暗号の解読
復号シフト | 取得される平文 |
---|---|
0 | exxegoexsrgi |
1 | dwwdfndwrqfh |
2 | cvvcemcvqpeg |
3 | buubdlbupodf |
4 | attackatonce |
5 | zsszbjzsnmbd |
6 | yrryaiyrmlac |
... | |
23 | haahjrhavujl |
24 | gzzgiqgzutik |
25 | fyyfhpfytshj |
シーザー暗号は暗号文単独攻撃によって簡単に解読することができる。以下の2つのシチュエーションを想定する。
- 攻撃者は何らかの単一換字式暗号が使われていることを知っている(もしくは推測している)が、それがシーザー暗号かどうかまでは分からない。
- 攻撃者はシーザー暗号が使われていることを知っているが、シフトの数が分からない。
はじめのケースでは、頻度分析や単語パターンなどの、一般的な単換字式暗号と同様の解読手法を使用することができる[19]。シーザー暗号は特徴的なアルゴリズムであるため、解読者はすぐに法則性に気づき、解読もしくは推測することができるだろう。
![](http://upload.wikimedia.org/wikipedia/commons/thumb/4/41/English-slf.png/320px-English-slf.png)
二番目のケースにおいては、より直接的に暗号解読を行える。英語であれば26通りといったように、シフト可能な数は限られているため、総当たり攻撃を試みることができる[20]。総当たり攻撃の一つの方法は、暗号文の一部をシフト可能な数だけ表に書き出してみる事である[21]。この方法は「completing the plain component」と呼ばれている[22]。例として、"EXXEGOEXSRGI"という暗号文があるとき、平文は4つシフトしたものであると、すぐに識別できる。もう一つの総当たり攻撃は、暗号文の各文字の下に、逆順にシフトさせたアルファベットすべてを記載していく方法である。この際、縦方向にアルファベットを逆順に並べた紙片を用意しておくとより手早く行うことができる。その紙片を使って暗号文を並べると、別のいずれかの列に平文が出現する。
文字の頻度分布と組み合わせることで、別の総当たり攻撃を試みることができる。暗号文に出現する文字の頻度のグラフと、使用されている言語の文字の分布期待値のグラフにより、人はグラフの特徴を比べることで、いくつシフトしているかを容易に発見することができるだろう。たとえば、英語の平文ではEやTが最も出現頻度が高く、QやZが最も出現頻度が低いといった特徴がある[23]。コンピュータを使用し、たとえばカイ二乗検定などを実施することでも、暗号文の出現頻度と平文の出現頻度の比較を行うこともできる[24]。
自然言語の場合、ほとんどの場合において解読結果は1通りに定まるが、平文が極端に短い場合、複数の解読候補が存在しうる。たとえば、英語において、"MPQY"という暗号文は"aden"または"know"と解読しうる。同様に、"ALIIP"は"dolls"または"wheel"に、"AFCCP"は"jolly"または"cheer"に変換しうる。詳細は判別距離を参照。
シーザー暗号による暗号化や復号を複数回行った場合でも、安全性に変化はない。なぜなら、A 個分のシフトと B 個分のシフトを別個に行ったとしても、それは (A + B) 個分のシフトを行ったものと同等だからである。数学的には複数の暗号鍵による暗号化を行ったとしても、それはひとつの群として扱われる[25]。
出典
- ^ a b Gustavus J. Simmons. “substitution cipher \”. Britannica.com. 2015年12月17日閲覧。
- ^ 金光滋、熊谷博竹、内販繁「暗号-歴史的観点から-」(pdf)『鹿児島工業高等専門学校研究報告.RESEARCH REPORTS OF KAGOSHIMA NATIONAL COLLEGE OF TECHNOLOGY』第45巻、鹿児島工業高等専門学校、2011年2月23日、53頁、ISSN 03899314、NCID AN00040002、2015年12月17日閲覧。
- ^ a b “White Paper : 簡単にわかる暗号の歴史”. デジサート・ジャパン合同会社. 2021年5月16日閲覧。
- ^ 今井秀樹「暗号技術の動向」(pdf)『情報処理学会研究報告電子化知的財産・社会基盤(EIP)』第2002巻57(2002-EIP-016)、情報処理学会、2002年6月22日、1-8頁、ISSN 09196072、NAID 110002675760、NCID AA11238429、2015年12月17日閲覧。
- ^ a b Schneier, Bruce (1996). Applied Cryptography (Second ed.). John Wiley & Sons. pp. 11. ISBN 0-471-11709-9
- ^ “A Brief History of Cryptography”. Cypher Research Laboratories (24 January 2006). 2016年1月4日閲覧。
- ^ Reinke, Edgar C. (December 1962). “Classical Cryptography”. The Classical Journal 58 (3): 114.
- ^ Pieprzyk, Josef; Thomas Hardjono; Jennifer Seberry (2003). Fundamentals of Computer Security. Springer. p. 6. ISBN 3-540-43101-2
- ^ Singh, Simon (2000). The Code Book. Anchor. pp. 14–20. ISBN 0-385-49532-3
- ^ Alexander Poltorak. “Mezuzah and Astrology”. chabad.org. 2008年6月13日閲覧。
- ^ Kahn, David (1967). The Codebreakers. pp. 775–6. ISBN 978-0-684-83130-5
- ^ Kahn, David (1967). The Codebreakers. pp. 631–2. ISBN 978-0-684-83130-5
- ^ Wobst, Reinhard (2001). Cryptology Unlocked. Wiley. p. 20. ISBN 978-0-470-06064-3
- ^ “NetBSD 6.1.5 - man page for caesar (netbsd section 6)”. Unix and Linux Forums. 2015年12月17日閲覧。
- ^ “Man page of CAESAR”. JM Project. 2015年12月17日閲覧。
- ^ Kahn, David (1967). The Codebreakers. ISBN 978-0-684-83130-5
- ^ Luciano, Dennis; Gordon Prichett (January 1987). “Cryptology: From Caesar Ciphers to Public-Key Cryptosystems”. The College Mathematics Journal 18 (1): 2–17. doi:10.2307/2686311. JSTOR 2686311.
- ^ Wobst, Reinhard (2001). Cryptology Unlocked. Wiley. p. 19. ISBN 978-0-470-06064-3
- ^ Beutelspacher, Albrecht (1994). Cryptology. Mathematical Association of America. pp. 9–11. ISBN 0-88385-504-6
- ^ Beutelspacher, Albrecht (1994). Cryptology. Mathematical Association of America. pp. 8–9. ISBN 0-88385-504-6
- ^ Leighton, Albert C. (April 1969). “Secret Communication among the Greeks and Romans”. Technology and Culture 10 (2): 139–154. doi:10.2307/3101474. JSTOR 3101474.
- ^ Sinkov, Abraham; Paul L. Irwin (1966). Elementary Cryptanalysis: A Mathematical Approach. Mathematical Association of America. pp. 13–15. ISBN 0-88385-622-0
- ^ Singh, Simon (2000). The Code Book. Anchor. pp. 72–77. ISBN 0-385-49532-3
- ^ Savarese, Chris (2002年7月15日). “The Caesar Cipher”. 2008年7月16日閲覧。
- ^ Wobst, Reinhard (2001). Cryptology Unlocked. Wiley. p. 31. ISBN 978-0-470-06064-3
注釈
- ^ 古典ラテン語において、アルファベットの最後の文字はXであった。
- ^ たとえば、アメリカ南北戦争において、南部連合は「Complete Victory」といった、短いフレーズの暗号鍵を3つ使用していた。
参考文献
- デビッド・カーン(英語版), The Codebreakers – The Story of Secret Writing, Revised ed. 1996. ISBN 0-684-83130-9.
- F.L. Bauer(英語版), Decrypted Secrets, 2nd edition, 2000, Springer. ISBN 3-540-66871-3.
- Chris Savarese and Brian Hart, The Caesar Cipher, 1999
外部リンク
![Spoken Wikipediaのアイコン](http://upload.wikimedia.org/wikipedia/commons/thumb/4/47/Sound-icon.svg/45px-Sound-icon.svg.png)
- Weisstein, Eric W. "Caesar's Method". mathworld.wolfram.com (英語).
- 最小二乗法を用いたシーザー暗号の解読