{

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