mtbf/point.go

package main

import (
	_ "fmt"
)

type Point struct {
	curve *WCurve
	x, y  bigint
	order bigint
}

var InfinityPoint *Point = NewInfPoint()

func NewPoint(curve *WCurve, x, y, order bigint) *Point {
	point := Point{}
	point.x = x
	point.y = y
	point.order = order

	/*if curve != nil && !curve.containsPoint(x, y) {
	    panic("point is not on a curve")
	  }/*

	  /*if curve != nil && curve.h.NeInt(1) && !order.Empty() {
	    if point.Mul(order).Eq(InfinityPoint) {
	      panic("point is not a scalar multiple")
	    }
	  }*/

	return &point
}

func NewInfPoint() *Point {
	return NewPoint(nil, NewEmptyBigint(), NewEmptyBigint(), NewEmptyBigint())
}

func (self *Point) IsInf() bool {
	return self.curve == nil && self.x.Empty() && self.y.Empty()
}

func (self *Point) Eq(other *Point) bool {
	eqCurve := self.curve != nil && other.curve != nil && self.curve.Eq(other.curve)
	eqX := !self.x.Empty() && !other.x.Empty() && self.x.Eq(other.x)
	eqY := !self.y.Empty() && !other.y.Empty() && self.y.Eq(other.y)

	if self.IsInf() && other.IsInf() {
		return true
	}

	return eqCurve && eqX && eqY
}

func (self *Point) Neg() *Point {
	return NewPoint(self.curve, self.x, self.curve.p.Sub(self.y), NewEmptyBigint())
}

func (self *Point) Add(other *Point) *Point {
	if other.Eq(InfinityPoint) {
		return self
	}

	if self.Eq(InfinityPoint) {
		return other
	}

	if !self.curve.Eq(other.curve) {
		panic("cannot add points on different curves")
	}

	if self.x.Eq(other.x) {
		if self.y.Add(other.y).Mod(self.curve.p).EqInt(0) {
			return NewInfPoint()
		} else {
			return self.Double()
		}
	}

	p := self.curve.p
	im := modinv(other.x.Sub(self.x), p)
	l := other.y.Sub(self.y).Mul(im).Mod(p)

	x3 := l.Mul(l).Sub(self.x).Sub(other.x).Mod(p)
	y3 := l.Mul(self.x.Sub(x3)).Sub(self.y).Mod(p)

	return NewPoint(self.curve, x3, y3, NewEmptyBigint())
}

func (self *Point) Mul(other bigint) *Point {
	e := other

	if e.EqInt(0) || (!self.order.Empty() && e.Mod(self.order).EqInt(0)) {
		return NewInfPoint()
	}
	if self.Eq(InfinityPoint) {
		return NewInfPoint()
	}
	if e.LtInt(0) {
		return self.Neg().Mul(e.Neg())
	}

	e3 := e.MulInt(3)
	negativeSelf := NewPoint(self.curve, self.x, self.y.Neg(), self.order)
	i := leftmostBit(e3).DivInt(2)
	res := self

	for i.GtInt(1) {
		res = res.Double()
		if !e3.And(i).EqInt(0) && e.And(i).EqInt(0) {
			res = res.Add(self)
		}
		if e3.And(i).EqInt(0) && !e.And(i).EqInt(0) {
			res = res.Add(negativeSelf)
		}

		i = i.DivInt(2)
	}

	return res
}

func (self *Point) Double() *Point {
	if self.Eq(InfinityPoint) {
		return NewInfPoint()
	}

	p := self.curve.p
	a := self.curve.a

	im := modinv(self.y.MulInt(2), p)
	l := self.x.MulInt(3).Mul(self.x).Add(a).Mul(im).Mod(p)

	x3 := l.Mul(l).Sub(self.x.MulInt(2)).Mod(p)
	y3 := l.Mul(self.x.Sub(x3)).Sub(self.y).Mod(p)

	return NewPoint(self.curve, x3, y3, NewEmptyBigint())
}

type JacobiPoint struct {
	curve   *WCurve
	x, y, z bigint
	order   bigint
}

func NewJacobiPoint(curve *WCurve, x, y, z, order bigint) *JacobiPoint {
	// attempt to initialize normal point
	NewPoint(curve, x, y, order)

	point := JacobiPoint{}
	point.x = x
	point.y = y
	point.z = z
	point.curve = curve
	point.order = order
	return &point
}

func NewInfJacobiPoint() *JacobiPoint {
	return NewJacobiPoint(nil, NewEmptyBigint(), NewEmptyBigint(), NewEmptyBigint(), NewEmptyBigint())
}

func (self *JacobiPoint) IsInf() bool {
	return self.curve == nil && self.x.Empty() && self.y.Empty() && self.z.Empty()
}

func (self *JacobiPoint) EqCoords(x2, y2, z2 bigint) bool {
	x1 := self.x
	y1 := self.y
	z1 := self.z
	p := self.curve.p

	zz1 := z1.Mul(z1).Mod(p)
	zz2 := z2.Mul(z2).Mod(p)

	m1 := x1.Mul(zz2).Sub(x2.Mul(zz1)).Mod(p)
	m2 := y1.Mul(zz2).Mul(z2).Sub(y2.Mul(zz1).Mul(z1)).Mod(p)

	return m1.EqInt(0) && m2.EqInt(0)
}

func (self *JacobiPoint) EqPoint(other *Point) bool {
	if other.IsInf() {
		return self.y.Empty() || self.z.Empty()
	}
	if !self.curve.Eq(other.curve) {
		return false
	}

	return self.EqCoords(other.x, other.y, NewBigint(1))
}

func (self *JacobiPoint) Eq(other *JacobiPoint) bool {
	if other.IsInf() {
		return self.y.Empty() || self.z.Empty()
	}
	if !self.curve.Eq(other.curve) {
		return false
	}

	return self.EqCoords(other.x, other.y, other.z)
}

func (self *JacobiPoint) Neg() *JacobiPoint {
	return NewJacobiPoint(self.curve, self.x, self.y.Neg(), self.z, self.order)
}

func (self *JacobiPoint) AffineX() bigint {
	if self.z.EqInt(1) {
		return self.x
	}

	z := modinv(self.z, self.curve.p)
	return self.x.Mul(z.Mul(z)).Mod(self.curve.p)
}

func (self *JacobiPoint) AffineY() bigint {
	if self.z.EqInt(1) {
		return self.y
	}

	z := modinv(self.z, self.curve.p)
	return self.y.Mul(z.Mul(z).Mul(z)).Mod(self.curve.p)
}

// modifies in-place
func (self *JacobiPoint) Scale() *JacobiPoint {
	if self.z.EqInt(1) {
		return self
	}

	p := self.curve.p
	zInv := modinv(self.z, p)
	zzInv := zInv.Mul(zInv).Mod(p)

	x := self.x.Mul(zzInv).Mod(p)
	y := self.y.Mul(zzInv).Mul(zInv).Mod(p)

	self.x = x
	self.y = y
	self.z = NewBigint(1)
	return self
}

func (self *JacobiPoint) ToAffine() *Point {
	if self.y.Empty() || self.z.Empty() {
		return NewInfPoint()
	}

	self.Scale()
	return NewPoint(self.curve, self.x, self.y, self.order)
}

func (self *Point) FromAffine() *JacobiPoint {
	return NewJacobiPoint(self.curve, self.x, self.y, NewBigint(1), self.order)
}

func (self *JacobiPoint) _Double(x1, y1, z1, p, a bigint) (t, y3, z3 bigint) {
	if y1.Empty() || z1.Empty() {
		return NewBigint(0), NewBigint(0), NewBigint(1)
	}

	xx, yy := x1.Mul(x1).Mod(p), y1.Mul(y1).Mod(p)
	if yy.Empty() {
		return NewBigint(0), NewBigint(0), NewBigint(1)
	}

	yyyy := yy.Mul(yy).Mod(p)
	zz := z1.Mul(z1).Mod(p)

	s := NewBigint(2).Mul(x1.Add(yy).Mul(x1.Add(yy)).Sub(xx).Sub(yyyy)).Mod(p)
	m := NewBigint(3).Mul(xx).Add(a.Mul(zz).Mul(zz)).Mod(p)
	t = m.Mul(m).Sub(NewBigint(2).Mul(s)).Mod(p)
	y3 = m.Mul(s.Sub(t)).Sub(NewBigint(8).Mul(yyyy)).Mod(p)
	z3 = y1.Add(z1).Mul(y1.Add(z1)).Sub(yy).Sub(zz).Mod(p)

	return t, y3, z3
}

func (self *JacobiPoint) Double() *JacobiPoint {
	if self.y.Empty() {
		return NewInfJacobiPoint()
	}

	x3, y3, z3 := self._Double(self.x, self.y, self.z, self.curve.p, self.curve.a)
	if y3.Empty() || z3.Empty() {
		return NewInfJacobiPoint()
	}

	return NewJacobiPoint(self.curve, x3, y3, z3, self.order)
}

func (self *JacobiPoint) _Add(x1, y1, z1, x2, y2, z2, p bigint) (x3, y3, z3 bigint) {
	if y1.Empty() || z1.Empty() {
		return x2, y2, z2
	}
	if y2.Empty() || z2.Empty() {
		return x1, y1, z1
	}

	z1z1 := z1.Mul(z1).Mod(p)
	z2z2 := z2.Mul(z2).Mod(p)
	u1 := x1.Mul(z2z2).Mod(p)
	u2 := x2.Mul(z1z1).Mod(p)
	s1 := y1.Mul(z2).Mul(z2z2).Mod(p)
	s2 := y2.Mul(z1).Mul(z1z1).Mod(p)
	h := u2.Sub(u1)
	i := NewBigint(4).Mul(h).Mul(h).Mod(p)
	j := h.Mul(i).Mod(p)
	r := NewBigint(2).Mul(s2.Sub(s1)).Mod(p)

	if h.Empty() && r.Empty() {
		return self._Double(x1, y1, z1, p, self.curve.a)
	}

	v := u1.Mul(i)
	x3 = r.Mul(r).Sub(j).Sub(NewBigint(2).Mul(v)).Mod(p)
	y3 = r.Mul(v.Sub(x3)).Sub(NewBigint(2).Mul(s1).Mul(j)).Mod(p)
	z3 = z1.Add(z2).Mul(z1.Add(z2)).Sub(z1z1).Sub(z2z2).Mul(h).Mod(p)

	return x3, y3, z3
}

func (self *JacobiPoint) AddPoint(other *Point) *JacobiPoint {
	return self.Add(other.FromAffine())
}

func (self *JacobiPoint) Add(other *JacobiPoint) *JacobiPoint {
	if other.IsInf() {
		return self
	}

	if self.IsInf() {
		return other
	}

	if !self.curve.Eq(other.curve) {
		panic("cannot add with different curves")
	}

	x3, y3, z3 := self._Add(self.x, self.y, self.z, other.x, other.y, other.z, self.curve.p)
	if y3.Empty() || z3.Empty() {
		return NewInfJacobiPoint()
	}

	return NewJacobiPoint(self.curve, x3, y3, z3, self.order)
}

func (self *JacobiPoint) Mul(other bigint) *JacobiPoint {
	if self.y.Empty() || other.Empty() {
		return NewInfJacobiPoint()
	}
	if other.EqInt(1) {
		return self
	}
	if !self.order.Empty() {
		other = other.Mod(self.order.MulInt(2))
	}

	self = self.Scale()
	x2, y2 := self.x, self.y
	x3, y3, z3 := NewBigint(0), NewBigint(0), NewBigint(1)
	p, a := self.curve.p, self.curve.a

	nf := naf(other)

	for i := len(nf) - 1; i >= 0; i-- {
		x3, y3, z3 = self._Double(x3, y3, z3, p, a)
		if nf[i].LtInt(0) {
			x3, y3, z3 = self._Add(x3, y3, z3, x2, y2.Neg(), NewBigint(1), p)
		} else if nf[i].GtInt(0) {
			x3, y3, z3 = self._Add(x3, y3, z3, x2, y2, NewBigint(1), p)
		}
	}

	if y3.Empty() || z3.Empty() {
		return NewInfJacobiPoint()
	}

	return NewJacobiPoint(self.curve, x3, y3, z3, self.order)
}

func (self *JacobiPoint) MulAdd(selfMul bigint, other *JacobiPoint, otherMul bigint) *JacobiPoint {
	return self.Mul(selfMul).Add(other.Mul(otherMul))
}