Введение
Алгоритм быстрого модульного умножения. В вычислениях в модульной арифметике умножение Монтгомери, более известное как умножение Монтгомери, является методом быстрого модульного умножения. Оно было представлено в 1985 году американским математиком Питером Л. Монтгомери. Умножение Монтгомери опирается на специальное представление чисел, называемое формой Монтгомери. Алгоритм использует формы Монтгомери чисел a и b для эффективного вычисления формы Монтгомери произведения ab по модулю N. Эффективность достигается за счет избежания дорогостоящих операций деления. Классическое модульное умножение уменьшает произведение двойной ширины ab, используя деление на N и сохраняя только остаток. Это деление требует оценки и коррекции разрядных коэффициентов частного. Форма Монтгомери, напротив, зависит от константы R > N, взаимно простой с N, и единственное деление, необходимое при умножении Монтгомери, — это деление на R. Константу R можно выбрать так, чтобы деление на R было простым, что значительно повышает скорость алгоритма. На практике R всегда является степенью двойки, поскольку деление на степени двойки может быть реализовано с помощью битового сдвига. Необходимость преобразования a и b в форму Монтгомери и преобразования их произведения из формы Монтгомери означает, что вычисление одного произведения с помощью умножения Монтгомери медленнее, чем с использованием обычных алгоритмов восстановления или восстановления Барретта. Однако при выполнении множества последовательных умножений, как, например, при модульном возведении в степень, промежуточные результаты можно оставлять в форме Монтгомери. Тогда начальные и конечные преобразования становятся пренебрежимо малой частью общих вычислений. Многие важные криптосистемы, такие как RSA и обмен ключами Диффи — Хеллмана, основаны на арифметических операциях по модулю большого нечетного числа, и для этих криптосистем вычисления с использованием умножения Монтгомери, где R является степенью двойки, быстрее, чем доступные альтернативы.
In modular arithmetic computation, Montgomery modular multiplication, more commonly referred to as Montgomery multiplication, is a method for performing fast modular multiplication. It was introduced in 1985 by the American mathematician Peter L. Montgomery. Montgomery modular multiplication relies on a special representation of numbers called Montgomery form. The algorithm uses the Montgomery forms of a and b to efficiently compute the Montgomery form of ab mod N. The efficiency comes from avoiding expensive division operations. Classical modular multiplication reduces the double width product ab using division by N and keeping only the remainder. This division requires quotient digit estimation and correction. The Montgomery form, in contrast, depends on a constant R > N which is coprime to N, and the only division necessary in Montgomery multiplication is division by R. The constant R can be chosen so that division by R is easy, significantly improving the speed of the algorithm. In practice, R is always a power of two, since division by powers of two can be implemented by bit shifting. The need to convert a and b into Montgomery form and their product out of Montgomery form means that computing a single product by Montgomery multiplication is slower than the conventional or Barrett reduction algorithms. However, when performing many multiplications in a row, as in modular exponentiation, intermediate results can be left in Montgomery form. Then the initial and final conversions become a negligible fraction of the overall computation. Many important cryptosystems such as RSA and Diffie–Hellman key exchange are based on arithmetic operations modulo a large odd number, and for these cryptosystems, computations using Montgomery multiplication with R a power of two are faster than the available alternatives.
Модульная арифметика
Пусть N обозначает положительное целое число – модуль. Кольцо Z/NZ состоит из классов вычетов по модулю N, то есть его элементы представляют собой множества вида {a + kN | k ∈ Z}, где a пробегает все целые числа. Каждый класс вычетов – это множество целых чисел, для которых разность любых двух чисел из множества делится на N (и класс вычетов максимален относительно этого свойства; целые числа не исключаются из класса вычетов, если только они не нарушают условие делимости). Класс вычетов, соответствующий a, обозначается [a]. Равенство классов вычетов называется сравнением и обозначается a ≡ b (mod N).
where a ranges across the integers. Each residue class is a set of integers such that the difference of any two integers in the set is divisible by N (and the residue class is maximal with respect to that property; integers aren't left out of the residue class unless they would violate the divisibility condition). The residue class corresponding to a is denoted Equality of residue classes is called congruence and is denoted
Storing an entire residue class on a computer is impossible because the residue class has infinitely many elements. Instead, residue classes are stored as representatives. Conventionally, these representatives are the integers a for which 0 ≤ a ≤ N − 1. If a is an integer, then the representative of is written a mod N. When writing congruences, it is common to identify an integer with the residue class it represents. With this convention, the above equality is written a ≡ b mod N.
Arithmetic on residue classes is done by first performing integer arithmetic on their representatives. The output of the integer operation determines a residue class, and the output of the modular operation is determined by computing the residue class's representative. For example, if 1=N = 17, then the sum of the residue classes and is computed by finding the integer sum 1=7 + 15 = 22, then determining 22 mod 17, the integer between 0 and 16 whose difference with 22 is a multiple of 17. In this case, that integer is 5, so .
Хранить весь класс вычетов на компьютере невозможно, поскольку класс вычетов содержит бесконечно много элементов. Вместо этого классы вычетов хранятся в виде представителей. Обычно эти представители – целые числа a, для которых 0 ≤ a ≤ N − 1. Если a – целое число, то представитель класса [a] записывается как a mod N. При записи сравнений принято отождествлять целое число с классом вычетов, который оно представляет. При этом соглашении вышеуказанное равенство записывается как a ≡ b (mod N).
where a ranges across the integers. Each residue class is a set of integers such that the difference of any two integers in the set is divisible by N (and the residue class is maximal with respect to that property; integers aren't left out of the residue class unless they would violate the divisibility condition). The residue class corresponding to a is denoted Equality of residue classes is called congruence and is denoted
Storing an entire residue class on a computer is impossible because the residue class has infinitely many elements. Instead, residue classes are stored as representatives. Conventionally, these representatives are the integers a for which 0 ≤ a ≤ N − 1. If a is an integer, then the representative of is written a mod N. When writing congruences, it is common to identify an integer with the residue class it represents. With this convention, the above equality is written a ≡ b mod N.
Arithmetic on residue classes is done by first performing integer arithmetic on their representatives. The output of the integer operation determines a residue class, and the output of the modular operation is determined by computing the residue class's representative. For example, if 1=N = 17, then the sum of the residue classes and is computed by finding the integer sum 1=7 + 15 = 22, then determining 22 mod 17, the integer between 0 and 16 whose difference with 22 is a multiple of 17. In this case, that integer is 5, so .
Арифметика классов вычетов выполняется путем предварительного выполнения арифметических операций над их представителями. Результат целочисленной операции определяет класс вычетов, а результат операции взятия по модулю определяется вычислением представителя этого класса вычетов. Например, если N = 17, то сумма классов вычетов [7] и [15] вычисляется путем нахождения целочисленной суммы 7 + 15 = 22, затем определения 22 mod 17, то есть целого числа между 0 и 16, разность которого с 22 кратна 17. В этом случае это число равно 5, то есть [7] + [15] ≡ [5] (mod 17).
where a ranges across the integers. Each residue class is a set of integers such that the difference of any two integers in the set is divisible by N (and the residue class is maximal with respect to that property; integers aren't left out of the residue class unless they would violate the divisibility condition). The residue class corresponding to a is denoted Equality of residue classes is called congruence and is denoted
Storing an entire residue class on a computer is impossible because the residue class has infinitely many elements. Instead, residue classes are stored as representatives. Conventionally, these representatives are the integers a for which 0 ≤ a ≤ N − 1. If a is an integer, then the representative of is written a mod N. When writing congruences, it is common to identify an integer with the residue class it represents. With this convention, the above equality is written a ≡ b mod N.
Arithmetic on residue classes is done by first performing integer arithmetic on their representatives. The output of the integer operation determines a residue class, and the output of the modular operation is determined by computing the residue class's representative. For example, if 1=N = 17, then the sum of the residue classes and is computed by finding the integer sum 1=7 + 15 = 22, then determining 22 mod 17, the integer between 0 and 16 whose difference with 22 is a multiple of 17. In this case, that integer is 5, so .
Арифметика в форме Монтгомери
Многие операции, представляющие интерес по модулю N, могут быть выражены столь же хорошо в форме Монтгомери. Сложение, вычитание, отрицание, сравнение на равенство, умножение на целое число, не представленное в форме Монтгомери, и наибольший общий делитель с N могут быть выполнены с использованием стандартных алгоритмов. Символ Якоби может быть вычислен, если сохраняется значение . Когда 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^(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.
Боковые атаки
Поскольку восстановление по Монтгомери избегает корректирующих шагов, необходимых при обычном делении, когда оценки цифр частного неточны, оно в значительной степени лишено условных переходов, которые являются основными объектами атак по временным и энергетическим каналам утечки информации; последовательность выполняемых инструкций не зависит от значений входных операндов. Единственное исключение — финальное условное вычитание модуля, которое, однако, легко модифицировать (чтобы всегда вычитать что-либо, либо модуль, либо ноль) для обеспечения его устойчивости. Разумеется, необходимо также убедиться в устойчивости алгоритма возведения в степень, построенного на основе примитива умножения.