Take the 2-minute tour ×
Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It's 100% free, no registration required.

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?
share|improve this question
add comment

1 Answer 1

up vote 3 down vote accepted

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).

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.