모듈로 2 (Mod 2)

모듈로 2(Mod 2)는 GF(2)로 표기되는 체(field)로, 정수 집합 {0,1}과 덧셈(+)·곱셈(*) 연산으로 이루어지며 연산 결과는 2로 나눈 나머지입니다. GF(2)는 원소가 2개인 갈루아 체(Galois Field)이며, 이 체에서 덧셈은 비트 연산 XOR(배타적 논리합)과 같고 곱셈은 AND(논리곱)와 같습니다. 이 때문에 컴퓨터의 비트 연산과 암호, 오류 검출 코드의 기초가 됩니다.

GF(2)의 연산

• 덧셈 (+) = XOR: 두 수를 더한 뒤 2로 나눈 나머지를 취합니다.
  • 0 + 0 = 0
  • 0 + 1 = 1
  • 1 + 0 = 1
  • 1 + 1 = 0 (합 2를 2로 나누면 나머지가 0이기 때문입니다)
• 곱셈 (*) = AND: 이진 숫자만 다루므로 간단합니다.
  • 0 * 0 = 0, 0 * 1 = 0, 1 * 0 = 0
  • 1 * 1 = 1

모든 원소 a에 대해 a + a = 0이므로, GF(2)에서는 각 원소가 자기 자신의 덧셈 역원입니다. 즉 빼기와 더하기가 같은 연산입니다. 같은 값을 두 번 XOR하면 원래 값으로 돌아오는 성질이 여기서 나옵니다.

간단한 예: 전등 스위치

ON(1) 또는 OFF(0)일 수 있는 전등 스위치를 생각해 보십시오. ON일 때 스위치를 토글(1 추가)하면 (1 + 1) mod 2 = 0이므로 OFF로 전환됩니다. 다시 토글하면 (0 + 1) mod 2 = 1이므로 다시 ON으로 전환됩니다. 일반 이진수 덧셈과 달리 mod 2 덧셈에는 자리 올림(carry)이 없으며, 여러 비트를 한꺼번에 더할 때도 각 자리를 독립적으로 XOR합니다.

암호와 오류 검출에서의 역할

• 스트림 암호: 평문 비트와 키 스트림 비트를 mod 2로 더해(XOR) 암호문을 만듭니다. 받는 쪽은 같은 키 스트림을 다시 XOR해 평문을 복원합니다. 원타임 패드도 같은 원리입니다.
• 블록 암호와 선형 구조: 많은 블록 암호가 라운드 키를 데이터에 XOR하는 단계를 사용하며, 선형 피드백 시프트 레지스터(LFSR) 같은 구성 요소도 GF(2) 위의 연산으로 설명됩니다.
• CRC와 오류 수정 코드: CRC는 데이터를 GF(2) 계수의 다항식으로 보고 생성 다항식으로 나눈 나머지를 체크섬으로 씁니다. 이 나눗셈의 빼기는 XOR로 계산됩니다. 패리티 비트와 해밍 코드 등 오류 수정 코드도 mod 2 연산에 기반합니다.

Mod 2 사용의 장점

• 단순성: GF(2) 연산은 XOR와 AND 회로로 바로 구현되어 컴퓨터가 수행하기에 매우 간단하고 효율적입니다.
• 오류 감지 및 수정: 체크섬 알고리즘 및 오류 수정 코드에서 데이터 무결성을 확인하는 데 기본적입니다.
• 암호 응용: 특히 스트림 암호, 블록 암호 같은 대칭 키 암호에서 많은 암호 프리미티브의 토대가 됩니다.

Mod 2 사용의 단점

• 제한된 표현력: GF(2)만으로 복잡한 수학적 구조를 나타내는 것은 제한적일 수 있습니다.
• 선형성의 위험: XOR만으로 이루어진 구조는 선형이어서 그대로 암호에 쓰면 쉽게 분석됩니다. 실제 암호는 비선형 요소(S-박스 등)를 함께 사용합니다.