몽고메리 곱셈

모듈러 산술 계산에서 몽고메리 모듈러 곱셈(Montgomery modular multiplication)은 일반적으로 몽고메리 곱셈이라고 불리며, 빠른 모듈러 곱셈을 수행하는 방법이다. 이 방법은 1985년 미국의 수학자 피터 L. 몽고메리에 의해 소개되었다.Martin Kochanski, "Montgomery Multiplication"  a colloquial explanation.

몽고메리 모듈러 곱셈은 몽고메리 형식이라고 불리는 특별한 숫자 표현에 의존한다. 이 알고리즘은 와 의 몽고메리 형식을 사용하여 의 몽고메리 형식을 효율적으로 계산한다. 효율성은 값비싼 나눗셈 연산을 피하는 데서 비롯된다. 고전적인 모듈러 곱셈은 이중 폭의 곱 를 으로 나누어 나머지만을 취함으로써 축소한다. 이 나눗셈은 몫 자릿수 추정과 보정을 필요로 한다. 이와 대조적으로, 몽고메리 형식은 과 서로소인 상수 에 의존하며, 몽고메리 곱셈에 필요한 유일한 나눗셈은 로 나누는 것이다. 상수 은 로 나누는 것이 쉽게 되도록 선택할 수 있어, 알고리즘의 속도를 크게 향상시킨다. 이진 컴퓨터에서 은 항상 2의 거듭제곱이며, 2의 거듭제곱으로 나누는 것은 비트 시프팅으로 구현할 수 있다.

와 를 몽고메리 형식으로 변환하고, 그 결과를 몽고메리 형식에서 벗어나게 변환하는 과정이 필요하므로, 몽고메리 곱셈으로 단일 곱셈을 계산하는 것은 기존의 배럿 축소 알고리즘보다 느리다. 그러나 모듈러 지수화와 같이 많은 곱셈을 연속해서 수행할 때는 중간 결과를 몽고메리 형식으로 유지할 수 있다. 그러면 초기 및 최종 변환이 전체 계산에서 무시할 수 있는 부분이 된다. RSA 및 디피-헬먼 키 교환과 같은 많은 중요한 암호 시스템은 큰 홀수에 대한 모듈러 산술 연산을 기반으로 하며, 이러한 암호 시스템의 경우 을 2의 거듭제곱으로 하는 몽고메리 곱셈을 사용하는 계산이 사용 가능한 대안보다 빠르다.Alfred J. Menezes, Paul C. van Oorschot, and Scott A. Vanstone. Handbook of Applied Cryptography. CRC Press, 1996. , chapter 14.
 모듈러 산술 

을 양의 정수 모듈러라고 하자. 몫환 는 을 법으로 하는 잉여류들로 구성된다. 즉, 그 원소들은 다음과 같은 형태의 집합이다.

여기서 는 정수 범위에 걸쳐 있다. 각 잉여류는 집합 내의 임의의 두 정수의 차이가 으로 나누어지는 정수들의 집합이다(그리고 잉여류는 그 속성에 대해 최대적이다. 정수들은 나눗셈 조건을 위반하지 않는 한 잉여류에서 제외되지 않는다). 에 해당하는 잉여류는 로 표기한다. 잉여류의 같음을 합동이라고 하며 다음과 같이 표기한다.

잉여류는 무한히 많은 원소를 가지므로, 전체 잉여류를 컴퓨터에 저장하는 것은 불가능하다. 대신 잉여류는 대표원(representative)으로 저장된다. 일반적으로 이 대표원들은 인 정수 이다. 가 정수이면, 의 대표원은 으로 표기한다. 합동을 쓸 때, 정수를 그 정수가 나타내는 잉여류와 동일시하는 것이 일반적이다. 이 관례에 따라 위 등식은 으로 표기된다.

잉여류에 대한 산술은 먼저 그 대표원에 대한 정수 산술을 수행함으로써 이루어진다. 정수 연산의 결과는 잉여류를 결정하며, 모듈러 연산의 결과는 잉여류의 대표원을 계산함으로써 결정된다. 예를 들어, 일 때, 잉여류 과 의 합은 정수 합 를 구한 다음, 22와 17의 차이가 17의 배수인 0과 16 사이의 정수인 을 결정함으로써 계산된다. 이 경우, 그 정수는 5이므로, 이다.
 몽고메리 형식 

와 가  범위의 정수라면, 그 합은  범위에 있고, 그 차이는  범위에 있으므로, 의 대표원을 결정하는 데는 의 뺄셈 또는 덧셈(각각)이 최대 한 번 필요하다. 그러나 곱셈 는  범위에 있다. 중간 정수 곱셈 를 저장하는 데는  또는 보다 두 배 많은 비트가 필요하며, 에서 대표원을 효율적으로 결정하려면 나눗셈이 필요하다. 수학적으로, 0과  사이에서 와 합동인 정수는 유클리드 나눗셈 정리를 적용하여 표현할 수 있다.

여기서 는 몫 이고, 나머지 은  구간에 있다. 나머지 은 이다. 을 결정하는 것은 를 계산한 다음, 에서 을 빼는 방식으로 할 수 있다. 예를 들어, 다시 로, 곱셈 는 를 계산하고, 을 나눈 다음, 을 뺄셈하여 결정된다.

의 계산은 나눗셈을 필요로 하므로, 대부분의 컴퓨터 하드웨어에서 바람직하지 않게 비싸다. 몽고메리 형식은 값비싼 나눗셈 없이 모듈러 곱셈을 계산할 수 있는 링의 원소를 표현하는 다른 방법이다. 나눗셈은 여전히 필요하지만, 다른 제수 에 대해 수행할 수 있다. 이 제수는 2의 거듭제곱으로 선택할 수 있으며, 이 경우 나눗셈은 시프팅으로 대체될 수 있고, 또는 전체 기계어 워드 수로 선택할 수 있으며, 이 경우 나눗셈은 워드를 생략함으로써 대체될 수 있다. 이러한 나눗셈은 빠르므로, 몽고메리 형식을 사용하여 모듈러 곱셈을 계산하는 비용의 대부분은 일반 곱셈을 계산하는 비용이다.

보조 모듈러스 은 인 양의 정수여야 한다. 계산상의 목적으로 에 대한 나눗셈과 축소가 저렴해야 하며, 이 아니면 모듈러스는 모듈러 곱셈에 유용하지 않다. 에 대한 잉여류 의 몽고메리 형식은 이다. 즉, 잉여류 의 대표원이다. 예를 들어, 이고 이라고 가정하자. 3, 5, 7, 15의 몽고메리 형식은 각각 , , , 이다.

몽고메리 형식에서의 덧셈과 뺄셈은 분배 법칙 때문에 일반적인 모듈러 덧셈 및 뺄셈과 동일하다.

몽고메리 형식으로 연산을 수행하는 것이 몫환 에서 연산을 수행하는 것에 비해 정보를 잃지 않는다는 점에 유의해야 한다. 이는 이므로, 을 곱하는 것이 덧셈군 에 대한 동형 사상이기 때문이다. 예를 들어, 는 몽고메리 형식으로 이 된다.

그러나 몽고메리 형식에서의 곱셈은 겉보기에는 더 복잡하다. 과 의 일반적인 곱셈은 이라는 추가 인자가 있기 때문에 와 의 곱을 나타내지 않는다.

몽고메리 형식으로 곱셈을 계산하려면 의 추가 인자를 제거해야 한다. 로 나누는 것은 저렴하지만, 중간 곱셈 은 모듈러 연산이 이 속성을 파괴했기 때문에 로 나누어지지 않는다. 따라서 예를 들어, R = 100일 때 7과 15를 17을 법으로 하는 몽고메리 형식으로 곱하면 3과 4의 곱인 12가 된다. 12는 100으로 나누어지지 않으므로, 의 추가 인자를 제거하기 위한 추가적인 노력이 필요하다.

의 추가 인자를 제거하는 것은 을 만족하는 정수 을 곱함으로써 수행할 수 있다. 즉, 을 을 법으로 하는 모듈러 역원인 의 잉여류를 곱하는 것이다. 그러면 을 법으로 작업할 때,

정수 은 과 이 서로소라는 가정 때문에 존재한다. 이는 확장 유클리드 호제법을 사용하여 구성할 수 있다. 확장 유클리드 호제법은 베주 항등식을 만족하는 정수 와 을 효율적으로 결정한다.
, 이며, 다음을 만족한다.

이는 몽고메리 형식으로 곱셈을 수행하는 것이 가능함을 보여준다. 따라서 몽고메리 형식으로 숫자를 곱하는 간단한 알고리즘은 , , 그리고 을 정수로 곱하고 을 법으로 줄이는 것이다.

예를 들어, 7과 15를 17을 법으로 몽고메리 형식으로 곱하려면, 다시 으로, 위와 같이 3과 4의 곱을 계산하여 12를 얻는다. 확장 유클리드 호제법은 임을 의미하므로 이다. 12에 8을 곱하여 96을 얻고 17을 법으로 줄이면 11이 된다. 이는 예상대로 3의 몽고메리 형식이다.

 REDC 알고리즘 

위의 알고리즘은 정확하지만, 을 곱하고 으로 나누어야 하기 때문에 표준 표현법에서의 곱셈보다 느리다. REDC로도 알려진 몽고메리 환원은 에 의한 곱셈과 을 법으로 하는 환원을 단순한 방법보다 빠르게 동시에 계산하는 알고리즘이다. 수를 보다 작게 만드는 데 중점을 두는 기존의 모듈러 환원과 달리, 몽고메리 환원은 수를 로 더 잘 나누어지게 만드는 데 중점을 둔다. 이는 을 법으로 하는 나머지를 상쇄하도록 정교하게 선택된 의 작은 배수를 추가함으로써 이루어진다. 그 결과를 로 나누면 훨씬 작은 수가 나온다. 이 수는 너무 작아서 거의 을 법으로 하는 환원과 같으며, 을 법으로 하는 환원을 계산하는 데는 최종 조건부 뺄셈만 필요하다. 모든 계산은 이 아닌 에 대한 환원과 나눗셈만을 사용하여 수행되므로, 이 알고리즘은 나눗셈을 통한 직접적인 모듈러 환원보다 빠르게 실행된다.
function REDC is
     input: 정수 R과 N, 을 만족,
            정수 N′ ( 범위), 을 만족,
            정수 T ( 범위).
     output: 정수 S ( 범위), 을 만족

     m ← ((T mod R)N′) mod R
     t ← (T + mN) / R
     if t ≥ N then
         return 
     else
         return t
     end if
 end function

이 알고리즘이 올바르다는 것을 확인하려면, 먼저 이 이 로 나누어지도록 정확하게 선택된다는 것을 관찰해야 한다. 어떤 숫자가 로 나누어지는 것은 을 법으로 0과 합동일 필요충분조건이며, 우리는 다음을 얻는다.

따라서 는 정수이다. 둘째, 출력은  또는 인데, 둘 다 과 합동이므로, 출력이 과 합동임을 증명하려면 가 임을 증명하는 것으로 충분하다. 는 다음을 만족한다.

따라서 출력은 올바른 잉여류를 가진다. 셋째, 은 에 있으며, 따라서 은 0과  사이에 있다. 그러므로 는 보다 작으며, 정수이므로 는  범위에 있다. 따라서 를 원하는 범위로 줄이는 데는 최대 한 번의 뺄셈만 필요하므로, 알고리즘의 출력은 올바른 범위에 있다.

REDC를 사용하여 17을 법으로 하는 7과 15의 곱을 계산하려면, 먼저 몽고메리 형식으로 변환하고 정수로 곱하여 위와 같이 12를 얻는다. 그런 다음 , ,  및 를 사용하여 REDC를 적용한다. 첫 번째 단계에서 을 로 설정한다. 두 번째 단계에서는 를 로 설정한다. 은 예상대로 100의 배수인 1100임을 알 수 있다. 는 11로 설정되고, 11은 17보다 작으므로 최종 결과는 11이 되며, 이는 이전 섹션의 계산과 일치한다.

다른 예로, 의 곱을 으로 고려해보자. 확장 유클리드 호제법을 사용하여 을 계산하면, 은 이 된다. 7과 15의 몽고메리 형식은 각각 와 이다. 이들의 곱 28은 REDC의 입력 이며, 이므로 REDC의 가정은 만족된다. REDC를 실행하려면 을 으로 설정한다. 그런 다음 이므로 이다. 이므로, 이는 의 몽고메리 형식이다.

 중국인의 나머지 정리를 통한 해석 
출처:

몽고메리 환원에서 사용된 계수 과 몽고메리 기수 이 주어졌을 때, 잉여류환

을 고려하면, 중국인의 나머지 정리 (CRT)에서 비롯되는 동형 사상이다.

 중간 곱을 위한 CRT 재구성 
인 정수  (두 잉여류를 곱하여 가 발생하는 일반적인 경우)에 대해, 그 환원들을 취하면 다음과 같다.

CRT는 명시적인 재구성 공식을 제공한다.

우변이 이미 을 법으로 취해졌기 때문에, 이것은 다음과 같이도 쓸 수 있다.

두 합산항은 모두 반개방 구간 에 놓인다.

따라서, 정수 방정식(단순한 합동이 아님)으로 다음과 같이 쓸 수 있다.

또는

 T mod N을 포함하는 항 분리 
에 대해 풀기 위해 첫 번째 합산항을 분리하면 다음과 같다.

위의 모든 양은 정수이며, 좌변은 의 배수이다. 따라서 각 우변은 로 나눌 수 있다. 로 나누면 다음과 같다.

 결과 관계 
결과적으로,

이는 두 가지 핵심 사실을 제공한다.

 합동

 수치 경계

따라서,

을 다시 으로 법을 취하여 환원하면, 을 나타내는 음이 아닌 잉여류를 얻는다.

 몽고메리 형식의 산술 

을 법으로 하는 많은 흥미로운 연산들은 몽고메리 형식으로도 잘 표현될 수 있다. 덧셈, 뺄셈, 부정, 등호 비교, 몽고메리 형식이 아닌 정수와의 곱셈, 그리고 과의 최대공약수는 모두 표준 알고리즘으로 수행될 수 있다. 야코비 기호는 로 계산될 수 있으며, 이때 이 저장되어야 한다.

일 때, 다른 대부분의 산술 연산은 REDC로 표현될 수 있다. 이 가정은 을 법으로 하는 두 표현의 곱이 보다 작다는 것을 의미하며, 이는 REDC가 정확한 출력을 생성하는 데 필요한 정확한 가정이다. 특히, 과 의 곱은 이다. 곱셈과 REDC를 결합한 연산을 종종 몽고메리 곱셈이라고 부른다.

몽고메리 형식으로의 변환은 을 계산하여 수행된다. 몽고메리 형식에서 벗어나는 변환은 을 계산하여 수행된다. 의 모듈러 역수는 이다. 모듈러 지수승은 제곱을 이용한 지수승을 사용하여 수행될 수 있으며, 초기 곱을 몽고메리 형식의 1, 즉 으로 초기화하고, 곱셈 및 제곱 단계를 몽고메리 곱셈으로 대체한다.

이러한 연산을 수행하려면 적어도 과 을 알아야 한다. 이 작은 양의 정수 의 거듭제곱일 때, 은 헨젤의 보조정리로 계산될 수 있다. 의 를 법으로 하는 역수는 순진한 알고리즘(예: 이면 역수는 1)으로 계산되고, 헨젤의 보조정리가 반복적으로 사용되어 의 더 높은 거듭제곱을 법으로 하는 역수를 찾으며, 을 법으로 하는 역수를 알게 되면 멈춘다. 은 이 역수의 부정이다. 상수 과 은 과 으로 생성될 수 있다. 기본적인 연산은 곱의 REDC를 계산하는 것이다. 독립적인 REDC가 필요할 때, 과의 곱의 REDC로 계산될 수 있다. 직접적인 을 법으로 하는 환원이 필요한 유일한 곳은 의 사전 계산이다.

 다중 정밀도 정수에서의 몽고메리 산술 

대부분의 암호화 응용 프로그램은 수백 또는 심지어 수천 비트 길이의 숫자를 필요로 한다. 이러한 숫자는 단일 머신 워드에 저장하기에는 너무 크다. 일반적으로 하드웨어는 특정 베이스 를 법으로 하는 곱셈을 수행하므로, 더 큰 곱셈을 수행하려면 여러 작은 곱셈을 결합해야 한다. 베이스 는 일반적으로 마이크로 전자 응용 프로그램의 경우 2, 8비트 펌웨어의 경우 28 또는 소프트웨어 응용 프로그램의 경우 232 또는 264이다.

REDC 알고리즘은 을 법으로 하는 곱셈을 필요로 하며, 일반적으로 이므로 REDC를 사용하여 곱셈을 계산할 수 있다. 그러나 이 의 거듭제곱일 때, 머신 워드 크기의 정수의 곱셈만 필요한 REDC의 변형이 있다. 양의 다중 정밀도 정수가 리틀 엔디언으로 저장된다고 가정하자. 즉, 는 배열 로 저장되며, 모든 에 대해 이고 이다. 알고리즘은 다중 정밀도 정수 로 시작하여 한 워드씩 환원한다. 먼저 가 로 나눌 수 있도록 의 적절한 배수가 추가된다. 그런 다음 가 로 나눌 수 있도록 의 배수가 추가되는 식이다. 결국 는 로 나눌 수 있게 되고, 로 나눈 후 알고리즘은  계산 후의 REDC와 동일한 위치에 있게 된다.

 함수 MultiPrecisionREDC 은
     입력: 인 정수 N, p 워드 배열로 저장됨,
            정수 ,     --따라서 r = logB R
            인  범위의 정수 N′,
             범위의 정수 T,  워드 배열로 저장됨.

     출력: 인  범위의 정수 S, p 워드 배열로 저장됨.

     으로 설정 (추가 자리올림 워드)
     for  do
         --loop1- T를 로 나눌 수 있게 만듦

         c ← 0
         m ← 
         for  do
             --loop2- 와 이전 자리올림을 더하고 새로운 자리올림을 찾음

             x ← 
             T[i + j] ← 
             c ← 
         end for
         for  do
             --loop3- 자리올림 계속

             x ← 
             T[i + j] ← 
             c ← 
         end for
     end for

     for  do
         S[i] ← T[i + r]
     end for

     if  then
         return 
     else
         return 
     end if
 함수 끝
최종 비교 및 뺄셈은 표준 알고리즘으로 수행된다.

위 알고리즘은 REDC가 올바른 것과 본질적으로 동일한 이유로 올바르다.  루프를 돌 때마다 은 이 로 나눌 수 있도록 선택된다. 그런 다음 가 에 더해진다. 이 양은 을 법으로 0이므로, 이를 더해도 의 값에 영향을 미치지 않는다. 가 루프의 번째 반복에서 계산된 의 값을 나타낸다면, 알고리즘은 를 으로 설정한다. MultiPrecisionREDC와 REDC는 동일한 출력을 생성하므로, 이 합은 REDC 알고리즘이 만들 의 선택과 동일하다.

의 마지막 워드인  (그리고 결과적으로 )는 오직 자리올림을 저장하는 데 사용되는데, 이는 초기 환원 결과가  범위의 결과에 묶여 있기 때문이다. 따라서 임이 미리 알려져 있다면 이 추가 자리올림 워드를 완전히 피할 수 있다. 일반적인 이진 구현에서, 이는 의 비트 수가 의 비트 수보다 작다면 이 자리올림 워드를 피할 수 있다는 것과 동등하다. 그렇지 않으면 자리올림은 0 또는 1이 된다. 프로세서에 따라 이 워드를 전체 크기의 워드 대신 자리올림 플래그로 저장하는 것이 가능할 수도 있다.

다중 정밀도 곱셈과 REDC를 단일 알고리즘으로 결합하는 것이 가능하다. 이 결합된 알고리즘은 일반적으로 몽고메리 곱셈이라고 불린다. Koç, Acar 및 Kaliski는 여러 가지 다른 구현을 설명한다. 이 알고리즘은  워드 (더하기 자리올림 비트)만큼 적은 저장 공간을 사용할 수 있다.

예를 들어, , , 이라고 하자.  및 이라고 가정하자. 와 의 몽고메리 표현은 와 이다. 을 계산한다. MultiPrecisionREDC의 초기 입력 는 [6, 4, 8, 5, 6, 7]이 된다. 숫자 은 [7, 9, 9]로 표현된다. 확장 유클리드 호제법은 이므로, 은 7이 된다고 말한다.

 i ← 0
 m ← 

 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 ← 

 j T       c
 - ------- -
 0 0087670 6    (첫 번째 루프의 첫 번째 반복 후)
 1 0067670 8
 2 0067670 8
 3 0067470 1    (두 번째 루프의 첫 번째 반복 후)
 4 0067480 0
 5 0067480 0

 i ← 2
 m ← 

 j T       c
 - ------- -
 0 0007480 2    (첫 번째 루프의 첫 번째 반복 후)
 1 0007480 2
 2 0007480 2
 3 0007400 1    (두 번째 루프의 첫 번째 반복 후)
 4 0007401 0

따라서, 최종 비교 및 뺄셈 전에 이다. 최종 뺄셈은 숫자 50을 산출한다. 의 몽고메리 표현이 이므로, 이는 예상된 결과이다.

2진수 기반에서 작업할 때, 각 단계에서 올바른 을 결정하는 것은 특히 쉽다. 현재 작업 비트가 짝수이면 은 0이고, 홀수이면 은 1이다. 또한 MultiPrecisionREDC의 각 단계는 가장 낮은 비트만 알면 되므로, 몽고메리 곱셈은 자리올림수 저장 가산기와 쉽게 결합될 수 있다.

 부채널 공격 

몽고메리 환원은 몫 자리 추정치가 부정확할 때 기존 나눗셈에서 필요한 보정 단계를 피하므로, 타이밍 및 전력 부채널 공격의 주요 목표인 조건부 분기에서 거의 자유롭다. 실행되는 명령어 시퀀스는 입력 피연산자 값과 독립적이다. 유일한 예외는 계수의 최종 조건부 뺄셈이지만, 이를 저항할 수 있도록 (항상 계수 또는 0을 빼도록) 쉽게 수정할 수 있다.  (발표 슬라이드.) 물론 곱셈 기본 요소로 구축된 지수승 알고리즘도 저항력이 있는지 확인해야 한다.Marc Joye and Sung-Ming Yen. "The Montgomery Powering Ladder". 2002.

 같이 보기 
 배럿 환원

 각주 

 외부 링크 


분류:모듈러 산술
분류:암호 알고리즘
분류:컴퓨터 산술