miesource/ecc_hardware_Accelerator_P · Elliptic curve scalar multiplication over P-256, VHDL, GHDL-verified, constant-time Montgomery ladder with parallel multipliers, AXI4-Lite
The plan going in was small: take my GF(2^233) scalar multiplier, keep the architecture, swap the field. Prime fields and binary fields agree on almost nothing at the level that matters for hardware, so “keep the architecture” mostly meant keeping the shape of the thing, not the content. Constant time as to not leak timing information about the scalar, a parallel-multiplier datapath to make that core’s extra cost bearable, and an AXI4-Lite slave to put the whole thing on a bus instead of a serial port.
What a prime field takes away
The binary-field version got two things almost for free that don’t exist here. Addition was XOR, no carry, one gate deep. Squaring was linear, since squaring is the Freshman’s Dream, so it cost a bit-spread instead of a multiply. Neither survives the move to GF(p). Addition needs a real carry-propagate adder and a conditional correction (add or subtract p depending on which way the result overflowed), and squaring costs exactly what a general multiply costs, because there’s no shortcut once you’re not in characteristic 2. The inversion story follows the same pattern: the binary version used Itoh-Tsujii, which works by getting a pile of squarings for free and using them to build up a large exponent quickly. Take away free squaring and there’s nothing to build the shortcut out of, so inversion here is plain Fermat, square-and-multiply over the full 256-bit exponent, no faster path available.
A Residue Number System project of mine did not make it to light at last, but some parts of it did. MODADDER a block that computes a sum two ways at once, the direct sum and the sum minus the modulus, and picks whichever one didn’t over/underflow. It’s built out of Xilinx CARRY4 primitive to reduce the propagation delay, but does not simulate in GHDL without proprietary libraries and doesn’t synthesize anywhere but Xilinx. The algorithm generalizes cleanly to any width, though, so fp_mod_add.vhd here is the same two-path structure at 256 bits with plain VHDL arithmetic standing in for the carry chain.
Two addition formulas, because one operand isn’t always fixed
Jacobian coordinates put off the field inversion that plain affine arithmetic needs on every point addition, paying for it once at the very end instead. The doubling formula is the standard shortcut for curves with a = -3, which P-256 has, so that part carried over cleanly. Addition is where it splits into two.
The ordinary scalar multiplication loop keeps a fixed base point at Z=1 the whole time, which lets the addition formula skip several multiplications it would otherwise need. That’s jac_point_add.vhd, 11 field multiplications, same shape as the binary-field version’s Z=1 shortcut. The constant-time core can’t make that assumption. Its two accumulators both have general Z throughout, so it needs the fully general formula (add-2007-bl, 16 multiplications instead of 11) in jac_point_add_general.vhd. That formula also isn’t valid for every input, it breaks down when the two points share an X coordinate, which is a fact the ladder has to work around rather than something the formula handles on its own.
More multipliers, where it actually helps
fp_mult_interleaved.vhd always takes exactly 256 cycles, regardless of its inputs. Four copies of it, started on the same clock edge, always finish on the same clock edge. That’s the whole trick behind the parallel modules: work out which multiplies in a formula are independent of each other, put those in the same batch, run the batch on separate multiplier instances, and there’s no need to track which instance finished when, since they all finish together. Point doubling’s 8 multiplies split into 4 batches this way; the general addition’s 16 split into 5. Measured, not estimated: the single-multiplier doubler finishes 2G in 20865ns, the 4-multiplier version finishes the same computation in 10495ns, almost exactly the 2x the batch analysis predicted.
The ladder itself gets one more layer of parallelism on top of that. Every round, it needs one point doubling and one point addition, and neither depends on the other’s result within that round, both only need the state from the start of the round. So they run at the same time, one on the 4-multiplier doubler, one on the 4-multiplier general adder, 8 multiplier instances active together during the main loop.
The ladder, and the mux that replaces a swap
The usual double-and-add loop only calls point addition when the current scalar bit is 1. Whether that call happens, and how long it takes, depends on the bit, which is exactly the kind of thing you don’t want if the scalar needs to stay secret. The fix is a Montgomery ladder: every round does one addition and one doubling, unconditionally, and only which register receives which result depends on the bit, selected by a multiplexer rather than skipped or not skipped.
add_result <- R0 + R1 (always, same fixed order)
double_input <- b=1 ? R1 : R0 (mux)
double_result <- 2 * double_input
R0 <- b=1 ? add_result : double_result
R1 <- b=1 ? double_result : add_resultWorking through both cases by hand against the textbook ladder (swap R0 and R1 if the bit is 1, add, double, swap back) confirms they land on the same R0 and R1 either way, this is just the swap written as two small selects around a fixed-order add and a fixed doubling instead of two literal register swaps. The other piece the general addition formula doesn’t handle on its own is the very first round, where one accumulator is still the point at infinity by construction. jac_point_add_general runs its full 5-batch computation regardless, then picks the right answer, either the formula’s output or the untouched other operand, with a mux at the end. Same cost either way, nothing skipped.
What “constant time” turned out to mean, and where the evidence stops
Two scalars with very different bit patterns, k=1 (one bit set out of 256) and k=5, both ran through the full constant-time core and both took exactly 435729 clock cycles, not approximately the same, identical. That’s the strongest kind of confirmation a simulation can give for this specific property.
A harder version of the same test, k=1 against k=n-1 (166 bits set, about as dense as a scalar gets), didn’t finish in the time available. The sparse case took under a minute; the dense one ran past several minutes without completing. Every state transition in every FSM in this design was checked by hand and none of them branch to a different state based on scalar bits, only on fixed counters and completion flags, so the likely explanation is that denser bit patterns cause more combinational switching activity, which costs an event-driven simulator more work per clock edge even when the actual clocked cycle count is identical.
Getting it onto a bus
axi_lite_ecc_wrapper.vhd puts the constant-time core behind a 32-bit register file, one AXI transaction at a time, which is fully within spec for AXI4-Lite and is all a control/status interface like this needs. 256-bit values split across 8 words each for k, the base point, and the result; write the operands, write a start bit, poll a status register, read the result back. Checked with a real bus-functional-model testbench driving actual VALID/READY handshaking on all five channels, computing 5*G through the register map and getting the right answer back.
Running it
git clone https://github.com/miesource/ecc_scalar_mult_p256.git
cd ecc_scalar_mult_p256
sudo apt-get install ghdl
./scripts/run_tests.shApache 2.0 licensed.