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

>>> * Fix ecp_nistz256_mul_by_2 and ecp_nistz256_mul_by_3 to fully reduce >>> their outputs. >>> >>> * Fix ecp_nistz256_add to fully reduce its output. >> >> As for specifically addition see below. As for fixing mul_by_[23] and >> the fact that they use addition. There are two ways. a) Modify

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

>> * Fix ecp_nistz256_mul_by_2 and ecp_nistz256_mul_by_3 to fully reduce >> their outputs. >> >> * Fix ecp_nistz256_add to fully reduce its output. > > As for specifically addition see below. As for fixing mul_by_[23] and > the fact that they use addition. There are two ways. a) Modify addition >

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

>> It appears to me that with multiplication, squaring, subtraction, >> negation, halving *preserving* property of being fully reduced (i.e. if >> inputs are fully reduced, then output is too), we only have to watch out >> for mul_by_[23], i.e. ensure that their outputs are fully reduced. This >>

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

Andy Polyakov wrote: > It appears to me that with multiplication, squaring, subtraction, > negation, halving *preserving* property of being fully reduced (i.e. if > inputs are fully reduced, then output is too), we only have to watch out > for mul_by_[23], i.e. ensure that

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

On Thu, Aug 18, 2016 at 04:24:56PM +0200, Andy Polyakov wrote: > >> 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

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

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

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

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

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

Andy Polyakov 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

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

> Let's recall that result of multiplication prior final reduction is > actually n+1-limb value, with +1 limb being single bit, This came out wrong. Result is N+1 *bits* wide, it's just in this particular case you have to spend additional limb on the the additional bit. It's just that particular

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

> ... I re-read the code for the conditional subtraction at the > end of ecp_nistz256_mul_mont (__ecp_nistz256_mul_montq, actually) and > I couldn't convince myself that the result was always fully reduced. > > My concern is that what you say and what Vlad said is contradictory. > You both

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

Andy Polyakov wrote: > And it's not only that multiplication (and squaring) result is fully > reduced, it, multiplication (ans squaring) subroutine can actually > manage partially reduced input. On related note one can point out that > result of addition (and mul_by_[2|3]) is

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

>>> No, it subtraction subroutine uses *borrow* to determine if modulus is >>> to be added. I.e. (a >= b) ? (a - b) : (P - (b - a)). If both a and b >>> are less than P, then result is less than P. >> >> Consider the case where a > P and a >= b and b is very small (e.g. 1). >> For example, a == P

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

>> No, it subtraction subroutine uses *borrow* to determine if modulus is >> to be added. I.e. (a >= b) ? (a - b) : (P - (b - a)). If both a and b >> are less than P, then result is less than P. > > Consider the case where a > P and a >= b and b is very small (e.g. 1). > For example, a == P + 2

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

Andy Polyakov wrote: > No, it subtraction subroutine uses *borrow* to determine if modulus is > to be added. I.e. (a >= b) ? (a - b) : (P - (b - a)). If both a and b > are less than P, then result is less than P. Consider the case where a > P and a >= b and b is very small

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

>>> Note in particular that, IIUC, ecp_nistz256_neg will never get an >>> unreduced input when applied to the the based point multiples, because >>> those are already fully reduced. But, when it is used in >>> ecp_nistz256_windowed_mul, it isn't clear whether or how the input Y >>> coordinate is

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

> C-callables are wrappers around inlined subroutines. The only thing they > do is load input into designated registers and call inlines, those used > in point functions. It's true for modules other than x86_64, but not x86_64 one. Sorry about confusion. -- openssl-dev mailing list To

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

Andy Polyakov wrote: >> Note in particular that, IIUC, ecp_nistz256_neg will never get an >> unreduced input when applied to the the based point multiples, because >> those are already fully reduced. But, when it is used in >> ecp_nistz256_windowed_mul, it isn't clear whether