I have no other comments.
Thanks,
Xuelei
On 3/20/2018 7:50 AM, Adam Petcher wrote:
> Latest webrev: http://cr.openjdk.java.net/~apetcher/8181594/webrev.02/
>
> Comments inline below.
>
> In addition, I also changed the name of IntegerModuloP_Base to
> IntegerModuloP, and IntegerModuloP to ImmutableIntegerModuloP.
>
>
> On 3/11/2018 12:04 PM, Xuelei Fan wrote:
>> On 2/26/2018 10:39 AM, Adam Petcher wrote:
>>>
>>> On 2/23/2018 12:46 PM, Xuelei Fan wrote:
>>>
>>>> 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.
>>>
>>> It is also used by XDHPublicKeyImpl (in the XDH code review). XDH
>>> public keys are represented as BigInteger, and I use the array
>>> reverse method to convert encoded keys to BigInteger.
>>>
>> If it is not widely used by other classes, please have these methods
>> in the class where is get called. The sun.security.util is exported
>> to other modules as well, we may not want to add stuff into this
>> package unless it is really necessary.
>
> Okay. I put these methods in BigIntegerModuloP and removed the ArrayUtil
> class. This array reverse code will be duplicated where it is used by
> XDH public keys (in the other code review).
>
>>
>>>>
>>>> MutableIntegerModuloP.java
>>>> ==========================
>>>> void conditionalSwapWith(MutableIntegerModuloP b, int swap);
>>>> As the 'swap' parameter can only be 0 or 1, could it be a boolean
>>>> parameter?
>>>
>>> I couldn't come up with a way to implement this without branching
>>> when the swap parameter is boolean. See
>>> IntegerPolynomial.conditionalSwap to see how this is implemented in
>>> arithmetic with an int swap argument. If you (or anyone) can think of
>>> a way to do this with boolean, let me know.
>>>
>>> I added a sentence to the comment above conditionalSwapWith that
>>> describes why it is an int instead of a boolean.
>>>
>> I did not get the point about the need to avoid branching. Can you
>> have more details?
>
> The goal is to avoid things like if(secret){...}, in order to prevent
> the secrets from leaking into side channels (mostly timing and cache).
> The way this method is used by XDH, the swap parameter is a single bit
> of the private key. By storing this bit as an integer, and then doing
> the swap using only integer arithmetic, we can avoid branching which may
> leak the bits of the key.
>
>>
>>>>
>>>> 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?
>>>
>>> The comment above the class definition has this sentence:
>>>
>>> "This interface can be used to improve performance and avoid the
>>> allocation of a large number of temporary objects."
>>>
>>> Do you need more information than this in the comments? The
>>> performance motivation is so that a.add(b).multiply(c)... can be done
>>> without allocating a new buffer for each operation. For example,
>>> without mutable field elements, an X25519 point multiplication would
>>> allocate around 4,300 temporary arrays totaling 350,000 bytes. If I
>>> remember correctly, switching the X25519 implementation to mutable
>>> field elements reduced the point multiplication time by about half.
>>>
>> I see your point. The benefits is obviously.
>>
>> OK, why you need the immutable version then? Sounds like the mutable
>> version interface is sufficient, including performance. If an
>> immutable version is really needed, we can have the implementation
>> making the decision. Accordingly, the conditionalSwapWith() can be
>> defined as optional method, if it is not required to be implemented in
>> immutable implementation.
>>
>> It's confusing to me that the immutable and mutable and the base
>> versions/interfaces mixed together. It would be nice if we can
>> simplify the interface a little bit.
>>
>> For internal APIs, sometimes we don't want the same quality level as
>> public APIs. I think this set of class will be widely used by new EC
>> curves, ChaCha20/Poly1305, or more in the future. It would be nice if
>> we could do it good at the beginning.
>
> The mutable version adds the conditional swap as well as mutable
> versions of many of the basic operations. The XDH implementation uses
> both the mutable and immutable versions. The immutable version allows me
> to simplify the client code because I don't have to worry about whether
> some value has been modified. For example, the XDH code keeps a
> representation of 0, 1, and the constant that defines the curve as
> immutable values.
>
> So I prefer to have both. It complicates this API a bit, but it allows
> simpler and more robust code in the client of this API.
>
>>
>>>>
>>>>
>>>> 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".
>>>
>>> To be precise, it calculates "((this % p) + (b % p)) % 2^m" (where p
>>> is the prime that defines the field, and m is the desired length, in
>>> bits). Note that the addition here is normal integer addition (not
>>> addition in GF(p)).
>>>
>>> This operation is not used in XDH, but it is used in Poly1305 to add
>>> the AES encryption of a nonce to a field element. So you can get more
>>> information about this operation by reading the Poly1305 paper/RFC.
>>>
>> I was not meant to say the function of the method. I meant that the
>> method name is a little bit misleading, not very straightforward to me.
>>
>>>> Besides, what's the benefits of the two methods? Could we just use:
>>>> this.add(b).asByteArray()
>>>
>>> No, because that would calculate "((this + b) mod p) mod 2^m". The
>>> value of (this + b) can be larger than p, so this would not produce
>>> the desired result.
>>> >>
>>>> 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()
>>>>
>>>
>>> Any attempt to perform the addition in IntegerModuloP and then pull
>>> out the byte array will not work.
>> Does it mean if I perform a addition, and cannot get the byte array in
>> the following step?
>> that = this.add(b);
>> byte[] bs = that.asByteArray(); // does not work?
>> or
>> byte[] bs = that.asByteArray(length); // does not work?
>> or
>> byte[] bs = that.asByteArray(byteArray); // does not work?
>>
>>> This class can only represent field elements, so the sum would be in
>>> the field, which is not what we want.
>>>
>> I did not get the point. If getting an add result, the add is done
>> (sum in the field). Did you have an example that pulling out the byte
>> array will not work?
>
> Say we are in the field of integers modulo 269, and the final result of
> some computation will be stored in a single byte. In this example, we
> discard information when we truncate to the byte array. This may seem
> strange, but it is exactly what Poly1305 does. Now say we want to add x
> with itself, and x has the value 260.
>
> // x.add(x) has value 251
> byte[] result = new byte[1];
> x.add(x).asByteArray(result); // result has value 251
> x.addModPowerTwo(x, result) // result has value 8
>
> The difference between the two statements above is that the first one
> does a reduction mod 269 after the addition (and before converting to a
> byte array), while the second one does not. I can't split addModPowerTwo
> into two method calls without also adding another type for integers
> modulo a possibly-non-prime, and I didn't think it was worth the effort.
>
> I don't have a problem with renaming the method if you think this will
> make it more clear. Let me know which name you prefer. The name
> addModSize is probably okay, although technically we are reducing mod
> 2^size, so the name might be slightly misleading. Maybe something a
> little less precise like addToSize?
>