В модульной арифметике модульное умножение Монтгомери , более часто называемое умножением Монтгомери , является методом выполнения быстрого модульного умножения. Он был введен в 1985 году американским математиком Питером Л. Монтгомери . [1] [2]
Модульное умножение Монтгомери опирается на специальное представление чисел, называемое формой Монтгомери. Алгоритм использует формы Монтгомери a и b для эффективного вычисления формы Монтгомери ab mod N. Эффективность достигается за счет избегания дорогостоящих операций деления. Классическое модульное умножение уменьшает произведение двойной ширины ab, используя деление на N и сохраняя только остаток. Это деление требует оценки и коррекции цифры частного. Форма Монтгомери, напротив, зависит от константы R > N , которая взаимно проста с N , и единственное деление, необходимое в умножении Монтгомери, — это деление на R. Константу R можно выбрать так, чтобы деление на R было простым, что значительно повышает скорость алгоритма. На практике R всегда является степенью двойки, поскольку деление на степени двойки можно реализовать путем сдвига битов .
Необходимость преобразования a и b в форму Монтгомери и их произведения из формы Монтгомери означает, что вычисление одного произведения с помощью умножения Монтгомери происходит медленнее, чем обычные алгоритмы или алгоритмы сокращения Барретта . Однако при выполнении многих умножений подряд, как при модульном возведении в степень , промежуточные результаты можно оставить в форме Монтгомери. Тогда начальное и конечное преобразования становятся незначительной частью общего вычисления. Многие важные криптосистемы, такие как RSA и обмен ключами Диффи–Хеллмана , основаны на арифметических операциях по модулю большого нечетного числа, и для этих криптосистем вычисления с использованием умножения Монтгомери с R, степенью двойки, выполняются быстрее, чем доступные альтернативы. [3]
Пусть N обозначает положительный целый модуль. Фактор-кольцо Z / N Z состоит из классов вычетов по модулю N , то есть его элементами являются множества вида
где a пробегает целые числа. Каждый класс остатков — это набор целых чисел, такой, что разность любых двух целых чисел в наборе делится на N (и класс остатков является максимальным относительно этого свойства; целые числа не исключаются из класса остатков, если только они не нарушают условие делимости). Класс остатков, соответствующий a, обозначается a . Равенство классов остатков называется конгруэнтностью и обозначается
Хранение всего класса остатков на компьютере невозможно, поскольку класс остатков имеет бесконечно много элементов. Вместо этого классы остатков хранятся как представители. Традиционно эти представители — целые числа a, для которых 0 ≤ a ≤ N − 1. Если a — целое число, то представитель a записывается как a mod N. При записи сравнений принято отождествлять целое число с классом остатков, который оно представляет. При таком соглашении приведенное выше равенство записывается как a ≡ b mod N.
Арифметика над классами остатков выполняется путем предварительного выполнения целочисленной арифметики над их представителями. Выход целочисленной операции определяет класс остатков, а выход модульной операции определяется путем вычисления представителя класса остатков. Например, если N = 17 , то сумма классов остатков 7 и 15 вычисляется путем нахождения целочисленной суммы 7 + 15 = 22 , а затем определения 22 mod 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 − 2 N + 1] . Для хранения промежуточного целочисленного произведения ab требуется вдвое больше бит, чем для a или b , а эффективное определение представителя в [0, N − 1] требует деления. Математически целое число между 0 и N − 1 , которое конгруэнтно ab, можно выразить, применив теорему Евклида о делении :
где q — частное , а r — остаток, находится в интервале [0, N − 1] . Остаток r равен ab mod N. Определение r можно выполнить, вычислив q , а затем вычтя qN из ab . Например, снова с , произведение 7 ⋅ 15 определяется вычислением , делением и вычитанием .
Поскольку вычисление 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 mod 17 = 11 , 500 mod 17 = 7 , 700 mod 17 = 3 и 1500 mod 17 = 4 .
Сложение и вычитание в форме Монтгомери аналогичны обычному модульному сложению и вычитанию из-за распределительного закона:
Обратите внимание, что выполнение операции в форме Монтгомери не теряет информацию по сравнению с выполнением ее в фактор-кольце 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 :
Вычисление продуктов в форме Монтгомери требует удаления дополнительного множителя R. Хотя деление на R является дешевым, промежуточный продукт ( aR mod N )( bR mod N ) не делится на R , поскольку операция по модулю разрушила это свойство. Так, например, произведение форм Монтгомери 7 и 15 по модулю 17, при R = 100 , является произведением 3 и 4, что равно 12. Поскольку 12 не делится на 100, требуются дополнительные усилия для удаления дополнительного множителя R.
Удалить лишний множитель R можно, умножив на целое число R ′ такое, что RR ′ ≡ 1 (mod N ) , то есть на R ′, класс вычетов которого является модульным обратным к R mod N . Затем, работая по модулю N ,
Целое число R ′ существует из-за предположения, что R и N взаимно просты. Его можно построить с помощью расширенного алгоритма Евклида . Расширенный алгоритм Евклида эффективно определяет целые числа R ′ и N ′ , которые удовлетворяют тождеству Безу : 0 < R ′ < N , 0 < N ′ < R , и:
Это показывает, что можно выполнить умножение в форме Монтгомери. Таким образом, простой алгоритм умножения чисел в форме Монтгомери заключается в том, чтобы умножить aR mod N , bR mod N и R ′ как целые числа и сократить по модулю N .
Например, чтобы умножить 7 и 15 по модулю 17 в форме Монтгомери, снова с R = 100 , вычислите произведение 3 и 4, чтобы получить 12, как указано выше. Расширенный алгоритм Евклида подразумевает, что 8⋅100 − 47⋅17 = 1 , поэтому R ′ = 8. Умножьте 12 на 8, чтобы получить 96, и уменьшите по модулю 17, чтобы получить 11. Это форма Монтгомери для 3, как и ожидалось.
Хотя приведенный выше алгоритм является правильным, он медленнее умножения в стандартном представлении из-за необходимости умножать на 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 конец, если функция конца
Чтобы убедиться в правильности этого алгоритма, сначала заметим, что m выбрано точно так, чтобы T + mN делилось на R. Число делится на R тогда и только тогда, когда оно сравнимо с нулем по модулю R , и мы имеем:
Следовательно, t — целое число. Во-вторых, выход — это либо t , либо t − N , оба из которых конгруэнтны t mod N , поэтому для доказательства того, что выход конгруэнтен TR −1 mod N , достаточно доказать, что t есть TR −1 mod N , t удовлетворяет:
Следовательно, вывод имеет правильный класс остатков. В-третьих, 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 mod 17 , но с R = 10. Используя расширенный алгоритм Евклида, вычислите −5 ⋅ 10 + 3 ⋅ 17 = 1 , поэтому N ′ будет равно −3 mod 10 = 7. Формы Монтгомери для 7 и 15 равны 70 mod 17 = 2 и 150 mod 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 mod 17 = 13 , это форма Монтгомери для 3 = 7 ⋅ 15 mod 17 .
Многие операции, представляющие интерес по модулю N, можно выразить одинаково хорошо в форме Монтгомери. Сложение, вычитание, отрицание, сравнение на равенство, умножение на целое число, не представленное в форме Монтгомери, и наибольшие общие делители с N можно выполнить с помощью стандартных алгоритмов. Символ Якоби можно вычислить, пока он хранится.
Когда R > N , большинство других арифметических операций можно выразить в терминах REDC. Это предположение подразумевает, что произведение двух представителей mod N меньше RN , точная гипотеза, необходимая для того, чтобы REDC генерировал правильный вывод. В частности, произведение aR mod N и bR mod N равно REDC(( aR mod N )( bR mod N )) . Объединенная операция умножения и REDC часто называется умножением Монтгомери .
Преобразование в форму Монтгомери выполняется путем вычисления REDC(( a mod N )( R 2 mod N )) . Преобразование из формы Монтгомери выполняется путем вычисления REDC( aR mod N ) . Модульное обратное значение aR mod N равно REDC(( aR mod N ) −1 ( R 3 mod N )) . Модульное возведение в степень можно выполнить с помощью возведения в степень путем возведения в квадрат, инициализируя начальное произведение представлением Монтгомери 1, то есть R mod N , и заменив шаги умножения и возведения в квадрат умножениями Монтгомери.
Для выполнения этих операций требуется знать как минимум N ′ и R 2 mod N . Когда R является степенью небольшого положительного целого числа b , N ′ можно вычислить с помощью леммы Гензеля : обратная величина N по модулю b вычисляется с помощью наивного алгоритма (например, если b = 2, то обратная величина равна 1), и лемма Гензеля используется многократно для нахождения обратной величины по модулю все более и более высоких степеней b , останавливаясь, когда обратная величина по модулю R становится известной; N ′ является отрицанием этой обратной величины. Константы R mod N и R 3 mod N могут быть сгенерированы как REDC( R 2 mod N ) и как REDC(( R 2 mod N )( R 2 mod N )) . Основная операция — вычислить REDC произведения. Когда требуется отдельная REDC, ее можно вычислить как REDC произведения с 1 mod N . Единственное место, где необходимо прямое сокращение по модулю N, — это предварительное вычисление R 2 mod N .
Большинству криптографических приложений требуются числа длиной в сотни или даже тысячи бит. Такие числа слишком велики, чтобы храниться в одном машинном слове. Обычно оборудование выполняет умножение mod некоторого основания B , поэтому выполнение больших умножений требует объединения нескольких небольших умножений. Основание B обычно равно 2 для микроэлектронных приложений, 2 8 для 8-битных прошивок [4] или 2 32 или 2 64 для программных приложений.
Алгоритм REDC требует произведений по модулю R , и обычно R > N , так что REDC можно использовать для вычисления произведений. Однако, когда R является степенью B , существует вариант REDC, который требует произведений только целых чисел размером с машинное слово. Предположим, что положительные целые числа с множественной точностью хранятся с прямым порядком байтов , то есть x хранится как массив x [0], ..., x [ℓ - 1] такой, что 0 ≤ x [ i ] < B для всех i и x = ∑ x [ i ] B i . Алгоритм начинается с целого числа с множественной точностью T и сокращает его по одному слову за раз. Сначала добавляется соответствующее кратное N , чтобы сделать T делящимся на B . Затем добавляется кратное N , чтобы сделать T делящимся на B 2 , и так далее. В конце концов T делится на R , и после деления на R алгоритм оказывается в том же месте, в котором был REDC после вычисления t .
Функция MultiPrecisionREDC имеет входные данные: целое число N с gcd( B , N ) = 1 , сохраненное в виде массива из p слов, Целое число R = B r , --таким образом, 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 i+1 c ← 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 ⌋ конец для для p ≤ j ≤ r + p − i сделать --loop3- Продолжить перенос x ← T [ i + j ] + c T [ i + j ] ← x mod B c ← ⌊ x / B ⌋ конец для конец для для 0 ≤ i ≤ p do S [ i ] ← T [ i + r ] конец для если S ≥ N, то вернуть S − N, иначе вернуть S, конец, если функция завершена
Окончательное сравнение и вычитание выполняется по стандартным алгоритмам.
Вышеуказанный алгоритм верен по сути по тем же причинам, по которым верен REDC. Каждый раз в цикле i выбирается m так, чтобы T [ i ] + mN [0] делилось на B . Затем mNB i добавляется к T . Поскольку эта величина равна нулю mod N , ее добавление не влияет на значение T mod N . Если m i обозначает значение m, вычисленное в i- й итерации цикла, то алгоритм устанавливает S в T + (∑ m i B i ) N . Поскольку MultiPrecisionREDC и REDC выдают одинаковый вывод, эта сумма совпадает с выбором m , который сделал бы алгоритм REDC.
Последнее слово T , T [ r + p ] (и, следовательно, S [ p ] ), используется только для хранения переноса, поскольку начальный результат редукции связан с результатом в диапазоне 0 ≤ S < 2N . Из этого следует, что этого дополнительного слова переноса можно полностью избежать, если заранее известно, что R ≥ 2N . В типичной двоичной реализации это эквивалентно утверждению, что этого слова переноса можно избежать, если количество бит N меньше количества бит R . В противном случае перенос будет равен либо нулю, либо единице. В зависимости от процессора может быть возможно сохранить это слово как флаг переноса вместо полноразмерного слова.
Можно объединить умножение с множественной точностью и REDC в один алгоритм. Этот объединенный алгоритм обычно называется умножением Монтгомери. Несколько различных реализаций описаны Кочем, Акаром и Калиски. [5] Алгоритм может использовать всего 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 = 2j Т с- ------- -0 0485670 2 (После первой итерации первого цикла)1 0485670 22 0485670 23 0487670 0 (После первой итерации второго цикла)4 0487670 05 0487670 06 0487670 0я ← 1м ← 4 ⋅ 7 мод 10 = 8j Т с- ------- -0 0087670 6 (После первой итерации первого цикла)1 0067670 82 0067670 83 0067470 1 (После первой итерации второго цикла)4 0067480 05 0067480 0я ← 2м ← 6 ⋅ 7 мод 10 = 2j Т с- ------- -0 0007480 2 (После первой итерации первого цикла)1 0007480 22 0007480 23 0007400 1 (После первой итерации второго цикла)4 0007401 0
Следовательно, перед окончательным сравнением и вычитанием S = 1047. Окончательное вычитание дает число 50. Поскольку представление Монтгомери для 314 ⋅ 271 mod 997 = 349 равно 349000 mod 997 = 50 , это ожидаемый результат.
При работе в системе счисления с основанием 2 определение правильного m на каждом этапе особенно просто: если текущий рабочий бит четный, то m равно нулю, а если нечетный, то m равно единице. Кроме того, поскольку каждый шаг MultiPrecisionREDC требует знания только самого младшего бита, умножение Монтгомери можно легко объединить с сумматором с сохранением переноса .
Поскольку сокращение Монтгомери избегает шагов коррекции, необходимых при обычном делении, когда оценки цифр частного неточны, оно в основном свободно от условных ветвей, которые являются основными целями атак по времени и мощности ; последовательность выполняемых инструкций не зависит от значений входных операндов. Единственным исключением является конечное условное вычитание модуля, но его легко модифицировать (чтобы всегда что-то вычитать, либо модуль, либо ноль), чтобы сделать его устойчивым. [4] Конечно, необходимо гарантировать, что алгоритм возведения в степень, построенный вокруг примитива умножения, также устойчив. [4] [6]
