Fix Overflow Error

[GoodiesHQ]

Hello,

Using the curve "secp521k1", I was running into seemingly random instances of an OverflowError when encoding/decoding the points. For troubleshooting, I went into ecpy/curves.py and modified the encode_point to print out the calculated size (self.size >> 3) and the ACTUAL size, in bits, of the X and Y coordinates of the point. I noticed that sometimes it was too small.

Reproduce:

>>> import random
>>> from ecpy.curves import Curve
>>>
>>> curve = Curve.get_curve("secp521r1")
>>> p = 7777777 * curve.generator
>>> curve.encode_point(p)
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
  File "C:\Users\Austin Archer\AppData\Roaming\Python\Python38\site-packages\ecpy\curves.py", line 360, in encode_point
    x = bytearray(P.x.to_bytes(size,'big'))
OverflowError: int too big to convert

What I discovered was that around 50% of the time, the value self.size >> 3 is insufficient by one byte. In order to remedy this, the proper size of the numbers should be calculated by using ceil(self.size / 8), or a slightly faster method such as size = self.size >> 3 + bool(self.size % 8) which will result in the proper bit sizes each time.

This is an issue because the bit size of secp521k1 is 521, and 521 >> 3 is equal to 65, but 66 is often required.

[GoodiesHQ]

I actually got some surprising results from a few methods... picked the fastest.

Note: Pretty sure % 8 is implemented as & 7 within Python because I got no appreciable difference between the two, and % 8 is simply more readable.

>>> from timeit import timeit
>>> count = 10**7
>>> 
>>> # METHOD 1:
>>> timeit("ceil(521 / 8)", setup="from math import ceil", number=count)
2.355680199999995

>>> # METHOD 2
>>> timeit("(521 >> 3) + bool(521 % 8)", number=count)
2.0705702999999858

>>> # METHOD 3
>>> timeit("(521 >> 3) + (1 if 521 % 8 else 0)", number=count)
0.6898246000000086

[cslashm]

Thanks for reporting, Indeed 521 bit leads to 65.125 bytes :)

I think (self.size+7)>>3 will do the job in the fastest way. Can you update your PR if I'm right?

[GoodiesHQ]

Thanks for the response! These two methods show little to no difference between execution speeds:

>>> from timeit import timeit
>>> count = 10**7
>>> timeit("(521 >> 3) + (not not 521 % 8)", number=count)
0.13011330000063026
>>> timeit("((521+7) >> 3)", number=count)
0.11733189999995375
>>> timeit("(521+7 >> 3)", number=count)
0.10996770000019751

however will say that your method is a bit more readable so I will go ahead and add that to the PR!

For fun:

>>> from dis import dis
>>> dis("x >> 3")
  1           0 LOAD_NAME                0 (x)
              2 LOAD_CONST               0 (3)
              4 BINARY_RSHIFT
              6 RETURN_VALUE
>>> dis("x >> 3 + (not not x & 7)")
  1           0 LOAD_NAME                0 (x)
              2 LOAD_CONST               0 (3)
              4 LOAD_NAME                0 (x)
              6 LOAD_CONST               1 (7)
              8 BINARY_AND
             10 UNARY_NOT
             12 UNARY_NOT
             14 BINARY_ADD
             16 BINARY_RSHIFT
             18 RETURN_VALUE
>>> dis("x+7 >> 3")
  1           0 LOAD_NAME                0 (x)
              2 LOAD_CONST               0 (7)
              4 BINARY_ADD
              6 LOAD_CONST               1 (3)
              8 BINARY_RSHIFT
             10 RETURN_VALUE