단일 치환 암호 해독 (패턴 분석 공격) - 공부하는 도비

단일 치환 암호는 무차별 대입 공격이나 빈도수 분석을 통하여 암호문을 해독할 수 있습니다.

오늘은 단일 치환 암호를 해독하는 방법 중 패턴 분석을 사용하여 암호를 분석해보려고 합니다. 

패턴 분석 방법은 Known plaintext Attack 방법 중 하나로, "공격자가 일정 부분의 평문과 이에 대응하는 암호문을 가진 상태에서 공격하는 유형"을 의미합니다. 

 

알려진 평문 공격을 하면, 단순히 무차별 대입 공격이나 빈도수 분석을 하는 것보다 암호문 해독이 더 수월해집니다. 

 

예시를 통하여 패턴 분석을 해보도록 하겠습니다.

아래는 단일 치환 암호로 암호화 한 문장입니다. 

만약 빈도수 분석을 하면,  여기서 가장 많이 나온 글자를 찾아 알바벳 빈두수에 따라 하나하나 치환하며 암호문을 해독해야 합니다. 

알파벳 빈도수

위 암호문에 대한 비밀키는 다음과 같습니다.

대입하면, 아래와 같은 평문을 얻을 수 있습니다.

---

다시 알려진 평문 공격으로 돌아와서 오늘은 패턴 분석을 할 것이니, 우리는 공격자가 저 암호문의 평문 중 몇 가지 단어를 알고 있다고 가정하고, 위에서 정리한 치환 키는 모르는 것으로 간주합니다.

 

우선, 패턴 분석(Pattern Analysis)이란?

: 각 단어의 패턴을 숫자로 표준화하여, 암호문에서 각 단어와 동일한 패턴을 찾아 암호문을 해독하는 공격 방법

 

단어의 첫 알파벳부터 index를 부여하는데, 출현 빈도가 1인 알파벳은 새로운 index를 주고, 그렇지 않으면 이미 부여된  index를 다시 사용하여, 단어의 패턴을 만들도록 합니다. 

 

Ex_1) substitution

처음 나온 s에 index = 0을 주고, 두번 째로 나온 s 역시 index = 0을 줘서, 결론적으로 substitution에 대한 패턴 012034313456을 만들 수 있습니다.

Ex_2) indistinguishable

만약 단어가 길다면, 눈에 띄는 패턴이 생성됩니다. 

 

이렇게 생성된 패턴을 가지고, 암호문에서도 동일한 패턴이 있는 찾습니다. 단일 치환 암호는 알파벳이 1:1 매핑이 된다는 특징이 있기 때문에 평문의 패턴이 암호문에도 그대로 적용이 됩니다. 

---

패턴 분석 코드

def makePattern(p): 
    tmp = {}
    res = []
    index = 0
    for c in p:
        if c in tmp:
            res.append(tmp[c])
        else:
            tmp[c] = str(index)
            res.append(str(index))
            index += 1
    return res
    

print(makePattern('substitution'))
print(makePattern('indistinguishable'))

결과

 

생성된 평문 패턴을 사용하여, 암호문에 동일한 패턴이 있는지 확인하는 코드

# 암호문에서 평문의 패턴과 동일한 부분 리턴 하는 함수
def findPattern(cipertext, p): 
    pattern = makePattern(p)    # 패턴 생성 함수 호출 
    blocksize = len(p)
    pos = 0
    while True:
        data = ciphertext[pos:pos+blocksize]
        if len(data) < blocksize:
            break
        
        ptrn = makePattern(data)
        if ptrn == pattern:
            return data
        pos += 1

 

전체 코드

# 평문의 패턴을 만드는 함수
def makePattern(p): 
    tmp = {}
    res = []
    index = 0
    for c in p:
        if c in tmp:
            res.append(tmp[c])
        else:
            tmp[c] = str(index)
            res.append(str(index))
            index += 1
    return res

# 암호문에서 평문의 패턴과 동일한 부분 리턴 하는 함수
def findPattern(cipertext, p): 
    pattern = makePattern(p)    # 패턴 생성
    blocksize = len(p)
    pos = 0
    while True:
        data = ciphertext[pos:pos+blocksize]
        if len(data) < blocksize:
            break
        
        ptrn = makePattern(data)
        if ptrn == pattern:
            return data
        pos += 1

if __name__ == '__main__':
    ciphertext = '''jiywybmdvwyjksnybgmhnkbdmvubgmksoqlznggpbougiysybgmngbwmensjynobjdunvontmdsznxmpubzmumpngdjozjjtbdlbsjiymvgjkmkjympbdmndvumgmoozmvcnxtbdubgxunbywnxmobzomvisojpnyvgoumgid'''

    known_plaintext = ['friend', 'surprise', 'evaporation']
    for p in known_plaintext:
        ret = findPattern(ciphertext, p)
        print('[%s] = [%s]' %(p, ret))

결과