Peter Montgomery created the Montgomery ladder [1], and which computes a point multiplication (\(kG\)) within a fixed amount of time. This means that it is immune from timing and power attacks. The Montgomery Ladder thus determines \(kG\), and where \(G\) is a base point, and \(k\) is a scalar value.
Montgomery Ladder |
Background
Peter Montgomery created the Montgomery ladder [1], and which computes a point multiplication (\(kG\)) within a fixed amount of time. This means that it is immune from timing and power attacks. The method uses a double-and-add approach apart from where it uses the same number of point additions and doubles regardless of the value of \(k\). Basically, to determine \(kP\), we use the representation of:
\(k =k_{0}+2k_{1}+2^{2}k_{2}+\cdots +2^{m}k_{m} \)
where \(k_{0}~..~k_{m}\in \{0,1\},m=\lfloor \log _{2}{k}\rfloor\)
The core algorithm is:
R0 <- 0 R1 <- P for i from m downto 0 do if ki = 0 then R1 <- point_add(R0, R1) R0 <- point_double(R0) else R0 <- point_add(R0, R1) R1 <- point_double(R1) return R0
The base point (G) for secp256k1 is: (79BE667EF9DCBBAC55A06295CE870B07029BFCDB2DCE28D959F2815B16F81798, 483ADA7726A3C4655DA4FBFC0E1108A8FD17B448A68554199C47D08FFB10D4B8) and the prime number is FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEFFFFFC2F (\(2^{256} - 2^{32} - 2^9 - 2^8 - 2^7 - 2^6 - 2^4 - 1\)) and the curve is \(y^2 = x^3 + 7\).
A sample run is:
G = {55066263022277343669578718895168534326250603453777594175500187360389116729240 32670510020758816978083085130507043184471273380659243275938904335757337482424} k = 1 kG = {55066263022277343669578718895168534326250603453777594175500187360389116729240 32670510020758816978083085130507043184471273380659243275938904335757337482424} We cannot get a curve above above FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEBAAEDCE6AF48A03BBFD25E8CD0364141 (N). Let's check:Point at x=N: G = {} Point at x=(N-1): G = {55066263022277343669578718895168534326250603453777594175500187360389116729240 83121579216557378445487899878180864668798711284981320763518679672151497189239}
Code
The following is the Montgomery Ladder method [here]:
// ScalarMult computes Q = k * P on EllipticCurve ec. func (ec *EllipticCurve) ScalarMult(k *big.Int, P Point) (Q Point) { /* Note: this function is not constant time, due to the branching nature of * the underlying point Add() function. */ /* Montgomery Ladder Point Multiplication * * Implementation based on pseudocode here: * See https://en.wikipedia.org/wiki/Elliptic_curve_point_multiplication#Montgomery_ladder */ var R0 Point var R1 Point R0.X = nil R0.Y = nil R1.X = new(big.Int).Set(P.X) R1.Y = new(big.Int).Set(P.Y) for i := ec.N.BitLen() - 1; i >= 0; i-- { if k.Bit(i) == 0 { R1 = ec.Add(R0, R1) R0 = ec.Add(R0, R0) } else { R0 = ec.Add(R0, R1) R1 = ec.Add(R1, R1) } } return R0 }
The following code is based on this code [here]:
// https://asecuritysite.com/encryption/go_bitcoin package main import ( "encoding/hex" "errors" "fmt" "math/big" "os" ) // Code from https://github.com/vsergeev/btckeygenie/blob/master/btckey/elliptic_test.go // Point represents a point on an EllipticCurve. type Point struct { X *big.Int Y *big.Int } /* y**2 = x**3 + a*x + b % p */ // EllipticCurve represents the parameters of a short Weierstrass equation elliptic curve. type EllipticCurve struct { A *big.Int B *big.Int P *big.Int G Point N *big.Int H *big.Int } // format formats the bytes of a point for debugging. func (p *Point) format() string { if p.X == nil && p.Y == nil { return "(inf,inf)" } return fmt.Sprintf("(%s,%s)", hex.EncodeToString(p.X.Bytes()), hex.EncodeToString(p.Y.Bytes())) } /*** Modular Arithmetic ***/ /* NOTE: Returning a new z each time below is very space inefficient, but the * alternate accumulator based design makes the point arithmetic functions look * absolutely hideous. I may still change this in the future. */ // addMod computes z = (x + y) % p. func addMod(x *big.Int, y *big.Int, p *big.Int) (z *big.Int) { z = new(big.Int).Add(x, y) z.Mod(z, p) return z } // subMod computes z = (x - y) % p. func subMod(x *big.Int, y *big.Int, p *big.Int) (z *big.Int) { z = new(big.Int).Sub(x, y) z.Mod(z, p) return z } // mulMod computes z = (x * y) % p. func mulMod(x *big.Int, y *big.Int, p *big.Int) (z *big.Int) { n := new(big.Int).Set(x) z = big.NewInt(0) for i := 0; i < y.BitLen(); i++ { if y.Bit(i) == 1 { z = addMod(z, n, p) } n = addMod(n, n, p) } return z } // invMod computes z = (1/x) % p. func invMod(x *big.Int, p *big.Int) (z *big.Int) { z = new(big.Int).ModInverse(x, p) return z } // expMod computes z = (x^e) % p. func expMod(x *big.Int, y *big.Int, p *big.Int) (z *big.Int) { z = new(big.Int).Exp(x, y, p) return z } // sqrtMod computes z = sqrt(x) % p. func sqrtMod(x *big.Int, p *big.Int) (z *big.Int) { /* assert that p % 4 == 3 */ if new(big.Int).Mod(p, big.NewInt(4)).Cmp(big.NewInt(3)) != 0 { panic("p is not equal to 3 mod 4!") } /* z = sqrt(x) % p = x^((p+1)/4) % p */ /* e = (p+1)/4 */ e := new(big.Int).Add(p, big.NewInt(1)) e = e.Rsh(e, 2) z = expMod(x, e, p) return z } /*** Point Arithmetic on Curve ***/ // IsInfinity checks if point P is infinity on EllipticCurve ec. func (ec *EllipticCurve) IsInfinity(P Point) bool { /* We use (nil,nil) to represent O, the point at infinity. */ if P.X == nil && P.Y == nil { return true } return false } // IsOnCurve checks if point P is on EllipticCurve ec. func (ec *EllipticCurve) IsOnCurve(P Point) bool { if ec.IsInfinity(P) { return false } /* y**2 = x**3 + a*x + b % p */ lhs := mulMod(P.Y, P.Y, ec.P) rhs := addMod( addMod( expMod(P.X, big.NewInt(3), ec.P), mulMod(ec.A, P.X, ec.P), ec.P), ec.B, ec.P) if lhs.Cmp(rhs) == 0 { return true } return false } // Add computes R = P + Q on EllipticCurve ec. func (ec *EllipticCurve) Add(P, Q Point) (R Point) { /* See rules 1-5 on SEC1 pg.7 http://www.secg.org/collateral/sec1_final.pdf */ if ec.IsInfinity(P) && ec.IsInfinity(Q) { /* Rule #1 Identity */ /* R = O + O = O */ R.X = nil R.Y = nil } else if ec.IsInfinity(P) { /* Rule #2 Identity */ /* R = O + Q = Q */ R.X = new(big.Int).Set(Q.X) R.Y = new(big.Int).Set(Q.Y) } else if ec.IsInfinity(Q) { /* Rule #2 Identity */ /* R = P + O = P */ R.X = new(big.Int).Set(P.X) R.Y = new(big.Int).Set(P.Y) } else if P.X.Cmp(Q.X) == 0 && addMod(P.Y, Q.Y, ec.P).Sign() == 0 { /* Rule #3 Identity */ /* R = (x,y) + (x,-y) = O */ R.X = nil R.Y = nil } else if P.X.Cmp(Q.X) == 0 && P.Y.Cmp(Q.Y) == 0 && P.Y.Sign() != 0 { /* Rule #5 Point doubling */ /* R = P + P */ /* Lambda = (3*P.X*P.X + a) / (2*P.Y) */ num := addMod( mulMod(big.NewInt(3), mulMod(P.X, P.X, ec.P), ec.P), ec.A, ec.P) den := invMod(mulMod(big.NewInt(2), P.Y, ec.P), ec.P) lambda := mulMod(num, den, ec.P) /* R.X = lambda*lambda - 2*P.X */ R.X = subMod( mulMod(lambda, lambda, ec.P), mulMod(big.NewInt(2), P.X, ec.P), ec.P) /* R.Y = lambda*(P.X - R.X) - P.Y */ R.Y = subMod( mulMod(lambda, subMod(P.X, R.X, ec.P), ec.P), P.Y, ec.P) } else if P.X.Cmp(Q.X) != 0 { /* Rule #4 Point addition */ /* R = P + Q */ /* Lambda = (Q.Y - P.Y) / (Q.X - P.X) */ num := subMod(Q.Y, P.Y, ec.P) den := invMod(subMod(Q.X, P.X, ec.P), ec.P) lambda := mulMod(num, den, ec.P) /* R.X = lambda*lambda - P.X - Q.X */ R.X = subMod( subMod( mulMod(lambda, lambda, ec.P), P.X, ec.P), Q.X, ec.P) /* R.Y = lambda*(P.X - R.X) - P.Y */ R.Y = subMod( mulMod(lambda, subMod(P.X, R.X, ec.P), ec.P), P.Y, ec.P) } else { panic(fmt.Sprintf("Unsupported point addition: %v + %v", P.format(), Q.format())) } return R } // ScalarMult computes Q = k * P on EllipticCurve ec. func (ec *EllipticCurve) ScalarMult(k *big.Int, P Point) (Q Point) { /* Note: this function is not constant time, due to the branching nature of * the underlying point Add() function. */ /* Montgomery Ladder Point Multiplication * * Implementation based on pseudocode here: * See https://en.wikipedia.org/wiki/Elliptic_curve_point_multiplication#Montgomery_ladder */ var R0 Point var R1 Point R0.X = nil R0.Y = nil R1.X = new(big.Int).Set(P.X) R1.Y = new(big.Int).Set(P.Y) for i := ec.N.BitLen() - 1; i >= 0; i-- { if k.Bit(i) == 0 { R1 = ec.Add(R0, R1) R0 = ec.Add(R0, R0) } else { R0 = ec.Add(R0, R1) R1 = ec.Add(R1, R1) } } return R0 } // ScalarBaseMult computes Q = k * G on EllipticCurve ec. func (ec *EllipticCurve) ScalarBaseMult(k *big.Int) (Q Point) { return ec.ScalarMult(k, ec.G) } // Decompress decompresses coordinate x and ylsb (y's least significant bit) into a Point P on EllipticCurve ec. func (ec *EllipticCurve) Decompress(x *big.Int, ylsb uint) (P Point, err error) { /* y**2 = x**3 + a*x + b % p */ rhs := addMod( addMod( expMod(x, big.NewInt(3), ec.P), mulMod(ec.A, x, ec.P), ec.P), ec.B, ec.P) /* y = sqrt(rhs) % p */ y := sqrtMod(rhs, ec.P) /* Use -y if opposite lsb is required */ if y.Bit(0) != (ylsb & 0x1) { y = subMod(big.NewInt(0), y, ec.P) } P.X = x P.Y = y if !ec.IsOnCurve(P) { return P, errors.New("Compressed (x, ylsb) not on curve.") } return P, nil } func dec2int(decstring string) (v *big.Int) { v, _ = new(big.Int).SetString(decstring, 10) return v } func hex2int(hexstring string) (v *big.Int) { v, _ = new(big.Int).SetString(hexstring, 16) return v } var curve EllipticCurve func main() { argCount := len(os.Args[1:]) k := "1" if argCount > 0 { k = (os.Args[1]) } /* secp256k1 elliptic curve parameters */ curve.P, _ = new(big.Int).SetString("FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEFFFFFC2F", 16) curve.A, _ = new(big.Int).SetString("0000000000000000000000000000000000000000000000000000000000000000", 16) curve.B, _ = new(big.Int).SetString("0000000000000000000000000000000000000000000000000000000000000007", 16) curve.G.X, _ = new(big.Int).SetString("79BE667EF9DCBBAC55A06295CE870B07029BFCDB2DCE28D959F2815B16F81798", 16) curve.G.Y, _ = new(big.Int).SetString("483ADA7726A3C4655DA4FBFC0E1108A8FD17B448A68554199C47D08FFB10D4B8", 16) curve.N, _ = new(big.Int).SetString("FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEBAAEDCE6AF48A03BBFD25E8CD0364141", 16) curve.H, _ = new(big.Int).SetString("01", 16) Q := curve.ScalarMult(dec2int(k), curve.G) fmt.Println("G = ", curve.G) fmt.Println("\nk = ", k) fmt.Println("\nkG = ", Q) fmt.Printf("\nWe cannot get a curve above above FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEBAAEDCE6AF48A03BBFD25E8CD0364141 (N).\nLet's check:") fmt.Println("Point at x=N:") Q = curve.ScalarMult(curve.N, curve.G) fmt.Println("\nG = ", Q) fmt.Println("\nPoint at x=(N-1):") a := big.NewInt(1) c := big.NewInt(0).Sub(curve.N, a) Q = curve.ScalarMult(c, curve.G) fmt.Println("\nG = ", Q) }
References
[1] Montgomery, Peter L. (1987). "Speeding the Pollard and elliptic curve methods of factorization". Math. Comp. 48 (177): 243–264. doi:10.2307/2007888.