RFR 8208648: ECC Field Arithmetic Enhancements

[Jamil Nimeh]

Hi Adam,

The changes look good.  With respect to the other coefficients, I agree 
with you that it's probably not worth the trouble to make them into 
constants.  It was just that one specific literal value in each file 
that jumped out at me.  Thanks also for the overflow explanation.  I 
would agree that given the extent to which you are exercising that code 
there would be some evidence if an overflow was causing issues.

--Jamil

On 12/7/2018 8:53 AM, Adam Petcher wrote:
>
> Updated webrev: http://cr.openjdk.java.net/~apetcher/8208648/webrev.01/
>
> Thanks for looking at this. See below.
>
> On 12/6/2018 8:03 PM, Jamil Nimeh wrote:
>> Hi Adam, comments/questions below (mostly simple stuff, nothing major):
>>
>>   * IntegerPolynomial.java
>>       o The comment block for multByInt should reflect your changes
>>         you made, namely the removal of "r" from the signature.
>>
> Fixed.
>
>>       o 88: In the case of multiplying two very large long values
>>         would we ever see those cause an overflow.  If so, is it OK
>>         to have them overflow before the reduce operation?
>>
> The potential for overflow is the hardest part of all this, and any 
> overflow will cause serious problems. You can do some calculations to 
> ensure that overflow doesn't happen. For the multiplication, these 
> calculations are pretty simple and can be done manually. For an n-bit 
> representation, each limb has a maximum magnitude of 2^(n + 1) going 
> into the multiplication. If there are k limbs, then the maximum 
> magnitude of any limb after the multiplication is 2^(2n + 2 + log k). 
> There is no overflow during multiplication as long as this maximum is 
> strictly less than 2^63. For example, the P-521 field uses 19 limbs 
> with 28 bits each. So the maximum limb magnitude after multiplication 
> is 2^(2*28 + 2 + log 19) =~ 2^(62.25).
>
> Doing these sorts of calculations to ensure that there is no overflow 
> during the carry/reduce sequence is much more tedious. I have a model 
> of this arithmetic that does all this calculation for me, and that is 
> what I used to ensure there is no overflow. Also, the unit test 
> (TestIntegerModuloP.java) does a large number of random operations, 
> and I suspect that it would be very unlikely for an accidental 
> overflow to get past that test.
>
>>      o
>>
>>
>>       o 420-425: Looks like this was a copy of the comment block from
>>         conditionalSwap().  Maybe needs to be tailored to what the
>>         conditionalAssign method does?
>>
> Fixed.
>>
>>       o IntegerPolynomialP256.java, IntegerPolynomialP384.java,
>>         IntegerPolynomialP521.java
>>           + In the carryReduce0 and carryReduce methods, you have
>>             many uses of an integer literal (33554432 for P256,
>>             134217728 for P384/521).  Should these be made as private
>>             static final long values?
>>       o P256OrderField.java, P384OrderField.java, P521OrderField.java
>>           + Similar question about using a static final long vs.
>>             repeated int literal values in the carryReduce* methods.
>>       o With respect to the last two main bullet items: Would
>>         conversion to a static final value be difficult due to the
>>         fact that they are generated from Fieldgen.jsh?
>>
> I changed the literal that was used during the carry operations to a 
> class constant called CARRY_ADD, and made it more clear what it is (it 
> is 1 << n for some n). The only literals remaining are the 
> coefficients that are used in reduction. Making these constants is a 
> bit more complicated, because there are several cases to consider, and 
> there are optimizations for each of these cases to make the code more 
> clear. For example, if the coefficient is 1, then don't bother 
> multiplying by it. I can make these class constants, too, but I'm not 
> sure it is worth the trouble. Let me know what you think.
>
> Changing the generator to produce better generated code is no problem, 
> so please let me know if you find more opportunities to make this code 
> more clear.
>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mail.openjdk.java.net/pipermail/security-dev/attachments/20181207/4401dc5e/attachment.html>