3

High‐assurance field inversion for curve‐based cryptography

Sun Yimin edited this page 2024-08-21 09:25:48 +08:00

Table of Contents

• 尝试1
• 尝试优化实现：jumpdivstep2等
• Reference

This file contains ambiguous Unicode characters

This file contains Unicode characters that might be confused with other characters. If you think that this is intentional, you can safely ignore this warning. Use the Escape button to reveal them.

尝试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

2. 用divsteps2事先的模求逆并没有比经过addchain优化的模求逆方法性能好。

尝试优化实现：jumpdivstep2等

// TODO

Reference

• High-assurance field inversion for curve-based cryptography
• Fast constant-time gcd and modular inversion
• The safegcd implementation in libsecp256k1 explained
• Use field-element code generated by fiat-crypto to implement ecdsa with curve secp256r1
• https://github.com/mirage/mirage-crypto/blob/main/ec/implementation.mld
• https://github.com/mirage/mirage-crypto/blob/main/ec/native/inversion_template.h