# Secure Remote Protocol - Are these 2 equations equivalent?

I'm implementing the Secure Remote Protocol that is specified to have this equation for the parameter S, the premaster secret.

 S = (B - (k * g^x)) ^ (a + (u * x)) % N


But the implementation I'm referring to, has done it this way. Is this equivalent to the author's description? Its too complex for me to understand. Can you please check it and/or explain?

 S = ((B + (N - ((k * (g^x % N)) % N))) ^ (a + u * x) %  N);


Some questions:

• Why the 3 mod's instead of just 1 at the end?
• Why B+ and N- instead of B-?
• Can it be optimized in any way?
-

## 1 Answer

Well, the bottom line is that it is equivalent.

The intermediate mod's do not modify the value of the expression; this is because all the arithmetic done by the expression (except for the calculation of the exponent (a + u * x)) is done modulo N; it is always safe to do intermediate reductions.

And, in this case, it's actually necessary; g^x is quite a huge number, and you really have to compute it modulo N, the actual value is just too big.

As for why B+ and N- instead of B-, well, it is likely that the modular exponentiation primitive that the programmer used wasn't able to handle negative bases. By reducing the value of k * g^x modulo N (which is safe, as above), that value is always less than N; and so N - (k * g^x % N) is always positive, and so is B + (N - (k * g^x % N)). Also note that this modification is also safe, because for all $A$, $B$, $N$, we have:

$A - B = A + N - B = A + (N - B) \mod N$

I would note that there are some further reductions that could have been done:

• The exponent could have been computed modulo (N-1), as in (a + u*x) % (N-1). This is a safe reduction because N is prime (and Fermat's Little Theorem); this would speed up the second modular exponentiation operation by giving it a smaller exponent. Note that the modular exponentiation primitive cannot do it (it couldn't assume N is prime).

• When computing (B + (N - ((k * (g^x % N)) % N)), they could have done a final % N to it; this might speed up the second modular exponentiation operation (by giving it a smaller base). However, unlike the above operation, the code that computes the modular exponentiation might do that already (because that is always safe, whether or not N is prime).

-