Please support curves over extension Fields in attacks/ecc/smart_attack.py !

[ytrezq]

It’s perfectly possible to use Nigel’s Smart algorithm for anomalous curves over extension fields. The problem is I failed to understand this paper myself enough to implement the variant that works in extension fields.

[jvdsn]

Are you referring to prime power fields (Section 6.2 of that paper)? Do you have an anomalous curve over a prime power (with n > 1) field?

[ytrezq]

@jvdsn yes I am refering to prime power. The paper contains a step by step example for such curve.

[jvdsn]

Sure, it explains how to perform the attack, but I'd need to have a curve to test it on. It's not trivial to generate anomalous curves over prime power fields if n > 1.

[ytrezq]

@jvdsn I may have an imperfect idea. What about a supersingular curves in their extension degree?. For example bn254 has embedding degree 12. Then create 2 points in extension power 12 of and move them to the underlying common suborder/subgroup between the 1 of the curve and the 1 of the underlying finite field.

This means only a part of the order is common to both the curve and it s finite field, but it s where the solution is lying.
Would that work?

[jvdsn]

What's the specification of bn254? I'm seeing conflicting information. Regardless, bn254 doesn't seem to be anomalous so I'm not sure how Smart's attack could be applied to it.

[ytrezq]

@jvdsn yes, the regular curve isn t anomalous but it s degree 12 extension field is partially anomalous. See https://neuromancer.sk/std/bn/bn254 for it s definition.

Don t hesitate to ask me anything else.

[ytrezq]

Let’s have the following curve

p = 0x2523648240000001BA344D80000000086121000000000013A700000000000013
K = GF(p)
a = K(0x0000000000000000000000000000000000000000000000000000000000000000)
b = K(0x0000000000000000000000000000000000000000000000000000000000000002)
E = EllipticCurve(K, (a, b))
G = E(0x2523648240000001BA344D80000000086121000000000013A700000000000012, 0x0000000000000000000000000000000000000000000000000000000000000001)   
E.set_order(0x2523648240000001BA344D8000000007FF9F800000000010A10000000000000D * 0x01)
E_semi_anomalous = E.base_extend(GF(p^12))

and determine the discrete logarithm between those 2 points

pk=E_semi_anomalous.random_point()*ZZ(E_semi_anomalous.order()//E.order())
sk=E_semi_anomalous.random_point()*ZZ(E_semi_anomalous.order()//E.order())

Given the prime E.order() exist in the GF(p**12) base field and also the discrete logarithm lies in the E.order() subgroup.

[jvdsn]

@ytrezq have you tried executing that code? The line E_semi_anomalous = E.base_extend(GF(p^12)) doesn't seem to finish on my machine.

[ytrezq]

@ytrezq have you tried executing that code? The line E_semi_anomalous = E.base_extend(GF(p^12)) doesn't seem to finish on my machine.

It depends on the SageMath version. Please try E_semi_anomalous = E.base_extend(GF(p^12,'a')). Also, thr random point generation code sometimes generates points directly in the correct order which means moving them by ZZ(E_semi_anomalous.order()//E.order()) isn t needed.

[Hurd8x]

Let’s have the following curve

p = 0x2523648240000001BA344D80000000086121000000000013A700000000000013
K = GF(p)
a = K(0x0000000000000000000000000000000000000000000000000000000000000000)
b = K(0x0000000000000000000000000000000000000000000000000000000000000002)
E = EllipticCurve(K, (a, b))
G = E(0x2523648240000001BA344D80000000086121000000000013A700000000000012, 0x0000000000000000000000000000000000000000000000000000000000000001)   
E.set_order(0x2523648240000001BA344D8000000007FF9F800000000010A10000000000000D * 0x01)
E_semi_anomalous = E.base_extend(GF(p^12))

and determine the discrete logarithm between those 2 points

pk=E_semi_anomalous.random_point()*ZZ(E_semi_anomalous.order()//E.order())
sk=E_semi_anomalous.random_point()*ZZ(E_semi_anomalous.order()//E.order())

Given the prime E.order() exist in the GF(p**12) base field and also the discrete logarithm lies in the E.order() subgroup.

Good day. Does it work for secp256k1 ?

Thank you

[ytrezq]

@Hurd8x secp256k1 is a secure prime curve which means no effective attack is known if used correctly. However, feel free to explore adapting https://www.iacr.org/archive/pkc2016/96140156/96140156.pdf to the existing inneficient index calculus methods for prime curves you can find on https://scholar.google.com. Or find a way to apply Pohlig Hellman to the method described in https://eprint.iacr.org/2024/1321 since order−1 has small factors in the case of secp256k1.

You may acheive a research breakthrough.

[Hurd8x]

@Hurd8x secp256k1 is a secure prime curve which means no effective attack is known if used correctly. However, feel free to explore adapting https://www.iacr.org/archive/pkc2016/96140156/96140156.pdf to the existing inneficient index calculus methods for prime curves you can find on https://scholar.google.com. Or find a way to apply Pohlig Hellman to the method described in https://eprint.iacr.org/2024/1321 since order−1 has small factors in the case of secp256k1.

You may acheive a breakthrough.

Thank you.

[jvdsn]

Added in ff1b5b7. I can't promise it'll be particularly fast but it works in polynomial time.

[ytrezq]

Added in ff1b5b7. I can't promise it'll be particularly fast but it works in polynomial time.

Does it works with my example curve here?

[jvdsn]

No, it won't, because your curve is not anomalous