5
$\begingroup$

I thought I understood cofactor clearing before I read this write-up which generally seems quite popular (lot of other sites link to it) - Cofactor Explained: Clearing Elliptic Curves' dirty little secret

Let's say you have a group of non-prime order like say $44$. Now, $44 = 11 * 4$. We are interested in working in the prime-order subgroup - i.e. the subgroup of order $11$ - i.e. $[0, 4, 8, 12, 16, 20, 24, 28, 32, 36, 40]$

If I pick a random element from the group of $44$, I can easily map it to the prime order subgroup by scalar multiplying the element by the cofactor ($4$). It can be easily shown that this operation maps any element of the group to an element of the prime-order subgroup. This is called cofactor clearing (as per other texts I have read).

However, this write-up (the one I have linked to at the start) presents quite a complicated way of doing cofactor clearing.

He first expresses an element $E$ of the group as $E = 4.a + 11.b$ & does some stuff to do the cofactor clearing. I spent quite some time poring over it & I am unable to figure out why is he is doing all this?

My question isn't about how he goes about cofactor clearing but about why he does this complicated stuff rather than just multiplying by $4$. Also my question isn't about why cofactor clearing is required which I understand.

$\endgroup$
7
  • 1
    $\begingroup$ One easy way to see this is viewing $Z_{44}$ as $Z_{4}\times Z_{11}$, then $12$ can be represented as $(0,1)$ $\endgroup$
    – kelalaka
    Sep 2, 2022 at 16:03
  • $\begingroup$ @kelalaka - my question is why? Why do all this at all if you can map any element to the prime subgroup by multiplying by the cofactor? $\endgroup$
    – user93353
    Sep 2, 2022 at 19:18
  • $\begingroup$ Because they ( poster ) want to investigate a possible structure, however they did not see the easy connection of the direct product groups. Also, multiplying with 4 maps to another point, where as, 12 is just removing the one dimension. $\endgroup$
    – kelalaka
    Sep 2, 2022 at 19:31
  • $\begingroup$ @kelalaka How is the structure relevant to cofactor clearing? $\endgroup$
    – user93353
    Sep 2, 2022 at 19:35
  • $\begingroup$ See the updated comment... $\endgroup$
    – kelalaka
    Sep 2, 2022 at 19:35

1 Answer 1

4
$\begingroup$

What you're arguing is that if you pick a uniformly random element of a non-prime order group and you multiply by the cofactor, you'll get a uniformly random element of the prime-order subgroup. This is true and you could prove it by arguing that cosets of the kernel of this multiplication form a partition of the group.

However, if a cyclic group $C$ has order $np$ for $p$ prime and $gcd(n,p)=1$, then it can be written as $C\cong C_n\times C_p$, i.e. a product of two cyclic groups. So any element $g\in C$ can be written as a pair $(g_n,g_p)$. Multiplying just by the cofactor $n$ maps us from $(g_n,g_p)$ to $(0,ng_p)$. This cleared the cofactor part, but it changed the prime-order part. What if we didn't want that? What if we wanted to go from $(g_n,g_p)$ to $(0,g_p)$? We want to project to one component (almost like multiplying by $(0,1)$, but these are additive groups so we can't multiply elements like that). One way to see this is that after we multiply by $n$ (which clears out the first component) we need to multiply by something to clear out $n$ in the second component. Since $gcd(n,p)=1$, there is some $n'\equiv n^{-1}\mod p$, so multiplying by $nn'$ does the trick.

We can see this another way by noting that we have a projection $P:C_n\times C_p\rightarrow C_n\times C_p$ such that $P(a,b)=(0,b)$, and we want to create a map $\tilde{P}:C\rightarrow C$ such that $\tilde{P}$ has the same action as $P$ given the isomorphism from $C_n\times C_p$ to $C$. The original posted gives an explicit isomorphism in the comments, as $f(a,b)=an + bp$. You can then show that multiplying by $nn'$ in $C$ does have the effect of projecting to $C_p$ in $C_n\times C_p$.

But I have no idea why we would want that. I tried reading through the rest of it and I still don't really see why. Here's my best guess: later on they say for various reasons we want to output public keys as uniformly random points on Curve25519, even though we only do the key exchange on the prime-order subgroup. So, we need to add a random point in the cofactor group. That is, Alice's "real" public key would be some point $(0,p_A)=(0,s_Ap)$, but she modifies it to $(r_A,p_A)$ by adding a random cofactor point $r_A$ (here using the product notation of above).

The way they explain it, both parties have already multiplied a cofactor of 4 into their private keys, so multiplying by their private key will automatically clear out the cofactor part of the group, e.g., if Bob's secret key $s_B$ is divisible by $4$, then $s_B(r_A,p_A)=(s_Br_A,s_Bp_A)=(0,s_Bp_A)$, as it should be.

Suppose instead I stored my secret key as $s_B'\in \{0,1,\dots,p-1\}$, so that my public key is $(0,s_B'p)$. Then if I multiplied by this secret key, I'd get $(s_B'r_A,s_B'p_A)$ where $s_B'r_A$ is not necessarily $0$. I want to clear that out without modifying $s_B'p_A$ in any way. So, I use the more complicated cofactor clearing shown in the post.

It seems to me like a simpler way to do the same would be to enforce multiplying by the cofactor at the start of any scalar multiplication, but there might be subtle issues I'm missing, or I'm totally wrong about why we would do this.

$\endgroup$
11
  • 1
    $\begingroup$ Actually, the post just multiplies with $(0,1)$ that is 12, it is just another way to see the multiplier. Just clears the one dimension from the space, nothing more. $\endgroup$
    – kelalaka
    Sep 2, 2022 at 16:09
  • $\begingroup$ Yeah, $3=4^{-1}\mod 11$ so 12 is 4 times $4^{-1}$. $\endgroup$
    – Sam Jaques
    Sep 2, 2022 at 17:50
  • $\begingroup$ I just indicate an easy way to see it to improve your post. The poster is not talking about efficiency, they talk about how to find the multiplier. $\endgroup$
    – kelalaka
    Sep 2, 2022 at 18:06
  • 1
    $\begingroup$ @kelalaka - by "poster", do you mean me or the guy who wrote the blog? $\endgroup$
    – user93353
    Sep 2, 2022 at 19:19
  • $\begingroup$ Yeah, that's a good suggestion, edited. $\endgroup$
    – Sam Jaques
    Sep 3, 2022 at 19:45

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.