RFR 8181594: Efficient and constant-time modular arithmetic
Xuelei Fan
xuelei.fan at oracle.com
Fri Feb 23 17:46:45 UTC 2018
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
>>
>>
>>
>
More information about the core-libs-dev
mailing list