Montgomery modular multiplication

Montgomery modular multiplication is a clever way to make multiplying numbers under modular arithmetic faster. It was created in 1985 by American mathematician Peter L. Montgomery. This method is especially useful when we need to do many multiplications one after another, like in some important computer security systems.

The trick behind Montgomery multiplication is to represent numbers in a special way, called Montgomery form. This lets the computer avoid a slow step called division that normally happens when multiplying numbers under modulus. Instead, it only needs to divide by a special number R, which can be chosen to make this division really easy. On computers that work with binary numbers, R is often a power of two, and dividing by such numbers is as simple as shifting bits.

While converting numbers to and from this special form takes some extra steps, it saves time when many multiplications are needed. This is why Montgomery multiplication is used in important systems like RSA and Diffie–Hellman key exchange. These systems rely on doing arithmetic with very large numbers, and Montgomery multiplication helps make those calculations faster and more efficient.

Modular arithmetic

Let N be a positive integer. In modular arithmetic, we work with numbers by considering their remainders after division by N. These remainders are called residue classes. For example, when N is 17, the numbers 7 and 24 are in the same residue class because both leave a remainder of 7 when divided by 17.

We can add, subtract, or multiply these residue classes by using their remainders. For instance, to add 7 and 15 modulo 17, we first add the numbers to get 22. Then we find the remainder when 22 is divided by 17, which is 5. So, 7 + 15 is equivalent to 5 modulo 17. This way, we keep numbers small and easy to work with in calculations.

Montgomery form

Montgomery form is a special way to represent numbers that makes multiplying large numbers under modular arithmetic easier and faster. Normally, multiplying two numbers and then finding the remainder after division can be slow because division takes a lot of time on computers.

In Montgomery form, numbers are changed so that division can be replaced with simpler actions like shifting or dropping parts of the number, which are much faster. This helps computers do big calculations more quickly.

Montgomery arithmetic on multiprecision integers

Most cryptographic tools need to work with very large numbers, sometimes hundreds or even thousands of bits long. These numbers are too big to fit into a single piece of computer memory, so they are broken into smaller parts for calculation.

Montgomery multiplication is a smart way to make these big number calculations faster. It works by breaking down the problem into smaller, easier steps that the computer can handle more quickly. This method is especially useful when dealing with numbers in modular arithmetic, a key part of keeping information safe online.

Side-channel attacks

Montgomery reduction avoids correction steps needed in regular division when estimates are wrong. This helps protect against timing and power side-channel attacks because the steps the computer takes do not change based on the numbers being used. There is one small exception at the end, but it can be adjusted to stay safe. It's also important that the overall exponentiation method used with this multiplication is secure.