Skip to content

High‐assurance field inversion for curve‐based cryptography

Jump to bottom
Sun Yimin edited this page Aug 21, 2024 · 3 revisions

尝试1

使用fiat-crypto生成的代码，来事先模求逆： 代码片段1是原有的通过addchain生成的模求逆：

// Invert sets e = 1/x, and returns e.
//
// If x == 0, Invert returns e = 0.
func (e *SM2P256Element) Invert(x *SM2P256Element) *SM2P256Element {
	// Inversion is implemented as exponentiation with exponent p − 2.
	// The sequence of 14 multiplications and 255 squarings is derived from the
	// following addition chain generated with github.com/mmcloughlin/addchain v0.4.0.
	//
	//	_10      = 2*1
	//	_11      = 1 + _10
	//	_110     = 2*_11
	//	_111     = 1 + _110
	//	_111000  = _111 << 3
	//	_111111  = _111 + _111000
	//	_1111110 = 2*_111111
	//	_1111111 = 1 + _1111110
	//	x12      = _1111110 << 5 + _111111
	//	x24      = x12 << 12 + x12
	//	x31      = x24 << 7 + _1111111
	//	i39      = x31 << 2
	//	i68      = i39 << 29
	//	x62      = x31 + i68
	//	i71      = i68 << 2
	//	x64      = i39 + i71 + _11
	//	i265     = ((i71 << 32 + x64) << 64 + x64) << 94
	//	return     (x62 + i265) << 2 + 1
	//
	var z = new(SM2P256Element).Set(e)
	var t0 = new(SM2P256Element)
	var t1 = new(SM2P256Element)
	var t2 = new(SM2P256Element)

	z.Square(x)
	t0.Mul(x, z)
	z.Square(t0)
	z.Mul(x, z)
	t1.Square(z)
	for s := 1; s < 3; s++ {
		t1.Square(t1)
	}
	t1.Mul(z, t1)
	t2.Square(t1)
	z.Mul(x, t2)
	for s := 0; s < 5; s++ {
		t2.Square(t2)
	}
	t1.Mul(t1, t2)
	t2.Square(t1)
	for s := 1; s < 12; s++ {
		t2.Square(t2)
	}
	t1.Mul(t1, t2)
	for s := 0; s < 7; s++ {
		t1.Square(t1)
	}
	z.Mul(z, t1)
	t2.Square(z)
	for s := 1; s < 2; s++ {
		t2.Square(t2)
	}
	t1.Square(t2)
	for s := 1; s < 29; s++ {
		t1.Square(t1)
	}
	z.Mul(z, t1)
	for s := 0; s < 2; s++ {
		t1.Square(t1)
	}
	t2.Mul(t2, t1)
	t0.Mul(t0, t2)
	for s := 0; s < 32; s++ {
		t1.Square(t1)
	}
	t1.Mul(t0, t1)
	for s := 0; s < 64; s++ {
		t1.Square(t1)
	}
	t0.Mul(t0, t1)
	for s := 0; s < 94; s++ {
		t0.Square(t0)
	}
	z.Mul(z, t0)
	for s := 0; s < 2; s++ {
		z.Square(z)
	}
	z.Mul(x, z)
	return e.Set(z)
}

代码片段2通过safegcd介绍的最基本方法模求逆：

// Reference https://github.com/mit-plv/fiat-crypto/blob/master/inversion/c/inversion_template.c
func P256Inverse(g *[4]uint64) *[4]uint64 {
	var precomp, v, out4, out5 [4]uint64
	var d, out1 uint64
	var f, out2, out3, gs [5]uint64
	var r sm2p256MontgomeryDomainFieldElement
	r1 := (*[4]uint64)(&r)
	sm2p256DivstepPrecomp(&precomp)
	sm2p256Msat(&f)
	sm2p256SetOne(&r)

	for i := 0; i < 4; i++ {
		gs[i] = g[i]
	}

	// 370 = (256 * 49 + 57) / 17 - 1
	for i := 0; i < 370; i++ {
		sm2p256Divstep(&out1, &out2, &out3, &out4, &out5, d, &f, &gs, &v, r1)
		sm2p256Divstep(&d, &f, &gs, &v, r1, out1, &out2, &out3, &out4, &out5)
	}

	sm2p256Divstep(&out1, &out2, &out3, &out4, &out5, d, &f, &gs, &v, r1)
	for i := 0; i < 4; i++ {
		v[i] = out4[i]
		f[i] = out2[i]
	}
	f[4] = out2[4]

	var out sm2p256MontgomeryDomainFieldElement
	sm2p256Opp(&out, (*sm2p256MontgomeryDomainFieldElement)(&v))
	sm2p256Selectznz(&v, (sm2p256Uint1)(f[4]>>63), &v, (*[4]uint64)(&out))

	sm2p256Mul(&out, (*sm2p256MontgomeryDomainFieldElement)(&v), (*sm2p256MontgomeryDomainFieldElement)(&precomp))
	return (*[4]uint64)(&out)
}

以下是测试代码：

package fiat

import (
	"encoding/hex"
	"testing"
)


var testValues = []string{
	"0000000000000000000000000000000000000000000000000000000000000001",
	"0000000000000000000000000000000000000000000000000000000000000002",
	"0000000000000000000000000000000000000000000000000000000000000003",
	"1000000000000000000000000000000000000000000000000000000000000000",
	"1000000000000000000000000000000000000000000000000000000000000001",
	"1000000000000000000000000000000000000000000000000000000000000002",
	"1000000000000000000000000000000000000000000000000000000000000003",
	"8356e642a40ebd18d29ba3532fbd9f3bbee8f027c3f6f39a5ba2f870369f9988",
	"981f5efe55d1c5cdf6c0ef2b070847a14f7fdf4272a8df09c442f3058af94ba1",
	"d6833540d019e0438a5dd73b414f26ab43d8064b99671206944e284dbd969093",
	"6c5a0a0b2eed3cbec3e4f1252bfe0e28c504a1c6bf1999eebb0af9ef0f8e6c85",
}

func TestP256Inverse(t *testing.T) {
	for _, v := range testValues {
		vBytes, _ := hex.DecodeString(v)

		in, err := new(SM2P256Element).SetBytes(vBytes)
		if err != nil {
			t.Errorf("SetBytes failed: %v", err)
		}
		in2 := *(*[4]uint64)(&in.x)
		out1 := new(SM2P256Element).Invert(in)
		out1r := (*[4]uint64)(&out1.x)
		out2 := P256Inverse(&in2)
		tmp := (*sm2p256NonMontgomeryDomainFieldElement)(out2)
		out3 := new(sm2p256MontgomeryDomainFieldElement)
		sm2p256ToMontgomery(out3, tmp)
		if *out3 != *out1r  {
			t.Errorf("got %v, want %v", out3, &out1.x)
		}
	}
}

func BenchmarkP256Inverse(b *testing.B) {
	vBytes, _ := hex.DecodeString(testValues[0])

	in, _ := new(SM2P256Element).SetBytes(vBytes)
	in2 := *(*[4]uint64)(&in.x)
	b.ReportAllocs()
	b.ResetTimer()
	for i := 0; i < b.N; i++ {
		P256Inverse(&in2)
	}
}

func BenchmarkInvert(b *testing.B) {
	vBytes, _ := hex.DecodeString(testValues[0])

	in, _ := new(SM2P256Element).SetBytes(vBytes)
	out := new(SM2P256Element)
	b.ReportAllocs()
	b.ResetTimer()
	for i := 0; i < b.N; i++ {
		out.Invert(in)
	}
}
  1. 还有就是fiat-cyrpto目前的实现，输入、输出有些小问题：输入是蒙哥马利型，输出是非蒙哥马利型；输入是非蒙哥马利型，输出是蒙哥马利型。这个是已知问题。https://github.com/mit-plv/fiat-crypto/issues/1020 
goos: windows
goarch: amd64
pkg: github.com/emmansun/gmsm/internal/sm2ec/fiat
cpu: Intel(R) Core(TM) i5-9500 CPU @ 3.00GHz
BenchmarkInvert
BenchmarkInvert-6
  227496	      5806 ns/op	       0 B/op	       0 allocs/op
PASS
ok  	github.com/emmansun/gmsm/internal/sm2ec/fiat	1.792s

goos: windows
goarch: amd64
pkg: github.com/emmansun/gmsm/internal/sm2ec/fiat
cpu: Intel(R) Core(TM) i5-9500 CPU @ 3.00GHz
BenchmarkP256Inverse
BenchmarkP256Inverse-6
   58394	     20644 ns/op	      32 B/op	       1 allocs/op
PASS
ok  	github.com/emmansun/gmsm/internal/sm2ec/fiat	1.793s
  1. 用divsteps2事先的模求逆并没有比经过addchain优化的模求逆方法性能好。

尝试优化实现：jumpdivstep2等

// TODO

Reference

Clone this wiki locally