암호 분석에서의 양자 무차별 대입

암호화에 대한 양자 무차별 대입 공격

무차별 대입 키 탐색 공격은 가능한 평문의 공간이 전체 문자 공간보다 훨씬 작을 때 적용됩니다. 이브는 앨리스가 밥에게 보낸 암호문을 가로채고 두 가지 함수를 구현합니다: DECRYPT(key, ciphertext)로 복호화하고, ISPLAINTEXT(text)로 텍스트가 유효한 평문 집합에 속하는지 확인합니다. 암호화가 블록 기반이라면 DECRYPT는 블록 단위로 작동하고, ISPLAINTEXT는 결과를 누적합니다.

공격의 의사 코드는 간단합니다:

for each key
    text = DECRYPT(key, ciphertext)
    if ISPLAINTEXT(text) == 0 then return (key,text)
end for

ISPLAINTEXT 기준은 데이터베이스 없이 문자 통계, 조합 또는 휴리스틱을 사용합니다—빈도, 엔트로피 또는 언어 패턴을 확인합니다.

성공 평가를 위한 정보 이론

단일 알파벳 암호의 경우, 우리는 거짓 양성의 확률을 추정합니다:

• LENGTH(plaintext) — 비트 단위 길이
• LENGTH(key) — 키 길이(비트)
• LENGTH(ciphertext) — 암호문 길이(비트)
• ENTROPY(plaintext) — 평문의 섀넌 엔트로피

조건:

• LENGTH(plaintext) ≤ LENGTH(ciphertext)
• 거짓 통과 확률: 2^-(LENGTH(plaintext) - ENTROPY(plaintext))
• 만약 LENGTH(plaintext) - ENTROPY(plaintext) > LENGTH(key)라면, 키는 고유하게 결정됩니다

길이 보존 알고리즘의 경우: LENGTH(ciphertext) - ENTROPY(plaintext) ≥ LENGTH(key)일 때, 공격은 키를 보장되게 찾습니다.

무차별 대입에 대한 양자 접근법

양자 컴퓨팅은 큐비트의 중첩과 얽힘에 의존합니다. N개의 얽힌 큐비트 레지스터는 2^N개의 고전적 상태와 동등합니다. 산술 연산(덧셈, 곱셈, 시프트)은 양자 게이트—유니터리 연산자의 변환—로 구현됩니다.

키 레지스터에 대한 모든 고전적 함수는 유니터리 U(K)로 변환될 수 있으며, 여기서 K는 모든 키의 중첩입니다.

키 탐색을 위한 그로버 알고리즘

양자 공격의 단계:

• 길이 LENGTH(key)의 레지스터 K를 모든 키의 균일 중첩으로 초기화: |K⟩ = (1/√2^{LENGTH(key)}) Σ |key⟩
• 오라클 U(K) = DECRYPT(K, ciphertext)를 적용한 후, ISPLAINTEXT(U(K)): ISPLAINTEXT == 0인 상태에 대해 위상이 반전됩니다
• 그로버 알고리즘을 사용하여 목표 상태의 진폭을 증폭: π/4 * √2^{LENGTH(key)} 반복(확산 연산자와 오라클 사용)
• 레지스터 K를 측정—확률 ~1로 올바른 키로 붕괴됩니다

오라클은 DECRYPT와 ISPLAINTEXT를 가역 양자 회로로 구현해야 합니다. 블록 암호의 경우—보조 큐비트와 함께 블록 단위로 처리합니다.

// 양자 회로 의사 코드 (Q# 스타일)
operation BruteForce(keyReg : Qubit[], ciphertext : String) : (Int, String) {
    // 모든 큐비트에 H 적용하여 중첩 생성
    ApplyToEach(H, keyReg);
    // 오라클: ISPLAINTEXT(DECRYPT(keyReg, ciphertext)) == 0이면 위상 반전
    Oracle(keyReg, ciphertext);
    // 그로버 반복
    for iter in 0 .. GroverIterations() - 1 {
        GroverDiffusion(keyReg);
        Oracle(keyReg, ciphertext);
    }
    // 측정
    let key = MeasureKey(keyReg);
    return (0, DECRYPT(key, ciphertext));
}

2차 속도 향상: O(2^{LENGTH(key)}) 대신 O(√2^{LENGTH(key)}).

핵심 요약

• 고전적 vs. 양자: CPU에서 128비트 키 무차별 대입—10^38 연산; 양자 컴퓨터에서—10^19.
• 성공 조건: 실용적인 공격을 위해 평문 중복성(LENGTH - ENTROPY) > LENGTH(key)/2.
• 한계: NISQ 시스템의 노이즈는 오류 정정이 필요함; DECRYPT 오라클은 AES 유사 암호에 복잡함.
• 포스트-양자 암호화: 격자 기반, 해시 기반 방식으로의 전환이 필수적.
• 실습: Q# / Cirq 시뮬레이터로 20비트 키에서 시연 가능.

— Editorial Team