転置式暗号

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