programmingbitcoin icon indicating copy to clipboard operation
programmingbitcoin copied to clipboard

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

Open salmonberry7 opened this issue 1 year ago • 0 comments

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__ - since the troublesome power k(p - 1) described above does not arise in these cases. 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.

salmonberry7 avatar Oct 30 '24 20:10 salmonberry7