Electronics Guide

Fundamental Concepts

Modular arithmetic confines calculations within a finite range, with all operations performed modulo some integer n:

• Modular addition: (a + b) mod n, straightforward with possible subtraction of n if the sum exceeds the modulus
• Modular subtraction: (a − b) mod n, potentially requiring addition of n if the difference is negative
• Modular multiplication: (a × b) mod n, the core operation requiring efficient reduction techniques
• Modular reduction: Computing the remainder after division by n, critical for maintaining operand sizes

The modulus n in cryptographic applications is typically 2048 bits or larger for RSA, making naive division-based reduction impractical.

Montgomery Multiplication

Montgomery multiplication transforms modular multiplication to avoid expensive division operations:

• Montgomery domain: Values are represented as aR mod n, where R is a power of 2 larger than n and coprime to it, which an odd modulus guarantees
• Domain conversion: Converting to Montgomery form requires one multiplication and reduction; converting back requires another
• Montgomery product: Computing abR⁻¹ mod n using only multiplication, addition, and shifts
• Interleaved approach: Combining multiplication and reduction steps to avoid double-width intermediate products

The Montgomery reduction process adds a carefully chosen multiple of n to make the result divisible by R, allowing a simple right shift instead of division. For a sequence of modular multiplications, the overhead of domain conversion is amortized across many operations.

Speed is only half of the reason Montgomery multiplication dominates cryptographic implementations. The other half is that its main loop contains no data-dependent division and no comparison against the modulus, so the instruction sequence does not vary with the secret operands. The textbook formulation spoils this with a final conditional subtraction that fires only when the intermediate result exceeds the modulus. That single branch is operand-dependent, and counting how often it fires across many operations has been enough to recover RSA private keys from a network-facing server. Two remedies are standard: choose R greater than four times the modulus and keep operands below twice the modulus, which makes the final subtraction unnecessary altogether, or perform the subtraction unconditionally and choose between the two candidate results with a constant-time mask.

Exponentiation Algorithms

Computing a^e mod n directly by repeated multiplication would require an impractical number of operations for cryptographic exponents. Efficient algorithms reduce this to roughly log₂(e) squarings plus a smaller number of multiplications:

• Square-and-multiply (binary method): Processing exponent bits from most or least significant, squaring for each bit and multiplying by the base only for each 1 bit
• m-ary exponentiation: Pre-computing a table of powers and processing several exponent bits per iteration
• Sliding window: Variable-length windows reducing the number of multiplications while limiting table size
• Fixed-window: Constant-time variant that performs the same operation sequence for every exponent and reads every table entry, selecting the wanted one arithmetically
• Square-and-multiply-always: Regularizing the binary method with a dummy multiplication on each 0 bit, at the cost of roughly a third more work

The choice of algorithm decides security as much as speed. Plain square-and-multiply performs a multiplication only where the exponent bit is 1, so the sequence of squarings and multiplications is the exponent written out. A single power or electromagnetic trace, or a careful timing measurement, can therefore expose an RSA private exponent. Window methods leak in a subtler way, because the table entry selected on each iteration depends on secret bits and the address of that entry is visible to anything sharing a cache. Implementations that must resist physical observation combine a regular algorithm with randomization: the Montgomery ladder or a fixed-window method for regularity, exponent blinding so that the same secret never drives the same operation sequence twice, and table access that touches every entry. Dummy operations alone are not sufficient, because an attacker who injects a fault into an operation whose result is discarded learns from the absence of an error that the operation was a dummy.

Chinese Remainder Theorem Optimization

For RSA private key operations where the modulus n = pq is the product of two primes, the Chinese Remainder Theorem (CRT) enables significant acceleration:

• Split computation: Computing separately modulo p and modulo q, then combining results
• Speedup factor: Roughly fourfold, because each of the two exponentiations uses half-size operands and a half-size exponent
• Recombination: Using Garner's formula or similar to reconstruct the final result from the two partial results
• Security considerations: A single faulty result in one of the two branches lets an attacker factor the modulus from one incorrect signature, so CRT implementations verify the result before releasing it

Hardware Implementation Considerations

Implementing modular exponentiation in hardware requires balancing multiple design factors:

• Operand width: Supporting 2048-bit, 3072-bit, and 4096-bit operations; NIST SP 800-57 Part 1 places a 2048-bit RSA modulus at 112 bits of security strength and a 3072-bit modulus at 128 bits
• Multiplier architecture: Word-serial multipliers trade throughput for area, while parallel arrays maximize speed
• Memory requirements: Storing pre-computed powers and intermediate values
• Pipeline depth: Breaking long operations into stages for higher throughput in batch processing

Elliptic Curve Mathematics

Cryptographic elliptic curves are defined by equations over finite fields, with points on the curve forming a mathematical group. Over a prime field GF(p) with p greater than 3, the curve is written in short Weierstrass form:

y² = x³ + ax + b

This is the short form, not the general Weierstrass equation. Reducing the general form to it requires dividing by 2 and by 3, so the short form applies only where the field characteristic is neither 2 nor 3. Curves over GF(2^m) take the form y² + xy = x³ + ax² + b instead, with b not equal to zero for the non-supersingular curves used in cryptography. A short Weierstrass curve must also be non-singular, which holds exactly when 4a³ + 27b² ≠ 0 in GF(p). A curve that violates that condition has a cusp or a node. The singular point breaks the chord-and-tangent rule, and the points that remain form a group isomorphic to the additive or the multiplicative group of a finite field, where the discrete logarithm problem is easy or far easier.

Whichever equation applies, the group structure built on it is the same:

• Point at infinity: The identity element for the group operation, analogous to zero in addition
• Point addition: Given two points P and Q, computing a third point R = P + Q by the chord-and-tangent construction
• Point doubling: Computing 2P, a special case with its own optimized formulas
• Point negation: For a point (x, y) on a short Weierstrass curve, the negation is (x, −y)

The security of ECC relies on the elliptic curve discrete logarithm problem: given points P and Q = kP, finding the scalar k is computationally infeasible for properly chosen curves and sufficiently large k.

Coordinate Systems

Different coordinate representations offer trade-offs between operation count and inversion requirements:

• Affine coordinates: Standard (x, y) representation requiring a modular inversion for every point operation
• Projective coordinates: Representing points as (X:Y:Z) where x = X/Z and y = Y/Z, deferring inversion
• Jacobian coordinates: Using (X:Y:Z) where x = X/Z² and y = Y/Z³, optimizing doubling operations
• Mixed coordinates: Adding an affine point to a Jacobian one, which saves several multiplications because the affine operand has Z equal to 1

Projective coordinates are preferred for hardware implementation because modular inversion is far more expensive than multiplication. A single inversion at the end of scalar multiplication converts the result back to affine coordinates.

Avoiding inversion is a security measure as much as an optimization. The extended Euclidean algorithm, usually the fastest way to invert in a prime field, runs for a number of iterations that depends on the value being inverted, so affine point arithmetic executes a secret-dependent number of iterations inside every point operation of a scalar multiplication. Deferring inversion removes that leak from the inner loop, and the one remaining inversion should itself run in fixed time, either by Fermat exponentiation, a⁻¹ = a^p−2 mod p, or by a binary algorithm written with constant-time conditional swaps. Projective coordinates bring a second benefit: because (X:Y:Z) and (λ²X:λ³Y:λZ) denote the same Jacobian point, drawing a fresh λ at the start of each scalar multiplication decorrelates the intermediate values from any fixed input and blunts differential power analysis.

Scalar Multiplication Algorithms

Scalar multiplication computes Q = kP for a large scalar k and base point P, the fundamental operation for ECC protocols:

• Double-and-add: Analogous to square-and-multiply, processing scalar bits with doubling and conditional addition, and leaking the scalar the same way
• Montgomery ladder: A regular algorithm performing exactly one addition and one doubling per bit regardless of bit value
• Window methods: Pre-computing small multiples of P to process several scalar bits per iteration
• NAF (Non-Adjacent Form): Representing the scalar with digits from {−1, 0, 1} to reduce the number of additions
• w-NAF: Generalized NAF with width-w digits, faster still but not constant time, because the spacing between additions reveals the digit pattern

The Montgomery ladder dominates security-focused implementations because its operation sequence is identical for every scalar, so neither timing nor the shape of a power trace distinguishes a 0 bit from a 1 bit. The regularity comes with conditions. The two ladder registers must be exchanged with an arithmetic mask rather than a branch, and the ladder by itself does nothing against differential power analysis, which correlates many traces against hypotheses about intermediate values rather than reading a single trace. Scalar blinding, which adds a random multiple of the group order to the scalar, and randomized projective coordinates are its usual companions. Signed-digit window methods remain attractive where the scalar is public, but signing keys have been recovered from ECDSA implementations that used a w-NAF scalar multiplication, by an attacker who merely shared a processor cache with the victim.

Field Arithmetic for ECC

Elliptic curve operations reduce to field arithmetic in GF(p) or GF(2^m):

• Prime field operations: Modular addition, subtraction, multiplication, and inversion in GF(p)
• Special primes: The P-256 prime 2²⁵⁶ − 2²²⁴ + 2¹⁹² + 2⁹⁶ − 1 is a sum of a few powers of 2, so reduction becomes a short fixed sequence of shifted additions and subtractions
• Pseudo-Mersenne primes: Primes just below a power of 2, such as the 2²⁵⁵ − 19 of Curve25519, allowing reduction by folding the high half back with a single small multiplication
• Montgomery reduction: Applicable to ECC field arithmetic as well as RSA, and the usual choice for a modulus with no exploitable structure

Binary-field curves once attracted hardware designers because GF(2^m) arithmetic needs no carry propagation. NIST SP 800-186 deprecated every binary curve it specifies, both the Koblitz K-curves and the pseudorandom B-curves, citing their limited adoption and directing new implementations to prime-field curves. Binary-field arithmetic remains central to AES and to GCM authentication, but it is no longer a recommended basis for elliptic curve key establishment or signatures.

Modern Curve Implementations

Contemporary curve designs simplify secure implementation:

• Curve25519: A Montgomery curve over the field of 2²⁵⁵ − 19, shaped for the ladder, whose x-coordinate-only scalar multiplication has no exceptional cases to branch around
• Edwards curves: Providing a single addition formula that is correct for every pair of inputs, including a doubling and the identity, which removes the branches those exceptional cases would otherwise demand
• Ed25519: The twisted Edwards curve birationally equivalent to Curve25519, used for signatures
• Curve448: A Montgomery curve over the field of 2⁴⁴⁸ − 2²²⁴ − 1, rated at 224 bits of security strength

NIST SP 800-186 specifies Curve25519, Curve448, and their Edwards forms alongside the older P-curves, placing the 255-bit curves at 128 bits of security strength and the 448-bit curves at 224 bits. The phrase "built-in side-channel resistance" attaches itself to Ed25519 and deserves qualification. Its signature nonce is derived deterministically by hashing the private key together with the message, which removes any dependence on the quality of the random number generator at signing time, a real and frequent source of key compromise in ECDSA. That same determinism is a liability against fault injection: an attacker who obtains two signatures over one message, one of them corrupted mid-computation, can solve for the private scalar. Deployments that face a physical attacker therefore mix fresh randomness back into the nonce derivation.

Binary Extension Fields

Fields of the form GF(2^m) are particularly suited to digital hardware:

• Polynomial representation: Field elements are polynomials over GF(2) of degree less than m
• Addition: Coefficient-wise XOR, requiring no carries
• Multiplication: Polynomial multiplication followed by reduction modulo an irreducible polynomial
• Irreducible polynomials: The field-defining polynomial, analogous to a prime modulus for prime fields

The carry-free nature of addition in GF(2^m) makes these fields highly efficient for hardware implementation.

AES Field Operations

The Advanced Encryption Standard operates in GF(2⁸) with the irreducible polynomial

x⁸ + x⁴ + x³ + x + 1

Every byte of the cipher state is an element of that field, and the round transformations are field operations on those bytes:

• S-box computation: Multiplicative inverse in GF(2⁸), with zero mapped to itself, followed by an affine transformation over GF(2)
• MixColumns: Matrix multiplication with coefficients in GF(2⁸)
• XTime operation: Multiplication by x (0x02) with conditional reduction
• Composite field implementations: Decomposing GF(2⁸) into GF((2⁴)²) or GF(((2²)²)²) for smaller hardware

Composite field techniques replace one inversion in a 256-element field with inversions and multiplications in fields of 16 or 4 elements, which is far cheaper in gates but adds levels of logic. The saving is not automatic. GF(2⁸) admits many isomorphisms onto a tower field, and the gate count of the resulting S-box varies widely with the choice of subfield polynomials and of basis; the smallest published AES S-boxes come from an exhaustive search over the choice of basis, polynomial or normal, for each subfield of the tower, in which an all-normal-basis tower proved smallest, rather than from the first isomorphism that works. The isomorphism and its inverse are themselves linear maps whose gates count toward the total, which is why a composite-field S-box pays off in a design that instantiates many of them and rarely in one that needs a single table.

Two further claims about composite-field S-boxes should be resisted. They are not constant-time in any useful sense merely by being composite: a combinational S-box settles in the same number of cycles for every input, but so does a table realized in logic, and neither statement says anything about power or electromagnetic leakage. Nor are they glitch-free. Signals in a deep combinational network arrive at different times, so a gate can transiently evaluate on a mixture of old and new inputs. Where the network carries masked shares, those transient values can recombine shares that were meant to stay separate, and first-order masking applied naively to a composite-field S-box has been shown to leak in hardware for exactly that reason. Glitch-resistant styles such as threshold implementations, which split every variable into shares and require each output share to be independent of at least one input share, exist because the combinational depth that makes composite fields small also makes them leaky.

GF(2¹²⁸) for Authentication

Galois/Counter Mode (GCM) authentication uses multiplication in GF(2¹²⁸):

• GHASH operation: Sequential multiplication by the hash subkey and XOR, accumulating the authentication tag
• Parallel implementations: Processing several blocks at once against pre-computed powers of the subkey, since the accumulation is a polynomial evaluation that splits cleanly
• Karatsuba multiplication: Building a 128-bit carry-less product from three 64-bit products instead of four, at the cost of extra XORs
• Lookup table approaches: Trading memory for computation in software implementations

The table-driven form carries a warning. It indexes pre-computed tables with values derived from the hash subkey, and on a processor with shared caches that access pattern is observable by other software, which exposes the subkey to cache-timing analysis; an attacker who recovers the subkey can forge authentication tags. Implementations that share a machine with untrusted code use carry-less multiply instructions or a bit-sliced formulation instead, neither of which touches a secret-dependent address.

Multiplication Algorithms

Various algorithms implement Galois field multiplication with different trade-offs:

• Shift-and-XOR: Basic bit-serial multiplication analogous to shift-and-add for integers
• Mastrovito multiplier: Parallel multiplication with built-in reduction
• Karatsuba method: Divide-and-conquer reducing multiplication complexity from O(n²) to O(n^1.58), the exponent being log₂3
• Tower field constructions: Hierarchical field decomposition enabling recursive implementation

Inversion Methods

Multiplicative inverse in Galois fields is required for several cryptographic operations:

• Extended Euclidean Algorithm: Iteratively computing the inverse using polynomial GCD, fast but with an operand-dependent iteration count
• Fermat's Little Theorem: Computing the inverse of a nonzero a as a⁻¹ = a^2m−2, a fixed exponentiation that takes the same number of steps for every operand
• Itoh-Tsujii algorithm: Optimized exponentiation using addition chains and Frobenius automorphism
• Lookup tables: Pre-computing all inverses for small field sizes like GF(2⁸)

Primality Testing

Probabilistic primality tests determine whether a candidate is likely prime:

• Miller-Rabin test: The most widely used probabilistic test, based on modular exponentiation
• Fermat test: A simpler but less reliable test checking whether aⁿ⁻¹ ≡ 1 (mod n), which the Carmichael numbers pass for every base coprime to n
• Lucas test: Often combined with Miller-Rabin for additional confidence
• False positive probability: Each random base bounds the chance of accepting a composite at 1/4, so k independent rounds give a worst-case error of at most 4^−k

This 4^−k bound is conservative: for the large random candidates used in key generation the true error is vastly smaller, so only a handful of rounds is needed to drive it below any realistic threshold. Table B.1 of FIPS 186-5 accordingly specifies modest fixed round counts that fall as the prime size grows, four rounds for 1024-bit RSA primes and two for 2048-bit primes at a target error probability of 2⁻¹⁰⁰, and Appendix C of the same standard gives the analysis those counts rest on. Implementations that must tolerate adversarially chosen candidates, rather than freshly generated random ones, instead use a large fixed count such as 40 or more, or combine Miller-Rabin with a Lucas test, a pairing that no composite is known to pass.

Sieving and Trial Division

Pre-filtering candidates before expensive primality testing dramatically improves efficiency:

• Trial division: Testing divisibility by small primes (typically the first few hundred or thousand)
• Sieve methods: Generating candidate sequences that avoid obvious composites
• Incremental sieving: Efficiently updating residues as candidates are tested
• Expected attempts: By the prime number theorem, a random n-bit candidate is prime with probability near 1/(n ln 2), so roughly n ln 2 (about 0.69n) candidates are tested on average—fewer once sieving removes multiples of small primes

Special Prime Forms

Cryptographic applications often require primes with specific properties:

• Safe primes: Primes p where (p − 1)/2 is also prime, used for Diffie-Hellman groups
• Strong primes: Extra conditions on the factors of p − 1 and p + 1, aimed at Pollard's p − 1 and Williams' p + 1 factoring methods; for randomly generated primes of modern length these conditions add little, since the general number field sieve is what actually bounds the difficulty
• Primes for ECC: Field primes with efficient reduction properties
• Balanced RSA primes: Similar bit lengths for the two factors

Hardware Prime Generation

Implementing prime generation in hardware presents specific challenges:

• Modular exponentiator reuse: Using the same hardware for primality testing and other operations
• Candidate generation: Efficient random candidate selection with basic filtering
• Parallel testing: Testing multiple candidates simultaneously when hardware permits
• Timing considerations: Variable generation time may leak information about prime values

Entropy Sources

True randomness originates from physical processes with inherent unpredictability:

• Thermal noise: Johnson-Nyquist noise in resistors and transistors
• Shot noise: Statistical fluctuations in electron flow
• Ring oscillator jitter: Timing variations in free-running oscillators
• Metastability: Unpredictable resolution of flip-flops in metastable states
• Quantum effects: Inherently random processes at the quantum level

Hardware random number generators must carefully extract entropy from these sources while accounting for potential biases and environmental influences. The line between the physical source and the deterministic machinery downstream of it is the one that matters most. Conditioning and DRBG expansion redistribute entropy; they never create it. A generator seeded with 80 bits of genuine entropy delivers 80 bits of unpredictability no matter how many gigabytes of output follow, so the entropy estimate for the source, justified by the statistical assessment that NIST SP 800-90B prescribes, sets the ceiling for everything built on top of it.

Conditioning and Extraction

Raw entropy sources typically exhibit biases that must be removed:

• Von Neumann extraction: Converting biased bits to unbiased by examining pairs
• Cryptographic hashing: Compressing entropy pool contents through hash functions
• Linear feedback shift registers: Whitening sequences to remove obvious patterns
• XOR combination: Combining multiple independent sources for improved quality

Deterministic Random Bit Generators

DRBGs expand true random seeds into longer sequences while maintaining cryptographic security. NIST SP 800-90A Revision 1 approves three mechanisms, whose names the standard spells with underscores. All three update their internal state after every request, so an attacker who captures the current state cannot reconstruct earlier output, a property the standard calls backtracking resistance:

• CTR_DRBG: Based on a block cipher in counter mode, almost always AES, which lets a hardware design reuse an existing AES core
• Hash_DRBG: Using an approved hash function for generation
• HMAC_DRBG: Based on HMAC, iterating the same keyed-hash construction used for message authentication
• Reseeding: Periodically incorporating fresh entropy to limit the damage from a state compromise, and to give prediction resistance when it is performed before a request

Earlier editions of SP 800-90A specified a fourth mechanism, Dual_EC_DRBG, which produced output from scalar multiplications on a NIST curve using two fixed points supplied in the standard. Researchers showed that whoever chose those points could have kept the scalar relating them, and that such a party could then predict all subsequent output after observing a modest quantity of generated bits. NIST removed the mechanism: Revision 1 of SP 800-90A, published in June 2015, deleted Dual_EC_DRBG along with its parameters, worked examples, and security discussion. The episode is why the provenance of a generator's constants is now treated as part of its security argument, and it is the one piece of this history worth knowing before trusting any random bit generator built on unexplained values.

The rest of the SP 800-90 series covers the surrounding machinery. SP 800-90B specifies how an entropy source is designed, health-tested, and given a min-entropy estimate, and SP 800-90C, finalized in September 2025, specifies the constructions that join an entropy source to a DRBG mechanism, including the case in which full-entropy output is required.

Health Monitoring

Hardware random number generators require continuous monitoring to detect failures:

• Startup tests: Verifying proper operation before generating output
• Continuous tests: Checking each output for obvious failures like stuck values
• Statistical tests: Monitoring entropy estimates and distribution properties
• Alarm mechanisms: Halting output and alerting when anomalies are detected

Implementation Standards

Cryptographic random number generators must meet rigorous standards:

• FIPS 140-3: The current requirements for cryptographic modules and the generators inside them; the validation program began accepting FIPS 140-3 submissions on 22 September 2020 and took its last FIPS 140-2 submissions for new certificates on 31 March 2022, and FIPS 140-2 modules could be selected for new systems only through 21 September 2026, after which the program places their certificates on its historical list, usable in existing systems only
• AIS 20/31: The German BSI evaluation methodology for deterministic and physical random number generators
• SP 800-90B: NIST specification for entropy source design, health testing, and min-entropy assessment
• Common Criteria: Protection profiles addressing random generation

SHA-2 Family

SHA-256 and SHA-512 dominate current deployments, sharing a common Merkle-Damgard construction over 32-bit and 64-bit words respectively:

• Message padding: Appending a 1 bit, zeros, and the message length to achieve a block-aligned input
• Message schedule: Expanding 512-bit (SHA-256) or 1024-bit (SHA-512) blocks into 64 or 80 words
• Compression function: Iterating rounds that mix working variables with scheduled message words and constants
• Finalization: Adding the compression output to the running hash state

The primary hardware optimization challenge is breaking the adder chains in the compression function critical path. The construction also carries a structural quirk with practical consequences: because the digest is the entire internal state, anyone who knows a digest and the length of the message behind it can continue hashing and produce a valid digest for an extended message. That length-extension property is why a keyed hash over SHA-2 uses the nested HMAC construction rather than simply prefixing a key to the message.

SHA-3 and Keccak

SHA-3 uses the Keccak sponge construction with fundamentally different characteristics:

• State array: A 1600-bit state organized as a 5 × 5 array of 64-bit lanes
• Permutation rounds: 24 rounds of the five step mappings θ, ρ, π, χ, and ι (theta, rho, pi, chi, and iota)
• Absorbing phase: XORing message blocks into the first r bits of the state, followed by a permutation; r is 1088 bits for SHA3-256, leaving a capacity of 512 bits that is never touched by the message
• Squeezing phase: Extracting output blocks with intervening permutations, which lets the same construction produce arbitrary-length output as SHAKE128 and SHAKE256

The sponge structure maps efficiently to hardware. Its round function is built from XOR, rotation, and AND, with no adders at all, so a round becomes a single wide layer of combinational logic and the 1600-bit state is the dominant resource requirement. The sponge also avoids length extension, because the capacity bits never appear in the output, which is why a keyed hash over SHA-3 can simply prefix the key. Extendable output has become more than a convenience: SHAKE128 and SHAKE256 expand the public matrices and sample the secrets inside ML-KEM and ML-DSA, and SHAKE is one of the two hash options for SLH-DSA, so a hash core that supports extendable output earns its area twice over.

Optimization Techniques

Hardware hash implementations employ various optimization strategies:

• Carry-save arithmetic: Maintaining sums in redundant form to reduce critical paths
• Pipelining: Breaking rounds into stages for throughput improvement
• Unrolling: Implementing multiple rounds in parallel where data dependencies permit
• Message schedule optimization: Pre-computing or pipelining the message expansion

Hash-Based Constructions

Hash functions serve as building blocks for larger cryptographic constructions:

• HMAC: Keyed hashing for message authentication using two nested hash operations
• HKDF: Key derivation extracting and expanding keying material
• Merkle trees: Hierarchical hashing for efficient verification of large data sets
• Commitment schemes: Hash-based commitments for cryptographic protocols

Timing Attack Prevention

Constant-time execution eliminates timing-based information leakage:

• Uniform control flow: Executing the same sequence of instructions regardless of secret values
• Constant-time selection: Using arithmetic rather than branches for conditional operations
• Regular algorithms: Preferring algorithms whose operation sequence does not depend on secret values, such as the Montgomery ladder
• Memory access patterns: Avoiding secret-dependent array indexing that could leak through cache timing

Where the Fast Algorithms Leak

Almost every optimization described earlier in this article was designed for speed before side channels were well understood, and several of them leak. A secure implementation starts from that list rather than from a general intention to be careful:

• Square-and-multiply and double-and-add: The operation sequence is the secret exponent or scalar, readable from a single trace
• Sliding-window and w-NAF methods: Table indices depend on secret digits, and the spacing of the additions reveals the digit pattern
• Montgomery multiplication: The conditional final subtraction is operand-dependent unless the parameters are chosen to eliminate it
• Affine point arithmetic: Euclidean inversion runs for a value-dependent number of iterations inside the inner loop
• Table-driven field multiplication: Secret-dependent memory addresses leak through shared caches
• CRT-based RSA: One faulty branch reveals a factor of the modulus
• Reduction of a signature nonce: A biased or variable-time reduction leaks a few bits per signature, and a few bits across enough signatures recover the private key by lattice reduction

The countermeasures appear in the sections around this one: regular algorithms, arithmetic selection in place of branches, blinding of exponents, scalars, and messages, and randomized projective representations. None of them is complete on its own, which is why a design that must survive laboratory analysis applies several at once and then measures the result rather than assuming it.

Power Analysis Countermeasures

Masking and hiding techniques protect against power consumption analysis:

• Boolean masking: XORing sensitive values with random masks, processing masked values throughout
• Arithmetic masking: Adding random values to operands in modular arithmetic
• Mask conversion: Securely converting between Boolean and arithmetic masks
• Higher-order masking: Using several mask shares so that an attacker must combine that many leakage points to learn anything
• Threshold implementations: Sharing schemes constructed so that glitches in combinational logic cannot recombine the shares, which ordinary masking in hardware does not guarantee

Blinding Techniques

Randomizing computations prevents correlation with known values:

• Message blinding: For RSA, computing (m · r^e)^d · r⁻¹ mod n for a fresh random r, rather than m^d directly, so that the exponentiation never runs on a value the attacker chose
• Exponent blinding: Adding a random multiple of the group order, or of Euler's totient in the RSA case, to the exponent so that no two operations run the same sequence
• Point blinding: For ECC, randomizing the base point representation
• Projective coordinate randomization: Using random equivalent projective representations

Fault Attack Resistance

Protecting against induced computational errors:

• Computation redundancy: Performing operations twice and comparing results
• Check values: Verifying algebraic relationships that should hold for correct computation
• CRT fault detection: Re-encrypting the result before release, verifying that s^e mod n equals the original input, which catches the single-prime faults exploited by the Bellcore attack
• Point validation: Verifying ECC intermediate points lie on the curve

Implementation Patterns

Secure implementation follows established patterns:

• Algorithm selection: Choosing algorithms with inherent resistance properties
• Constant-time primitives: Building from verified constant-time basic operations
• Randomization integration: Systematically incorporating randomness throughout computation
• Defense in depth: Combining multiple countermeasures for comprehensive protection

Basic Operations

Multi-precision arithmetic builds complex operations from word-level primitives:

• Addition with carry: Propagating carries across the full operand width
• Subtraction with borrow: Managing borrow chains analogously to carries
• Word-by-word multiplication: Computing partial products and accumulating with proper alignment
• Comparison: Determining ordering through high-to-low word comparison

Multiplication Algorithms

Large operand multiplication employs algorithms with sub-quadratic complexity:

• Schoolbook multiplication: O(n²) complexity, practical for smaller operands
• Karatsuba multiplication: Divide-and-conquer achieving O(n^1.58) complexity, the exponent being log₂3
• Toom-Cook: Generalized polynomial evaluation and interpolation; the three-way split reaches O(n^1.46), the exponent log₃5, and higher splits approach but never reach linear-logarithmic behavior
• Number Theoretic Transform: FFT-style multiplication; the Schonhage-Strassen algorithm achieves O(n log n log log n), and later theoretical work has lowered the bound further still

These are asymptotic bounds, and the constants decide which algorithm actually wins. Every level of Karatsuba recursion trades one multiplication for several additions and extra bookkeeping, so libraries leave schoolbook behind only above a threshold of a few dozen machine words, move to Toom-Cook at larger sizes still, and reach FFT-based methods only in the thousands. Cryptographic operands sit below most of those thresholds. A 256-bit elliptic curve field element is four 64-bit words and is multiplied schoolbook, usually by a fully unrolled routine; a 2048-bit RSA modulus is thirty-two words and sits near the Karatsuba crossover, where the gain is real but modest. The asymptotically superior algorithms earn their place on the very large integers of primality proofs and on the polynomial arithmetic of post-quantum schemes, not on the field arithmetic of everyday elliptic curve work. One practical consequence follows: a library that switches multiplication algorithms according to operand size introduces a timing difference tied to that size, which has been exploited where the operand size itself reflected a secret.

Modular Reduction

Efficient reduction is critical for modular arithmetic performance:

• Barrett reduction: Pre-computing a scaled reciprocal for approximate division
• Montgomery reduction: Avoiding division through careful construction
• Special form moduli: Exploiting structure in primes like Mersenne or pseudo-Mersenne forms
• Residue number systems: Representing values by residues modulo several smaller moduli

Hardware Architecture Choices

Multi-precision arithmetic hardware spans a design spectrum:

• Word-serial: Processing one word at a time with minimal hardware, maximizing area efficiency
• Digit-serial: Intermediate parallelism with multiple-word processing
• Full parallel: Complete operand-width datapaths for maximum throughput
• Systolic arrays: Regular structures with local communication for scalable implementation

Polynomial Ring Arithmetic

Lattice-based schemes operate on polynomials in rings of the form Z_q[x]/(xⁿ + 1), where n is a power of 2 and q is a small prime:

• Polynomial addition: Coefficient-wise addition modulo q
• Polynomial multiplication: Convolution followed by reduction modulo xⁿ + 1
• Negacyclic property: The reduction xⁿ = −1 wraps overflowing terms back with a change of sign, which costs a subtraction and nothing more
• Coefficient operations: Modular arithmetic on each coefficient, small enough that a Montgomery or Barrett reduction on a single machine word suffices

The standards choose their parameters with the transform in mind. ML-KEM uses n = 256 with q = 3329, and ML-DSA uses n = 256 with q = 8380417, which is 2²³ − 2¹³ + 1. Both moduli are far smaller than an RSA or elliptic curve modulus, so every coefficient fits comfortably in a machine word. The difficulty moves from operand width to the sheer number of coefficient operations and the memory traffic they generate, which is the opposite of the problem classical public-key arithmetic poses.

Number Theoretic Transform

The NTT accelerates polynomial multiplication in post-quantum schemes:

• FFT analog: Transforming polynomial multiplication into point-wise multiplication in the transform domain, which reduces the coefficient-by-coefficient cost from quadratic to linear-logarithmic
• Finite field roots: Using roots of unity that exist in the coefficient ring, which is why q is chosen so that q − 1 is divisible by a large power of 2
• Butterfly operations: The basic computational unit, combining addition, subtraction, and modular multiplication by a twiddle factor
• Memory access patterns: Bit-reversal or constant-geometry arrangements

How far the transform can go depends on that arithmetic detail. For ML-DSA, q − 1 is divisible by 2¹³, which supplies a primitive 512th root of unity and permits a complete length-256 transform in which multiplication becomes 256 independent coefficient products. For ML-KEM, q − 1 is 2⁸ × 13, which supplies only a 256th root, so the transform stops one level short: x²⁵⁶ + 1 factors only into 128 quadratics, a transformed polynomial is 128 residues of two coefficients each, and the point-wise stage multiplies those pairs modulo the corresponding quadratic. A hardware NTT unit therefore has to be written for the scheme it serves rather than reused unchanged between them.

Sampling from Distributions

Lattice schemes require sampling from specific probability distributions:

• Discrete Gaussian: Bell-shaped distribution over the integers, required by Falcon and by several older lattice designs, and notably awkward to sample in constant time
• Centered binomial: The simpler distribution ML-KEM uses for its secret and error polynomials, formed by subtracting the Hamming weights of two short random bit strings
• Bounded uniform with rejection: ML-DSA takes a different route, drawing secret coefficients uniformly from a small symmetric range and discarding candidate values that fall outside it
• Rejection sampling in signing: ML-DSA follows the Fiat-Shamir with aborts pattern, restarting the signature whenever the candidate response would betray information about the private key, so signing time varies by design
• Constant-time sampling: Arranging that whatever timing variation remains depends only on public or freshly random values, never on the private key

Hardware Considerations

PQC hardware implementation presents new challenges:

• Large state sizes: Degree-256 polynomials gathered into vectors and matrices whose dimensions grow with the security level, so a single key or signature occupies kilobytes where an elliptic curve needs tens of bytes
• NTT units: Dedicated butterfly processors with modular arithmetic
• Memory bandwidth: Moving large polynomials efficiently between computation and storage
• Hybrid designs: Supporting both classical and post-quantum algorithms during transition