shithub: libdp9ik

ref: 7e77582b6904979700dde6b0cba53f2d91e2b28d

View raw version
package libdp9ik

import (
	"math/big"
)

func modmul(b1 *big.Int, b2 *big.Int, m *big.Int, r *big.Int) {
	r.Mul(b1, b2)
	r.Mod(r, m)
}

func modadd(b1 *big.Int, b2 *big.Int, m *big.Int, r *big.Int) {
	r.Add(b1, b2)
	r.Mod(r, m)
}

func modsub(b1 *big.Int, b2 *big.Int, m *big.Int, r *big.Int) {
	r.Sub(b1, b2)
	r.Mod(r, m)
}

func misqrt(a *big.Int, p *big.Int, r *big.Int) {
	e := big.NewInt(0)
	tmp1 := big.NewInt(4)
	tmp1.Mod(p, tmp1)
	tmp2 := big.NewInt(3)
	if tmp1.Cmp(tmp2) == 0 {
		e.SetUint64(3)
		e.Sub(p, e)
		e.Rsh(e, 2)
		r.Exp(a, e, p)
	} else {
		r.ModSqrt(a, p)
		if r.Cmp(big.NewInt(0)) != 0 {
			r.ModInverse(r, p)
		}
	}
}

//Probably not safe from timing attacks
func elligator2(p *big.Int, a *big.Int, d *big.Int, n *big.Int, r0 *big.Int, X *big.Int, Y *big.Int, Z *big.Int, T *big.Int) {
	t := big.NewInt(0)
	s := big.NewInt(0)
	e := big.NewInt(0)
	c := big.NewInt(0)
	ND := big.NewInt(0)
	N := big.NewInt(0)
	D := big.NewInt(0)
	r := big.NewInt(0)
	tmp1 := big.NewInt(0)

	modmul(n, r0, p, tmp1)
	modmul(tmp1, r0, p, r)
	tmp1.SetInt64(0)
	modmul(d, r, p, tmp1)
	modadd(tmp1, a, p, tmp1)
	modsub(tmp1, d, p, tmp1)
	tmp2 := big.NewInt(0)
	modmul(d, r, p, tmp2)
	tmp3 := big.NewInt(0)
	modmul(a, r, p, tmp3)
	modsub(tmp2, tmp3, p, tmp2)
	modsub(tmp2, d, p, tmp2)
	modmul(tmp1, tmp2, p, D)
	tmp2.SetInt64(0)
	modadd(r, big.NewInt(1), p, tmp2)
	tmp1.SetInt64(0)
	modadd(d, d, p, tmp1)
	modsub(a, tmp1, p, tmp1)
	modmul(tmp2, tmp1, p, N)
	modmul(N, D, p, ND)
	if ND.Cmp(big.NewInt(0)) == 0 {
		c.SetInt64(1)
		e.SetInt64(0)
	} else {
		e.ModSqrt(ND, p)
		if e.Cmp(big.NewInt(0)) != 0 {
			c.SetInt64(1)
			e.ModInverse(e, p)
		} else {
			modsub(big.NewInt(0), big.NewInt(1), p, c)
			tmp4 := big.NewInt(0)
			modmul(n, r0, p, tmp4)
			tmp5 := big.NewInt(0)
			tmp6 := big.NewInt(0)
			modmul(n, ND, p, tmp6)
			misqrt(tmp6, p, tmp5)
			modmul(tmp4, tmp5, p, e)
		}
	}
	tmp1.SetInt64(0)
	modmul(c, N, p, tmp1)
	modmul(tmp1, e, p, s)
	tmp1.SetInt64(0)
	tmp2.SetInt64(0)
	modmul(c, N, p, tmp2)
	tmp3.SetInt64(0)
	modsub(r, big.NewInt(1), p, tmp3)
	modmul(tmp2, tmp3, p, tmp1)
	tmp3.SetInt64(0)
	tmp2.SetInt64(0)
	modadd(d, d, p, tmp2)
	modsub(a, tmp2, p, tmp2)
	modmul(tmp2, e, p, tmp3)
	modmul(tmp3, tmp3, p, tmp3)
	modmul(tmp1, tmp3, p, t)
	modsub(big.NewInt(0), t, p, t)
	modsub(t, big.NewInt(1), p, t)
	tmp3.SetInt64(0)
	modadd(s, s, p, tmp3)
	modmul(tmp3, t, p, X)
	tmp3.SetInt64(0)
	tmp1.SetInt64(0)
	modmul(a, s, p, tmp1)
	modmul(tmp1, s, p, tmp3)
	modsub(big.NewInt(1), tmp3, p, tmp3)
	tmp1.SetInt64(0)
	tmp2.SetInt64(0)
	modmul(a, s, p, tmp2)
	modmul(tmp2, s, p, tmp1)
	modadd(big.NewInt(1), tmp1, p, tmp1)
	modmul(tmp3, tmp1, p, Y)
	tmp1.SetInt64(0)
	tmp3.SetInt64(0)
	modmul(a, s, p, tmp3)
	modmul(tmp3, s, p, tmp1)
	modadd(big.NewInt(1), tmp1, p, tmp1)
	modmul(tmp1, t, p, Z)
	tmp1.SetInt64(0)
	modadd(s, s, p, tmp1)
	tmp3.SetInt64(0)
	tmp2.SetInt64(0)
	modmul(a, s, p, tmp2)
	modmul(tmp2, s, p, tmp3)
	modsub(big.NewInt(1), tmp3, p, tmp3)
	modmul(tmp1, tmp3, p, T)
}