Mike Rosing Blog on EmbeddedRelated.com

Elliptic Curve Cryptography - Multiple Signatures

Mike Rosing — Sun, 19 Nov 2023 22:04:18 +0000

The use of point pairing becomes very useful when many people are required to sign one document. This is typical in a contract situation when several people are agreeing to a set of requirements. If we used the method described in the blog on signatures, each person would sign the document, and then the verification process would require checking every single signature. By using...

Elliptic Curve Cryptography - Extension Fields

Mike Rosing — Sun, 29 Oct 2023 18:12:36 +0000

Field Extension

When my kids play games they talk about "leveling up". To get to the mathematics of pairing points over elliptic curves, we need to "level up" to extension fields from prime fields. If you've done any work with binary codes this is actually very familiar. Rather than base 2 fields, we are going to use base $p$ fields. An extension field is over $F_{p^k}$. It is...

Elliptic Curve Cryptography - Key Exchange and Signatures

Mike Rosing — Sat, 21 Oct 2023 15:13:21 +0000

To recap the basic math, an elliptic curve over a finite field has points $(x, y)$ which satisfy the equation $$y^2 = x^3 + a x + b \text{ mod } q.$$When points are added to themselves multiple times we write the multiplication as $$Y = k P$$where $k$ is an integer. Since the number of points is finite, after a while we get to a value of $k = n$ such that $$\mathscr O = n P....

Elliptic Curve Cryptography - Security Considerations

Mike Rosing — Mon, 16 Oct 2023 15:51:11 +0000

Cryptographic security has a lot of components. The simple stuff is the mathematics which is what I want to talk about. The hard stuff is preventing people from giving away things that should be secret (Loose lips sink ships still holds today!). The cryptographic security I want to talk about here comes from solving a mathematical problem to find a secret. The assumption is the...

Elliptic Curve Cryptography - Basic Math

Mike Rosing — Tue, 10 Oct 2023 22:52:50 +0000

Cryptography is the art of hiding messages, NOT writing on graves, which is a direct translation a friend of mine once asked. I should have said "that's engraving!", but I was a week late. The main engine of encrypting a message uses a single key and a fast algorithm. The NIST standard is AES which can use key sizes of 128 bits, 192 bits, or 256 bits. Each of these is considered a...

New book on Elliptic Curve Cryptography

Mike Rosing — Wed, 30 Aug 2023 15:47:59 +0000

Last year I was asked by Manning Publications if I wanted to write another book on elliptic curve crypto. I said that as long as I can learn a lot of new math I'd love to. So I spent 6 months learning math and then another year writing. The first three chapters are now online here: http://mng.bz/D9NA

Along the way I had proposed to explain an encryption scheme described on NIST...

Ancient History

Mike Rosing — Mon, 18 Jan 2016 14:15:28 +0000

The other day I was downloading an IDE for a new (to me) OS. When I went to compile some sample code, it failed. I went onto a forum, where I was told "if you read the release notes you'd know that the peripheral libraries are in a legacy download". Well damn! Looking back at my previous versions I realized I must have done that and forgotten about it. Everything...

Dealing With Fixed Point Fractions

Mike Rosing — Tue, 05 Jan 2016 15:52:45 +0000

Fixed point fractional representation always gives me a headache because I screw it up the first time I try to implement an algorithm. The difference between integer operations and fractional operations is in the overflow. If the representation fits in the fixed point result, you can not tell the difference between fixed point integer and fixed point fractions. When integers...

Mathematics and Cryptography

Mike Rosing — Mon, 14 Dec 2015 15:53:29 +0000

The mathematics of number theory and elliptic curves can take a life time to learn because they are very deep subjects. As engineers we don't have time to earn PhD's in math along with all the things we have to learn just to make communications systems work. However, a little learning can go a long way to helping make our communications systems secure - we don't need to know...

Elliptic Curve Digital Signatures

Mike Rosing — Wed, 09 Dec 2015 13:24:00 +0000

A digital signature is used to prove a message is connected to a specific sender. The sender can not deny they sent that message once signed, and no one can modify the message and maintain the signature. The message itself is not necessarily secret. Certificates of authenticity, digital cash, and software distribution use digital signatures so recipients can verify they are getting what...

Elliptic Curve Key Exchange

Mike Rosing — Thu, 03 Dec 2015 16:45:53 +0000

Elliptic Curve Cryptography is used to create a Public Key system that allows two people (or computers) to exchange public data so that both sides know a secret that no one else can find in a reasonable time. The simplest method uses a fixed public key for each person. Once cracked, every message ever sent with that key is open. More advanced key exchange systems have...

Polynomial Inverse

Mike Rosing — Mon, 23 Nov 2015 16:51:06 +0000

One of the important steps of computing point addition over elliptic curves is a division of two polynomials. When working in $GF(2^n)$ we don't have large enough powers to actually do a division, so we compute the inverse of the denominator and then multiply. This is usually done using Euclid's method, but if squaring and multiplying are fast we can take advantage of these...

One Clock Cycle Polynomial Math

Mike Rosing — Fri, 20 Nov 2015 19:56:34 +0000

Error correction codes and cryptographic computations are most easily performed working with $GF(2^n)$ polynomials. By using very special values of $n$ we can build circuits which multiply and square in one clock cycle on an FPGA. These circuits come about by flipping back and forth between a standard polynomial basis and a normal basis representation of elements in $GF(2^n)$....

Elliptic Curve Cryptography

Mike Rosing — Mon, 16 Nov 2015 13:47:01 +0000

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. Public Key encryption is used to create a private key between two sides that have not previously communicated. Compared to the history...

Polynomial Math

Mike Rosing — Tue, 03 Nov 2015 15:24:16 +0000

Elliptic Curve Cryptography is used as a public key infrastructure to secure credit cards, phones and communications links. All these devices use either FPGA's or embedded microprocessors to compute the algorithms that make the mathematics work. While the math is not hard, it can be confusing the first time you see it. This blog is an introduction to the operations of squaring and...

Number Theory for Codes

Mike Rosing — Thu, 22 Oct 2015 20:01:21 +0000

Everything in the digital world is encoded. ASCII and Unicode are combinations of bits which have specific meanings to us. If we try to interpret a compiled program as Unicode, the result is a lot of garbage (and beeps!) To reduce errors in transmissions over radio links we use Error Correction Codes so that even when bits are lost we can recover the ASCII or...