sm2 point scalar multiple ASM implementation issue: final p256PointAddAsm's input maybe equal

[emmansun]

目前p256ScalarMult实现使用了NIST-P256一样的实现，window=5，按照https://github.com/google/boringssl/blob/master/crypto/fipsmodule/ec/util.c 的说明：

// This proof constructs k, so, to show the converse, let k_H = n_H - 2^w,
// k_M = 2^(w-1), k_L = 2^(w-1) - n_L. This will result in a non-trivial point
// doubling in the final addition and is the only such scalar.
//
// COMMON CURVES:
//
// The group orders for common curves end in the following bit patterns:
//
//   P-521: ...00001001; w = 4 is okay
//   P-384: ...01110011; w = 2, 5, 6, 7 are okay
//   P-256: ...01010001; w = 5, 7 are okay
//   P-224: ...00111101; w = 3, 4, 5, 6 are okay

，SM2曲线N = ...00100011，所以，选择w = 5 必然会导致这个问题。
以下是w=5，NIST P256 和SM2的测试及结果：

func TestScalarMultWindow(t *testing.T) {
	for i := int64(-64); i <=64; i++ {
		t.Run(fmt.Sprintf("NIST P256 N%+d", i), func(t *testing.T) {
			testScalarMultWindow(t, nistP256N, new(big.Int).Add(nistP256N, big.NewInt(i)))
		})
		t.Run(fmt.Sprintf("SM2 N%+d", i), func(t *testing.T) {
			testScalarMultWindow(t, sm2n, new(big.Int).Add(sm2n, big.NewInt(i)))
		})
	}
}

func testScalarMultWindow(t *testing.T, n, s *big.Int) {
	byteLen := len(n.Bytes())

	scalar := new(p256OrdElement)
	p256OrdBigToLittle(scalar, toElementArray(s.FillBytes(make([]byte, byteLen))))

	// Start scanning the window from top bit
	index := uint(254)
	var sel, sign int

	wvalue := (scalar[index/64] >> (index % 64)) & 0x3f
	sel, _ = boothW5(uint(wvalue))

	zero := sel

	for index > 4 {
		index -= 5

		if index < 192 {
			wvalue = ((scalar[index/64] >> (index % 64)) + (scalar[index/64+1] << (64 - (index % 64)))) & 0x3f
		} else {
			wvalue = (scalar[index/64] >> (index % 64)) & 0x3f
		}

		sel, _ = boothW5(uint(wvalue))

		zero |= sel
	}
	wvalue = (scalar[0] << 1) & 0x3f
	sel, sign = boothW5(uint(wvalue))
	if new(big.Int).Add(big.NewInt(int64(2*sel)), s).Cmp(n) == 0 && sign != 0 {
		t.Errorf("encounter scalar = n - 2*sel, and sign != 0")
	}
	if new(big.Int).Add(big.NewInt(int64(2*sel)), n).Cmp(s) == 0 && sign == 0 {
		t.Errorf("encounter scalar = n + 2*sel, and sign == 0")
	}
}

结果：

--- FAIL: TestScalarMultWindow (0.00s)
    --- FAIL: TestScalarMultWindow/SM2_N-6 (0.00s)
        sm2p256_asm_test.go:203: encounter scalar = n - 2*sel, and sign != 0
    --- FAIL: TestScalarMultWindow/NIST_P256_N+30 (0.00s)
        sm2p256_asm_test.go:206: encounter scalar = n + 2*sel, and sign == 0
FAIL

w = 6

func TestScalarMultWindow6(t *testing.T) {
	for i := int64(-128); i <= 128; i++ {
		t.Run(fmt.Sprintf("NIST P256 N%+d", i), func(t *testing.T) {
			testScalarMultWindow6(t, nistP256N, new(big.Int).Add(nistP256N, big.NewInt(i)))
		})
		t.Run(fmt.Sprintf("SM2 N%+d", i), func(t *testing.T) {
			testScalarMultWindow6(t, sm2n, new(big.Int).Add(sm2n, big.NewInt(i)))
		})
	}
}

func testScalarMultWindow6(t *testing.T, n, s *big.Int) {
	byteLen := len(n.Bytes())

	scalar := new(p256OrdElement)
	p256OrdBigToLittle(scalar, toElementArray(s.FillBytes(make([]byte, byteLen))))

	// Start scanning the window from top bit
	index := uint(251)
	var sel, sign int

	wvalue := (scalar[index/64] >> (index % 64)) & 0x7f
	sel, _ = boothW6(uint(wvalue))

	zero := sel

	for index > 5 {
		index -= 6

		if index < 192 {
			wvalue = ((scalar[index/64] >> (index % 64)) + (scalar[index/64+1] << (64 - (index % 64)))) & 0x7f
		} else {
			wvalue = (scalar[index/64] >> (index % 64)) & 0x7f
		}

		sel, _ = boothW6(uint(wvalue))

		zero |= sel
	}
	wvalue = (scalar[0] << 1) & 0x7f
	sel, sign = boothW6(uint(wvalue))
	if new(big.Int).Add(big.NewInt(int64(2*sel)), s).Cmp(n) == 0 && sign != 0 {
		t.Errorf("encounter scalar = n - 2*sel, and sign != 0")
	}
	if new(big.Int).Add(big.NewInt(int64(2*sel)), n).Cmp(s) == 0 && sign == 0 {
		t.Errorf("encounter scalar = n + 2*sel, and sign == 0")
	}
}

结果：

--- FAIL: TestScalarMultWindow6 (0.01s)
    --- FAIL: TestScalarMultWindow6/NIST_P256_N-34 (0.00s)
        sm2p256_asm_test.go:252: encounter scalar = n - 2*sel, and sign != 0
    --- FAIL: TestScalarMultWindow6/SM2_N+58 (0.00s)
        sm2p256_asm_test.go:255: encounter scalar = n + 2*sel, and sign == 0
FAIL

所以有两个方案：

1. p256ScalarMult的最后一个p256PointAddAsm改为完整实现：7f54c1e
2. p256ScalarMult方法改为w=6，并且ScalarMult/SacalarBaseMult中都对scalar进行处理，使之小于N。de14139