I'm doing Montgomery arithmetic modulo $N = 2^{255}-19$ for the Curve25519, picking $R = 2^{256}$ for Montgomery.
After multiplying two numbers $0 \leq A,B < N$ in the Montgomery representation using MonMul
, I would normally obtain the result $0 \leq C < N$ also in the Montgomery representation.
However, if I forget the conditional subtraction in MonMul
I obtain some $0 \leq C^{\prime} < 2N$. In other words, I basically ended up in a different representation which is not unique anymore.
I could live with that and do all the additions/subtractions modulo $2^{256}-38$ instead afterwards. That means I basically postponed the conditional subtraction until the end of my whole computation.
But my question is what happens if I have to do MonMul
again somewhere during my computation? It would mean that one (or both) of the input numbers for MonMul
could be in fact between $N$ and $2N$.
Do I have to make the conditional subtraction before doing the MonMul
again (to put my numbers back in the right representation)? Or can I still postpone it until the end? I realized that not doing the subtraction before any repeated multiplication didn't spoil the computation so far. Does it really hold universally for my $N$?
MonPro
could be used for this purpose as well. $\endgroup$MonMul(2N-1,2N-1)
. $\endgroup$