브루트포스 공격(Brute Force Attack)과 빈도 분석

Brute Force Attack (전사 공격)

단일치환 암호화와 시저 암호의 차이
시저 암호 - 전사공격으로 해독 가능 (최대 26번 시도해보면 평문이 구해짐)
단일 치환 암호 - 전사공격으로 해독이 힘듦

Brute Force Attack의 어려움

키가 많으면 브루트포스 공격으로 조사하는 것은 매우 어렵다. 키가 많은 경우 모든 키를 적용해보는 데에는 상당한 시간이 필요한데 단일 치환암호의 경우 1초에 10억 개의 키를 적용하여 조사한다고 해도, 모든 키를 조사하는 데 120억년 이상의 시간이 걸린다. 바른 키를 찾기까지의 평균 시간은 약 60억년으로 사실상 해독하는 것이 어렵다고 볼 수 있다.

키 공간(key space)

어떤 암호에서 사용할 수 있는 모든 키의 집합

키 공간의 크기

• 키 공간에 속하는 가능한 키의 총수
• 키 공간이 크면 클수록 전사 공격은 어려워지게 된다.

빈도 분석 암호 해독법

Brute Force Attack로 단일 치환 암호를 해독하는 것은 어렵지만, 빈도 분석 암호 해석법을 사용하면 단일 치환 암호도 해독할 수 있다.

빈도분석이란 평문에 등장하는 문자의 빈도와 암호문에 나오는 문자의 빈도가 일치하는 것을 이용하는 것으로, 최초 -9세기 '암호문 해독에 관한 논고'에 등장하는 아랍의 현학자 알칸디에 의해 제안됐다.

빈도 분석 단어의 특징

• 빈도가 높은 문자뿐만 아니라 빈도가 낮은 문자도 단서가 된다.
• 단어의 단락을 알면 그것도 단서가 될 수 있다.
• 암호문이 길면 해독이 쉬워진다.
• 같은 문자가 연속해서 나타나면 그것은 단서가 된다.
• 해독의 속도가 점점 빨라진다.

단일치환암호의 약점

평문과 암호문간의 단순 대응으로 평문에 등장하는 문자의 빈도와 암호문에 등장하는 문자의 빈도가 일치하여 빈도 분석 해독에 취약하다. 빈도 분석을 어렵게 하기 위해서는 ** 암호문에 나타나는 문자들의 빈도를 거의 균등하게 해야 한다.**

그렇다면 빈도 분석에 강한 암호는 무엇일까? 빈도 분석에 강한 암호는 다중치환암호(polyalphabetic substitution cipher)이다.

다중치환 암호

다중치환암호란 암호문에 나타나는 문자들의 빈도를 거의 균등하게 만드는 암호로 대표적인 예로는 비제네르 암호, 힐 암호 등이 있다.

비제네르 암호
1586년 프랑스 외교관 비제네르에 의해 발표된 암호로 평문장을 여러 부분으로 나누어 각각 서로 다른 단일치환암호를 적용하는 방식이다. 전문가들이 많이 사용하는 암호들의 기본형이 된다.
비제네르 암호화 방법

1. 키는 키 단어라고 하는 문자로 된 수열 사용
2. 키 단어를 평문의 각 문자 바로 아래에 반복하여 씀
3. 키를 정하여 서로 공유
4. 암호문은 키 단어의 문자와 평문의 문자를 세로로 더하여 만듬

암호 알고리즘과 키

암호를 만들어서 반복 사용하기 위해서는 반복 사용하여도 안전할 수 있도록

• 반복 사용하는 부분(암호 알고리즘)

• 변경 가능한 부분(키) 으로 나누어 설계한다.