가중치 (Weight)

암호학에서 가중치(웨이트)는 비트열에서 1인 비트의 개수, 또는 부울 함수의 진리표 출력 중 1의 개수를 뜻합니다. 비트열의 경우 해밍 가중치(Hamming weight, 해밍 무게)라고도 하며, 물리학의 무게(중력)와는 관계가 없습니다.

자세히 알아보기

n개의 입력을 받는 부울 함수 f의 진리표에는 2ⁿ개의 출력이 있습니다. 이 가운데 1의 개수가 f의 가중치 wt(f)입니다. 가중치가 정확히 2ⁿ⁻¹, 즉 출력의 절반이 1이고 절반이 0인 함수를 균형(balanced) 함수라고 합니다. 균형이 깨진 함수는 출력이 0이나 1 한쪽으로 치우치므로, 공격자가 통계적으로 출력을 예측하는 데 활용할 수 있습니다. 그래서 스트림 암호의 결합 함수나 블록 암호의 S-박스를 설계할 때 균형성은 기본 요건으로 다뤄집니다.

비트열 x의 해밍 가중치는 x에 포함된 1의 개수이며, 두 비트열 사이의 해밍 거리는 d(x, y) = wt(x ⊕ y)로 계산됩니다. 오류 정정 부호에서는 0이 아닌 부호어의 최소 가중치가 부호의 최소 거리와 같아(선형 부호의 경우) 오류를 몇 개까지 정정할 수 있는지를 결정합니다. 또한 부울 함수의 비선형성은 함수와 모든 아핀 함수 사이의 해밍 거리 최솟값으로 정의되므로, 가중치는 비선형성·상관 면역성 같은 암호학적 지표를 계산하는 출발점이 됩니다.

컴퓨터에서는 해밍 가중치를 '팝카운트(popcount)'라고도 부르며, 많은 CPU가 이를 한 번에 계산하는 전용 명령어를 제공합니다. 가중치는 함수나 비트열의 '모양'을 숫자 하나로 요약할 뿐이므로, 가중치가 적절하다고 해서 암호학적으로 안전하다는 뜻은 아닙니다. 예컨대 균형 함수라도 선형 함수라면 쉽게 분석되므로, 설계자는 가중치와 함께 비선형성, 확산 특성, 대수적 차수 등을 종합적으로 검토합니다.

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

하드웨어 지갑과 스마트카드에 대한 부채널 공격에서는 "해밍 가중치 모델"이 자주 쓰입니다. 칩이 데이터를 처리할 때 소비 전력이 처리 중인 값의 1 비트 개수에 비례해 조금씩 달라지는 경향이 있어, 공격자는 전력 파형을 분석해 개인 키 일부를 추정하려고 시도합니다. 보안 칩은 이를 막기 위해 마스킹 등 대응 기법을 사용합니다. 또한 타원곡선 스칼라 곱셈에서는 스칼라를 가중치가 낮은 표현(예: NAF)으로 바꿔 연산 횟수를 줄이기도 합니다.

쉽게 말하면

스위치 여러 개가 한 줄로 놓여 있을 때 켜져 있는 스위치의 개수를 세는 것이 가중치입니다.

예시

• 비트열 0110의 해밍 가중치는 2입니다.
• 2입력 부울 함수 XOR의 진리표 출력은 0, 1, 1, 0이므로 가중치는 2 = 2²⁻¹이고, 균형 함수입니다.
• AND의 출력은 0, 0, 0, 1이므로 가중치는 1이며, 균형 함수가 아닙니다.