, 컴퓨터는 제대로 여부 키를 추측 여부 어떤 생각을 가질 필요가있다. 우리는 메시지가 영어로되어 있다는 것을 알고 있습니다. 그래서 우리는 컴퓨터가 어떻게 든 그것을 이해하도록해야합니다.
이 목적을 위해 컴퓨터에 바이트 시퀀스가 영어가 될 가능성을 알려주는 통계 모델을 사용할 수 있습니다. 아마도 가장 기본적인 통계 모델은 간단한 문자 빈도 표일 것입니다. (이것은 당신의 특정 암호문에 대해 꽤 잘 작동합니다.)
영어가 바이트로 인코딩되는 방식 또한 중요합니다. 텍스트가 ASCII를 사용한다고 추측 할 수 있습니다. 그래서 우리는 ASCII로 인코딩 된 영어 텍스트에서 각 바이트 값이 얼마나 자주 발생 하는지를 알려주고 싶습니다.
이러한 테이블은 온라인에서 찾을 수 있지만 일반적으로 많은 양의 데이터 ("corpus")를 분석하면 이러한 정보의 출처가됩니다. 데이터가 더 잘 일치할수록 (스타일, 단어 선택, 철자법, 대문자 사용, 띄어쓰기 등의 측면에서 - 모델에서 발견되는 것만이 중요 함) 해독하려는 텍스트가 더 좋을수록 더 나은 컴퓨터 디코딩은 할 것입니다.
모델을 사용하여 가장 적합한 키를 결정하기 위해 베이지안 추정을 사용할 수 있습니다. 여기의 수학은 약간 무서운 것처럼 들릴지도 모르겠지만, 편지 빈도의 경우 꽤 간단합니다. 공식적으로, 우리는 가능한 모든 키에 대해 균일 한 전제를 가정하고, 평문은 모델에 의해 주어진 분포로부터 독립적으로 선택된다고 가정한다. 그러면 키의 우도는 모델에서 쉽게 계산되는 평문의 집합의 (이전) 우도에 비례합니다.문자 빈도의 경우 각 문자가 독립적이므로 키의 각 바이트를 따로 따로 추측 할 수 있으므로이 작업이 더 쉽습니다.
(텍스트를 작은 독립적 인 덩어리로 분해 할 수없는 모델을 사용하는 경우 너무 많은 문자가있을 수 있으므로 모든 키를 고려할 수는 없지만 더 똑똑한 검색 알고리즘 (예 : Dijkstra 's)을 사용할 수 있습니다. 또는 A *를 사용하여 모든 키를 고려하지 않도록하십시오.
이 예제에서는 The Blog Authorship Corpus의 첫 번째 100 개의 파일을 사용했습니다 (상당히 임의적으로 선택). (이 코퍼스는 XML이므로 정확하게 구문 분석하지는 못하지만 메타 데이터 및 구문 오버 헤드의 양은 작아서이 간단한 예제에서는별로 중요하지 않다고 생각합니다.)
(면책 조항 : 나는 많은 파이썬를 쓰지 않는다)
import os
import glob
# Build language model by digesting corpus
frequency = [0 for i in xrange(0, 256)]
filecount = 0
for filename in glob.iglob(os.path.join('Corpus', '*')):
filecount += 1
if filecount > 100: break
with open(filename, 'rb') as f:
for c in f.read():
frequency[ord(c)] += 1
sum = 0
for count in frequency: sum += count
frequency = [(1.0 * count)/sum for count in frequency]
# Hard-coded message data
messages = [
b"\x7B\x53\xD5\xEE\x76\x46\x75\x5E\x99\x9A\x2A\xFF\xDF\xCB\x35\x3F\xA0\x50\x77\x00\x3B\xEB\x3F\xCC\xCB\x96",
b"\x7B\x44\xDB\xF7\x76\x03\x66\x10\x8A\xDB\x2C\xB0\xD6\xD9\x32\x3F\xA3\x4C\x66\x0C\x77\xFD\x22\xC7\xCB\x96",
b"\x77\x57\xC2\xF9\x25\x04\x7B\x51\x89\xC9\x7E\xF7\xCB\xD9\x33\x7B\xE6\x4D\x60\x09\x3B\xF5\x25\xCE\xCA\x96",
b"\x6A\x42\xDB\xEE\x60\x15\x34\x47\x98\xC8\x3B\xB0\xCD\xD0\x28\x6F\xB6\x5A\x61\x4D\x6F\xF3\x32\xC3\xD6\x96",
b"\x6E\x53\xD0\xEE\x60\x15\x70\x51\x84\x9A\x33\xFF\xCC\xD6\x28\x71\xA1\x1F\x6C\x1E\x3B\xFA\x3F\xCC\xCA\x96",
b"\x6D\x5E\xD1\xF9\x25\x07\x66\x55\xDD\xD4\x31\xE4\x9E\xCB\x29\x7E\xB4\x4F\x25\x08\x75\xF3\x23\xC5\xC7\x96",
b"\x7D\x5F\xD7\xF4\x6C\x09\x7A\x51\x8F\xC3\x7E\xF1\xCA\xCC\x20\x7C\xAD\x1F\x76\x19\x7A\xEE\x22\xC7\xCB\x96",
]
length = len(max(messages, key=lambda message: len(message)))
# Guess the key
key = []
for i in xrange(0, length):
best_keybyte = 0
best_keybyte_p = 0.0
for keybyte in xrange(0, 256):
# Calculate the prior probability of the plaintext for this key byte
p = 1.0
for message in messages:
if i < len(message):
messagebyte = ord(message[i])
plaintext = chr(messagebyte^keybyte)
p *= frequency[ord(plaintext)]
if p > best_keybyte_p:
best_keybyte = keybyte
best_keybyte_p = p
key.append(best_keybyte)
# Decode the messages based on the guess
for message in messages:
plaintext = ""
for i in xrange(0, len(message)):
plaintext += chr(ord(message[i])^key[i])
print(plaintext)
이 제공 :..
eears and toast form wtni
erokser war has escalaiei
iave boats guard red inlh
ttores were shipped toyat
pedresday morning is ftnh
shee are not sharp enohge
cichionary attack stariei
는 (각 라인 뒤에 공간이 있습니다)
을 분명이, BU는 완벽하지 않습니다 그것은 당신이 아마 (영어에 대한 당신의 뛰어난 지식을 사용하여) 손으로 오류를 쉽게 해결할 수있을만큼 충분히 가깝습니다.
우수한 영어 모델을 사용하면 컴퓨터가 이러한 문제를 자동으로 해결하는 데 도움이 될 수 있습니다. 예를 들어, 문자 빈도 모델은 메시지가 대문자로 시작될 가능성이 있음을 알지 못합니다. 일반적으로 문자 쌍의 빈도를 고려해야합니다.
필자는 열 접근 방식을 사용하고 있습니다. 그래서 첫 번째 줄에서는 7b, 7b, 77,6a, 6e, 6d, 7d를 할 것입니다. 두 번째 행은 53,44,57,42,53,5e, 5f 등을 만들 것입니다.이 경우에는 의미가 있습니다. –
이것은 질문에 대한 대답이 아닙니다. 그것은 주석이어야합니다. –
@James, 알고 있습니다. 그러나 낮은 명성으로 인해 나는 논평 할 수 없었다. downvote 주셔서 감사합니다. – alex