《网络空间安全技术实践教程》课件7.1课件

7.1大整数运算实验实验原理：本此实验中将使用无符号字符(unsignedchar)的数组表示大整数，用结构体实现。typedefstructBigint

//定义结构体用于表示大整数的无符号字符数组{unsignedcharnum[SIZE];}Bigint;typedefstructBigint2

//大整数乘法可能需要的数组长度是原数组的两倍{ unsignedcharnum[2*SIZE];}Bigint2;网络空间安全实践教程17.1大整数运算实验实验原理：大整数表示：无符号字符范围是0~255，即用256进制表示大整数。假设数组a里元素从低位到高位分别为a.num[0],a.num[1],……,a.num[SIZE-1]，则a表示的数为a.num[0]*1+a.num[1]*256+a.num[SIZE-1]*256SIZE-1例如数组a为a.num[0]=1,a.num[1]=0,a.num[2]=2,a.num[s]=0(s=3,4,……)，则a表示的数为1*1+0*256+2*2562=131073#defineSIZE17

//SIZE是数组长度，考虑到加法可能会溢出，其能表示的最大整数的bit数是8*(SIZE-1)，SIZE可自由选取。例如SIZE取成17，则能表示的最大整数的bit数是128bit，即能表示[0,2128-1]范围内的整数。网络空间安全实践教程27.1大整数运算实验实验原理：大整数加法：加法是256进制加法，即从低位到高位逐字节相加，若有进位则加到前一字节中。例如两个数a与b如下所述：a.num[0]=100，a.num[1]=234，其余位置均为0b.num[0]=200,b.num[1]=50，其余位置均为0a+b的结果若用c表示，则c.num[0]=(100+200)mod256=44，有进位1c.num[1]=(234+50+1)mod256=29，有进位1c.num[2]=1，其余位置为0网络空间安全实践教程37.1大整数运算实验实验原理：大整数减法：是256进制减法，即从低位到高位逐字节相减，若结果小于0则向前一字节进行借位。例如两个数a与b如下所述：a.num[0]=100，a.num[1]=234，其余位置均为0b.num[0]=200,b.num[1]=50，其余位置均为0a-b的结果若用c表示，则c.num[0]=(100-200)mod256=156，有借位1c.num[1]=(234-50-1)mod256=183，其余位置为0网络空间安全实践教程47.1大整数运算实验实验原理：大整数乘法：先定义一个Bigint2类型的数组，再使用二重循环往此数组对应的位置上加上两个字节的乘积，若有进位则记下。可参考如下代码：网络空间安全实践教程57.1大整数运算实验

Bigint2Mul(Biginta,Bigintb)//大整数乘法a*b{ Bigint2c={0}; unsignedshorttemp;//定义临时积 unsignedcharcarry;//定义进位 for(inti=0;i<SIZE;i++) { carry=0; for(intj=0;j<SIZE;j++) { temp=a.num[i]*b.num[j]+c.num[i+j]+carry; c.num[i+j]=temp&0x00ff;//a.num[i]*b.num[j]，加到c.num[i+j]上并记录结果 carry=(temp>>8)&0xff;//记录进位 } } c.num[2*SIZE-1]=carry; returnc;}网络空间安全实践教程67.1大整数运算实验实验原理：大整数求模与除法：求模与除法的思路类似，都是基于竖式除法。第一步先算出商的数组长度m；第二步将除数左移m个字节，作为临时除数，不断地用此临时除数去减被除数，每减一次商往上加一次，直到被除数比结果小，得到商的最高字节；第三步再将除数左移m-1个字节，作为新的临时除数，同样利用减法得到商的次高字节；依次做下去，最后得到商与求模的最终结果，可参考如下代码：网络空间安全实践教程77.1大整数运算实验

BigintMod(Biginta,Bigintb)//大整数求模amodb{

if(Compare(a,b)<0) returna; else { BigintB={0}; intlen=Length(a)-Length(b); while(len>=0) { B=ByteMoveLeft(b,len);//除数b左移len个字节，作为临时除数B while(Compare(a,B)>=0) a=Sub(a,B);//当a>=B时，不断减去B len--; } returna;//减到最后，a就是结果 }}网络空间安全实践教程87.1大整数运算实验

BigintDiv(Biginta,Bigintb)//大整数除法a/b{ BigintB={0}; Bigintc={0}; intlen=Length(a)-Length(b);//商的数组长度 while(len>=0) { B=ByteMoveLeft(b,len);//除数b左移len个字节，作为临时除数B while(Compare(a,B)>=0) { a=Sub(a,B);//当a>=B时，不断减去B c.num[len]++;//商不断自增 } len--; } returnc;}网络空间安全实践教程97.1大整数运算实验实验原理：在此把本节中可能用到的函数全列出来。

BigintInit(unsignedchara[],intlength);//初始化voidCopy(Bigint&a,Bigintb);//拷贝voidPrint(Biginta);//打印输出intLength(Biginta);//计算数组长度intLength(Bigint2a);intCompare(Biginta,Bigintb);//比较大小：a>b,a=b,a<b分别输出1,0,-1intCompare(Bigint2a,Bigint2b);BigintByteMoveLeft(Biginta,intloop);//左移loop个字节Bigint2ByteMoveLeft(Bigint2a,intloop);voidBitMoveRight(Bigint&a);//右移一个比特Bigint2Extend(Biginta);//扩充数组BigintNarrow(Bigint2a);//截断数组网络空间安全实践教程107.1大整数运算实验

BigintAdd(Biginta,Bigintb);//加法:输入a,b,返回a+bBigintSub(Biginta,Bigintb);//减法:输入a>b,返回a-bBigint2Sub(Bigint2a,Bigint2b);//减法:输入a>b,返回a-bBigint2Mul(Biginta,Bigintb);//乘法:输入a,b,返回a*bBigintDiv(Biginta,Bigintb);//除法:输入a,b,返回a/bBigintMod(Biginta,Bigintb);//求余:输入a,b,返回amodbBigint2Mod(Bigint2a,Bigint2b);//求余:输入a,b,返回amodbBigintAddMod(Biginta,Bigintb,Bigintn);//模加:计算a+bmodnBigintSubMod(Biginta,Bigintb,Bigintn);//模减:计算a-bmodn(要求a>=b)BigintSub2Mod(Biginta,Bigintb,Bigintn);//模减:计算a-bmodnBigintMulMod(Biginta,Bigintb,Bigintn);//模乘:计算a*bmodnBigintPowMod(Biginta,Bigintb,Bigintn);//模幂:计算abmodn网络空间安全实践教程117.1大整数运算实验实验原理：大整数模逆：给定模数N及与N互素的a，a模N的逆指的是区间(0,N)中满足xa=1(modn)的数x。求大整数的模逆需要用到扩展欧几里得算法：即输入正整数a，b，输出x，y满足x*a+y*b=gcd(a,b)。在扩展欧几里得算法中，令b=N，由于N与a互素，则输出的x，y满足x*a+y*N=gcd(a,N)=1，则x满足xa=1(modn)，最后取x=xmodN就保证x在(0,N)中，即x就是a模N的逆。可参考如下代码：网络空间安全实践教程127.1大整数运算实验

boolInverse(Biginte,BigintN,Bigint&d)//大整数模逆：求e模N的逆，结果存入d{ Bigintr1={0};Bigintr2={0}; Copy(r1,e);Copy(r2,N);//设初始值r1=e,r2=N Bigints1={1};Bigints2={0};//设系数初始值s1=1,s2=0 Bigints={0};Bigintr={0}; while(1) { if(Length(r1)==0)//若r1=0,求模逆失败 return0; if(Length(r1)==1&&r1.num[0]==1) {Copy(d,s1);return1;}//若r1=1,求模逆成功，将结果s1存入d q=Div(r1,r2);//商q=r1/r2 s=Sub2Mod(s1,MulMod(q,s2,N),N);//s=s1-q*s2,为了结果非负,使用模N运算 r=Sub(r1,Narrow(Mul(q,r2)));//r=r1-q*r2 Copy(r1,r2);Copy(s1,s2); Copy(s2,s);Copy(r2,r); }}网络空间安全实践教程137.1大整数运算实验实验原理：大整数模幂：模幂即计算abmodn的结果，普通的模幂算法需要计算b-1次模乘，当b很大时，运算效率比较低。幸运的是，模平方算法可以将模乘的次数降至2log2b次左右，是很大的改进。描述如下：先将b用二进制表示成bkbk-1…b0，即，则我们得到

所以只需要将满足bi=1的i对应的相乘并模n就可以，而从a出发不断地做模n平方就能得到所有。网络空间安全实践教程147.1大整数运算实验

BigintPowMod(Biginta,Bigintb,Bigintn)//模幂：计算abmodn{ Bigintc={1}; Biginton