i want to make a dongle like protection with 8 bit CPU (which also known as smart card CPUs), with 8K ROM and 256 bytes RAM.

it gonna encrypt a file with a key. the cipher kind come to my mind is block cipher. i've read the new AES candidate paper. and those who suitable with that spec are:

Crypton, DEAL, DFC, Magenta, Mars, RC6, Rijndael, SAFER+, Serpent, and Twofish.

could anyone tell me which one of these is the best to implement and for security ?

Those were the ones submitted as candidates; Serpent, Twofish, Rijndael, RC6, and MARS amde it to the final round. Some pretty hefty attacks were levied against RC6 and MARS. Rijndael won, and since it's byte-based, it works well on 8-bit processors. It's very easy to understand; I'd suggest you use that one.

You should be aware of attacks against smartcard chips, like power analysis, and fault analysis. How is the system going to be used?

the system is dongle like, it transfer an encrypted file purchased, and there's timestamp too, if needed. about power/some else analysis, i'm not look at those thing yet.

yeah, after search and read some, the winner is Rijndael, and i read from somewhere that it has 8051 implementation, which is an 8 bit cheap microprosesor. but i couldn't find it. Could u tell me where's the good resource for this thing, Mike ?

You can write the author at vincent.rijmen@esat.kuleuven.ac.be or post on sci.crypt.

thanks... i waiting for reply now.
and how about the security problem, Mike ?
there's several cryptanalysis out there about rijndael. do i have to take care of it ?

Right now (as far as I know) the paper I co-wrote as part of the extended Twofish team is still the best attack against rijndael. It does not come close to breaking it.

now on reading rijndael algo...
the preliminary math is finite field GF(2^8). but, sadly, i don't know much about it. could you tell me where's the good resource to learn this thing ?

and meanwhile, i'll be off for a week, just for a moment, while still reading rijndael aes proposal.

GF(2^8) is a field; that is, you can do addition & multiplication, and every element except zero has a multiplicative inverse. That is, for every element x except zero, there's an element y such that x*y=1.

GF(p^n) behaves like polynomials of order (n-1) with integer coefficients mod p. So in this case, addition acts like XOR. The polynomials are also taken mod a "primitive polynomial". I won't give the defenition here; if you're interested, I'm sure you can find it somewhere on the web.

So for example, say our primitive polynomial is x^4-x-1.

Starting with 1 and multiplying by x, we get

1 = 1
x = 2
x^2 = 4
x^3 = 8

and then we get to x^4. We take x^4 modulo x^4-x-1 and get x+1. Then we multiply by x again until we get an x^4 term:

x^4 = x+1 = 3
x^5 = x^2+x = 6
x^6 = x^3+x^2 = 12

and then we get to x^4+x^3. We take x^4 modulo x^4-x-1 and get x+1. Then we multiply by x again until we get an x^4 term:

x^7 = x^3+x+1 = 11

and then we get to x^4+x^2+x. We take x^4 modulo x^4-x-1 and get x+1. Then we multiply by x again until we get an x^4 term:

x^8 = x^2+2x+1 = x^2+1 mod 2 = 5
x^9 = x^3+x = 10

and then we get to x^4+x^2. We take x^4 modulo x^4-x-1 and get x+1. Then we multiply by x again until we get an x^4 term:

x^10 = x^2+x+1 = 7
x^11 = x^3+x^2+x = 14

and then we get to x^4+x^3+x^2. We take x^4 modulo x^4-x-1 and get x+1. Then we multiply by x again until we get an x^4 term:

x^12 = x^3+x^2+x+1 = 15

and then we get to x^4+x^3+x^2+x. We take x^4 modulo x^4-x-1 and get x+1. Then we multiply by x again until we get an x^4 term:

x^13 = x^3+x^2+2x+1 = x^3+x^2+1 mod 2 = 13

and then we get to x^4+x^3+x. We take x^4 modulo x^4-x-1 and get x+1. Then we multiply by x again until we get an x^4 term:

x^14 = x^3+2x+1 = x^3+1 mod 2 = 9

and then we get to x^4+x. We take x^4 modulo x^4-x-1 and get x+1. Then we multiply by x again until we get an x^4 term:

x^15 = 2x+1 = 1

which is where we started.

We can do this whole thing easier by shifting left one bit and if the carry bit (bit 4 in this case) is set, XOR with 3. Notice that we got every number between 1 and 15 and that x^15 = 1.

So, for example, x^13*x^2 = 1 = 13*4. So 13 and 4 are inverses in GF(16).

Hope that quick review helps.

welcome back again.
Hi, Mike, thanks for that review, if i'm not wrong, you're trying to figure out how primitive polynomial in GF(2^8) works. that's good, but i had it mine now. hmm... is that true that multiplicative inverses can be calculated with bit shift in 4 bit form ? is it not in 8 bit form ?

i've read whole proposal, but can't take it at once. and well, the real source code for 8 bit processor is in C language, and implemented by C51 software simulator. but, i think it won't help me to learn the algo more than assembly language in 8051. is there anyone has implement it in assembly 51?

I was illustrating gf(16) modulo x^4-x-1. You would be using gf(2^8) modulo something else (doesn't really matter what, since they're all related by linear transformations).

Rijndael goes like this

key xor
sbox
shift
mix

repeated 16x and one more key xor.

Sbox replaces every byte x by s(x). Shift moves bytes around on a row. Mix is a matrix multiplication in GF(2^8).

author said that he choose a polynom such that it has inverse form. umm... how can one determine such polynom has an inverse, and how to do the calculation ?

The polynomial has to be primitive in the field. For example, with 5 bits, taking the polynomials modulo x+1 doesn't give rise to a field--2 isn't a generator. There's no number y such that 7=2^y, for example.

I don't know offhand what the algorithm is to find primitive polynomials, but there are tables of them for small integers.

As far as I know, they just chose the first one they found for 8 bits out of a table that used some standard ordering.

All of this is irrelevant for implementation issues. It's only useful if you're going to be cryptanalyzing it. (By all means, do!)

The C reference implementation is very readable. I recommend that you look it over.

Did you know about aes.nist.gov that has everything anyone has ever written about AES?

i've read the C source code, and i've download all paper about rijndael from nist. alas, as far as i know, the C51 code is little diff from conventional C code, but i don't see that in their C source code.

hmm.. so there's a table. and yep! i am willing to cryptanalyze it! but i'm lake understanding in this field, so that i'm asking in this forum.

honestly, i still don't fully understood your exp about primitive polynom, Mike. but, the means of all is there's an inverse form. by now i'm trying to explore this. is the heart of this polynom is somekind of modulo ?

First go find a good intro to number theory that talks about finite fields. These are also known as Galois (pronounced "gal-wah"fields, thus the GF(.) notation.

A field has commutatitive multiplication and addition defined, and every element except zero has a multiplicative inverse. I think that's what they were talking about when they mentioned inverses. The s-box is written concisely as inv(x) XOR 99h, where inv(0)=0.

The key XOR step is just addition in GF(256)
The sbox is inverse followed by addition
the shift is just moving bytes around
the mix is matrix multiplication

You already know all these concepts except how they work in gf(256), so go find a tutorial on it.

If things look a little different in different implementations, it's because they've implemented different optimizations. There's a whole section on them in the NIST proposal.

umm... could you recommend me one of them, i mean good intro to finite field.

If you're really serious about understanding it, I'd recommend a book:

Neil Koblitz, A Course in Number Theory and Cryptography, Graduate Texts in Math. No. 114, Springer-Verlag, New York, 1987. Second edition, 1994.

If you're just trying to implement it, all you need to know is how to multiply and add.

Since something like 13*a can be written

(8 + 4 + 1)*a = 8*a + 4*a + 1*a,

you only need to know how to multiply by powers of two and how to add. Adding is just xor. a+b -> a XOR b

Multiplying by two is left shift followed by an xor if the carry bit is set. In the case of Rijndael, they use the primitive polynomial

x^8+x^4+x^3+x+1, or 11Bh

So if you left shift your number and it's bigger than 255, you xor 0x11B with it. For example (all numbers in hex):

2 * 49 = (49<<1) = 92

2 * C3 = (C3<<1) = 186 -- bigger than 255, so xor with 11B
186 XOR 11B = 9D, so 2*C3 = 9D

3 * C3 = 2*C3 XOR 1*C3 = 9D XOR C3 = 5E

Some reference code I've seen uses log tables and power tables. These work exactly the way you'd expect them to.

a*b = 2^( log_2(a) + log_2(b) )

Since each number in GF(2^n) is also a power of 2, you can calculate a table of logs and powers to speed things up.

Good luck!

Thanks, Mike. Trying to seek that book now, and i think i've to end this useless question right now and begin to dive into deeper part.