카시스키 시험

암호해석에서는 카시스키 검사(카시스키의 시험이나 카시스키의 방법이라고도 한다)는 비게네르 암호와 같은 다알파자 치환 암호를 공격하는 방법이다.^[1][2]1863년 프리드리히 카시스키에 의해 처음 출판되었으나,^[3] 이르면 1846년 찰스 배비지에 의해 독자적으로 발견된 것으로 보인다.^[4][5]

작동 방식

키워드를 사용해 대체 알파벳을 선택하는 폴리알파벳 대체암호에서 카시스키 검사는 암호 분석가가 키워드의 길이를 추론할 수 있도록 한다.일단 키워드의 길이가 발견되면 암호 분석가는 암호문을 n열로 배열하는데, 여기서 n은 키워드의 길이다.그러면 각 열은 단일 알파벳 대체 암호의 암호문처럼 취급될 수 있다.이와 같이 각 열은 주파수 분석으로 공격할 수 있다.^[6]마찬가지로, 로터 스트림 암호기를 사용한 경우, 이 방법은 개별 로터의 길이를 차감할 수 있다.

카시스키 검사는 암호문에서 반복되는 문자열을 찾는 것을 포함한다.시험이 성공하려면 문자열이 3자 이상이어야 한다.그러면 문자열의 연속 발생 간 거리는 키워드 길이의 배수가 될 가능성이 높다.따라서 더 많은 반복적인 문자열을 찾는 것은 키워드의 가능한 길이를 좁힐 수 있다. 왜냐하면 우리는 모든 거리에서 가장 큰 공통점을 가질 수 있기 때문이다.

이 테스트가 작동하는 이유는 일반 텍스트에서 반복된 문자열이 발생하고 해당 문자 사이의 거리가 키워드 길이의 배수인 경우 키워드 문자는 문자열의 발생과 동일한 방식으로 정렬되기 때문이다.예를 들어, 일반 텍스트를 고려하십시오.

암호는 암호문의 줄임말이다. 

"crypto"는 반복되는 문자열로 발생 간 거리는 20자.일반 텍스트를 6자 키워드 "abcdef"(6은 20으로 나누지 않음)로 줄 서 있는 경우:

abcdefabcdefabcdefabc defabc crypto는 암호문의 줄임말이다. 

instanceo의 첫 번째 인스턴스는 "abcdef"로, 두 번째 인스턴스는 "cdefab"으로 정렬한다.두 예는 서로 다른 암호문을 암호화할 것이며, 카시스키 검사에서는 아무것도 드러나지 않을 것이다.단, 5자 키워드 "abcde"(5 나누기 20)를 사용하여 다음을 수행하십시오.

abcdeabcdeabcdeabdeabcdeabdeabc crypto는 암호학의 줄임말이다. 

"crypto"의 두 발생 모두 "abcdea"와 일맥상통한다.두 예는 동일한 암호문서로 암호화되며, 카시스키 검사의 효력이 발생한다.

스트링 기반 공격

카시스키 검사의 사용의 어려움은 반복되는 현을 찾는 데 있다.이것은 수동으로 수행하기 매우 어려운 작업이지만, 컴퓨터는 그것을 훨씬 쉽게 만들 수 있다.그러나 일부 반복 문자열은 우연의 일치일 뿐이므로 일부 반복 거리는 오해의 소지가 있으므로 주의가 필요하다.암호 분석가는 정확한 길이를 찾기 위해 우연을 배제해야 한다.물론, 그 결과의 단일 알파벳 암호문들은 암호화되어야 한다.

1. 암호 분석가는 반복된 문자 그룹을 찾고 각 반복된 그룹의 시작 사이의 문자 수를 계산한다.예를 들어, 암호문이 FGX인 경우THJAQWNFGXX, FGX 그룹 사이의 거리는 10이다.분석가는 반복된 모든 그룹의 거리를 텍스트에 기록한다.
2. 분석가는 이 숫자들 각각을 다음 요인으로 작용한다.이들 요인 대다수에 어떤 숫자가 반복되면 키워드의 길이가 될 가능성이 높다.이는 같은 문자가 단순한 우연의 일치보다는 동일한 키 문자를 사용하여 암호화될 때 반복된 그룹이 발생할 가능성이 높기 때문이다. 이는 특히 긴 일치 문자열의 경우에 해당된다.키 글자는 키 길이의 배수로 반복되기 때문에 1단계에서 발견되는 거리는 대부분 키 길이의 배수가 될 가능성이 높다.공통적인 요인은 대개 명백하다.
3. 키워드 길이가 알려지면 배비지와 카시스키의 다음과 같은 관찰이 작용한다.키워드가 다음과 같은 경우N글자 길이, 그 다음마다N그 편지는 키텍스트의 같은 문자를 사용하여 암호화된 것이 틀림없다.그룹화 간격N그 분석가는 함께 편지를 썼다.N각 피스는 1회 치환법을 사용하여 암호화되며, 각 피스는 주파수 분석을 사용하여 공격될 수 있다.
4. 분석가는 해결된 메시지를 이용해 키워드가 무엇이었는지 빠르게 판단할 수 있다.또는, 조각을 푸는 과정에서 분석가는 키워드에 대한 추측을 통해 메시지를 해독하는 데 도움을 줄 수 있다.
5. 일단 요격자가 키워드를 알게 되면, 그 지식은 같은 키를 사용하는 다른 메시지를 읽는 데 사용될 수 있다.

중첩

카시스키는 실제로 비게네르 암호를 풀기 위해 "초상화"를 사용하였다.그는 위와 같이 열쇠 길이를 찾는 것으로 시작했다.그런 다음 그는 여러 통의 메시지를 한 장씩 복사하여 키의 길이에 따라 각각 왼쪽으로 이동시켰다.그러자 카시스키는 각 열이 하나의 알파벳으로 암호화된 문자로 이루어져 있다는 것을 관찰했다.그의 방법은 위에서 설명한 것과 같았지만, 아마도 그림 그리기가 더 쉬울 것이다.

폴리 알파벳 암호에 대한 현대의 공격은 위에서 설명한 것과 본질적으로 동일하며, 우연 계산의 한 가지 개선이다.현대 분석가는 반복적인 그룹을 찾는 대신에 메시지를 두 부씩 복사하여 한 부씩 겹쳐 놓곤 했다.

현대 분석가들은 컴퓨터를 사용하지만, 이 설명은 컴퓨터 알고리즘이 구현하는 원리를 보여준다.

일반화된 방법:

1. 분석가는 맨 아래 메시지를 한 글자씩 왼쪽으로 옮기고, 그 다음에 한 글자씩 더 왼쪽으로 옮기고, 매번 전체 메시지를 거치면서 맨 위와 맨 아래 메시지에 같은 문자가 나타나는 횟수를 세어본다.
2. "공인"의 수는 하단 메시지가 키 길이의 배수로 이동될 때 급격히 증가하는데, 이는 인접한 문자가 동일한 알파벳을 사용하여 동일한 언어로 되어 있기 때문이다.
3. 키 길이를 찾은 후 주파수 분석을 통해 위에서 설명한 대로 암호해석을 진행한다.

참조