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


Number Theory for Codes

Mike October 22, 20156 comments

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 Unicode original.  To prevent anyone from understanding a transmission we can encrypt the raw data...


The CRC Wild Goose Chase: PPP Does What?!?!?!

Jason Sachs October 23, 20142 comments

I got a bad feeling yesterday when I had to include reference information about a 16-bit CRC in a serial protocol document I was writing. And I knew it wasn’t going to end well.

The last time I looked into CRC algorithms was about five years ago. And the time before that… sometime back in 2004 or 2005? It seems like it comes up periodically, like the seventeen-year locust or sunspots or El Niño,...


Reverse engineering wireless wall outlets

Fabien Le Mentec July 19, 2014
Introduction

I am improving the domotics framework that I described in a previous article://www.embeddedrelated.com/showarticle/605.php

I want to support wireless wall outlets, allowing me to switch devices power from a remote location over HTTP.

To do so, I could design my own wireless wall outlets and use a hardware similar to the previous one, based on the NRF905 chipset. The problem is that such a product would not be certified, and that would be an issue regarding the home insurance,...


Using a RTLSDR dongle to validate NRF905 configuration

Fabien Le Mentec January 27, 20146 comments
I am currently working on a system to monitor the garage door status from my flat. Both places are 7 floors apart, and I need to send the data wirelessly. I chose to operate on the 433MHz carrier, and I ordered 2 PTR8000 modules: http://www.electrodragon.com/w/NRF905_Transceiver_433MHz-Wireless_ModuleThe PTR8000 is based on the dual band sub 1GHz NRF905 chipset from NORDICSEMI: http://www.nordicsemi.com/eng/Products/Sub-1-GHz-RF/nRF905I...

MSP430 LaunchPad Tutorial - Part 4 - UART Transmission

Enrico Garante July 3, 201320 comments

Today we are going to learn how to communicate using UART with the Launchpad. For this purpose I will replace the default microcontroller that comes with the board with the MSP430G2553. It is the most powerful device in the MSP430 Value Line and it comes with an integrated hardware UART module, along with 16 Kb of Flash memory, 512 bytes of SRAM and an 8-channel, 10 bit ADC.

UART communication can be useful when dealing with sensors: as a basic example, we could...


Linear Feedback Shift Registers for the Uninitiated, Part XVII: Reverse-Engineering the CRC

Jason Sachs July 7, 20181 comment

Last time, we continued a discussion about error detection and correction by covering Reed-Solomon encoding. I was going to move on to another topic, but then there was this post on Reddit asking how to determine unknown CRC parameters:

I am seeking to reverse engineer an 8-bit CRC. I don’t know the generator code that’s used, but can lay my hands on any number of output sequences given an input sequence.

This is something I call the “unknown oracle”...


Linear Feedback Shift Registers for the Uninitiated, Part XII: Spread-Spectrum Fundamentals

Jason Sachs December 29, 20171 comment

Last time we looked at the use of LFSRs for pseudorandom number generation, or PRNG, and saw two things:

  • the use of LFSR state for PRNG has undesirable serial correlation and frequency-domain properties
  • the use of single bits of LFSR output has good frequency-domain properties, and its autocorrelation values are so close to zero that they are actually better than a statistically random bit stream

The unusually-good correlation properties...


Linear Feedback Shift Registers for the Uninitiated, Part XV: Error Detection and Correction

Jason Sachs June 12, 2018

Last time, we talked about Gold codes, a specially-constructed set of pseudorandom bit sequences (PRBS) with low mutual cross-correlation, which are used in many spread-spectrum communications systems, including the Global Positioning System.

This time we are wading into the field of error detection and correction, in particular CRCs and Hamming codes.

Ernie, You Have a Banana in Your Ear

I have had a really really tough time writing this article. I like the...


Designing Communication Protocols, Practical Aspects

Fotis Chatzinikolaou May 14, 20192 comments

For most embedded developers always comes the time when they have to make their embedded MCU talk to another system. That other system will be a PC or a different embedded system or a smartphone etc. For the purpose of this article I am assuming that we are in the control of the protocol between the two ends and we don’t have to follow something that is already in place on one side.

So let’s say that we have our embedded MCU, we have implemented and configured the USB stack (or just...


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


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


Number Theory for Codes

Mike October 22, 20156 comments

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 Unicode original.  To prevent anyone from understanding a transmission we can encrypt the raw data...


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