寝癖頭の解法

小学生の目線から、勉強中の覚え書きを投稿、更新していきます。

シーザー暗号について

シーザー暗号についての話です。
きっかけは、第6回日本情報オリンピック予選の過去問からの出題でした。
https://onlinejudge.u-aizu.ac.jp/problems/0512

シーザー暗号とは、Wikipediaによれば...
>シーザー暗号は暗号理論上、もっともシンプルで、広く知られた暗号のひとつである。
>カエサル式暗号、シフト暗号とも呼ばれる。
ja.wikipedia.org
古代ローマの軍事的指導者で政治家だった、ガイウス・ユリウス・カエサル(Gaius Julius Caesar)が使用したことが由来みたいです。

暗号としては...
>シーザー暗号は単一換字式暗号の一種であり、平文の各文字を辞書順で3文字分シフトして(ずらして)暗号文とする暗号である。
>文字のシフト数は固定であるが、3に限る必要はない。
>たとえば左に3文字分シフトさせる場合、「D」は「A」に置き換わり、同様に「E」は「B」に置換される。
>ヴィジュネル暗号などの部品として使用されることがあるほか、現代でもシフト数を13にした方式としてROT13が使用されることがある。
>きわめて単純な暗号であるが、現代の暗号においても重要な、規則(アルゴリズム)および鍵という2つの要素が既に含まれている。

規則としては...
>特定の文字を、それよりも辞書順に特定の数だけ後ろ(または前)にある文字と置き換える。

鍵については...
>辞書順にずらす文字数。
>カエサルが実際に用いたシーザー暗号の場合、鍵は3である。

作成手順については...
>暗号化には二つのアルファベット列を使用する。
>暗号化のためのアルファベットは、通常のアルファベットを左、または右にいくつか循環シフト(ローテーション)させる。
>シフトの方向およびシフトさせた個数は、この暗号の鍵として使用される。
>プログラミングで実装する場合、使用する言語によって剰余演算の定義が異なる場合がある。
>シーザー暗号の場合、文字の交換方式はメッセージ全体を通して同一である。
>このような暗号を単一換字式暗号と呼ぶ。
>対して、文字ごとに交換方式を変えるものを多表換字式暗号と呼ぶ。

そして、第6回日本情報オリンピック予選の過去問からの出題では...
大文字のアルファベット 26 文字だけからなる文字列を,カエサルがしたように3文字ずつずらす変換を施し得られた文字列がある.
このような文字列を元の文字列に戻すプログラムを作成せよ.

僕が作成、提出したコードは、以下のとおりです。

Aizu Online Judge in C++ #Volume5 - 0512 : Caesar Cipher
/*
Aizu Online Judge in C++ #Volume5 - 0512 : Caesar Cipher
https://onlinejudge.u-aizu.ac.jp/problems/0512
提出コードの解答例
https://neguse-atama.hatenablog.com
*/
#include<bits/stdc++.h>
using namespace std;
int main(void){
  string s;
  cin>>s;
  char c[26];
  for(int i=1;i<=26;i++){
    if(i<=23){
      c[i-1]=(char)i+67;
    }else{
      c[i-1]=(char)i+41;
    }
  }
  for(int i=0;i<s.size();i++){
    for(int j=0;j<26;j++){
      if(s[i]==c[j]){
        char ans=(char)j+65;
        cout<<ans;
      }
    }
  }
  cout<<endl;
  return 0;
}

>シーザー暗号は他の単一換字式暗号と同様、容易に解読されるので、今日においては有効ではない。
僕がパっと見ただけでも解けてしまえる程度だから、たしかにその通りだと思いました。
あっ、でもミスリードを目的とするならば、あえて読ませるために現在でも使えそうです。

歴史としては...
>スエトニウスによれば、カエサルは秘密を必要とする場合、各文字をシフトして暗号を作成したといわれた。
>この手法を用いたのはカエサルが初めてであると記録されているが、他の換字式暗号はより古い時期から使用されていたことが知られている。
>カエサルの甥である アウグストゥスもまた同様に暗号を使っていたが、彼の使用していた暗号化は右に1つシフトするものであり、またアルファベットの始めにローテーションしないものであった。
当時の時代背景として、カエサルの敵対者の多くが文盲だったらしくて、またカエサルはより複雑な暗号を使用していた可能性が、アウルス・ゲッリウスの『アッティカの夜』で言及されているそうです。

>19世紀には、新聞の個人広告欄がシンプルな暗号によるメッセージのやりとりにしばしば使われた。
>また、1915年という比較的近年であっても、シーザー暗号は使われていた。
>当時のロシア陸軍は、兵士が習得するのに難しすぎるために、より複雑な暗号からシーザー暗号へと変更した。
>そのため、ドイツやオーストリアの暗号解読者は、暗号文をたやすく復号することができた。
だから、2枚の回転盤を組み合わせる事で、シーザー暗号の暗号化や復号を行うことができる『デコーダーリング』と言う玩具もあるみたいです。

そして、現在では...
>ネットニュースなどでは、一見しただけで読めてほしくない、しかし読もうと思えば誰でも読める文章(パズルの答えなど)を投稿するのにシーザー暗号が使われることがあり、この場合、鍵は伝統的に13にし、ROT13とも呼ばれる。

それから、ヴィジュネル暗号については...
ja.wikipedia.org
>フランスの外交官ブレーズ・ド・ヴィジュネルによる多表式の換字式暗号のことである。
>ヴィジュネル暗号は、文章の文字ひとつひとつに異なったシフト数のシーザー暗号を用いている。
>シフト数は暗号鍵の単語を繰り返して決められる。
>暗号鍵がメッセージと同じ長さのランダムな文字列で、誰にも知られることなく、二度と使われることがないのであれば、それはワンタイムパッドとなり解読不能となる。
>暗号鍵がメッセージよりも短い場合、頻度分析を統計的に拡張することで暗号文に周期的なパターンが検出される。

終わりに、まとめとして...
>シーザー暗号の場合、文字の交換方式はメッセージ全体を通して同一である。
>このような暗号を単一換字式暗号と呼ぶ。
>対して、文字ごとに交換方式を変えるものを多表換字式暗号と呼ぶ。
>シーザー暗号による暗号化や復号を複数回行った場合でも、安全性に変化はない。
>なぜなら、A 個分のシフトと B 個分のシフトを別個に行ったとしても、それは (A + B) 個分のシフトを行ったものと同等だからである。
>数学的には複数の暗号鍵による暗号化を行ったとしても、それはひとつの群として扱われる。

「問題を解く」と言うことについて、今の自分のレベルにとっては難しかったりすると、その直後に達成感みたいなものが得られるのだけれど、こうして枝葉を知れたりするのも面白いなーって、最近は実感しています。

設問の出典は、第6回日本情報オリンピック 予選(過去問)です。
問題は、"AtCoder Problems"でも公開されています。
atcoder.jp