{
title: Cofactor Explained: Clearing Elliptic Curves’ dirty little secret
description:
Efficient elliptic curves tend not to have a prime order.
This discusses the problems this causes, and the solutions.
}
April 2020
Cofactor Explained: Clearing Elliptic Curves’ dirty little secret
=================================================================
Much of public key cryptography uses the notion of prime-order groups.
We first relied on the difficulty of the [Discrete Logarithm
Problem][DLP]. Problem was, [Index Calculus][IC] makes DLP less
difficult than it first seems. So we used longer and longer keys
– up to 4096 bits (512 bytes) in 2020 – to keep up with
increasingly efficient attacks.
Elliptic curves solved that. A well chosen, safe curve can only be
broken by [brute force][PR]. In practice, elliptic curve keys can be as
small as 32 bytes.
On the other hand, elliptic curves were not exactly fast, and the maths
involved many edge cases and subtle death traps. Most of those problems
were addressed by [Edwards curves][EC], which have a complete addition
law with no edge cases, and [Montgomery curves][MC], with a simple and
fast [scalar multiplication method][ML].
Those last curves however did introduced a tiny little problem: their
order is _not_ prime.
[DLP]: https://en.wikipedia.org/wiki/Discrete_logarithm (Wikipedia)
[IC]: https://en.wikipedia.org/wiki/Index_calculus_algorithm (Wikipedia)
[PR]: https://en.wikipedia.org/wiki/Pollard%27s_rho_algorithm (Pollard’s rho)
[EC]: https://en.wikipedia.org/wiki/Edwards_curve (Wikipedia)
[MC]: https://en.wikipedia.org/wiki/Montgomery_curve (Wikipedia)
[ML]: https://eprint.iacr.org/2017/293.pdf (Bernstein & Lange, 2017)
_(Before we dive in, be advised: this is a dense article. Don’t
hesitate to take the time you need to digest what you’ve just read and
develop an intuitive understanding. Prior experience with elliptic
curve scalar multiplication helps too.)_
Prime-order groups primer
————————-
First things first: what’s so great about prime-order groups? What’s a
[group][] anyway? What does “order” even mean?
[group]: https://en.wikipedia.org/wiki/Group_(mathematics) (Wikipedia)
A _group_ is the combination of a _set_ of elements “G”, and an
operation “+”. The operation follows what we call the _group laws_.
– For all a and b in G, a+b is also in G _(closure)_.
– For all a, b, and c in G, (a+b)+c = a+(b+c) _(associativity)_.
– There’s an element “0” such that for all a, 0+a = a+0 = a _(identity
element)_.
– For all a in G, there’s an element -a such that a + -a = 0 _(inverse
element)_.
Basically what you’d expect from good old addition.
The _order_ of a group is simply the number of elements in that
group.
To give you an example, let’s take G = [0..15], and define + as binary
exclusive or. All laws above can be checked. It’s order is 16 (there
are 16 elements). Note some weird properties. For instance, each
element is its own inverse (a xor a is zero).
More interesting are _cyclic groups_, which have a _generator_: an
element that repeatedly added to itself can walk through the entire
group (and back to itself, so it can repeat the cycle all over again).
Cyclic groups are all [isomorphic][] to the group of non-negative
integers modulo the same order. Let’s take for instance [0..9], with
addition modulo 10. The number 1 is a generator of the group:
[isomorphic]: https://en.wikipedia.org/wiki/Isomorphism#Integers_modulo_6 (Wikipedia)
1 = 1
2 = 1+1
3 = 1+1+1
4 = 1+1+1+1
5 = 1+1+1+1+1
6 = 1+1+1+1+1+1
7 = 1+1+1+1+1+1+1
8 = 1+1+1+1+1+1+1+1
9 = 1+1+1+1+1+1+1+1+1
0 = 1+1+1+1+1+1+1+1+1+1
1 = 1+1+1+1+1+1+1+1+1+1+1 (next cycle starts)
2 = 1+1+1+1+1+1+1+1+1+1+1+1
etc.
Not all numbers are generators of the entire group. 5 for instance can
generate only 2 elements: 5, and itself.
5 = 5
0 = 5+5
5 = 5+5+5 (next cycle starts)
0 = 5+5+5+5
etc.
Note: we also use the word “order” to speak of how many elements are
generated by a given element. In the group [0..9], 5 “has order 2”,
because it can generate 2 elements. 1, 3, 5, and 9 have order 10. 2, 4,
6, and 8 have order 5. 0 has order 1.
Finally, _prime-order groups_ are groups with a prime number of
elements. They are all cyclic. What’s great about them is their
uniform structure: _every element_ (except zero) can generate the whole
group. Take for instance the group [0..10] (which has order 11). Every
element except 0 is a generator:
_(Note: from now on, I will use the notation `A.4` to denote `A+A+A+A`.
This is called “scalar multiplication” (in this example, the group
element is `A` and the scalar is `4`). Since addition is associative,
[various tricks][FSM] can speed up this scalar multiplication. I use a
dot instead of “×” so we don’t confuse it with ordinary multiplication,
and to remind that the group element on the left of the dot is not
necessarily a number.)_
[FSM]: fast-scalarmult
1.1 = 1 2.1 = 2 3.1 = 3 4.1 = 4
1.2 = 2 2.2 = 4 3.2 = 6 4.2 = 8
1.3 = 3 2.3 = 6 3.3 = 9 4.3 = 1
1.4 = 4 2.4 = 8 3.4 = 1 4.4 = 5
1.5 = 5 2.5 = 10 3.5 = 4 4.5 = 9
1.6 = 6 2.6 = 1 3.6 = 7 4.6 = 2 etc.
1.7 = 7 2.7 = 3 3.7 = 10 4.7 = 6
1.8 = 8 2.8 = 5 3.8 = 2 4.8 = 10
1.9 = 9 2.9 = 7 3.9 = 5 4.9 = 3
1.10 = 10 2.10 = 9 3.10 = 8 4.10 = 7
1.11 = 0 2.11 = 0 3.11 = 0 4.11 = 0
You get the idea.
In practice, we can’t distinguish group elements from each other: apart
from zero, they all have the same properties. That’s why discrete
logarithm is so difficult: there is no structure to latch on to, so an
attacker would mostly have to resort to brute force.
_(Okay, I lied. Natural numbers do have some structure to latch on to,
which is why RSA keys need to be so damn huge. Elliptic curves –
besides treacherous [exceptions][] – don’t have a known
exploitable structure.)_
[exceptions]: https://safecurves.cr.yp.to/transfer.html
The cofactor
————
So what we want is a group of order P, where P is a big honking prime.
Unfortunately, the simplest and most efficient elliptic curves out there
– those that can be expressed in Montgomery and Edwards form
– don’t give us that. Instead, they have order P×H, where P is
suitably large, and H is a small number (often 4 or 8): the _cofactor_.
Let’s illustrate this with the cyclic group [0..43], of order 44. How
much structure can we latch on to?
0 1 2 3
4 5 6 7
8 9 10 11
12 13 14 15
16 17 18 19
20 21 22 23
24 25 26 27
28 29 30 31
32 33 34 35
36 37 38 39
40 41 42 43
Since 44 is not prime, not all elements will have order 44. For
instance:
– 1 has order 44
– 2 has order 22
– 3 has order 44
– 4 has order 11
– …
You get the idea. When we go over all numbers, we notice that the order
of each element is not arbitrary. It is either 1, 2, 4, 11, 22, or 44.
Note that 44 = 11 × 2 × 2. We can see were the various orders come
from: 1, 2, 2×2, 11, 11×2, 11×2×2.
The order of an element is easy to test: just multiply by the order to
test, see if it yields zero. For instance (remember `A.4` is a short
hand for `A+A+A+A`, and we’re working modulo 44 – the order of the
group):
8 . 11 = 0 — prime order
24 . 11 = 0 — prime order
25 . 11 = 33 — not prime order
11 . 4 = 0 — low order
33 . 4 = 0 — low order
25 . 4 = 12 — not low order
_(“Low order” means orders below 11: 1, 2, 4. Not much lower than 11,
but if we replace 11 by a large prime P, the term “low order” makes more
sense.)_
Understandably, there are only few elements of low order: 0, 11, 22,
and 33. 0 has order 1, 22 has order 2, 11 and 33 have order 4. Like the
column on the left, they form a proper subgroup. It’s easier to see by
swapping and rotating the columns a bit:
0 11 22 33
4 15 26 37
8 19 30 41
12 23 34 1
16 27 38 5
20 31 42 9
24 35 2 13
28 39 6 17
32 43 10 21
36 3 14 25
40 7 18 29
The low order subgroup is shown on the first line. And now we can
finally see the structure of this group: a narrow rectangle, with 11
lines and 4 columns, where each element in this rectangle is the sum of
an element of prime order, and an element of low order. For instance:
30 = 8 + 22 = 4.2 + 11.2
35 = 24 + 11 = 4.7 + 11.1
1 = 12 + 33 = 1.3 + 11.3
You just have to look left and up to know which elements to sum. To do
this algebraically, you need to multiply by the right scalar. You need
to _clear the (co)factor_.
Let’s first look left. How do we clear the cofactor? We start by an
element that can be expressed thus:
E = A.4 + B.11
What we want to find is the scalar `s` such that
E.s = A.4
Note that
E.s = A.(4×s) + B.(11×s)
E.s = A.(4×1) + B.(11×0)
Recall that `A` has order 11, and `B` has order 4. So `s` must follow
these equations:
s = 1 mod 11 — preserve A
s = 0 mod 4 — absorb B
There’s only one such scalar between 0 and 44: 12. So, multiplying by
12 clears the cofactor, and preserves the prime factor. For instance:
13.12 = 24
27.12 = 16
42.12 = 20
Now we know how to look left. To look _up_, we follow the same
reasoning, except this time, our scalar `s` must follow _these_
equations:
s = 0 mod 11 — absorb A
s = 1 mod 4 — preserve B
That’s 33. For instance:
13.33 = 33
27.33 = 11
42.33 = 22
Now we can look up as well.
_(Note: This “looking up” and “looking left” terminology isn’t
established mathematical terminology, but rather a hopefully helpful
illustration. Do not ask established mathematicians or cryptographers
about “looking up” and “looking left” without expecting them to be at
least somewhat confused.)_
Torsion safe representatives
—————————-
We now have an easy way to project elements in the prime-order
subgroup. Just look left by multiplying the element by the appropriate
scalar (in the case of our [0..43] group, that’s 12). That lets us treat
each line of the rectangle as an equivalence class, with one canonical
representative: the leftmost element – the one that is on the
prime-order subgroup. This effectively gets us what we want: a
prime-order group.
Let’s say we have a scalar `s` and an element `E`, which are not
guaranteed to be on the prime-order subgroup. We want to know in which
line their scalar multiplication will land, and we want to represent
that line by its leftmost element. To do so, we just need to perform the
scalar multiplication, then look left. For instance:
s = 7 — some random scalar
E = 31 — some random point
E.s = 41
result = (E.s).12 = 8
Or we could _first_ project `E` to the left, then perform the scalar
multiplication. It will stay on the left column, and give us the same
result:
E = 31
E . 12 = 20
result = (E.12).s = 8
The problem with this approach is that it is _slow_. We’re performing
two scalar multiplications instead of just one. That kind of defeats
the purpose of choosing a fast curve to begin with. We need something
better.
Let us look at our result one more time:
result = (E.s).12 = 8
result = (E.12).s = 8
It would seem the order in which we do the scalar multiplications does
not matter. Indeed, the associativity of group addition means we can
rely on the following:
(A.s).t = A.(s×t)
= A.(t×s)
= (A.t).s
Now you can see that we can avoid performing two scalar multiplications,
and multiply the two scalars instead. To go back to our example:
s = 7 — our random scalar
E = 31 — our random point
result = E.(7×12) — scalarmult and look left
result = E.(84)
result = E.(40) — because 84 % 44 = 40
result = 8
Remember we are working with a cyclic group of order 44: adding an
element to itself 84 times is like adding it to itself 44 times (the
result is zero), and again 40 times. So better reduce the scalar modulo
the group order so we can have a cheaper scalar multiplication.
Let’s recap:
s = 7 — our random scalar
E = 31 — our random point
E.s = 41
E.(s×12) = 8
41 and 8 are on the same line, and 8 is in the prime-order subgroup.
Multiplying by s×12 instead of s preserved the main factor, and
_cleared_ the cofactor. Because of this, we call `s×12` the _torsion
safe representative_ of `s`.
Now computing `(s×12) % 44` may be simple, but it doesn’t look very
cheap. Thankfully, we’re not out of performance tricks:
(s×12) % 44 = (s×(11+1)) % 44
= (s×(11+1)) % 44
= (s + (s × 11)) % 44
= s + (s × 11) % 44 — we assume s
