# Pohlig Hellman and small subgroup attacks

While studying Curve25519 I read about the small subgroup attack in chapter 3. So far i know, that you need a point with a small subgroup to do such an attack. Curve25519 has a basepoint with prime order, therefore it is resistent. My question is: How does such a small subgroup attack work? Can you give me an example?

Now I'm a bit confused, too. I know the Pohling Hellman attack. You can use this attack, when the order of the field of the elliptic curve is not prime ( you can use it with a prime field, too, but it is not useful ). How it works: Be $$E$$ an elliptic curve over $$F_p$$. Be $$p = f_1 \cdot f_2 \cdot ... \cdot f_n$$ the factorization. Be $$xP = Q$$ the discrete logarithm. Now you can use the Chinese remainder theorem to solve the following system of equations: $$x \cdot (p/f_1)P = (p/f_1)Q$$, $$x \cdot (p/f_2)P = (p/f_2)Q$$, ... , $$x \cdot (p/f_n)P = (p/f_n)Q$$. So this can be used to calculate the private key by just knowing the public key. My question: I think those two attacks are related. But I don't understand how. Can you explain this to me?

The Pohlig-Hellman algorithm reduces the discrete logarithm from a group of composite order to subgroups of prime order. For instance, with an elliptic curve and a point $$P$$ whose order is a composite integer $$q = p_1 \cdot p_2$$, and we want to find $$k$$ such that $$Q = [k]P$$ for a given point $$Q$$. Then, since $$[p_2]P$$ is a point of order $$p_1$$. Let $$Q_2 = [p_2] Q,\quad \text{and} \quad P_2 = [p_2]P,$$ and now we have $$Q_2 = [k\bmod p_1] P_2$$. Generic discrete logarithm algorithms can then be used to get to obtain $$k\bmod p_1$$.

With $$Q_1 = [p_1]Q$$ and $$P_1 = [p_1]P$$, we obtain $$k\bmod p_2$$ and the Chinese Remainder Theorem can be used to get $$k$$. Then, the security depends mainly on the largest prime in the decomposition of $$q$$. That's why points whose order $$q$$ is a large prime is chosen.

In the small subgroup attack, the idea is to make the computation happens with a point of small order instead of a point whose order is a large prime. Typically, standardized curves in cryptography have order $$q\cdot h$$ where $$q$$ is a large prime and $$h$$ is generally small. The principle is the attacker, instead of sending a point of order $$q$$, sends a point $$P$$ of order $$h$$ (for example in a Diffie-Hellman key-exchange). Then the computation with a secret value $$k$$ will be $$Q = [k]P$$, but since $$P$$ has order $$h$$, there is at most $$h$$ possible values for $$Q$$.

In a Diffie-Hellman key-exchange, it works like this: the attacker sends $$P$$ of small order to Alice instead of its valid public point. Alice computes $$Q = [k]P$$ thinking that the point $$Q$$ is the shared secret, from which she derives a symmetric key to encrypt the communication. Since there is only a few possible values for $$Q$$, there are only a few possible keys. The attacker tries them one by one until the decryption is correct. When this is the case, he learns $$k \bmod h$$.

You can use this attack, when the order of the field of the elliptic curve is not prime ( you can use it with a prime field, too, but it is not useful ). How it works: Be $$E$$ an elliptic curve over $$F_p$$. Be $$p = f_1 \cdot f_2 \cdot \ldots \cdot f_n$$ the factorization.

For clarification, in cryptography an elliptic curve is defined over a finite field, and a finite field has an order that is either a prime $$p$$ or a power of a prime $$p^\ell$$. This value is not the order of the curve. The order of the curve is very close to it, but is generally different.

• But how exactly does a small subgroup attack work? First attempt: I'm sending a "bad" public point to the victim. Then the victim calculates a secret shared key, which I should not get. Second attempt: I take the public key of the victim, then make a multiplication with a small subgroup. But I don't understand how to get informations with this method. I did not find a example for that attack, can you provide a simple one? – Titanlord Jul 11 at 10:15
• The attacker sends a point $P$ to Alice who thinks it's a valid public point. she computes $Q=[k]P$ thinking $Q$ is the shared secret. Since there is only a few possible values for $Q$, it is the same for the secret key derived from it. Then, the attacker decrypts the communication by trying the possible keys, and learns $k\bmod h$ when the decryption is correct. (I have added this in my answer above.) – corpsfini Jul 11 at 11:19