# 키 기반 치환 (Keyed Substitution)

키 기반 치환(keyed substitution)은 치환표, 즉 입력 값을 다른 값으로 바꾸는 표(S-box)의 내용 배열을 키에 따라 다르게 정하는 방식입니다. 크기와 들어 있는 값이 같은 두 치환표는 값의 순서(순열)만 다를 수 있으므로, 키로 그 순서를 고르는 것이 곧 키 설정입니다. 보통 키로 초기화한 난수 생성기를 써서 표를 섞는 방식으로 구현합니다.

## 자세히 알아보기

n비트 치환표는 2^n개의 항목을 가지며, 가능한 배열은 (2^n)!가지입니다. 8비트 표 하나만 해도 256! ≈ 2^1684가지로, 이론적인 키 공간이 약 1,684비트에 이릅니다. 다만 실제 안전성은 이 숫자가 아니라 표를 섞는 데 쓴 키의 길이와 섞는 과정의 품질에 따라 정해집니다.

표를 섞을 때는 피셔-예이츠(Fisher–Yates) 셔플처럼 모든 순열이 같은 확률로 나오는 알고리즘을 써야 하며, 난수를 범위에 맞출 때 모듈로 편향이 생기지 않게 해야 합니다. 키에 따라 표가 달라지면 공격자가 S-box 내용을 미리 알 수 없어서, S-box를 알고 있다고 가정하는 선형·차분 암호 분석을 그대로 적용하기 어려워집니다. 반면 표마다 비선형도·차분 균일도 같은 품질이 들쭉날쭉할 수 있고, 표 생성에 시간이 들며, 메모리 조회 시간 차이로 인한 캐시 타이밍 공격에 취약해질 수 있습니다.

## 블록체인·암호화폐에서는

- 역사적 사례: 블로피시와 투피시는 키에 의존하는 S-box를 쓰는 블록 암호이고, RC4는 키 스케줄링 단계에서 256바이트 순열을 키로 섞습니다. RC4는 출력 편향 때문에 현재 TLS에서 사용이 금지되었습니다(RFC 7465).
- 현대의 선택: 지갑·거래소·TLS에서 쓰는 AES와 ChaCha20은 키 기반 치환을 쓰지 않습니다. AES는 공개된 고정 S-box를 쓰는데, 수학적으로 검증된 최적에 가까운 S-box를 쓰는 편이 무작위로 섞은 표보다 분석과 상수 시간 구현에 유리하기 때문입니다.
- 셔플의 공정성 문제는 온체인 추첨·NFT 배정에서도 똑같이 나타나며, 검증 가능한 난수(VRF)와 편향 없는 셔플 알고리즘을 함께 써야 합니다.

## 쉽게 말하면

비밀 순서로 섞은 카드 한 벌을 암호표로 쓰는 것입니다. 같은 키를 가진 사람만 똑같이 섞을 수 있습니다.

## 예시

4개 항목 표 [0,1,2,3]을 키로 섞어 [2,0,3,1]을 얻었다면 0→2, 1→0, 2→3, 3→1로 치환하고, 복호화에는 역표 [1,3,0,2]를 씁니다.

---
출처: https://achivx.kr/glossary/keyed-substitution-%ED%82%A4-%EA%B8%B0%EB%B0%98-%EC%B9%98%ED%99%98/ · ACHIVX 용어 사전 · 수정일 2026-10-20