Fused modular square root on 32-bit - wrong "isSquare" result

[mratsim]

constantine/tests/test_ec_weierstrass_projective_g1.nim

Lines 105 to 155 in 3d1b1fa

	test "EC add is associative":
	proc test(F: typedesc, randZ: static bool) =
	for _ in 0 ..< Iters:
	when randZ:
	let a = rng.random_unsafe_with_randZ(ECP_SWei_Proj[F])
	let b = rng.random_unsafe_with_randZ(ECP_SWei_Proj[F])
	let c = rng.random_unsafe_with_randZ(ECP_SWei_Proj[F])
	else:
	let a = rng.random_unsafe(ECP_SWei_Proj[F])
	let b = rng.random_unsafe(ECP_SWei_Proj[F])
	let c = rng.random_unsafe(ECP_SWei_Proj[F])
	var tmp1{.noInit.}, tmp2{.noInit.}: ECP_SWei_Proj[F]
	# r0 = (a + b) + c
	tmp1.sum(a, b)
	tmp2.sum(tmp1, c)
	let r0 = tmp2
	# r1 = a + (b + c)
	tmp1.sum(b, c)
	tmp2.sum(a, tmp1)
	let r1 = tmp2
	# r2 = (a + c) + b
	tmp1.sum(a, c)
	tmp2.sum(tmp1, b)
	let r2 = tmp2
	# r3 = a + (c + b)
	tmp1.sum(c, b)
	tmp2.sum(a, tmp1)
	let r3 = tmp2
	# r4 = (c + a) + b
	tmp1.sum(c, a)
	tmp2.sum(tmp1, b)
	let r4 = tmp2
	# ...
	check:
	bool(r0 == r1)
	bool(r0 == r2)
	bool(r0 == r3)
	bool(r0 == r4)
	test(Fp[BN254_Snarks], randZ = false)
	test(Fp[BN254_Snarks], randZ = true)
	test(Fp[BLS12_381], randZ = false)
	test(Fp[BLS12_381], randZ = true)

https://travis-ci.com/github/mratsim/constantine/jobs/345566834#L1059

seed: 1591548864

[mratsim]

The bug was that somehow the RNG was able to create a random point that was not on the curve.

Point config

import
  # Internals
  ../constantine/config/[common, curves],
  ../constantine/arithmetic,
  ../constantine/io/[io_bigints, io_ec],
  ../constantine/elliptic/[ec_weierstrass_affine, ec_weierstrass_projective]

proc test() =

  var a: ECP_SWei_Proj[Fp[BLS12_381]]
  var b: ECP_SWei_Proj[Fp[BLS12_381]]
  var c: ECP_SWei_Proj[Fp[BLS12_381]]

  doAssert a.fromHex( # This is not on the curve
    x = "0x0426d6f73952e652c229561b9718b76593b60cd9e44aa1f83b4531bb9e6b20a8a959735ac483dbd92dfe48b2ce937987",
    y = "0x025366df8ed339c3e3f8f0a826a24c04343f78c0ec865d56ff1d4718206749a5e07dcb9785520d0f85d4ef209493b41b"
  )
  doAssert b.fromHex(
    x = "0x0d544f56919ea56b16eef9066713331ea54f43ee0d8853d5952847a15694a17d5f21eb9f067e39b3701bebc649ba518a",
    y = "0x0b877f4a58dc1ce70ce9c9d56a536b5cfdff5460b0df60849c9155de252ea25f103f98ac3f9789ffb3d813fe31c3097c",
  )
  doAssert c.fromHex(
    x = "0x065a5dd4ca6a8aba7dc41c8747a99632d6de2f0f3e53899dba906013b3cf2e29a64d7706137b9cf540780235e27035fb",
    y = "0x034c4bd6e37c275f2f7237af190c87e445f624c44b60d0d583c906b2756875e739fd3cc545719b4731577724730571e5"
  )

  var tmp1{.noInit.}, tmp2{.noInit.}: ECP_SWei_Proj[Fp[BLS12_381]]

  # r0 = (a + b) + c
  tmp1.sum(a, b)
  tmp2.sum(tmp1, c)
  let r0 = tmp2

  # r1 = a + (b + c)
  tmp1.sum(b, c)
  tmp2.sum(a, tmp1)
  let r1 = tmp2

  # r2 = (a + c) + b
  tmp1.sum(a, c)
  tmp2.sum(tmp1, b)
  let r2 = tmp2

  # r3 = a + (c + b)
  tmp1.sum(c, b)
  tmp2.sum(a, tmp1)
  let r3 = tmp2

  # r4 = (c + a) + b
  tmp1.sum(c, a)
  tmp2.sum(tmp1, b)
  let r4 = tmp2

  # ...

  doAssert bool(r0 == r1)
  doAssert bool(r0 == r2)
  doAssert bool(r0 == r3)
  doAssert bool(r0 == r4)

test()

[mratsim]

The isSquare and sqrt_if_square are returning different results:

import
  # Internals
  ../constantine/config/[common, curves],
  ../constantine/arithmetic,
  ../constantine/io/[io_bigints, io_fields, io_ec],
  ../constantine/elliptic/[ec_weierstrass_affine, ec_weierstrass_projective]

var f: Fp[BLS12_381]

f.fromHex("0x184d02ce4f24d5e59b4150a57a31b202fd40a4b41d7518c22b84bee475fbcb7763100448ef6b17a6ea603cf062e5db51")

echo bool(f.isSquare()) # false
let wasSquare = f.sqrt_if_square_p3mod4()
echo bool(wasSquare) # true <--- only in 32-bit, carry bug?
echo "f sqrt: ", f.toHex()