[Python]単一換字式暗号の解読/暗号化の考え方・ソースコード

後輩にアフィン暗号を解けたと伝えたら、「換字暗号やってください」と言われた。今度のは大変だから心して解けと言われた。

まぁ、全くわからないのでwebで参考になりそうなサイトを探しながら解いてみた。

1 換字暗号/単一換字式暗号とは
2 暗号文/問題文
3 解読
4 暗号化

換字暗号/単一換字式暗号とは

単一換字式暗号（たんいつかえじしきあんごう、Simple substitution cipher）

暗号文の文字が常に同じ文字に変換されるような暗号のこと。例えば、平文の“d”が、暗号文で必ず“a”になるならば、それは単一換字式暗号である。

解読法
単一換字式暗号の解読には頻度分析が有効である。 wikipediaより

なるほど

アルファベットを特定の数順だけずらすシーザー暗号は、最も簡単な換字式暗号の一つ。今回はそれぞれのアルファベットが異なるアルファベットにずらされる。

シーザー暗号の場合、最大でも26通りだけど、アルファベットをランダムに置き換えるとパターンは２６の階乗通りある。虱潰しだと厳しそうだ。意味が通っているか否かをチェックする労力がめちゃくちゃ大変そう…。

~~いや、総当りして、意味が通じるのを自動識別…とかする方法もありか?できるものかな？~~

~~パターンが多すぎる?とりあえず考えないことにした。~~

そこでアルファベットの頻度分析が役に立つようだ。

頻度分析 (暗号)

英語の一般的な文章の場合、アルファベット（単文字）を数え上げてヒストグラムを作成すると（右図参照）、概ね e, t, a, o, i, n, …, j, x, q, z の順で出現することが分る。同様に2文字（連接文字）の場合、t-h, h-e, i-n, e-r, … 、3文字の場合には、t-h-e, a-n-d, i-n-g, i-o-n, … などの順で出現頻度が高いことが知られている。連接文字の場合、’q’ の次には ‘u’ が出現するなどの条件付きの出現頻度に特徴がある場合もある。この特徴を連接特徴という。さらにスペース（単語の区切り）が判明する場合には、単語の出現頻度を利用できる。

解読作業は出現頻度などの統計量を手掛りに、1文字ずつ平文の文字を推定して、矛盾がでたら一つ戻って次の文字を試すことを繰り返す。 wikipediaより

暗号文/問題文

JOLCQWBICH PT HKCIZPRX KPZYCH

WP HKCIZPRX KPZYCH HKC UH JZAJVH _WKC_ APYJQ. U KJLC HCZOPY KCJIO
KUY YCQWUPQ KCI BQOCI JQV PWKCI QJYC. UQ KUH CVCH HKC CRZUSHCH JQO
SICOPYUQJWCH WKC AKPZC PT KCI HCF. UW AJH QPW WKJW KC TCZW JQV CYPWUPQ
JXUQ WP ZPLC TPI UICQC JOZCI. JZZ CYPWUPQH, JQO WKJW PQC SJIWURBZJIZV,
ACIC JEKPIICQW WP KUH RPZO, SICRUHC, EBW JOYUIJEZV EJZJQRCO YUQO. KC
AJH, U WJXC UW, WKC YPHW SCITCRW ICJHPQUQD JQO PEHCILUQD YJRKUQC WKJW
WKC APIZO KJH HCCQ; EBW, JH J ZPLCI, KC APBZO KJLC SZJRCO KUYHCZT UQ J
TJZHC SPHUWUPQ. KC QCLCI HSPXC PT WKC HPTWCI SJHHUPQH, HJLC AUWK J DUEC
JQO J HQCCI. WKCV ACIC JOYUIJEZC WKUQDH TPI WKC PEHCILCI-CFRCZZCQW
TPI OIJAUQD WKC LCUZ TIPY YCQ’H YPWULCH JQO JRWUPQH. EBW TPI WKC
WIJUQCO ICJHPQCI WP JOYUW HBRK UQWIBHUPQH UQWP KUH PAQ OCZURJWC JQO
TUQCZV JONBHWCO WCYSCIJYCQW AJH WP UQWIPOBRC J OUHWIJRWUQD TJRWPI AKURK
YUDKW WKIPA J OPBEW BSPQ JZZ KUH YCQWJZ ICHBZWH. DIUW UQ J HCQHUWULC
UQHWIBYCQW, PI J RIJRX UQ PQC PT KUH PAQ KUDK-SPACI ZCQHCH, APBZO QPW
EC YPIC OUHWBIEUQD WKJQ J HWIPQD CYPWUPQ UQ J QJWBIC HBRK JH KUH. JQO
VCW WKCIC AJH EBW PQC APYJQ WP KUY, JQO WKJW APYJQ AJH WKC ZJWC UICQC
JOZCI, PT OBEUPBH JQO MBCHWUPQJEZC YCYPIV.

…長いので省略…

“QCLCI YUQO KUY. U YJV AJQW VPBI KCZS, JQO HP YJV KC. KCIC KC RPYCH.
HUW OPAQ UQ WKJW JIY-RKJUI, OPRWPI, JQO DULC BH VPBI ECHW JWWCQWUPQ.”

J HZPA JQO KCJLV HWCS, AKURK KJO ECCQ KCJIO BSPQ WKC HWJUIH JQO UQ WKC
SJHHJDC, SJBHCO UYYCOUJWCZV PBWHUOC WKC OPPI. WKCQ WKCIC AJH J ZPBO JQO
JBWKPIUWJWULC WJS.

“RPYC UQ!” HJUO KPZYCH.

※上記暗号文を今後は文字列”string”として扱う。

とりあえず頻度分析

str_list = list(string)
eigo = ['A','B','C','D','E','F','G','H','I','J','K','L','M','N','O','P','Q','R','S','T','U','V','W','X','Y','Z']
for i in eigo:
    print(i, str_list.count(i))

str_list = list(string)

eigo = ['A','B','C','D','E','F','G','H','I','J','K','L','M','N','O','P','Q','R','S','T','U','V','W','X','Y','Z']

for i in eigo:

print(i, str_list.count(i))

出力結果

A 197

B 248

C 990

D 135

E 120

F 12

G 4

H 540

I 452

J 660

K 484

L 82

M 8

N 6

O 325

P 637

Q 522

R 214

S 136

T 167

U 587

V 181

W 688

X 63

Y 240

Z 307

一番多く出現しているのは”C”で、頻度分析に従うと、これはおそらく”E”になりそう。

スペースが空いているので、1文字の”U”と”J”がわかりやすい。
1文字英単語は”I”か”A”のどちらかに絞れる。

頻度分析では”U”が587回、”J”が660回出現している。
“I”と”A”では”A”の方が出現頻度が高いみたいだ。

…まぁ、頻度分析しなくても、”J”は文の中間で頻出しているので、英文法的に「I」の可能性は低い。

よって”U”が”I”、”J”が”A”だとわかる。

次に、スペースで区切った場合の頻度分析を行う。

buf = string.split()

import collections
c = collections.Counter(buf)
print(c)

buf = string.split()

import collections

c = collections.Counter(buf)

print(c)

出力結果

Counter({'WKC': 78, 'JQO': 64, 'PT': 59, 'J': 57, 'WP': 46, 'U': 44, 'KUH': 37, 'VPB': 33, 'UQ': 27, 'KC': 25,
 'UH': 21, 'AJH': 21, 'WKJW': 21, 'UW': 19, ...省略...

1 2	Counter({'WKC': 78, 'JQO': 64, 'PT': 59, 'J': 57, 'WP': 46, 'U': 44, 'KUH': 37, 'VPB': 33, 'UQ': 27, 'KC': 25, 'UH': 21, 'AJH': 21, 'WKJW': 21, 'UW': 19, ...省略...

“WKC”と”JQO”という3文字のアルファベットが頻出している。

3文字で頻度の多いものは”THE”と”AND”。

先程”J”は”A”だとわかったので、”JQO”は”AND”の可能性が非常に高い。
ということは、”WKC”は”THE”。

ここまでわかるとかなりわかってくる。

dict = {

'J':'A',
'U':'I',

#'J':'A',
'Q':'N',
'O':'D',

'W':'T',
'K':'H',
'C':'E',

}
table = str.maketrans(dict)
buf = string.translate(table)
print(buf)

dict = {

'J':'A',

'U':'I',

#'J':'A',

'Q':'N',

'O':'D',

'W':'T',

'K':'H',

'C':'E',

}

table = str.maketrans(dict)

buf = string.translate(table)

print(buf)

出力例

“THIH IH INDEED A YVHTEIV,” I IEYAIXED. “AHAT DP VPB IYADINE THAT IT
YEANH?”

“I HALE NP DATA VET. IT IH A RASITAZ YIHTAXE TP THEPIIGE EETPIE PNE HAH
DATA. INHENHIEZV PNE EEDINH TP TAIHT TARTH TP HBIT THEPIIEH, INHTEAD PT
THEPIIEH TP HBIT TARTH. EBT THE NPTE ITHEZT. AHAT DP VPB DEDBRE TIPY
IT?”

I RAIETBZZV EFAYINED THE AIITIND, AND THE SASEI BSPN AHIRH IT AAH
AIITTEN.

“THE YAN AHP AIPTE IT AAH SIEHBYAEZV AEZZ TP DP,” I IEYAIXED,
ENDEALPIIND TP IYITATE YV RPYSANIPN’H SIPREHHEH. “HBRH SASEI RPBZD NPT
EE EPBDHT BNDEI HAZT A RIPAN A SARXET. IT IH SERBZIAIZV HTIPND AND
HTITT.”

だいぶわかりやすくなってきた。

まぁ、あとは、クイズのような感じで1つずつ埋めていく。

上記の例だと”IT IH”は”IT IS”だろうなとか。

(高頻度で出現する)”PT”や”WP”はよく使われる前置詞なんだろうなぁとか。

できた。

dict = {
'A':'W',
'B':'U',
'C':'E',
'D':'G',
'E':'B',
'F':'X',
'G':'Z',
'H':'S',
'I':'R',
'J':'A',
'K':'H',
'L':'V',
'M':'Q',
'N':'J',
'O':'D',
'P':'O',
'Q':'N',
'R':'C',
'S':'P',
'T':'F',
'U':'I',
'V':'Y',
'W':'T',
'X':'K',
'Y':'M',
'Z':'L',
}
table = str.maketrans(dict)
unciphered_text = string.translate(table)
print(unciphered_text)

dict = {

'A':'W',

'B':'U',

'C':'E',

'D':'G',

'E':'B',

'F':'X',

'G':'Z',

'H':'S',

'I':'R',

'J':'A',

'K':'H',

'L':'V',

'M':'Q',

'N':'J',

'O':'D',

'P':'O',

'Q':'N',

'R':'C',

'S':'P',

'T':'F',

'U':'I',

'V':'Y',

'W':'T',

'X':'K',

'Y':'M',

'Z':'L',

}

table = str.maketrans(dict)

unciphered_text = string.translate(table)

print(unciphered_text)

解読

ADVENTURES OF SHERLOCK HOLMES

TO SHERLOCK HOLMES SHE IS ALWAYS _THE_ WOMAN. I HAVE SELDOM HEARD
HIM MENTION HER UNDER ANY OTHER NAME. IN HIS EYES SHE ECLIPSES AND
PREDOMINATES THE WHOLE OF HER SEX. IT WAS NOT THAT HE FELT ANY EMOTION
AKIN TO LOVE FOR IRENE ADLER. ALL EMOTIONS, AND THAT ONE PARTICULARLY,
WERE ABHORRENT TO HIS COLD, PRECISE, BUT ADMIRABLY BALANCED MIND. HE
WAS, I TAKE IT, THE MOST PERFECT REASONING AND OBSERVING MACHINE THAT
THE WORLD HAS SEEN; BUT, AS A LOVER, HE WOULD HAVE PLACED HIMSELF IN A
FALSE POSITION. HE NEVER SPOKE OF THE SOFTER PASSIONS, SAVE WITH A GIBE
AND A SNEER. THEY WERE ADMIRABLE THINGS FOR THE OBSERVER-EXCELLENT
FOR DRAWING THE VEIL FROM MEN’S MOTIVES AND ACTIONS. BUT FOR THE
TRAINED REASONER TO ADMIT SUCH INTRUSIONS INTO HIS OWN DELICATE AND
FINELY ADJUSTED TEMPERAMENT WAS TO INTRODUCE A DISTRACTING FACTOR WHICH
MIGHT THROW A DOUBT UPON ALL HIS MENTAL RESULTS. GRIT IN A SENSITIVE
INSTRUMENT, OR A CRACK IN ONE OF HIS OWN HIGH-POWER LENSES, WOULD NOT
BE MORE DISTURBING THAN A STRONG EMOTION IN A NATURE SUCH AS HIS. AND
YET THERE WAS BUT ONE WOMAN TO HIM, AND THAT WOMAN WAS THE LATE IRENE
ADLER, OF DUBIOUS AND QUESTIONABLE MEMORY.

…省略…

“NEVER MIND HIM. I MAY WANT YOUR HELP, AND SO MAY HE. HERE HE COMES.
SIT DOWN IN THAT ARM-CHAIR, DOCTOR, AND GIVE US YOUR BEST ATTENTION.”

A SLOW AND HEAVY STEP, WHICH HAD BEEN HEARD UPON THE STAIRS AND IN THE
PASSAGE, PAUSED IMMEDIATELY OUTSIDE THE DOOR. THEN THERE WAS A LOUD AND
AUTHORITATIVE TAP.

“COME IN!” SAID HOLMES.

…謎は解けたよ、ワトソン君

暗号化

def encrypt(input_text, cipher_alphabet):
    alphabet = 'ABCDEFGHIJKLMNOPQRSTUVWXYZ'
    encryption = ''

    for i in input_text:
        #input_textにスペースが入った場合の処理
        if i == " ":
            encryption += " "
            continue

        index = alphabet.index(i)
        encryption += cipher_alphabet[index]
    return encryption

#左から順に、通常のアルファベット順(ABCDEFG...)と対応する。
#この場合、AとV、BとW、CとX...が置き換わる。
cipher_alphabet = 'VWXYZABCDEFGOPQRSTUHIJKLMN'

#大文字アルファベットで入力
input_text = "AAA"
result = encrypt(input_text, cipher_alphabet)
print(result)

# 出力結果
# VVV

input_text = "I HAVE A PEN"
result = encrypt(input_text, cipher_alphabet)
print(result)

# 出力結果
# D CVJZ V RZP