파이스텔 구조 (Feistel Construction)

파이스텔 구조는 입력 블록을 왼쪽과 오른쪽 두 반쪽으로 나누고, 한쪽 반에 라운드 함수를 적용한 결과를 다른 쪽 반에 XOR한 뒤 두 반을 맞바꾸는 과정을 여러 라운드 반복하는 블록 암호 설계 방식입니다. DES가 대표적인 예입니다.

자세히 알아보기

한 라운드는 다음과 같이 계산합니다. 라운드 키를 K_i, 라운드 함수를 F라고 하면

• L_{i+1} = R_i
• R_{i+1} = L_i ⊕ F(R_i, K_i)

가장 큰 장점은 F가 역함수를 가지지 않아도 전체 구조는 항상 되돌릴 수 있다는 점입니다. 복호화는 같은 과정을 라운드 키 순서만 거꾸로 해서 수행합니다(L_i = R_{i+1} ⊕ F(L_{i+1}, K_i)). 그래서 암호화와 복호화에 같은 회로나 코드를 거의 그대로 쓸 수 있어 하드웨어 구현이 간단합니다.

한 라운드에서는 블록의 절반만 바뀌므로 충분한 확산을 얻으려면 여러 라운드가 필요합니다. DES는 16라운드를 씁니다. 이론적으로는 Luby와 Rackoff가 F가 안전한 의사난수 함수라면 3라운드로 의사난수 순열, 4라운드로 강한 의사난수 순열을 얻는다는 것을 증명했습니다. 실제 보안은 F의 품질(비선형성, S-박스 설계)과 키 스케줄에 달려 있습니다.

이름은 IBM에서 Lucifer 암호를 설계한 Horst Feistel에서 왔습니다. DES, Blowfish, Twofish, Camellia 등이 파이스텔 구조를 쓰며, AES는 파이스텔 구조가 아닌 치환-순열 네트워크(SPN) 방식입니다. 참고로 DES는 56비트 키 때문에 현재는 안전하지 않으며, 새 시스템에는 AES를 써야 합니다.

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

블록체인 핵심 프로토콜이 파이스텔 암호를 직접 쓰는 경우는 드물지만, 영지식 증명용으로 설계된 일부 해시·암호(예: MiMC의 파이스텔 변형)처럼 같은 원리를 활용하는 연구가 있습니다.

예시

8비트 장난감 예로 원리를 보겠습니다. 입력을 L0 = 1010, R0 = 0011로 나누고, 라운드 함수가 F(R, K) = R ⊕ K, 라운드 키가 K1 = 0110이라고 하면

• L1 = R0 = 0011
• R1 = L0 ⊕ F(R0, K1) = 1010 ⊕ (0011 ⊕ 0110) = 1010 ⊕ 0101 = 1111

복호화는 R0 = L1 = 0011을 먼저 얻고, L0 = R1 ⊕ F(L1, K1) = 1111 ⊕ 0101 = 1010으로 원래 값을 되찾습니다. F가 단순한 XOR이라 실제로는 전혀 안전하지 않지만, 어떤 F를 써도 되돌릴 수 있다는 구조의 성질을 확인할 수 있습니다. 실제 암호에서는 F 안에 S-박스(비선형 치환)와 순열을 넣어 혼돈과 확산을 만듭니다.

변형 구조

• 비균형 파이스텔: 블록을 같은 크기가 아닌 두 부분으로 나눕니다.
• 일반화 파이스텔: 블록을 셋 이상으로 나누고 여러 가지를 돌려 가며 갱신합니다.
• Lai–Massey 구조: IDEA 등에서 쓰인 다른 방식의 가역 구조입니다.

파이스텔 구조는 형식 보존 암호화(FPE) 표준인 NIST SP 800-38G의 FF1 등에도 쓰여, 카드 번호처럼 형식을 유지해야 하는 데이터를 암호화하는 데 활용됩니다.

쉽게 말하면

반쪽을 섞는 재료로 삼아 다른 반쪽을 섞고, 자리를 바꿔 다시 섞기를 반복하는 방식입니다. 순서만 거꾸로 하면 언제든 원래대로 풀 수 있습니다.