대칭 키 암호
공유된 비밀 키를 사용하여 평문을 암호화, 복호화 하는 암호
P : 평문, C : 암호문, K : Key
Encryption : C = Ek(P)
Decryption : P = Dk(C)
Dk(Ek(x)) = Ek(Dk(x)) = x
Kerckhoff's Principle
암호시스템의 안정성은 암호 알고리즘의 비밀을 지키는데 의존되어서는 안되고, 키의 비밀을 지키는데 의존되어야 한다는 원리
Kerckhoff의 원리에 따라 공격자는 항상 암호/복호 알고리즘을 알고 있다고 가정
암호의 안정성은 키의 안정성에 기반함
Cryptanalysis
암호분석공격
Ciphertext-only : Eve가 어떤 암호문을 얻어 대응되는 평문과 키를 찾는 공격 - 전수조사, 통계적, 패턴 공격
Known-plaintext : Eve가 암호문 외에 추가로 여러 개의 평문/암호문 쌍을 확보 - 주어진 평문/암호문 의 연관성을 이용해 해독
Chosen-plaintext : Known-plaintext와 비슷하지만 Eve가 확보할 수 있는 평문/암호문 쌍이 공격자가 선택한 값
Chosen-ciphertext : Eve가 자신이 원하는 암호문을 선택하고 그에 대응되는 평문을 얻음
대치 암호 (Substitution Cipher)
하나의 기호를 다른 기호로 대체하는 암호
ex) A->D, T->Z
단일문자 암호와 다중문자 암호로 나뉨
Monoalphabetic Cipher (단일문자 암호)
단일문자 암호에서 평문의 기호와 암호문에 대응되는 기호는 항상 일대일 대응 관계를 가짐
Additive Cipher : 덧셈 암호는 가장 간단한 단일문자 암호, 각 문자는 Z26의 원소로 대응하고 키인 n만큼 더하여 암호화
특정 문자의 출현 빈도수를 이용하는 통계적 공격에 취약
Multiplicative Cipher : 곱셈 암호, Z26에서 키인 n을 곱하여 암호화 (복호화는 키인 n의 역원을 곱해야함)
암호화와 복호화가 서로 역함수 관계에 있음을 보장하기 위해 키는 집합 Z*26의 원소이어야 함 {1,3,5,7,9,11,13,15,17,19,21,23,25}
Affine Cipher : 두 개의 키를 사용하고, 덧셈 암호와 곱셈 암호를 결함한 암호
첫 번째 키는 곱셈 암호에 사용, 두 번째 키는 덧셈 암호에 사용 ( C=(P x K + k2)mod26, P=((C-k2) x k의역원)mod26 )
아핀 암호는 연립방정식을 이용해 해독
파이썬으로 아핀 암호를 구현해봄
import numpy as np
# 곱셈에 대한 역원을 구하는 함수
def find_mod_inv(a,n):
return pow(a, -1, n)
# 문자를 숫자로 바꾸는 함수
def str2int(text):
ret = list()
for t in text:
ret.append(ord(t)-65)
return ret
# 암호화 함수
def affine_encrypt(plain, k1, k2, n=26):
ret = list()
num_list = str2int(plain)
for i in num_list:
c = np.mod(i*k1+k2,n)
ret.append(chr(c+65))
return ''.join(ret)
# 복호화 함수
def affine_decrypt(cipher,k1,k2,n=26):
ret = list()
num_list = str2int(cipher)
k1_inv = find_mod_inv(k1,n)
for i in num_list:
c = np.mod((i-k2) * k1_inv,n)
ret.append(chr(c+65))
return ''.join(ret)
#대문자만 가능 (소문자로 하려면 -97, +97로 바꿔야함)
plain = input("평문을 입력하세요: ")
k1 = int(input("키 1을 입력하세요: "))
k2 = int(input("키 2를 입력하세요: "))
print("암호문은 " + affine_encrypt(plain,k1,k2,n=26)+" 입니다.")
cipher = input("암호문을 입력하세요: ")
print("평문은 " + affine_decrypt(cipher,k1,k2,n=26)+" 입니다.")대소문자 상관없이 가능하도록 구현해보려고 했으나 숫자를 이용하여 암호화 하는 과정에서 대소문자중 한가지로 통일되므로 불가능
숫자를 따로 처리하면 역원 계산이 불가능 한거같은데..
upper(), lower()함수로 입력만 소문자로 하거나 출력만 소문자로 할 순 있어도 둘다 하는 방법은 찾지 못함
Monoalphabetic Subsitution Cipher : 전수조사 공격에 취약한 암호를 해결하기 위해 평문 문자와 대응되는 암호문 문자 사이의 대응을구성, 이 경우 키 공간의 크기가 26! 이기때문에 전수조사 공격에 어느정도 대응 가능
문자의 출현 빈도수를 변경시키지는 않기 때문에 통계적 공격을 적용할 수 있음
Polyalphabetic Cipher (다중문자 암호)
다중문자 암호에서 각 문자는 다른 대치를 가짐, 평문 문자와 암호문 문자와의 관계는 일대다대응
예를 들어, "a"는 문장의 시작점에서는 "D"로, 중간에서는 "N"으로 암호화
다중문자 암호는 언어의 문자 빈도를 감추는 장점이 있음
메시지에서 평문문자와 그 문자의 위치에 따라 암호문 문자를 생성
키가 암호화를 할 때 평문 문자의 위치에 따라 정해지는 부분키들로 구성된 키수열
즉 키 k는 (k1, k2, k3...)이며 평문의 i번째 문자를 암호화 하는데 ki가 사용
Autokey Cipher : 자동키 암호, 간단한 다중문자 암호
P = P1P2P3... C = C1C2C3... k = (k1, P1, P2...)
Encryption = Ci = (Pi + ki)mod 26, Decryption = Pi = (Ci - Ki)mod 26
Playfair Cipher : 1차 세계 대전 중 영국군이 사용, 5x5행렬로 배열된 25개의 알파벳 문자로 비밀 키가 구성(한 칸만 두개 문자, 행렬의 배열을 다르게 하여 많은 비밀키 생성 가능)
평문의 두 문자가 연속하여 같으면 가짜문자(bogus letter)을 삽입
한 쌍으로 된 두 문자가 같은 열이냐, 같은 행이냐, 다른 열과 행이냐 에 따라 다른 방식으로 암호화
Vigenere Cipher : 키 수열은 길이가 m(1<=m<=26)인 초기 비밀 키 수열의 반복 Alice 와 Bob이 합의한 초기 비밀키를 반복하여 암호화
vigenere 암호는 m개의 덧셈 암호의 조합으로써 간주될 수 있다 (덧셈 암호는 m=1인 경우의 vigenere 암호)
해독하기 위해선 1. 키의 길이를 찾아내고 2. 키 자체를 찾아내면 됨
키의 길이를 찾기 위해 kasiski 테스트를 진행, 이 테스트는 최소 3문자로 구성된 반복된 텍스트 세그멘트를 찾아냄
이런 세그멘트를 두 개 찾았다고 가정하고 그들 사이의 거리를 d라고 하면 키의 길이 m에 대하여 d|m이라고 추정할 수 있음
거리가 d1, d2, d3... 인 더 많은 반복된 세그멘트가 발견되면 gcd(d1, d2, d3...)|m
키의 길이를 찾은 뒤에는 암호문을 m개의 서로 다른 조각으로 나눈 뒤, 빈도 공격을 포함한 덧셈 암호를 해독하는데 사용하는 방법을 적용
Hill Cipher