Incorrect Zero-point handle
longnetwork opened this issue · 15 comments
point_addition(point_subtraction(P,P),P) - incorrect result
scalar_multiplication(0) - incorrect result
and so on
Thanks for the feedback. I tried to fix it in the updated version. Please see if i missed something.
I test with this code (not include loops, vectors, sequential methods)
import secp256k1 as btc
p = int('FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFE FFFFFC2F'.replace(' ',''),16)
n = int('FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFE BAAEDCE6 AF48A03B BFD25E8C D0364141'.replace(' ',''),16)
G = bytes.fromhex('04 79BE667E F9DCBBAC 55A06295 CE870B07 029BFCDB 2DCE28D9 59F2815B 16F81798 483ADA77 26A3C465 5DA4FBFC 0E1108A8 FD17B448 A6855419 9C47D08F FB10D4B8'.replace(' ',''))
Zero=b'\x04\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00'
if __name__ == '__main__':
print(btc.scalar_multiplication(n)==btc.scalar_multiplication(0))
print(btc.point_increment(Zero)==G)
print(btc.point_negation(Zero)==Zero)
print(btc.point_doubling(Zero)==Zero)
print(btc.point_addition(G,Zero)==G,btc.point_addition(Zero,G)==G)
print(btc.point_subtraction(G,G)==Zero)
print(btc.point_negation(btc.point_negation(G))==G)
print(btc.point_subtraction(G,Zero)==G, btc.point_subtraction(Zero,G)==btc.point_negation(G))
Last point_subtraction with Zerro argument is incorrect
in methods containing iteration by points, if the intermediate result is a zero point, then it must also be interpreted correctly, otherwise subsequent iterations will be incorrect
Thanks. I solved the bug. Now testing the looping functions for the Zeros.
I do not know the formula (algorithm) of operations
point_loop_addition, point_vector_addition, point_sequential_increment
I don't know what these operations should do (there are no such operations on eleptic curves)
I guessed that point_increment is P + G, but what is point_sequential_increment - I don't know
These functions are for easier and quicker use in a script. They are not exactly any ecdsa function.
For example...
Point_loop_addition is just like starting from a point P and incrementing +G continuously m times. So we get P+G, P+2G, P+3G...... All these are returned concatenated in 65bytes*m.
Same is the case with vector_addition but here two Point vectors are added together. Lets say 10points of 650bytes added with 10points of 650bytes to get added 650bytes.
Sequential is similar to loop_increment except some vector trick is used to make it faster. Although it is not yet working in very low range Privatekey Points.
In future, i might remove 1 of these two function. When 1 of them is stable enough for all cases.
Please update git
import secp256k1 as btc
p = int('FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFE FFFFFC2F'.replace(' ',''),16)
n = int('FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFE BAAEDCE6 AF48A03B BFD25E8C D0364141'.replace(' ',''),16)
G = bytes.fromhex('04 79BE667E F9DCBBAC 55A06295 CE870B07 029BFCDB 2DCE28D9 59F2815B 16F81798 483ADA77 26A3C465 5DA4FBFC 0E1108A8 FD17B448 A6855419 9C47D08F FB10D4B8'.replace(' ',''))
Zero=b'\x04\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00'
from random import random
def point_addition(P1,P2):
if P1==Zero: return P2
if P2==Zero: return P1
return btc.point_addition(P1,P2)
def point_doubling(P):
if P==Zero: return Zero
return btc.point_doubling(P)
def scalar_multiplication(k):
if k==0: return Zero
return btc.scalar_multiplication(k)
def point_multiplication(k, P):
def bits(k):
while k:
yield k & 1
k >>= 1
result = Zero
addend = P
for bit in bits(k):
if bit == 1: result=point_addition(result,addend)
addend=point_doubling(addend)
return result
if __name__ == '__main__':
P1=btc.scalar_multiplication(int(random()*n))
#P1=Zero
P2=btc.scalar_multiplication(int(random()*n))
#P2=btc.point_negation(P1)
#P2=Zero
n=10 # 0 1 2 3
seq=btc.point_loop_addition(n,P1,P2); # '', 'P1+P2', 'P1+P2''P1+2P2', 'P1+P2''P1+2P2''P1+3P2'...
points=[ seq[i*65:(i+1)*65] for i in range(0,len(seq)//65)]
for i in range(n):
print(point_addition(P1,point_multiplication(i+1,P2))==points[i])
point_loop_addition is valid only if the arguments and intermediate iterations are not equal to zero
Thanks. i found some more and fixed those passing from order-1 point to Zero. Updated these files on git.
checked point_loop_addition for interior points in sequence ( P2=btc.point_negation(btc.point_multiplication(pow(6,-1,n),P1)) )
Everything is good!
I can't guess the point_vector_addition algorithm
If this is the same as point_loop_addition, then it does not work correctly for any input data
Ok, I will check in few days.
Vector addition is add 2 arrays of Points of equal length. Say adding 1000 Points with another 1000 Points to receive the added 1000 Points.
#! /usr/bin/env python3
# -*- coding: utf-8 -*-
import secp256k1 as btc
p = int('FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFE FFFFFC2F'.replace(' ',''),16)
n = int('FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFE BAAEDCE6 AF48A03B BFD25E8C D0364141'.replace(' ',''),16)
G = bytes.fromhex('04 79BE667E F9DCBBAC 55A06295 CE870B07 029BFCDB 2DCE28D9 59F2815B 16F81798 483ADA77 26A3C465 5DA4FBFC 0E1108A8 FD17B448 A6855419 9C47D08F FB10D4B8'.replace(' ',''))
Zero=b'\x04\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00'
from random import random
if __name__ == '__main__':
k=6; zk=6; # Zero on zk-iteration in point_loop_addition
p1=btc.scalar_multiplication(int(random()*n)); _p1=btc.point_negation(btc.point_multiplication(pow(zk,-1,n),p1))
p2=btc.scalar_multiplication(int(random()*n)); _p2=btc.point_negation(btc.point_multiplication(pow(zk,-1,n),p2))
vec1=btc.point_loop_addition(k,p1,_p1); # 'P1', 'P1+P2', 'P1+P2''P1+2P2', 'P1+P2''P1+2P2''P1+3P2'...
vec2=btc.point_loop_addition(k,p2,_p2); # 'P1', 'P1+P2', 'P1+P2''P1+2P2', 'P1+P2''P1+2P2''P1+3P2'...
points1=[ vec1[i*65:(i+1)*65] for i in range(0,len(vec1)//65)]
points2=[ vec2[i*65:(i+1)*65] for i in range(0,len(vec2)//65)]
vec=btc.point_vector_addition(k,vec1,vec2)
points=[ vec[i*65:(i+1)*65] for i in range(0,len(vec)//65)]
for i in range(k):
print(i+1, btc.point_addition(points1[i],points2[i])==points[i])point_vector_addition is correct only until iterations are close to zero. If the sequence should form zero, then the whole sequence is initially considered wrong.
So in the example above, if k=5, all is good:
1 True
2 True
3 True
4 True
5 True
And if k=10, it's wrong:
1 False
2 False
3 False
4 False
5 False
6 True
7 False
8 False
9 False
10 False
The inputs are chosen so that at the 6th iteration there is 0.
I assume that the same optimizations are used for vector_addition as for sequential_increment, when approaching zero is forbidden (pvk>num). If so, the function works correctly. You only need to specify this nuance in the documentation
Yes currently the vector_addition and sequential_increment are using same optimizations and not able to handle Zero Point.
Wrote it in function document. maybe in future i will see if i can bypass this hurdle, but it is not a concern currently.
@longnetwork Thanks for your input. Zero Point handling added.
Vector and Sequential functions now check for Zero Point and fall back to another function if found.