Pythonで単一換字式暗号(アルファベット、英語)の解読をしてみた。

# はじめに
この暗号、解読できますか？
![sentence1.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3775294/09fca86f-1e6c-e0ff-70b3-45f5f27cdb61.png)

自然言語処理を学んでいて思い出したのがシャーロックホームズの踊る人形であった。
ホームズは優れた状況判断能力を活かし、さらに頻度分析を用いて暗号を解読していた。
私にもPythonを用いて暗号解読できそうな気がしたのでこの記事を作成した。
単純な換字式暗号（アルファベット、英語）の解読を試みる。

（この暗号は下記サイトを利用して作った。そもそも踊る人形にでてくる暗号表記のため解読表が存在するのだが、今回は解読表がないものとして利用する。）
<br>
**解読できる暗号の想定**
・単純な換字式暗号文であること。（図形にはアルファベットが割り振られている）
・文章は簡単な英語であるという想定。
・単語間にちゃんとスペースがある。
・特殊な記号、特殊な固有名詞は使われていないものとする。

# 手順１：単語一覧の前処理
一致させる単語の一覧を準備する。
今回は単純に一通りの単語が網羅されている単語一覧が欲しかったため、使い勝手の良さそうなこちらからデータセットを拝借した。
https://github.com/kujirahand/EJDict

UTF-8の形式を選び、前処理を行っていく。

```python
with open('ejdict-hand-utf8.txt', 'r', encoding='utf-8') as word_file:
    word_list = word_file.read()
    print(word_list)
```
結果
![ejdict-hand-utf8.jpg](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3775294/02b19b22-990c-ee78-5d6b-b75182c240f7.jpeg)
このようなデータセットが入っているため加工していく。

```python
import pandas as pd
#扱いやすいようにデータフレーム化する。
df_word_list = pd.read_csv('ejdict-hand-utf8.txt', encoding='utf-8', delimiter='\t')

#今回日本語訳はいらないため削除する。
df_word_list = df_word_list[['ENGLISH']]

#データ型を文字列型に統一する。
df_word_list = df_word_list.astype(str)

#検索に影響しないよう、すべて大文字に変換しておく。
df_word_list.loc[:, 'ENGLISH'] = df_word_list['ENGLISH'].apply(lambda x: x.upper())

#単語ごとに※ユニット番号をつける。
def num_per_word(word):
    char_to_number = {}
    current_number = 1
    result = []
    for char in word:
        if char not in char_to_number:
            char_to_number[char] = current_number
            current_number += 1
        result.append(char_to_number[char])
    return result

_num_per_word = df_word_list['ENGLISH'].apply(num_per_word)
df_word_list['ENCODE'] = _num_per_word

df_word_list
```
結果
![dataset_df.jpg](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3775294/6b50360c-3e1e-58ad-78cc-25bc270f6e36.jpeg)
※ユニット番号
以下の条件で振り分けた番号のこと。
1.始めて出てきたアルファベットに1から順に数字を振っていく。
2.同じアルファベットが出てきたら同じ番号を振る。

# 手順２：文章全体の準備

手順１とはまた別に単語毎に番号を振り分ける。（目視作業）

![sentesnce1_num.jpg](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3775294/b008e138-d037-ff15-d0a6-1d426cc1f865.jpeg)

1.始めて出てきた図形に1から順に数字を振っていく。
2.同じ図形が出てきたら同じ番号を振る。

```python
word_1 = [1]
word_2 = [2, 3]
word_3 = [1, 4, 5, 6, 7, 6, 8, 5, 6, 9]
word_4 = [1, 4]
word_5 = [9, 2, 5, 2]
word_6 = [8, 10, 1, 6, 4, 10, 6]

words = [word_1, word_2, word_3, word_4, word_5, word_6]
sentence = '  '.join(' '.join(map(str, sublist)) for sublist in words)
sentence
```

```:結果
'1  2 3  1 4 5 6 7 6 8 5 6 9  1 4  9 2 5 2  8 10 1 6 4 10 6'
```

3.スペースごとに番号をリストに入れ各単語を想定した変数を作る。
4.最終的に完成させたい文章の箱を作る

# 手順３：単語毎の準備

手順２とは別に、出現単語毎にユニット番号を振る。（目視作業）

```python
unit_1 = [1]
unit_2 = [1, 2]
unit_3 = [1, 2, 3, 4, 5, 4, 6, 3, 4, 7]
unit_4 = [1, 2]
unit_5 = [1, 2, 3, 2]
unit_6 = [1, 2, 3, 4, 5, 2, 4]
```


単語一覧と出現単語のユニットが一致するものを抽出する関数を用意する。

```python
def narrow_down (unit_num):
    matched_unit = df_word_list[df_word_list['ENCODE'].apply(lambda x: x == unit_num)]
    return matched_unit
```
```python
narrow_down(unit_num)
```

このような結果が得られる
![narrow_down_unit.jpg](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3775294/3864efb9-1691-acf9-3add-62a8fb85512f.jpeg)

<br>

**unit毎の解釈**

```python
def print_candidate(num, unit_num):
    result = narrow_down(unit_num).shape[0]
    return print(f'word_{num}の候補数は、 {result} 個')

word_nums = [1, 2, 3, 4, 5, 6]
units = [unit_1, unit_2, unit_3, unit_4, unit_5, unit_6]
for i, unit_i in zip(word_nums, units):
    print_candidate(i, unit_i)
```

```:結果
word_1の候補数は、 31 個
word_2の候補数は、 307 個
word_3の候補数は、 3 個
word_4の候補数は、 307 個
word_5の候補数は、 176 個
word_6の候補数は、 11 個
```

候補数を降順にすると、
word_3 < word_6 < word_1 ……となる。
候補数の少ない順にwordに当てはめた数字をさらに絞り込んでいけそうだ。

# 手順４：暗号解読
候補数の少ないword_3を確認してみる。

```python
print(word_3)
narrow_down(unit_3)['ENGLISH']
```

```:結果
[1, 4, 5, 6, 7, 6, 8, 5, 6, 9]
1651     ANTIBIOTIC
21111    INTERESTED
28096    OPTIMISTIC
Name: ENGLISH, dtype: object
```

この結果をリストに入れておく。

```python
candidate_word_3_1 = list(narrow_down(unit_3).loc[1651, 'ENGLISH'])
candidate_word_3_2 = list(narrow_down(unit_3).loc[21111, 'ENGLISH'])
candidate_word_3_3 = list(narrow_down(unit_3).loc[28096, 'ENGLISH'])

print(candidate_word_3_1)
print(candidate_word_3_2)
print(candidate_word_3_3)
```

```:結果
['A', 'N', 'T', 'I', 'B', 'I', 'O', 'T', 'I', 'C']
['I', 'N', 'T', 'E', 'R', 'E', 'S', 'T', 'E', 'D']
['O', 'P', 'T', 'I', 'M', 'I', 'S', 'T', 'I', 'C']
```

[1, 4, 5, 6, 7, 6, 8, 5, 6, 9]
の単語が
候補１：['A', 'N', 'T', 'I', 'B', 'I', 'O', 'T', 'I', 'C']
候補２：['I', 'N', 'T', 'E', 'R', 'E', 'S', 'T', 'E', 'D']
候補３：['O', 'P', 'T', 'I', 'M', 'I', 'S', 'T', 'I', 'C']
という３つの候補に絞れた。

この候補３つをしらみつぶしていく。<br>
まずは候補１のANTIBIOTICから。

### 候補１　ANTIBIOTIC

仮の辞書_alpha_wordに分かったアルファベットを入れていく。

```
dict_candidate_word_3_1 = dict(zip(word_3, candidate_word_3_1))
print(dict_candidate_word_3_1)
```

```:結果
{1: 'A', 4: 'N', 5: 'T', 6: 'I', 7: 'B', 8: 'O', 9: 'C'}
```

```python
_alpha_dict = {1: '未1', 2: '未2', 3: '未3', 4: '未4', 5: '未5', 6: '未6', 7: '未7', 8: '未8', 9: '未9', 10: '未10'}
updates = dict_candidate_word_3

def update_alpha_dict(alpha_dict, updates):
    for key, value in updates.items():
        if key in alpha_dict:
            alpha_dict[key] = value
    return alpha_dict

_alpha_dict = update_alpha_dict(_alpha_dict, updates)
print(_alpha_dict)
```

```:結果
{1: 'A', 2: '未2', 3: '未3', 4: 'N', 5: 'T', 6: 'I', 7: 'B', 8: 'O', 9: 'C', 10: '未10'}
```

次に候補数が２番目に少ないword_6を確認していく。
```python
print(word_6)
print(narrow_down(unit_6)['ENGLISH'])
```

```:結果
[8, 10, 1, 6, 4, 10, 6]
2268     ASPERSE
8926     COPYBOY
11925    DOGTROT
15926    FOXTROT
20970    INSTANT
21175    INTERNE
21820    JOGTROT
22854    LEARNER
24828    MEASLES
35363    SCIENCE
39637    SURTOUT
Name: ENGLISH, dtype: object
```

候補は１６個。
だが、_alpha_dictに入れた数字とアルファベットの対応から絞り込めそうだ。

```python
replaced_words = [_alpha_dict[num] if num in _alpha_dict else num for num in word_6]
print(replaced_words)
```
`['O', '未10', 'A', 'I', 'N', '未10', 'I']`

絞り込まれたword_6から正規表現を用いてマッチングする。

```python
import re

pattern = r'^O.*A.*I.*N.*I$' 
matched_rows = narrow_down(unit_6)['ENGLISH'][narrow_down(unit_6)['ENGLISH'].str.match(pattern, flags=re.IGNORECASE)]
print(matched_rows)
```

`Series([], Name: ENGLISH, dtype: object)`

候補がないようだ。
固有名詞である可能性もあるが、今回一旦候補１は除外して考えてみる。

### 候補２　INTERESTED

暗号解読の最初に戻って候補２のINTERESTEDで再考していく。
以下は同様の手順となるため省略する。

```python
print(candidate_word_3_2)

dict_candidate_word_3_2 = dict(zip(word_3, candidate_word_3_2))
print(dict_candidate_word_3_2)

updates = dict_candidate_word_3_2

_alpha_dict = update_alpha_dict(_alpha_dict, updates)
print(_alpha_dict)

replaced_words = [_alpha_dict[num] if num in _alpha_dict else num for num in word_6]
print(replaced_words)
```

```:結果
['I', 'N', 'T', 'E', 'R', 'E', 'S', 'T', 'E', 'D']
{1: 'I', 4: 'N', 5: 'T', 6: 'E', 7: 'R', 8: 'S', 9: 'D'}
{1: 'I', 2: '未2', 3: '未3', 4: 'N', 5: 'T', 6: 'E', 7: 'R', 8: 'S', 9: 'D', 10: '未10'}
['S', '未10', 'I', 'E', 'N', '未10', 'E']
```

```python
pattern = r'^S.*I.*E.*N.*E$' 
matched_rows = narrow_down(unit_6)[narrow_down(unit_6)['ENGLISH'].str.match(pattern, flags=re.IGNORECASE)]
print(matched_rows)
```

```:結果
35363  SCIENCE  [1, 2, 3, 4, 5, 2, 4]
```

今度は先ほどと違い、候補が１つ上がった。
INTERESTED SCIENCE
文章として違和感がないように思うため、このまま進めてみよう。
```python
def replace_numbers(s, mapping):
    words = s.split()
    result = []
    for word in words:
        if word.isdigit() and int(word) in mapping:
            result.append(mapping[int(word)])
        else:
            result.append(word)
    return ' '.join(result)

output_sentence = replace_numbers(sentence, _alpha_dict)
print(output_sentence)
```

```:結果
I 未2 未3 I N T E R E S T E D I N D 未2 T 未2 S C I E N C E
```

```python
pattern = r'D.T'
matched_rows = narrow_down(unit_5)[narrow_down(unit_5)['ENGLISH'].str.match(pattern, flags=re.IGNORECASE)]
print(matched_rows)
```

```:結果
10198    DATA  [1, 2, 3, 2]
```

```python
candidate_word_5 = list(narrow_down(unit_5).loc[10198, 'ENGLISH'])
print(candidate_word_5)

dict_candidate_word_5 = dict(zip(word_5, candidate_word_5))
print(dict_candidate_word_5)

updates = dict_candidate_word_5

_alpha_dict = update_alpha_dict(_alpha_dict, updates)
print(_alpha_dict)
```

```:結果
['D', 'A', 'T', 'A']
{9: 'D', 2: 'A', 5: 'T'}
{1: 'I', 2: 'A', 3: '未3', 4: 'N', 5: 'T', 6: 'E', 7: 'R', 8: 'S', 9: 'D', 10: 'C'}
```

```python
output_sentence = replace_numbers(sentence, _alpha_dict)
print(output_sentence)
```

```:結果
I A 未3 I N T E R E S T E D I N D A T A S C I E N C E
```

最後の１単語となった。
ここまで来たら予測はつくが、一応BERTを使ってみよう。

```python
pip install transformers
```
```python
from transformers import pipeline
fill_mask = pipeline("fill-mask", model="bert-base-uncased")
text = "I [MASK] INTERESTED IN DATA SCIENCE"
results = fill_mask(text)

results_list =[]
for result in results:
    results_list.append(result['token_str'].upper())

results_list
```

```:結果
['WAS', 'AM', 'BECAME', 'GOT', 'GET']
```

```python
matched_word = matched_rows[matched_rows['ENGLISH'].isin(results_list)]
matched_word
```

```:結果
1212	AM	[1, 2]
1213	AM	[1, 2]
```

```python
matched_word = list(narrow_down(unit_2).loc[1212, 'ENGLISH'])
print(matched_word)

dict_mached_word = dict(zip(word_2, matched_word))
print(dict_mached_word)

updates = dict_mached_word

_alpha_dict = update_alpha_dict(_alpha_dict, updates)
print(_alpha_dict)

alpha_dict = _alpha_dict
```

```:結果
['A', 'M']
{2: 'A', 3: 'M'}
{1: 'I', 2: 'A', 3: 'M', 4: 'N', 5: 'T', 6: 'E', 7: 'R', 8: 'S', 9: 'D', 10: 'C'}
```

未知のアルファベットがすべて埋まった。
それでは、暗号文を解読してみよう。

```python
def replace_numbers(s, mapping):
    def replacer(match):
        num = int(match.group())
        return mapping.get(num, match.group())
    
    pattern = re.compile(r'\b\d+\b')
    return pattern.sub(replacer, s)

output_sentence = replace_numbers(sentence, alpha_dict)
print(output_sentence)
```

```:結果
I  A M  I N T E R E S T E D  I N  D A T A  S C I E N C E
```

上手くいったようだ。

# 課題とまとめ

今回行った暗号はこの方法で解けたが、課題が多く残った。

<br>

**固有名詞への対応**
踊る人形ではエルシーやエルリッジなどの固有名詞が登場する。
ホームズはその暗号が書かれた状況を予測して解読をしていた。
今回の手順で行った解読方法を使うならば、土地や名前などの固有名詞を集めておくとなお解読の幅が広がるだろう。
<br>
**単語間のアルファベットの重複が少ない場合**

![スクリーンショット 2024-07-01 031321.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3775294/cf459177-feb8-34bc-1dd6-ec0921cc507c.png)

こちらは第三者に作ってもらった暗号である。
今回の手順でやってみると、

```python
sentence_1 = "1 2 3 4  3 4  5  6 7 8"

word_1 = [1, 2, 3, 4]
word_2 = [3, 4]
word_3 = [5]
word_4 = [6, 7, 8]

print(sentence)
```
```python
def print_candidate(num, unit_num):
    result = narrow_down(unit_num).shape[0]
    return print(f'word_{num}の候補数は、 {result} 個')

word_nums = [1, 2, 3, 4]
units = [unit_1, unit_2, unit_3, unit_4]
for i, unit_i in zip(word_nums, units):
    print_candidate(i, unit_i)
```
```:結果
word_1の候補数は、 2083 個
word_2の候補数は、 307 個
word_3の候補数は、 31 個
word_4の候補数は、 899 個
```

と、単語間の重複が少なく絞り込みが困難であった。
(word_3は１文字であるためこの総当たり方法では如何ともしがたい)
さらなる工夫を必要とする。

**完全自動化へ**
例えば最初のユニット番号の振り分けやINTERESTとSCIENCEの組み合わせがそれらしいと考えたのは私自身である。
これを自動化して最終結果まで一気通貫で解読できるようにしていきたい。
画像処理や自然言語処理あたりで出来そうではあるので更新したい。

<br>

冗長になりましたが、ここまでお読みくださりありがとうございました。
コードの書き方や暗号解読に関することなど、ご意見アドバイスありましたらよろしくお願いします。

# 参考URL

**この記事は以下のサイトを参考に執筆した。**

[古代の暗号をPythonで実装する](https://qiita.com/twrcd1227/items/7540141050181b8cb7c2#%E5%8D%98%E4%B8%80%E6%8F%9B%E5%AD%97%E6%9A%97%E5%8F%B7)
こちらのサイトで単一換字暗号というワードを知った。
ホームズも行った頻度分析の方法が記されている。
上手く組み合わせれば課題の解決に繋がるかもしれない。

[シャーロック・ホームズ・トピアー踊る人形デモ](https://sh-topia.com/dancingmen/)
暗号作成用に利用。
こちらに暗号解読表があるが、これがないものとして扱った。