README.md

# s2n-bignum

Assembly for the NIST prime curves from AWS's
[s2n-bignum](https://github.com/awslabs/s2n-bignum), vendored here.

`COMMIT` holds the upstream revision these files came from, and `import.sh`
fetches them again.  The files are unmodified: the choice between the two
variants of each routine is made in crypton's own C, not by editing theirs.

## Why

crypton's P-256 is portable C, and on the two architectures s2n-bignum
covers, hand-written assembly beats it by a lot.  Measured against crypton's
own code in the same process, agreeing with it on every scalar tried:

| | crypton | s2n-bignum |
| --- | ---: | ---: |
| Apple M4 | 52.9 us | **20.6** |
| x86-64 with ADX (EPYC 9V74) | 175.9 | **54.5** |
| x86-64, ADX not advertised | 156.1 | **59.4** |

The third row is the `_alt` path, which is what crypton picks where `CPUID`
does not report ADX.  It was measured on a KVM guest whose `CPUID` says so
while the host underneath runs ADX instructions anyway, so it says what the
two implementations cost relative to each other on that path, not what an
actual pre-Broadwell part would do.

Each routine also carries a machine-checked proof in HOL-Light that it
computes what it says, and is written in a constant-time style.

## Licence

`Apache-2.0 OR ISC OR MIT-0`, one of which is on every file and all three in
`LICENSE`.  crypton is BSD-3, so it takes these under **ISC** -- the MIT-0
option would do as well, and the Apache one is the reason OpenSSL's and
BoringSSL's `ecp_nistz256`, which is Apache-2.0 only, cannot be used here.

## Which variant

Both forms of each routine are vendored, because which one is faster is not
the same question on the two architectures:

* **On ARM**, `_alt` is written for parts with high multiplier throughput,
  which is what Apple silicon is, and it wins there by 30-40%.  The plain
  form is for parts that pipeline `UMULH` less well.  There is no feature bit
  for this, so the choice is made at compile time on `__APPLE__`.
* **On x86-64**, the plain form uses `MULX`, `ADCX` and `ADOX`, and `_alt` is
  the fallback for processors without them.  That *is* a feature bit, so the
  choice is made at run time, from `crypton_x86_simd_features()`.

## RSA

`crypton_powm.c`'s modular exponentiation also borrows from here, but only its
innermost step and only on x86-64: `bignum_kmul_16_32`, `bignum_ksqr_16_32`,
`bignum_kmul_32_64`, `bignum_ksqr_32_64` and `bignum_emontredc_8n` replace the
C's Montgomery multiplication and square.  The window, the table and its masked
scan are crypton's throughout.  Sixteen limbs is 1024 bits and thirty-two is
2048: the halves a CRT exponentiation works in for RSA-2048 and RSA-4096, and
the whole thing without CRT.  The reduction wants ADX, so the choice is made at
run time like the other x86-64 ones.

It is twice the C, because the C cannot form the two carry chains `ADCX` and
`ADOX` give.  Measured on an EPYC 7763 at 1024 bits:

| | C | s2n-bignum |
| --- | ---: | ---: |
| multiplication | 0.4832 us | **0.2479** |
| square | 0.3984 | **0.1994** |

### The Montgomery constant

`bignum_montifier` is vendored for **both** architectures.  It is the one
routine here that is not about a particular curve or a particular size: every
modular exponentiation and every setup in `crypton_ecc.c` starts by computing
R^2 mod m, and this computes it.  crypton's C climbs to it by a
binary ladder of Montgomery squarings -- log2 of the modulus' bits of them,
eleven at 2048 -- and the assembly is between two and three and a half times
faster, the gap being the carry chains again:

| | C | s2n-bignum |
| --- | ---: | ---: |
| M4, 1024 bits | 1.853 us | **0.771** |
| M4, 2048 bits | 5.835 | **2.407** |
| an Intel x86-64, 1024 bits | 6.145 | **1.995** |
| an Intel x86-64, 2048 bits | 23.332 | **6.852** |

A CRT signature computes it twice, so an RSA-2048 private operation on the
EPYC 7763 goes from 613.5 to 606.4 microseconds -- a little over one per
cent, which is all a constant computed twice out of some two and a half
thousand multiplications can be.  It is worth much more than that to anything
whose exponent is short, which is why it is here: see `crypton_powm.c`.

The two agree bit for bit; `cbits/tests/powm` requires it at six widths, with
moduli that fill their limbs and moduli that do not, and a build without the
assembly (`-DCRYPTON_NO_MONTIFIER`) is what it is checked against.

**None of the five above is vendored for AArch64**, where they measure level
with the C.  That took three attempts to establish, and the first two were
wrong in opposite directions: a reading when the x86-64 routines went in put
the C 5% ahead, and one on 2026-09-26 put the assembly 4% ahead.  Both were
wall-clock times on a machine with other work on it, where a swing of that size
says nothing.  Measured by thread CPU time, taking the best of twenty-five
batches and alternating the two binaries with the order swapped, one RSA-2048
CRT private operation is 598.9 us through the C and 597.7 through the assembly:
two tenths of a per cent, which is nothing.  The two agree on 200 random cases
at 1024 and 2048 bits, so both were computing the same thing.  Five files for
nothing is not a trade, so the C stays.

The gap to OpenSSL on Apple silicon -- about half its speed -- is assembly and
not the C, and no portable C closes it.  BearSSL's `i62`, which is as far as
portable C is known to go -- 62-bit limbs in 64-bit words, so that a
multiply-accumulate fits an `__int128` with no carry chain at all, and a
five-bit window against crypton's four -- was built and measured the same way
on the same machine: 626.4 us against crypton's C at 668.0, a tie.

`bignum_emontredc_8n_cdiff` was tried too and is not the answer either: it
wants a precomputation this test did not give it, and was slower besides.  What
the window is worth, and why it is four and not five, is in
`cbits/crypton_powm.c` beside the constant.

## Windows

x86-64 Windows takes the assembly as every other x86-64 does.  Two things
stood in the way, and neither is fixed in a vendored file:

* **The ELF directives.**  Each file ends its symbols with `.type` and
  `.size`, which the COFF assemblers refuse -- mingw's gas says "junk at end
  of line" after a warning, clang says "expected absolute expression".
  There is nothing in a PE object for them to say, so on `_WIN32` they are
  emptied, as upstream already does for Mach-O.
* **The calling convention.**  Each file carries a prologue that moves
  Microsoft's argument registers into System V's, under `WINDOWS_ABI`, which
  upstream leaves to the build to define.  On `_WIN32` it is defined.

Both are done in `x86_att/_internal_s2n_bignum_x86_att.h`, which is crypton's
and not upstream's.  Every vendored file includes that name in quotes, and a
quoted include looks first beside the file that asks for it, so this is the
one each gets; it hands on to upstream's in `include/` by a relative path.
**It must not be removed as an upstream file that went missing**: without it
Windows does not assemble.  On Linux and macOS it changes nothing -- the
objects are byte for byte what they were without it.

Not `#include_next`, which is the obvious way to hand on: clang, finding this
header beside the file that asked for it, starts that search from the top
and finds this header again, without end.

Windows on ARM keeps the C.  The AArch64 files have the same directives and
would want the same header, and there is no runner to check one.

## What is not here

s2n-bignum has only x86-64 and AArch64, so crypton's C stays and is what
every other architecture uses.

Its `generic` directory holds a complete variable-size bignum library on both
architectures -- `bignum_montmul`, `bignum_montredc`, `bignum_emontredc`,
`bignum_modinv` and a whole `bignum_modexp` -- and only `bignum_montifier` is
taken from it.  **The rest was measured on an M4 and is slower than what is
here**, which is why it stays out; they agree with crypton's answers in every
case first, so both were computing the same thing.

| nanoseconds, AArch64 | C | s2n-bignum |
| --- | ---: | ---: |
| Montgomery multiply, 1024 bits | **171.7** | 227.9 |
| Montgomery multiply, 2048 bits | **649.6** | 870.3 |
| Montgomery square, 1024 bits | **157.3** | 202.6 |
| Montgomery square, 2048 bits | **539.2** | 870.8 |

That is the inline assembly above doing its job: four limbs to an iteration
with two carry chains, where a size-parametric routine takes them one at a
time.  `bignum_modexp`, which would have replaced `crypton_powm_sec` outright,
loses by more again -- 421.0 microseconds against 246.4 at 1024 bits and 3578
against 1534 at 2048 -- because it has that multiplication inside it and no
window, so it pays about twice the multiplications as well.

The README there says every function is written in a constant-time style, with
one named exception that is none of these, though it also says that unlike
functional correctness this is not machine-checked.

`p384_montjscalarmul` and `p521_jscalarmul`
have no affine wrapper upstream; crypton's is in `cbits/p256/p256_s2n.c`'s
sibling for those curves.  There is no fixed-base routine for P-384 or
P-521 at all, so signing on those curves keeps crypton's comb.