mirror of
https://github.com/arnaucube/go-iden3-crypto.git
synced 2026-02-07 11:36:41 +01:00
Compare commits
1 Commits
feature/go
...
feature/bb
| Author | SHA1 | Date | |
|---|---|---|---|
|
8a260d66d3 |
@@ -4,12 +4,5 @@ language: go
|
||||
go:
|
||||
- "1.12"
|
||||
|
||||
jobs:
|
||||
include:
|
||||
- name: "Unit Tests 64 bit arch"
|
||||
env: GOARCH="amd64"
|
||||
- name: "Unit Test 32 bit arch"
|
||||
env: GOARCH="386"
|
||||
|
||||
env:
|
||||
- GO111MODULE=on
|
||||
|
||||
@@ -5,14 +5,15 @@ import (
|
||||
"math/big"
|
||||
|
||||
"github.com/iden3/go-iden3-crypto/constants"
|
||||
"github.com/iden3/go-iden3-crypto/ff"
|
||||
"github.com/iden3/go-iden3-crypto/utils"
|
||||
)
|
||||
|
||||
// A is one of the babyjub constants.
|
||||
var A *big.Int
|
||||
var A *ff.Element
|
||||
|
||||
// D is one of the babyjub constants.
|
||||
var D *big.Int
|
||||
var D *ff.Element
|
||||
|
||||
// Order of the babyjub curve.
|
||||
var Order *big.Int
|
||||
@@ -27,29 +28,52 @@ var B8 *Point
|
||||
|
||||
// init initializes global numbers and the subgroup base.
|
||||
func init() {
|
||||
A = utils.NewIntFromString("168700")
|
||||
D = utils.NewIntFromString("168696")
|
||||
A = ff.NewElement().SetString("168700")
|
||||
D = ff.NewElement().SetString("168696")
|
||||
|
||||
Order = utils.NewIntFromString(
|
||||
"21888242871839275222246405745257275088614511777268538073601725287587578984328")
|
||||
SubOrder = new(big.Int).Rsh(Order, 3)
|
||||
|
||||
B8 = NewPoint()
|
||||
B8.X = utils.NewIntFromString(
|
||||
B8.X = ff.NewElement().SetString(
|
||||
"5299619240641551281634865583518297030282874472190772894086521144482721001553")
|
||||
B8.Y = utils.NewIntFromString(
|
||||
B8.Y = ff.NewElement().SetString(
|
||||
"16950150798460657717958625567821834550301663161624707787222815936182638968203")
|
||||
}
|
||||
|
||||
// Point represents a point of the babyjub curve.
|
||||
type Point struct {
|
||||
// PointBI represents a point of the babyjub curve.
|
||||
type PointBI struct {
|
||||
X *big.Int
|
||||
Y *big.Int
|
||||
}
|
||||
|
||||
// NewPoint creates a new Point.
|
||||
type Point struct {
|
||||
X *ff.Element
|
||||
Y *ff.Element
|
||||
}
|
||||
|
||||
func PointBIToPoint(p *PointBI) *Point {
|
||||
return &Point{
|
||||
X: ff.NewElement().SetBigInt(p.X),
|
||||
Y: ff.NewElement().SetBigInt(p.Y),
|
||||
}
|
||||
}
|
||||
|
||||
func PointToPointBI(p *Point) *PointBI {
|
||||
return &PointBI{
|
||||
X: p.X.BigInt(),
|
||||
Y: p.Y.BigInt(),
|
||||
}
|
||||
}
|
||||
|
||||
// NewPoint creates a new PointBI.
|
||||
func NewPointBI() *PointBI {
|
||||
return &PointBI{X: big.NewInt(0), Y: big.NewInt(1)}
|
||||
}
|
||||
|
||||
func NewPoint() *Point {
|
||||
return &Point{X: big.NewInt(0), Y: big.NewInt(1)}
|
||||
return &Point{X: ff.NewElement().SetZero(), Y: ff.NewElement().SetOne()}
|
||||
}
|
||||
|
||||
// Set copies a Point c into the Point p
|
||||
@@ -59,44 +83,45 @@ func (p *Point) Set(c *Point) *Point {
|
||||
return p
|
||||
}
|
||||
|
||||
func (p *Point) Equal(q *Point) bool {
|
||||
// return p.X.Cmp(q.X) == 0 && p.Y.Cmp(q.Y) == 0
|
||||
return p.X.Equal(q.X) && p.Y.Equal(q.Y)
|
||||
}
|
||||
|
||||
// Add adds Point a and b into res
|
||||
func (res *Point) Add(a *Point, b *Point) *Point {
|
||||
// x = (a.x * b.y + b.x * a.y) * (1 + D * a.x * b.x * a.y * b.y)^-1 mod q
|
||||
x1a := new(big.Int).Mul(a.X, b.Y)
|
||||
x1b := new(big.Int).Mul(b.X, a.Y)
|
||||
x1a := ff.NewElement().Mul(a.X, b.Y)
|
||||
x1b := ff.NewElement().Mul(b.X, a.Y)
|
||||
x1a.Add(x1a, x1b) // x1a = a.x * b.y + b.x * a.y
|
||||
|
||||
x2 := new(big.Int).Set(D)
|
||||
x2 := ff.NewElement().Set(D)
|
||||
x2.Mul(x2, a.X)
|
||||
x2.Mul(x2, b.X)
|
||||
x2.Mul(x2, a.Y)
|
||||
x2.Mul(x2, b.Y)
|
||||
x2.Add(constants.One, x2)
|
||||
x2.Mod(x2, constants.Q)
|
||||
x2.ModInverse(x2, constants.Q) // x2 = (1 + D * a.x * b.x * a.y * b.y)^-1
|
||||
x2.Add(ff.NewElement().SetOne(), x2)
|
||||
x2.Inverse(x2) // x2 = (1 + D * a.x * b.x * a.y * b.y)^-1
|
||||
|
||||
// y = (a.y * b.y - A * a.x * b.x) * (1 - D * a.x * b.x * a.y * b.y)^-1 mod q
|
||||
y1a := new(big.Int).Mul(a.Y, b.Y)
|
||||
y1b := new(big.Int).Set(A)
|
||||
y1a := ff.NewElement().Mul(a.Y, b.Y)
|
||||
y1b := ff.NewElement().Set(A)
|
||||
y1b.Mul(y1b, a.X)
|
||||
y1b.Mul(y1b, b.X)
|
||||
|
||||
y1a.Sub(y1a, y1b) // y1a = a.y * b.y - A * a.x * b.x
|
||||
|
||||
y2 := new(big.Int).Set(D)
|
||||
y2 := ff.NewElement().Set(D)
|
||||
y2.Mul(y2, a.X)
|
||||
y2.Mul(y2, b.X)
|
||||
y2.Mul(y2, a.Y)
|
||||
y2.Mul(y2, b.Y)
|
||||
y2.Sub(constants.One, y2)
|
||||
y2.Mod(y2, constants.Q)
|
||||
y2.ModInverse(y2, constants.Q) // y2 = (1 - D * a.x * b.x * a.y * b.y)^-1
|
||||
y2.Sub(ff.NewElement().SetOne(), y2)
|
||||
y2.Inverse(y2) // y2 = (1 - D * a.x * b.x * a.y * b.y)^-1
|
||||
|
||||
res.X = x1a.Mul(x1a, x2)
|
||||
res.X = res.X.Mod(res.X, constants.Q)
|
||||
|
||||
res.Y = y1a.Mul(y1a, y2)
|
||||
res.Y = res.Y.Mod(res.Y, constants.Q)
|
||||
|
||||
return res
|
||||
}
|
||||
@@ -104,8 +129,8 @@ func (res *Point) Add(a *Point, b *Point) *Point {
|
||||
// Mul multiplies the Point p by the scalar s and stores the result in res,
|
||||
// which is also returned.
|
||||
func (res *Point) Mul(s *big.Int, p *Point) *Point {
|
||||
res.X = big.NewInt(0)
|
||||
res.Y = big.NewInt(1)
|
||||
res.X = ff.NewElement().SetZero()
|
||||
res.Y = ff.NewElement().SetOne()
|
||||
exp := NewPoint().Set(p)
|
||||
|
||||
for i := 0; i < s.BitLen(); i++ {
|
||||
@@ -120,25 +145,21 @@ func (res *Point) Mul(s *big.Int, p *Point) *Point {
|
||||
|
||||
// InCurve returns true when the Point p is in the babyjub curve.
|
||||
func (p *Point) InCurve() bool {
|
||||
x2 := new(big.Int).Set(p.X)
|
||||
x2 := ff.NewElement().Set(p.X)
|
||||
x2.Mul(x2, x2)
|
||||
x2.Mod(x2, constants.Q)
|
||||
|
||||
y2 := new(big.Int).Set(p.Y)
|
||||
y2 := ff.NewElement().Set(p.Y)
|
||||
y2.Mul(y2, y2)
|
||||
y2.Mod(y2, constants.Q)
|
||||
|
||||
a := new(big.Int).Mul(A, x2)
|
||||
a := ff.NewElement().Mul(A, x2)
|
||||
a.Add(a, y2)
|
||||
a.Mod(a, constants.Q)
|
||||
|
||||
b := new(big.Int).Set(D)
|
||||
b := ff.NewElement().Set(D)
|
||||
b.Mul(b, x2)
|
||||
b.Mul(b, y2)
|
||||
b.Add(constants.One, b)
|
||||
b.Mod(b, constants.Q)
|
||||
b.Add(ff.NewElement().SetOne(), b)
|
||||
|
||||
return a.Cmp(b) == 0
|
||||
return a.Equal(b)
|
||||
}
|
||||
|
||||
// InSubGroup returns true when the Point p is in the subgroup of the babyjub
|
||||
@@ -148,7 +169,7 @@ func (p *Point) InSubGroup() bool {
|
||||
return false
|
||||
}
|
||||
res := NewPoint().Mul(SubOrder, p)
|
||||
return (res.X.Cmp(constants.Zero) == 0) && (res.Y.Cmp(constants.One) == 0)
|
||||
return res.X.Equal(ff.NewElement().SetZero()) && res.Y.Equal(ff.NewElement().SetOne())
|
||||
}
|
||||
|
||||
// PointCoordSign returns the sign of the curve point coordinate. It returns
|
||||
@@ -171,8 +192,9 @@ func PackPoint(ay *big.Int, sign bool) [32]byte {
|
||||
// Compress the point into a 32 byte array that contains the y coordinate in
|
||||
// little endian and the sign of the x coordinate.
|
||||
func (p *Point) Compress() [32]byte {
|
||||
sign := PointCoordSign(p.X)
|
||||
return PackPoint(p.Y, sign)
|
||||
pBI := PointToPointBI(p)
|
||||
sign := PointCoordSign(pBI.X)
|
||||
return PackPoint(pBI.Y, sign)
|
||||
}
|
||||
|
||||
// Decompress a compressed Point into p, and also returns the decompressed
|
||||
@@ -183,34 +205,37 @@ func (p *Point) Decompress(leBuf [32]byte) (*Point, error) {
|
||||
sign = true
|
||||
leBuf[31] = leBuf[31] & 0x7F
|
||||
}
|
||||
utils.SetBigIntFromLEBytes(p.Y, leBuf[:])
|
||||
if p.Y.Cmp(constants.Q) >= 0 {
|
||||
y := big.NewInt(0)
|
||||
utils.SetBigIntFromLEBytes(y, leBuf[:])
|
||||
if y.Cmp(constants.Q) >= 0 {
|
||||
return nil, fmt.Errorf("p.y >= Q")
|
||||
}
|
||||
p.Y = ff.NewElement().SetBigInt(y)
|
||||
|
||||
y2 := new(big.Int).Mul(p.Y, p.Y)
|
||||
y2.Mod(y2, constants.Q)
|
||||
xa := big.NewInt(1)
|
||||
y2 := ff.NewElement().Mul(p.Y, p.Y)
|
||||
xa := ff.NewElement().SetOne()
|
||||
xa.Sub(xa, y2) // xa == 1 - y^2
|
||||
|
||||
xb := new(big.Int).Mul(D, y2)
|
||||
xb.Mod(xb, constants.Q)
|
||||
xb := ff.NewElement().Mul(D, y2)
|
||||
xb.Sub(A, xb) // xb = A - d * y^2
|
||||
|
||||
if xb.Cmp(big.NewInt(0)) == 0 {
|
||||
if xb.Equal(ff.NewElement().SetZero()) {
|
||||
return nil, fmt.Errorf("division by 0")
|
||||
}
|
||||
xb.ModInverse(xb, constants.Q)
|
||||
xb.Inverse(xb)
|
||||
p.X.Mul(xa, xb) // xa / xb
|
||||
p.X.Mod(p.X, constants.Q)
|
||||
noSqrt := p.X.ModSqrt(p.X, constants.Q)
|
||||
|
||||
q := PointToPointBI(p)
|
||||
noSqrt := q.X.ModSqrt(q.X, constants.Q)
|
||||
if noSqrt == nil {
|
||||
return nil, fmt.Errorf("x is not a square mod q")
|
||||
}
|
||||
if (sign && !PointCoordSign(p.X)) || (!sign && PointCoordSign(p.X)) {
|
||||
p.X.Mul(p.X, constants.MinusOne)
|
||||
if (sign && !PointCoordSign(q.X)) || (!sign && PointCoordSign(q.X)) {
|
||||
q.X.Mul(q.X, constants.MinusOne)
|
||||
}
|
||||
p.X.Mod(p.X, constants.Q)
|
||||
q.X.Mod(q.X, constants.Q)
|
||||
|
||||
p = PointBIToPoint(q)
|
||||
|
||||
return p, nil
|
||||
}
|
||||
|
||||
@@ -7,13 +7,21 @@ import (
|
||||
"testing"
|
||||
|
||||
"github.com/iden3/go-iden3-crypto/constants"
|
||||
"github.com/iden3/go-iden3-crypto/ff"
|
||||
"github.com/iden3/go-iden3-crypto/utils"
|
||||
"github.com/stretchr/testify/assert"
|
||||
)
|
||||
|
||||
func zero() *ff.Element {
|
||||
return ff.NewElement().SetZero()
|
||||
}
|
||||
func one() *ff.Element {
|
||||
return ff.NewElement().SetOne()
|
||||
}
|
||||
|
||||
func TestAdd1(t *testing.T) {
|
||||
a := &Point{X: big.NewInt(0), Y: big.NewInt(1)}
|
||||
b := &Point{X: big.NewInt(0), Y: big.NewInt(1)}
|
||||
a := &Point{X: zero(), Y: one()}
|
||||
b := &Point{X: zero(), Y: one()}
|
||||
|
||||
c := NewPoint().Add(a, b)
|
||||
// fmt.Printf("%v = 2 * %v", *c, *a)
|
||||
@@ -22,15 +30,15 @@ func TestAdd1(t *testing.T) {
|
||||
}
|
||||
|
||||
func TestAdd2(t *testing.T) {
|
||||
aX := utils.NewIntFromString(
|
||||
aX := ff.NewElement().SetString(
|
||||
"17777552123799933955779906779655732241715742912184938656739573121738514868268")
|
||||
aY := utils.NewIntFromString(
|
||||
aY := ff.NewElement().SetString(
|
||||
"2626589144620713026669568689430873010625803728049924121243784502389097019475")
|
||||
a := &Point{X: aX, Y: aY}
|
||||
|
||||
bX := utils.NewIntFromString(
|
||||
bX := ff.NewElement().SetString(
|
||||
"17777552123799933955779906779655732241715742912184938656739573121738514868268")
|
||||
bY := utils.NewIntFromString(
|
||||
bY := ff.NewElement().SetString(
|
||||
"2626589144620713026669568689430873010625803728049924121243784502389097019475")
|
||||
b := &Point{X: bX, Y: bY}
|
||||
|
||||
@@ -45,15 +53,15 @@ func TestAdd2(t *testing.T) {
|
||||
}
|
||||
|
||||
func TestAdd3(t *testing.T) {
|
||||
aX := utils.NewIntFromString(
|
||||
aX := ff.NewElement().SetString(
|
||||
"17777552123799933955779906779655732241715742912184938656739573121738514868268")
|
||||
aY := utils.NewIntFromString(
|
||||
aY := ff.NewElement().SetString(
|
||||
"2626589144620713026669568689430873010625803728049924121243784502389097019475")
|
||||
a := &Point{X: aX, Y: aY}
|
||||
|
||||
bX := utils.NewIntFromString(
|
||||
bX := ff.NewElement().SetString(
|
||||
"16540640123574156134436876038791482806971768689494387082833631921987005038935")
|
||||
bY := utils.NewIntFromString(
|
||||
bY := ff.NewElement().SetString(
|
||||
"20819045374670962167435360035096875258406992893633759881276124905556507972311")
|
||||
b := &Point{X: bX, Y: bY}
|
||||
|
||||
@@ -68,15 +76,15 @@ func TestAdd3(t *testing.T) {
|
||||
}
|
||||
|
||||
func TestAdd4(t *testing.T) {
|
||||
aX := utils.NewIntFromString(
|
||||
aX := ff.NewElement().SetString(
|
||||
"0")
|
||||
aY := utils.NewIntFromString(
|
||||
aY := ff.NewElement().SetString(
|
||||
"1")
|
||||
a := &Point{X: aX, Y: aY}
|
||||
|
||||
bX := utils.NewIntFromString(
|
||||
bX := ff.NewElement().SetString(
|
||||
"16540640123574156134436876038791482806971768689494387082833631921987005038935")
|
||||
bY := utils.NewIntFromString(
|
||||
bY := ff.NewElement().SetString(
|
||||
"20819045374670962167435360035096875258406992893633759881276124905556507972311")
|
||||
b := &Point{X: bX, Y: bY}
|
||||
|
||||
@@ -91,19 +99,19 @@ func TestAdd4(t *testing.T) {
|
||||
}
|
||||
|
||||
func TestInCurve1(t *testing.T) {
|
||||
p := &Point{X: big.NewInt(0), Y: big.NewInt(1)}
|
||||
p := &Point{X: zero(), Y: one()}
|
||||
assert.Equal(t, true, p.InCurve())
|
||||
}
|
||||
|
||||
func TestInCurve2(t *testing.T) {
|
||||
p := &Point{X: big.NewInt(1), Y: big.NewInt(0)}
|
||||
p := &Point{X: one(), Y: zero()}
|
||||
assert.Equal(t, false, p.InCurve())
|
||||
}
|
||||
|
||||
func TestMul0(t *testing.T) {
|
||||
x := utils.NewIntFromString(
|
||||
x := ff.NewElement().SetString(
|
||||
"17777552123799933955779906779655732241715742912184938656739573121738514868268")
|
||||
y := utils.NewIntFromString(
|
||||
y := ff.NewElement().SetString(
|
||||
"2626589144620713026669568689430873010625803728049924121243784502389097019475")
|
||||
p := &Point{X: x, Y: y}
|
||||
s := utils.NewIntFromString("3")
|
||||
@@ -123,9 +131,9 @@ func TestMul0(t *testing.T) {
|
||||
}
|
||||
|
||||
func TestMul1(t *testing.T) {
|
||||
x := utils.NewIntFromString(
|
||||
x := ff.NewElement().SetString(
|
||||
"17777552123799933955779906779655732241715742912184938656739573121738514868268")
|
||||
y := utils.NewIntFromString(
|
||||
y := ff.NewElement().SetString(
|
||||
"2626589144620713026669568689430873010625803728049924121243784502389097019475")
|
||||
p := &Point{X: x, Y: y}
|
||||
s := utils.NewIntFromString(
|
||||
@@ -140,9 +148,9 @@ func TestMul1(t *testing.T) {
|
||||
}
|
||||
|
||||
func TestMul2(t *testing.T) {
|
||||
x := utils.NewIntFromString(
|
||||
x := ff.NewElement().SetString(
|
||||
"6890855772600357754907169075114257697580319025794532037257385534741338397365")
|
||||
y := utils.NewIntFromString(
|
||||
y := ff.NewElement().SetString(
|
||||
"4338620300185947561074059802482547481416142213883829469920100239455078257889")
|
||||
p := &Point{X: x, Y: y}
|
||||
s := utils.NewIntFromString(
|
||||
@@ -157,45 +165,45 @@ func TestMul2(t *testing.T) {
|
||||
}
|
||||
|
||||
func TestInCurve3(t *testing.T) {
|
||||
x := utils.NewIntFromString(
|
||||
x := ff.NewElement().SetString(
|
||||
"17777552123799933955779906779655732241715742912184938656739573121738514868268")
|
||||
y := utils.NewIntFromString(
|
||||
y := ff.NewElement().SetString(
|
||||
"2626589144620713026669568689430873010625803728049924121243784502389097019475")
|
||||
p := &Point{X: x, Y: y}
|
||||
assert.Equal(t, true, p.InCurve())
|
||||
}
|
||||
|
||||
func TestInCurve4(t *testing.T) {
|
||||
x := utils.NewIntFromString(
|
||||
x := ff.NewElement().SetString(
|
||||
"6890855772600357754907169075114257697580319025794532037257385534741338397365")
|
||||
y := utils.NewIntFromString(
|
||||
y := ff.NewElement().SetString(
|
||||
"4338620300185947561074059802482547481416142213883829469920100239455078257889")
|
||||
p := &Point{X: x, Y: y}
|
||||
assert.Equal(t, true, p.InCurve())
|
||||
}
|
||||
|
||||
func TestInSubGroup1(t *testing.T) {
|
||||
x := utils.NewIntFromString(
|
||||
x := ff.NewElement().SetString(
|
||||
"17777552123799933955779906779655732241715742912184938656739573121738514868268")
|
||||
y := utils.NewIntFromString(
|
||||
y := ff.NewElement().SetString(
|
||||
"2626589144620713026669568689430873010625803728049924121243784502389097019475")
|
||||
p := &Point{X: x, Y: y}
|
||||
assert.Equal(t, true, p.InSubGroup())
|
||||
}
|
||||
|
||||
func TestInSubGroup2(t *testing.T) {
|
||||
x := utils.NewIntFromString(
|
||||
x := ff.NewElement().SetString(
|
||||
"6890855772600357754907169075114257697580319025794532037257385534741338397365")
|
||||
y := utils.NewIntFromString(
|
||||
y := ff.NewElement().SetString(
|
||||
"4338620300185947561074059802482547481416142213883829469920100239455078257889")
|
||||
p := &Point{X: x, Y: y}
|
||||
assert.Equal(t, true, p.InSubGroup())
|
||||
}
|
||||
|
||||
func TestCompressDecompress1(t *testing.T) {
|
||||
x := utils.NewIntFromString(
|
||||
x := ff.NewElement().SetString(
|
||||
"17777552123799933955779906779655732241715742912184938656739573121738514868268")
|
||||
y := utils.NewIntFromString(
|
||||
y := ff.NewElement().SetString(
|
||||
"2626589144620713026669568689430873010625803728049924121243784502389097019475")
|
||||
p := &Point{X: x, Y: y}
|
||||
|
||||
@@ -209,9 +217,9 @@ func TestCompressDecompress1(t *testing.T) {
|
||||
}
|
||||
|
||||
func TestCompressDecompress2(t *testing.T) {
|
||||
x := utils.NewIntFromString(
|
||||
x := ff.NewElement().SetString(
|
||||
"6890855772600357754907169075114257697580319025794532037257385534741338397365")
|
||||
y := utils.NewIntFromString(
|
||||
y := ff.NewElement().SetString(
|
||||
"4338620300185947561074059802482547481416142213883829469920100239455078257889")
|
||||
p := &Point{X: x, Y: y}
|
||||
|
||||
@@ -230,7 +238,8 @@ func TestCompressDecompressRnd(t *testing.T) {
|
||||
buf := p1.Compress()
|
||||
p2, err := NewPoint().Decompress(buf)
|
||||
assert.Equal(t, nil, err)
|
||||
assert.Equal(t, p1, p2)
|
||||
// assert.Equal(t, p1, p2)
|
||||
assert.True(t, p1.Equal(p2))
|
||||
}
|
||||
}
|
||||
|
||||
@@ -241,15 +250,15 @@ func BenchmarkBabyjub(b *testing.B) {
|
||||
|
||||
var badpoints [n]*Point
|
||||
for i := 0; i < n; i++ {
|
||||
x := new(big.Int).Rand(rnd, constants.Q)
|
||||
y := new(big.Int).Rand(rnd, constants.Q)
|
||||
x := ff.NewElement().SetRandom()
|
||||
y := ff.NewElement().SetRandom()
|
||||
badpoints[i] = &Point{X: x, Y: y}
|
||||
}
|
||||
|
||||
var points [n]*Point
|
||||
baseX := utils.NewIntFromString(
|
||||
baseX := ff.NewElement().SetString(
|
||||
"17777552123799933955779906779655732241715742912184938656739573121738514868268")
|
||||
baseY := utils.NewIntFromString(
|
||||
baseY := ff.NewElement().SetString(
|
||||
"2626589144620713026669568689430873010625803728049924121243784502389097019475")
|
||||
base := &Point{X: baseX, Y: baseY}
|
||||
for i := 0; i < n; i++ {
|
||||
@@ -263,8 +272,8 @@ func BenchmarkBabyjub(b *testing.B) {
|
||||
}
|
||||
|
||||
b.Run("AddConst", func(b *testing.B) {
|
||||
p0 := &Point{X: big.NewInt(0), Y: big.NewInt(1)}
|
||||
p1 := &Point{X: big.NewInt(0), Y: big.NewInt(1)}
|
||||
p0 := &Point{X: zero(), Y: one()}
|
||||
p1 := &Point{X: zero(), Y: one()}
|
||||
|
||||
p2 := NewPoint()
|
||||
for i := 0; i < b.N; i++ {
|
||||
|
||||
@@ -180,7 +180,7 @@ func (k *PrivateKey) SignMimc7(msg *big.Int) *Signature {
|
||||
r.Mod(r, SubOrder)
|
||||
R8 := NewPoint().Mul(r, B8) // R8 = r * 8 * B
|
||||
A := k.Public().Point()
|
||||
hmInput := []*big.Int{R8.X, R8.Y, A.X, A.Y, msg}
|
||||
hmInput := []*big.Int{R8.X.BigInt(), R8.Y.BigInt(), A.X.BigInt(), A.Y.BigInt(), msg}
|
||||
hm, err := mimc7.Hash(hmInput, nil) // hm = H1(8*R.x, 8*R.y, A.x, A.y, msg)
|
||||
if err != nil {
|
||||
panic(err)
|
||||
@@ -196,7 +196,7 @@ func (k *PrivateKey) SignMimc7(msg *big.Int) *Signature {
|
||||
// VerifyMimc7 verifies the signature of a message encoded as a big.Int in Zq
|
||||
// using blake-512 hash for buffer hashing and mimc7 for big.Int hashing.
|
||||
func (p *PublicKey) VerifyMimc7(msg *big.Int, sig *Signature) bool {
|
||||
hmInput := []*big.Int{sig.R8.X, sig.R8.Y, p.X, p.Y, msg}
|
||||
hmInput := []*big.Int{sig.R8.X.BigInt(), sig.R8.Y.BigInt(), p.X.BigInt(), p.Y.BigInt(), msg}
|
||||
hm, err := mimc7.Hash(hmInput, nil) // hm = H1(8*R.x, 8*R.y, A.x, A.y, msg)
|
||||
if err != nil {
|
||||
panic(err)
|
||||
@@ -207,7 +207,7 @@ func (p *PublicKey) VerifyMimc7(msg *big.Int, sig *Signature) bool {
|
||||
r1.Mul(r1, hm)
|
||||
right := NewPoint().Mul(r1, p.Point())
|
||||
right.Add(sig.R8, right) // right = 8 * R + 8 * hm * A
|
||||
return (left.X.Cmp(right.X) == 0) && (left.Y.Cmp(right.Y) == 0)
|
||||
return left.X.Equal(right.X) && left.Y.Equal(right.Y)
|
||||
}
|
||||
|
||||
// SignPoseidon signs a message encoded as a big.Int in Zq using blake-512 hash
|
||||
@@ -223,7 +223,7 @@ func (k *PrivateKey) SignPoseidon(msg *big.Int) *Signature {
|
||||
R8 := NewPoint().Mul(r, B8) // R8 = r * 8 * B
|
||||
A := k.Public().Point()
|
||||
|
||||
hmInput := [poseidon.T]*big.Int{R8.X, R8.Y, A.X, A.Y, msg, big.NewInt(int64(0))}
|
||||
hmInput := [poseidon.T]*big.Int{R8.X.BigInt(), R8.Y.BigInt(), A.X.BigInt(), A.Y.BigInt(), msg, big.NewInt(int64(0))}
|
||||
hm, err := poseidon.PoseidonHash(hmInput) // hm = H1(8*R.x, 8*R.y, A.x, A.y, msg)
|
||||
if err != nil {
|
||||
panic(err)
|
||||
@@ -240,7 +240,7 @@ func (k *PrivateKey) SignPoseidon(msg *big.Int) *Signature {
|
||||
// VerifyPoseidon verifies the signature of a message encoded as a big.Int in Zq
|
||||
// using blake-512 hash for buffer hashing and Poseidon for big.Int hashing.
|
||||
func (p *PublicKey) VerifyPoseidon(msg *big.Int, sig *Signature) bool {
|
||||
hmInput := [poseidon.T]*big.Int{sig.R8.X, sig.R8.Y, p.X, p.Y, msg, big.NewInt(int64(0))}
|
||||
hmInput := [poseidon.T]*big.Int{sig.R8.X.BigInt(), sig.R8.Y.BigInt(), p.X.BigInt(), p.Y.BigInt(), msg, big.NewInt(int64(0))}
|
||||
hm, err := poseidon.PoseidonHash(hmInput) // hm = H1(8*R.x, 8*R.y, A.x, A.y, msg)
|
||||
if err != nil {
|
||||
panic(err)
|
||||
@@ -251,5 +251,5 @@ func (p *PublicKey) VerifyPoseidon(msg *big.Int, sig *Signature) bool {
|
||||
r1.Mul(r1, hm)
|
||||
right := NewPoint().Mul(r1, p.Point())
|
||||
right.Add(sig.R8, right) // right = 8 * R + 8 * hm * A
|
||||
return (left.X.Cmp(right.X) == 0) && (left.Y.Cmp(right.Y) == 0)
|
||||
return left.X.Equal(right.X) && left.Y.Equal(right.Y)
|
||||
}
|
||||
|
||||
@@ -31,8 +31,8 @@ func TestPublicKey(t *testing.T) {
|
||||
hex.Decode(k[:], []byte{byte(i)})
|
||||
}
|
||||
pk := k.Public()
|
||||
assert.True(t, pk.X.Cmp(constants.Q) == -1)
|
||||
assert.True(t, pk.Y.Cmp(constants.Q) == -1)
|
||||
assert.True(t, pk.X.BigInt().Cmp(constants.Q) == -1)
|
||||
assert.True(t, pk.Y.BigInt().Cmp(constants.Q) == -1)
|
||||
}
|
||||
|
||||
func TestSignVerifyMimc7(t *testing.T) {
|
||||
|
||||
@@ -12,19 +12,14 @@
|
||||
// See the License for the specific language governing permissions and
|
||||
// limitations under the License.
|
||||
|
||||
// Code generated by goff (v0.2.0) DO NOT EDIT
|
||||
// Code generated by goff DO NOT EDIT
|
||||
|
||||
// Package ff contains field arithmetic operations
|
||||
package ff
|
||||
|
||||
import (
|
||||
"math/bits"
|
||||
|
||||
"golang.org/x/sys/cpu"
|
||||
)
|
||||
|
||||
var supportAdx = cpu.X86.HasADX && cpu.X86.HasBMI2
|
||||
|
||||
func madd(a, b, t, u, v uint64) (uint64, uint64, uint64) {
|
||||
var carry uint64
|
||||
hi, lo := bits.Mul64(a, b)
|
||||
|
||||
386
ff/element.go
386
ff/element.go
@@ -12,33 +12,29 @@
|
||||
// See the License for the specific language governing permissions and
|
||||
// limitations under the License.
|
||||
|
||||
// Code generated by goff (v0.2.0) DO NOT EDIT
|
||||
// field modulus q =
|
||||
//
|
||||
// 21888242871839275222246405745257275088548364400416034343698204186575808495617
|
||||
// Code generated by goff DO NOT EDIT
|
||||
// goff version: - build:
|
||||
// Element are assumed to be in Montgomery form in all methods
|
||||
|
||||
// Package ff contains field arithmetic operations
|
||||
// Package ff (generated by goff) contains field arithmetics operations
|
||||
package ff
|
||||
|
||||
// /!\ WARNING /!\
|
||||
// this code has not been audited and is provided as-is. In particular,
|
||||
// there is no security guarantees such as constant time implementation
|
||||
// or side-channel attack resistance
|
||||
// /!\ WARNING /!\
|
||||
|
||||
import (
|
||||
"crypto/rand"
|
||||
"encoding/binary"
|
||||
"io"
|
||||
"math/big"
|
||||
"math/bits"
|
||||
"strconv"
|
||||
"sync"
|
||||
|
||||
"unsafe"
|
||||
)
|
||||
|
||||
// Element represents a field element stored on 4 words (uint64)
|
||||
// Element are assumed to be in Montgomery form in all methods
|
||||
// field modulus q =
|
||||
//
|
||||
// 21888242871839275222246405745257275088548364400416034343698204186575808495617
|
||||
type Element [4]uint64
|
||||
|
||||
// ElementLimbs number of 64 bits words needed to represent Element
|
||||
@@ -315,7 +311,6 @@ func (z *Element) SetRandom() *Element {
|
||||
z[3] %= 3486998266802970665
|
||||
|
||||
// if z > q --> z -= q
|
||||
// note: this is NOT constant time
|
||||
if !(z[3] < 3486998266802970665 || (z[3] == 3486998266802970665 && (z[2] < 13281191951274694749 || (z[2] == 13281191951274694749 && (z[1] < 2896914383306846353 || (z[1] == 2896914383306846353 && (z[0] < 4891460686036598785))))))) {
|
||||
var b uint64
|
||||
z[0], b = bits.Sub64(z[0], 4891460686036598785, 0)
|
||||
@@ -327,38 +322,6 @@ func (z *Element) SetRandom() *Element {
|
||||
return z
|
||||
}
|
||||
|
||||
// One returns 1 (in montgommery form)
|
||||
func One() Element {
|
||||
var one Element
|
||||
one.SetOne()
|
||||
return one
|
||||
}
|
||||
|
||||
// FromInterface converts i1 from uint64, int, string, or Element, big.Int into Element
|
||||
// panic if provided type is not supported
|
||||
func FromInterface(i1 interface{}) Element {
|
||||
var val Element
|
||||
|
||||
switch c1 := i1.(type) {
|
||||
case uint64:
|
||||
val.SetUint64(c1)
|
||||
case int:
|
||||
val.SetString(strconv.Itoa(c1))
|
||||
case string:
|
||||
val.SetString(c1)
|
||||
case big.Int:
|
||||
val.SetBigInt(&c1)
|
||||
case Element:
|
||||
val = c1
|
||||
case *Element:
|
||||
val.Set(c1)
|
||||
default:
|
||||
panic("invalid type")
|
||||
}
|
||||
|
||||
return val
|
||||
}
|
||||
|
||||
// Add z = x + y mod q
|
||||
func (z *Element) Add(x, y *Element) *Element {
|
||||
var carry uint64
|
||||
@@ -369,7 +332,6 @@ func (z *Element) Add(x, y *Element) *Element {
|
||||
z[3], _ = bits.Add64(x[3], y[3], carry)
|
||||
|
||||
// if z > q --> z -= q
|
||||
// note: this is NOT constant time
|
||||
if !(z[3] < 3486998266802970665 || (z[3] == 3486998266802970665 && (z[2] < 13281191951274694749 || (z[2] == 13281191951274694749 && (z[1] < 2896914383306846353 || (z[1] == 2896914383306846353 && (z[0] < 4891460686036598785))))))) {
|
||||
var b uint64
|
||||
z[0], b = bits.Sub64(z[0], 4891460686036598785, 0)
|
||||
@@ -390,7 +352,6 @@ func (z *Element) AddAssign(x *Element) *Element {
|
||||
z[3], _ = bits.Add64(z[3], x[3], carry)
|
||||
|
||||
// if z > q --> z -= q
|
||||
// note: this is NOT constant time
|
||||
if !(z[3] < 3486998266802970665 || (z[3] == 3486998266802970665 && (z[2] < 13281191951274694749 || (z[2] == 13281191951274694749 && (z[1] < 2896914383306846353 || (z[1] == 2896914383306846353 && (z[0] < 4891460686036598785))))))) {
|
||||
var b uint64
|
||||
z[0], b = bits.Sub64(z[0], 4891460686036598785, 0)
|
||||
@@ -411,7 +372,6 @@ func (z *Element) Double(x *Element) *Element {
|
||||
z[3], _ = bits.Add64(x[3], x[3], carry)
|
||||
|
||||
// if z > q --> z -= q
|
||||
// note: this is NOT constant time
|
||||
if !(z[3] < 3486998266802970665 || (z[3] == 3486998266802970665 && (z[2] < 13281191951274694749 || (z[2] == 13281191951274694749 && (z[1] < 2896914383306846353 || (z[1] == 2896914383306846353 && (z[0] < 4891460686036598785))))))) {
|
||||
var b uint64
|
||||
z[0], b = bits.Sub64(z[0], 4891460686036598785, 0)
|
||||
@@ -456,31 +416,18 @@ func (z *Element) SubAssign(x *Element) *Element {
|
||||
return z
|
||||
}
|
||||
|
||||
// Exp z = x^exponent mod q
|
||||
// (not optimized)
|
||||
// exponent (non-montgomery form) is ordered from least significant word to most significant word
|
||||
func (z *Element) Exp(x Element, exponent ...uint64) *Element {
|
||||
r := 0
|
||||
msb := 0
|
||||
for i := len(exponent) - 1; i >= 0; i-- {
|
||||
if exponent[i] == 0 {
|
||||
r++
|
||||
} else {
|
||||
msb = (i * 64) + bits.Len64(exponent[i])
|
||||
break
|
||||
}
|
||||
}
|
||||
exponent = exponent[:len(exponent)-r]
|
||||
if len(exponent) == 0 {
|
||||
// Exp z = x^e mod q
|
||||
func (z *Element) Exp(x Element, e uint64) *Element {
|
||||
if e == 0 {
|
||||
return z.SetOne()
|
||||
}
|
||||
|
||||
z.Set(&x)
|
||||
|
||||
l := msb - 2
|
||||
l := bits.Len64(e) - 2
|
||||
for i := l; i >= 0; i-- {
|
||||
z.Square(z)
|
||||
if exponent[i/64]&(1<<uint(i%64)) != 0 {
|
||||
if e&(1<<uint(i)) != 0 {
|
||||
z.MulAssign(&x)
|
||||
}
|
||||
}
|
||||
@@ -531,7 +478,6 @@ func (z *Element) FromMont() *Element {
|
||||
}
|
||||
|
||||
// if z > q --> z -= q
|
||||
// note: this is NOT constant time
|
||||
if !(z[3] < 3486998266802970665 || (z[3] == 3486998266802970665 && (z[2] < 13281191951274694749 || (z[2] == 13281191951274694749 && (z[1] < 2896914383306846353 || (z[1] == 2896914383306846353 && (z[0] < 4891460686036598785))))))) {
|
||||
var b uint64
|
||||
z[0], b = bits.Sub64(z[0], 4891460686036598785, 0)
|
||||
@@ -567,33 +513,15 @@ func (z *Element) String() string {
|
||||
|
||||
// ToBigInt returns z as a big.Int in Montgomery form
|
||||
func (z *Element) ToBigInt(res *big.Int) *big.Int {
|
||||
if bits.UintSize == 64 {
|
||||
bits := (*[4]big.Word)(unsafe.Pointer(z))
|
||||
return res.SetBits(bits[:])
|
||||
} else {
|
||||
var bits [8]big.Word
|
||||
for i := 0; i < len(z); i++ {
|
||||
bits[i*2] = big.Word(z[i])
|
||||
bits[i*2+1] = big.Word(z[i] >> 32)
|
||||
}
|
||||
return res.SetBits(bits[:])
|
||||
}
|
||||
}
|
||||
|
||||
// ToBigIntRegular returns z as a big.Int in regular form
|
||||
func (z Element) ToBigIntRegular(res *big.Int) *big.Int {
|
||||
z.FromMont()
|
||||
if bits.UintSize == 64 {
|
||||
bits := (*[4]big.Word)(unsafe.Pointer(&z))
|
||||
return res.SetBits(bits[:])
|
||||
} else {
|
||||
var bits [8]big.Word
|
||||
for i := 0; i < len(z); i++ {
|
||||
bits[i*2] = big.Word(z[i])
|
||||
bits[i*2+1] = big.Word(z[i] >> 32)
|
||||
}
|
||||
return res.SetBits(bits[:])
|
||||
}
|
||||
}
|
||||
|
||||
// SetBigInt sets z to v (regular form) and returns z in Montgomery form
|
||||
@@ -603,19 +531,6 @@ func (z *Element) SetBigInt(v *big.Int) *Element {
|
||||
zero := big.NewInt(0)
|
||||
q := elementModulusBigInt()
|
||||
|
||||
// fast path
|
||||
c := v.Cmp(q)
|
||||
if c == 0 {
|
||||
return z
|
||||
} else if c != 1 && v.Cmp(zero) != -1 {
|
||||
// v should
|
||||
vBits := v.Bits()
|
||||
for i := 0; i < len(vBits); i++ {
|
||||
z[i] = uint64(vBits[i])
|
||||
}
|
||||
return z.ToMont()
|
||||
}
|
||||
|
||||
// copy input
|
||||
vv := new(big.Int).Set(v)
|
||||
|
||||
@@ -633,19 +548,9 @@ func (z *Element) SetBigInt(v *big.Int) *Element {
|
||||
}
|
||||
// v should
|
||||
vBits := vv.Bits()
|
||||
if bits.UintSize == 64 {
|
||||
for i := 0; i < len(vBits); i++ {
|
||||
z[i] = uint64(vBits[i])
|
||||
}
|
||||
} else {
|
||||
for i := 0; i < len(vBits); i++ {
|
||||
if i%2 == 0 {
|
||||
z[i/2] = uint64(vBits[i])
|
||||
} else {
|
||||
z[i/2] |= uint64(vBits[i]) << 32
|
||||
}
|
||||
}
|
||||
}
|
||||
return z.ToMont()
|
||||
}
|
||||
|
||||
@@ -658,97 +563,202 @@ func (z *Element) SetString(s string) *Element {
|
||||
return z.SetBigInt(x)
|
||||
}
|
||||
|
||||
// Legendre returns the Legendre symbol of z (either +1, -1, or 0.)
|
||||
func (z *Element) Legendre() int {
|
||||
var l Element
|
||||
// z^((q-1)/2)
|
||||
l.Exp(*z,
|
||||
11669102379873075200,
|
||||
10671829228508198984,
|
||||
15863968012492123182,
|
||||
1743499133401485332,
|
||||
)
|
||||
// Mul z = x * y mod q
|
||||
func (z *Element) Mul(x, y *Element) *Element {
|
||||
|
||||
if l.IsZero() {
|
||||
return 0
|
||||
var t [4]uint64
|
||||
var c [3]uint64
|
||||
{
|
||||
// round 0
|
||||
v := x[0]
|
||||
c[1], c[0] = bits.Mul64(v, y[0])
|
||||
m := c[0] * 14042775128853446655
|
||||
c[2] = madd0(m, 4891460686036598785, c[0])
|
||||
c[1], c[0] = madd1(v, y[1], c[1])
|
||||
c[2], t[0] = madd2(m, 2896914383306846353, c[2], c[0])
|
||||
c[1], c[0] = madd1(v, y[2], c[1])
|
||||
c[2], t[1] = madd2(m, 13281191951274694749, c[2], c[0])
|
||||
c[1], c[0] = madd1(v, y[3], c[1])
|
||||
t[3], t[2] = madd3(m, 3486998266802970665, c[0], c[2], c[1])
|
||||
}
|
||||
{
|
||||
// round 1
|
||||
v := x[1]
|
||||
c[1], c[0] = madd1(v, y[0], t[0])
|
||||
m := c[0] * 14042775128853446655
|
||||
c[2] = madd0(m, 4891460686036598785, c[0])
|
||||
c[1], c[0] = madd2(v, y[1], c[1], t[1])
|
||||
c[2], t[0] = madd2(m, 2896914383306846353, c[2], c[0])
|
||||
c[1], c[0] = madd2(v, y[2], c[1], t[2])
|
||||
c[2], t[1] = madd2(m, 13281191951274694749, c[2], c[0])
|
||||
c[1], c[0] = madd2(v, y[3], c[1], t[3])
|
||||
t[3], t[2] = madd3(m, 3486998266802970665, c[0], c[2], c[1])
|
||||
}
|
||||
{
|
||||
// round 2
|
||||
v := x[2]
|
||||
c[1], c[0] = madd1(v, y[0], t[0])
|
||||
m := c[0] * 14042775128853446655
|
||||
c[2] = madd0(m, 4891460686036598785, c[0])
|
||||
c[1], c[0] = madd2(v, y[1], c[1], t[1])
|
||||
c[2], t[0] = madd2(m, 2896914383306846353, c[2], c[0])
|
||||
c[1], c[0] = madd2(v, y[2], c[1], t[2])
|
||||
c[2], t[1] = madd2(m, 13281191951274694749, c[2], c[0])
|
||||
c[1], c[0] = madd2(v, y[3], c[1], t[3])
|
||||
t[3], t[2] = madd3(m, 3486998266802970665, c[0], c[2], c[1])
|
||||
}
|
||||
{
|
||||
// round 3
|
||||
v := x[3]
|
||||
c[1], c[0] = madd1(v, y[0], t[0])
|
||||
m := c[0] * 14042775128853446655
|
||||
c[2] = madd0(m, 4891460686036598785, c[0])
|
||||
c[1], c[0] = madd2(v, y[1], c[1], t[1])
|
||||
c[2], z[0] = madd2(m, 2896914383306846353, c[2], c[0])
|
||||
c[1], c[0] = madd2(v, y[2], c[1], t[2])
|
||||
c[2], z[1] = madd2(m, 13281191951274694749, c[2], c[0])
|
||||
c[1], c[0] = madd2(v, y[3], c[1], t[3])
|
||||
z[3], z[2] = madd3(m, 3486998266802970665, c[0], c[2], c[1])
|
||||
}
|
||||
|
||||
// if l == 1
|
||||
if (l[3] == 1011752739694698287) && (l[2] == 7381016538464732718) && (l[1] == 3962172157175319849) && (l[0] == 12436184717236109307) {
|
||||
return 1
|
||||
// if z > q --> z -= q
|
||||
if !(z[3] < 3486998266802970665 || (z[3] == 3486998266802970665 && (z[2] < 13281191951274694749 || (z[2] == 13281191951274694749 && (z[1] < 2896914383306846353 || (z[1] == 2896914383306846353 && (z[0] < 4891460686036598785))))))) {
|
||||
var b uint64
|
||||
z[0], b = bits.Sub64(z[0], 4891460686036598785, 0)
|
||||
z[1], b = bits.Sub64(z[1], 2896914383306846353, b)
|
||||
z[2], b = bits.Sub64(z[2], 13281191951274694749, b)
|
||||
z[3], _ = bits.Sub64(z[3], 3486998266802970665, b)
|
||||
}
|
||||
return -1
|
||||
return z
|
||||
}
|
||||
|
||||
// Sqrt z = √x mod q
|
||||
// if the square root doesn't exist (x is not a square mod q)
|
||||
// Sqrt leaves z unchanged and returns nil
|
||||
func (z *Element) Sqrt(x *Element) *Element {
|
||||
// q ≡ 1 (mod 4)
|
||||
// see modSqrtTonelliShanks in math/big/int.go
|
||||
// using https://www.maa.org/sites/default/files/pdf/upload_library/22/Polya/07468342.di020786.02p0470a.pdf
|
||||
// MulAssign z = z * x mod q
|
||||
func (z *Element) MulAssign(x *Element) *Element {
|
||||
|
||||
var y, b, t, w Element
|
||||
// w = x^((s-1)/2))
|
||||
w.Exp(*x,
|
||||
14829091926808964255,
|
||||
867720185306366531,
|
||||
688207751544974772,
|
||||
6495040407,
|
||||
)
|
||||
|
||||
// y = x^((s+1)/2)) = w * x
|
||||
y.Mul(x, &w)
|
||||
|
||||
// b = x^s = w * w * x = y * x
|
||||
b.Mul(&w, &y)
|
||||
|
||||
// g = nonResidue ^ s
|
||||
var g = Element{
|
||||
7164790868263648668,
|
||||
11685701338293206998,
|
||||
6216421865291908056,
|
||||
1756667274303109607,
|
||||
var t [4]uint64
|
||||
var c [3]uint64
|
||||
{
|
||||
// round 0
|
||||
v := z[0]
|
||||
c[1], c[0] = bits.Mul64(v, x[0])
|
||||
m := c[0] * 14042775128853446655
|
||||
c[2] = madd0(m, 4891460686036598785, c[0])
|
||||
c[1], c[0] = madd1(v, x[1], c[1])
|
||||
c[2], t[0] = madd2(m, 2896914383306846353, c[2], c[0])
|
||||
c[1], c[0] = madd1(v, x[2], c[1])
|
||||
c[2], t[1] = madd2(m, 13281191951274694749, c[2], c[0])
|
||||
c[1], c[0] = madd1(v, x[3], c[1])
|
||||
t[3], t[2] = madd3(m, 3486998266802970665, c[0], c[2], c[1])
|
||||
}
|
||||
r := uint64(28)
|
||||
|
||||
// compute legendre symbol
|
||||
// t = x^((q-1)/2) = r-1 squaring of x^s
|
||||
t = b
|
||||
for i := uint64(0); i < r-1; i++ {
|
||||
t.Square(&t)
|
||||
{
|
||||
// round 1
|
||||
v := z[1]
|
||||
c[1], c[0] = madd1(v, x[0], t[0])
|
||||
m := c[0] * 14042775128853446655
|
||||
c[2] = madd0(m, 4891460686036598785, c[0])
|
||||
c[1], c[0] = madd2(v, x[1], c[1], t[1])
|
||||
c[2], t[0] = madd2(m, 2896914383306846353, c[2], c[0])
|
||||
c[1], c[0] = madd2(v, x[2], c[1], t[2])
|
||||
c[2], t[1] = madd2(m, 13281191951274694749, c[2], c[0])
|
||||
c[1], c[0] = madd2(v, x[3], c[1], t[3])
|
||||
t[3], t[2] = madd3(m, 3486998266802970665, c[0], c[2], c[1])
|
||||
}
|
||||
if t.IsZero() {
|
||||
return z.SetZero()
|
||||
{
|
||||
// round 2
|
||||
v := z[2]
|
||||
c[1], c[0] = madd1(v, x[0], t[0])
|
||||
m := c[0] * 14042775128853446655
|
||||
c[2] = madd0(m, 4891460686036598785, c[0])
|
||||
c[1], c[0] = madd2(v, x[1], c[1], t[1])
|
||||
c[2], t[0] = madd2(m, 2896914383306846353, c[2], c[0])
|
||||
c[1], c[0] = madd2(v, x[2], c[1], t[2])
|
||||
c[2], t[1] = madd2(m, 13281191951274694749, c[2], c[0])
|
||||
c[1], c[0] = madd2(v, x[3], c[1], t[3])
|
||||
t[3], t[2] = madd3(m, 3486998266802970665, c[0], c[2], c[1])
|
||||
}
|
||||
if !((t[3] == 1011752739694698287) && (t[2] == 7381016538464732718) && (t[1] == 3962172157175319849) && (t[0] == 12436184717236109307)) {
|
||||
// t != 1, we don't have a square root
|
||||
return nil
|
||||
}
|
||||
for {
|
||||
var m uint64
|
||||
t = b
|
||||
|
||||
// for t != 1
|
||||
for !((t[3] == 1011752739694698287) && (t[2] == 7381016538464732718) && (t[1] == 3962172157175319849) && (t[0] == 12436184717236109307)) {
|
||||
t.Square(&t)
|
||||
m++
|
||||
{
|
||||
// round 3
|
||||
v := z[3]
|
||||
c[1], c[0] = madd1(v, x[0], t[0])
|
||||
m := c[0] * 14042775128853446655
|
||||
c[2] = madd0(m, 4891460686036598785, c[0])
|
||||
c[1], c[0] = madd2(v, x[1], c[1], t[1])
|
||||
c[2], z[0] = madd2(m, 2896914383306846353, c[2], c[0])
|
||||
c[1], c[0] = madd2(v, x[2], c[1], t[2])
|
||||
c[2], z[1] = madd2(m, 13281191951274694749, c[2], c[0])
|
||||
c[1], c[0] = madd2(v, x[3], c[1], t[3])
|
||||
z[3], z[2] = madd3(m, 3486998266802970665, c[0], c[2], c[1])
|
||||
}
|
||||
|
||||
if m == 0 {
|
||||
return z.Set(&y)
|
||||
}
|
||||
// t = g^(2^(r-m-1)) mod q
|
||||
ge := int(r - m - 1)
|
||||
t = g
|
||||
for ge > 0 {
|
||||
t.Square(&t)
|
||||
ge--
|
||||
}
|
||||
|
||||
g.Square(&t)
|
||||
y.MulAssign(&t)
|
||||
b.MulAssign(&g)
|
||||
r = m
|
||||
// if z > q --> z -= q
|
||||
if !(z[3] < 3486998266802970665 || (z[3] == 3486998266802970665 && (z[2] < 13281191951274694749 || (z[2] == 13281191951274694749 && (z[1] < 2896914383306846353 || (z[1] == 2896914383306846353 && (z[0] < 4891460686036598785))))))) {
|
||||
var b uint64
|
||||
z[0], b = bits.Sub64(z[0], 4891460686036598785, 0)
|
||||
z[1], b = bits.Sub64(z[1], 2896914383306846353, b)
|
||||
z[2], b = bits.Sub64(z[2], 13281191951274694749, b)
|
||||
z[3], _ = bits.Sub64(z[3], 3486998266802970665, b)
|
||||
}
|
||||
return z
|
||||
}
|
||||
|
||||
// Square z = x * x mod q
|
||||
func (z *Element) Square(x *Element) *Element {
|
||||
|
||||
var p [4]uint64
|
||||
|
||||
var u, v uint64
|
||||
{
|
||||
// round 0
|
||||
u, p[0] = bits.Mul64(x[0], x[0])
|
||||
m := p[0] * 14042775128853446655
|
||||
C := madd0(m, 4891460686036598785, p[0])
|
||||
var t uint64
|
||||
t, u, v = madd1sb(x[0], x[1], u)
|
||||
C, p[0] = madd2(m, 2896914383306846353, v, C)
|
||||
t, u, v = madd1s(x[0], x[2], t, u)
|
||||
C, p[1] = madd2(m, 13281191951274694749, v, C)
|
||||
_, u, v = madd1s(x[0], x[3], t, u)
|
||||
p[3], p[2] = madd3(m, 3486998266802970665, v, C, u)
|
||||
}
|
||||
{
|
||||
// round 1
|
||||
m := p[0] * 14042775128853446655
|
||||
C := madd0(m, 4891460686036598785, p[0])
|
||||
u, v = madd1(x[1], x[1], p[1])
|
||||
C, p[0] = madd2(m, 2896914383306846353, v, C)
|
||||
var t uint64
|
||||
t, u, v = madd2sb(x[1], x[2], p[2], u)
|
||||
C, p[1] = madd2(m, 13281191951274694749, v, C)
|
||||
_, u, v = madd2s(x[1], x[3], p[3], t, u)
|
||||
p[3], p[2] = madd3(m, 3486998266802970665, v, C, u)
|
||||
}
|
||||
{
|
||||
// round 2
|
||||
m := p[0] * 14042775128853446655
|
||||
C := madd0(m, 4891460686036598785, p[0])
|
||||
C, p[0] = madd2(m, 2896914383306846353, p[1], C)
|
||||
u, v = madd1(x[2], x[2], p[2])
|
||||
C, p[1] = madd2(m, 13281191951274694749, v, C)
|
||||
_, u, v = madd2sb(x[2], x[3], p[3], u)
|
||||
p[3], p[2] = madd3(m, 3486998266802970665, v, C, u)
|
||||
}
|
||||
{
|
||||
// round 3
|
||||
m := p[0] * 14042775128853446655
|
||||
C := madd0(m, 4891460686036598785, p[0])
|
||||
C, z[0] = madd2(m, 2896914383306846353, p[1], C)
|
||||
C, z[1] = madd2(m, 13281191951274694749, p[2], C)
|
||||
u, v = madd1(x[3], x[3], p[3])
|
||||
z[3], z[2] = madd3(m, 3486998266802970665, v, C, u)
|
||||
}
|
||||
|
||||
// if z > q --> z -= q
|
||||
if !(z[3] < 3486998266802970665 || (z[3] == 3486998266802970665 && (z[2] < 13281191951274694749 || (z[2] == 13281191951274694749 && (z[1] < 2896914383306846353 || (z[1] == 2896914383306846353 && (z[0] < 4891460686036598785))))))) {
|
||||
var b uint64
|
||||
z[0], b = bits.Sub64(z[0], 4891460686036598785, 0)
|
||||
z[1], b = bits.Sub64(z[1], 2896914383306846353, b)
|
||||
z[2], b = bits.Sub64(z[2], 13281191951274694749, b)
|
||||
z[3], _ = bits.Sub64(z[3], 3486998266802970665, b)
|
||||
}
|
||||
return z
|
||||
}
|
||||
|
||||
@@ -1,170 +0,0 @@
|
||||
// +build !amd64
|
||||
|
||||
// Copyright 2020 ConsenSys AG
|
||||
//
|
||||
// Licensed under the Apache License, Version 2.0 (the "License");
|
||||
// you may not use this file except in compliance with the License.
|
||||
// You may obtain a copy of the License at
|
||||
//
|
||||
// http://www.apache.org/licenses/LICENSE-2.0
|
||||
//
|
||||
// Unless required by applicable law or agreed to in writing, software
|
||||
// distributed under the License is distributed on an "AS IS" BASIS,
|
||||
// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
|
||||
// See the License for the specific language governing permissions and
|
||||
// limitations under the License.
|
||||
|
||||
// Code generated by goff (v0.2.0) DO NOT EDIT
|
||||
|
||||
// Package ff contains field arithmetic operations
|
||||
package ff
|
||||
|
||||
// /!\ WARNING /!\
|
||||
// this code has not been audited and is provided as-is. In particular,
|
||||
// there is no security guarantees such as constant time implementation
|
||||
// or side-channel attack resistance
|
||||
// /!\ WARNING /!\
|
||||
|
||||
import "math/bits"
|
||||
|
||||
// Mul z = x * y mod q
|
||||
// see https://hackmd.io/@zkteam/modular_multiplication
|
||||
func (z *Element) Mul(x, y *Element) *Element {
|
||||
|
||||
var t [4]uint64
|
||||
var c [3]uint64
|
||||
{
|
||||
// round 0
|
||||
v := x[0]
|
||||
c[1], c[0] = bits.Mul64(v, y[0])
|
||||
m := c[0] * 14042775128853446655
|
||||
c[2] = madd0(m, 4891460686036598785, c[0])
|
||||
c[1], c[0] = madd1(v, y[1], c[1])
|
||||
c[2], t[0] = madd2(m, 2896914383306846353, c[2], c[0])
|
||||
c[1], c[0] = madd1(v, y[2], c[1])
|
||||
c[2], t[1] = madd2(m, 13281191951274694749, c[2], c[0])
|
||||
c[1], c[0] = madd1(v, y[3], c[1])
|
||||
t[3], t[2] = madd3(m, 3486998266802970665, c[0], c[2], c[1])
|
||||
}
|
||||
{
|
||||
// round 1
|
||||
v := x[1]
|
||||
c[1], c[0] = madd1(v, y[0], t[0])
|
||||
m := c[0] * 14042775128853446655
|
||||
c[2] = madd0(m, 4891460686036598785, c[0])
|
||||
c[1], c[0] = madd2(v, y[1], c[1], t[1])
|
||||
c[2], t[0] = madd2(m, 2896914383306846353, c[2], c[0])
|
||||
c[1], c[0] = madd2(v, y[2], c[1], t[2])
|
||||
c[2], t[1] = madd2(m, 13281191951274694749, c[2], c[0])
|
||||
c[1], c[0] = madd2(v, y[3], c[1], t[3])
|
||||
t[3], t[2] = madd3(m, 3486998266802970665, c[0], c[2], c[1])
|
||||
}
|
||||
{
|
||||
// round 2
|
||||
v := x[2]
|
||||
c[1], c[0] = madd1(v, y[0], t[0])
|
||||
m := c[0] * 14042775128853446655
|
||||
c[2] = madd0(m, 4891460686036598785, c[0])
|
||||
c[1], c[0] = madd2(v, y[1], c[1], t[1])
|
||||
c[2], t[0] = madd2(m, 2896914383306846353, c[2], c[0])
|
||||
c[1], c[0] = madd2(v, y[2], c[1], t[2])
|
||||
c[2], t[1] = madd2(m, 13281191951274694749, c[2], c[0])
|
||||
c[1], c[0] = madd2(v, y[3], c[1], t[3])
|
||||
t[3], t[2] = madd3(m, 3486998266802970665, c[0], c[2], c[1])
|
||||
}
|
||||
{
|
||||
// round 3
|
||||
v := x[3]
|
||||
c[1], c[0] = madd1(v, y[0], t[0])
|
||||
m := c[0] * 14042775128853446655
|
||||
c[2] = madd0(m, 4891460686036598785, c[0])
|
||||
c[1], c[0] = madd2(v, y[1], c[1], t[1])
|
||||
c[2], z[0] = madd2(m, 2896914383306846353, c[2], c[0])
|
||||
c[1], c[0] = madd2(v, y[2], c[1], t[2])
|
||||
c[2], z[1] = madd2(m, 13281191951274694749, c[2], c[0])
|
||||
c[1], c[0] = madd2(v, y[3], c[1], t[3])
|
||||
z[3], z[2] = madd3(m, 3486998266802970665, c[0], c[2], c[1])
|
||||
}
|
||||
|
||||
// if z > q --> z -= q
|
||||
// note: this is NOT constant time
|
||||
if !(z[3] < 3486998266802970665 || (z[3] == 3486998266802970665 && (z[2] < 13281191951274694749 || (z[2] == 13281191951274694749 && (z[1] < 2896914383306846353 || (z[1] == 2896914383306846353 && (z[0] < 4891460686036598785))))))) {
|
||||
var b uint64
|
||||
z[0], b = bits.Sub64(z[0], 4891460686036598785, 0)
|
||||
z[1], b = bits.Sub64(z[1], 2896914383306846353, b)
|
||||
z[2], b = bits.Sub64(z[2], 13281191951274694749, b)
|
||||
z[3], _ = bits.Sub64(z[3], 3486998266802970665, b)
|
||||
}
|
||||
return z
|
||||
}
|
||||
|
||||
// MulAssign z = z * x mod q
|
||||
// see https://hackmd.io/@zkteam/modular_multiplication
|
||||
func (z *Element) MulAssign(x *Element) *Element {
|
||||
|
||||
var t [4]uint64
|
||||
var c [3]uint64
|
||||
{
|
||||
// round 0
|
||||
v := z[0]
|
||||
c[1], c[0] = bits.Mul64(v, x[0])
|
||||
m := c[0] * 14042775128853446655
|
||||
c[2] = madd0(m, 4891460686036598785, c[0])
|
||||
c[1], c[0] = madd1(v, x[1], c[1])
|
||||
c[2], t[0] = madd2(m, 2896914383306846353, c[2], c[0])
|
||||
c[1], c[0] = madd1(v, x[2], c[1])
|
||||
c[2], t[1] = madd2(m, 13281191951274694749, c[2], c[0])
|
||||
c[1], c[0] = madd1(v, x[3], c[1])
|
||||
t[3], t[2] = madd3(m, 3486998266802970665, c[0], c[2], c[1])
|
||||
}
|
||||
{
|
||||
// round 1
|
||||
v := z[1]
|
||||
c[1], c[0] = madd1(v, x[0], t[0])
|
||||
m := c[0] * 14042775128853446655
|
||||
c[2] = madd0(m, 4891460686036598785, c[0])
|
||||
c[1], c[0] = madd2(v, x[1], c[1], t[1])
|
||||
c[2], t[0] = madd2(m, 2896914383306846353, c[2], c[0])
|
||||
c[1], c[0] = madd2(v, x[2], c[1], t[2])
|
||||
c[2], t[1] = madd2(m, 13281191951274694749, c[2], c[0])
|
||||
c[1], c[0] = madd2(v, x[3], c[1], t[3])
|
||||
t[3], t[2] = madd3(m, 3486998266802970665, c[0], c[2], c[1])
|
||||
}
|
||||
{
|
||||
// round 2
|
||||
v := z[2]
|
||||
c[1], c[0] = madd1(v, x[0], t[0])
|
||||
m := c[0] * 14042775128853446655
|
||||
c[2] = madd0(m, 4891460686036598785, c[0])
|
||||
c[1], c[0] = madd2(v, x[1], c[1], t[1])
|
||||
c[2], t[0] = madd2(m, 2896914383306846353, c[2], c[0])
|
||||
c[1], c[0] = madd2(v, x[2], c[1], t[2])
|
||||
c[2], t[1] = madd2(m, 13281191951274694749, c[2], c[0])
|
||||
c[1], c[0] = madd2(v, x[3], c[1], t[3])
|
||||
t[3], t[2] = madd3(m, 3486998266802970665, c[0], c[2], c[1])
|
||||
}
|
||||
{
|
||||
// round 3
|
||||
v := z[3]
|
||||
c[1], c[0] = madd1(v, x[0], t[0])
|
||||
m := c[0] * 14042775128853446655
|
||||
c[2] = madd0(m, 4891460686036598785, c[0])
|
||||
c[1], c[0] = madd2(v, x[1], c[1], t[1])
|
||||
c[2], z[0] = madd2(m, 2896914383306846353, c[2], c[0])
|
||||
c[1], c[0] = madd2(v, x[2], c[1], t[2])
|
||||
c[2], z[1] = madd2(m, 13281191951274694749, c[2], c[0])
|
||||
c[1], c[0] = madd2(v, x[3], c[1], t[3])
|
||||
z[3], z[2] = madd3(m, 3486998266802970665, c[0], c[2], c[1])
|
||||
}
|
||||
|
||||
// if z > q --> z -= q
|
||||
// note: this is NOT constant time
|
||||
if !(z[3] < 3486998266802970665 || (z[3] == 3486998266802970665 && (z[2] < 13281191951274694749 || (z[2] == 13281191951274694749 && (z[1] < 2896914383306846353 || (z[1] == 2896914383306846353 && (z[0] < 4891460686036598785))))))) {
|
||||
var b uint64
|
||||
z[0], b = bits.Sub64(z[0], 4891460686036598785, 0)
|
||||
z[1], b = bits.Sub64(z[1], 2896914383306846353, b)
|
||||
z[2], b = bits.Sub64(z[2], 13281191951274694749, b)
|
||||
z[3], _ = bits.Sub64(z[3], 3486998266802970665, b)
|
||||
}
|
||||
return z
|
||||
}
|
||||
@@ -1,39 +0,0 @@
|
||||
// Copyright 2020 ConsenSys AG
|
||||
//
|
||||
// Licensed under the Apache License, Version 2.0 (the "License");
|
||||
// you may not use this file except in compliance with the License.
|
||||
// You may obtain a copy of the License at
|
||||
//
|
||||
// http://www.apache.org/licenses/LICENSE-2.0
|
||||
//
|
||||
// Unless required by applicable law or agreed to in writing, software
|
||||
// distributed under the License is distributed on an "AS IS" BASIS,
|
||||
// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
|
||||
// See the License for the specific language governing permissions and
|
||||
// limitations under the License.
|
||||
|
||||
// Code generated by goff (v0.2.0) DO NOT EDIT
|
||||
|
||||
// Package ff contains field arithmetic operations
|
||||
package ff
|
||||
|
||||
// MulAssignElement z = z * x mod q (constant time)
|
||||
// calling this instead of z.MulAssign(x) is prefered for performance critical path
|
||||
//go:noescape
|
||||
func MulAssignElement(res, y *Element)
|
||||
|
||||
// Mul z = x * y mod q (constant time)
|
||||
// see https://hackmd.io/@zkteam/modular_multiplication
|
||||
func (z *Element) Mul(x, y *Element) *Element {
|
||||
res := *x
|
||||
MulAssignElement(&res, y)
|
||||
z.Set(&res)
|
||||
return z
|
||||
}
|
||||
|
||||
// MulAssign z = z * x mod q (constant time)
|
||||
// see https://hackmd.io/@zkteam/modular_multiplication
|
||||
func (z *Element) MulAssign(x *Element) *Element {
|
||||
MulAssignElement(z, x)
|
||||
return z
|
||||
}
|
||||
@@ -1,695 +0,0 @@
|
||||
// Code generated by goff (v0.2.0) DO NOT EDIT
|
||||
|
||||
#include "textflag.h"
|
||||
|
||||
// func MulAssignElement(res,y *Element)
|
||||
// montgomery multiplication of res by y
|
||||
// stores the result in res
|
||||
TEXT ·MulAssignElement(SB), NOSPLIT, $0-16
|
||||
|
||||
// dereference our parameters
|
||||
MOVQ res+0(FP), DI
|
||||
MOVQ y+8(FP), R8
|
||||
|
||||
// check if we support adx and mulx
|
||||
CMPB ·supportAdx(SB), $1
|
||||
JNE no_adx
|
||||
|
||||
// the algorithm is described here
|
||||
// https://hackmd.io/@zkteam/modular_multiplication
|
||||
// however, to benefit from the ADCX and ADOX carry chains
|
||||
// we split the inner loops in 2:
|
||||
// for i=0 to N-1
|
||||
// for j=0 to N-1
|
||||
// (A,t[j]) := t[j] + a[j]*b[i] + A
|
||||
// m := t[0]*q'[0] mod W
|
||||
// C,_ := t[0] + m*q[0]
|
||||
// for j=1 to N-1
|
||||
// (C,t[j-1]) := t[j] + m*q[j] + C
|
||||
// t[N-1] = C + A
|
||||
|
||||
// ---------------------------------------------------------------------------------------------
|
||||
// outter loop 0
|
||||
|
||||
// clear up the carry flags
|
||||
XORQ R9 , R9
|
||||
|
||||
// R12 = y[0]
|
||||
MOVQ 0(R8), R12
|
||||
|
||||
// for j=0 to N-1
|
||||
// (A,t[j]) := t[j] + x[j]*y[i] + A
|
||||
|
||||
// DX = res[0]
|
||||
MOVQ 0(DI), DX
|
||||
MULXQ R12, CX , R9
|
||||
|
||||
// DX = res[1]
|
||||
MOVQ 8(DI), DX
|
||||
MOVQ R9, BX
|
||||
MULXQ R12, AX, R9
|
||||
ADOXQ AX, BX
|
||||
|
||||
// DX = res[2]
|
||||
MOVQ 16(DI), DX
|
||||
MOVQ R9, BP
|
||||
MULXQ R12, AX, R9
|
||||
ADOXQ AX, BP
|
||||
|
||||
// DX = res[3]
|
||||
MOVQ 24(DI), DX
|
||||
MOVQ R9, SI
|
||||
MULXQ R12, AX, R9
|
||||
ADOXQ AX, SI
|
||||
|
||||
// add the last carries to R9
|
||||
MOVQ $0, DX
|
||||
ADCXQ DX, R9
|
||||
ADOXQ DX, R9
|
||||
|
||||
// m := t[0]*q'[0] mod W
|
||||
MOVQ $0xc2e1f593efffffff, DX
|
||||
MULXQ CX,R11, DX
|
||||
|
||||
// clear the carry flags
|
||||
XORQ DX, DX
|
||||
|
||||
// C,_ := t[0] + m*q[0]
|
||||
MOVQ $0x43e1f593f0000001, DX
|
||||
MULXQ R11, AX, R10
|
||||
ADCXQ CX ,AX
|
||||
|
||||
// for j=1 to N-1
|
||||
// (C,t[j-1]) := t[j] + m*q[j] + C
|
||||
|
||||
MOVQ $0x2833e84879b97091, DX
|
||||
MULXQ R11, AX, DX
|
||||
ADCXQ BX, R10
|
||||
ADOXQ AX, R10
|
||||
MOVQ R10, CX
|
||||
MOVQ DX, R10
|
||||
|
||||
MOVQ $0xb85045b68181585d, DX
|
||||
MULXQ R11, AX, DX
|
||||
ADCXQ BP, R10
|
||||
ADOXQ AX, R10
|
||||
MOVQ R10, BX
|
||||
MOVQ DX, R10
|
||||
|
||||
MOVQ $0x30644e72e131a029, DX
|
||||
MULXQ R11, AX, DX
|
||||
ADCXQ SI, R10
|
||||
ADOXQ AX, R10
|
||||
MOVQ R10, BP
|
||||
MOVQ $0, AX
|
||||
ADCXQ AX, DX
|
||||
ADOXQ DX, R9
|
||||
MOVQ R9, SI
|
||||
|
||||
// ---------------------------------------------------------------------------------------------
|
||||
// outter loop 1
|
||||
|
||||
// clear up the carry flags
|
||||
XORQ R9 , R9
|
||||
|
||||
// R12 = y[1]
|
||||
MOVQ 8(R8), R12
|
||||
|
||||
// for j=0 to N-1
|
||||
// (A,t[j]) := t[j] + x[j]*y[i] + A
|
||||
|
||||
// DX = res[0]
|
||||
MOVQ 0(DI), DX
|
||||
MULXQ R12, AX, R9
|
||||
ADOXQ AX, CX
|
||||
|
||||
// DX = res[1]
|
||||
MOVQ 8(DI), DX
|
||||
ADCXQ R9, BX
|
||||
MULXQ R12, AX, R9
|
||||
ADOXQ AX, BX
|
||||
|
||||
// DX = res[2]
|
||||
MOVQ 16(DI), DX
|
||||
ADCXQ R9, BP
|
||||
MULXQ R12, AX, R9
|
||||
ADOXQ AX, BP
|
||||
|
||||
// DX = res[3]
|
||||
MOVQ 24(DI), DX
|
||||
ADCXQ R9, SI
|
||||
MULXQ R12, AX, R9
|
||||
ADOXQ AX, SI
|
||||
|
||||
// add the last carries to R9
|
||||
MOVQ $0, DX
|
||||
ADCXQ DX, R9
|
||||
ADOXQ DX, R9
|
||||
|
||||
// m := t[0]*q'[0] mod W
|
||||
MOVQ $0xc2e1f593efffffff, DX
|
||||
MULXQ CX,R11, DX
|
||||
|
||||
// clear the carry flags
|
||||
XORQ DX, DX
|
||||
|
||||
// C,_ := t[0] + m*q[0]
|
||||
MOVQ $0x43e1f593f0000001, DX
|
||||
MULXQ R11, AX, R10
|
||||
ADCXQ CX ,AX
|
||||
|
||||
// for j=1 to N-1
|
||||
// (C,t[j-1]) := t[j] + m*q[j] + C
|
||||
|
||||
MOVQ $0x2833e84879b97091, DX
|
||||
MULXQ R11, AX, DX
|
||||
ADCXQ BX, R10
|
||||
ADOXQ AX, R10
|
||||
MOVQ R10, CX
|
||||
MOVQ DX, R10
|
||||
|
||||
MOVQ $0xb85045b68181585d, DX
|
||||
MULXQ R11, AX, DX
|
||||
ADCXQ BP, R10
|
||||
ADOXQ AX, R10
|
||||
MOVQ R10, BX
|
||||
MOVQ DX, R10
|
||||
|
||||
MOVQ $0x30644e72e131a029, DX
|
||||
MULXQ R11, AX, DX
|
||||
ADCXQ SI, R10
|
||||
ADOXQ AX, R10
|
||||
MOVQ R10, BP
|
||||
MOVQ $0, AX
|
||||
ADCXQ AX, DX
|
||||
ADOXQ DX, R9
|
||||
MOVQ R9, SI
|
||||
|
||||
// ---------------------------------------------------------------------------------------------
|
||||
// outter loop 2
|
||||
|
||||
// clear up the carry flags
|
||||
XORQ R9 , R9
|
||||
|
||||
// R12 = y[2]
|
||||
MOVQ 16(R8), R12
|
||||
|
||||
// for j=0 to N-1
|
||||
// (A,t[j]) := t[j] + x[j]*y[i] + A
|
||||
|
||||
// DX = res[0]
|
||||
MOVQ 0(DI), DX
|
||||
MULXQ R12, AX, R9
|
||||
ADOXQ AX, CX
|
||||
|
||||
// DX = res[1]
|
||||
MOVQ 8(DI), DX
|
||||
ADCXQ R9, BX
|
||||
MULXQ R12, AX, R9
|
||||
ADOXQ AX, BX
|
||||
|
||||
// DX = res[2]
|
||||
MOVQ 16(DI), DX
|
||||
ADCXQ R9, BP
|
||||
MULXQ R12, AX, R9
|
||||
ADOXQ AX, BP
|
||||
|
||||
// DX = res[3]
|
||||
MOVQ 24(DI), DX
|
||||
ADCXQ R9, SI
|
||||
MULXQ R12, AX, R9
|
||||
ADOXQ AX, SI
|
||||
|
||||
// add the last carries to R9
|
||||
MOVQ $0, DX
|
||||
ADCXQ DX, R9
|
||||
ADOXQ DX, R9
|
||||
|
||||
// m := t[0]*q'[0] mod W
|
||||
MOVQ $0xc2e1f593efffffff, DX
|
||||
MULXQ CX,R11, DX
|
||||
|
||||
// clear the carry flags
|
||||
XORQ DX, DX
|
||||
|
||||
// C,_ := t[0] + m*q[0]
|
||||
MOVQ $0x43e1f593f0000001, DX
|
||||
MULXQ R11, AX, R10
|
||||
ADCXQ CX ,AX
|
||||
|
||||
// for j=1 to N-1
|
||||
// (C,t[j-1]) := t[j] + m*q[j] + C
|
||||
|
||||
MOVQ $0x2833e84879b97091, DX
|
||||
MULXQ R11, AX, DX
|
||||
ADCXQ BX, R10
|
||||
ADOXQ AX, R10
|
||||
MOVQ R10, CX
|
||||
MOVQ DX, R10
|
||||
|
||||
MOVQ $0xb85045b68181585d, DX
|
||||
MULXQ R11, AX, DX
|
||||
ADCXQ BP, R10
|
||||
ADOXQ AX, R10
|
||||
MOVQ R10, BX
|
||||
MOVQ DX, R10
|
||||
|
||||
MOVQ $0x30644e72e131a029, DX
|
||||
MULXQ R11, AX, DX
|
||||
ADCXQ SI, R10
|
||||
ADOXQ AX, R10
|
||||
MOVQ R10, BP
|
||||
MOVQ $0, AX
|
||||
ADCXQ AX, DX
|
||||
ADOXQ DX, R9
|
||||
MOVQ R9, SI
|
||||
|
||||
// ---------------------------------------------------------------------------------------------
|
||||
// outter loop 3
|
||||
|
||||
// clear up the carry flags
|
||||
XORQ R9 , R9
|
||||
|
||||
// R12 = y[3]
|
||||
MOVQ 24(R8), R12
|
||||
|
||||
// for j=0 to N-1
|
||||
// (A,t[j]) := t[j] + x[j]*y[i] + A
|
||||
|
||||
// DX = res[0]
|
||||
MOVQ 0(DI), DX
|
||||
MULXQ R12, AX, R9
|
||||
ADOXQ AX, CX
|
||||
|
||||
// DX = res[1]
|
||||
MOVQ 8(DI), DX
|
||||
ADCXQ R9, BX
|
||||
MULXQ R12, AX, R9
|
||||
ADOXQ AX, BX
|
||||
|
||||
// DX = res[2]
|
||||
MOVQ 16(DI), DX
|
||||
ADCXQ R9, BP
|
||||
MULXQ R12, AX, R9
|
||||
ADOXQ AX, BP
|
||||
|
||||
// DX = res[3]
|
||||
MOVQ 24(DI), DX
|
||||
ADCXQ R9, SI
|
||||
MULXQ R12, AX, R9
|
||||
ADOXQ AX, SI
|
||||
|
||||
// add the last carries to R9
|
||||
MOVQ $0, DX
|
||||
ADCXQ DX, R9
|
||||
ADOXQ DX, R9
|
||||
|
||||
// m := t[0]*q'[0] mod W
|
||||
MOVQ $0xc2e1f593efffffff, DX
|
||||
MULXQ CX,R11, DX
|
||||
|
||||
// clear the carry flags
|
||||
XORQ DX, DX
|
||||
|
||||
// C,_ := t[0] + m*q[0]
|
||||
MOVQ $0x43e1f593f0000001, DX
|
||||
MULXQ R11, AX, R10
|
||||
ADCXQ CX ,AX
|
||||
|
||||
// for j=1 to N-1
|
||||
// (C,t[j-1]) := t[j] + m*q[j] + C
|
||||
|
||||
MOVQ $0x2833e84879b97091, DX
|
||||
MULXQ R11, AX, DX
|
||||
ADCXQ BX, R10
|
||||
ADOXQ AX, R10
|
||||
MOVQ R10, CX
|
||||
MOVQ DX, R10
|
||||
|
||||
MOVQ $0xb85045b68181585d, DX
|
||||
MULXQ R11, AX, DX
|
||||
ADCXQ BP, R10
|
||||
ADOXQ AX, R10
|
||||
MOVQ R10, BX
|
||||
MOVQ DX, R10
|
||||
|
||||
MOVQ $0x30644e72e131a029, DX
|
||||
MULXQ R11, AX, DX
|
||||
ADCXQ SI, R10
|
||||
ADOXQ AX, R10
|
||||
MOVQ R10, BP
|
||||
MOVQ $0, AX
|
||||
ADCXQ AX, DX
|
||||
ADOXQ DX, R9
|
||||
MOVQ R9, SI
|
||||
|
||||
reduce:
|
||||
// reduce, constant time version
|
||||
// first we copy registers storing t in a separate set of registers
|
||||
// as SUBQ modifies the 2nd operand
|
||||
MOVQ CX, DX
|
||||
MOVQ BX, R8
|
||||
MOVQ BP, R9
|
||||
MOVQ SI, R10
|
||||
MOVQ $0x43e1f593f0000001, R11
|
||||
SUBQ R11, DX
|
||||
MOVQ $0x2833e84879b97091, R11
|
||||
SBBQ R11, R8
|
||||
MOVQ $0xb85045b68181585d, R11
|
||||
SBBQ R11, R9
|
||||
MOVQ $0x30644e72e131a029, R11
|
||||
SBBQ R11, R10
|
||||
JCS t_is_smaller // no borrow, we return t
|
||||
|
||||
// borrow is set, we return u
|
||||
MOVQ DX, (DI)
|
||||
MOVQ R8, 8(DI)
|
||||
MOVQ R9, 16(DI)
|
||||
MOVQ R10, 24(DI)
|
||||
RET
|
||||
t_is_smaller:
|
||||
MOVQ CX, 0(DI)
|
||||
MOVQ BX, 8(DI)
|
||||
MOVQ BP, 16(DI)
|
||||
MOVQ SI, 24(DI)
|
||||
RET
|
||||
|
||||
no_adx:
|
||||
|
||||
// ---------------------------------------------------------------------------------------------
|
||||
// outter loop 0
|
||||
|
||||
// (A,t[0]) := t[0] + x[0]*y[0]
|
||||
MOVQ (DI), AX // x[0]
|
||||
MOVQ 0(R8), R12
|
||||
MULQ R12 // x[0] * y[0]
|
||||
MOVQ DX, R9
|
||||
MOVQ AX, CX
|
||||
|
||||
// m := t[0]*q'[0] mod W
|
||||
MOVQ $0xc2e1f593efffffff, R11
|
||||
IMULQ CX , R11
|
||||
|
||||
// C,_ := t[0] + m*q[0]
|
||||
MOVQ $0x43e1f593f0000001, AX
|
||||
MULQ R11
|
||||
ADDQ CX ,AX
|
||||
ADCQ $0, DX
|
||||
MOVQ DX, R10
|
||||
|
||||
// for j=1 to N-1
|
||||
// (A,t[j]) := t[j] + x[j]*y[i] + A
|
||||
// (C,t[j-1]) := t[j] + m*q[j] + C
|
||||
MOVQ 8(DI), AX
|
||||
MULQ R12 // x[1] * y[0]
|
||||
MOVQ R9, BX
|
||||
ADDQ AX, BX
|
||||
ADCQ $0, DX
|
||||
MOVQ DX, R9
|
||||
|
||||
MOVQ $0x2833e84879b97091, AX
|
||||
MULQ R11
|
||||
ADDQ BX, R10
|
||||
ADCQ $0, DX
|
||||
ADDQ AX, R10
|
||||
ADCQ $0, DX
|
||||
|
||||
MOVQ R10, CX
|
||||
MOVQ DX, R10
|
||||
MOVQ 16(DI), AX
|
||||
MULQ R12 // x[2] * y[0]
|
||||
MOVQ R9, BP
|
||||
ADDQ AX, BP
|
||||
ADCQ $0, DX
|
||||
MOVQ DX, R9
|
||||
|
||||
MOVQ $0xb85045b68181585d, AX
|
||||
MULQ R11
|
||||
ADDQ BP, R10
|
||||
ADCQ $0, DX
|
||||
ADDQ AX, R10
|
||||
ADCQ $0, DX
|
||||
|
||||
MOVQ R10, BX
|
||||
MOVQ DX, R10
|
||||
MOVQ 24(DI), AX
|
||||
MULQ R12 // x[3] * y[0]
|
||||
MOVQ R9, SI
|
||||
ADDQ AX, SI
|
||||
ADCQ $0, DX
|
||||
MOVQ DX, R9
|
||||
|
||||
MOVQ $0x30644e72e131a029, AX
|
||||
MULQ R11
|
||||
ADDQ SI, R10
|
||||
ADCQ $0, DX
|
||||
ADDQ AX, R10
|
||||
ADCQ $0, DX
|
||||
|
||||
MOVQ R10, BP
|
||||
MOVQ DX, R10
|
||||
|
||||
ADDQ R10, R9
|
||||
MOVQ R9, SI
|
||||
|
||||
// ---------------------------------------------------------------------------------------------
|
||||
// outter loop 1
|
||||
|
||||
// (A,t[0]) := t[0] + x[0]*y[1]
|
||||
MOVQ (DI), AX // x[0]
|
||||
MOVQ 8(R8), R12
|
||||
MULQ R12 // x[0] * y[1]
|
||||
ADDQ AX, CX
|
||||
ADCQ $0, DX
|
||||
MOVQ DX, R9
|
||||
|
||||
// m := t[0]*q'[0] mod W
|
||||
MOVQ $0xc2e1f593efffffff, R11
|
||||
IMULQ CX , R11
|
||||
|
||||
// C,_ := t[0] + m*q[0]
|
||||
MOVQ $0x43e1f593f0000001, AX
|
||||
MULQ R11
|
||||
ADDQ CX ,AX
|
||||
ADCQ $0, DX
|
||||
MOVQ DX, R10
|
||||
|
||||
// for j=1 to N-1
|
||||
// (A,t[j]) := t[j] + x[j]*y[i] + A
|
||||
// (C,t[j-1]) := t[j] + m*q[j] + C
|
||||
MOVQ 8(DI), AX
|
||||
MULQ R12 // x[1] * y[1]
|
||||
ADDQ R9, BX
|
||||
ADCQ $0, DX
|
||||
ADDQ AX, BX
|
||||
ADCQ $0, DX
|
||||
MOVQ DX, R9
|
||||
|
||||
MOVQ $0x2833e84879b97091, AX
|
||||
MULQ R11
|
||||
ADDQ BX, R10
|
||||
ADCQ $0, DX
|
||||
ADDQ AX, R10
|
||||
ADCQ $0, DX
|
||||
|
||||
MOVQ R10, CX
|
||||
MOVQ DX, R10
|
||||
MOVQ 16(DI), AX
|
||||
MULQ R12 // x[2] * y[1]
|
||||
ADDQ R9, BP
|
||||
ADCQ $0, DX
|
||||
ADDQ AX, BP
|
||||
ADCQ $0, DX
|
||||
MOVQ DX, R9
|
||||
|
||||
MOVQ $0xb85045b68181585d, AX
|
||||
MULQ R11
|
||||
ADDQ BP, R10
|
||||
ADCQ $0, DX
|
||||
ADDQ AX, R10
|
||||
ADCQ $0, DX
|
||||
|
||||
MOVQ R10, BX
|
||||
MOVQ DX, R10
|
||||
MOVQ 24(DI), AX
|
||||
MULQ R12 // x[3] * y[1]
|
||||
ADDQ R9, SI
|
||||
ADCQ $0, DX
|
||||
ADDQ AX, SI
|
||||
ADCQ $0, DX
|
||||
MOVQ DX, R9
|
||||
|
||||
MOVQ $0x30644e72e131a029, AX
|
||||
MULQ R11
|
||||
ADDQ SI, R10
|
||||
ADCQ $0, DX
|
||||
ADDQ AX, R10
|
||||
ADCQ $0, DX
|
||||
|
||||
MOVQ R10, BP
|
||||
MOVQ DX, R10
|
||||
|
||||
ADDQ R10, R9
|
||||
MOVQ R9, SI
|
||||
|
||||
// ---------------------------------------------------------------------------------------------
|
||||
// outter loop 2
|
||||
|
||||
// (A,t[0]) := t[0] + x[0]*y[2]
|
||||
MOVQ (DI), AX // x[0]
|
||||
MOVQ 16(R8), R12
|
||||
MULQ R12 // x[0] * y[2]
|
||||
ADDQ AX, CX
|
||||
ADCQ $0, DX
|
||||
MOVQ DX, R9
|
||||
|
||||
// m := t[0]*q'[0] mod W
|
||||
MOVQ $0xc2e1f593efffffff, R11
|
||||
IMULQ CX , R11
|
||||
|
||||
// C,_ := t[0] + m*q[0]
|
||||
MOVQ $0x43e1f593f0000001, AX
|
||||
MULQ R11
|
||||
ADDQ CX ,AX
|
||||
ADCQ $0, DX
|
||||
MOVQ DX, R10
|
||||
|
||||
// for j=1 to N-1
|
||||
// (A,t[j]) := t[j] + x[j]*y[i] + A
|
||||
// (C,t[j-1]) := t[j] + m*q[j] + C
|
||||
MOVQ 8(DI), AX
|
||||
MULQ R12 // x[1] * y[2]
|
||||
ADDQ R9, BX
|
||||
ADCQ $0, DX
|
||||
ADDQ AX, BX
|
||||
ADCQ $0, DX
|
||||
MOVQ DX, R9
|
||||
|
||||
MOVQ $0x2833e84879b97091, AX
|
||||
MULQ R11
|
||||
ADDQ BX, R10
|
||||
ADCQ $0, DX
|
||||
ADDQ AX, R10
|
||||
ADCQ $0, DX
|
||||
|
||||
MOVQ R10, CX
|
||||
MOVQ DX, R10
|
||||
MOVQ 16(DI), AX
|
||||
MULQ R12 // x[2] * y[2]
|
||||
ADDQ R9, BP
|
||||
ADCQ $0, DX
|
||||
ADDQ AX, BP
|
||||
ADCQ $0, DX
|
||||
MOVQ DX, R9
|
||||
|
||||
MOVQ $0xb85045b68181585d, AX
|
||||
MULQ R11
|
||||
ADDQ BP, R10
|
||||
ADCQ $0, DX
|
||||
ADDQ AX, R10
|
||||
ADCQ $0, DX
|
||||
|
||||
MOVQ R10, BX
|
||||
MOVQ DX, R10
|
||||
MOVQ 24(DI), AX
|
||||
MULQ R12 // x[3] * y[2]
|
||||
ADDQ R9, SI
|
||||
ADCQ $0, DX
|
||||
ADDQ AX, SI
|
||||
ADCQ $0, DX
|
||||
MOVQ DX, R9
|
||||
|
||||
MOVQ $0x30644e72e131a029, AX
|
||||
MULQ R11
|
||||
ADDQ SI, R10
|
||||
ADCQ $0, DX
|
||||
ADDQ AX, R10
|
||||
ADCQ $0, DX
|
||||
|
||||
MOVQ R10, BP
|
||||
MOVQ DX, R10
|
||||
|
||||
ADDQ R10, R9
|
||||
MOVQ R9, SI
|
||||
|
||||
// ---------------------------------------------------------------------------------------------
|
||||
// outter loop 3
|
||||
|
||||
// (A,t[0]) := t[0] + x[0]*y[3]
|
||||
MOVQ (DI), AX // x[0]
|
||||
MOVQ 24(R8), R12
|
||||
MULQ R12 // x[0] * y[3]
|
||||
ADDQ AX, CX
|
||||
ADCQ $0, DX
|
||||
MOVQ DX, R9
|
||||
|
||||
// m := t[0]*q'[0] mod W
|
||||
MOVQ $0xc2e1f593efffffff, R11
|
||||
IMULQ CX , R11
|
||||
|
||||
// C,_ := t[0] + m*q[0]
|
||||
MOVQ $0x43e1f593f0000001, AX
|
||||
MULQ R11
|
||||
ADDQ CX ,AX
|
||||
ADCQ $0, DX
|
||||
MOVQ DX, R10
|
||||
|
||||
// for j=1 to N-1
|
||||
// (A,t[j]) := t[j] + x[j]*y[i] + A
|
||||
// (C,t[j-1]) := t[j] + m*q[j] + C
|
||||
MOVQ 8(DI), AX
|
||||
MULQ R12 // x[1] * y[3]
|
||||
ADDQ R9, BX
|
||||
ADCQ $0, DX
|
||||
ADDQ AX, BX
|
||||
ADCQ $0, DX
|
||||
MOVQ DX, R9
|
||||
|
||||
MOVQ $0x2833e84879b97091, AX
|
||||
MULQ R11
|
||||
ADDQ BX, R10
|
||||
ADCQ $0, DX
|
||||
ADDQ AX, R10
|
||||
ADCQ $0, DX
|
||||
|
||||
MOVQ R10, CX
|
||||
MOVQ DX, R10
|
||||
MOVQ 16(DI), AX
|
||||
MULQ R12 // x[2] * y[3]
|
||||
ADDQ R9, BP
|
||||
ADCQ $0, DX
|
||||
ADDQ AX, BP
|
||||
ADCQ $0, DX
|
||||
MOVQ DX, R9
|
||||
|
||||
MOVQ $0xb85045b68181585d, AX
|
||||
MULQ R11
|
||||
ADDQ BP, R10
|
||||
ADCQ $0, DX
|
||||
ADDQ AX, R10
|
||||
ADCQ $0, DX
|
||||
|
||||
MOVQ R10, BX
|
||||
MOVQ DX, R10
|
||||
MOVQ 24(DI), AX
|
||||
MULQ R12 // x[3] * y[3]
|
||||
ADDQ R9, SI
|
||||
ADCQ $0, DX
|
||||
ADDQ AX, SI
|
||||
ADCQ $0, DX
|
||||
MOVQ DX, R9
|
||||
|
||||
MOVQ $0x30644e72e131a029, AX
|
||||
MULQ R11
|
||||
ADDQ SI, R10
|
||||
ADCQ $0, DX
|
||||
ADDQ AX, R10
|
||||
ADCQ $0, DX
|
||||
|
||||
MOVQ R10, BP
|
||||
MOVQ DX, R10
|
||||
|
||||
ADDQ R10, R9
|
||||
MOVQ R9, SI
|
||||
|
||||
JMP reduce
|
||||
@@ -1,93 +0,0 @@
|
||||
// +build !amd64
|
||||
|
||||
// Copyright 2020 ConsenSys AG
|
||||
//
|
||||
// Licensed under the Apache License, Version 2.0 (the "License");
|
||||
// you may not use this file except in compliance with the License.
|
||||
// You may obtain a copy of the License at
|
||||
//
|
||||
// http://www.apache.org/licenses/LICENSE-2.0
|
||||
//
|
||||
// Unless required by applicable law or agreed to in writing, software
|
||||
// distributed under the License is distributed on an "AS IS" BASIS,
|
||||
// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
|
||||
// See the License for the specific language governing permissions and
|
||||
// limitations under the License.
|
||||
|
||||
// Code generated by goff (v0.2.0) DO NOT EDIT
|
||||
|
||||
// Package ff contains field arithmetic operations
|
||||
package ff
|
||||
|
||||
// /!\ WARNING /!\
|
||||
// this code has not been audited and is provided as-is. In particular,
|
||||
// there is no security guarantees such as constant time implementation
|
||||
// or side-channel attack resistance
|
||||
// /!\ WARNING /!\
|
||||
|
||||
import "math/bits"
|
||||
|
||||
// Square z = x * x mod q
|
||||
// see https://hackmd.io/@zkteam/modular_multiplication
|
||||
func (z *Element) Square(x *Element) *Element {
|
||||
|
||||
var p [4]uint64
|
||||
|
||||
var u, v uint64
|
||||
{
|
||||
// round 0
|
||||
u, p[0] = bits.Mul64(x[0], x[0])
|
||||
m := p[0] * 14042775128853446655
|
||||
C := madd0(m, 4891460686036598785, p[0])
|
||||
var t uint64
|
||||
t, u, v = madd1sb(x[0], x[1], u)
|
||||
C, p[0] = madd2(m, 2896914383306846353, v, C)
|
||||
t, u, v = madd1s(x[0], x[2], t, u)
|
||||
C, p[1] = madd2(m, 13281191951274694749, v, C)
|
||||
_, u, v = madd1s(x[0], x[3], t, u)
|
||||
p[3], p[2] = madd3(m, 3486998266802970665, v, C, u)
|
||||
}
|
||||
{
|
||||
// round 1
|
||||
m := p[0] * 14042775128853446655
|
||||
C := madd0(m, 4891460686036598785, p[0])
|
||||
u, v = madd1(x[1], x[1], p[1])
|
||||
C, p[0] = madd2(m, 2896914383306846353, v, C)
|
||||
var t uint64
|
||||
t, u, v = madd2sb(x[1], x[2], p[2], u)
|
||||
C, p[1] = madd2(m, 13281191951274694749, v, C)
|
||||
_, u, v = madd2s(x[1], x[3], p[3], t, u)
|
||||
p[3], p[2] = madd3(m, 3486998266802970665, v, C, u)
|
||||
}
|
||||
{
|
||||
// round 2
|
||||
m := p[0] * 14042775128853446655
|
||||
C := madd0(m, 4891460686036598785, p[0])
|
||||
C, p[0] = madd2(m, 2896914383306846353, p[1], C)
|
||||
u, v = madd1(x[2], x[2], p[2])
|
||||
C, p[1] = madd2(m, 13281191951274694749, v, C)
|
||||
_, u, v = madd2sb(x[2], x[3], p[3], u)
|
||||
p[3], p[2] = madd3(m, 3486998266802970665, v, C, u)
|
||||
}
|
||||
{
|
||||
// round 3
|
||||
m := p[0] * 14042775128853446655
|
||||
C := madd0(m, 4891460686036598785, p[0])
|
||||
C, z[0] = madd2(m, 2896914383306846353, p[1], C)
|
||||
C, z[1] = madd2(m, 13281191951274694749, p[2], C)
|
||||
u, v = madd1(x[3], x[3], p[3])
|
||||
z[3], z[2] = madd3(m, 3486998266802970665, v, C, u)
|
||||
}
|
||||
|
||||
// if z > q --> z -= q
|
||||
// note: this is NOT constant time
|
||||
if !(z[3] < 3486998266802970665 || (z[3] == 3486998266802970665 && (z[2] < 13281191951274694749 || (z[2] == 13281191951274694749 && (z[1] < 2896914383306846353 || (z[1] == 2896914383306846353 && (z[0] < 4891460686036598785))))))) {
|
||||
var b uint64
|
||||
z[0], b = bits.Sub64(z[0], 4891460686036598785, 0)
|
||||
z[1], b = bits.Sub64(z[1], 2896914383306846353, b)
|
||||
z[2], b = bits.Sub64(z[2], 13281191951274694749, b)
|
||||
z[3], _ = bits.Sub64(z[3], 3486998266802970665, b)
|
||||
}
|
||||
return z
|
||||
|
||||
}
|
||||
@@ -1,34 +0,0 @@
|
||||
// Copyright 2020 ConsenSys AG
|
||||
//
|
||||
// Licensed under the Apache License, Version 2.0 (the "License");
|
||||
// you may not use this file except in compliance with the License.
|
||||
// You may obtain a copy of the License at
|
||||
//
|
||||
// http://www.apache.org/licenses/LICENSE-2.0
|
||||
//
|
||||
// Unless required by applicable law or agreed to in writing, software
|
||||
// distributed under the License is distributed on an "AS IS" BASIS,
|
||||
// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
|
||||
// See the License for the specific language governing permissions and
|
||||
// limitations under the License.
|
||||
|
||||
// Code generated by goff (v0.2.0) DO NOT EDIT
|
||||
|
||||
// Package ff contains field arithmetic operations
|
||||
package ff
|
||||
|
||||
// SquareElement z = x * x mod q
|
||||
// calling this instead of z.Square(x) is prefered for performance critical path
|
||||
// go - noescape
|
||||
// func SquareElement(res,x *Element)
|
||||
|
||||
// Square z = x * x mod q
|
||||
// see https://hackmd.io/@zkteam/modular_multiplication
|
||||
func (z *Element) Square(x *Element) *Element {
|
||||
if z != x {
|
||||
z.Set(x)
|
||||
}
|
||||
MulAssignElement(z, x)
|
||||
// SquareElement(z, x)
|
||||
return z
|
||||
}
|
||||
@@ -1,26 +1,9 @@
|
||||
// Copyright 2020 ConsenSys AG
|
||||
//
|
||||
// Licensed under the Apache License, Version 2.0 (the "License");
|
||||
// you may not use this file except in compliance with the License.
|
||||
// You may obtain a copy of the License at
|
||||
//
|
||||
// http://www.apache.org/licenses/LICENSE-2.0
|
||||
//
|
||||
// Unless required by applicable law or agreed to in writing, software
|
||||
// distributed under the License is distributed on an "AS IS" BASIS,
|
||||
// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
|
||||
// See the License for the specific language governing permissions and
|
||||
// limitations under the License.
|
||||
|
||||
// Code generated by goff (v0.2.0) DO NOT EDIT
|
||||
|
||||
// Package ff contains field arithmetic operations
|
||||
// Code generated by goff DO NOT EDIT
|
||||
package ff
|
||||
|
||||
import (
|
||||
"crypto/rand"
|
||||
"math/big"
|
||||
"math/bits"
|
||||
mrand "math/rand"
|
||||
"testing"
|
||||
)
|
||||
@@ -38,14 +21,7 @@ func TestELEMENTCorrectnessAgainstBigInt(t *testing.T) {
|
||||
|
||||
modulusMinusOne.Sub(modulus, &one)
|
||||
|
||||
var n int
|
||||
if testing.Short() {
|
||||
n = 10
|
||||
} else {
|
||||
n = 500
|
||||
}
|
||||
|
||||
for i := 0; i < n; i++ {
|
||||
for i := 0; i < 1000; i++ {
|
||||
|
||||
// sample 2 random big int
|
||||
b1, _ := rand.Int(rand.Reader, modulus)
|
||||
@@ -81,7 +57,7 @@ func TestELEMENTCorrectnessAgainstBigInt(t *testing.T) {
|
||||
|
||||
rbExp := new(big.Int).SetUint64(rExp)
|
||||
|
||||
var bMul, bAdd, bSub, bDiv, bNeg, bLsh, bInv, bExp, bExp2, bSquare big.Int
|
||||
var bMul, bAdd, bSub, bDiv, bNeg, bLsh, bInv, bExp, bSquare big.Int
|
||||
|
||||
// e1 = mont(b1), e2 = mont(b2)
|
||||
var e1, e2, eMul, eAdd, eSub, eDiv, eNeg, eLsh, eInv, eExp, eSquare, eMulAssign, eSubAssign, eAddAssign Element
|
||||
@@ -130,40 +106,12 @@ func TestELEMENTCorrectnessAgainstBigInt(t *testing.T) {
|
||||
cmpEandB(&eNeg, &bNeg, "Neg")
|
||||
cmpEandB(&eInv, &bInv, "Inv")
|
||||
cmpEandB(&eExp, &bExp, "Exp")
|
||||
|
||||
cmpEandB(&eLsh, &bLsh, "Lsh")
|
||||
|
||||
// legendre symbol
|
||||
if e1.Legendre() != big.Jacobi(b1, modulus) {
|
||||
t.Fatal("legendre symbol computation failed")
|
||||
}
|
||||
if e2.Legendre() != big.Jacobi(b2, modulus) {
|
||||
t.Fatal("legendre symbol computation failed")
|
||||
}
|
||||
|
||||
// these are slow, killing circle ci
|
||||
if n <= 5 {
|
||||
// sqrt
|
||||
var eSqrt, eExp2 Element
|
||||
var bSqrt big.Int
|
||||
bSqrt.ModSqrt(b1, modulus)
|
||||
eSqrt.Sqrt(&e1)
|
||||
cmpEandB(&eSqrt, &bSqrt, "Sqrt")
|
||||
|
||||
bits := b2.Bits()
|
||||
exponent := make([]uint64, len(bits))
|
||||
for k := 0; k < len(bits); k++ {
|
||||
exponent[k] = uint64(bits[k])
|
||||
}
|
||||
eExp2.Exp(e1, exponent...)
|
||||
bExp2.Exp(b1, b2, modulus)
|
||||
cmpEandB(&eExp2, &bExp2, "Exp multi words")
|
||||
}
|
||||
}
|
||||
}
|
||||
|
||||
func TestELEMENTIsRandom(t *testing.T) {
|
||||
for i := 0; i < 50; i++ {
|
||||
for i := 0; i < 1000; i++ {
|
||||
var x, y Element
|
||||
x.SetRandom()
|
||||
y.SetRandom()
|
||||
@@ -177,6 +125,7 @@ func TestELEMENTIsRandom(t *testing.T) {
|
||||
// benchmarks
|
||||
// most benchmarks are rudimentary and should sample a large number of random inputs
|
||||
// or be run multiple times to ensure it didn't measure the fastest path of the function
|
||||
// TODO: clean up and push benchmarking branch
|
||||
|
||||
var benchResElement Element
|
||||
|
||||
@@ -270,15 +219,6 @@ func BenchmarkSquareELEMENT(b *testing.B) {
|
||||
}
|
||||
}
|
||||
|
||||
func BenchmarkSqrtELEMENT(b *testing.B) {
|
||||
var a Element
|
||||
a.SetRandom()
|
||||
b.ResetTimer()
|
||||
for i := 0; i < b.N; i++ {
|
||||
benchResElement.Sqrt(&a)
|
||||
}
|
||||
}
|
||||
|
||||
func BenchmarkMulAssignELEMENT(b *testing.B) {
|
||||
x := Element{
|
||||
1997599621687373223,
|
||||
@@ -292,183 +232,3 @@ func BenchmarkMulAssignELEMENT(b *testing.B) {
|
||||
benchResElement.MulAssign(&x)
|
||||
}
|
||||
}
|
||||
|
||||
func BenchmarkMulAssignASMELEMENT(b *testing.B) {
|
||||
x := Element{
|
||||
1997599621687373223,
|
||||
6052339484930628067,
|
||||
10108755138030829701,
|
||||
150537098327114917,
|
||||
}
|
||||
benchResElement.SetOne()
|
||||
b.ResetTimer()
|
||||
for i := 0; i < b.N; i++ {
|
||||
MulAssignElement(&benchResElement, &x)
|
||||
}
|
||||
}
|
||||
|
||||
func TestELEMENTAsm(t *testing.T) {
|
||||
// ensure ASM implementations matches the ones using math/bits
|
||||
modulus, _ := new(big.Int).SetString("21888242871839275222246405745257275088548364400416034343698204186575808495617", 10)
|
||||
for i := 0; i < 500; i++ {
|
||||
// sample 2 random big int
|
||||
b1, _ := rand.Int(rand.Reader, modulus)
|
||||
b2, _ := rand.Int(rand.Reader, modulus)
|
||||
|
||||
// e1 = mont(b1), e2 = mont(b2)
|
||||
var e1, e2, eTestMul, eMulAssign, eSquare, eTestSquare Element
|
||||
e1.SetBigInt(b1)
|
||||
e2.SetBigInt(b2)
|
||||
|
||||
eTestMul = e1
|
||||
eTestMul.testMulAssign(&e2)
|
||||
eMulAssign = e1
|
||||
eMulAssign.MulAssign(&e2)
|
||||
|
||||
if !eTestMul.Equal(&eMulAssign) {
|
||||
t.Fatal("inconsisntencies between MulAssign and testMulAssign --> check if MulAssign is calling ASM implementaiton on amd64")
|
||||
}
|
||||
|
||||
// square
|
||||
eSquare.Square(&e1)
|
||||
eTestSquare.testSquare(&e1)
|
||||
|
||||
if !eTestSquare.Equal(&eSquare) {
|
||||
t.Fatal("inconsisntencies between Square and testSquare --> check if Square is calling ASM implementaiton on amd64")
|
||||
}
|
||||
}
|
||||
}
|
||||
|
||||
// this is here for consistency purposes, to ensure MulAssign on AMD64 using asm implementation gives consistent results
|
||||
func (z *Element) testMulAssign(x *Element) *Element {
|
||||
|
||||
var t [4]uint64
|
||||
var c [3]uint64
|
||||
{
|
||||
// round 0
|
||||
v := z[0]
|
||||
c[1], c[0] = bits.Mul64(v, x[0])
|
||||
m := c[0] * 14042775128853446655
|
||||
c[2] = madd0(m, 4891460686036598785, c[0])
|
||||
c[1], c[0] = madd1(v, x[1], c[1])
|
||||
c[2], t[0] = madd2(m, 2896914383306846353, c[2], c[0])
|
||||
c[1], c[0] = madd1(v, x[2], c[1])
|
||||
c[2], t[1] = madd2(m, 13281191951274694749, c[2], c[0])
|
||||
c[1], c[0] = madd1(v, x[3], c[1])
|
||||
t[3], t[2] = madd3(m, 3486998266802970665, c[0], c[2], c[1])
|
||||
}
|
||||
{
|
||||
// round 1
|
||||
v := z[1]
|
||||
c[1], c[0] = madd1(v, x[0], t[0])
|
||||
m := c[0] * 14042775128853446655
|
||||
c[2] = madd0(m, 4891460686036598785, c[0])
|
||||
c[1], c[0] = madd2(v, x[1], c[1], t[1])
|
||||
c[2], t[0] = madd2(m, 2896914383306846353, c[2], c[0])
|
||||
c[1], c[0] = madd2(v, x[2], c[1], t[2])
|
||||
c[2], t[1] = madd2(m, 13281191951274694749, c[2], c[0])
|
||||
c[1], c[0] = madd2(v, x[3], c[1], t[3])
|
||||
t[3], t[2] = madd3(m, 3486998266802970665, c[0], c[2], c[1])
|
||||
}
|
||||
{
|
||||
// round 2
|
||||
v := z[2]
|
||||
c[1], c[0] = madd1(v, x[0], t[0])
|
||||
m := c[0] * 14042775128853446655
|
||||
c[2] = madd0(m, 4891460686036598785, c[0])
|
||||
c[1], c[0] = madd2(v, x[1], c[1], t[1])
|
||||
c[2], t[0] = madd2(m, 2896914383306846353, c[2], c[0])
|
||||
c[1], c[0] = madd2(v, x[2], c[1], t[2])
|
||||
c[2], t[1] = madd2(m, 13281191951274694749, c[2], c[0])
|
||||
c[1], c[0] = madd2(v, x[3], c[1], t[3])
|
||||
t[3], t[2] = madd3(m, 3486998266802970665, c[0], c[2], c[1])
|
||||
}
|
||||
{
|
||||
// round 3
|
||||
v := z[3]
|
||||
c[1], c[0] = madd1(v, x[0], t[0])
|
||||
m := c[0] * 14042775128853446655
|
||||
c[2] = madd0(m, 4891460686036598785, c[0])
|
||||
c[1], c[0] = madd2(v, x[1], c[1], t[1])
|
||||
c[2], z[0] = madd2(m, 2896914383306846353, c[2], c[0])
|
||||
c[1], c[0] = madd2(v, x[2], c[1], t[2])
|
||||
c[2], z[1] = madd2(m, 13281191951274694749, c[2], c[0])
|
||||
c[1], c[0] = madd2(v, x[3], c[1], t[3])
|
||||
z[3], z[2] = madd3(m, 3486998266802970665, c[0], c[2], c[1])
|
||||
}
|
||||
|
||||
// if z > q --> z -= q
|
||||
// note: this is NOT constant time
|
||||
if !(z[3] < 3486998266802970665 || (z[3] == 3486998266802970665 && (z[2] < 13281191951274694749 || (z[2] == 13281191951274694749 && (z[1] < 2896914383306846353 || (z[1] == 2896914383306846353 && (z[0] < 4891460686036598785))))))) {
|
||||
var b uint64
|
||||
z[0], b = bits.Sub64(z[0], 4891460686036598785, 0)
|
||||
z[1], b = bits.Sub64(z[1], 2896914383306846353, b)
|
||||
z[2], b = bits.Sub64(z[2], 13281191951274694749, b)
|
||||
z[3], _ = bits.Sub64(z[3], 3486998266802970665, b)
|
||||
}
|
||||
return z
|
||||
}
|
||||
|
||||
// this is here for consistency purposes, to ensure Square on AMD64 using asm implementation gives consistent results
|
||||
func (z *Element) testSquare(x *Element) *Element {
|
||||
|
||||
var p [4]uint64
|
||||
|
||||
var u, v uint64
|
||||
{
|
||||
// round 0
|
||||
u, p[0] = bits.Mul64(x[0], x[0])
|
||||
m := p[0] * 14042775128853446655
|
||||
C := madd0(m, 4891460686036598785, p[0])
|
||||
var t uint64
|
||||
t, u, v = madd1sb(x[0], x[1], u)
|
||||
C, p[0] = madd2(m, 2896914383306846353, v, C)
|
||||
t, u, v = madd1s(x[0], x[2], t, u)
|
||||
C, p[1] = madd2(m, 13281191951274694749, v, C)
|
||||
_, u, v = madd1s(x[0], x[3], t, u)
|
||||
p[3], p[2] = madd3(m, 3486998266802970665, v, C, u)
|
||||
}
|
||||
{
|
||||
// round 1
|
||||
m := p[0] * 14042775128853446655
|
||||
C := madd0(m, 4891460686036598785, p[0])
|
||||
u, v = madd1(x[1], x[1], p[1])
|
||||
C, p[0] = madd2(m, 2896914383306846353, v, C)
|
||||
var t uint64
|
||||
t, u, v = madd2sb(x[1], x[2], p[2], u)
|
||||
C, p[1] = madd2(m, 13281191951274694749, v, C)
|
||||
_, u, v = madd2s(x[1], x[3], p[3], t, u)
|
||||
p[3], p[2] = madd3(m, 3486998266802970665, v, C, u)
|
||||
}
|
||||
{
|
||||
// round 2
|
||||
m := p[0] * 14042775128853446655
|
||||
C := madd0(m, 4891460686036598785, p[0])
|
||||
C, p[0] = madd2(m, 2896914383306846353, p[1], C)
|
||||
u, v = madd1(x[2], x[2], p[2])
|
||||
C, p[1] = madd2(m, 13281191951274694749, v, C)
|
||||
_, u, v = madd2sb(x[2], x[3], p[3], u)
|
||||
p[3], p[2] = madd3(m, 3486998266802970665, v, C, u)
|
||||
}
|
||||
{
|
||||
// round 3
|
||||
m := p[0] * 14042775128853446655
|
||||
C := madd0(m, 4891460686036598785, p[0])
|
||||
C, z[0] = madd2(m, 2896914383306846353, p[1], C)
|
||||
C, z[1] = madd2(m, 13281191951274694749, p[2], C)
|
||||
u, v = madd1(x[3], x[3], p[3])
|
||||
z[3], z[2] = madd3(m, 3486998266802970665, v, C, u)
|
||||
}
|
||||
|
||||
// if z > q --> z -= q
|
||||
// note: this is NOT constant time
|
||||
if !(z[3] < 3486998266802970665 || (z[3] == 3486998266802970665 && (z[2] < 13281191951274694749 || (z[2] == 13281191951274694749 && (z[1] < 2896914383306846353 || (z[1] == 2896914383306846353 && (z[0] < 4891460686036598785))))))) {
|
||||
var b uint64
|
||||
z[0], b = bits.Sub64(z[0], 4891460686036598785, 0)
|
||||
z[1], b = bits.Sub64(z[1], 2896914383306846353, b)
|
||||
z[2], b = bits.Sub64(z[2], 13281191951274694749, b)
|
||||
z[3], _ = bits.Sub64(z[3], 3486998266802970665, b)
|
||||
}
|
||||
return z
|
||||
|
||||
}
|
||||
|
||||
@@ -1,5 +1,13 @@
|
||||
package ff
|
||||
|
||||
import "math/big"
|
||||
|
||||
func NewElement() *Element {
|
||||
return &Element{}
|
||||
}
|
||||
|
||||
func (e *Element) BigInt() *big.Int {
|
||||
b := big.NewInt(0)
|
||||
e.ToBigIntRegular(b)
|
||||
return b
|
||||
}
|
||||
|
||||
Reference in New Issue
Block a user