Category Archives: Math

Understanding the Montgomery reduction algorithm

2009-12-24 – 17:18

The Montgomery reduction algorithm finds the remainder of a division. Many cryptographic schemes work with numbers modulo a prime. When you have to multiply two numbers with e.g. 128 bits each, first you multiply them the usual way (there are many techniques for this) to obtain a 256-bit (“double precision”) number. Then you need to reduce this result modulo the prime you’re working with, that is, compute the remainder of the division of this number over the prime.

You can compute the remainder of a division with the “schoolbook” technique everyone learns in school, but that is expensive and requires divisions, with are costly in many platforms (some microcontrollers don’t even have a division instruction). Montgomery reduction only needs a division by a powers of the integer size, which are cheap for computers.

Here I’ll try to explain how it works, in an informal approach. For detailed proofs of its correctness, check e.g. the chapter 14 of the Handbook of Applied Cryptography or the original paper.

First approach

When working modulo a prime (or modulo anything), you can add or subtract the prime (call it p) from the number you’re working with (call it x) and you’ll always get the same number. For example, 3 = 3 + 7 = 10 = 3 (mod 7), or 3 = 3 – 7 = -4 = 3 (mod 7). This gives the basic approach for finding remainders: just subtract the p from x until you reach a number smaller than p.

For example, you want to compute 6 * 5 modulo 7. You have 6 * 5 = 30, now you just need the remainder of the division of 30 over 7, that is, 30 modulo 7. Now it’s just subtractions:

30 - 7 = 23 (mod 7)
21 - 7 = 16 (mod 7)
16 - 7 = 9 (mod 7)
9 - 7 = 2 (mod 7)

And you’re done: 6 * 5 = 2 (mod 7). But if the number you’re working with is big, the number of subtractions you’ll need will be too large. You can speed up this process by dividing the number by the modulus and computing r = x – (x/p * p). But as I said, division is expensive.

Let’s add, not subtract

The first insight of the Montgomery reduction is this: what if instead of subtracting, you add the prime modulus many times? And more, what if you add the modulus in a way that the number being reduced is filled with zeros to the right? For example, let’s work modulo 97. You want to compute 43 * 56 (mod 97). You multiply the operands obtaining 2408, and you’ll need to reduce it modulo 97. You can add the 97 to this number any times you want, that is, you can add any multiple of 97. Which multiple of 97 that, when added to 2408, leads to a number with last digit 0?

2408 + 6 * 97 =
2408 + 582 =
2990

It’s 6 times 97. It’s easy to find this “magic number”, but I won’t go into this right now. OK, you have a rightmost zero. Let’s try to add again in order to have two zeros:

2990 + 30 * 97 =
2408 + 2910 =
5900

Great! But… so what? Well, suppose these numbers live in a world where they must be divided by 100 after you multiply them and use the above procedure. Then you divide 5900 by 100, which is cheap, and you have 59.

Sadly, these numbers don’t live in such a world, and 59 is not the right answer. If the division is exact, you can divide by any multiple of 97, but you can’t simply divide by 100.

The Montgomery World

The second insight of the Montgomery reduction is: if you need such a world were you must divide by 100, then just create it!

The Montgomery reduction requires transforming the numbers into the “Montgomery domain”, which is exactly the world we need. First let’s look at our modulus: 97. It has two digits in base 10. Then let R be smaller power of the base that is greater than the modulus. For 97, we have R = 10^2 = 100.

To transform a number x into the Montgomery domain, compute x * R (mod p). In our example, suppose x = 35. Then 35 * 100 (mod 97) = 8 (mod 97).

(You may notice that this transformation simply begs the question – you need to reduce modulo p in order to convert the numbers to a form where it’s easier to reduce modulo p! I’ll talk about this later on.)

Now, the beauty of the Montgomery domain: suppose that you want to compute x * y (mod p). Converting the operands, you’ll actually compute (x * R) * (y * R) (mod p). But you want the result to still live in the Montgomery domain. That’s because you may need to do many other multiplications. Since converting the number back to the real world is somewhat expensive, it’s best to keep the computations in the Montgomery domain. Therefore, you want to compute x * y * R (mod p), i.e., you want x * y, but in the Montgomery domain.

Let’s see… if you just multiply the operands the usual way, you get (x * R) * (y * R) (mod p) = x * y * R * R (mod p). But you want x * y * R (mod p). Therefore, every time you multiply two numbers, you’ll need to reduce the result modulo p, but you’ll also need to divide by R. Recall our example, where R = 100, and we wanted to be required to divide by 100. That’s exactly what we got: the Montgomery domain requires the division by 100!

An example

Let x = 43, y = 56, p = 97, R = 100. You want to compute x * y (mod p). First you convert x and y to the Montgomery domain. For x, compute x’ = x * R (mod p) = 43 * 100 (mod 97) = 32, and for y, compute y’ = y * R (mod p) = 56 * 100 (mod 97) = 71.

Compute a := x’ * y’ = 32 * 71 = 2272.

In order to zero the first digit, compute a := a + (4p) = 2272 + 388 = 2660.

In order to zero the second digit, compute a := a + (20p) = 2660 + 194 = 4600.

Compute a := a / R = 4600 / 100 = 46.

We have that 46 is the Montgomery representation of x * y (mod p), that is, x * y * R (mod p). In order to convert it back, compute a * (1/R) (mod p) = 46 * 65 (mod 97) = 80. You can check that 43 * 56 (mod 97) is indeed 80.

Converting the numbers

Let Montgomery(x’,y’) = (x’y')/R (mod p) be the Montgomery reduction of x’ and y’.

Like I mentioned, in order to compute the Montgomery representation of a number or in order to convert it back, you need to multiply by R modulo p or divide by R modulo p. You can compute this remainders using a classic, expensive algorithm, since for practical applications you’ll rarely need to convert the numbers (for example, in a cryptographic application: since no one will need to actually see the real form of the numbers, there is no need for conversions and it’s possible to work entirely in the Montgomery domain). But there is also another approach. You can precompute R’ = R^2 (mod p) and then convert a number x to xR (mod p) by simple computing the Montgomery reduction of x and R’, since Montgomery(x, R’) = Montgomery(x, R^2) = (xRR)/R (mod p) = xR (mod p). To convert back a number x’ = xR (mod p), simply compute the Montgomery reduction of x’ and 1, since Montgomery(x’, 1) = Montgomery(xR, 1) = (xR)/R (mod p) = x (mod p).

The magic numbers

Let B be the base you’re working with. The main step of the Montgomery reduction is “add a multiple k of p that, when added to a, makes its i-th digit zero”. It’s not hard to find k. First, notice that the only relevant digits are the first digit of p (call it p[0]) and the i-th digit of a (call it a[i]). Then:

a[i] + B^i * k * p[0] = 0 (mod B)
k = B^i * a[i] * -(1/p[0]) (mod B)

You can precompute -(1/p[0]) (mod B) and then multiply it by a[i] and B^i (which is just an offset) in order to find k. In our example, with p = 97 and base 10, this value is -(1/7) (mod 10) = -3 (mod 10) = 7.

In the real world

For example, in elliptic curve cryptography in the 128-bit level of security, the operands have 256 bits. Suppose the target platform is a desktop PC with 32 bits. Then the operands are represented by eight 32-bit digits (i.e. B=2^32 as opposed to B=10 in the examples); R is 2^256; and the Montgomery reduction requires eight steps (since the numbers have eight integers).

If you look carefully, you can notice that the Montgomery reduction is nothing more than a multiplication of p with an operand which is computed on the fly (the “magic numbers”). This allows the use of many optimizations from multiplication algorithms.

By Conrado | Also posted in Cryptography | Tagged , , | Comments (0)

Understanding the extended Euclidian algorithm

2009-09-05 – 19:22

The Euclidian algorithm finds the greatest common divisor of two numbers a and b. There is an extended version of it that also finds two numbers x and y such that ax + by = gcd(x,y). This is useful when searching for modular multiplicative inverses.

The algorithm is simple, but I’ve never bothered to study why and how it works (a shame, really, but sometimes you have to postpone the understanding of some basic things in order to go on…). Finally I’ve decide to put some thought on it and came up with this (this is not a proof; it’s just some intuitive thinking to grasp the inner workings of the algorithm).

Suppose that you want to compute the extended Euclidian algorithm for a = 14 and b = 101. You can write

14 *   1 + 101 *   0 =  14
14 *   0 + 101 *   1 = 101

Which is obviously true. Now subtract the first equation from the second:

14 *   1 + 101 *   0 =  14
14 *   0 + 101 *   1 - (14 *   1 + 101 *   0) = 101 - 14 ->
14 *  -1 + 101 *   1 = 87

You can repeat this many times before reducing the right-hand 101 in the second equation to the smallest positive value possible. Notice that it’s faster to take the floor(101/14) and subtract the first equation times the result from the second. In this case, we have floor(101/14) = 7. Therefore, replace the last step with:

14 *   1 + 101 *   0 =  14
14 *   0 + 101 *   1 - [7 * (14 *   1 + 101 *   0)] = 101 - [7 * 14] ->
14 *  -7 + 101 *   1 =   3

Now, switch equations, in order to make the first one the one with the smallest right-hand size (you’ll always need to switch):

14 *  -7 + 101 *   1 =   3
14 *   1 + 101 *   0 =  14

And here you are. Just repeat the same step over and over:

14 *  29 + 101 *  -4 =   2
14 *  -7 + 101 *   1 =   3

14 * -36 + 101 *   5 =   1
14 *  29 + 101 *  -4 =   2

14 * 101 + 101 * -14 =   0
14 * -36 + 101 *   5 =   1

When your first equation has right-hand side equal to 0 (this will always happen), the second equation will be ax + by = gcd(x,y)!

As I mentioned, this is useful in order to find modular inverses: to find which number that when multiplied by 14 gives 1 (modulo 101) you run the algorithm as described and finds that it’s -36 (which is 65 modulo 101). That is, 14 * 65 = 910, which when divided by 101, gives remainder 1. Modular inverses are used in many cryptographic applications, such as RSA.

I think I’ll study next the seemingly magical Montgomery reduction (I understand how it works, I have even implemented it, but I still don’t know why the heck it works)…

By Conrado | Also posted in Cryptography | Comments (1)

The Frobenius endomorphism with finite fields

2009-02-09 – 00:17

The Frobenius endomorphism is defined as:

\Phi(x)=x^p

where p is the characteristic of the ring you’re working with. Simple, right?

If you’re working with a field with prime order, then Frobenius is actually the identity map. Since the order of the multiplicative subgroup is p, when you raise to the power of p you get back to x due to Fermat’s little theorem. Things get more interesting when you’re working with a extension field (i.e. a field which order is a prime power).

I’m studying pairings for my master’s degree and the Frobenius endomorphism appears all the time in their computation. For example, you need to do a “final exponentation” which can be split in multiple exponentiations, and some of them are to the power of p. This is good because powering to p is “easy” due to Frobenius, or at least all the papers I read said so. But for a while I couldn’t see why, and that’s the reason I’m posting this. It’s really easy; it’s just not that obvious to see why.

Why Frobenius is easy?

Say you’re working with a quadratic extension, that is, with a field GF(p^2) where p is a prime. You can represent this group with polynomials of degree 1 which can be added the usual way and multiplied taking the result modulo a irreducible polynomial of degree 2. To understand why this makes sense, I recommend this excellent write-up at Everything2. Assume that you pick a irreducible polynomial in the form X^2-\beta. Working modulo this polynomial is the same thing as working in a “world” where X^2 = \beta. (You could of course work with a polynomial in the form X^2 + aX + b but that would complicate things.)

So every element of GF(p^2) can be written as a + bX. What happens when you apply the Frobenius endomorphism? Let’s see:

(a + bX)^p = (a^p + b^pX^p)

Why is that so? That’s a known fact about the Frobenius, check the explanation at Wikipedia for more details. But basically, the expansion of (a + bX)^p has many terms, but only the first (a^p) and the last (b^pX^p) survive because all others are multiples of p. Since we’re working with coefficients modulo p, they are all zero.

Let’s continue. Since a, b \in GF(p), then raising to the power of p won’t change them (yep, that’s Frobenius again). So we have:

(a + bX)^p = (a^p + b^pX^p) = (a + bX^p)

There’s only X^p left to bother us. If p is odd (not 2), then you can rearrange this as:

(a + bX)^p = (a + bX^p) = (a + b(X^2)^{(p-1)/2}X)

Now remember that we’re working in a “world” where X^2 = \beta. Then we get:

(a + bX)^p = (a + b(X^2)^{(p-1)/2}X^p) = (a + b\beta^{(p-1)/2}X)

That’s why Frobenius is easy: “a” stays the same, all you need to do is multiply “b” with \beta^{(p-1)/2}. But according to Euler’s criterion, since \beta is not a square (if it were, X^2-\beta wouldn’t be irreducible), we have \beta^{(p-1)/2} \equiv -1 \pmod{p}. Then the formula gets much simpler:

(a + bX)^p = (a-bX)

A concrete example

Just for the sake of concreteness, let’s work out an example. I’ll use Sage for that, but I’ll explain what each command does.

sage: K = GF(7)

We create a field with 7 elements (that’s actually integers modulo 7).

sage: K(5)^7
5

We take the element 5 and power to 7. We get 5 again. If you don’t believe it works for all elements:

sage: [(x,x^7) for x in K]
[(0, 0), (1, 1), (2, 2), (3, 3), (4, 4), (5, 5), (6, 6)]

Let’s create GF(7^2).

sage: KR.<X> = GF(7)[]

This creates a polynomial ring with the X variable and coefficients in GF(7), just to allow us to specify the modulus in the next step:

sage: K2.<X> = GF(7^2, modulus=X^2+1)

We create the GF(7^2) field using the variable X (I’m overwriting the X used in the ring, you could use other name) and modulus X^2+1 (so \beta = -1). Let’s take an arbitrary element to the power of 7:

sage: (3*X + 2)^7
4*X + 2

Remeber when \beta = -1 then (a + bX)^p = (a-bX). And modulo 7, -3 is actually 4, so the result is correct (of course!). Again, if you don’t believe it works for all elements:

sage: all(x^7 == (x.vector()[0] - x.vector()[1]*X) for x in K2)
True

This checks, for all elements in the field K2, if the element raised to the power of 7 is equal to the element built with our special formula. The method vector() returns the coefficients of the polynomial as a list. The all function is a relatively unknown function of Python that returns True if all the elements of the iterable passed to it evaluate to True (there’s any(iter) too).

Extensions of higher degree

The trick to calculate the Frobenius endomorphism also works for extensions of higher degree. When implementing them, usually using a tower of extensions is more efficient then using a direct extension. For example, when working with GF(p^{12}), you can represent it as a quadratic extension of GF(p^6), which can be represented as a cubic extension of GF(p^2), which can be represented as a quadratic extension of GF(p).

For example, for (a + bX) \in GF(p^{12}) built this way, with a, b \in GF(p^6), you just apply the same trick explained above. The only difference is that a and b to the power of p aren’t a and b themselves, but that’s not a problem, you just apply the same trick recursively.

By Conrado | Also posted in Cryptography | Tagged , , | Comments (2)

Visualizing group structure with colored addition/multiplication tables

2008-12-07 – 01:32

When working with finite fields, if the number of elements is a prime power p^m with m > 1, you can represent the elements as polynomials with degree m-1 and do the field addition and multiplication modulo a irreducible polynomial with degree m.

The field GF(5) is composed by the numbers 0 to 4. We don’t need to represent its elements as polynomials since m=1. Addition is done modulo 5 and multiplication also modulo 5. So 2 + 3 = 0; 4 * 2 = 3; and so on. This is the addition table for GF(5):

Multiplicative table of integers modulo 5

The rows, top down, represent 0 to 4. The columns, right to left, represent 0 to 4. Each square is the result of the addition of the respective numbers in the row / column it belongs to. Black is 0, purple is 1, red is 2, orange is 3, yellow is 4.

In the field GF(25) = GF(5²), as I said, you represent each element as a polynomial. So we have 25 elements: 0 to 4; x, x+ 1, …, x + 4; 2x, 2x + 1, …; 3x, 3x + 1, …; 4x, 4x + 1, …, 4x + 4.

In order to add two elements, add them as you would add two polynomials, but remember that the coefficients are in GF(5); for example, in GF(5²), we have (3x + 2) + (4x + 4) = (2x + 1). In order to multiply two elements, multiply them as usual but then take the result modulo an irreducible polynomial. So, with GF(5²) modulo x^2 + 4x + 2, you have (2x + 5) * (3x + 4) = (4x + 3).

I always wondered what would happen when you changed the modulus. Obviously the group “changes”, but in order to actually see it, I’ve built the multiplication table for GF(5²) modulus x^2 + 4x + 2 and x^2 + 3x + 3:

Multiplicative table for GF(5^2)/(x^2+4x+2)Multiplicative table for GF(5^2)/(x^2+3x+3)

Yep, they’re different :D

Of course, both are isomorphic, so you’re free to pick your favorite modulus.

Multiplicative group of integers modulo n vs group of points in a elliptic curve

Then I got curious: how would the multiplication table of integers modulo n look like? This group is the group used in many cryptographic schemes, like RSA. This is the multiplication table for integers modulo 509:

Multiplicative table for integers modulo 509

Pretty (and trippy)!

What about the group of points on a elliptic curve over a finite field, which is also a group used in cryptographic schemes? This is the additive table for the points on y^2 = x^3 + 4x + 1 over GF(503):

Additive table for points in y^2 = x^3 +4x + 1 over GF(503)

The difference between them is striking; the elliptic group seems almost random. This is (intuitively speaking! I’m not being formal here) the reason why this group is used in cryptography in the first place: since the group structure is more “messed up”, you can get away with using groups of much smaller size (no smaller than 2^{160} elements) than with multiplicative groups of integers modulo n (no smaller than 2^{1024} elements). This is not set in stone though; maybe someday someone will come up with a better method to crack this seemingly random structure (for now the best method to solve the discrete log problem for elliptic groups is exponential, while the best method for integers modulo n is sub-exponential).

It’s worth mentioning that even this elliptic group is not that extraordinary: it is isomorphic to the very simple additive group of integers modulo 506:

Additive table of integers modulo 516

The big problem is to find the isomorphism! You can see this better with a small example. This is the elliptic group of y^2 = x^3 + 3x + 2 over GF(5) (left) which is isomorphic to the additive group modulo 5 (right):

Additive table of points on y^2 = x^3 + 3x + 2 over GF(5)Additive table for integers modulo 5

(OK, it’s not that easy to see)

Software

To generate those images, I’ve used Python with PIL and Sage. Sage aims to be a open source replacement for (expensive) software like Magma, Maple, Mathematica and Matlab. Since I’ve never used those, I can’t really say how it is going in its mission, but it’s really awesome. If you’re a Windows user you’ll probably be scared by the fact that the Windows version of Sage is actually an entire Linux virtual machine! They’re working to port it natively, but even until then, it’s worth it (and you’ll have an excuse to try Linux ;) )

Update

Someone asked for the source code used to generate those. It’s ugly (I’ve added comments at least) but you can download it here: the sage script and the python script. In the sage script, uncomment the lines representing what you want to plot, then run ./sage gentable.sage (or whichever path to were sage is). It will generate a data.txt in the same folder. Now run python plottable.py img.png to plot it on the img.png file (or omit it to show on the screen). You’ll need to have PIL installed.

If you don’t want to plot fancy stuff as elliptic groups, you can easily transform the gentable.sage into a normal Python script and write the addition/multiplication yourself (like a + b % n). Have fun, and feel free to ask anything.

By Conrado | Also posted in Cryptography | Tagged , , , , | Comments (2)