RFR 8181594: Efficient and constant-time modular arithmetic

[Xuelei Fan]

ArrayUtil.java:
===============
I'm not very sure how widely this utilities will be used in the future. 
Looks like only BigIntegerModuloP uses this classes.  I may prefer to 
define private methods for byte array swap in BigIntegerModuloP.


BigIntegerModuloP.java:
=======================
As this is a class for testing or ptototype purpose,  it might not be a 
part of JDK products, like JRE.  Would you mind move it to a test 
package if you want to keep it?


IntegerModuloP, IntegerModuloP_Base and MutableIntegerModuloP
=============================================================
In the security package/context, it may make sense to use 
"IntegerModulo" for the referring to "integers modulo a prime value". 
The class name of "IntegerModuloP_Base" is not a general Java coding 
style.  I may prefer a little bit name changes like:
      IntegerModuloP_Base   -> IntegerModulo
      IntegerModuloP        -> ImmutableIntegerModulo
      MutableIntegerModuloP -> MutableIntegerModulo

      IntegerFieldModuloP   -> IntegerModuloField (?)


MutableIntegerModuloP.java
==========================
void conditionalSwapWith(MutableIntegerModuloP b, int swap);
As the 'swap' parameter can only be 0 or 1, could it be a boolean parameter?

Except the conditionalSwapWith() method, I did not get the points why we 
need a mutable version.  Would you please have more description of this 
requirement?


IntegerModuloP_Base.java
========================
default byte[] addModPowerTwo(IntegerModuloP_Base b, int len)
void addModPowerTwo(IntegerModuloP_Base b, byte[] result);

For the first sign of the method names, I thought it is to calculate as 
"(this + b) ^ 2 mod m".  Besides, what's the benefits of the two 
methods?  Could we just use:
       this.add(b).asByteArray()

I guess, but not very sure, it is for constant time calculation.  If the 
function is required, could it be renamed as:

       // the result is inside of the size range
       IntegerModuloP addModSize(IntegerModuloP_Base b, int size)
Or
       // the result is wrapped if outside of the size range
       IntegerModuloP addOnWrap(IntegerModuloP_Base b, int size)

and the use may look like:
       this.addModSize(b, size).asByteArray()


Will review the rest when I understand more about the interfaces design.

Thanks,
Xuelei

On 1/30/2018 8:52 AM, Adam Petcher wrote:
> +core-libs-dev
> 
> 
> On 1/26/2018 4:06 PM, Adam Petcher wrote:
>> JBS: https://bugs.openjdk.java.net/browse/JDK-8181594
>> Webrev: http://cr.openjdk.java.net/~apetcher/8181594/webrev.00/
>>
>> This is a code review for the field arithmetic that will be used in 
>> implementations of X25519/X448 key agreement, the Poly1305 
>> authenticator, and EdDSA signatures. I believe that the library has 
>> all the features necessary for X25519/X448 and Poly1305, and I expect 
>> at most a couple of minor enhancements will be required to support 
>> EdDSA. There is no public API for this library, so we can change it in 
>> the future to suit the needs of new algorithms without breaking 
>> compatibility with external code. Still, I made an attempt to clearly 
>> structure and document the (internal) API, and I want to make sure it 
>> is understandable and easy to use.
>>
>> This is not a general-purpose modular arithmetic library. It will only 
>> work well in circumstances where the sequence of operations is 
>> restricted, and where the prime that defines the field has some useful 
>> structure. Moreover, each new field will require some field-specific 
>> code that takes into account the structure of the prime and the way 
>> the field is used in the application. The initial implementation 
>> includes a field for Poly1305 and the fields for X25519/X448 which 
>> should also work for EdDSA.
>>
>> The benefits of using this library are that it is much more efficient 
>> than using similar operations in BigInteger. Also, many operations are 
>> branch-free, making them suitable for use in a side-channel resistant 
>> implementation that does not branch on secrets.
>>
>> To provide some context, I have attached a code snippet describing how 
>> this library can be used. The snippet is the constant-time Montgomery 
>> ladder from my X25519/X448 implementation, which I expect to be out 
>> for review soon. X25519/X448 only uses standard arithmetic operations, 
>> and the more unusual features (e.g. add modulo a power of 2) are 
>> needed by Poly1305.
>>
>> The field arithmetic (for all fields) is implemented using a 32-bit 
>> representation similar to the one described in the Ed448 paper[1] (in 
>> the "Implementation on 32-bit platforms" section). Though my 
>> implementation uses signed limbs, and grade-school multiplication 
>> instead of Karatsuba. The argument for correctness is essentially the 
>> same for all three fields: the magnitude of each 64-bit limb is at 
>> most 2^(k-1) after reduction, except for the last limb which may have 
>> a magnitude of up to 2^k. The values of k are between 26 to 28 
>> (depending on the field), and we can calculate that the maximum 
>> magnitude for any limb during an add-multiply-carry-reduce sequence is 
>> always less than 2^63. Therefore, no overflow occurs and all 
>> operations are correct.
>>
>> Process note: this enhancement is part of JEP 324 (Key Agreement with 
>> Curve25519 and Curve448). When this code review is complete, nothing 
>> will happen until all other work for this JEP is complete, and the JEP 
>> is accepted as part of some release. This means that this code will be 
>> pushed to the repo along with the X25519/X448 code that uses it.
>>
>> [1] https://eprint.iacr.org/2015/625.pdf
>>
>>
>>
>