《網絡空間安全技術實踐教程》課件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進制加法，即從低位到高位逐字節(jié)相加，若有進位則加到前一字節(jié)中。例如兩個數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進制減法，即從低位到高位逐字節(jié)相減，若結果小于0則向前一字節(jié)進行借位。例如兩個數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類型的數組，再使用二重循環(huán)往此數組對應的位置上加上兩個字節(jié)的乘積，若有進位則記下。可參考如下代碼：網絡空間安全實踐教程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個字節(jié)，作為臨時除數，不斷地用此臨時除數去減被除數，每減一次商往上加一次，直到被除數比結果小，得到商的最高字節(jié)；第三步再將除數左移m-1個字節(jié)，作為新的臨時除數，同樣利用減法得到商的次高字節(jié)；依次做下去，最后得到商與求模的最終結果，可參考如下代碼：網絡空間安全實踐教程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個字節(jié)，作為臨時除數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個字節(jié)，作為臨時除數B while(Compare(a,B)>=0) { a=Sub(a,B);//當a>=B時，不斷減去B c.num[len]++;//商不斷自增 } len--; } returnc;}網絡空間安全實踐教程97.1大整數運算實驗實驗原理：在此把本節(jié)中可能用到的函數全列出來。

BigintInit(unsignedchara[],intlength);//初始化voidCopy(Bigint&a,Bigintb);//拷貝voidPrint(Biginta);//打印輸出intLength(Biginta);//計算數組長度intLength(Bigint2a);intCompare(Biginta,Bigintb);//比較大?。篴>b,a=b,a<b分別輸出1,0,-1intCompare(Bigint2a,Bigint2b);BigintByteMoveLeft(Biginta,intloop);//左移loop個字節(jié)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的逆指的是區(qū)間(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的逆?？蓞⒖既缦麓a：網絡空間安全實踐教程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出發(fā)不斷地做模n平方就能得到所有。網絡空間安全實踐教程147.1大整數運算實驗

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