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$
9
  • $\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
2
$\begingroup$

Theorem 2 in [Dussé et al. 1991] states that, if we skip the final subtraction, then, for $N < R / 4$ and $0 \leq A, B < 2 N$, we have $0 \leq C = \text{MonMul}(A B) < 2 N$, while keeping $C \equiv A B R^{-1} \pmod N$. I think the condition $N < R / 4$ inherently holds in your case e.g. you are using larger $R$ value acutually.

Improve this answer
$\endgroup$

Your Answer

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

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