curve/tools/curve.go

package tools

import (
	"context"
	"errors"
	"fmt"
	"math/big"

	"git.ali33.ru/fcg-xvii/go-tools/json"
)

var (
	MinP = big.NewInt(11)
)

// 4a³ + 27b² = 0 - проверка кривой на сингулярность
func NewCurve(a, b *big.Int) (*Curve, error) {
	c := &Curve{
		a: new(big.Int).Set(a),
		b: new(big.Int).Set(b),
	}
	return c, c.IsSingular()
}

type Curve struct {
	a *big.Int // константа a
	b *big.Int // константа b
	p *big.Int // размер конечного поля
	g *Point   // базовая точка подгруппы
	//n *big.Int // порядок подгруппы
	//h *big.Int // кофактор подгруппы
}

func (s *Curve) A() (res *big.Int) {
	return intCopy(s.a)
}

func (s *Curve) B() (res *big.Int) {
	return intCopy(s.b)
}

func (s *Curve) G() (res *Point) {
	if s.g != nil {
		res = s.g.Copy()
	}
	return
}

func (s *Curve) P() (res *big.Int) {
	if s.p != nil {
		res = intCopy(s.p)
	}
	return
}

// Проверка, установлен ли размер конечного поля
func (s *Curve) IsValidP() (err error) {
	if err = s.IsValidConstants(); err == nil {
		if s.p == nil {
			err = errors.New("размер конечного поля не установлен")
		}
	}
	return
}

func (s *Curve) IsValidG() (err error) {
	if err = s.IsValidP(); err == nil {
		if s.g == nil {
			err = errors.New("базовая точка подгруппы g не определена")
		}
	}
	return
}

// Возвращает строку уравнения кривой
func (s *Curve) FormulaString() string {
	return fmt.Sprintf(
		"y² = x³ + %sx + %s",
		mustBigInt(s.a),
		mustBigInt(s.b),
	)
}

// Проверка кривой на сингулярность (4a³ + 27b² = 0)
func (s *Curve) IsSingular() (err error) {
	if err = s.IsValidConstants(); err != nil {
		return
	}
	l := new(big.Int).Mul(new(big.Int).Exp(s.a, big.NewInt(3), nil), big.NewInt(4))
	r := new(big.Int).Mul(new(big.Int).Exp(s.b, big.NewInt(2), nil), big.NewInt(27))
	if l.Add(l, r).Cmp(big.NewInt(0)) == 0 {
		err = fmt.Errorf("кривая [ %s ] сингулярна и не рекомендуется к использованию", s.FormulaString())
	}
	return
}

// Проверка констант уравнения на валидность
func (s *Curve) IsValidConstants() error {
	if s.a == nil {
		return errors.New("константа [ a ] не определена")
	}
	if s.b == nil {
		return errors.New("константа [ b ] не определена")
	}
	return nil
}

// Установка размера конечного поля
func (s *Curve) SetP(p *big.Int) (err error) {
	if s.p != nil {
		return errors.New("резмер конечного поля уже определен")
	}
	if err = s.IsValidConstants(); err != nil {
		return
	}
	if !IsPrime(p) {
		err = fmt.Errorf("число [ %s ] не является простым. Размер конечного поля должен быть простым числом", p)
		return
	}
	s.p = p
	return
}

func (s *Curve) Point(x, y *big.Int) *Point {
	return NewPoint(x, y, s)
}

func (s *Curve) InverseMod(k, p *big.Int) (res *big.Int, err error) {
	if err = s.IsValidP(); err != nil {
		return
	}
	if k == nil {
		err = errors.New("[ k ] не определено")
		return
	} else if rk := k.Cmp(intZero); rk == 0 {
		err = errors.New("[ k ] == 0. Деление на 0 невозможно")
		return
	} else if rk < 0 {
		// k ** -1 = p - (-k) ** -1  (mod p)
		// point - self.inverseMod(-k, point)
		var iMod *big.Int
		if iMod, err = s.InverseMod(Neg(k), p); err == nil {
			res = Sub(p, iMod)
		}
	} else {
		s, olds := big.NewInt(0), big.NewInt(1)
		t, oldt := big.NewInt(1), big.NewInt(0)
		r, oldr := intCopy(p), intCopy(k)

		for r.Cmp(intZero) != 0 {
			quot := Div(oldr, r)
			oldr, r = r, Sub(oldr, Mul(quot, r))
			olds, s = s, Sub(olds, Mul(quot, s))
			oldt, t = t, Sub(oldt, Mul(quot, t))
		}
		// gcd, x, y = old_r, old_s, old_t
		res = Mod(olds, p)
	}
	return
}

func (s *Curve) Points(dx *big.Int) (p1, p2 *Point, err error) {
	if err = s.IsValidG(); err != nil {
		return
	}
	return s.points(dx)
}

// Определение координат пары зеркальных точек по x
func (s *Curve) points(dx *big.Int) (p1, p2 *Point, err error) {
	dxx := intCopy(dx)
	// Инициализируем результирующие точки пустыми
	p1, p2 = s.Point(nil, nil), s.Point(nil, nil)
	var dy *big.Int
	// Операции, обратной делению по модулю, не существует, поэтому
	// для определения координаты по y, необходимо, путем перебора с подстановкой y,
	// проверить равенство левой части уравнения, разделенного по модулю на p с
	// правой частью, так же разделенной по модулю на p
	for i := big.NewInt(0); i.Cmp(s.p) < 0; i.Add(i, big.NewInt(1)) {
		// i ** 2 % s.p == (dx ** 3 + s.a * dx + self.b) % self.p > 0
		l := Mod(Exp64(i, 2), s.p)
		r := Mod(
			Add(
				Exp64(dx, 3),
				Add(
					Mul(s.a, dx),
					s.b,
				),
			),
			s.p,
		)
		if l.Cmp(r) == 0 {
			dy = i
			break
		}
	}
	if dy == nil {
		err = fmt.Errorf("не удалось найти пару зеркальных точек на кривой после x [ %s ]", dxx)
	} else {
		p1.x, p1.y = dx, dy
		p2.x = intCopy(p1.x)
		p2.y = Mod(Neg(p1.y), s.p)
	}
	return
}

func (s *Curve) SearchClosePoints(x *big.Int, ctx context.Context) (p1, p2 *Point, err error) {
	if err = s.IsValidG(); err != nil {
		return
	}
	return s.searhClosePoints(x, ctx)
}

func (s *Curve) searhClosePoints(x *big.Int, ctx context.Context) (p1, p2 *Point, err error) {
	cx := intCopy(x)
	if x.Cmp(s.p) >= 0 {
		x = Sub(s.p, big.NewInt(1))
	} else if x.Cmp(intZero) < 0 {
		x = big.NewInt(0)
	}
	//kx := Sub64(x, 1)
	kx := intCopy(x)
	ch := make(chan struct{})
	go func() {
		defer close(ch)
		for {
			select {
			case <-ctx.Done():
				return
			default:
				//log.Println("xkx", x, kx)
				if x.Cmp(s.p) >= 0 && kx.Cmp(intZero) <= 0 {
					err = fmt.Errorf("не удалось найти точки, близкие к [ %s ]", cx)
					return
				} else {
					// Поиск вправо
					if x.Cmp(s.p) <= 0 {
						if p1, p2, err = s.points(x); err == nil {
							if p1.IsInCurve() == nil {
								return
							}
						}
						x = Add64(x, 1)
					}
					// Поиск влево
					if kx.Cmp(intZero) < 0 {
						if p1, p2, err = s.points(kx); err == nil {
							if p1.IsInCurve() == nil {
								return
							}
						}
						kx = Sub64(kx, 1)
					}
				}
			}
		}
	}()
	select {
	case <-ch:
	case <-ctx.Done():
		err = fmt.Errorf("Поиск точки, близкой к [ %v ] прерван - время вышло", x)
	}
	return
}

func (s *Curve) SetG(g *Point) (err error) {
	if s.g != nil {
		err = errors.New("базовая точка подгруппы g уже определена")
		return
	}
	if err = s.IsValidP(); err != nil {
		return
	}
	if err = g.IsInCurve(); err == nil && g.curve == s {
		s.g = g
	}
	return
}

func (s *Curve) SetGRandom(ctx context.Context) (err error) {
	if s.g != nil {
		err = errors.New("базовая точка подгруппы g уже определена")
		return
	}
	if err = s.IsValidP(); err != nil {
		return
	}
	x := Random(
		Div(s.p, big.NewInt(2)),
		Sub(s.p, big.NewInt(10)),
	)
	//log.Println(x)
	p1, p2, err := s.searhClosePoints(x, ctx)
	if err != nil {
		return
	}
	if err = p1.IsInCurve(); err == nil {
		s.g = p1
	} else if err = p2.IsInCurve(); err == nil {
		s.g = p2
	} else {
		err = errors.New("не удалось найти точку g, пренадлежащую кривой")
	}
	return
}

func (s *Curve) Map() json.Map {
	res := json.Map{
		"a": s.A(),
		"b": s.B(),
		"p": s.P(),
		"g": s.G(),
	}
	return res
}

/*
// Поиск порядка подгруппы
func (s *Curve) SetN() (err error) {
	if s.n != nil {
		return errors.New("порядок подгруппы уже определен")
	}
	if err = s.IsValidP(); err != nil {
		return
	}
	dx, dy := intCopy(s.g.x), Mod(Neg(s.g.y), s.p)
	tmpG := s.g.Copy()
	s.n = big.NewInt(1)
	for {
		s.n.Add(s.n, big.NewInt(1))
		if tmpG, err = tmpG.Add(s.g); err != nil {
			return
		}
		if tmpG.x.Cmp(dx) == 0 && tmpG.y.Cmp(dy) == 0 {
			s.n.Add(s.n, big.NewInt(1))
			return
		}
	}
}

func (s *Curve) KeyPub(priv *big.Int) (pub *Point, err error) {
	if err = s.IsValidN(); err != nil {
		return
	}
	pub, err = s.g.Mul(priv)
	return
}

func (s *Curve) RandomKeyPair() (priv *big.Int, pub *Point, err error) {
	if err = s.IsValidN(); err != nil {
		return
	}
	priv = Random(big.NewInt(1), Sub64(s.n, 1))
	pub, err = s.g.Mul(priv)
	return
}

// Вычисление общего секрета
func (s *Curve) PointSecret(mPriv *big.Int, fPub *Point) (res *Point, err error) {
	if err = s.IsValidN(); err != nil {
		return
	}
	res, err = fPub.Mul(mPriv)
	return
}

type ELKeyPriv struct {
	d *big.Int
}

type ELKeyPub struct {
	e1 *Point
	e2 *Point
}

type ELKeyPair struct {
	curve  *Curve
	priv   *ELKeyPriv
	pub    *ELKeyPub
	dTable map[byte]*Point
}

func (s *ELKeyPair) setupDataTable() error {
	if s.dTable != nil {
		return nil
	}
	s.dTable = make(map[byte]*Point)
	dx := big.NewInt(0)
	//var points []*Point
	//var p *Point
	for i := byte(0); i <= 254; i++ {
		p, _, err := s.curve.searhClosePoints(dx)
		if err != nil {
			return err
		}
		// check already exists - todo
		dx = Add64(p.x, 1)
		s.dTable[i] = p
		log.Println(i, p)
	}
	return nil
}

type ELMessage struct {
	c1 *Point
	cd []*Point
}

// c1 = r x e1
// c2 = P + r x e2
func (s *ELKeyPair) EncodeMessage(data []byte) (mes *ELMessage, err error) {
	r := Random(big.NewInt(1), Sub64(s.curve.p, 1))
	c1, err := s.pub.e1.Mul(r)
	if err != nil {
		return nil, err
	}
	mes = &ELMessage{
		c1: c1,
		cd: make([]*Point, len(data)),
	}
	for i, d := range data {
		p := s.dTable[d]
		c2, err := s.pub.e2.Mul(r)
		if err != nil {
			return nil, err
		}
		cd, err := p.Add(c2)
		if err != nil {
			return nil, err
		}
		mes.cd[i] = cd
	}
	return mes, nil
}

// p = c2 – (d x c1)
func (s *ELKeyPair) DecodeMessage(mes *ELMessage) ([]byte, error) {
	res := make([]byte, len(mes.cd))
	part, err := mes.c1.Mul(s.priv.d)
	if err != nil {
		return nil, err
	}
	part, _ = part.Neg()
	for _, c2 := range mes.cd {
		p, err := c2.Add(part)
		if err != nil {
			return nil, err
		}
		log.Println(p)
	}
	return res, nil
}

func (s *Curve) ELKeyPair() (*ELKeyPair, error) {
	e1, _, err := s.searhClosePoints(Random(big.NewInt(1), Sub64(s.p, 1)))
	if err != nil {
		return nil, err
	}
	d := Random(big.NewInt(1), Sub64(s.n, 1))
	e2, err := e1.Mul(d)
	if err != nil {
		return nil, err
	}
	res := &ELKeyPair{
		curve: s,
		priv: &ELKeyPriv{
			d: d,
		},
		pub: &ELKeyPub{
			e1: e1,
			e2: e2,
		},
	}
	return res, res.setupDataTable()
}
*/

/*
func (s *Curve) HEncode(b byte, pub *Point) (cm1, cm2 *Point, err error) {
	var p1 *Point
	if p1, _, err = s.points(big.NewInt(int64(b))); err != nil {
		return
	}
	c1 = pub.Add()
}
*/

/*
// 𝐶𝑚 = (𝑘 × 𝐺, 𝑃𝑚 + 𝑘 × 𝑃𝐵)
func (s *Curve) HellmanEncode(b byte, pub *Point) (cm1, cm2 *Point, err error) {
	k := Random(big.NewInt(1), Sub64(s.n, 1))
	if cm1, err = s.g.Mul(k); err != nil {
		return
	}
	cm2, err = pub.Mul(Add64(k, int64(b)))
	return
}
*/

/*
func (s *Curve) HellmanDecode(cm1, cm2 *Point, priv *big.Int) {

}
*/