유니시티 거리

이 글은 검증을 위해 인용구가 추가로 필요하다. 신뢰할 수 있는 출처에 인용문을 추가하여 이 기사를 개선할 수 있도록 도와주십시오. 공급되지 않은 재료는 도전하여 제거할 수 있다. 출처 찾기: "유니시티 거리" – 뉴스 · 신문 · 책 · 학자 · JSTOR(2007년 10월) (이 템플릿 메시지를 제거하는 방법과 시기 학습)

암호학에서 단성 거리는 흉물 공격에서 가능한 모의 키의 수를 0으로 줄임으로써 암호를 해독하는 데 필요한 원래 암호문의 길이를 말한다. 즉, 가능한 모든 키를 시도한 후, 기본 메시지에 중복성이 있다고 가정하여 키를 완전히 결정하는 데 필요한 암호문의 예상 양인 하나의 해독만이 있어야 한다.^[1]

Claude Shannon은 1949년 논문 "비밀유지 시스템의 통신 이론"에서 단일성 거리를 정의했다.

5글자 키로 Vigenere 암호로 암호화된 암호 문자열 "WNAIW"에 대한 공격을 고려한다. 이 문자열은 다른 문자열로 해독할 수 있다.River와 WATER는 둘 다 특정 키에 대한 가능성이다. 이것은 암호해석의 일반적인 규칙이다. 추가 정보가 없으면 이 메시지를 해독할 수 없다.

물론 이 경우에도 일정 수의 5개의 문자키만 있으면 영어단어가 나오게 된다. 가능한 모든 키를 시도하면 REVEL과 WATER뿐만 아니라 SXOOS와 KHDOP도 얻을 수 있을 것이다. "작동" 키의 수는 가능한 모든 키의 집합보다 훨씬 적을 것이다. 문제는 이 "작동" 열쇠들 중 어느 것이 옳은지 아는 것이다. 나머지는 가짜다.

키 크기 및 가능한 일반 텍스트와의 관계

일반적으로 키의 크기와 가능한 메시지 수에 대한 특정한 가정을 할 때, 읽을 수 있는 메시지를 생성하는 키(평균)가 하나밖에 없는 평균 암호 텍스트 길이가 있다. 위의 예에서는 영문 대문자만 볼 수 있으므로 일반 텍스트가 이 형식을 가지고 있다고 가정하면 문자열의 각 위치에 대해 26개의 가능한 문자가 있다. 마찬가지로 5자로 된 대문자 키를 가정할 경우 K=26개의⁵ 가능한 키가 있으며, 그 중 대다수가 "작동"하지 않는다.

이 제한된 문자 집합 N = 26을^L 사용하여 수많은 가능한 메시지 N을 생성할 수 있으며 여기서 L은 메시지의 길이입니다. 그러나, 언어의 규칙, 아마도 M의 규칙 때문에 더 작은 집합만이 읽을 수 있는 일반 텍스트로 되어 있는데, 여기서 M은 N보다 훨씬 작을 가능성이 높다.게다가 M은 작동하는 키의 수와 일대일 관계를 맺고 있기 때문에, K 가능한 키를 감안하면, 이들 중 K × (M/N)만이 "작동"하게 된다. 이것들 중 하나는 정확한 열쇠고 나머지는 가짜다.

M/N은 메시지의 L 길이가 증가함에 따라 임의로 작아지기 때문에, 결국 가짜 키의 수를 0과 같게 만들 수 있을 만큼 큰 L이 있다. 대략, 이것은 KM/N=1을 만드는 L이다. 이 L은 단일성 거리야.

키 엔트로피 및 일반 텍스트 중복과의 관계

단일성 거리는 연산적으로 무제한의 적수가 고유한 암호화 키를 복구할 수 있도록 하기 위해 필요한 최소 암호문 양으로 동등하게 정의될 수 있다.^[1]

그러면 예상되는 단일성 거리는 다음과 같이 나타날 수 있다.^[1]

$[\displaystyle U=H(k)/D}$

여기서 U는 단일성 거리, H(k)는 키 공간의 엔트로피(예: 128 for 2¹²⁸ equipmentable keys, 오히려 키가 기억된 암호문자일 경우)이다. D는 글자당 비트 단위의 일반 텍스트 중복으로 정의된다.

이제 32자의 알파벳은 문자당 5비트(32 = 2⁵)의 정보를 전달할 수 있다. 일반적으로 문자당 정보의 비트 수는 로그₂(N)이며, 여기서 N은 알파벳의 문자 수, 로그는₂ 이진 로그다. 그래서 영어의 경우 각 문자는 로그₂(26) = 4.7비트의 정보를 전달할 수 있다.

그러나 의미 있는 영어 텍스트의 문자당 실제 정보 전달량은 문자당 평균 1.5비트 정도에 불과하다. 따라서 일반 텍스트 중복은 D = 4.7 - 1.5 = 3.2이다.^[1]

기본적으로 단일성 거리가 클수록 좋다. 무제한 크기의 1회용 패드에 대해, 키 공간의 무한 엔트로피를 고려하면, $우리$는${\displaystyle }$U = ${\displaystyle \mathrm{\infty }}$ ${\displaystyle$ U$=\infit }$을(를) 가지고 있는데$,$ 이는 1회용 패드가 깨지지 않는 것과 일치한다.

대체 암호의 고유성 거리

단순 치환 암호의 경우, 가능한 키의 수는 26! = 4.0329 × 10²⁶ = 2이며^88.4, 알파벳을 순열할 수 있는 방법의 수입니다. 모든 키가 동일하다고 가정하면 H(k) = log₂(26!) = 88.4비트. 영어 텍스트 D = 3.2, 따라서 U = 88.4/3.2 = 28.

따라서 28자의 암호문을 제공하면 이론적으로 영어의 일반 텍스트와 그에 따른 키를 알아내는 것이 가능해야 한다.

실용화

단성거리는 유용한 이론적 척도지만 실제(제한적) 자원을 가진 적에게 공격을 받았을 때 블록 암호의 보안에 대해서는 별로 말하지 않는다. 3개의 암호 텍스트 블록의 고유성 거리를 가진 블록 암호를 고려하십시오. 비록 계산적으로 무한대의 적수가 올바른 키를 찾기에 충분한 정보가 분명히 존재하지만(단순히 철저한 검색) 이는 실제로 계산적으로 실현 불가능할 수 있다.

일반 텍스트 중복성을 줄임으로써 단일성 거리를 늘릴 수 있다. 이를 위한 한 가지 방법은 암호화 전에 데이터 압축 기법을 배치하는 것이다. 예를 들어 가독성을 유지하면서 중복 모음을 제거하는 것이다. 암호화할 데이터의 양을 줄인다는 점에서 어쨌든 좋은 생각이다.

단일성 거리보다 큰 암호문은 하나의 의미 있는 암호 해독만 가지고 있다고 가정할 수 있다. 단일성 거리보다 짧은 암호문에는 여러 개의 그럴듯한 암호 해독이 있을 수 있다. 단성 거리는 암호해석에 필요한 암호문의 양을 측정하는 것이 아니라,^[why?] 암호해석을 위한 합리적인 해결책이 하나만 존재하기 위해서는 암호문의 양이 얼마나 필요한지를 측정하는 것이다.

참조

외부 링크

• 브루스 슈나이어: 일반 텍스트 인식 방법(1998년 12월 15일 Crypto-Gram 뉴스레터)
• 공통 암호에 대해 계산된 유니시티 거리