에브리데이 크립토그래피 2/e — 2장(1)

역사상의 암호화 시스템

단일 문자 암호

카이사르 암호

카이사르 암호(Caesar Cipher)는 암호화 기법을 소개할 때면 가장 먼저 나오는 사례습니다. 카이사르 암호는 이동 암호(shift cipher)중 하나 인데, 카이사르 암호는 특별하게 세 자리 간격으로 이동하는 경우만을 뜻하는 것으로 국한됩니다.

카이사르 암호의 개념은 알파벳의 각 문자를 일정한 숫자 간격으로 밀어서 다른 알파벳으로 암호화하는 방법입니다.

만약 평문 ‘HOBBY’를 카이사르 암호를 이용하면 ‘KREEB’라는 암호문으로 암호화됩니다.

암호문을 받으면 사전에 합의한 이동 간격을 알고 있으므로 동일한 방식으로 위치시킵니다. 그리고 복호화 하는과정을 보면 ’NHVWUHO’라는 암호문은 ‘KESTREL’

• 키 공간 : 26

카이사르 암호의 취약성

가장 명백한 약점은 키 공간의 크기입니다. 볼 수 있는 키가 겨우 26개밖에 안 되기 때문에 공격자는 연필 한 자루와 종이 한 장 그리고 5분 정도면 완전한 키 검색이 가능합니다. 공격자는 단순히 26개 키에 암호문 후보 26개를 각각 시험해 보면 그만인 것 입니다. 만약 평문이 그럴 듯하게 읽히면 정확하게 해독됐는지 금방 알 수 있습니다.

만약 평문이 인식 가능한 중복이 없더라도(그것이 무작위로 선택된 문자로 구성) 완전한 키 검색은 평문 후보의 숫자를 26개로 줄여주므로 여전히 매우 효과적입니다. 오리지널 평문이 겨우 다섯 문자밖에 안 된다고 생각하면, 평문에 대한 아무런 사전 지식이 없더라도 우리는 그 다섯 단어짜리 평문이 가능한 11881376개 중 하나임을 알 수 있습니다.

26⁶ = 26 x 26 x 26 x 26 x 26 = 11881376

간단한 대체 암호화

간단한 대체 암호화는 카이사르 암호를 상당부분 향상시킨 형태입니다. 하지만 카이사르 암호처럼 이 암호화 시스템 역시 근본적으로 허점이 있음을 보게 될 것입니다.

순열

순열(permutation)은 한 세트의 객체를 일정한 순서로 배열하는 방식입니다.

모든 알파벳 문자의 순열은 26개 문자를 일정한 순서로 배열하는 것입니다. 가장 자연스러운 순열은 (A, B, C …, Z)지만 (Z, Y, X …, A) 이고, 26개의 알파벳의 순서를 무작위로 위치시킨 것도 순열 중 하나입니다. 그러한 순열의 총 숫자는 이렇게 계산됩니다.

26 x 25 x 24 x 23 x … x 3 x 2 x 1

또한 이것을 ’26!’ 으로 ’26 팩토리얼’이라고 표현 할 수 있습니다.

얼핏 보이기에 카이사르 암호랑 비슷하지만, (A, B, C … X, Y, Z)에 대한 임의 순열로 알파벳을 대체하는 차이점이 있습니다.

간단한 대체 암호화 기법의 취약점

아마도 가장 주목할 만한 대목은 키 공간이 워낙 커서 모든 가능한 키 선택 요소를 무난히 찾아낼 수 있을 만큼 강력한 컴퓨터 시스템이 아직 없을 정도라는 점입니다. 그러나 간단한 대체 암호화 기법은 심각한 디자인 결함이 있어서 이 막대한 규모의 키 공간에도 불구하고 대부분의 경우에 쉽사리 깨질 수 있습니다.

빈도 분석

카이사르 암호와 간단한 대체 암호화 기법 같은 암호화 시스템이 쉽사리 악용될 수 있는 심각한 결함이 있음을 볼 수 있는데, 흥미롭게도 이런 결함은 ‘평문’의 전형적인 특성에서 비롯됩니다.

평문의 본질

어느 언어에서든 다른 문자보다 더 자주 등장하는 문자나 문자의 조합이 있게 마련이고, 따라서 언어는 고도로 구조화돼 있습니다.

10만자의 영어 텍스트마다 A는 8,167개, E는 12,702개지만 Z는 겨우 74개에 불과합니다. 여기에서 이끌어낼 수 있는 추론은 명확합니다. 영어의 어떤 평문에서든 문자 E가 문자 Z보다 훨씬 더 자주 나타난다는 점입니다.

문자 빈도 분석

여기서 인지하게 되는 특성은 카이사르 암호와 간단한 대체 암호화 모두 우리가 일단 키를 선택하면 “표본 평문 문자는 항상 동일한 성격의 암호문 문자로 암호화된다”는 점입니다. 암호화 알고리즘이 이런 특성을 갖는 암호화 시스템은 보통 ‘단일 문자 암호문(monoalphabetic cipher)’이라고 합니다.

간단한 대체 암호 기법을 푸는 일반 전략은 명확합니다. 암호문을 해독하는 데 전체 키를 모두 파악해야 할 필요도 거의 없습니다. 일반 충분한 문자가 파악되면 평문의 나머지는 추론으로 풀 수 있기 때문입니다.

문자 빈도 분석의 한계

문자 빈도 분석이 실패할 가능성이 높은 두 가지 상황이 있습니다.

1. 평문 문자가 ‘정상적인’ 문자 빈도와 일치하지 않을 경우
2. 평문이 너무 짧아서 신뢰할 만한 빈도 측정이 불가능한 경우

첫 번째 경우 정확한 예측을 하기 어려울 수 있습니다. 가장 극단적인 시나리오는 평문이 무작위로 생성되는 상황으로, 이 경우에는 모든 평문 문자가 동일한 빈도로 나타나서 암호문 문자의 빈도는 평평하게 나타난다. 이렇게 되면 어쩔 수 없게됩니다. 평문의 어느 위치에서 알 수 없는 문자가 나타나는지는 결정할 수 있기 때문에 평문에 대한 일종의 단서 정도는 알게 되겠지만, 그것이 얼마나 유효한지도 불투명합니다.

두 번째 경우 암호문 문자의 빈도는 어떤 평문 문자가 어떤 암호문 문자와 일치 하는지 추론하기에 불충분합니다.

키 공간 크기만으로는 충분하지 않다.

어떻게 간단한 대체 암호화 기법이 커다란 키 공간을 보유했음에도 불구하고 쉽게 깨질 수 있는지 보았습니다. 이것은 해당 기법이 암호화하기 전 평문의 실제 문자를 가려주는 데 그칠 뿐 평문의 구조 자체를 근본적으로 ‘파괴하지’ 못하기 때문입니다.

“커다란 키 공간은 완전한 키 검색을 무용지물로 만드는 데 필요하지만, 암호화 시스템의 보안성 자체를 보장하는 데는 충분하지 않다”

“커다란 키가 보안성을 보장해주지는 않지만 작은 키는 비보안성을 보장한다.”

이론과 실제 간의 간극

이론과 실제 사이에는 상당한 ‘간극(gap)’이 있습니다. 만약 우리가 28개와 200개 사이의 암호문을 갖고 있다면 그중에 표적 암호문으로 연결되는 오직 하나의 유의미한 평문이 있을 것이라고 거의 확신할 수 있지만 어느 것인지 파악하기는 어려울 수 있습니다.

이 경우 ‘이론’에 따르면 간단한 대체 암호화 기법은 평문이 28자에 근접하는 경우 사용하지 않는 게 안전합니다. 그러나 ‘실제’ 상황에서는 해당 암호화 기법이 50자짜리 평문을 암호화하는 데 사용됐다면 우리는 ‘그것으로 충분히 안전할’ 가능성이 높습니다.

이 경우 이 간극은 이론은 그것이 존재한다고 말해줄 뿐, 그것을 어떻게 찾아야 하는지는 알려주지 않는다는 것에서 비롯됩니다.