Do we need an unsigned multiplyHigh?

[Adam Petcher]

I agree that an unsigned multiplyHigh would be useful for crypto 
purposes, and we should consider adding it. Of course, I would much 
rather have multiply operations that return both 64-bit parts of the 
result, but that is going to be hard to do well without value types. So 
it would be nice to have something like this in the meantime.

If we are going to add this operation, it should probably be added along 
with an intrinsic. I think the Java code can simply factor out the else 
branch from the existing multiplyHigh code. This way, 
unsignedMultiplyHigh will be at least as fast as multiplyHigh, whether 
the intrinsic implementation is available or not.

If possible, the implementation of this operation should not branch on 
either operand. This would make it more widely useful for constant-time 
crypto implementations. Though this property would need to go into the 
spec in order for constant-time crypto code to use this method, and I 
don't know how reasonable it is to put something like this in the spec.

Side note: at the moment, I am using signed arithmetic in prototypes for 
Poly1305, X25519, and EdDSA, partially due to lack of support for 
unsigned operations like this one. I don't think having 
unsignedMultiplyHigh would, on its own, convince me to use an unsigned 
representation, but the forces are different for each 
algorithm/implementation.


On 9/25/2017 10:50 AM, Andrew Haley wrote:
> We now have a multiplyHigh intrinsic, but it is signed.  Unsigned
> multiplyHigh is in general a more useful primitive for crypto than
> signed, and I wonder if we need an intrinsic for that as well.  I've
> looked at cooking up an unsigned multiplyHigh in Java, and I think the
> fastest way is this:
>
>      private static final long unsignedMultiplyHigh(long a, long b) {
>          long result = Math.multiplyHigh(a, b);
>          if (a < 0)  result += b;
>          if (b < 0)  result += a;
>          // Can also be written as:
>          // result += (a >> 63) & b;
>          // result += (b >> 63) & a;
>          return result;
>      }
>
> It's still about 50% slower than the signed multiplyHigh, though.
> Thoughts?
>