비선형성 (Nonlinearity)

비선형성(nonlinearity)은 함수나 관계가 선형적이지 않은 정도, 즉 출력이 입력에 정비례하거나 입력들의 단순한 합으로 표현되지 않는 성질입니다. 통계에서는 두 변수 관계가 직선으로 설명되지 않는 상황을 말하고, 암호학에서는 불 함수나 S-box가 모든 선형(아핀) 함수로부터 얼마나 떨어져 있는지를 비선형도라는 숫자로 측정합니다.

자세히 알아보기

함수 f가 선형이라는 것은 f(x + y) = f(x) + f(y), f(ax) = af(x)를 만족한다는 뜻입니다. 선형 시스템은 입력을 쪼개 따로 계산한 뒤 합치면 되므로 분석이 쉽고, 미지수가 있으면 연립 일차방정식으로 풀립니다.

암호에서 이것은 치명적입니다. 암호가 전부 선형이라면 평문·암호문 쌍 몇 개로 키에 대한 일차방정식을 세워 가우스 소거법으로 즉시 풀 수 있습니다. 그래서 모든 현대 대칭 암호는 반드시 비선형 부품을 갖고, 선형 부품(확산 층)과 번갈아 배치합니다. 불 함수의 비선형도는 진리표에서 가장 가까운 아핀 함수까지의 해밍 거리로 정의하며, 월시 변환으로 계산합니다. 비선형도가 높을수록 선형 암호 분석에 강합니다. 비선형도 외에도 대수적 차수, 차분 균일도 같은 보완 지표를 함께 봅니다.

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

• AES: 지갑 파일과 거래소 통신을 보호하는 AES에서 비선형 요소는 S-box 하나뿐이며, 그 비선형도는 112로 8비트 순열에서 알려진 최고 수준입니다.
• 해시 함수: SHA-256의 Ch·Maj 함수와 정수 덧셈, 이더리움 Keccak-256의 χ 단계가 비선형성을 공급합니다. 이것이 없으면 채굴용 해시나 주소 해시의 충돌을 방정식으로 풀 수 있게 됩니다.
• 영지식 증명 비용: zk-SNARK 회로에서 덧셈(선형)은 거의 공짜지만 곱셈(비선형)마다 제약이 하나씩 생깁니다. Poseidon 같은 해시가 비선형 연산 수를 최소화하도록 설계되는 이유입니다.
• 참고로 RSA·타원곡선 같은 공개 키 암호의 안전성은 '비선형성'보다는 인수분해·이산 로그 같은 수론적 문제의 어려움에서 나옵니다.

쉽게 말하면

선형은 '두 배 넣으면 두 배 나오는' 정직한 관계, 비선형은 그렇지 않은 관계입니다. 암호는 일부러 정직하지 않은 부품을 넣어 역산을 막습니다.

예시

f(x) = 3x는 선형이고 f(x) = x²은 비선형입니다(f(1 + 1) = 4 ≠ f(1) + f(1) = 2). 불 함수 x₁ ⊕ x₂는 선형, x₁x₂는 비선형입니다.