ECC Double-and-add for point multiplication |
Theory
The basic method for \(d_i\) as the bit at position \(i\):
N ← P Q ← 0 for i from 0 to m do if di = 1 then Q ← point_add(Q, N) N ← point_double(N) return Q
For \(a=100\) we have a binary value of \(1100100\):
- 1100100, thus we double the point \((N=2G)\).
- 1100100, thus we double the point \((N=4G)\).
- 1100100, thus we add the point \((Q=4G)\), and then double the point \((N=8G)\).
- 1100100, thus we double the point \((N=16G)\).
- 1100100, thus we double the point \((N=32G)\).
- 1100100, thus we add the point \((Q=4G+32G=36G)\), and then double the point (\(N=64G)\).
- 1100100, thus we add the point \((Q=36G+64G=100G)\), and then double the point \((N=128G)\).
The result is then \(Q=4G+32G+64G=100G\).
Coding
import sys from secp256k1 import curve,is_on_curve,point_neg,point_add def scalar_mult(k, point): """Returns k * point computed using the double and point_add algorithm.""" assert is_on_curve(point) if k % curve.n == 0 or point is None: return None if k <0: # k * point = -k * (-point) return scalar_mult(-k, point_neg(point)) result = None addend = point while k: bit=k&1 print (f"Bit={bit}",end=' ') if k & 1: # Add. result = point_add(result, addend) print ("Point add",end=' ') # Double. addend = point_add(addend, addend) print ("Point double") k >>= 1 assert is_on_curve(result) return result a=10 if (len(sys.argv)>1): a=int(sys.argv[1]) print (f"Calculation = {a}G") print ("a:",bin(a)) A= scalar_mult(a,curve.g) print (f"Point = {A}")
A sample run for the base point is:
Calculation = 1G a: 0b1 Bit=1 Point add Point double Point = (55066263022277343669578718895168534326250603453777594175500187360389116729240, 32670510020758816978083085130507043184471273380659243275938904335757337482424)
For \(a=100\):
Calculation = 100G a: 0b1100100 Bit=0 Point double Bit=0 Point double Bit=1 Point add Point double Bit=0 Point double Bit=0 Point double Bit=1 Point add Point double Bit=1 Point add Point double Point = (107303582290733097924842193972465022053148211775194373671539518313500194639752, 103795966108782717446806684023742168462365449272639790795591544606836007446638)
and for \(a=1000\):
Calculation = 1000G a: 0b1111101000 Bit=0 Point double Bit=0 Point double Bit=0 Point double Bit=1 Point add Point double Bit=0 Point double Bit=1 Point add Point double Bit=1 Point add Point double Bit=1 Point add Point double Bit=1 Point add Point double Bit=1 Point add Point double Point = (33614996735103061868086131503312627786077049888376966084542785773152043381677, 84557594361191031609962062080128931200952163654712344162477769532776951195137)