Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Bitwise operations for scalars #995

Open
ycscaly opened this issue Nov 24, 2023 · 6 comments
Open

Bitwise operations for scalars #995

ycscaly opened this issue Nov 24, 2023 · 6 comments

Comments

@ycscaly
Copy link
Contributor

ycscaly commented Nov 24, 2023

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
Copy link
Contributor

str4d commented Nov 29, 2023

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
Copy link
Contributor Author

ycscaly commented Nov 29, 2023

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
Copy link
Member

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
Copy link
Contributor Author

ycscaly commented Nov 29, 2023

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
Copy link
Member

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

@mahmudsudo
Copy link

can i take on this ?

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
None yet
Projects
None yet
Development

No branches or pull requests

5 participants
@tarcieri @ycscaly @str4d @mahmudsudo and others