RustCrypto / RustCrypto/crypto-bigint

Optimize Bernstein-Yang for 32-bit targets

Open
#380 2 comments 0 reactions 0 assignees View on GitHub

Nobody has claimed this yet.

Dominant language
Rust
Stars
309
Forks
95
Avg merge
1d 14h
Merged PRs (30d)
3

Description

Bernstein-Yang as described in the original paper uses 62-bit limbs and is optimized for 64-bit targets: https://eprint.iacr.org/2019/266

Section 12.3 of the paper suggests it can be better optimized for 32-bit targets:

12.3. Other CPUs. Our advantage is larger on platforms with smaller multipliers. For
example, we have written software to invert modulo 2^255 − 19 on an ARM Cortex-A7,
obtaining a median cycle count of 35277 cycles. The best previous Cortex-A7 result we
have found in the literature is 62648 cycles reported by Fujii and Aranha [34], using
Fermat’s method. Internally, our software does repeated calls to jump32divsteps2, units
of 30 iterations with the resulting transition matrix fitting inside 32-bit general-purpose
registers.

However, I wasn't able to find more information about adapting the algorithm to 32-bit targets beyond this, nor was I able to find any more information about jump32divsteps2.

I attempted to naively translate the implementation to using 30-bit limbs as suggested by the "units of 30 iterations" in #372 but was unable to get it to work.

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 with the existing Bernstein–Yang implementation and Section 12.3 of the cited paper, then compare the attempted 30-bit-limb approach from #372 with the paper’s jump32divsteps2 reference. The issue is done when a correct, optimized implementation for 32-bit targets is available.

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
Stale
Clarity
Needs clarification
Newbie friendliness
25/100

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.