BigInteger.ModPow asserting in SubtractSelf

[bartonjs]

Description

Trying to use BigInteger for test authoring is currently impeded by it asserting.

Reproduction Steps

byte[] buf = new byte[2048 >> 3];
buf[1] = 2;
buf.AsSpan(2, 8).Fill(1);
BigInteger m = new BigInteger(buf, true, true);
BigInteger e = 65537;

buf = new byte[]
{
    0xB1, 0x7C, 0xEE, 0x77, 0xB4, 0x59, 0xA4, 0x65,
    0x92, 0x8D, 0x7F, 0x55, 0x77, 0x80, 0x39, 0xBA,
    0x22, 0xBA, 0x29, 0xA5, 0xFF, 0xE5, 0x53, 0xFB,
    0x40, 0x98, 0xA8, 0x35, 0xE5, 0x2D, 0x0A, 0xDC,
    0x85, 0x17, 0x6E, 0xE4, 0xD6, 0x93, 0x82, 0x20,
    0x71, 0x8D, 0xE9, 0xDD, 0xC9, 0xD5, 0xBD, 0x30,
    0x47, 0xEE, 0x59, 0xB9, 0xE6, 0xA8, 0x79, 0x9E,
    0x47, 0x96, 0x8E, 0x63, 0xCD, 0xA6, 0x28, 0x9D,
    0x7B, 0x6D, 0x83, 0xAA, 0x68, 0xE2, 0x46, 0xD6,
    0x1C, 0x8C, 0x2B, 0xA1, 0xC4, 0x04, 0x12, 0xAE,
    0x61, 0x07, 0xAF, 0x6F, 0xE9, 0x2B, 0x48, 0x5C,
    0xCA, 0xC2, 0x0E, 0x52, 0x71, 0x21, 0x03, 0xE0,
    0x05, 0x1C, 0x07, 0xC0, 0x56, 0xFD, 0x8A, 0x61,
    0x7A, 0x95, 0x39, 0x4B, 0xAA, 0x5A, 0x9D, 0x03,
    0x6D, 0x7A, 0x51, 0x3E, 0x7A, 0xE4, 0xAB, 0xED,
    0xB4, 0x0A, 0x88, 0x80, 0x3C, 0x07, 0xED, 0x19,
    0x21, 0xA2, 0xDC, 0xD7, 0x9C, 0x3F, 0x3B, 0x19,
    0x59, 0x33, 0x39, 0x8A, 0x25, 0xDB, 0xCE, 0x8D,
    0x8E, 0x10, 0xDA, 0xB1, 0x38, 0x32, 0xCA, 0x59,
    0xA1, 0x69, 0x3C, 0x23, 0x76, 0x50, 0x37, 0xB3,
    0xBF, 0x73, 0x58, 0x77, 0x38, 0xC5, 0x16, 0x03,
    0x60, 0x36, 0x0D, 0x31, 0x8C, 0xBE, 0xA5, 0x12,
    0x2F, 0xE5, 0x16, 0xAD, 0x1C, 0x80, 0x01, 0x50,
    0xEB, 0x3C, 0x86, 0x79, 0x22, 0xD3, 0x7F, 0xD4,
    0x90, 0x85, 0xB8, 0xEB, 0xB0, 0x7D, 0xD8, 0xC8,
    0x8B, 0xBB, 0x88, 0xBE, 0xFE, 0xB8, 0xBA, 0xAD,
    0x61, 0xC7, 0xF9, 0x68, 0x20, 0xB2, 0xA9, 0x1D,
    0xB4, 0xDC, 0xB0, 0x5B, 0xC7, 0xB3, 0xF2, 0x83,
    0x35, 0x43, 0xB0, 0xAE, 0x19, 0x2B, 0xA6, 0xFA,
    0x88, 0x48, 0xB9, 0xFB, 0xB3, 0xCD, 0xF8, 0xA9,
    0x9C, 0x20, 0x6F, 0x63, 0x23, 0xE5, 0xC2, 0x85,
    0xCD, 0x75, 0x7A, 0x55, 0x04, 0xA4, 0x08, 0x99,
};

BigInteger n = new BigInteger(buf, true, true);
BigInteger c = BigInteger.ModPow(m, e, n);

Expected behavior

No assertion.

Actual behavior

Process terminated. Assertion failed.
     at System.Numerics.BigIntegerCalculator.SubtractSelf(Span`1 left, ReadOnly
  Span`1 right) in C:\git\bartonjs\runtime.3\src\libraries\System.Runtime.Numer
  ics\src\System\Numerics\BigIntegerCalculator.AddSub.cs:line 135
     at System.Numerics.BigIntegerCalculator.FastReducer.SubMod(Span`1 left, Re
  adOnlySpan`1 right, ReadOnlySpan`1 modulus, Int32 k) in C:\git\bartonjs\runti
  me.3\src\libraries\System.Runtime.Numerics\src\System\Numerics\BigIntegerCalc
  ulator.FastReducer.cs:line 114
     at System.Numerics.BigIntegerCalculator.FastReducer.Reduce(Span`1 value) i
  n C:\git\bartonjs\runtime.3\src\libraries\System.Runtime.Numerics\src\System\
  Numerics\BigIntegerCalculator.FastReducer.cs:line 61
     at System.Numerics.BigIntegerCalculator.PowCore(Span`1 value, Int32 valueL
  ength, UInt32 power, FastReducer& reducer, Span`1 result, Int32 resultLength,
   Span`1 temp) in C:\git\bartonjs\runtime.3\src\libraries\System.Runtime.Numer
  ics\src\System\Numerics\BigIntegerCalculator.PowMod.cs:line 539
     at System.Numerics.BigIntegerCalculator.PowCore(Span`1 value, Int32 valueL
  ength, UInt32 power, ReadOnlySpan`1 modulus, Span`1 temp, Span`1 bits) in C:\
  git\bartonjs\runtime.3\src\libraries\System.Runtime.Numerics\src\System\Numer
  ics\BigIntegerCalculator.PowMod.cs:line 416
     at System.Numerics.BigIntegerCalculator.Pow(ReadOnlySpan`1 value, UInt32 p
  ower, ReadOnlySpan`1 modulus, Span`1 bits) in C:\git\bartonjs\runtime.3\src\l
  ibraries\System.Runtime.Numerics\src\System\Numerics\BigIntegerCalculator.Pow
  Mod.cs:line 243
     at System.Numerics.BigInteger.ModPow(BigInteger value, BigInteger exponent
  , BigInteger modulus) in C:\git\bartonjs\runtime.3\src\libraries\System.Runti
  me.Numerics\src\System\Numerics\BigInteger.cs:line 1005

Regression?

No response

Known Workarounds

No response

Configuration

No response

Other information

Definitely happens on bc0b28f on both osx and win. The osx build merged up through 3bf9bee (main as of about an hour ago) and still sees the assert.

Tagging subscribers to this area: @dotnet/area-system-numerics
See info in area-owners.md if you want to be subscribed.

Issue Details

---

Description

Trying to use BigInteger for test authoring is currently impeded by it asserting.

Reproduction Steps

byte[] buf = new byte[2048 >> 3];
buf[1] = 2;
buf.AsSpan(2, 8).Fill(1);
BigInteger m = new BigInteger(buf, true, true);
BigInteger e = 65537;

buf = new byte[]
{
    0xB1, 0x7C, 0xEE, 0x77, 0xB4, 0x59, 0xA4, 0x65,
    0x92, 0x8D, 0x7F, 0x55, 0x77, 0x80, 0x39, 0xBA,
    0x22, 0xBA, 0x29, 0xA5, 0xFF, 0xE5, 0x53, 0xFB,
    0x40, 0x98, 0xA8, 0x35, 0xE5, 0x2D, 0x0A, 0xDC,
    0x85, 0x17, 0x6E, 0xE4, 0xD6, 0x93, 0x82, 0x20,
    0x71, 0x8D, 0xE9, 0xDD, 0xC9, 0xD5, 0xBD, 0x30,
    0x47, 0xEE, 0x59, 0xB9, 0xE6, 0xA8, 0x79, 0x9E,
    0x47, 0x96, 0x8E, 0x63, 0xCD, 0xA6, 0x28, 0x9D,
    0x7B, 0x6D, 0x83, 0xAA, 0x68, 0xE2, 0x46, 0xD6,
    0x1C, 0x8C, 0x2B, 0xA1, 0xC4, 0x04, 0x12, 0xAE,
    0x61, 0x07, 0xAF, 0x6F, 0xE9, 0x2B, 0x48, 0x5C,
    0xCA, 0xC2, 0x0E, 0x52, 0x71, 0x21, 0x03, 0xE0,
    0x05, 0x1C, 0x07, 0xC0, 0x56, 0xFD, 0x8A, 0x61,
    0x7A, 0x95, 0x39, 0x4B, 0xAA, 0x5A, 0x9D, 0x03,
    0x6D, 0x7A, 0x51, 0x3E, 0x7A, 0xE4, 0xAB, 0xED,
    0xB4, 0x0A, 0x88, 0x80, 0x3C, 0x07, 0xED, 0x19,
    0x21, 0xA2, 0xDC, 0xD7, 0x9C, 0x3F, 0x3B, 0x19,
    0x59, 0x33, 0x39, 0x8A, 0x25, 0xDB, 0xCE, 0x8D,
    0x8E, 0x10, 0xDA, 0xB1, 0x38, 0x32, 0xCA, 0x59,
    0xA1, 0x69, 0x3C, 0x23, 0x76, 0x50, 0x37, 0xB3,
    0xBF, 0x73, 0x58, 0x77, 0x38, 0xC5, 0x16, 0x03,
    0x60, 0x36, 0x0D, 0x31, 0x8C, 0xBE, 0xA5, 0x12,
    0x2F, 0xE5, 0x16, 0xAD, 0x1C, 0x80, 0x01, 0x50,
    0xEB, 0x3C, 0x86, 0x79, 0x22, 0xD3, 0x7F, 0xD4,
    0x90, 0x85, 0xB8, 0xEB, 0xB0, 0x7D, 0xD8, 0xC8,
    0x8B, 0xBB, 0x88, 0xBE, 0xFE, 0xB8, 0xBA, 0xAD,
    0x61, 0xC7, 0xF9, 0x68, 0x20, 0xB2, 0xA9, 0x1D,
    0xB4, 0xDC, 0xB0, 0x5B, 0xC7, 0xB3, 0xF2, 0x83,
    0x35, 0x43, 0xB0, 0xAE, 0x19, 0x2B, 0xA6, 0xFA,
    0x88, 0x48, 0xB9, 0xFB, 0xB3, 0xCD, 0xF8, 0xA9,
    0x9C, 0x20, 0x6F, 0x63, 0x23, 0xE5, 0xC2, 0x85,
    0xCD, 0x75, 0x7A, 0x55, 0x04, 0xA4, 0x08, 0x99,
};

BigInteger n = new BigInteger(buf, true, true);
BigInteger c = BigInteger.ModPow(m, e, n);

Expected behavior

No assertion.

Actual behavior

Process terminated. Assertion failed.
     at System.Numerics.BigIntegerCalculator.SubtractSelf(Span`1 left, ReadOnly
  Span`1 right) in C:\git\bartonjs\runtime.3\src\libraries\System.Runtime.Numer
  ics\src\System\Numerics\BigIntegerCalculator.AddSub.cs:line 135
     at System.Numerics.BigIntegerCalculator.FastReducer.SubMod(Span`1 left, Re
  adOnlySpan`1 right, ReadOnlySpan`1 modulus, Int32 k) in C:\git\bartonjs\runti
  me.3\src\libraries\System.Runtime.Numerics\src\System\Numerics\BigIntegerCalc
  ulator.FastReducer.cs:line 114
     at System.Numerics.BigIntegerCalculator.FastReducer.Reduce(Span`1 value) i
  n C:\git\bartonjs\runtime.3\src\libraries\System.Runtime.Numerics\src\System\
  Numerics\BigIntegerCalculator.FastReducer.cs:line 61
     at System.Numerics.BigIntegerCalculator.PowCore(Span`1 value, Int32 valueL
  ength, UInt32 power, FastReducer& reducer, Span`1 result, Int32 resultLength,
   Span`1 temp) in C:\git\bartonjs\runtime.3\src\libraries\System.Runtime.Numer
  ics\src\System\Numerics\BigIntegerCalculator.PowMod.cs:line 539
     at System.Numerics.BigIntegerCalculator.PowCore(Span`1 value, Int32 valueL
  ength, UInt32 power, ReadOnlySpan`1 modulus, Span`1 temp, Span`1 bits) in C:\
  git\bartonjs\runtime.3\src\libraries\System.Runtime.Numerics\src\System\Numer
  ics\BigIntegerCalculator.PowMod.cs:line 416
     at System.Numerics.BigIntegerCalculator.Pow(ReadOnlySpan`1 value, UInt32 p
  ower, ReadOnlySpan`1 modulus, Span`1 bits) in C:\git\bartonjs\runtime.3\src\l
  ibraries\System.Runtime.Numerics\src\System\Numerics\BigIntegerCalculator.Pow
  Mod.cs:line 243
     at System.Numerics.BigInteger.ModPow(BigInteger value, BigInteger exponent
  , BigInteger modulus) in C:\git\bartonjs\runtime.3\src\libraries\System.Runti
  me.Numerics\src\System\Numerics\BigInteger.cs:line 1005

Regression?

No response

Known Workarounds

No response

Configuration

No response

Other information

Definitely happens on bc0b28f on both osx and win. The osx build merged up through 3bf9bee (main as of about an hour ago) and still sees the assert.

Author:	bartonjs
Assignees:	-
Labels:	area-System.Numerics, untriaged
Milestone:	-

[jeffhandley]

Tentatively marked this as 9.0.0. If it's not fully blocking though, we'll move it to Future.

[bartonjs]

This is blocking test authoring for #97738; so, yes, it's "fully blocking"

[eiriktsarpalis]

It appears that there is a flaw in the SubMod implementation in the "FastReducer" algorithm:

runtime/src/libraries/System.Runtime.Numerics/src/System/Numerics/BigIntegerCalculator.FastReducer.cs

Lines 102 to 114 in 9367edc

	private static int SubMod(Span<uint> left, ReadOnlySpan<uint> right, ReadOnlySpan<uint> modulus, int k)
	{
	// Executes the subtraction algorithm for left and right,
	// but considers only the first k limbs, which is equivalent to
	// preceding reduction by 2^(32*k). Furthermore, if left is
	// still greater than modulus, further subtractions are used.
	if (left.Length > k)
	left = left.Slice(0, k);
	if (right.Length > k)
	right = right.Slice(0, k);
	SubtractSelf(left, right);

in that it incorrectly assumes that left is greater than or equal to right after truncating to the k least significant digits of the representation. The FastReducer was introduced as a performance optimization in dotnet/corefx#2182.

Minimal Reproduction

BigInteger modulus = (BigInteger)3 << 1024;
BigInteger value = modulus;
int exponent = 2;

BigInteger.ModPow(value, exponent, value); // Assertion failure in debug builds

It should be noted that superficially, the result appears to be correct using the following validation logic:

BigInteger result = BigInteger.ModPow(value, exponent, modulus);

BigInteger expectedResult = 1;
for (int i = 0; i < exponent; i++)
{
    expectedResult = (expectedResult * value) % modulus;
}

Assert.Equal(expectedResult, result); // Passes for given inputs

However, I don't think it would be safe to simply comment out the asserts. The SubtractSelf algorithm --where the assertion is failing-- has not been designed for cases where left < right:

runtime/src/libraries/System.Runtime.Numerics/src/System/Numerics/BigIntegerCalculator.AddSub.cs

Lines 132 to 162 in 9367edc

	private static void SubtractSelf(Span<uint> left, ReadOnlySpan<uint> right)
	{
	Debug.Assert(left.Length >= right.Length);
	Debug.Assert(Compare(left, right) >= 0);
	int i = 0;
	long carry = 0L;
	// Switching to managed references helps eliminating
	// index bounds check...
	ref uint leftPtr = ref MemoryMarshal.GetReference(left);
	// Executes the "grammar-school" algorithm for computing z = a - b.
	// Same as above, but we're writing the result directly to a and
	// stop execution, if we're out of b and c is already 0.
	for (; i < right.Length; i++)
	{
	long digit = (Unsafe.Add(ref leftPtr, i) + carry) - right[i];
	Unsafe.Add(ref leftPtr, i) = unchecked((uint)digit);
	carry = digit >> 32;
	}
	for (; carry != 0 && i < left.Length; i++)
	{
	long digit = left[i] + carry;
	left[i] = (uint)digit;
	carry = digit >> 32;
	}
	Debug.Assert(carry == 0);
	}

The final assert checking that carry == 0 also ends up failing. It isn't clear to me whether the final result is accidentally correct for the particular examined inputs or because it happens to work with the invariants required by this particular implementation of Barrett's algorithm.

[eiriktsarpalis]

I fuzzed the .NET 8 implementation with FsCheck, using parameters that trigger the assert failing:

using FsCheck;
using FsCheck.Fluent;
using System.Numerics;

Config configuration = Config.Quick.WithMaxTest(10_000_000);

Parallel.For(0, Environment.ProcessorCount, i =>
{
    Prop.ForAll<(int, int, byte)>(t => ModPowPropertyTest(t.Item1, t.Item2, t.Item3))
        .Check(configuration);
});

static bool ModPowPropertyTest(int valueSeed, int modulusSpread, ushort exponent)
{
    if (Math.Abs(valueSeed) < 2 || exponent < 2)
    {
        return true; // Skip trivial values
    }

    // Arrange
    BigInteger value = (BigInteger)valueSeed << 1024; // To trigger the bug, uint[] representation needs to start with at least 32 zeros.
    BigInteger modulus = value + modulusSpread; // The modulus must be approximately the same size as the value.

    // Act
    BigInteger result = BigInteger.ModPow(value, exponent, modulus);

    // Assert
    BigInteger expectedResult = 1;
    for (int i = 0; i < exponent; i++)
    {
        expectedResult = (expectedResult * value) % modulus;
    }

    return expectedResult == result;
}

After 160 million runs, no invalid outputs were detected. @jeffhandley I think we could try removing the asserts to unblock @bartonjs's work.

[bartonjs]

BigInteger value = (BigInteger)valueSeed << 1024; // To trigger the bug, uint[] representation needs to start with at least 32 zeros.

If keeping a bit set in the least significant segment works around the problem, I'll give that a go.

[bartonjs]

It seems to be more nuanced than just keeping a low bit set, since the number described by

byte[] buf = new byte[2048 >> 3];
buf[1] = 2;
buf.AsSpan(2, 8).Fill(1);
buf[^1] = 1;

still asserted; but 00 02 01 01 01 01 ... 01 01 01 01 didn't). So it's probably a "can't have a chunk of all zeros" where chunk is, presumably, defined.

[bartonjs]

byte[] buf = new byte[2048 >> 3];
buf[1] = 2;
buf.AsSpan(2, 8).Fill(1);

yields

 Process terminated. Assertion failed.
     at System.Numerics.BigIntegerCalculator.SubtractSelf(Span`1 left, ReadOnly
  Span`1 right) in C:\git\bartonjs\runtime.3\src\libraries\System.Runtime.Numer
  ics\src\System\Numerics\BigIntegerCalculator.AddSub.cs:line 135
     at System.Numerics.BigIntegerCalculator.FastReducer.SubMod(Span`1 left, Re
  adOnlySpan`1 right, ReadOnlySpan`1 modulus, Int32 k) in C:\git\bartonjs\runti
  me.3\src\libraries\System.Runtime.Numerics\src\System\Numerics\BigIntegerCalc
  ulator.FastReducer.cs:line 114
     at System.Numerics.BigIntegerCalculator.FastReducer.Reduce(Span`1 value) i
  n C:\git\bartonjs\runtime.3\src\libraries\System.Runtime.Numerics\src\System\
  Numerics\BigIntegerCalculator.FastReducer.cs:line 61
     at System.Numerics.BigIntegerCalculator.PowCore(Span`1 value, Int32 valueL
  ength, UInt32 power, FastReducer& reducer, Span`1 result, Int32 resultLength,
   Span`1 temp) in C:\git\bartonjs\runtime.3\src\libraries\System.Runtime.Numer
  ics\src\System\Numerics\BigIntegerCalculator.PowMod.cs:line 539
     at System.Numerics.BigIntegerCalculator.PowCore(Span`1 value, Int32 valueL
  ength, UInt32 power, ReadOnlySpan`1 modulus, Span`1 temp, Span`1 bits) in C:\
  git\bartonjs\runtime.3\src\libraries\System.Runtime.Numerics\src\System\Numer
  ics\BigIntegerCalculator.PowMod.cs:line 416
     at System.Numerics.BigIntegerCalculator.Pow(ReadOnlySpan`1 value, UInt32 p
  ower, ReadOnlySpan`1 modulus, Span`1 bits) in C:\git\bartonjs\runtime.3\src\l
  ibraries\System.Runtime.Numerics\src\System\Numerics\BigIntegerCalculator.Pow
  Mod.cs:line 243
     at System.Numerics.BigInteger.ModPow(BigInteger value, BigInteger exponent
  , BigInteger modulus) in C:\git\bartonjs\runtime.3\src\libraries\System.Runti
  me.Numerics\src\System\Numerics\BigInteger.cs:line 1005

adding in buf[^1] = 1

yields

  Process terminated. Assertion failed.
     at System.Numerics.BigIntegerCalculator.SubtractSelf(Span`1 left, ReadOnly
  Span`1 right) in C:\git\bartonjs\runtime.3\src\libraries\System.Runtime.Numer
  ics\src\System\Numerics\BigIntegerCalculator.AddSub.cs:line 135
     at System.Numerics.BigIntegerCalculator.FastReducer.SubMod(Span`1 left, Re
  adOnlySpan`1 right, ReadOnlySpan`1 modulus, Int32 k) in C:\git\bartonjs\runti
  me.3\src\libraries\System.Runtime.Numerics\src\System\Numerics\BigIntegerCalc
  ulator.FastReducer.cs:line 114
     at System.Numerics.BigIntegerCalculator.FastReducer.Reduce(Span`1 value) i
  n C:\git\bartonjs\runtime.3\src\libraries\System.Runtime.Numerics\src\System\
  Numerics\BigIntegerCalculator.FastReducer.cs:line 61
     at System.Numerics.BigIntegerCalculator.PowCore(Span`1 value, Int32 valueL
  ength, UInt32 power, FastReducer& reducer, Span`1 result, Int32 resultLength,
   Span`1 temp) in C:\git\bartonjs\runtime.3\src\libraries\System.Runtime.Numer
  ics\src\System\Numerics\BigIntegerCalculator.PowMod.cs:line 539
     at System.Numerics.BigIntegerCalculator.PowCore(Span`1 value, Int32 valueL
  ength, UInt32 power, ReadOnlySpan`1 modulus, Span`1 temp, Span`1 bits) in C:\
  git\bartonjs\runtime.3\src\libraries\System.Runtime.Numerics\src\System\Numer
  ics\BigIntegerCalculator.PowMod.cs:line 416
     at System.Numerics.BigIntegerCalculator.Pow(ReadOnlySpan`1 value, UInt32 p
  ower, ReadOnlySpan`1 modulus, Span`1 bits) in C:\git\bartonjs\runtime.3\src\l
  ibraries\System.Runtime.Numerics\src\System\Numerics\BigIntegerCalculator.Pow
  Mod.cs:line 243
     at System.Numerics.BigInteger.ModPow(BigInteger value, BigInteger exponent
  , BigInteger modulus) in C:\git\bartonjs\runtime.3\src\libraries\System.Runti
  me.Numerics\src\System\Numerics\BigInteger.cs:line 1005

Which looks the same to me.

[eiriktsarpalis]

The two inputs trigger the same condition. TL;DR the implementation calculates the value $n^2$ and then attempts to subtract from it a value $q_2$ that is known to be smaller than that square (modulo $m + 1$). The problem is that it does so by applying a performance optimization that truncates the input values down to the $\log (m + 1)$ least significant digits, however this truncation operation can invalidate the original assumption that $n^2 \ge q_2$.

If the least significant digits of the input value $n$ are zero, or almost zero, then squaring that value will essentially double the number of least significant digits that are zero, which triggers the above condition.