Andy Polyakov <ap...@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 -- openssl-dev mailing list To unsubscribe: https://mta.openssl.org/mailman/listinfo/openssl-dev
