정의
몽고메리 곱셈(Montgomery multiplication)은 모듈러 연산에서 큰 정수들의 곱을 효율적으로 계산하기 위한 알고리즘이다. 주어진 양의 정수 $a$, $b$와 모듈러 $N$에 대해, 몽고메리 곱셈은 추가적인 변환을 이용해 $(a \cdot b) \bmod N$ 를 직접적인 나눗셈 없이 계산한다. 이 방법은 특히 RSA, ECC 등 공개키 암호 시스템에서 사용되는 대규모 모듈러 연산의 성능을 크게 향상시킨다.
개요
-
배경
- 모듈러 곱셈은 $\frac{a \cdot b}{N}$ 의 나머지를 구하는 연산으로, 전통적인 구현에서는 큰 수의 나눗셈이 필요해 연산 비용이 높다.
- 1985년 Peter L. Montgomery가 제안한 이 기법은 나눗셈을 피하고 대신 비트 시프트와 덧셈·곱셈만으로 연산을 수행한다.
-
핵심 아이디어
- 미리 선택한 $R = 2^{k}$ ( $R > N$ ) 를 사용하여 정수를 R-표현(Montgomery representation)으로 변환한다: $\widetilde{a}=aR \bmod N$.
- 두 수 $\widetilde{a}, \widetilde{b}$ 의 몽고메리 곱을 정의한다:
$$ \operatorname{MontMul}(\widetilde{a},\widetilde{b}) = \frac{\widetilde{a},\widetilde{b}R^{-1} \bmod N}{} $$ - 결과는 다시 R-표현 형태이므로, 최종적으로 원래 표현으로 되돌리기 위해 몽고메리 역변환을 수행한다.
-
절차
- 전처리: $R$ 와 $R^{-1} \bmod N$, 그리고 $-N^{-1} \bmod R$ (보통 $N'$ 로 표기) 를 미리 계산한다.
- 곱셈 단계:
- $t = \widetilde{a},\widetilde{b}$
- $m = (t \bmod R) \cdot N' \bmod R$
- $u = (t + mN) / R$
- 만약 $u \ge N$이면 $u = u - N$
- 후처리: 필요 시 역변환을 수행해 일반 정수 형태로 변환한다.
어원/유래
- “몽고메리”는 알고리즘을 고안한 미국의 컴퓨터 과학자 Peter L. Montgomery(피터 L. 몽고메리)에서 유래한다. 그는 1985년 논문 “Modular Multiplication Without Trial Division” 에서 이 방법을 제시하였다. 한국어에서는 그의 성을 음역한 “몽고메리”를 그대로 사용한다.
특징
- 나눗셈 회피: 큰 수에 대한 직접적인 나눗셈이 없으며, 대신 비트 연산과 덧셈·곱셈만 사용한다.
- 하드웨어 친화성: 대부분의 현대 마이크로프로세서와 암호화 전용 하드웨어(예: GPU, FPGA, ASIC)에서 효율적으로 구현할 수 있다.
- 일관된 시간 복잡도: 입력값에 관계없이 수행 시간이 일정하므로, 사이드‑채널 공격(특히 타이밍 공격)에 대한 저항성이 있다.
- 전처리 비용: $R$, $R^{-1}$, $N'$ 등의 사전 계산이 필요하지만, 이는 한 번만 수행하면 여러 연산에 재사용 가능하다.
- 다양한 변형: Montgomery reduction 외에도 “Co‑Montgomery”, “Montgomery Ladder” 등 변형 알고리즘이 존재한다.
관련 항목
- 모듈러 연산
- RSA 암호
- 타원 곡선 암호(ECC)
- Montgomery reduction (몽고메리 환원)
- Co‑Montgomery multiplication
- 사이드‑채널 공격
- Peter L. Montgomery
※ 본 내용은 기존 학술 자료와 공개된 기술 문서를 기반으로 작성되었으며, 최신 구현에 따라 세부 절차가 다소 변형될 수 있다.