[openssl-dev] Partially- vs. full- reduced inputs to ecp_nistz256_neg

[Brian Smith]

Andy Polyakov <appro at openssl.org> wrote:
>> My understand after talking with Vlad that the "sbb \$0, $acc2" makes
>> this equivalent to (r >= 2**256) ? (r - q) : r. If the "sbb \$0,
>> $acc2" line were removed then it would be equivalent to (r >= q) ? (r
>> - q) : r. My understanding is that the difference in semantics is
>> exactly the difference between partially reduced results and fully
>> reduced results.
>
> Let's recall that result of multiplication prior final reduction is
> actually n+1-limb value, with +1 limb being single bit, that's $acc2,
> 5th limb in the context. So that the $0 in last 'sbb \$0,$acc2'
> represents 5th ("imaginary") limb of modulus[!]. And since we're looking
> at borrow from this 5-limb subtraction, outcome is actually
>
> if (ret > P) ret -= P'

OK, let's agree on that.

I think you are assuming that ret is in the range [0, 2P), so that if
you subtract P, the result would be in the range [0, P). That is the
case in normal Montgomery multiplication, where the inputs are in the
range [0, P). But, my understanding is that if the inputs are in the
range [P, 2**256), e.g. they are the result of ecp_nistz256_add, then
that assumption doesn't necessarily hold.

I understand Almost Montgomery Multiplication (AMM) as described in
[1], where one accepts inputs in the range [0, 2**n] and returns a
result in the range [0, 2**n), not [0, P).

I also read the original paper on the ecp_nistz256 implementation [2],
which has "0 ≤ a, b < p" as a precondition for the Montgomery
multiplication.

To put my concern another way: Earlier in the thread, you said the
function can take inputs that aren't fully reduced--i.e. are in in the
range [0, 2**n)--and returns outputs that are fully reduced--i.e. in
the range [0, P)--but it isn't clear how that is achieved. My
understanding is that the domain and range of the function are the
same.

[1] https://eprint.iacr.org/2011/239.pdf
[2] https://eprint.iacr.org/2013/816.pdf

Cheers,
Brian