Bitwise operations for scalars

[ycscaly]

I'm curious as to why Shr is the only bitwise operator implemented for scalars? I'm interested in k256 specifically, but I think this is a more generalized question.

Why not have Shl, And, etc. etc.?

[str4d]

The problem with bitwise operations on scalars (or more generally, odd prime-order fields elements) is what to do when the result is not a valid scalar. This occurs in non-intuitive places, because the "bit width" of a scalar covers a superset of the valid range of scalars (unlike unsigned integers like u64).

Shr is pretty uncontroversial: drop the lowest bit and shift the others right. This always results in a valid scalar, and leaves the bit pattern untouched other than dropping the LSB.

Shl, by contrast, immediately shows problems. If implemented the same way as for unsigned integers, then we'd drop the "top" bit (for which you'd probably use the position of the highest bit set for modulus - 1) and shift all other bits left. But if the remaining bits, once shifted left by one, don't form a valid scalar, what do you do?

• Drop any bits that would result in an invalid scalar? That changes the bit pattern in non-intuitive (and I'd argue non-useful) ways.
• Drop bits from the top until what is left is a valid scalar? That preserves as much of the bit pattern as possible, but doesn't match the intuitive definition of "shift right".
• Reduce the result modulo modulus, i.e. pretend that the shift-left part was actually "double"? That completely changes the bit pattern, and also doesn't match the intuitive definition of "shift left".
• Don't drop the top bit at all, and just use "double"? But that has wrapping behaviour that is closer to "rotate left" than "shift left", and also doesn't preserve the bit pattern.

Other binary operators like And have similar issues.

The end result is that the only bitwise operator that can safely be implemented for prime-order fields is Shr. For everything else, if you're reaching for a bitwise operation, then:

• Check what your cryptographer says, because this is almost certainly unnecessary.
• If it is necessary, then encode the scalar, perform the bitwise operations on the encoding, and then parse the result as a scalar (which may fail).

[ycscaly]

The problem with bitwise operations on scalars (or more generally, odd prime-order fields elements) is what to do when the result is not a valid scalar. This occurs in non-intuitive places, because the "bit width" of a scalar covers a superset of the valid range of scalars (unlike unsigned integers like u64).

Shr is pretty uncontroversial: drop the lowest bit and shift the others right. This always results in a valid scalar, and leaves the bit pattern untouched other than dropping the LSB.

Shl, by contrast, immediately shows problems. If implemented the same way as for unsigned integers, then we'd drop the "top" bit (for which you'd probably use the position of the highest bit set for modulus - 1) and shift all other bits left. But if the remaining bits, once shifted left by one, don't form a valid scalar, what do you do?

• Drop any bits that would result in an invalid scalar? That changes the bit pattern in non-intuitive (and I'd argue non-useful) ways.
• Drop bits from the top until what is left is a valid scalar? That preserves as much of the bit pattern as possible, but doesn't match the intuitive definition of "shift right".
• Reduce the result modulo modulus, i.e. pretend that the shift-left part was actually "double"? That completely changes the bit pattern, and also doesn't match the intuitive definition of "shift left".
• Don't drop the top bit at all, and just use "double"? But that has wrapping behaviour that is closer to "rotate left" than "shift left", and also doesn't preserve the bit pattern.

Other binary operators like And have similar issues.

The end result is that the only bitwise operator that can safely be implemented for prime-order fields is Shr. For everything else, if you're reaching for a bitwise operation, then:

• Check what your cryptographer says, because this is almost certainly unnecessary.
• If it is necessary, then encode the scalar, perform the bitwise operations on the encoding, and then parse the result as a scalar (which may fail).

Those are all good points, but that being said they could be a disclaimer to a functionality that would let users choose whether to use it, rather than prohibit it from the get go.

There are use-cases where this is desirable, and if we have edge cases in which the results are invalid, we can return Result. Another possibility is to have a wrapped implementation that reduces it by the moduli like suggested. As long as it is documented properly, it can still be beneficial.

This feature is optional for me and so I won't push any further, I was curious for the reason and you gave a good explanation, I gave an alternative and it's fine to disagree with it or accept it, as you wish.

Thanks for the explanation

[tarcieri]

But if the remaining bits, once shifted left by one, don't form a valid scalar, what do you do?

One option would be to have a checked_shl that returns CtOption

[ycscaly]

But if the remaining bits, once shifted left by one, don't form a valid scalar, what do you do?

One option would be to have a checked_shl that returns CtOption

exactly

[tarcieri]

Would be good to get a trait for that into crypto-bigint