Do we need an unsigned multiplyHigh? (original) (raw)

Adam Petcher adam.petcher at oracle.com
Mon Sep 25 17:21:55 UTC 2017

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?

More information about the security-dev mailing list