polynomial extended euclidean algorithm

T

Tiza Naziri

Hi,

Anybody have an idea on how to start writing a C code for generating
the inverse of finite field GF(2^8) using extended Euclidean algorithm?
What I mean is how to represent a polynomial, e.g. f(x)=x^8+x^4+x^3+x+1
in C? How to represent the multiplication & division process of
polynomial?

Regards.

-- Tiza --
 
J

jacob navia

Tiza said:
Hi,

Anybody have an idea on how to start writing a C code for generating
the inverse of finite field GF(2^8) using extended Euclidean algorithm?
What I mean is how to represent a polynomial, e.g. f(x)=x^8+x^4+x^3+x+1
in C? How to represent the multiplication & division process of
polynomial?

Regards.

-- Tiza --
There are basically two ways:
1) Dense representation:
Use a vector of N+1 positions where N is the highest degree term.
In this case you would use a vector of 9 positions:
1 0 0 0 1 1 0 1 1
In a polynomial 5x^8 + 25x^4 + 567 you would have:
5 0 0 0 25 0 0 0 567
2) Sparse representation:
Use a linked list where each term is represented by a pair of
numbers exponent and constant term. This representation is better for
polynomials like 10x^200 + x + 5:
{ 200 10 } {1 1} { 0 5}

jacob
 
B

BRG

Tiza said:
Hi,

Anybody have an idea on how to start writing a C code for generating
the inverse of finite field GF(2^8) using extended Euclidean algorithm?
What I mean is how to represent a polynomial, e.g. f(x)=x^8+x^4+x^3+x+1
in C? How to represent the multiplication & division process of
polynomial?

Let the bits in a variable represent powers of x so that, for example,
x^8+x^4+x^3+x+1 is represented by bits *, 4, 3, 1 and 0. In this case
we obtain 0x11b as the represntation of this polynomial.

Now if we want to add or subtract two such values, all we have to do is
to xor them together so that, for example:

'x + 1' + 'x^2 + x' ==> 0x003 xor 0x006 = 0x005 ==> x^2 + 1.

And multiplication by x is a shift left by one position. Finally if bit
8 is set after an operation we have to subtract (xor) 0x11b into the
result (assuming that 0x11b is our modular polynomial). Division can
then be represented by repeated subtraction.

If we want to divide GF(2^8) element T by element B, we shift left the B
variable until its top bit matches the top bit of T. We then xor the
result into T so that the top bit of T becomes zero. Now we can repeat
this again for the new value of T until T has fewer bits than B. The
resulting T value is the remainder of the division, while the quotient
is the 1 bits representing the multiples of B that we take away from T
in this process

The US FIPS document for the AES encryption algorithm explains this in
more detail.

Brian Gladman
 
J

jacob navia

BRG said:
Let the bits in a variable represent powers of x so that, for example,
x^8+x^4+x^3+x+1 is represented by bits *, 4, 3, 1 and 0. In this case
we obtain 0x11b as the represntation of this polynomial.

Is it possible to represent

45x^8 + 1769x^3 + 7.976x + 3.14159

using that representation?

Maybe it is possible to restrain the domain of the
polynomial but that wasn't in the specs, at least in
the specs such as I understood them...

jacob
 
S

Stephen Sprunk

jacob navia said:
Is it possible to represent

45x^8 + 1769x^3 + 7.976x + 3.14159

using that representation?

That representation can only handle coeffecients of one or zero, which are
all that are possible in certain fields of mathematics. Outside those
fields, such representation is unusable.

S
 
J

Jack Klein

Hi,

Anybody have an idea on how to start writing a C code for generating
the inverse of finite field GF(2^8) using extended Euclidean algorithm?
What I mean is how to represent a polynomial, e.g. f(x)=x^8+x^4+x^3+x+1
in C? How to represent the multiplication & division process of
polynomial?

Regards.

-- Tiza --

Sure...

#include <stdio.h>

int main(void)

....at least that's how I'd start writing it.
 
T

Tiza Naziri

Hi Brian,

How do I measure the cycles needed for the written C code? Currently
I'm using Pentium 4 2GHz processor. Is there any special software for
it or it just can be measured using C?

Regards.

-- Tiza --
 
J

jacob navia

Tiza said:
Hi Brian,

How do I measure the cycles needed for the written C code? Currently
I'm using Pentium 4 2GHz processor. Is there any special software for
it or it just can be measured using C?

Regards.

-- Tiza --

The best way is to use the time stamp counter of
the processor.

The assembly instruction is called RDTSC. Some compilers
provide intrinsics to do that.
 
B

BRG

jacob said:
Is it possible to represent

45x^8 + 1769x^3 + 7.976x + 3.14159

using that representation?

Maybe it is possible to restrain the domain of the
polynomial but that wasn't in the specs, at least in
the specs such as I understood them...

He explicitly said GF(2^8) ...

Brian Gladman
 
B

BRG

Tiza said:
Hi Brian,

How do I measure the cycles needed for the written C code? Currently
I'm using Pentium 4 2GHz processor. Is there any special software for
it or it just can be measured using C?

As Jacob Navia has said, if you want to start from scratch then you need
to learn about the use of the RDTSC instruction and how to access this
in C.

In fact its quite hard to get good timing information but if you are
happy to learn how others time their code you might be interested in an
approach that Cristophe Devine and I use, which is provided in the
source code available at:

http://www.cr0.net:8040/code/crypto/aesbench/

This measures differential timing information over many runs and
averages the results whilst also watching to ensure that the standard
deviation in the timing information is not too large.

Brian Gladman
 
C

CBFalconer

jacob said:
The best way is to use the time stamp counter of
the processor.

The assembly instruction is called RDTSC. Some compilers
provide intrinsics to do that.

Which instruction doesn't exist on a '486, for example, not to
mention MACs etc. Use of such causes illegal instruction traps.
So you should always guard any such use with detection of the
actual machine type in use.

Besides which this assembly diversion is all OT for c.l.c. It is
bad enough to get so far OT, but then to recommend practices that
cause crashes is totally reprehensible IMO.
 
T

Tiza Naziri

Do you think that memory-reduction design of an encryption algorithm
could lead to the efficiency of software encryption implementation,
especially with limited memory devices such as smart card?
 
T

Tiza Naziri

Actually, this question relates to my actual question on how to code
the polynomial EEA. I intend to reduce the memory usage of S-box by
generating all of the values on-the-fly for every process in encryption
& decryption of AES.
 
R

Randy Howard

Which instruction doesn't exist on a '486, for example, not to
mention MACs etc. Use of such causes illegal instruction traps.
So you should always guard any such use with detection of the
actual machine type in use.

Besides which this assembly diversion is all OT for c.l.c. It is
bad enough to get so far OT, but then to recommend practices that
cause crashes is totally reprehensible IMO.

It also can give completely bogus results when executed, even on
an Intel processor that supports RDTSC. Specifically, in the
case of an SMP platform. The TSC counters are not sync'd between
processors, so if your program gets bounced, the results can
effectively be no better than random or just making something up.
 

Ask a Question

Want to reply to this thread or ask your own question?

You'll need to choose a username for the site, which only take a couple of moments. After that, you can post your question and our members will help you out.

Ask a Question

Members online

Forum statistics

Threads
473,744
Messages
2,569,484
Members
44,904
Latest member
HealthyVisionsCBDPrice

Latest Threads

Top