우연의 일치 지수

이 글은 일반적인 참고문헌 목록을 포함하고 있지만, 그에 상응하는 인라인 인용구가 충분하지 않다. 보다 정확한 인용문을 도입하여 이 기사를 개선할 수 있도록 도와주십시오. (2009년 3월) (이 템플릿 메시지를 제거하는 방법과 시기 알아보기)

암호학에서는 우연 계산이 기술이다(윌리엄 F에 의해 발명되었다). 두 개의 텍스트를^[1] 나란히 놓고 두 텍스트에서 동일한 문자가 동일한 위치에 나타나는 횟수를 계산하는 프리드먼)이 카운트는 총수의 비율로 또는 무작위 소스 모델의 예상 카운트로 나누어 정규화하거나, 우연의 일치 지수 또는 짧은 IC로 알려져 있다.

자연어 문자는 균일하게 분포되지 않기 때문에, IC는 균일하게 무작위 텍스트 문자열보다 그러한 텍스트의 경우 더 높다.IC를 특히 유용하게 만드는 것은 두 텍스트가 동일한 단일 알파벳 대체 암호에 의해 스크램블되어 암호화 분석가가 그 형태의 암호화를 신속하게 검출할 수 있다면 그 값이 변하지 않는다는 사실이다.

계산

우연의 일치 지수는 주어진 텍스트에서 임의로 두 글자를 선택하여 일치하는 두 글자를 그릴 확률을 측정한다.텍스트에서 주어진 문자를 그릴 확률은 (글자가 나타나는 횟수/텍스트 길이)이다.(교체하지 않고) 같은 문자를 다시 그릴 기회는 (표현 - 1 / 텍스트 길이 - 1)이다.이 두 값의 산물은 당신에게 그 글자를 연속해서 두 번 그릴 기회를 준다.텍스트에 나타나는 각 글자에 대해 이 제품을 찾은 다음, 이 제품들을 합쳐서 두 종류의 그림을 그릴 기회를 얻을 수 있다.이 확률은 일부 계수(일반적으로 영어로 26)를 곱하여 정규화할 수 있다.

${\displaystyle \mathbf {IC} =c\times \left({\left({{\frac {n_{\mathrm {a} }}{N}}\times {\frac {n_{\mathrm {a} }-1}{N-1}}}\right)+\left({{\frac {n_{\mathrm {b} }}{N}}\times {\frac {n_{\mathrm {b} }-1}{N-1}}}\right)+\cdots +\left({{\frac {n_{\mathrm {z} }}{N}}\times {\frac {n_{\mathrm {z} }-1}{N-1}}}\right)}\right)}$

여기서 c는 정규화 계수(영어의 경우 26), n은_a 텍스트에 "a"가 나타나는 횟수, N은 텍스트의 길이다.

주어진 문자-주파수 분포에 대한 우연의 일치 IC 지수를 합계로서 표현할 수 있다.

${\displaystyle \mathbf {IC} ={\frac {\displaystyle \sum _{i=1}^{c_n(n_{i}-1){N(N-1)/c}}}$

여기서 N은 텍스트의 길이, n₁ ~ n은_c 알파벳의 c 문자의 주파수(정수로서)이다(단일 영어의 경우 c = 26).n의_i 합은 반드시 N이다.

n(n - 1) 제품은 한 번에 두 개씩 추출한 n 원소의 조합 수를 계산한다.(실제로 이것은 각 쌍을 두 번 계산한다; 2의 추가 요인은 공식의 분자와 분모에서 모두 발생하여 취소한다.)i번째 문자의 n번째_i 발생 각각은 동일한 문자의 n번째_i 발생 각각과 일치한다.전체 텍스트에는 총 N(N - 1)자 쌍이 있으며, 1/c는 문자의 균일한 무작위 분포를 가정하여 각 쌍에 대해 일치할 확률이다("null model"; 아래 참조).따라서 이 공식은 관측된 총 우연 횟수에 대해 null 모델에서 예상할 수 있는 총 우연 횟수의 비율을 제공한다.^[2]

IC에 대한 기대 평균 값은 소스 언어의 상대 문자 주파수 f에서_i 계산할 수 있다.

${\displaystyle \mathbf {IC} _{\mathrm {expected}{}={\frac {\displaystyle \sum \{i=1}^{f_{i}^{1}2}}/c}.}$

알파벳의 모든 c 글자가 동등하게 개연성이 있는 경우, 기대지수는 1.0이 될 것이다.실제 전신 영어 텍스트의 단문 IC는 약 1.73으로, 자연어 문자 분포의 불균형을 반영하고 있다.

때때로 영어의 경우 0.067 = 1.73/26과 같이 분모 정규화 없이 보고되는 경우가 있다. 이러한 값을 IC가 아닌_p ("("kappa-plaintext")라고 부를 수 있으며, 분모 1/c(영어에서는 0.0385=1/26)를 나타내기 위해 사용되는_r ("("kappa-random")이다.

적용

우연의 일치 지수는 자연어 평문 분석과 암호문 분석(암호분석)에서 모두 유용하다.암호문만 시험에 사용할 수 있고, 일반문자 ID가 위장되어 있어도, 암호문에서의 우연은 기초적인 평문에서의 우연에 의해 야기될 수 있다.예를 들어 이 기술은 비게네르 암호를 암호화하는 데 사용된다.행렬로 배열된 반복키 다형자 암호의 경우, 행렬의 폭이 키 길이의 배수일 때 각 열 내의 우연률은 대개 가장 높을 것이며, 이 사실은 시스템을 균열하는 첫 단계인 키 길이를 결정하는 데 사용될 수 있다.

우연의 일치로 계산하면 같은 알파벳을 사용하여 두 개의 지문이 같은 언어로 쓰여지는 시기를 결정하는 데 도움이 될 수 있다.(이 기술은 속칭 성경 코드를 검사하는 데 사용되었다.)그러한 텍스트에 대한 인과 우연의 일치 수는 다른 언어의 텍스트나 다른 알파벳을 사용하는 텍스트 또는 횡설수설 텍스트의 우연의 일치 계수보다 분명히 더 높을 것이다.

그 이유를 알아보려면 A와 B 두 글자의 "알파벳"을 상상해보라.우리의 "언어"에서 문자 A는 75%가 사용되고 문자 B는 25%가 사용된다고 가정해 보자.이 언어로 된 두 개의 텍스트가 나란히 놓여 있는 경우, 다음과 같은 쌍을 기대할 수 있다.

짝을	확률
AA	56.25%
BB	6.25%
AB	18.75%
BA	18.75%

전체적으로 "공인" 확률은 62.5%(AA의 경우 56.25% + BB의 경우 6.25%)이다.

이제 두 메시지가 모두 A를 B로 대체하거나 A를 B로 대체하는 단순한 모노 알파벳 대체 암호를 사용하여 암호화되는 경우를 생각해 보십시오.

짝을	확률
AA	6.25%
BB	56.25%
AB	18.75%
BA	18.75%

이 상황에서 우연의 전체적인 확률은 62.5%(AA의 경우 6.25% + BB의 경우 56.25%), 암호화되지 않은 "일반 텍스트" 사례와 정확히 동일하다.사실상 대체에 의해 생성된 새 알파벳은 원래 문자 정체성의 획일적인 개명에 불과해 일치 여부에 영향을 미치지 않는다.

이제 동일한 대체 암호(A,B)→(B,A)를 사용하여 하나의 메시지(예: 두 번째)만 암호화된다고 가정합시다.이제 다음과 같은 쌍을 기대할 수 있다.

짝을	확률
AA	18.75%
BB	18.75%
AB	56.25%
BA	6.25%

현재 우연의 일치 가능성은 37.5%(AA의 경우 18.75% + BB의 경우 18.75%)에 불과하다.이는 같은 언어의 알파벳 문자를 사용했을 때보다 눈에 띄게 낮다.분명히, 각 텍스트에서 가장 빈번한 문자가 동일할 때 우연의 일치 가능성이 더 높다.

E와 같은 특정 문자는 다른 문자보다 훨씬 더 자주 발생하기 때문에 영어와 같은 실제 언어에도 같은 원리가 적용된다.예를 들어, E와 관련된 우연들은 비교적 가능성이 높다.그래서 어떤 두 개의 영어 원문을 비교했을 때, 우연의 일치도는 영어 원문과 외국어 원문을 사용할 때보다 더 높을 것이다.

이런 효과가 미묘할 수 있다는 것은 쉽게 상상할 수 있다.예를 들어, 유사한 언어는 다른 언어보다 우연의 일치 수가 더 많을 것이다.또한 실제 텍스트와 유사한 주파수 분포로 무작위 텍스트를 생성하는 것도 어렵지 않아 인위적으로 우연 카운트를 증가시킨다.그럼에도 불구하고, 이 기법은 두 텍스트가 동일한 알파벳을 사용하여 동일한 언어로 의미 있는 정보를 포함할 가능성이 있는 경우를 식별하고, 반복 키의 기간을 발견하며, 암호문 내부 또는 암호문 사이에 있는 많은 다른 종류의 비랜덤 현상을 발견하는 데 효과적으로 사용될 수 있다.

다양한 언어의^[3] 예상 값은 다음과 같다.

언어	우연 지수
영어	1.73
프랑스어	2.02
독일어	2.05
이탈리아의	1.94
포르투갈어	1.94
러시아어	1.76
스페인어	1.94

일반화

위의 설명은 일반적인 상관관계 개념과 관련이 있는 우연지수를 사용하기 위한 소개일 뿐이다.다양한 형태의 우연지수가 고안되었다; "델타" 아이씨(위의 공식에 의해 주어짐)는 사실상 단일 분포의 자기 상관을 측정하는 반면, "카파" 아이씨는 두 텍스트 문자열을 일치시킬 때 사용된다.^[4]$일부{\displaystyle }$ 애플리케이션에서는 c ${\displaystyle c}$ $및{\displaystyle }$ N$$ ${\displaystyle N}$과 같은 상수 인자를 무시할 수 있지만$$, 보다 일반적인 상황에서는 귀무 가설에서 예상되는 값(일반적으로: 일치하지 않고 균일한 무작위 기호 분포)에 대해 각 IC를 실제로 지수화하는 데 상당한 가치가 있다.y 상황: 상관 관계가 없는 경우 기대값은 1.0이다.따라서 어떤 형태의 IC도 특정 시험 설정을 사용하여 (null 모델에 따라) 예상되는 우연 수에 실제로 관측된 우연 수의 비율로 표현할 수 있다.

앞에서 보면 카파 IC의 공식은 쉽게 알 수 있다.

${\displaystyle \mathbf {IC} ={\frac {\displaystyle \sum _{j=1}^{N}[a_{j}=b_{j}]}}{N/c},}$

여기서 $N{\displaystyle }$ ${\displaystyle N}$은(는) 두 텍스트 A와 B의 공통$$ 정렬 길이이며, A $텍스트$의$$j {\$displaystyle$ j$}$ -th$$ 글자가 $텍스트{\displaystyle }$B의 j {\$displaysty$ j} -th$$ 글자와 일치하면 1로 정의된다.

관련 개념인 분포의 "거품"은 관측된 IC와 null 값 1.0 사이의 차이를 측정한다.다형 알파벳 암호에 사용되는 암호 알파벳의 수는 많은 경우(예: 반복 키가 사용된 경우) 더 나은 기술을 사용할 수 있지만, 단일 알파벳에 대한 델타 I.C.의 예상 불량을 메시지에 대한 관측 불량으로 나누어 추정할 수 있다.

예

IC의 사용에 대한 실제적인 예로서, 다음과 같은 암호문 메시지를 가로챘다고 가정해 보십시오.

QPWKA LVRXC QZIKG RBPFA EOMFL  JMSDZ VDHXC XJYEB IMTRQ WNMEA IZRVK CVKVL XNEIC FZPZC ZZHKM  LVZVZ IZRRQ WDKEC HOSNY XXLSP MYKVQ XJTDC IOMEE XDQVS RXLRL  KZHOV

(5자로 묶는 것은 전신 규약일 뿐 실제 단어 길이와는 아무런 관계가 없다.)이것을 정상 A-Z 구성요소를 가진 Vigenér 암호와 짧은 반복 키워드를 사용하여 암호화된 영어 일반 텍스트로 의심하면, 우리는 암호문을 몇 개의 열(예: 7개)에 "stacked"한 것으로 생각할 수 있다.

QPWKALV RXCQZIK GRBPFAE OMFLJMS DZVDHXC XJYEBIM TRQWN…

만약 키 크기가 가정된 열의 수와 같다면, 단일 열 내의 모든 문자는 동일한 키 문자를 사용하여 암호화된 것이며, 사실상 영어 평문자의 무작위 선택에 간단한 카이사르 암호를 적용했을 것이다.해당 암호문자 집합은 문자 정체성이 서열화되었지만(키 문자에 해당하는 일정한 양으로 변함) 영어와 유사한 주파수 분포의 거칠기를 가져야 한다.따라서 모든 열에 대해 총 델타 I.C.를 계산하면("델타 바") 약 1.73이 되어야 한다.반면 키 크기(칼럼 수)를 잘못 알아맞혔다면 총 델타 IC는 1.00 정도여야 한다.그래서 우리는 델타 IC를 1에서 10까지 가정된 키 크기에 대해 계산한다.

크기	델타 바 IC
1	1.12
2	1.19
3	1.05
4	1.17
5	1.82
6	0.99
7	1.00
8	1.05
9	1.16
10	2.07

우리는 키 사이즈가 5일 가능성이 높다는 것을 안다.실제 크기가 5라면 각각의 열은 단순한 카이사르 암호화에 해당하기 때문에 10의 폭도 높은 IC를 보고할 것으로 예상하며, 우리는 이를 확인하게 된다.그래서 우리는 암호문을 다섯 개의 열로 쌓아야 한다.

QPWKA LVRXC QZIKG RBPFA UMFL JMSDZ VDH…

이제 우리는 별도로 고려되는 각 열에 대해 가장 가능성이 높은 키 문자를 결정할 수 있다, 키 문자에 대해 26가지 가능성 각각에 대해 카이사르 해독을 실시하고, 암호 해독된 열 문자 주파수와 상대 문자 fr 사이에 가장 높은 상관 관계를 생성하는 키 문자를 선택함으로써.일반 영어 텍스트의 등고정상화를 걱정할 필요가 없는 그 상관관계는 쉽게 다음과 같이 계산할 수 있다.

${\displaystyle \mathbf {\chi } =\sum _{i=1}^{c}n_{i}f_{i}}}}}}}$

여기서 $n{\displaystyle {}_{}}$ ${\displaystyle i_{}}$ ${\$는 관측된 열 문자 주파수이고 f i ${\$는 영어의 상대적인 문자 주파수다.우리가 이것을 시도할 때, 가장 잘 맞는 키 글자는 "라고 보고된다.EVERY"라는 단어를 실제 단어로 인식하고, 이 단어를 Vigenere 암호 해독에 사용하면 다음과 같은 일반 텍스트가 생성된다.

MUSTC HANGE MEETI NGLOC ATION FROMB RIDGE TOUND ERPAS  SSINC EENEM YAGEN TSARE BELIE VEDTO HAVEB EENAS SIGNE  DTOWA TCHBR IDGES TOPME ETING TIMEU NCHAN GEDXX

여기서 다음을 얻는다.

적 요원이 교량 중지를 감시하도록 지정되었으므로 회의 위치를 교량에서 지하도로 변경해야 함 XX

분명한 위치에 워드 사단이 복구된 후"XX"는 분명히 전송을 위해 최종 그룹을 패딩하는 데 사용되는 "반복적인" 문자들이다.

이 전체 절차는 그러한 암호를 해독하기 위한 자동화된 알고리즘으로 쉽게 포장될 수 있다.정상적인 통계적 변동으로 인해, 그러한 알고리즘은 특히 짧은 암호문 메시지를 분석할 때 때때로 잘못된 선택을 할 것이다.

참조

참고 항목

• 카시스키 시험
• 리버뱅크 출판물
• 암호학의 주제