jimmysong / programmingbitcoin

Repository for the book
Other
1.75k stars 656 forks source link

Checking for powers of zero and divide by zero corner cases in FieldElement class in ecc.py #287

Open salmonberry7 opened 3 weeks ago

salmonberry7 commented 3 weeks ago

In method __pow__ of class FieldElement an incorrect result of 1 is returned when 0 to the power k(p - 1) is calculated, where k is a non-zero integer (in the case of k = 0 the correct result of 1 is returned, since in field Fp, as in maths generally, zero to the power zero is normally taken to be 1 (eg. see Zero to the power of zero), and Python's built-in function pow computes pow(0, 0) as 1). This problem arises since n will come out as zero in this case and then num will be set to 1. The self.num == 0 case could be handled separately at the start of the function, with a ZeroDivisionError exception raised if exponent is any negative integer :

if self.num == 0 :
    if exponent < 0 :
        # original code returns 0 or 1 in this case
        raise ZeroDivisionError
    elif exponent == 0 :
        # original code works in this case
        return self.__class__(1, self.prime)
    else :
        # exponent > 0
        # original code returns 0 or 1 in this case
        return self.__class__(0, self.prime)

The code then works correctly as before for the case self.num != 0.

This bug does not affect the square root of zero in sqrt method of class S256Field when raising to power (p + 1)/4, since 0 < (p + 1)/4 < p - 1 for any odd prime p, and it does not affect taking the inverse in Fp by raising to power p - 2 in __truediv__. However __truediv__ should raise a ZeroDivisionError exception if the denominator is zero - currently it returns self.__class__(0, self.prime) in this case, without complaining.