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 curves.  The number theory articles cover basic polynomial math over Galois Fields which are especially suited for digital electronics.  The elliptic curve articles cover the basics of how high level math can be used to create a secure key exchange between two computers on a network.

The left column covers number theory.  The first article is a gentle introduction to number theory. The basics are discussed in Polynomial Math which goes into a bit of detail.  A more FPGA friendly method is described in On Clock Cycle Polynomial Math. The Polynomial Inverse article describes an alternative method of computing an inverse shown in Polynomial Math which is also FPGA friendly.

The right column covers elliptic curve cryptography.  The first article is a general description and covers the core mathematical operations.  The second article describes more secure ways to exchange secret keys using public channels.  And the last article describes digital signatures which have many uses.

Number Theory

Elliptic Curve Cryptography

Number Theory for Codes Elliptic Curve Cryptography
Polynomial Math Elliptic Curve Key Exchange
One Clock Cycle Polynomial Math
Elliptic Curve Digital Signatures
Polynomial Inverse

When the time comes that you actually need to know any of this, you will be able to find a lot of books that cover number theory or elliptic curve mathematics.  There are a few that do both, and a great one to start with is "A Course in Number Theory and Cryptography" by Neal Koblitz. You will also find a lot of articles written in IEEE journals that focus on very specific problems and their solutions.  

Once you've implemented a few subroutines and gotten them to work, you will be on your way to being an expert.  The most important thing is to not be afraid to start.  The mathematics can seem daunting, but the reality is nothing more than AND, XOR and shift.  The translation from math to code is what makes engineering fun, especially when things actually work.  


Previous post by Mike :
   Number Theory for Codes
Next post by Mike :
   Dealing With Fixed Point Fractions

Comments:

[ - ]
Comment by microsoftwareDecember 22, 2015
It is time to exam a bit G(16) now using the irreducible polynomial x4+x3+1 to construct it.
A root of x4+x3+1=0 is the b=010.
We have :


b2=0100
b3=1000
b4=1001
b5=1011
b6=1111
b7=0111
b8=1110

so, a normal basis for G8 is the set B={b8, b4 , b2 , b}

The elements of G8 can be represented now using B.
we have:

table 1

0--->0000
1----1111
2----0001
3----1110
4----0010
5----1101
6----0011
7----1100
8----1011
9----0100
10---1010
11---0101
12---1001
13---0110
14---1000
15---0111

Lets try now to find some squares of polynomials
===================================================
example 1
A(x) = 13 x2 + 0 x + 0

B(x) = 13 x2 + 0 x + 0

A(x) × B(x) = 7 x4 + 0 x3 + 0 x2 + 0 x + 0

we observe that :13----> 0110---> one cyclic left shift =1100 ---->comming back using table 1 = 7

=================================================

example 2
A(x) = 6 x2 + 0 x + 0

B(x) = 6 x2 + 0 x + 0

A(x) × B(x) = 13 x4 + 0 x3 + 0 x2 + 0 x + 0

following the philosophy of example 1 we have:

6----0011-----0110------13

================================================

example 3

A(x) = 15 x2 + 0 x + 0

B(x) = 15 x2 + 0 x + 0

A(x) × B(x) = 3 x4 + 0 x3 + 0 x2 + 0 x + 0

15----0111----1110------3

Nice !!!


Merry Christmas and a happy ,with health, 2016.

[ - ]
Comment by microsoftwareDecember 22, 2015
oh no, correct it please!

so, a normal basis for G16 is the set B={b8, b4 , b2 , b}

The elements of G16 can be represented now using B.
[ - ]
Comment by drmikeDecember 22, 2015
That is $GF(2^4)$ x $GF(2^3)$. It is probably better to use hex notation for the $GF(2^4)$ elements rather than decimal index. So "15" is "0x7" and "3" is "0xE". Otherwise, very nice!!
Happy new year!

To post reply to a comment, click on the 'reply' button attached to each comment. To post a new comment (not a reply to a comment) check out the 'Write a Comment' tab at the top of the comments.

Registering will allow you to participate to the forums on ALL the related sites and give you access to all pdf downloads.

Sign up

I agree with the terms of use and privacy policy.

Subscribe to occasional newsletter. VERY easy to unsubscribe.
or Sign in