AES中构造s盒中的乘法逆元的c语言实现

#include<stdio.h>
#include<string.h>

//二进制字符串转化成十进制
int bits_dec(char binary[])
{
    int len=strlen(binary);
    int i;
    int sum=0,value=1;
    for (i=len-1;i>=0;i--)
    {
        if(binary[i]=='1')
            sum+=value;
        value*=2;
    }
    return sum;
}
//计算一个十进制数的二进制表示时的位数有多大
//直接计算右移了多少位就可
int numb_bits(int v)
{
    int count=0;
    while(v>0)
    {
        v=v>>1;
        count++;
    }
    return count;
}
//输出一个十进制数的二进制表示
void printf_bit(int a)
{
    int n=numb_bits(a);
    int i;
    for(i=n-1;i>=0;i--)
    {
        if(1<<i & a)
            printf("1");
        else
            printf("0");
    }
}
//多项式除法
int polydivide(int a,int b,int *remainder )
{
    int tmp;
    int c=numb_bits(a)-numb_bits(b);
    int value=0;
    while(c>=0)
    {
        value=(1<<c) | value; //计算商，这时计算的c值就是每一个是1的位置，直接与1相与，就可以将其设置为1
        tmp=b;//将被除数向左移c位再与a相与，并赋给a
        tmp=tmp<<c;
        a=a^tmp;
        c=numb_bits(a)-numb_bits(b);
    }
    *remainder=a;
    return value;
    
}
//多项式乘法，算法就是书上96的算法
int polyMulti(int a,int b)
{
    int value=a;
    int result=a;
    int r;
    if(a==0 || b==0)
        return 0;
    r=b%2;
    b=b/2;
    if(!r)  //判断最后一位是0还是1,是0的话result就等于0
        result=0;
    while(b)
    {
        r=b%2;
        b=b/2;
        if(value>>7) //b7为1,就要与00011011相与
            value=(value<<1) & 0xff ^27;
        else
            value=(value<<1) & 0xff;
        if(r) //位为1的结果就参加异或运算
            result=result ^ value;
    } 
    
    return result;
}
//扩展的欧几里德算法
int Ext_Euclid(int a,int b)
{
    int tmp;
    if(a<b)
    {
        tmp=a;
        a=b;
        b=tmp;
    }
    int x0,y0,x1,y1;//初始化条件
    x0=1;
    y0=0;
    x1=0;
    y1=1;
    int tmp1,tmp2;
    int r1,r2,q1;
    r1=a;
    r2=b;
    int i=1;
    //下面直接用扩展欧几里德算法来做
    while(r2)
    {
        tmp1=r2;
        q1=polydivide(r1,r2,&r2);//r1对r2进行多项式除法，商存在q1,余数存在r2
        r1=tmp1;//这步比较重要，就是r1要变成上一次除法的被除数
        printf("q%d:\t",i);
        printf_bit(q1);
        printf("\tr%d:\t",i);
        printf_bit(r2);
        tmp1=x1;
        tmp2=y1;
        x1=x0 ^ polyMulti(q1,x1);  //计算v,w;每一个v(x)*f(x)+w(x)*g(x)=1成立
        y1=y0 ^ polyMulti(q1,y1);
        printf("\tv%d:\t",i);
        printf_bit(x1);
        printf("\tw%d:\t",i);
        printf_bit(y1);
        printf("\n\n");
        x0=tmp1;
        y0=tmp2;
        i++;
    }
    return y0;
}
int  main()
{
    char c1[64],c2[64];
    printf("请输入两个二进串（中间以空格隔开）:\n");
    scanf("%s%s",c1,c2);
    printf_bit(Ext_Euclid(bits_dec(c1),bits_dec(c2)));
    printf("\n");
}
           

测试结果：