Модульное умножение Монтгомери

В модульных арифметических вычислениях модульное умножение Монтгомери , чаще называемое умножением Монтгомери , представляет собой метод выполнения быстрого модульного умножения. Он был введен в 1985 году американским математиком Питером Л. Монтгомери .

Модульное умножение Монтгомери основано на специальном представлении чисел, называемом формой Монтгомери. Алгоритм использует формы Монтгомери a и b для эффективного вычисления формы Монтгомери ab mod N . Эффективность достигается за счет исключения дорогостоящих операций разделения. двойной ширины Классическое модульное умножение уменьшает произведение ab , используя деление на N и сохраняя только остаток. Это деление требует оценки и коррекции частных цифр. Форма Монтгомери, напротив, зависит от константы R > N , которая взаимно проста с N , и единственное деление, необходимое при умножении Монтгомери, — это деление R. на Константу R можно выбрать так, чтобы делить на R было легко, что значительно повышает скорость алгоритма. На практике R всегда является степенью двойки, поскольку деление на степени двойки можно реализовать с помощью сдвига битов .

Необходимость преобразования a и b в форму Монтгомери и их произведение из формы Монтгомери означает, что вычисление одного произведения путем умножения Монтгомери происходит медленнее, чем традиционные алгоритмы приведения или алгоритмы Барретта . Однако при выполнении множества умножений подряд, как при модульном возведении в степень , промежуточные результаты можно оставить в форме Монтгомери. Тогда начальные и конечные преобразования станут незначительной частью общего объема вычислений. Многие важные криптосистемы, такие как RSA и обмен ключами Диффи-Хеллмана , основаны на арифметических операциях по модулю большого нечетного числа, и для этих криптосистем вычисления с использованием умножения Монтгомери с R, равным степени двойки, выполняются быстрее, чем доступные альтернативы.

Модульная арифметика

Пусть N обозначает положительный целочисленный модуль. Факторкольцо N Z / N Z состоит из классов вычетов по модулю , то есть его элементами являются множества вида

$\{a+kN\colon k\in \mathbf {Z} \},$

где a варьируется в пределах целых чисел. Каждый класс остатков представляет собой набор целых чисел, в котором разница любых двух целых чисел в наборе делится на N (и класс остатков является максимальным по отношению к этому свойству; целые числа не исключаются из класса остатков, если только они не нарушают условие делимости). Класс вычетов, соответствующий a, обозначается a . Равенство классов вычетов называется конгруэнцией и обозначается

${\bar {a}}\equiv {\bar {b}}{\pmod {N}}.$

Хранение всего класса остатков на компьютере невозможно, поскольку класс остатков состоит из бесконечного числа элементов. Вместо этого классы остатков сохраняются как представители. Обычно этими представителями являются целые числа a, для которых 0 ≤ a ≤ N − 1 . Если a число, то представителем a записывается по модулю N. — целое При записи сравнений обычно целое число отождествляют с классом вычетов, которое оно представляет. приведенное выше равенство записывается a ≡ b mod N. С учетом этого соглашения

Арифметика над классами остатков выполняется путем сначала выполнения целочисленных арифметических операций над их представителями. Выход целочисленной операции определяет класс остатка, а результат модульной операции определяется путем вычисления представителя класса остатка. Например, если N = 17 , то сумма классов вычетов 7 и 15 вычисляется путем нахождения целочисленной суммы 7 + 15 = 22 , а затем определения 22 по модулю 17 , целого числа от 0 до 16, разница которого с 22 кратна из 17. В данном случае это целое число равно 5, поэтому 7 + 15 ≡ 5 mod 17 .

Форма Монтгомери

Если a и b являются целыми числами в диапазоне [0, N − 1] , то их сумма находится в диапазоне [0, 2 N − 2], а их разница находится в диапазоне [− N + 1, N − 1] , поэтому для определения представителя в [0, N − 1] требуется не более одного вычитания или добавления (соответственно) N . Однако произведение ab находится в диапазоне [0, N ² - 2 N + 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 , а затем вычитая qN из ab . Например, снова с $N=17$, произведение 7 ⋅ 15 определяется путем вычисления $7\cdot 15=105$, деление $\lfloor 105/17\rfloor =6$, и вычитание $105-6\cdot 17=105-102=3$.

Поскольку вычисление q требует деления, оно нежелательно дорого для большинства компьютерного оборудования. Форма Монтгомери — это другой способ выражения элементов кольца, в котором модульные произведения можно вычислять без дорогостоящих делений. деление по-прежнему необходимо, его можно выполнить относительно другого делителя R. Хотя Этот делитель может быть выбран степенью двойки, для которой деление можно заменить сдвигом, или целым числом машинных слов, для которых деление можно заменить опусканием слов. Эти разделения выполняются быстро, поэтому большая часть затрат на вычисление модульных произведений с использованием формы Монтгомери — это затраты на вычисление обычных произведений.

Вспомогательный модуль R должен быть положительным целым числом таким, что gcd( R , N ) = 1 . Для вычислительных целей также необходимо, чтобы деление и сокращение по модулю R были недорогими, а модуль бесполезен для модульного умножения, если R > N. только Форма Монтгомери класса вычетов a относительно R есть aR mod N , то есть она является представителем класса вычетов aR . Например, предположим, что N = 17 и что R = 100 . Формы Монтгомери 3, 5, 7 и 15: 300 по модулю 17 = 11 , 500 по модулю 17 = 7 , 700 по модулю 17 = 3 и 1500 по модулю 17 = 4 .

Сложение и вычитание в форме Монтгомери аналогичны обычному модульному сложению и вычитанию из-за распределительного закона:

$aR+bR=(a+b)R,$

$aR-bR=(a-b)R.$

что выполнение операции в форме Монтгомери не теряет информацию по сравнению с ее выполнением в факторкольце Z / N Z. Обратите внимание , Это следствие того факта, что, поскольку gcd( R , N ) = 1 , умножение на R является изоморфизмом на аддитивной группе Z / N Z . Например, (7 + 15) mod 17 = 5 , что в форме Монтгомери становится (3 + 4) mod 17 = 7 .

Однако умножение в форме Монтгомери, по-видимому, более сложное. Обычное произведение aR и bR не представляет собой произведение a и b, поскольку оно имеет дополнительный множитель R :

$(aR{\bmod {N}})(bR{\bmod {N}}){\bmod {N}}=(abR)R{\bmod {N}}.$

Вычисление произведений в форме Монтгомери требует удаления дополнительного R. множителя Хотя деление на R является дешевым, промежуточный продукт ( aR mod N ) ( bR mod N ) не делится на R , поскольку операция по модулю разрушила это свойство. Так, например, произведение форм Монтгомери 7 и 15 по модулю 17 с R = 100 является произведением 3 и 4, что равно 12. Поскольку 12 не делится на 100, требуются дополнительные усилия, чтобы удалить лишние коэффициент Р. ​

Удаление дополнительного множителя R можно выполнить путем умножения на целое число R ′ такое, что RR ′ ≡ 1 (mod N ) , то есть на R ′, класс вычетов которого является модулярным обратным к R mod N . Тогда, работая по модулю N ,

$(aR{\bmod {N}})(bR{\bmod {N}})R'\equiv (aR)(bR)R^{-1}\equiv (ab)R{\pmod {N}}.$

Целое число R ′ существует из-за предположения, что R и N взаимно просты. Его можно построить с помощью расширенного алгоритма Евклида . Расширенный алгоритм Евклида эффективно определяет целые числа R ′ и N ′, которые удовлетворяют тождеству Безу : 0 < R ′ < N , 0 < N ′ < R и:

$RR'-NN'=1.$

Это показывает, что можно выполнять умножение в форме Монтгомери. Поэтому простой алгоритм умножения чисел в форме Монтгомери состоит в том, чтобы умножить mod N , bR mod N и R ′ как целые числа и уменьшить их по модулю N. aR

Например, чтобы умножить 7 и 15 по модулю 17 в форме Монтгомери, снова с R = 100 , вычислите произведение 3 и 4, чтобы получить 12, как указано выше. Расширенный алгоритм Евклида подразумевает, что 8⋅100 − 47⋅17 = 1 , поэтому R ′ = 8 . Умножьте 12 на 8, чтобы получить 96, и уменьшите по модулю 17, чтобы получить 11. Как и ожидалось, это форма Монтгомери 3.

Алгоритм REDC

Хотя приведенный выше алгоритм верен, он медленнее, чем умножение в стандартном представлении, из-за необходимости умножать на R ′ и делить на N . Сокращение по Монтгомери , также известное как REDC, представляет собой алгоритм, который одновременно вычисляет произведение на R ′ и уменьшает по модулю N быстрее, чем наивный метод. В отличие от обычного модульного сокращения, которое фокусируется на том, чтобы сделать число меньше N , сокращение Монтгомери фокусируется на том, чтобы сделать число более делящимся на R . Это делается путем добавления небольшого числа, кратного N , которое тщательно выбирается для сокращения остатка по R. модулю Разделив результат на R , получим гораздо меньшее число. Это число настолько меньше, что оно почти равно сокращению по модулю N , а вычисление сокращения по модулю N требует только окончательного условного вычитания. Поскольку все вычисления выполняются с использованием только сокращения и деления относительно R , а не N , алгоритм работает быстрее, чем простое модульное сокращение путем деления.

 функция  REDC Вводится      :  целые числа  R  и  N  с  gcd(  R  ,  N  ) = 1  ,           Целое число  N  ′ из  [0,  R  − 1]  такое, что  NN  ′ ≡ −1 mod  R  ,           Целое число  T  в диапазоне  [0,  RN  − 1]  .     вывод:  целое число  S  в диапазоне  [0,  N  - 1]  такое, что  S  ≡  TR. −1  mod  N      m  ← ((  T  mod  R  )  N  ′) mod  R      t  ← (  T  +  mN  ) /  R,      если   t  ≥  N   , то          вернуть   t  -  N,      иначе          вернуть   t      end if  end function 

Чтобы убедиться в правильности этого алгоритма, сначала заметим, что выбрано именно так, что T + mN делится на R. m Число делится на R тогда и только тогда, когда оно конгруэнтно нулю по модулю R , и мы имеем:

$T+mN\equiv T+(((T{\bmod {R}})N'){\bmod {R}})N\equiv T+TN'N\equiv T-T\equiv 0{\pmod {R}}.$

Следовательно, t является целым числом. Во-вторых, выходной сигнал равен либо t, либо t − N , оба из которых конгруэнтны t mod N , поэтому для доказательства того, что выходные данные конгруэнтны TR ⁻¹ mod N достаточно доказать, что t есть TR ⁻¹ mod N , t удовлетворяет:

$t\equiv (T+mN)R^{-1}\equiv TR^{-1}+(mR^{-1})N\equiv TR^{-1}{\pmod {N}}.$

Таким образом, выходные данные имеют правильный класс остатка. В-третьих, m находится в [0, R − 1] и, следовательно, T + mN находится между 0 и ( RN − 1) + ( R − 1) N < 2 RN . Следовательно, t меньше 2 N , и поскольку оно целое, это помещает t в диапазон [0, 2 N − 1] . Следовательно, для уменьшения t до желаемого диапазона требуется не более одного вычитания, поэтому выходные данные алгоритма лежат в правильном диапазоне.

Чтобы использовать REDC для вычисления произведения 7 и 15 по модулю 17, сначала преобразуйте его в форму Монтгомери и умножьте как целые числа, чтобы получить 12, как указано выше. Затем примените REDC с R = 100 , N = 17 , N ′ = 47 и T = 12 . На первом этапе m устанавливается равным 12 ⋅ 47 mod 100 = 64 . На втором этапе t устанавливается равным (12 + 64 ⋅ 17)/100 . Обратите внимание, что 12 + 64 ⋅ 17 равно 1100, что кратно 100, как и ожидалось. t установлено равным 11, что меньше 17, поэтому окончательный результат равен 11, что согласуется с вычислениями предыдущего раздела.

В качестве другого примера рассмотрим произведение 7 ⋅ 15 по модулю 17, но с R = 10 . Используя расширенный алгоритм Евклида, вычислите −5 ⋅ 10 + 3 ⋅ 17 = 1 , так что N ′ будет равно −3 mod 10 = 7 . Формы Монтгомери 7 и 15 равны 70 по модулю 17 = 2 и 150 по модулю 17 = 14 соответственно. Их продукт 28 является входным сигналом T для REDC, и поскольку 28 < RN = 170 , предположения REDC удовлетворяются. Чтобы запустить REDC, установите m равным (28 mod 10) ⋅ 7 mod 10 = 196 mod 10 = 6 . Тогда 28 + 6 ⋅ 17 = 130 , поэтому t = 13 . Поскольку 30 по модулю 17 = 13 , это форма Монтгомери 3 = 7 ⋅ 15 по модулю 17 .

Арифметика в форме Монтгомери

Многие интересующие операции по модулю N могут быть одинаково хорошо выражены в форме Монтгомери. Сложение, вычитание, отрицание, сравнение на равенство, умножение на целое число, отличное от формы Монтгомери, а также определение наибольших общих делителей с N могут выполняться с помощью стандартных алгоритмов. Символ Якоби можно рассчитать как ${\big (}{\tfrac {a}{N}}{\big )}={\big (}{\tfrac {aR}{N}}{\big )}/{\big (}{\tfrac {R}{N}}{\big )}$ пока ${\big (}{\tfrac {R}{N}}{\big )}$ хранится.

Когда R > N , большинство других арифметических операций можно выразить через REDC. Это предположение подразумевает, что произведение двух представителей по модулю N меньше, чем RN , точная гипотеза, необходимая REDC для генерации правильного результата. В частности, произведением aR mod N и bR mod N является REDC(( aR mod N )( bR mod N )) . Комбинированную операцию умножения и REDC часто называют умножением Монтгомери .

Преобразование в форму Монтгомери осуществляется путем вычисления REDC(( a mod N )( R ² мод Н )) . Преобразование из формы Монтгомери выполняется путем вычисления REDC( aR mod N ) . Модульная инверсия aR mod N равна REDC(( aR mod N ) ⁻¹ ( Р ³ мод Н )) . Модульное возведение в степень можно выполнить с помощью возведения в степень возведением в квадрат путем инициализации исходного продукта представлением Монтгомери 1, то есть R mod N , и заменой шагов умножения и возведения в квадрат на умножения Монтгомери.

Для выполнения этих операций необходимо знать как минимум N ′ и R ² мод Н. ​Когда R является степенью небольшого положительного целого числа b , N ′ можно вычислить по лемме Гензеля : обратное значение N по модулю b вычисляется с помощью простого алгоритма (например, если b = 2 , то обратное значение равно 1), а число Гензеля лемма используется неоднократно для нахождения обратного по модулю все более и более высоких степеней b обратный по модулю R , останавливаясь, когда известен ; N ′ является отрицанием этого обратного. Константы R mod N и R ³ mod N может быть сгенерирован как REDC( R ² mod N ) и как REDC(( R ² против N )( R ² мод Н )) . Основная операция — вычисление REDC продукта. Когда необходим автономный REDC, его можно вычислить как REDC продукта с 1 N. mod Единственное место, где прямое сокращение по модулю N, необходимо - это предварительное вычисление R ² сторону Н. в

Монтгомери для целых чисел

Большинству криптографических приложений требуются числа длиной в сотни или даже тысячи бит. Такие числа слишком велики, чтобы их можно было хранить в одном машинном слове. Обычно аппаратное обеспечение выполняет умножение по некоторому основанию B , поэтому выполнение более крупных умножений требует объединения нескольких небольших умножений. База B обычно равна 2 для микроэлектронных приложений, 2 ⁸ для 8-битной прошивки, или 2 ³² или 2 ⁶⁴ для программных приложений.

Алгоритм REDC требует продуктов по модулю R и обычно R > N , чтобы REDC можно было использовать для вычисления продуктов. Однако, когда R является степенью B , существует вариант REDC, который требует произведения только целых чисел размером с машинное слово. Предположим, что положительные целые числа с множественной точностью хранятся с прямым порядком байтов , то есть x хранится как массив x [0], ..., x [ℓ - 1] такой, что 0 ≤ x [ i ] < B для всех i и Икс знак равно ∑ Икс [ я ] B ^я . Алгоритм начинается с целого числа множественной точности T и сокращает его по одному слову за раз. подходящее кратное N Сначала добавляется чтобы T делилось на B. , кратное N Затем добавляется , чтобы T делилось на B. ² , и так далее. В конце концов T делится на R , и после деления на R алгоритм находится в том же месте, где находился REDC после вычисления t .

функция  MultiPrecisionREDC  — это      входные данные:  целое число  N  с  gcd(  B  ,  N  ) = 1  , сохраненное в виде массива из  p  слов,           Целое число  R  =  B р , --таким образом,  r  =  log  B   R            Целое число  N  ′ из  [0,  B  − 1]  такое, что  NN  ′ ≡ −1 (mod  B  )  ,           Целое число  T  в диапазоне  0 ≤  T  <  RN  , сохраненное в виде массива из  r  +  p  слов.     Выходные данные:  целое число  S  из  [0,  N  − 1]  такое, что  TR −1  ≡  S  (mod  N  )  , хранящийся в виде массива из  p  слов.    Установите  T  [  r  +  p  ] = 0    (дополнительное слово переноса)      для   0 ≤  i  <  r   do          --loop1- Сделайте T делимым на  B я +1         в  ← 0         m  ←  T  [  i  ] ⋅  N  ′ mod  B          для   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  ⌋          конец для      конца для      0   ≤  i  ≤  p   do          S  [  i  ] ←  T  [  i  +  r  ]     end for,      если   S  ≥  N,   то          вернуть   S  −  N,      иначе          вернуть   S      end if  end function 

Окончательное сравнение и вычитание выполняется по стандартным алгоритмам.

Приведенный выше алгоритм верен по тем же причинам, что и REDC. Каждый раз в i цикле m выбирается так, чтобы T [ i ] + mN [0] на B. делилось Тогда мНБ ^я добавляется Т. к Поскольку эта величина равна нулю по модулю , ее добавление не влияет на значение T mod N. N Если m _i обозначает значение m, вычисленное на i -й итерации цикла, то алгоритм устанавливает S равным T + (∑ m _i B ^я ) Н . Поскольку MultiPrecisionREDC и REDC выдают одинаковый результат, эта сумма совпадает с выбором m, который сделал бы алгоритм REDC.

Последнее слово T , T [ r + p ] (и, следовательно, S [ p ] ), используется только для хранения переноса, поскольку исходный результат приведения привязан к результату в диапазоне 0 ≤ S < 2N . Отсюда следует, что этого дополнительного слова переноса можно полностью избежать, если заранее известно, что R ≥ 2N . В типичной двоичной реализации это эквивалентно утверждению, что этого слова переноса можно избежать, если количество битов N меньше количества битов R . В противном случае перенос будет либо нулем, либо единицей. В зависимости от процессора это слово можно сохранить как флаг переноса вместо полноразмерного слова.

Можно объединить умножение с высокой точностью и REDC в один алгоритм. Этот комбинированный алгоритм обычно называют умножением Монтгомери. Несколько различных реализаций описаны Кочем, Ачаром и Калиски. Алгоритм может использовать всего лишь p + 2 слова памяти (плюс бит переноса).

В качестве примера пусть B = 10 , N = 997 и R = 1000 . Предположим, что a = 314 и b = 271 . Представления Монтгомери a и b равны 314000 mod 997 = 942 и 271000 mod 997 = 813 . Вычислите 942 ⋅ 813 = 765846 . Начальным входным значением T для MultiPrecisionREDC будет [6, 4, 8, 5, 6, 7]. Число N будет представлено как [7, 9, 9]. Расширенный алгоритм Евклида говорит, что −299 ⋅ 10 + 3 ⋅ 997 = 1 , поэтому N ′ будет равно 7.

я ← 0м ←  6 ⋅ 7 по модулю 10 = 2 j Т c- ------- -0 0485670 2  (После первой итерации первого цикла) 1 0485670 22 0485670 23 0487670 0  (После первой итерации второго цикла) 4 0487670 05 0487670 06 0487670 0я ← 1м ←  4 ⋅ 7 по модулю 10 = 8 j T c- ------- -0 0087670 6  (После первой итерации первого цикла) 1 0067670 82 0067670 83 0067470 1  (После первой итерации второго цикла) 4 0067480 05 0067480 0я ← 2м ←  6 ⋅ 7 по модулю 10 = 2 j T c- ------- -0 0007480 2  (После первой итерации первого цикла) 1 0007480 22 0007480 23 0007400 1  (После первой итерации второго цикла) 4 0007401 0 

Следовательно, перед окончательным сравнением и вычитанием S = 1047 . Последнее вычитание дает число 50. Поскольку представление Монтгомери 314 ⋅ 271 по модулю 997 = 349 равно 349000 по модулю 997 = 50 , это ожидаемый результат.

При работе с базой 2 определить правильное m на каждом этапе особенно легко: если текущий рабочий бит четный, то m равен нулю, а если он нечетный, то m равен единице. Более того, поскольку каждый шаг MultiPrecisionREDC требует знания только младшего бита, умножение Монтгомери можно легко объединить с сумматором с сохранением переноса .

Атаки по побочным каналам

Поскольку сокращение Монтгомери позволяет избежать шагов коррекции, необходимых при обычном делении, когда оценки цифр частного являются неточными, оно в основном лишено условных ветвей, которые являются основными целями атак по времени и мощности побочного канала ; последовательность выполняемых инструкций не зависит от значений входных операндов. Единственным исключением является окончательное условное вычитание модуля, но его легко модифицировать (чтобы всегда что-то вычитать, либо модуль, либо ноль), чтобы сделать его устойчивым. Разумеется, необходимо обеспечить устойчивость алгоритма возведения в степень, построенного на основе примитива умножения.

См. также

• Сокращение Барретта

Внешние ссылки

• Генри С. Уоррен-младший (июль 2012 г.). «Теория и практика умножения Монтгомери». CiteSeerX   10.1.1.450.6124 .