単一換字式暗号文を解読してみた。

概要

単一換字式暗号の暗号文を ブルートフォースアタックで解読するコードを書いてみた。

単一換字暗号を行うコード(cipher.py)

暗号化アルゴリズム：

1. gen_key()で、アルファベット(self.string)をランダムに並び替え、その対応表(self.key)を作成する。
2. encrypt()(から呼び出されたcipher())で、その対応表(self.key)を元に、対象の文(message)に含まれる各文字を置き換える。
3. 置き換え完了後の文字列が暗号文(encrypted_message)

# coding: utf-8
# Here your code !
import random
import sys
class Cipher(object):
  def __init__(self,string):
    '''
    self.string = 'abcdefghijklmnopqrstuvwxyz   \'"+*-/=![]():;\\.,\n'
    '''
    #self.string = 'abcdefghijklmnopqrstuvwxyz'
    self.string = string
    self.key = self.string
    
  def cipher(self,string,key,message):
    ret = ''
    for s in message:
      ret += key[string.index(s)]
    return ret

  def encrypt(self,message):
    return self.cipher(self.string,self.key,message)

  def decrypt(self,message):
    return self.cipher(self.key,self.string,message)

  def gen_key(self):
    ret = ''
    string = self.string
    while string:
      i = random.randint(0,len(string)-1)
      s = string[i]
      tmp = string[:i]
      tmp += string[i+1:]
      string = tmp
      ret += s
    self.set_key(ret)
    return ret

  def set_key(self,key):
    self.key = key

  def get_key(self):
    return self.key

解読するコード(attacker.py)

解読アルゴリズム:

1. self.attack()からself.guess()を呼び出し、推測の文章(estimation)を作成する。guess()では、使用文字(self.string)からitertoolsを使って推測の鍵(estimated_key)を作成し、その鍵を元に暗号アルゴリズムと同じやり方で復号する。
2. is_natural()で推測の文章に含まれる単語が、すべて所定の単語リスト(self.words)に含まれたものであるかを確認する。
3. もし、2の判定結果が肯定的である場合、推測の文章を答えとして返答する。

所定の単語リストは、下記サイトのものを使用した。
http://tokoton-eitango.com/eitango/numindex/1/1

import itertools
class DecryptAttacher:
    def __init__(self,string,words_list):
        f = open(words_list)
        self.words = set(map(lambda x: x.replace('\n','').replace('\r',''), f.readlines()))
        #print self.words
        f.close()
        #self.string = 'abcdefghijklmnopqrstuvwxyz'
        self.string = string
    def attack(self,encrypted_message):
        for estimation in self.guess(encrypted_message):
            if self.is_natural(estimation):
                #print 'I got the word: %s' % estimation
                return estimation
    def is_natural(self,estimation):
        natural_flag = True
        words = estimation.split(' ')
        for w in words:
            if not w in self.words:
                #print '%s is wrong.' % estimation
                natural_flag = False
                break
        return natural_flag
    def cipher(self,string,key,message):
        ret = ''
        for s in message:
            ret += key[string.index(s)]
        return ret
    def decrypt(self,key,message):
        return self.cipher(key,self.string,message)
    def guess(self,encrypted_message):
        for estimated_keys in itertools.permutations(self.string):
            #print estimated_keys, 
            yield self.decrypt(''.join(estimated_keys),encrypted_message)
            

メインスクリプト

暗号化対象(msg)の文字列をboy ask guyとし、使用文字(string)をboyaskgu とした。

import cipher
import attacker

if __name__ == '__main__':
    string = 'boyaskgu '
    cp = cipher.Cipher(string)
    key = cp.gen_key()

    msg = 'boy ask guy'
    print 'message : %s' % msg
    encrypted_message = cp.encrypt(msg)
    print 'encrypted_message: %s key: %s' % (encrypted_message,key)
    at = attacker.DecryptAttacher(string,'words.list')
    print 'decrypted_message: %s' % at.attack(encrypted_message)

実行結果

message : boy ask guy
encrypted_message: gubys ayokb key: gubs aoky
decrypted_message: guy ask boy

節子、それ元の文章と違う。逆や。

message : boy ask guy buy bus
encrypted_message: oyksubas gksogksogb key: oykuba gs
decrypted_message: boy ask guy buy bus

文章を長くしてみると、情報が多くなるからなのか、正確に解読できるようになった。