転置式暗号
転置式暗号（てんちしきあんごう、Transposition cipher）は平文の文字を並べ替えて暗号文を作成する暗号のことである。文字を別の文字、記号に置き換える換字式暗号とともに、古典的な暗号の1つであり、16世紀頃には換え字式、転置式という分類がされている。
概要
[編集]
転置式暗号とは、たとえて言えば席替えである。その「場合の数」は多く、例えば6文字の並べ方は6!（6の階乗）すなわち720通りある。40文字を並べ替えるとき、文字の並べ方は40!（48桁の数）通りもあり、解読は不可能かと思われる。しかし、40!の中には元の平文と同一のものや、その一部に「こうきげせよ」（平文「こうげきせよ」の3文字目と4文字目を交換しただけ）など、明らかに推測されやすいものも含まれている。また、並べ替えの順序があまり複雑すぎると、暗号化と復号がしにくくなり、厄介である（例えば1,000文字の文をどう並べ替えるか、書くだけでも大変であろう）。したがって、多くの場合、並べ替えの方法には規則性があった。
しかしコンピュータを利用した擬似乱数を利用する事で非常に多くの置換群が表現できる様になり、並べ替えの方法も現代では無限に程近くなっている。転置式暗号ではブロック分けが必須で、最大の並べ替え数はブロック長の階乗に比例する大きさを持つ事になる。
紀元前5世紀にはスパルタでスキュタレー暗号が使用された。ある特定の太さの棒に紙（皮ひもやパピルス）を巻きつけ、文字を棒に沿って書いていき、ほどいてから送る。紙の上には、元の文字が一定の間隔で散らばる。届いた紙を同じ太さの棒に巻きつければ読める。
種類
[編集]- 図形を使う方法（図形転置式）
- k×k（kは偶数）の正方形に並んだ升目の板（グリル）の、一見でたらめな位置に孔（あな）を開け、そこから下の紙に文字を書き込んでいく。すべての孔に書き込んだら、グリルを90度回転して続きを書く。これを4回行ってすべての升目の位置を文字で埋める。グリルを回転したときの同じ位置（例えば4隅）のうち1箇所にしか孔が開けられない。したがって、孔の個数は k2/4 になる。
- 鍵を使った方法（鍵式転置式）
- 定められた鍵の順番を使って、暗号文を作り出す方法。ADFGVX暗号の並べ替えもこれ。
- 上記の方法を2度使う方法（二重転置式）
- 鍵式転置式を使った後、空間転置式を使うなど。
解析
[編集]一般的に、転置式暗号では、文字数を n とするとき並べ方は n!−1（−1 は元の平文の分）の可能性があるが、先にも述べたように有用な数はもっと少ない。また、例えば3文字の場合、平文「あいう」は「うあい」など5つが考えられる。しかし、たかが5つではすぐに解読者は6つ目の平文「あいう」に行き着くだろう。並べ替えの単位（ブロック）となる文字数 n が少ないと並べ替えの総数が少なく、多いと暗号化と復号が困難になるなど、難点が多い。よって、比較的単純な転置式暗号を、換え字式暗号と組み合わせて用いることが多かったと言われている。
どの種類の転置式暗号も、n 文字のブロック内での位置の変更にすぎない。これは、数学的には「置換」として表現できる。例えば「あいう」を「うあい」とする並べ替えは、結果の暗号文における各文字の、元の平文での位置を並べた列
- (3 1 2)
として表現できる。この置換の総数は n! 通りある（上記のとおり）。
ただし、解読する側にとってすべてを試すには、厄介な面もある。例えば「しだこいなさくたんろ」のすべての可能性を試すと、「さだくんころしたいな→佐田君、殺したいな」、「しろいこなたくさんだ→白い粉、沢山だ」など、意味が通る文が2つ以上できてしまう可能性がある。
解読には、文字の連接特徴（どの文字の次にどの文字が現れやすいか）を用いる。2文字の連接のしやすさは、遷移確率の行列として表すことができる。
関連項目
[編集] | この項目は、工学・技術に関連した書きかけの項目です。この項目を加筆・訂正などしてくださる協力者を求めています（Portal:技術と産業）。 |
