몽고메리 곱셈

모듈러 산술 계산에서 **몽고메리 모듈러 곱셈**(Montgomery modular multiplication)은 일반적으로 **몽고메리 곱셈**이라고 불리며, 빠른 모듈러 곱셈을 수행하는 방법이다. 이 방법은 1985년 미국의 수학자 피터 L. 몽고메리에 의해 소개되었다.url=https://www.ams.org/journals/mcom/1985-44-170/S0025-5718-1985-0777282-X/S0025-5718-1985-0777282-X.pdfMartin Kochanski, "Montgomery Multiplication" date=2010-03-27 a colloquial explanation. 몽고메리 모듈러 곱셈은 몽고메리 형식이라고 불리는 특별한 숫자 표현에 의존한다. 이 알고리즘은 a와 b의 몽고메리 형식을 사용하여 ab mod N의 몽고메리 형식을 효율적으로 계산한다. 효율성은 값비싼 나눗셈 연산을 피하는 데서 비롯된다. 고전적인 모듈러 곱셈은 이중 폭의 곱 ab를 N으로 나누어 나머지만을 취함으로써 축소한다. 이 나눗셈은 몫 자릿수 추정과 보정을 필요로 한다. 이와 대조적으로, 몽고메리 형식은 N과 서로소인 상수 R > N에 의존하며, 몽고메리 곱셈에 필요한 유일한 나눗셈은 R로 나누는 것이다. 상수 R은 R로 나누는 것이 쉽게 되도록 선택할 수 있어, 알고리즘의 속도를 크게 향상시킨다. 이진 컴퓨터에서 R은 항상 2의 거듭제곱이며, 2의 거듭제곱으로 나누는 것은 비트 시프팅으로 구현할 수 있다. a와 b를 몽고메리 형식으로 변환하고, 그 결과를 몽고메리 형식에서 벗어나게 변환하는 과정이 필요하므로, 몽고메리 곱셈으로 단일 곱셈을 계산하는 것은 기존의 배럿 축소 알고리즘보다 느리다. 그러나 모듈러 지수화와 같이 많은 곱셈을 연속해서 수행할 때는 중간 결과를 몽고메리 형식으로 유지할 수 있다. 그러면 초기 및 최종 변환이 전체 계산에서 무시할 수 있는 부분이 된다. RSA 및 디피-헬먼 키 교환과 같은 많은 중요한 암호 시스템은 큰 홀수에 대한 모듈러 산술 연산을 기반으로 하며, 이러한 암호 시스템의 경우 R을 2의 거듭제곱으로 하는 몽고메리 곱셈을 사용하는 계산이 사용 가능한 대안보다 빠르다.Alfred J. Menezes, Paul C. van Oorschot, and Scott A. Vanstone. Handbook of Applied Cryptography. CRC Press, 1996. , chapter 14.
# 모듈러 산술
N을 양의 정수 모듈러라고 하자. 몫환 **Z**/N**Z**는 N을 법으로 하는 잉여류들로 구성된다. 즉, 그 원소들은 다음과 같은 형태의 집합이다. :\\{ a + kN \colon k \in \mathbf{Z} \\}, 여기서 a는 정수 범위에 걸쳐 있다. 각 잉여류는 집합 내의 임의의 두 정수의 차이가 N으로 나누어지는 정수들의 집합이다(그리고 잉여류는 그 속성에 대해 최대적이다. 정수들은 나눗셈 조건을 위반하지 않는 한 잉여류에서 제외되지 않는다). a에 해당하는 잉여류는 a로 표기한다. 잉여류의 같음을 합동이라고 하며 다음과 같이 표기한다. :\bar a \equiv \bar b \pmod{N}. 잉여류는 무한히 많은 원소를 가지므로, 전체 잉여류를 컴퓨터에 저장하는 것은 불가능하다. 대신 잉여류는 대표원(representative)으로 저장된다. 일반적으로 이 대표원들은 0 ≤ a ≤ N − 1인 정수 a이다. a가 정수이면, a의 대표원은 a mod N으로 표기한다. 합동을 쓸 때, 정수를 그 정수가 나타내는 잉여류와 동일시하는 것이 일반적이다. 이 관례에 따라 위 등식은 a ≡ b mod N으로 표기된다. 잉여류에 대한 산술은 먼저 그 대표원에 대한 정수 산술을 수행함으로써 이루어진다. 정수 연산의 결과는 잉여류를 결정하며, 모듈러 연산의 결과는 잉여류의 대표원을 계산함으로써 결정된다. 예를 들어, 1=N = 17일 때, 잉여류 7과 15의 합은 정수 합 1=7 + 15 = 22를 구한 다음, 22와 17의 차이가 17의 배수인 0과 16 사이의 정수인 22 mod 17을 결정함으로써 계산된다. 이 경우, 그 정수는 5이므로, 5 mod 17이다.
# 몽고메리 형식
a와 b가 [0, N − 1] 범위의 정수라면, 그 합은 [0, 2N − 2] 범위에 있고, 그 차이는 [−N + 1, N − 1] 범위에 있으므로, [0, N − 1]의 대표원을 결정하는 데는 N의 뺄셈 또는 덧셈(각각)이 최대 한 번 필요하다. 그러나 곱셈 ab는 [0, N2 − 2N + 1] 범위에 있다. 중간 정수 곱셈 ab를 저장하는 데는 a 또는 b보다 두 배 많은 비트가 필요하며, [0, N − 1]에서 대표원을 효율적으로 결정하려면 나눗셈이 필요하다. 수학적으로, 0과 N − 1 사이에서 ab와 합동인 정수는 유클리드 나눗셈 정리를 적용하여 표현할 수 있다. :ab = qN + r, 여기서 q는 몫 \lfloor ab / N \rfloor이고, 나머지 r은 [0, N − 1] 구간에 있다. 나머지 r은 ab mod N이다. r을 결정하는 것은 q를 계산한 다음, ab에서 qN을 빼는 방식으로 할 수 있다. 예를 들어, 다시 N=17로, 곱셈 15는 7 \cdot 15 = 105를 계산하고, \lfloor 105 / 17 \rfloor = 6을 나눈 다음, 105 - 6 \cdot 17 = 105 - 102 = 3을 뺄셈하여 결정된다. q의 계산은 나눗셈을 필요로 하므로, 대부분의 컴퓨터 하드웨어에서 바람직하지 않게 비싸다. 몽고메리 형식은 값비싼 나눗셈 없이 모듈러 곱셈을 계산할 수 있는 링의 원소를 표현하는 다른 방법이다. 나눗셈은 여전히 필요하지만, 다른 제수 R에 대해 수행할 수 있다. 이 제수는 2의 거듭제곱으로 선택할 수 있으며, 이 경우 나눗셈은 시프팅으로 대체될 수 있고, 또는 전체 기계어 워드 수로 선택할 수 있으며, 이 경우 나눗셈은 워드를 생략함으로써 대체될 수 있다. 이러한 나눗셈은 빠르므로, 몽고메리 형식을 사용하여 모듈러 곱셈을 계산하는 비용의 대부분은 일반 곱셈을 계산하는 비용이다. 보조 모듈러스 R은 1=gcd(R, N) = 1인 양의 정수여야 한다. 계산상의 목적으로 R에 대한 나눗셈과 축소가 저렴해야 하며, R > N이 아니면 모듈러스는 모듈러 곱셈에 유용하지 않다. R에 대한 잉여류 a의 몽고메리 형식은 aR mod N이다. 즉, 잉여류 aR의 대표원이다. 예를 들어, 1=N = 17이고 1=R = 100이라고 가정하자. 3, 5, 7, 15의 몽고메리 형식은 각각 1=300 mod 17 = 11, 1=500 mod 17 = 7, 1=700 mod 17 = 3, 1=1500 mod 17 = 4이다. 몽고메리 형식에서의 덧셈과 뺄셈은 분배 법칙 때문에 일반적인 모듈러 덧셈 및 뺄셈과 동일하다. :aR + bR = (a + b)R, :aR - bR = (a - b)R. 몽고메리 형식으로 연산을 수행하는 것이 몫환 **Z**/N**Z**에서 연산을 수행하는 것에 비해 정보를 잃지 않는다는 점에 유의해야 한다. 이는 1=gcd(R, N) = 1이므로, R을 곱하는 것이 덧셈군 **Z**/N**Z**에 대한 동형 사상이기 때문이다. 예를 들어, 1=(7 + 15) mod 17 = 5는 몽고메리 형식으로 1=(3 + 4) mod 17 = 7이 된다. 그러나 몽고메리 형식에서의 곱셈은 겉보기에는 더 복잡하다. aR과 bR의 일반적인 곱셈은 R이라는 추가 인자가 있기 때문에 a와 b의 곱을 나타내지 않는다. :(aR \bmod N)(bR \bmod N) \bmod N = (abR)R \bmod N. 몽고메리 형식으로 곱셈을 계산하려면 R의 추가 인자를 제거해야 한다. R로 나누는 것은 저렴하지만, 중간 곱셈 (aR mod N)(bR mod N)은 모듈러 연산이 이 속성을 파괴했기 때문에 R로 나누어지지 않는다. 따라서 예를 들어, R = 100일 때 7과 15를 17을 법으로 하는 몽고메리 형식으로 곱하면 3과 4의 곱인 12가 된다. 12는 100으로 나누어지지 않으므로, R의 추가 인자를 제거하기 위한 추가적인 노력이 필요하다. R의 추가 인자를 제거하는 것은 RR′ ≡ 1 (mod N)을 만족하는 정수 R′을 곱함으로써 수행할 수 있다. 즉, R을 N을 법으로 하는 모듈러 역원인 R′의 잉여류를 곱하는 것이다. 그러면 N을 법으로 작업할 때, :(aR \bmod N)(bR \bmod N)R' \equiv (aR)(bR)R^{-1} \equiv (ab)R \pmod{N}. 정수 R′은 R과 N이 서로소라는 가정 때문에 존재한다. 이는 확장 유클리드 호제법을 사용하여 구성할 수 있다. 확장 유클리드 호제법은 베주 항등식을 만족하는 정수 R′와 N′을 효율적으로 결정한다. 0 N일 때, 다른 대부분의 산술 연산은 REDC로 표현될 수 있다. 이 가정은 N을 법으로 하는 두 표현의 곱이 RN보다 작다는 것을 의미하며, 이는 REDC가 정확한 출력을 생성하는 데 필요한 정확한 가정이다. 특히, aR mod N과 bR mod N의 곱은 REDC((aR mod N)(bR mod N))이다. 곱셈과 REDC를 결합한 연산을 종종 몽고메리 곱셈이라고 부른다. 몽고메리 형식으로의 변환은 REDC((a mod N)(R2 mod N))을 계산하여 수행된다. 몽고메리 형식에서 벗어나는 변환은 REDC(aR mod N)을 계산하여 수행된다. aR mod N의 모듈러 역수는 REDC((aR mod N)−1(R3 mod N))이다. 모듈러 지수승은 제곱을 이용한 지수승을 사용하여 수행될 수 있으며, 초기 곱을 몽고메리 형식의 1, 즉 R mod N으로 초기화하고, 곱셈 및 제곱 단계를 몽고메리 곱셈으로 대체한다. 이러한 연산을 수행하려면 적어도 N′과 R2 mod N을 알아야 한다. R이 작은 양의 정수 b의 거듭제곱일 때, N′은 헨젤의 보조정리로 계산될 수 있다. N의 b를 법으로 하는 역수는 순진한 알고리즘(예: 1=b = 2이면 역수는 1)으로 계산되고, 헨젤의 보조정리가 반복적으로 사용되어 b의 더 높은 거듭제곱을 법으로 하는 역수를 찾으며, R을 법으로 하는 역수를 알게 되면 멈춘다. N′은 이 역수의 부정이다. 상수 R mod N과 R3 mod N은 REDC(R2 mod N)과 REDC((R2 mod N)(R2 mod N))으로 생성될 수 있다. 기본적인 연산은 곱의 REDC를 계산하는 것이다. 독립적인 REDC가 필요할 때, 1 mod N과의 곱의 REDC로 계산될 수 있다. 직접적인 N을 법으로 하는 환원이 필요한 유일한 곳은 R2 mod N의 사전 계산이다.
# 다중 정밀도 정수에서의 몽고메리 산술
대부분의 암호화 응용 프로그램은 수백 또는 심지어 수천 비트 길이의 숫자를 필요로 한다. 이러한 숫자는 단일 머신 워드에 저장하기에는 너무 크다. 일반적으로 하드웨어는 특정 베이스 B를 법으로 하는 곱셈을 수행하므로, 더 큰 곱셈을 수행하려면 여러 작은 곱셈을 결합해야 한다. 베이스 B는 일반적으로 마이크로 전자 응용 프로그램의 경우 2, 8비트 펌웨어의 경우 28 또는 소프트웨어 응용 프로그램의 경우 232 또는 264이다. REDC 알고리즘은 R을 법으로 하는 곱셈을 필요로 하며, 일반적으로 R > N이므로 REDC를 사용하여 곱셈을 계산할 수 있다. 그러나 R이 B의 거듭제곱일 때, 머신 워드 크기의 정수의 곱셈만 필요한 REDC의 변형이 있다. 양의 다중 정밀도 정수가 리틀 엔디언으로 저장된다고 가정하자. 즉, x는 배열 x[0], ..., x[ℓ - 1]로 저장되며, 모든 i에 대해 0 ≤ x[i] < B이고 1=x = ∑ x[i] Bi이다. 알고리즘은 다중 정밀도 정수 T로 시작하여 한 워드씩 환원한다. 먼저 T가 B로 나눌 수 있도록 N의 적절한 배수가 추가된다. 그런 다음 T가 B2로 나눌 수 있도록 N의 배수가 추가되는 식이다. 결국 T는 R로 나눌 수 있게 되고, R로 나눈 후 알고리즘은 t 계산 후의 REDC와 동일한 위치에 있게 된다. **함수** MultiPrecisionREDC **은** **입력:** 1=gcd(B, N) = 1인 정수 N, p 워드 배열로 저장됨, 정수 1=R = Br, --따라서 r = logB R NN′ ≡ −1 (mod B)인 [0, B − 1] 범위의 정수 N′, 0 ≤ T < RN 범위의 정수 T, r + p 워드 배열로 저장됨. **출력:** TR−1 ≡ S (mod N)인 [0, N − 1] 범위의 정수 S, p 워드 배열로 저장됨. 1=T[r + p] = 0으로 설정 (추가 자리올림 워드) **for** 0 ≤ i < r **do** \--loop1- T를 Bi+1로 나눌 수 있게 만듦 c <- 0 m <- T[i] ⋅ N′ mod B **for** 0 ≤ j < p **do** \--loop2- m ⋅ N[j]와 이전 자리올림을 더하고 새로운 자리올림을 찾음 x <- T[i + j] + m ⋅ N[j] + c T[i + j] <- x mod B c <- ⌊x / B⌋ **end for** **for** p ≤ j ≤ r + p − i **do** \--loop3- 자리올림 계속 x <- T[i + j] + c T[i + j] <- x mod B c <- ⌊x / B⌋ **end for** **end for** **for** 0 ≤ i ≤ p **do** S[i] <- T[i + r] **end for** **if** S ≥ N **then** **return** S − N **else** **return** S **end if** **함수 끝** 최종 비교 및 뺄셈은 표준 알고리즘으로 수행된다. 위 알고리즘은 REDC가 올바른 것과 본질적으로 동일한 이유로 올바르다. i 루프를 돌 때마다 m은 T[i] + mN[0]이 B로 나눌 수 있도록 선택된다. 그런 다음 mNBi가 T에 더해진다. 이 양은 N을 법으로 0이므로, 이를 더해도 T mod N의 값에 영향을 미치지 않는다. mi가 루프의 i번째 반복에서 계산된 m의 값을 나타낸다면, 알고리즘은 S를 T + (∑ mi Bi)N으로 설정한다. MultiPrecisionREDC와 REDC는 동일한 출력을 생성하므로, 이 합은 REDC 알고리즘이 만들 m의 선택과 동일하다. T의 마지막 워드인 T[r + p] (그리고 결과적으로 S[p])는 오직 자리올림을 저장하는 데 사용되는데, 이는 초기 환원 결과가 0 ≤ S < 2N 범위의 결과에 묶여 있기 때문이다. 따라서 R ≥ 2N임이 미리 알려져 있다면 이 추가 자리올림 워드를 완전히 피할 수 있다. 일반적인 이진 구현에서, 이는 N의 비트 수가 R의 비트 수보다 작다면 이 자리올림 워드를 피할 수 있다는 것과 동등하다. 그렇지 않으면 자리올림은 0 또는 1이 된다. 프로세서에 따라 이 워드를 전체 크기의 워드 대신 자리올림 플래그로 저장하는 것이 가능할 수도 있다. 다중 정밀도 곱셈과 REDC를 단일 알고리즘으로 결합하는 것이 가능하다. 이 결합된 알고리즘은 일반적으로 몽고메리 곱셈이라고 불린다. Koç, Acar 및 Kaliski는 여러 가지 다른 구현을 설명한다.url=https://www.microsoft.com/en-us/research/wp-content/uploads/1996/01/j37acmon.pdf 이 알고리즘은 p + 2 워드 (더하기 자리올림 비트)만큼 적은 저장 공간을 사용할 수 있다. 예를 들어, 1=B = 10, 1=N = 997, 1=R = 1000이라고 하자. 1=a = 314 및 1=b = 271이라고 가정하자. a와 b의 몽고메리 표현은 1=314000 mod 997 = 942와 1=271000 mod 997 = 813이다. 1=942 ⋅ 813 = 765846을 계산한다. MultiPrecisionREDC의 초기 입력 T는 [6, 4, 8, 5, 6, 7]이 된다. 숫자 N은 [7, 9, 9]로 표현된다. 확장 유클리드 호제법은 1=−299 ⋅ 10 + 3 ⋅ 997 = 1이므로, N′은 7이 된다고 말한다. i <- 0 m <- 1=6 ⋅ 7 mod 10 = 2 j T c \- ------- - 0 0485670 2 (첫 번째 루프의 첫 번째 반복 후) 1 0485670 2 2 0485670 2 3 0487670 0 (두 번째 루프의 첫 번째 반복 후) 4 0487670 0 5 0487670 0 6 0487670 0 i <- 1 m <- 1=4 ⋅ 7 mod 10 = 8 j T c \- ------- - 0 0087670 6 (첫 번째 루프의 첫 번째 반복 후) 1 0067670 8 2 0067670 8 3 0067470 1 (두 번째 루프의 첫 번째 반복 후) 4 0067480 0 5 0067480 0 i <- 2 m <- 1=6 ⋅ 7 mod 10 = 2 j T c \- ------- - 0 0007480 2 (첫 번째 루프의 첫 번째 반복 후) 1 0007480 2 2 0007480 2 3 0007400 1 (두 번째 루프의 첫 번째 반복 후) 4 0007401 0 따라서, 최종 비교 및 뺄셈 전에 1=S = 1047이다. 최종 뺄셈은 숫자 50을 산출한다. 1=314 ⋅ 271 mod 997 = 349의 몽고메리 표현이 1=349000 mod 997 = 50이므로, 이는 예상된 결과이다. 2진수 기반에서 작업할 때, 각 단계에서 올바른 m을 결정하는 것은 특히 쉽다. 현재 작업 비트가 짝수이면 m은 0이고, 홀수이면 m은 1이다. 또한 MultiPrecisionREDC의 각 단계는 가장 낮은 비트만 알면 되므로, 몽고메리 곱셈은 자리올림수 저장 가산기와 쉽게 결합될 수 있다.
# 부채널 공격
몽고메리 환원은 몫 자리 추정치가 부정확할 때 기존 나눗셈에서 필요한 보정 단계를 피하므로, 타이밍 및 전력 부채널 공격의 주요 목표인 조건부 분기에서 거의 자유롭다. 실행되는 명령어 시퀀스는 입력 피연산자 값과 독립적이다. 유일한 예외는 계수의 최종 조건부 뺄셈이지만, 이를 저항할 수 있도록 (항상 계수 또는 0을 빼도록) 쉽게 수정할 수 있다.conference-url=https://www.nics.uma.es/pub/seciot10/ (발표 슬라이드.) 물론 곱셈 기본 요소로 구축된 지수승 알고리즘도 저항력이 있는지 확인해야 한다.Marc Joye and Sung-Ming Yen. "The Montgomery Powering Ladder". 2002.