푸리에 변환 (Fourier Transform)

푸리에 변환(Fourier transform)은 시간이나 공간에 따라 변하는 신호를 '어떤 주파수의 성분이 얼마나, 어떤 위상으로 들어 있는가'로 바꿔 표현하는 변환입니다. 연속 신호에는 F(ω) = ∫ f(t)e^−iωt dt를, 일정 간격으로 샘플링한 디지털 데이터에는 이산 푸리에 변환(DFT)을 씁니다. DFT는 주기적인 이산 시간 샘플과 주기적인 이산 주파수 샘플을 서로 대응시키며, 역변환으로 원래 신호를 완전히 되찾을 수 있습니다.

자세히 알아보기

푸리에 변환의 가장 중요한 성질은 합성곱 정리입니다. 시간 영역의 합성곱(필터링, 다항식 곱셈 등)이 주파수 영역에서는 단순한 곱셈이 됩니다. 그래서 복잡한 계산을 '변환 → 성분별 곱 → 역변환'으로 빠르게 처리할 수 있습니다. 또 파세발 정리에 의해 신호의 총 에너지는 두 영역에서 같습니다.

DFT의 각 출력은 모든 입력 값의 가중합이므로, 입력 하나가 바뀌면 모든 출력에 영향을 줍니다. 테리 리터는 이 '모든 입력을 모든 출력에 효율적으로 섞는' 구조, 특히 FFT의 나비 연산 패턴이 암호의 혼합(확산) 층 설계에 영감을 준다고 보았습니다. 다만 푸리에 변환은 선형 변환이므로 그 자체로 암호학적 안전성을 주지는 않으며, 비선형 요소와 함께 써야 합니다.

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

• 암호 분석 도구: 불 함수와 S-box 분석에 쓰는 월시-하다마드 변환은 GF(2)ⁿ 위의 푸리에 변환입니다. 선형 암호 분석에서 가장 잘 맞는 선형 근사를 찾는 것이 곧 '가장 큰 푸리에(월시) 계수'를 찾는 일입니다.
• 부채널 분석: 하드웨어 지갑의 전력·전자파 측정을 주파수 영역으로 바꿔 클럭 잡음을 거르거나, 시간 정렬이 어긋난 측정을 비교합니다.
• 다항식 연산: 유한체 버전인 수론 변환(NTT)은 영지식 증명 생성과 양자 내성 암호 ML-KEM·ML-DSA의 다항식 곱셈을 담당합니다.

쉽게 말하면

푸리에 변환은 섞여 있는 소리를 각 악기의 음으로 갈라내는 프리즘입니다. 다시 합치면 원래 소리가 그대로 돌아옵니다.

예시

1초에 3번 진동하는 사인파와 7번 진동하는 사인파를 더한 신호를 푸리에 변환하면, (양의 주파수 쪽에서) 주파수 3과 7에서만 뾰족한 값이 나타납니다.

역변환을 적용하면 두 사인파를 더한 원래 신호가 오차 없이 복원됩니다. 이산 푸리에 변환에서 n개의 입력은 n개의 주파수 성분으로 바뀌며, 정보가 늘거나 줄지 않습니다. 이 성질 덕분에 변환은 데이터를 다른 관점으로 보여 줄 뿐 숨기지는 못합니다.