search

jvdsn / crypto-attacks

Python implementations of cryptographic attacks and utilities.
MIT License
949 stars 125 forks source link

Generate Anomalous Curve with Given order #16

Open gunpal5 opened 1 year ago

gunpal5 commented 1 year ago

I was wondering if it is possible to extend the the function generate_anomalous_q to generate curves with more types of prime numbers, as mentioned in this paper for the case (Case hD ≥ 2.)

(https://doi.org/10.1016/j.ipl.2004.11.008)

Edit: in this file shared/ecc.py you mentioned you'll implement "Accelerating the CM method" by Sutherland. Would you be able to do that? That might help to generate elliptic curve with a given order

jvdsn commented 1 year ago

Could you give an example q for which generate_anomalous_q currently does not work?

in this file shared/ecc.py you mentioned you'll implement "Accelerating the CM method" by Sutherland. Would you be able to do that? That might help to generate elliptic curve with a given order

That Sutherland paper is very complicated. I put it in there as a TODO but it's very unlikely I'll implement that in the near future. I also don't think it would be needed for the LMVV Anomalous Curves paper.

gunpal5 commented 1 year ago

There are several I was specifically trying with m = 0xfffffffffffffffffffffffffffffffebaaedce6af48a03bbfd25e8cd0364141

jvdsn commented 1 year ago

OK, so I understand the problem you're having. In your case, p = 115792089237316195423570985008687907852837564279074904382605163141518161494337.

Then 4p - 1 = 3^2 * 11 * 30977 * 31259 * 9303467 * 4726907109366362731 * 109867024074060467297173061989374797162123

So D = -51463150772140531299364882226083514601261139679588846392268961396230293997483.

The problem here is that D is way too big for our complex multiplication. Yes, the Sutherland paper might help here, but even then I don't know if the complex multiplication method with such a big D value would work.

I think this is going to stay an open issue. As mentioned, the Sutherland paper is way too complicated to implement anyway, especially in python.

gunpal5 commented 1 year ago

@jvdsn Thank you for looking into the issue. I think you are right it is very difficult to use that value of D to use in CM. Please feel free to close the issue.