RustCrypto / RustCrypto/elliptic-curves

k256: type safety for non-normalized field elements

Open
#531 4 comments 0 reactions 0 assignees View on GitHub

Nobody has claimed this yet.

Dominant language
Rust
Stars
874
Forks
299
Avg merge
1d 4h
Merged PRs (30d)
12

Description

The k256 crate uses lazy normalization of field elements. While not a user-facing concern as we deliberately encapsulate FieldElement, there is a potential for bugs in code in k256 itself in the event one "forgets" to normalize a field element prior to returning it as the result of some computation. See #530 as an example (although there have been others).

One potential way to eliminate this class of bugs is to use separate types for normalized vs non-normalized field elements. For example, we could introduce something like LazyFieldElement on which all of the arithmetic operations are defined, while retaining FieldElement for the normalized form and defining all serialization operations on that.

LazyFieldElement::normalize could return FieldElement, and we could additionally have bidirectional From conversions between the two.

Things would be a bit tricky in regard to the the ff::Field traits. I imagine for compatibility reasons they would need to be impl'd on FieldElement, converting to a LazyFieldElement to perform the arithmetic, and then calling normalize() to get a FieldElement again as a result, which would mean that the performance benefits of lazy normalization wouldn't be available under such an API. However, that is the only safe usage pattern since the traits are designed to abstract over different fields/field implementations, and not all of them have lazy normalization.

cc @fjarri

See also: https://github.com/RustCrypto/traits/issues/1997

Contributor guide

No contributing guide indexed for this repository

First steps

  1. Read the whole issue, then the project's contributing guide.
  2. Comment on the issue to say you are picking it up — it saves two people doing the same work.
  3. Fork the repository and make your change on a branch.
  4. Open a pull request that references the issue number.

Research direction

Start by inspecting the k256 crate's FieldElement implementation and its ff::Field integration, using #530 and RustCrypto/traits issue #1997 as context. Define the boundary between normalized and non-normalized values, then verify arithmetic, conversions, serialization, and trait behavior with the crate's test suite.

Written by the indexing model from the issue text.

Assessment

Tech stack
rust
Domain
cryptography
Issue type
Refactor
Difficulty
5/5
Estimated time
Over a week
Activity status
Quiet
Clarity
Needs clarification
Newbie friendliness
35/100

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.