3
$\begingroup$

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$?

|improve this question
$\endgroup$
  • $\begingroup$ Stupid question: why are you using Montgomery Multiplication for $2^{255}-19$ in the first place? The reason we do Montgomery Multiplication is to make the modulo operation easier; however with $N=2^{255}-19$, it's already awfully easy, as $a \cdot 2^{255} + b \equiv a \cdot 19 + b \pmod{2^{255}-19}$ $\endgroup$ – poncho Jun 29 '15 at 17:54
  • $\begingroup$ I expected that question :) Because Montgomery multiplication saves me some code memory which I am optimizing for. Doing A*B and then doing the full reduction using what you just said requires far more code than for example CIOS Montgomery multiplication. $\endgroup$ – NumberFour Jun 29 '15 at 17:56
  • $\begingroup$ @NumberFour, as Poncho pointed out, the reduction process is obvious for this modulus format. Observe that $A \star B \; mod \; N \simeq \; A \star \; B \; - \; [High(A\star \;B)]\star N$. And this can also be optimised, without going to Montgomery arithmetic which necessitate additionnal pre and post process. $\endgroup$ – Robert NACIRI Jun 30 '15 at 16:35
  • $\begingroup$ I was already experimenting with all that. I am doing a specific implementation for a device with very restricted instruction set. For some reasons, I cannot optimize for speed but for code size and memory consumed. Montgomery comes out with least code size and memory requirements. Also the pre- and post- processing comes for free (in terms of extra memory) since MonPro could be used for this purpose as well. $\endgroup$ – NumberFour Jun 30 '15 at 17:23
  • $\begingroup$ I don't expect your algorithm to work without exceptions. You mentioned result is below $2N$, so try to square, through montgomery multiplication, $2N-1$ and see if the result is above $2N$. Note, don't convert anything into/from montgomery, just compute MonMul(2N-1,2N-1). $\endgroup$ – Ruggero Jul 1 '15 at 8:51

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.