CODEWITHSUNDEEP
c#.netmathsrp-protocol
stomseven
stomseven

Reputation: 157

C# BigIntegers get the positive modPow

I'm trying to implement the SRP Protocol for secure authentication. My problem is that when I have to calculate a ModPow of a negative number, it also returns a negative number. I know it's maybe called the remainder not the modulus but I really have to get the positive modulus to generate the correct hash.

How could I do that?

Upvotes: 0

Views: 515

Answers (2)

Craig Gidney
Craig Gidney

Reputation: 18296

SRP doesn't have any operations where you need to take the ModPow of a negative number. All arithmetic related to ModPow is supposed to be done in modular arithmetic, which in practice means all inputs and outputs should be non-negative and less than some modulus N.

If you're ending up with a negative number, perhaps after doing a subtraction, you're essentially supposed to add N to the result until it's non-negative. For huge negative values, computing x % N is equivalent to adding N until it only requires one more addition of N to be positive.

Upvotes: 0

Brett Hale
Brett Hale

Reputation: 22358

You can add (or subtract) any multiple of the modulus from the result since: r + km = r (mod m)

I assume the result is in: -m < r < 0, so you would simply use r + m.

The proper thing to do, is to find the least non-negative residue of the base, modulo m, prior to exponentiation - i.e., r <- r + m, and then exponentiate.

Upvotes: 1

Related Questions