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.
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 (?)
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
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:
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)
// the result is wrapped if outside of the size range
IntegerModuloP addOnWrap(IntegerModuloP_Base b, int size)
and the use may look like:
Will review the rest when I understand more about the interfaces design.
On 1/30/2018 8:52 AM, Adam Petcher wrote:
On 1/26/2018 4:06 PM, Adam Petcher wrote:
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 (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.