For readability, olease view this post with a fixed-width font.
What should be a simple algorithm is giving me some major problems, and I'm
hoping that someone out there will either be able to show me an
implementation that works, or tell me that there's a mistake in the
description.
The operation is split into two sub-functions. The first is the inverse of
a number modulo 283 (using the extended Euclipean algorithm, EEA), which is
them followed by an affine transformation. I'm sure that my implementation
of the EEA is correct (two separate, web-based implementations agree with
the results I produce), so I assume that the affine transformation must be
the culprit. The only problem is, I've read and re-read the description and
even performed it by hand, and my results never match those of the test
data.
As previously stated, the first step is to calculate the inverse of an 8-bit
number modulo 283 (0x011B) using the EEA. This is then truncated to an
8-bit number as some results will exceed 255. The affine transformation
then alters the intermediate at a bit level in the following manner:
for n = 0 to 7
o[n] = i[n] xor i[(n+4) mod 8] xor i[(n+5) mod 8] xor i[(n+6) mod 8] xor
i[(n+7) mod 8] xor c[n]
next n
where o is the final output, i is intermediate result from the EEA, and c is
a constant of 99 (0x63). The subscripts refer to bit positions within each
byte where 0 is the least significant bit and 7 is the most.
The loop can also be expressed in matrix form (which is clearer):
o0 1 0 0 0 1 1 1 1 i0 c0
o1 1 1 0 0 0 1 1 1 i1 c1
o2 1 1 1 0 0 0 1 1 i2 c2
o3 1 1 1 1 0 0 0 1 i3 c3
o4 = 1 1 1 1 1 0 0 0 X i4 xor c4
o5 0 1 1 1 1 1 0 0 i5 c5
o6 0 0 1 1 1 1 1 0 i6 c6
o7 0 0 0 1 1 1 1 1 i7 c7
I've included some of the test data below (presented in hexadecimal).
Unfortunately, no intermediate values were provided and I'd prefer not to
mislead anyone with values that I've obtained. I have included my
implementation of the affine transformation at the end of this post (in C)
for anyone who wants to cast their eye over it.
Any help you can offer would be greatly appreciated!
Michael
Input: 00 01 02 04 08 10 20 40 80 ff
Output: 63 7c 77 f2 30 ca b7 09 cd 16
My implementation of the affine transformation - apologies for, well, you'll
see 
unsigned char affine( unsigned char cByte )
{
unsigned char cResult = 0;
// Calculate the value of each bit in result using selected bits of byte
for( unsigned char i = 0; i < 8; i++ )
{
unsigned char cTemp = 0;
// Extract bits at i, i+4, i+5, i+6 and i+7 and xor them all
cTemp ^= ( cByte & ( 1 << i )) ? 1 : 0;
cTemp ^= ( cByte & ( 1 << (( i + 4 ) & 7 ))) ? 1 : 0;
cTemp ^= ( cByte & ( 1 << (( i + 5 ) & 7 ))) ? 1 : 0;
cTemp ^= ( cByte & ( 1 << (( i + 6 ) & 7 ))) ? 1 : 0;
cTemp ^= ( cByte & ( 1 << (( i + 7 ) & 7 ))) ? 1 : 0;
// Place the bit at current position in result
cResult |= ( cTemp << i );
}
// Apply the constant to result and return
return( cResult ^ 0x63 );
}
