비트 순열 (Bit Permutation)

비트 순열(bit permutation)은 데이터 블록 안의 비트 값은 그대로 두고 위치만 정해진 규칙에 따라 재배치하는 연산입니다. 문헌과 분야에 따라 비트 전치(bit transposition), 비트 셔플링(bit shuffling)이라고도 부릅니다. 블록 암호와 해시 함수에서 한 비트의 영향을 여러 위치로 퍼뜨리는 확산(diffusion) 층으로 쓰이며, 키에 따라 순열을 바꾸는 방식은 비트 전치 암호라고 부릅니다.

자세히 알아보기

n비트 블록의 비트 순열은 n!가지가 있습니다. 비트 순열은 1의 개수(해밍 무게)를 바꾸지 않고, GF(2) 위의 선형 변환이므로 혼자서는 안전성을 제공하지 못합니다. 입력과 출력의 관계가 선형 방정식으로 바로 드러나기 때문입니다. 두 입력을 XOR한 뒤 순열을 적용한 결과는 각각 순열을 적용한 뒤 XOR한 결과와 같고, 1과 0의 분포도 그대로 남습니다. 순열 규칙을 비밀로 하더라도 평문과 결과의 쌍 몇 개만 있으면 규칙이 드러납니다. 그래서 반드시 S-box 같은 비선형 치환과 번갈아 사용하며, 이 조합이 치환-순열 네트워크(SPN)입니다. 한편 같은 규칙의 역순열을 적용하면 원래 데이터를 정확히 되돌릴 수 있습니다.

비트 순열의 장점은 구현 비용입니다. 하드웨어에서는 배선만 바꾸면 되므로 사실상 공짜이고, 소프트웨어에서는 시프트·마스크·조회표로 구현합니다. 반면 범용 CPU에서 임의의 비트 순열은 느릴 수 있어, 현대 소프트웨어 지향 암호는 워드 단위 회전이나 바이트 단위 재배치를 선호합니다. 최신 CPU의 벡터 명령으로 이 비용을 줄이기도 합니다. 순열은 각 S-box의 출력이 다음 라운드에서 서로 다른 S-box들로 흩어지도록 설계해야 확산 효과가 큽니다.

암호 밖의 쓰임

• 데이터 압축 전처리: 과학 데이터 저장 라이브러리 등에서 쓰이는 비트셔플(bitshuffle) 필터는 정수나 부동소수점 배열에서 같은 자리의 비트끼리 모아 재배치합니다. 이웃한 값들의 상위 비트는 서로 비슷한 경우가 많아 0이나 1이 길게 이어지는 구간이 생기고, 뒤따르는 압축 알고리즘이 더 잘 압축합니다. 셔플링 자체가 데이터 크기를 줄이는 것은 아니며, 효과는 데이터의 성질에 따라 다릅니다.
• 채널 코딩(인터리빙): 전송 전에 비트 순서를 섞어 두면 잡음 때문에 연속된 비트가 한꺼번에 손상되는 버스트 오류가 수신 측에서 여러 위치로 흩어져, 오류 정정 부호로 고치기 쉬워집니다. 순열 자체가 오류를 감지하거나 고치는 것은 아닙니다.
• 데이터 숨기기: 비트 수준에서 다른 데이터 안에 정보를 숨기는 기법에서 비트 위치를 재배치하는 데 쓰입니다.

비트 셔플링, 비트 전치, 비트 순열은 거의 같은 뜻으로 쓰이므로, 문맥에서 압축용 전처리인지 암호 구성 요소인지 확인하는 것이 좋습니다.

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

• Keccak-256: 이더리움 주소와 트랜잭션 해시를 만드는 Keccak의 각 라운드에는 ρ(레인 안의 비트 회전)와 π(레인 위치 재배치)라는 순열 단계가 있고, 이들이 θ와 함께 확산을 담당합니다. 비선형성은 χ 단계가 맡습니다.
• DES와 경량 암호: 56비트 키 때문에 지금은 안전하지 않아 표준에서 폐기된 DES는 초기 순열(IP)과 라운드 내 P-박스를 사용했습니다. 경량 블록 암호 PRESENT는 64비트 비트 순열을 확산 층으로 씁니다.
• ChaCha20·SHA-256: 지갑 통신과 비트코인 채굴에 쓰이는 이 알고리즘들은 순수한 비트 순열 대신 워드 회전(rotate)을 사용하는데, 회전도 비트 순열의 한 종류입니다.

쉽게 말하면

비트 순열은 줄 서 있는 사람들의 자리만 정해진 대로 바꾸는 것입니다. 사람(비트 값)은 그대로이고 순서만 섞입니다.

예시

8비트 순열 규칙 '위치 i → 위치 (3i mod 8)'을 10110000에 적용하면(맨 왼쪽 비트를 위치 0으로 봄) 위치 0~7의 비트가 각각 위치 0, 3, 6, 1, 4, 7, 2, 5로 옮겨져 결과는 11000010입니다. 1의 개수(3개)는 그대로입니다.

규칙이 i → 3i mod 8처럼 주어지면 3과 8이 서로소이므로 모든 위치가 정확히 한 번씩 쓰여 진짜 순열이 됩니다. 반면 i → 2i mod 8 같은 규칙은 위치가 겹쳐 순열이 아닙니다.

모든 비트를 왼쪽으로 한 자리씩 옮기고 맨 왼쪽 비트를 오른쪽 끝으로 보내는 순환 이동(rotation)도 비트 순열입니다. 10011에 적용하면 00111이 되며, 역시 1의 개수(3개)는 그대로입니다.