Elliptic Curve Key Exchange
Elliptic Curve key exchange gives a fresh secret for every session so past messages stay safe even if one key is discovered. This post walks through an ElGamal-style ephemeral exchange and the MQV protocol, showing how MQV mixes static and random keys to provide mutual authentication and forward secrecy. It also explains how MQV can be implemented using only curve operations to save FPGA area and why erasing ephemeral values matters.
Polynomial Inverse
One of the important steps of computing point addition over elliptic curves is a division of two polynomials.
One Clock Cycle Polynomial Math
Error correction codes and cryptographic computations are most easily performed working with GF(2^n)
Elliptic Curve Cryptography
Secure online communications require encryption. One standard is AES (Advanced Encryption Standard) from NIST. But for this to work, both sides need the same key for encryption and decryption. This is called Private Key encryption.
Ten Little Algorithms, Part 5: Quadratic Extremum Interpolation and Chandrupatla's Method
Today we will be drifting back into the topic of numerical methods, and look at an algorithm that takes in a series of discretely-sampled data points, and estimates the maximum value of the waveform they were sampled from.
Polynomial Math
This post walks through squaring and inversion in a tiny finite field to make ECC math tangible. Using GF(2^5) with primitive polynomial beta^5 + beta^2 + 1 it shows why squaring cancels cross terms so you only need half the lookup table, and how Fermat exponentiation computes inverses via repeated squarings and multiplies. It also demonstrates the Extended Euclid polynomial inverse and compares FPGA and CPU tradeoffs.
Number Theory for Codes
If CRCs have felt like black magic, this post peels back the curtain with basic number theory and polynomial arithmetic over GF(2). It shows how fixed-width processor arithmetic becomes arithmetic in a finite field, how bit sequences are treated as polynomials, and why primitive polynomials generate every nonzero element. You also get practical insights on CRC implementation with byte tables and LFSRs.
Practical CRCs for Embedded Systems
Stephen Friederichs shows a practical way to get correct CRC code quickly by using PyCRC to generate C implementations, then verifying them on the desktop and an AVR ATMega328P. The post walks through the common generation algorithms, how to self-test with the standard "123456789" check value, and a real timing comparison that exposes the speed versus memory tradeoffs for embedded systems.
Ten Little Algorithms, Part 4: Topological Sort
Jason Sachs detours from signal processing to make topological sort feel practical and even a little funny, using a Martian Stew recipe to illustrate dependencies and cycles. He walks through two canonical algorithms, Kahn’s method and the depth-first-search variant, compares adjacency-list and matrix graph representations, and provides complete Python implementations so you can run and inspect cycle detection and ordering yourself.
Ten Little Algorithms, Part 3: Welford's Method (and Friends)
Jason Sachs takes a practical look at Welford's method, a numerically stable online algorithm for computing mean and sample variance without storing large batches. He demonstrates Python implementations, shows why the naive sum and sum-of-squares approach suffers catastrophic cancellation, and why Welford is a better fit for memory- and CPU-constrained embedded systems. Jason then turns Welford into simple filters for tracking time-varying noise and discusses heuristic fixes and tradeoffs.
Elliptic Curve Cryptography
Secure online communications require encryption. One standard is AES (Advanced Encryption Standard) from NIST. But for this to work, both sides need the same key for encryption and decryption. This is called Private Key encryption.
Polynomial Math
This post walks through squaring and inversion in a tiny finite field to make ECC math tangible. Using GF(2^5) with primitive polynomial beta^5 + beta^2 + 1 it shows why squaring cancels cross terms so you only need half the lookup table, and how Fermat exponentiation computes inverses via repeated squarings and multiplies. It also demonstrates the Extended Euclid polynomial inverse and compares FPGA and CPU tradeoffs.
Polynomial Inverse
One of the important steps of computing point addition over elliptic curves is a division of two polynomials.
One Clock Cycle Polynomial Math
Error correction codes and cryptographic computations are most easily performed working with GF(2^n)
Elliptic Curve Cryptography - Multiple Signatures
Point pairings let you compress many independent elliptic-curve signatures into a single verification, reducing n checks to one. This post explains how each signer derives a coefficient from the ordered list of public keys, aggregates signatures on the base group and public keys on the extension group, and verifies everything with one pairing computation. It also flags practical cautions like key validation and agreed ordering.
Ten Little Algorithms, Part 4: Topological Sort
Jason Sachs detours from signal processing to make topological sort feel practical and even a little funny, using a Martian Stew recipe to illustrate dependencies and cycles. He walks through two canonical algorithms, Kahn’s method and the depth-first-search variant, compares adjacency-list and matrix graph representations, and provides complete Python implementations so you can run and inspect cycle detection and ordering yourself.
Mathematics and Cryptography
Cryptographic math can look intimidating, but this roundup trims it to what FPGA engineers actually need. It groups concise articles on number theory and elliptic curves, focusing on polynomial math over Galois fields, FPGA-friendly inversion and one-clock-cycle techniques, and elliptic-curve key exchange and digital signatures. Read this to learn which subroutines to implement first and how to turn math into Verilog or VHDL.
Linear Regression with Evenly-Spaced Abscissae
Jason Sachs cuts through the matrix algebra to show a tiny trick for linear regression when x values are evenly spaced. You can compute the intercept as the mean and the slope as a simple weighted sum with arithmetic weights, using q = 12/(m^3 - m). The post includes Python examples and a compact routine to get least-squares coefficients without matrix solvers.
Elliptic Curve Key Exchange
Elliptic Curve key exchange gives a fresh secret for every session so past messages stay safe even if one key is discovered. This post walks through an ElGamal-style ephemeral exchange and the MQV protocol, showing how MQV mixes static and random keys to provide mutual authentication and forward secrecy. It also explains how MQV can be implemented using only curve operations to save FPGA area and why erasing ephemeral values matters.
Flood Fill, or: The Joy of Resource Constraints
When transferred from the PC world to a microcontroller, a famous, tried-and-true graphics algorithm is no longer viable. The challenge of creating an alternative under severe resource constraints is an intriguing puzzle, the kind that keeps embedded development fun and interesting.
Linear Feedback Shift Registers for the Uninitiated, Part IX: Decimation, Trace Parity, and Cyclotomic Cosets
Taking every jth bit of a maximal-length LFSR uncovers a surprising algebraic structure. Jason Sachs walks through cyclotomic cosets, shows why decimation by powers of two preserves minimal polynomials, and connects LFSR output to trace parity and simple bitmask parity computations. The article uses hands-on Python with libgf2, Berlekamp-Massey, and state recovery so you can reproduce and automate these analyses.
Elliptic Curve Key Exchange
Elliptic Curve key exchange gives a fresh secret for every session so past messages stay safe even if one key is discovered. This post walks through an ElGamal-style ephemeral exchange and the MQV protocol, showing how MQV mixes static and random keys to provide mutual authentication and forward secrecy. It also explains how MQV can be implemented using only curve operations to save FPGA area and why erasing ephemeral values matters.
Finite State Machines (FSM) in Embedded Systems (Part 3) - Unuglify C++ FSM with DSL
Domain Specific Languages (DSL) are an effective way to avoid boilerplate or repetitive code. Using DSLs lets the programmer focus on the problem domain, rather than the mechanisms used to solve it. Here I show how to design and implement a DSL using the C++ preprocessor, using the FSM library, and the examples I presented in my previous articles.
Elliptic Curve Cryptography - Security Considerations
The security of elliptic curve cryptography is determined by the elliptic curve discrete log problem. This article explains what that means. A comparison with real number logarithm and modular arithmetic gives context for why it is called a log problem.
You Don't Need an RTOS (Part 4)
In this fourth (and final!) article I'll share with you the last of the inter-process communication (IPC) methods I mentioned in Part 3: mailboxes/queues, counting semaphores, the Observer pattern, and something I'm calling a "marquee". When we're done, we'll have created the scaffolding for tasks to interact in all sorts of different the ways. Additionally, I'll share with you another alternative design for a non-preemptive scheduler called a dispatch queue that is simple to conceptualize and, like the time-triggered scheduler, can help you schedule some of your most difficult task sets.
Polynomial Math
This post walks through squaring and inversion in a tiny finite field to make ECC math tangible. Using GF(2^5) with primitive polynomial beta^5 + beta^2 + 1 it shows why squaring cancels cross terms so you only need half the lookup table, and how Fermat exponentiation computes inverses via repeated squarings and multiplies. It also demonstrates the Extended Euclid polynomial inverse and compares FPGA and CPU tradeoffs.
Elliptic Curve Cryptography - Extension Fields
An introduction to the pairing of points on elliptic curves. Point pairing normally requires curves over an extension field because the structure of an elliptic curve has two independent sets of points if it is large enough. The rules of pairings are described in a general way to show they can be useful for verification purposes.
Elliptic Curve Digital Signatures
Elliptic curve digital signatures deliver compact, strong message authentication by combining a hash of the message with elliptic curve point math. This post walks through the standard sign and verify equations, showing why recomputing a point R' yields the same x coordinate only when the hash matches. It also explains the Nyberg-Rueppel alternative that removes modular inversion and an FPGA-friendly trick of transmitting point D to avoid integer modular arithmetic.
Elliptic Curve Cryptography - Multiple Signatures
Point pairings let you compress many independent elliptic-curve signatures into a single verification, reducing n checks to one. This post explains how each signer derives a coefficient from the ordered list of public keys, aggregates signatures on the base group and public keys on the extension group, and verifies everything with one pairing computation. It also flags practical cautions like key validation and agreed ordering.
Flood Fill, or: The Joy of Resource Constraints
When transferred from the PC world to a microcontroller, a famous, tried-and-true graphics algorithm is no longer viable. The challenge of creating an alternative under severe resource constraints is an intriguing puzzle, the kind that keeps embedded development fun and interesting.
