应用密码学第2讲分组密码小节.pptVIP

分组密码小结 主要内容 欧几里德算法 求最大公约数 求模n的逆元 欧几里得算法（辗转相除法） 引理1 记gcd(a,b)是非负整数a和b的最大公因子,则gcd(a,b)=1等价于存在整数x,y,使得 ax+by=1 其中的x和y可由辗转相除法求出。 辗转相除法 引理2 (带余除法) 设a是整数, b是自然数,则存在整数q和非负整数r,使得a=bq+r，且 0=rb,并记amodb=r. 引理3 设a、b、r为不全为零的整数，且a=bq+r，则gcd(a,b)=gcd(b,r). 证明：设d= gcd(a,b)，由于d| a=bq+r,且d|b，则一定有d|r，则d| gcd(b,r).下证 d=gcd(b,r).由于gcd(a/d,b/d)=1,一定有 gcd(r/d,b/d)=1，故d=gcd(b,r)。证毕。 辗转相除法：----计算gcd(a,b) Step1 A?a;B?b Step2 计算带余除法，求出满足 A=qB+r和0=rB的 q和r. Step3 当r=0时,输出B=gcd(a,b); 当r0时,执行A?B;B?r后返回执行 Step2. 例1 计算gcd(63,100) 解 63 = 0×100 + 63, 100 = 1×63 + 37, 63 = 1×37 + 26 37 = 1×26 + 11, 26 = 2×11 + 4, 11 = 2×4 + 3, 4 =1×3 +1, 3 = 3×1 + 0 故gcd(63,100)=1. 系数的计算 倒推进行(将余数代入): 1 = 4 - 1×3 = 4 - 1×(11 -2×4) = -1×11+(1+2) ×4 = -1×11 + 3×4 = -1×11 + 3×(26 –2×11) = -7×11 + 3×26 = -7×(37 –26) + 3×26 = -7×37+ (7+3) ×26 = -7×37 +10×26 = -7×37+10×( 63-37) = 10×63 -17×37 = 10×63 -17×(100-63) = -17×100 + 27×63 输出使得ax+by=gcd(a,b)的gcd(a,b)和x,y的推理过程. 记a0=a,a1=b, 则求ax+by=gcd(a,b)的过程可写为：　 　　　　　　　　即 欧几里得算法：----计算gcd(a,b)和使ax+by=gcd(a,b)成立的x,y. 欧几里得算法：----计算gcd(a(x),b(x))和使z(x)a(x)+y(x)b(x)=gcd(a(x),b(x))成立的z(x),y(x). 辗转相除法的C语言算法 int inverse(a) int a; { register int n1,n2,q,r,b1,b2,t; if(!a) b2 = 0; else { n1 = n; n2 = a; b2 = 1; b1 = 0; do { r = (n1%n2); q = (n1-r)/n2; if(!r) { if(b20) b2 = n+b2; } else { n1=n2 ; n2 = r; t=b2; b2=b1 -q*b2; b1=t; } } while (r); } return (b2 ); } 例子：modb(x)中的逆a(x)=x7+x5+x4+x2+x, b(x)=x8+x4+x3+x+1?100011011,求z(x)满足 z(x)a(x)+y(x)b(x)=1. 解：step1:A(x)=a(x),B(x)=b(x),s(x)=1,z(x)=0, t(x)=0,y(x)=1; step2:A(x)=0*B(x)+r(x),r(x)=a(x); 由于r(x)!=0，则A(x)=B(x),B(x)=r(x); w(x)=z(x)=0;z(x)=s(x)-q(x)z(x)=s(x)=1;s(x)=w(x)=0 执行step2 (100011011)=x*+r 故q(x)=x;r(x)= A(x)= ;B(x)=r(