체커보드 구조 (Checkerboard Construction)

체커보드 구성(checkerboard construction)은 작은 라틴 방진의 각 기호를 서로 다른 기호 집합을 쓰는 또 다른 라틴 방진으로 바꾸어 더 큰 라틴 방진을 만드는 방법입니다. 차수 n인 기본 방진과 차수 m인 작은 방진들로 차수 n×m인 라틴 방진을 얻습니다. 테리 리터(Terry Ritter)의 암호 용어집은 이를 키에 따라 달라지는 다양한 라틴 방진을 만드는, 암호에서는 비교적 새로운 방법으로 소개합니다.

배경: 라틴 방진이 많이 필요한 이유

라틴 방진은 n개의 기호를 n×n 격자에 배치하되 각 행과 각 열에 모든 기호가 정확히 한 번씩 나오도록 한 배열입니다. 암호 설계에서는 라틴 방진을 치환 표처럼 써서 두 값을 섞는 결합기로 이용할 수 있고, 이때 키에 따라 달라지는 서로 다른 방진, 특히 직교 라틴 방진이 많이 필요합니다. 통계적 실험 설계용의 간단한 구성법은 있지만, 겉보기에 무작위인 방진을 대량으로 만드는 데는 거의 도움이 되지 않습니다.

구성 방법

1. 차수 n인 기본 라틴 방진을 고릅니다.
2. 기본 방진에 쓰인 n개의 기호마다, 서로 겹치지 않는 기호 집합(각 m개)을 하나씩 대응시킵니다.
3. 기본 방진의 각 칸을, 그 칸의 기호에 대응하는 기호 집합으로 만든 차수 m인 라틴 방진으로 바꿉니다.

기본 방진의 한 행에는 n개의 기호가 한 번씩 나오므로, 큰 방진의 각 행에는 서로 다른 n개의 기호 집합이 블록 단위로 한 번씩 들어갑니다. 각 블록 안에서는 그 집합의 m개 기호가 한 번씩 나오므로, 큰 방진의 모든 행과 열에 n×m개의 기호가 정확히 한 번씩 나타납니다. 열에 대해서도 같은 논리가 성립합니다. 예를 들어 차수 2인 기본 방진과 차수 3인 작은 방진 두 개로 차수 6인 방진을 만들 수 있습니다.

조합론에서는 같은 구성을 라틴 방진의 직접곱(direct product)이라고 부르며, 직교하는 방진 쌍끼리 이렇게 결합하면 결과도 직교하는 쌍이 된다는 성질이 알려져 있습니다.

다양성과 한계

기본 방진, 각 칸에 넣는 작은 방진, 기호 집합의 대응 방식을 바꾸면 매우 많은 서로 다른 큰 방진을 만들 수 있으므로, 이 선택을 키로 정하는 방식이 가능합니다. 이때 다양성은 기본 방진의 선택과 작은 방진에 쓰는 기호 집합의 배치에서 나옵니다.

다만 결과 방진은 블록 구조를 그대로 지니므로 완전히 무작위인 라틴 방진과는 통계적으로 구별될 수 있습니다. 따라서 이렇게 만든 방진을 쓰는 암호 시스템이 암호학적으로 안전한지는 별도로 분석하고 검증해야 하며, 이 방법은 표준화된 암호 기법이 아니라 설계 아이디어의 하나로 보는 것이 적절합니다. 큰 방진을 표로 저장하면 칸 수가 (n×m)의 제곱에 비례해 늘어나므로 메모리와 계산 부담도 구현상 고려해야 합니다.