Alice and Bob in Cryptoland – Random posts about cryptography and programming

Visualizing group structure, part 2: prime vs. composite, CRT

Some time ago I’ve generated colored addition/multiplication tables in order to visualize group structure. My idea was to compare extension fields of same order with different reduction polynomials, and to compare elliptic curve groups with groups of integers modulo a prime ( $\mathbb{Z}_p$ ). However, as pointed out by an attentive reader, I’ve messed up claiming that the latter group is used by RSA. It is not, it’s used for e.g. DSA, while RSA uses a composite modulus: the product of two prime numbers.

So, how do $\mathbb{Z}_p^*$ and $\mathbb{Z}_n^*$ compare?

The C language still surprises me

What does this code print?

#include <stdio.h>
 
int main()
{
    signed char x = -128;
 
    if (x < 0) {
        x = -x;
    }
    printf("x = %d\n", (int) x);
    return 0;
}

I’ve been reading Matters Computational, an excellent (free) book by Jörg Arndt about programming and algorithms. It surprised me in the very first pages with this pitfall in two’s complement – there is always a number that is equal to its own negative, besides zero. The code above prints −128!

In hindsight, it’s pretty obvious. A signed char can hold values from −128 to 127 — that is, there are 127 positive numbers and 128 negative numbers! Therefore, it’s impossible to the unary negative operator to be one-to-one. The smallest negative number will always be mapped to itself. Of course, this also applies to int, etc.

The main implication of this fact is that, after the innocent-looking code

if (x < 0) x = -x;

x is not guaranteed to be positive!

Understanding the Montgomery reduction algorithm

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.

Understanding the extended Euclidean algorithm

The Euclidean 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(a,b). 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).