장점(암호화)

암호학에서, 적의 장점은 암호 알고리즘을 그러한 유형의 알고리즘의 이상화된 버전과 구별함으로써, 암호 알고리즘을 얼마나 성공적으로 공격할 수 있는지를 측정하는 척도다.이러한 맥락에서 "반복"은 그 자체가 알고리즘이며 사람이 아니라는 점에 유의한다.암호 알고리즘은 적국의 계산 자원에 대한 특정 한계(구체적 보안 참조)를 조건으로, 적에게 불가해한 장점을 가지고 있지 않은 경우 안전한 것으로 간주된다."불가결함"은 일반적으로 "O(2^−p) 내"를 의미하며 여기서 p는 알고리즘과 관련된 보안 매개변수다.예를 들어, p는 블록 암호 키에 있는 비트 수입니다.

개념 설명

F는 연구 중인 함수의 신탁이 되고, G는 그러한 유형의 이상화된 함수의 신탁이 되게 한다.적수 A는 F 또는 G를 입력으로 제공하고 1 또는 0을 출력하는 확률 알고리즘이다.A의 일은 F와 G를 구분하는 것으로, 주어진 오라클에 쿼리를 하는 것을 기본으로 한다.우리는 다음과 같이 말한다 $Adv(A)=|\Pr[A(F)=1]-\Pr[A(G)=1]|$ A $Adv(A)=|\Pr[A(F)=1]-\Pr[A(G)=1]|$ $Adv(A)=|\Pr[A(F)=1]-\Pr[A(G)=1]|$ ( $Adv(A)=|\Pr[A(F)=1]-\Pr[A(G)=1]|$ A ) $Adv(A)=|\Pr[A(F)=1]-\Pr[A(G)=1]|$ = $Adv(A)=|\Pr[A(F)=1]-\Pr[A(G)=1]|$ [ $Adv(A)=|\Pr[A(F)=1]-\Pr[A(G)=1]|$ ( $Adv(A)=|\Pr[A(F)=1]-\Pr[A(G)=1]|$ ) $Adv(A)=|\Pr[A(F)=1]-\Pr[A(G)=1]|$ = 1 $Adv(A)=|\Pr[A(F)=1]-\Pr[A(G)=1]|$ ] $Adv(A)=|\Pr[A(F)=1]-\Pr[A(G)=1]|$ - $Adv(A)=|\Pr[A(F)=1]-\Pr[A(G)=1]|$ [ $Adv(A)=|\Pr[A(F)=1]-\Pr[A(G)=1]|$ ( $Adv(A)=|\Pr[A(F)=1]-\Pr[A(G)=1]|$ ) = 1 $Adv(A)=|\Pr[A(F)=1]-\Pr[A(G)=1]|$ $displaystyle Adv(A)= \Pr[A(F)=1]-\Pr[A(G)=1] }}}}$

예

F는 DES 블록 암호의 무작위 인스턴스가 되도록 하자.이 암호는 64비트 블록과 56비트 키를 가지고 있다.따라서 키는 가능한 두 개의⁶⁴ 64비트 블록에서 2개의⁵⁶ 순열 중 하나를 선택한다."랜덤 DES 인스턴스"는 우리의 오라클 F가 동일한 확률을 가진 2개의⁵⁶ 가능한 키 중에서 K가 선택되는 일부 키 K를 사용하여 DES를 계산하는 것을 의미한다.

우리는 DES 인스턴스를 이상적인 64비트 블록 암호와 비교하기를 원한다. 즉, 64비트 블록의 가능한⁶⁴ 순열에서 무작위로 선택된 순열화를 의미한다.이것을 무작위로 선택한 순열 G라고 부른다.스털링의 근사치에서 (2)!는⁶⁴ 약 $10^{3.47\times 10^{20}}$ . $10^{3.47\times 10^{20}}$ × $10^{3.47\times 10^{20}}$ 20 $[\$ 47 $\times$ 10 $^{20$ 이므로, 어떤 순열을 선택했는지 지정하더라도 실제 컴퓨터에서 정확히 나타내기에는 너무 큰 숫자를 적어야 한다.또 다른 방법으로 보면, G는 "키 길이"가 10비트²¹ 정도 되는 "주변인"의 한 예로서, 이것은 다시 컴퓨터에 맞추기에는 너무 크다.(단, 랜덤 오라클을 사용하여 쿼리 수에 비례하는 스토리지 공간을 사용하여 G를 구현할 수 있다.)

주의할 점은, 우리가 선택한 암호화 일반 텍스트가 주어졌기 때문에, 우리는 선택된 일반 텍스트 공격이나 CPA를 모델링하고 있으며, 우리가 계산하고 있는 이점은 주어진 적수의 CPA 장점이라고 불릴 수 있다는 것이다.만약 우리가 암호 해독을 할 수 있다면, 우리는 선택된 암호 해독 공격이나 CCA를 할 것이고, 상대편의 CCA의 장점을 발견할 것이다.

예제 1: 무작위로 추측

이 적수를 A라고₀ 불러라.그것은 단순히 동전을 던져버리고, 신탁통화를 하지 않고 동일한 확률로 1이나 0을 돌려준다.따라서 Pr[A₀(F)=1]과 Pr[A₀(G)=1]은 모두 0.5이다.이러한 확률의 차이는 0이므로 Adv(A₀)는 0이다.우리가 항상 0을 반환하거나 항상 1을 반환하는 경우에도 같은 것이 적용된다: 확률은 F와 G 둘 다 같으므로 이점은 0이다.이 상대는 F와 G를 구별할 수 없다.만약 우리가 암호 설계자라면, 우리의 바램은 (아마도 달성할 수 없는) 어떤 적들이 이것보다 훨씬 더 잘 하는 것이 계산적으로 불가능하도록 만드는 것이다.만약 우리가 무차별적인 힘 검색보다 더 빠른 암호를 만들 수 있다면 우리는 성공할 것이다.

예 2: 브루트 포스 검색

이 적수(그것을₁ A라고 부름)는 무력으로 그 입력의 암호화를 시도할 것이다.독자적인 DES 구현을 하고 있다.모든 0의 64비트 문자열을 암호화하도록 요청하는 단일 쿼리를 오라클에 제공한다.결과 암호 텍스트 E를₀ 호출하십시오.그런 다음 철저한 키 검색을 실행한다.알고리즘은 다음과 같다.

E₀_k = k에 대한 oracle_query(0)(0)(0, 1,...,2-1⁵⁶: DES(0) == E₀: 반환 1

56비트 DES 키 공간 전체를 검색하고 일치하는 키를 찾을 경우 "1"을 반환한다.실제로 키를 확인하기 위해 여러 개의 일반 텍스트가 필요하다. 서로 다른 두 개의 키로 인해 하나 이상의 일반 텍스트-암호 텍스트 쌍이 일치할 수 있기 때문이다.키가 없으면 0을 반환한다.

입력오라클이 DES인 경우, 이 철저한 검색은 키를 찾을 것이 확실하므로 Pr[A₁(F)=1] = 1. 입력오라클이 임의 순열인 경우 E의 가능한₀ 값이 2개⁶⁴ 있으며, 그 중 최대 2개는⁵⁶ DES 키 검색에서 검사를 받게 된다.따라서 A가₁ 1을 반환할 확률은 최대 2이다⁻⁸.즉,

$Pr[A_{1}(G)=1]\leq 2^{-8}$ $Pr[A_{1}(G)=1]\leq 2^{-8}$ [ $Pr[A_{1}(G)=1]\leq 2^{-8}$ 1 $Pr[A_{1}(G)=1]\leq 2^{-8}$ ( $Pr[A_{1}(G)=1]\leq 2^{-8}$ ) $Pr[A_{1}(G)=1]\leq 2^{-8}$ = $Pr[A_{1}(G)=1]\leq 2^{-8}$ $Pr[A_{1}(G)=1]\leq 2^{-8}$ $Pr[A_{1}(G)=1]\leq 2^{-8}$ $Pr[A_{1}(G)=1]\leq 2^{-8}$ - $Pr[A_{1}(G)=1]\leq 2^{-8}$ ${\$ 그러므로