복합 암호체계 암호해독의 매개변수 복잡도 분석

본 연구는 다중 암호 변환 계층으로 구성된 고전 암호체계의 암호해독을 위한 포괄적인 매개변수 복잡도 프레임워크를 제시한다. 이는 암호해독 문제의 계산 복잡도를 심층적으로 이해하고 효율적인 알고리즘 개발의 기반을 마련한다. 주요 이론적 기여는 세 가지다. 첫째, 구조적 복잡도 벡터 (k, ℓmax, |Σ|)를 매개변수로 사용할 경우 Cipher-Decode 문제가 고정 매개변수 추적 가능(FPT)함을 증명하고, O*(|Σ|k·ℓmax)의 실행 시간을 갖는 알고리즘을 제안한다. 둘째, 레이어 수 k만을 매개변수로 할 경우 이 문제가 para-NP-hard이며, k-Clique로부터의 완전한 형식적 환원을 통해 W[1]-hard임을 입증하여 엄격한 복잡도 이분법을 제공한다. 셋째, 쿨백-라이블러 발산 및 일치 지수(Index of Coincidence) 기반의 통계적 가지치기를 활용한 분기 한정(branch-and-bound) 알고리즘을 설계했다. 이 알고리즘은 탐색 공간을 완전 탐색 대비 2~6 자릿수까지 효과적으로 줄여준다. 비즈네르, 치환, ADFGVX 및 다층 복합 암호 등 47개 벤치마크 인스턴스에 대한 실험 평가를 통해 이론적 스케일링 예측(R2 = 0.9998)을 확인했으며, 순진한 기준선 대비 115배에서 2000배 이상의 속도 향상을 입증했다. 이는 다층 고전 암호 암호해독에 대한 최초의 엄격한 FPT 분석이다.