G(2^8)有限域上的运算
-----------------------------------------------------
本原多项式P(x) = x8+x4+x3+x2+1 [1 0001 1101]
定义 P(x) = 0 则 x8 = x4+x3+x2+1 [0 0001 1101]
-----------------------------------------------------
区间[0,255]可以表示成各种多项式。例如：
0 = 00000000 = 0
1 = 00000001 = x0 = 1
2 = 00000010 = x2
129 = 10000001 = x7+x
-----------------------------------------------------
加法：按位异或
-----------------------------------------------------
乘法：
3*7 = (x+1)*(x2+x+1)
= x*x2+x*x+x+x2+x+1
= x3+1
= 00001001
= 9
129*5 = (x7+1)*(x2+1)
= x9+x7+x2+1
= x5+x4+x3+x1 + x7+x2+1 ( 因为: x9 = x5+x4+x3+x1 )
= x7+x5+x4+x3+x2+x1+1
= 10111111
= 191
------------------------------------------------------
x的指数运算：可以得出x^i(i=0,1,2……)，用于乘法运算。
x0 = 00000001 = 1
x1 = 00000010 = x1
x2 = 00000100 = x2
x3 = 00001000 = x3
x4 = 00010000 = x4
x5 = 00100000 = x5
x6 = 01000000 = x6
x7 = 10000000 = x7
x8 = 00011101 = x4+x3+x2+1
x9 = 00111010 = x1*x8 = x1*(x4+x3+x2+1) = x5+x4+x3+x1
x10 = 01110100 = x1*x9 = x1*(x5+x4+x3+x1) = x6+x5+x4+x2
x11 = 11101000
x12 = 11001101 = x1*(x7+x6+x5+x3) = x8+x7+x6+x4
= x4+x3+x2+1+x7+x6+x4
= x7+x6+x3+x2+1
x13 = 10000111
……
x8 = x4+x3+x2+1 = 29 = 00111010
x12= x7+x6+x3+x2+1 = 205 = 11001101
则： 29*205=x20
29/205 = x8/x12 = x251
205/29 = x12/x8 = x4
/*-----------------------------------------------------
用有限域实现加解密
本原多项式: 0x11B( x8+x4+x3+x+1 )
明文: C[i]
密文: M[i]
DEF : 加密乘法因子 或 解密被除数. 注：DEF不能为0
加密: M[i] = C[i] * DEF
解密: C[i] = M[i] / DEF
*/
int XN[256], NX[256];
void genlt()
{
int i, j;
XN[0] = 1;
for (i = 1; i < 256; i++){
j = ( XN[i-1] << 1) ^ XN[i-1];
if ((j & 0x100) != 0) j ^= 0x11B;
XN[i] = j;
}
NX[0] = NX[1] = 0;
for (i = 1; i < 255; i++) NX[XN[i]] = i;
}
int mul( int a, int b )
{
if( a==0 || b==0 ) return 0;
else return XN[ (NX[a]+NX[b])%255 ];
}
int div( int a, int b )
{
int x;
if( a==0 ) return 0;
if( b==0 ) return -1;
x = NX[a]-NX[b] < 0 ? NX[a]-NX[b]+255 : NX[a]-NX[b];
return XN[x];
}
void main()
{
genlt();
int i;
unsigned char DEF = 2;
unsigned char C[256], M[256], O[256];
sprintf( (char*)C, "zhongguo shi shufa de haiyang !" );
printf( "%s\n", C );
for( i=0; i<256; i++ ){
M[i] = mul( DEF, C[i] );
}
printf( "%s\n", M );
for( i=0; i<256; i++ ){
O[i] = div( M[i], DEF );
}
printf( "%s\n", O );
}