search

OnedgeLee / simple-py-crypto

Simple toy implementation of crypto written in python
0 stars 0 forks source link

Elliptic curve point multiplication takes too long time #4

Open OnedgeLee opened 2 years ago

OnedgeLee commented 2 years ago

Current method for elliptic curve multiplication is done by iteration with elliptic curve point adding. Since modulo p = 115792089237316195423570985008687907853269984665640564039457584007908834671663, private key d can be up to almost 10^77 (since 1 <= d <= p-1) Multiplier is same as k on ECDSA, so it means iteration number can be up to almost 10^77.

There can be two kind of approach to resolve it.

  1. Understanding on elliptic curve would be help : May be, elliptic curve multiplication can form some cyclic behavior or converge to some point after some numbers of iterations. If so, total iteration to applied will be dramatically decreased.
  2. There are some algorithms to decrease the total number of iterations, dividing some operations : I've found some algorithms on wiki, and it would be help.
OnedgeLee commented 2 years ago

Not directly related to this issue, but as information, Modulo p = 115792089237316195423570985008687907853269984665640564039457584007908834671663 2 ^ 256 = 115792089237316195423570985008687907853269984665640564039457584007913129639936 So, p = 2^256 - 4294968273. So, 256 bit can cover private key of ECDSA.

OnedgeLee commented 2 years ago

This paper(Speed Optimizations in Bitcoin Key Recovery Attacks) would be help