[python] 4. 힐 암호(Hill cipher)

이번에 소개 할 암호는 힘 암호(Hill cipher)입니다.

힐 암호는 빈도 분석법으로 뚫을 수 없는 방법중 하나인

다중문자 치환(polygrapthic substitution)을 이용한 암호입니다.

다중문자 치환이란 한 번에 복수의 문자를 치환하는 암호기법입니다.

 

다중문자 치환 방식을 쓸 때는 먼저 블록의 크기를 정해야합니다.

즉, 문자를 몇 개의 단위로 치환할것인지 결정해야합니다.

힐 암호는 어떤 블록 크기에 대해서도 사용할 수 있는 암호입니다.

 

예를 들기위해 블록 크기가 2인 힐 암호를 살펴봅시다.

먼저 평문을 두 문자씩 묶고 마지막에 한 문자만 남게되면

무효 문자(null) 나 채움 문자(padding)을 채워넣습니다.

 

key는 a,b,c,d 로 구성된 1부터 26까지 수 중에서 선택해 구성합니다.

예를들어 "jacky and jill"이라는 평문이 있고

key는 3,5,6,1 로 설정해봅시다.

이때 암호화 공식은

c1 ≡ 3 x p1 + 5 x p2 mod26

c2 ≡ 6 x p1 + 1 x p2 mod26

입니다.

평문	ja	ck	ya	nd	ji	ll
index	10, 1	3, 11	25, 1	14, 4	10, 9	12, 12

위의 표처럼 두 글자씩 묶인 평문에 key값을 적용해 봅시다.

c1 ≡ 3 x 10 + 5 x 1 ≡ 9 mod26

c2 ≡ 6 x 10 + 1 x 1 ≡ 9 mod26

두개의 key값을 평문의 index에 각각 곱한 뒤 더한값을 모듈러 연산한 값이 암호문의 index가 되는겁니다.

 

나머지 블록도 공식을 적용하면 전체 암호문을 얻을 수 있습니다.

평문	ja	ck	ya	nd	ji	ll
평문 index	10, 1	3, 11	25, 1	14, 4	10, 9	12, 12
암호문 index	9, 9	12, 3	2, 21	10, 10	23, 17	18, 6
암호문	ii	lc	bu	jj	wq	rf

암호문은 "iilcbujjwqrf"가 됩니다.

위의 암호문에서 보이듯이 다중 치환암호에서는 여러 문자를 짝을 지어 암호화 하기때문에 

서로 다른 문자가 같은 같은문자로 암호화 될 수 있고 같은 문자도 다른 문자로 암호화 될 수 있습니다.

 

다음으로는 복호화 과정을 살펴보겠습니다.

위의 암호화 공식을 예로 들면

 

 

이와같은 행렬로 나타낼 수 있습니다

 

복호화 과정은 미지수가 2개 (p1,p2)인 연립방정식을 푸는 것과 같습니다.

연립방정식을 풀기 위해 역행렬을 곱하면 미지수를 구할 수 있습니다.

 

 

역행렬은 아래의 식을 이용해 구할 수있습니다

 

 

이때 |ad-bc|를 행렬식이라고 하는데

역행렬에서 행렬식으로 나누는 것 대신 앞에서 살펴본 곱셈 암호에서처럼

모듈러연산에서의 곱셈에 대한 역원을 곱하는 것으로 대신 할 수 있습니다.

복호화 공식을 살펴보면

 

 

p1과 p2를 이와같은 식으로 구할 수 있습니다.

plainText = []
cipherText = []
key = [0,0,0,0]
revKey = [0,0,0,0]

def modulo(a,b):
    a = a % b
    return a

def hill(inputText,key):
    textLen = len(inputText)
    print (textLen)
    if(textLen % 2 == 1):
        inputText = inputText + "a"
    for i in range (0,textLen,2):
        p1 = ord(inputText[i]) - ord("a") + 1
        p2 = ord(inputText[i+1]) - ord("a") + 1
        c1 = modulo(p1 * key[0] + p2 * key[1],26)
        c2 = modulo(p1 * key[2] + p2 * key[3],26)
        cipherText.append(chr(c1 + ord("a") - 1))
        cipherText.append(chr(c2 + ord("a") - 1))

def findRev(key):
    determinant = key[0] * key[3] - key[1] * key[2]
    for i in range(26):
        if (modulo(determinant * i,26) == 1):
            rev = i
            break
    return rev

def decode(cipherText,key):
    rev = findRev(key)

    revKey[0],revKey[3] = key[3],key[0]
    revKey[1],revKey[2] = key[1],key[2]
    revKey[0] *= rev
    revKey[1] *= -rev
    revKey[2] *= -rev
    revKey[3] *= rev

    textLen = len(cipherText)

    for i in range(0,textLen,2):
        c1 = ord(cipherText[i]) - ord("a") + 1
        c2 = ord(cipherText[i+1]) - ord("a") + 1
        p1 = modulo(c1 * revKey[0] + c2 * revKey[1], 26)
        p2 = modulo(c1 * revKey[2] + c2 * revKey[3], 26)
        plainText.append(chr(p1 + ord("a") - 1))
        plainText.append(chr(p2 + ord("a") - 1))


def textPrint(text):
    textLen = len(text)
    for i in range(textLen):
        print(text[i],end='')

if __name__ == "__main__":
    inputText = input("input plainText : ")
    inputText = inputText.lower()
    inputText = inputText.replace(" ","")
    print(inputText)
    key[0],key[1],key[2],key[3] = map(int,input("input four hill cipher key :").split())

    hill(inputText,key)
    textPrint(cipherText)
    print("\n")
    decode(cipherText,key)
    textPrint(plainText)

 

 

블록 크기가 2개인 힐 암호에 대해서만 작성해보았습니다.

행렬식의 곱셈에 대한 역원을 구하는 부분 역시 

곱셈 암호에서와 같이 유클리드 알고리즘을 이용해서 구할 수도 있지만

컴퓨터 연산을 이용해 역원을 빠르게 찾아 낼 수 있었습니다.

 

오늘도 긴 글 읽어주셔서 감사합니다.

틀렸거나 부족한 부분은 알려주시면 감사하겠습니다.