看了许多网上超多的关于S盒生成的文章，感觉没几个能说明白这个东西怎么算的，最后终于找到一篇文章：
这篇文章写的非常好，正是这篇文章才让我有完成这个作业的信心，他说清楚了，多项式的计算分为三种：
- 正常数学上的多项式运算，这里我们没用上
- 利用扩展欧几里得求解乘法逆元时，用的是模二运算
- 计算完逆元之后，验算这个数乘上他的逆元是否为单位元的时候，用的是模0x1B的运算
最终参考如下文章，终于写出来了S盒的生成：
代码
# include <stdio.h>
# include <stdint.h>
# define ROF8(x,n) (((x << n) | (x >> (8-n))) & 0xff)
uint32_t maxbit(uint32_t a){
if(a==0)return 0;
uint32_t value = 0;
for(uint32_t i=0;i<32;i++){
if(a&(1<<i)) value = i;
}
return value+1;
}
uint32_t mod2add( uint32_t a, uint32_t b){
return a^b;
}
uint32_t mod2sub( uint32_t a, uint32_t b){
return a^b;
}
uint32_t mod2mul( uint32_t a, uint32_t b){
uint32_t value = 0;
for(uint32_t i=0;i<32;i++){
if(a&(1<<i)){
value = mod2add(value,b<<i);
}
}
return value;
}
uint32_t mod2div( uint32_t a, uint32_t b, uint32_t * r){
uint32_t alen = maxbit(a);
uint32_t blen = maxbit(b);
if(alen<blen){
*r = a;
return 0;
}
else{
uint32_t c = alen - blen;
a = mod2sub(a, b<<c);
uint32_t s = mod2div(a, b, r)|(1<<c);
return s;
}
}
uint32_t exgcd( uint32_t a, uint32_t b, uint32_t * x, uint32_t *y){
if(b==0)
{
*x=1;*y=0;
return a;
}
uint32_t c = 0;
uint32_t s = mod2div(a,b,&c);
uint32_t r = exgcd(b,c,x,y);
uint32_t temp = *y;
*y= mod2sub(*x,mod2mul(s,*y));
*x= temp;
return r;
}
uint8_t affine(uint8_t a){
uint8_t tmp = 0;
uint8_t c = 0xf1;
for(int i = 0 ;i<8;i++){
uint8_t tmp2= 0;
for(int j = 0;j<8;j++){
tmp2 ^= ((a>>j)&1) & ((ROF8(c,i)>>j)&1);
}
tmp += tmp2<<i;
}
tmp = tmp ^ 0x63;
return tmp;
}
int main() {
uint32_t a=0;
uint32_t b=0;
for(int i = 0;i<256;i++){
exgcd(0x11b, i, &a,&b);
printf("0x%02X, ",affine(b));
if((i+1)%8==0){
printf("\n");
}
}
return 0;
}
运行结果：
➜ gcc sbox.c -o sbox
➜ ./sbox
0x63, 0x7C, 0x77, 0x7B, 0xF2, 0x6B, 0x6F, 0xC5,
0x30, 0x01, 0x67, 0x2B, 0xFE, 0xD7, 0xAB, 0x76,
0xCA, 0x82, 0xC9, 0x7D, 0xFA, 0x59, 0x47, 0xF0,
0xAD, 0xD4, 0xA2, 0xAF, 0x9C, 0xA4, 0x72, 0xC0,
0xB7, 0xFD, 0x93, 0x26, 0x36, 0x3F, 0xF7, 0xCC,
0x34, 0xA5, 0xE5, 0xF1, 0x71, 0xD8, 0x31, 0x15,
0x04, 0xC7, 0x23, 0xC3, 0x18, 0x96, 0x05, 0x9A,
0x07, 0x12, 0x80, 0xE2, 0xEB, 0x27, 0xB2, 0x75,
0x09, 0x83, 0x2C, 0x1A, 0x1B, 0x6E, 0x5A, 0xA0,
0x52, 0x3B, 0xD6, 0xB3, 0x29, 0xE3, 0x2F, 0x84,
0x53, 0xD1, 0x00, 0xED, 0x20, 0xFC, 0xB1, 0x5B,
0x6A, 0xCB, 0xBE, 0x39, 0x4A, 0x4C, 0x58, 0xCF,
0xD0, 0xEF, 0xAA, 0xFB, 0x43, 0x4D, 0x33, 0x85,
0x45, 0xF9, 0x02, 0x7F, 0x50, 0x3C, 0x9F, 0xA8,
0x51, 0xA3, 0x40, 0x8F, 0x92, 0x9D, 0x38, 0xF5,
0xBC, 0xB6, 0xDA, 0x21, 0x10, 0xFF, 0xF3, 0xD2,
0xCD, 0x0C, 0x13, 0xEC, 0x5F, 0x97, 0x44, 0x17,
0xC4, 0xA7, 0x7E, 0x3D, 0x64, 0x5D, 0x19, 0x73,
0x60, 0x81, 0x4F, 0xDC, 0x22, 0x2A, 0x90, 0x88,
0x46, 0xEE, 0xB8, 0x14, 0xDE, 0x5E, 0x0B, 0xDB,
0xE0, 0x32, 0x3A, 0x0A, 0x49, 0x06, 0x24, 0x5C,
0xC2, 0xD3, 0xAC, 0x62, 0x91, 0x95, 0xE4, 0x79,
0xE7, 0xC8, 0x37, 0x6D, 0x8D, 0xD5, 0x4E, 0xA9,
0x6C, 0x56, 0xF4, 0xEA, 0x65, 0x7A, 0xAE, 0x08,
0xBA, 0x78, 0x25, 0x2E, 0x1C, 0xA6, 0xB4, 0xC6,
0xE8, 0xDD, 0x74, 0x1F, 0x4B, 0xBD, 0x8B, 0x8A,
0x70, 0x3E, 0xB5, 0x66, 0x48, 0x03, 0xF6, 0x0E,
0x61, 0x35, 0x57, 0xB9, 0x86, 0xC1, 0x1D, 0x9E,
0xE1, 0xF8, 0x98, 0x11, 0x69, 0xD9, 0x8E, 0x94,
0x9B, 0x1E, 0x87, 0xE9, 0xCE, 0x55, 0x28, 0xDF,
0x8C, 0xA1, 0x89, 0x0D, 0xBF, 0xE6, 0x42, 0x68,
0x41, 0x99, 0x2D, 0x0F, 0xB0, 0x54, 0xBB, 0x16,
总结
这里需要我们重新定义加减乘除，在模二运算下，加减都是异或，乘除也就有了自己的定义。所以在上课的时候听得一脸懵逼，脑子里还是正常的加减乘除，而这里的运算只是名字上叫“加减乘除”而已。当定义了模二下的加减乘除这些运算，然后再用扩展欧几里得就可以求解对应的乘法逆元了。不过最后仿射变换的时候还是有点烧脑，正常应该异或上0xe3,不知道为啥我的代码异或上0x63才对？就是最高位的1个bit的问题，总之是打印出了s盒，真不容易，哭哭哭。