Running Average

Mike February 15, 20166 comments

The running average filter is a useful way to reduce noise in a system.  One project I recently worked on required a 4 times frequency output from an encoder input.  The problem was the encoder is mounted to the wheel of an old truck and bearing noise was making the original algorithm generate way too many pulses.  The original algorithm worked, but the noise on the input made it useless.

I first implemented the moving average based on


Ancient History

Mike January 18, 201612 comments

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 changes, and keeping up with it takes time and effort.

When I first started with microprocessors we...


Dealing With Fixed Point Fractions

Mike January 5, 20163 comments

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 overflow, they lose data off the most significant bits.  When fractions overflow, they lose data off...


Mathematics and Cryptography

Mike December 14, 20153 comments

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 everything. The following articles are broken down into two realms, number theory and elliptic...


Elliptic Curve Digital Signatures

Mike December 9, 2015

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 they paid for.

Since messages can be of any length and mathematical algorithms always use fixed...


Elliptic Curve Key Exchange

Mike December 3, 2015

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 "perfect forward secrecy" which means that even if one message key is cracked, no other message will...


Polynomial Inverse

Mike November 23, 20152 comments

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 operations and compute the multiplicative inverse in just a few steps.

The first time I ran across this...


One Clock Cycle Polynomial Math

Mike November 20, 201514 comments

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)$.

A normal basis is yet another form of polynomial but instead of adding powers of $\beta$ we add...


Elliptic Curve Cryptography

Mike November 16, 20156 comments

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 of encryption, Public Key methods are very recent having been started in the 1970's.  Elliptic...


Polynomial Math

Mike November 3, 20152 comments

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 computing an inverse over a finite field which are used in computing Elliptic Curve arithmetic. ...


Elliptic Curve Cryptography

Mike November 16, 20156 comments

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 of encryption, Public Key methods are very recent having been started in the 1970's.  Elliptic...


Dealing With Fixed Point Fractions

Mike January 5, 20163 comments

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 overflow, they lose data off the most significant bits.  When fractions overflow, they lose data off...


Running Average

Mike February 15, 20166 comments

The running average filter is a useful way to reduce noise in a system.  One project I recently worked on required a 4 times frequency output from an encoder input.  The problem was the encoder is mounted to the wheel of an old truck and bearing noise was making the original algorithm generate way too many pulses.  The original algorithm worked, but the noise on the input made it useless.

I first implemented the moving average based on


Mathematics and Cryptography

Mike December 14, 20153 comments

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 everything. The following articles are broken down into two realms, number theory and elliptic...


Ancient History

Mike January 18, 201612 comments

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 changes, and keeping up with it takes time and effort.

When I first started with microprocessors we...


One Clock Cycle Polynomial Math

Mike November 20, 201514 comments

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)$.

A normal basis is yet another form of polynomial but instead of adding powers of $\beta$ we add...


Elliptic Curve Key Exchange

Mike December 3, 2015

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 "perfect forward secrecy" which means that even if one message key is cracked, no other message will...


Polynomial Inverse

Mike November 23, 20152 comments

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 operations and compute the multiplicative inverse in just a few steps.

The first time I ran across this...


Elliptic Curve Digital Signatures

Mike December 9, 2015

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 they paid for.

Since messages can be of any length and mathematical algorithms always use fixed...


Polynomial Math

Mike November 3, 20152 comments

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 computing an inverse over a finite field which are used in computing Elliptic Curve arithmetic. ...