php从网页中导出数据,php数据库导出

AES算法中的S盒，求GF(2^8)上的乘法逆元怎么求啊？

一般根据定义 A^-1＝＝A^254，所以求A的254次方就可以了，254次又等于

128+64+32+16+8+4+2＝2*（ 2*（2*（2*（2*（2*（2+1）+1）+1）+1）+1）+1），所以只需要做7次平方和7次乘A。

当然在AES运算中，需要求出全部256个数的倒数，都用这种算法还是比较费的，可以用以下的方法

首先求3的全部255次幂，并做成两个查找表，即正向通过幂次查结果，和反向通过结果查幂次，这个过程可以，因为乘3是最简单的一个乘法操作 ，并且3的255次幂可以遍历整个GF(2,8)空间。

因为3^255=1,所以 当m+n=255时，3^m 和3^n互为倒数，即3^m的逆元就是3^n, n=255-m，那么求一个数A的逆元，可以先通过上面生成的反查表查出A对于3的幂次m，再用255－m=n，在正向表中查出3的n次幂，那个数就是A的逆元，这样求一个逆元就只是两次查表操作了。

相关问答

Q1: 用c语言编写扩展欧几里德算法用来求乘法逆元ab=1 mod(n) 要求我输入b，n，求出a。请编译运行通过，谢谢啦

#include stdio.h

int ExtendedEuclid( int f,int d ,int *result);

int main()

{

int n,b,z;

z = 0;

printf("输入两个数：\n");

scanf("%d%d",b,n);

if(ExtendedEuclid(n,b,z))

printf("%d和%d互素，乘法的逆元是：%d\n",b,n,z);

else

printf("%d和%d不互素，最大公约数为：%d\n",b,n,z);

return 0;

}

int ExtendedEuclid( int f,int d ,int *result)

{

int x1,x2,x3,y1,y2,y3,t1,t2,t3,q;

x1 = y2 = 1;

x2 = y1 = 0;

x3 = ( f=d )?f:d;

y3 = ( f=d )?d:f;

while( 1 )

{

if ( y3 == 0 )

{

*result = x3; /* 两个数不互素则result为两个数的最大公约数，此时返回值为零 */

return 0;

}

if ( y3 == 1 )

{

*result = y2; /* 两个数互素则resutl为其乘法逆元，此时返回值为1 */

return 1;

}

q = x3/y3;

t1 = x1 - q*y1;

t2 = x2 - q*y2;

t3 = x3 - q*y3;

x1 = y1;

x2 = y2;

x3 = y3;

y1 = t1;

y2 = t2;

y3 = t3;

}

}

/*输入两个数：

5 14

5和14互素，乘法的逆元是：3

*/

Q2: 用C语言编制的求模逆元的扩展欧几里德算法，只要能基本上实现这个功能就行

扩展欧几里德算法是用来在已知a, b求解一组x，y，使它们满足贝祖等式： ax+by = gcd(a, b) =d（解一定存在，根据数论中的相关定理）。扩展欧几里德常用在求解模线性方程及方程组中。

下面是一个使用C语言的实现：

intexGcd(int a,int b,int x,int y)

{

    if(b==0)    //当b==0时，得到解

    {

        x=1;y=0;

        return a;

    }

    intr=exGcd(b,a%b,x,y);//递归调用自身，求解

    intt=x;x=y;y=t-a/b*y;

    return r;

}

Q3: c语言，求一个数的逆的模n运算等于多少！

程序如下：

#include conio.h

#include stdio.h

int ExtEnclid(int d,int f)

{

int x1,x2,x3,y1,y2,y3,t1,t2,t3,k;

if(df) d=d+f-(d=f); //交换d和f使得df

x1=1,x2=0,x3=f;

y1=0,y2=1,y3=d;

while(1)

{

if(y3==0)

{

return 0; //没有逆元,gcd(d,f)=x3

}

if(y3==1)

{

return y2; //逆元为y2,gcd(d,f)=1

}

k=x3/y3;

t1=x1-k*y1, t2=x2-k*y2, t3=x3-k*y3;

x1=y1,x2=y2,x3=y3;

y1=t1,y2=t2,y3=t3;

}

}

int main()

{

int a, n, res;

printf("求 a^(-1) mod n 的值：\n");

printf("a = ");

scanf("%d", a);

printf("n = ");

scanf("%d", n);

res = ExtEnclid(a,n);

if (res == 0)

{

printf("Not Exist!\n");

getch();

return (0);

}

else if(res0)

{

res = res + n;

}

printf("a^(-1) mod n = %d\n", res);

getch();

return (0);

}

计算1/x mod n =x^(-1) mod n

就是求y，满足：

yx = 1 mod n

y是有限域F(n)上x的乘法逆元素

可用扩展的欧几里得算法求乘法逆元

扩展的欧几里德算法简单描述如下：

ExtendedEuclid(d,f)

1 （X1,X2,X3):=(1,0,f)

2 (Y1,Y2,Y3):=(0,1,d)

3 if (Y3=0) then return d'=null//无逆元

4 if (Y3=1) then return d'=Y2 //Y2为逆元

5 Q:=X3 div Y3

6 (T1,T2,T3):=(X1-Q*Y1,X2-Q*Y2,X3-Q*Y3)

7 （X1,X2,X3):=(Y1,Y2,Y3)

8 (Y1,Y2,Y3):=(T1,T2,T3)

9 goto 3

Q4: gf(2)中的乘法逆元怎么求解

用欧几里得扩展算法

在这里说很难给你讲明白，因为伪代码我记得不是很清晰了，你自己查下书吧，既然有讲AES算法，那书上不可能不提到欧几里得扩展算法的

不行百度一下也可以，我看了一下百度百科的：

欧几里德算法的扩展

扩展欧几里德算法不但能计算(a，b)的最大公约数，而且能计算a模b及b模a的乘法逆元，用C语言描述如下

但是是代码实现的，没有伪代码，还是自己找一下吧

这样可以么？

Q5: c语言乘法计算

严格来讲，你的代码是错误的，用int的b接收double型的a的计算结果，是不可以的，即使结果是整数。

结果当然也会出现误差。正确的应该是：

double a=10.3845;

double b;

b=10000*a;

printf("%lf",b);

补充：把上面 printf("%lf",b);改为printf("%.0lf",b); 就能使后面无小数。