Computer >> 컴퓨터 >  >> 프로그래밍 >> 프로그래밍

블로우피시(Blowfish) 알고리즘의 작동 원리: 서브키 생성부터 데이터 암호화까지

블로우피시(Blowfish) 알고리즘이란?

블로우피시(Blowfish)는 대칭 키 블록 암호(symmetric block cipher) 알고리즘으로, 한 번에 64비트 크기의 데이터 블록을 암호화합니다. 이 알고리즘은 파이스텔 네트워크(Feistel Network) 구조를 따르며, 전체 작동 과정은 크게 두 단계로 나눌 수 있습니다.

  • 서브키 생성(Subkey Generation) – 최대 448비트 길이의 키를 변환하여 총 4168비트의 서브키를 만드는 과정입니다.
  • 데이터 암호화(Data Encryption) – 네트워크를 16회 반복 수행하며, 각 라운드마다 키 의존적 치환(key-dependent permutation)과 키·데이터 의존적 대체(key and data-dependent substitution)가 포함됩니다. 알고리즘 내 연산은 32비트 워드 단위의 XOR 또는 덧셈으로 구성되며, 추가 연산으로는 라운드당 네 번의 인덱스 배열 조회(indexed array lookup)만 사용됩니다.

아래에서 두 단계를 자세히 살펴보겠습니다.

1. 서브키 생성 (Sub-key Generation)

블로우피시 암호 알고리즘은 매우 많은 수의 서브키를 사용합니다. 이 서브키들은 실제 데이터 암호화나 복호화가 시작되기 이전에 미리 생성되어야 합니다.

서브키는 다음과 같이 구성됩니다.

  • P-array: 18개의 32비트 서브키
    P1, P2, ………, P18
  • S-boxes: 각각 256개 항목을 가진 32비트 S-박스 4개
    S1,0, S1,1, ………. S1,255
    S2,0, S2,1, ……….. S2,255
    S3,0, S3,1, ……….. S3,255
    S4,0, S4,1, ………... S4,255

서브키 생성 절차

  1. 초기화: 먼저 P-array와 네 개의 S-박스를 순서대로 고정된 문자열로 초기화합니다. 이 문자열에는 π(원주율)의 16진수 자릿수가 포함됩니다.
    예: P1=0x243f6a88, P2=0x85a308d3, P3=0x13198a2e, P4=0x3707344 등
  2. XOR 연산: P1을 키의 첫 32비트와 XOR하고, P2를 키의 다음 32비트와 XOR하는 방식으로 키의 모든 비트에 대해 반복합니다(최대 P14까지). 키 비트를 순환하면서 전체 P-array가 키 비트와 XOR될 때까지 과정을 반복합니다. 짧은 키의 경우 사실상 동일한 더 긴 키가 하나 존재합니다. 예를 들어 A가 64비트 키라면 AA, AAA 등도 같은 키로 취급됩니다.
  3. 암호화 수행: 1단계와 2단계에서 정의된 서브키를 사용하여, 블로우피시 알고리즘으로 모두 0인 문자열(all-zero string)을 암호화합니다.
  4. P1, P2 교체: 3단계의 64비트 출력값으로 P1과 P2를 대체합니다.
  5. 반복 암호화: 변경된 서브키를 사용하여 3단계의 출력값을 다시 암호화합니다.
  6. P3, P4 교체: 5단계의 출력값으로 P3와 P4를 대체합니다.
  7. 전체 배열 갱신: 위 과정을 계속 반복하여 P-array의 모든 항목을 먼저 교체한 후, 계속 변화하는 알고리즘의 출력값으로 네 개의 S-박스를 순서대로 교체합니다.

필요한 모든 서브키를 생성하려면 총 521회의 반복(iteration)이 필요합니다. 따라서 응용 프로그램은 이 유도 과정을 여러 번 실행하는 대신, 생성된 서브키를 저장해 두고 재사용하는 것이 효율적입니다.

2. 데이터 암호화 (Data Encryption)

블로우피시는 16라운드로 구성된 파이스텔 네트워크입니다.

입력은 64비트 데이터 요소 x입니다. 이를 두 개의 32비트 절반으로 분할합니다: xL, xR.

그런 다음 i = 1부터 16까지 다음 연산을 반복합니다.

  • xL = xL XOR Pi
  • xR = F(xL) XOR xR
  • xL과 xR을 교환(Swap)

16번째 라운드가 끝나면, 마지막 교환을 되돌리기 위해 xL과 xR을 다시 한 번 교환합니다.

그 후 다음 연산을 수행합니다.

  • xR = xR XOR P17
  • xL = xL XOR P18

마지막으로 xL과 xR을 다시 결합하면 최종 암호문(ciphertext)이 완성됩니다.

복호화 (Decryption)

복호화 과정은 암호화와 동일하지만, 한 가지 차이점이 있습니다. 바로 P1, P2, ……P18 서브키를 역순(reverse order)으로 사용한다는 점입니다. 이러한 대칭적 구조 덕분에 블로우피시는 암호화와 복호화에 동일한 함수를 활용할 수 있어 구현이 간결하고 효율적입니다.