【文章內(nèi)容簡介】 鑰長度的關(guān)系如表1所列）。每一輪都需要一個與輸入分組具有相同長度的擴展密鑰Expandedkey(i)的參與。由于外部輸入的加密密鑰K長度有限,所以在算法中要用一個密鑰擴展程序(Keyexpansion)把外部密鑰K擴展成更長的比特串,以生成各輪的加密和解密密鑰。應(yīng)用：主要用于基于私鑰數(shù)據(jù)加密算法的各種信息安全技術(shù)和安全產(chǎn)品中：無線網(wǎng)絡(luò)應(yīng)用信息安全領(lǐng)域AES軟件應(yīng)用虛擬專用網(wǎng)、同步光網(wǎng)絡(luò)、遠程訪問服務(wù)器，高速路由器、移動通信、衛(wèi)星通信、電子金融業(yè)務(wù)等。 4 公開加密算法RSA本章主要介紹非對稱加密算法RSA的基本原理以及其算法結(jié)構(gòu)，并舉出RSA算法的一個具體實例進行分析，最后討論一下RSA的探索——大整數(shù)運算。 RSA的簡介RSA算法是第一個能同時用于加密和數(shù)字簽名的算法，也易于理解和操作。RSA是被研究得最廣泛的公鑰算法，從提出到現(xiàn)在已近二十年，經(jīng)歷了各種攻擊的考驗，逐漸為人們接受，普遍認為是目前最優(yōu)秀的公鑰方案之一。RSA的安全性依賴于大數(shù)的因子分解，但并沒有從理論上證明破譯RSA的難度與大數(shù)分解難度等價。即RSA的重大缺陷是無法從理論上把握它的保密性能如何，而且密碼學(xué)界多數(shù)人士傾向于因子分解不是NPC問題。RSA的缺點主要有：A)產(chǎn)生密鑰很麻煩，受到素數(shù)產(chǎn)生技術(shù)的限制，因而難以做到一次一密。B)分組長度太大，為保證安全性，n 至少也要 600bits以上，使運算代價很高，尤其是速度較慢，較對稱密碼算法慢幾個數(shù)量級；且隨著大數(shù)分解技術(shù)的發(fā)展，這個長度還在增加，不利于數(shù)據(jù)格式的標準化。目前，SET(Secure Electronic Transaction)協(xié)議中要求CA采用2048bits長的密鑰，其他實體使用1024比特的密鑰。C)RSA密鑰長度隨著保密級別提高，增加很快。下表列出了對同一安全級別所對應(yīng)的密鑰長度。這種算法1978年就出現(xiàn)了，它是第一個既能用于數(shù)據(jù)加密也能用于數(shù)字簽名的算法。它易于理解和操作，也很流行。算法的名字以發(fā)明者的名字命名：Ron Rivest, AdiShamir 和Leonard Adleman。早在1973年，英國國家通信總局的數(shù)學(xué)家Clifford Cocks就發(fā)現(xiàn)了類似的算法。但是他的發(fā)現(xiàn)被列為絕密，直到1998年才公諸于世。 RSA算法的結(jié)構(gòu)RSA加密算法使用了兩個非常大的素數(shù)來產(chǎn)生公鑰和私鑰。即使從一個公鑰中通過因數(shù)分解可以得到私鑰，但這個運算所包含的 計算 量是非常巨大的，以至于在現(xiàn)實上是不可行的。加密算法本身也是很慢的，這使得使用rsa算法加密大量的數(shù)據(jù)變的有些不可行。這就使得一些現(xiàn)實中加密算法都基于rsa加密算法。pgp算法(以及大多數(shù)基于rsa算法的加密方法)使用公鑰來加密一個對稱加密算法的密鑰，然后再利用一個快速的對稱加密算法來加密數(shù)據(jù)。（1）RSA算法原理RSA算法是基于數(shù)論中的同余理論。如果用m代表明文，c代表密文，E(m)代表加密運算，D（c）代表解密運算，x=y(mode z)表示x和y模z同余，則加密和解密算法簡單表示如下：加密算法 c=E(m)=me(mod n)解密算法 m=D(c)=cd(mod n)其中n和密鑰e是公開的，而密鑰d是保密的。下面討論密鑰的求取：①選取兩個隨機大素數(shù)p和q（保密）；②設(shè)n=pq；③歐拉函數(shù)φ（n）=（p1）（q1）（保密）；④選取與φ（n）互素的正整數(shù)e，即滿足gcd(φ(n),e)=1和0eφ(n)；⑤計算d(保密)，使?jié)M足ed=1（mod φ(n)），即d和e相對于模φ(n)互為逆元素。由RSA算法原理可知，RSA算法的核心是求模取余運算，其安全性是建立在大合數(shù)因子分解困難的基礎(chǔ)之上的。（2）模運算的實現(xiàn)RSA算法的核心操作也是最耗時的操作是模運算，所以開發(fā)一種快速指數(shù)和取模運算是解決運算速度的關(guān)鍵。通常的模運算都是利用加減法來實現(xiàn)的，因為加減法指令的執(zhí)行速度快。在進行模運算時，一般先將指數(shù)e(長度為kbit)改寫成二進制數(shù)組的形式e，即其中：ei∈{0,1},i=0,1,Λ,k1。這樣，在計算me(mod n)時，先做一次平方運算，然后根據(jù)ei的值，再做一次乘法運算，以此來簡化模運算的復(fù)雜性。由于實際中的e值非常大，為了提高運算速度，可以將e進行分組后運算。設(shè)對e以四位一組（十六進制）的形式計算me(mod n)，那么：其中：ei∈{0,1,2,…,15}，t=k/4；②求出m2,m3,…，m15(mod n)；③設(shè)置變量c:=1；④對于i=t1,t2,…，1，0重復(fù)計算：c:=c2(mod n)(平方)；c:=c2(mod n)(四次方)；c:=c2(mod n)(八次方)；c:=c2(mod n)(十六次方)；≠0,則c:=cmei(mod n)。⑤所得c即為所求。 RSA算法的案例 例如大數(shù)18446744073709551615，等于 ffffffff ffffffff，就相當(dāng)于十進制的99：有兩位，每位都是ffffffff。而18446744073709551616 等于00000001 0000000000000000，就相當(dāng)于十進制的100：有三位，第一位是1 ，其它兩位是0，如此等等。 在實際應(yīng)用中，“數(shù)字”數(shù)組的排列順序采用低位在前高位在后的方式，這樣，大數(shù)A 就可以方便地用數(shù)學(xué)表達式來表示其值：A=Sum[i=0 to n](A[i]*0x100000000**i)（其中Sum 表示求和，A[i]表示用以記錄A 的數(shù)組的第i 個元素，**表示乘方）。 任何整數(shù)運算最終都能分解成數(shù)字與數(shù)字之間的運算，在0x100000000 進制下其“數(shù)字”最大達到0xffffffff，其數(shù)字與數(shù)字之間的運算，結(jié)果也必然超出了目前32系統(tǒng)的字長。在VC++中，存在一個__int64 類型可以處理64位的整數(shù)，所以不用擔(dān)心這一問題，而在其它編譯系統(tǒng)中如果不存在64位整形，就需要采用更小的進制方式來存儲大數(shù)，例如WORD類型（16位）可以用來表示0x10000 進制，但效率更高的辦法還是采用32位的DWORD 類型，只不過將0x100000000 進制改成0x40000000進制，這樣兩個數(shù)字進行四則運算的最大結(jié)果為 0x3fffffff * 0x3fffffff，小于0xffffffff，只是不能簡單地用高位低位來將運算結(jié)果拆分成兩個“數(shù)字”。加法設(shè)：A=Sum[i=0 to p](A[i]*0x100000000**i)B=Sum[i=0 to q](B[i]*0x100000000**i)，p=qC=Sum[i=0 to n](C[i]*0x100000000**i)=A+B顯然：C[i]不是簡單地等于A[i]+B[i]，因為如果C[i]0xffffffff就需要進位，當(dāng)然計算C[i1]時也可能產(chǎn)生了進位，所以計算C[i]時還要加上上次的進位值。 如果用carry[i]記錄每次的進位則有： C[i]=A[i]+B[i]+carry[i1]carry[i]*0x100000000 其中carry[1]=0 若A[i]+B[i]+carry[i1]0xffffffff，則carry[i]=1；反之則carry[i]=0 若carry[p]=0，則n=p；反之則n=p+1減法設(shè)：A=Sum[i=0 to p](A[i]*0x100000000**i)B=Sum[i=0 to q](B[i]*0x100000000**i)，p=qC=Sum[i=0 to n](C[i]*0x100000000**i)=AB顯然：C[i]不是簡單地等于A[i]B[i]，因為如果A[i]B[i]就需要借位，當(dāng)然計算C[i1]時也可能產(chǎn)生了借位，所以計算C[i]時還要減去上次的借位值。 如果用carry[i]記錄每次的借位則有： C[i]=A[i]+carry[i]*0x100000000B[i]carry[i1] 其中carry[1]=0 若A[i]B[i]則carry[i]=0；反之則carry[i]=1 若C[p]=0，則n=p1；反之則n=p乘法設(shè)：A=Sum[i=0 to p](A[i]*0x100000000**i)B=Sum[i=0 to q](B[i]*0x100000000**i)，p=qC=Sum[i=0 to n](C[i]*0x100000000**i)=A*B顯然：C=Sum[i=0 to q](A*B[i]*0x100000000**i)而(A*B[i]*100000000**i)=Sum[j=0 to p](A[j]*B[i]*0x100000000**(i+j))所以C=Sum[i=0 to q](Sum[j=0 to p](A[j]*B[i]*0x100000000**(i+j)))因此：C[i]=Sum[j=0 to q](A[ij]*B[j])+carry[i1]carry[i]*0x100000000其中carry[1]=0carry[i]=(Sum[j=0 to q](A[ij]*B[j])+carry[i1])/0x100000000n=p+q1，若carry[n]0，則n=n+1，C[n]=carry除法設(shè)： A=Sum[i=0 to p](A[i]*0x100000000**i) B=Sum[i=0 to q](B[i]*0x100000000**i)，p=q C=Sum[i=0 to n](C[i]*0x100000000**i)=A/B由于無法將B 對A “試商”，我們只能轉(zhuǎn)換成B[q]對A[p]的試商來得到一個近似值，所以我們不能夠直接計算C。但是，我們可以一步一步地逼近C顯然： (A[p]/B[q]1)*0x100000000**(pq)C令：X=0重復(fù)：A=AX*B，X=X+(A[p]/B[q]1)*0x100000000**(pq)，直到AB則有：X=C注意： 由于大數(shù)可理解為0x100000000進制，所以對于任意大數(shù)A*0x100000000**k都等價于將A 的數(shù)組中的各元素左移k 位，不必計算；同樣，除法則等價于右移取模設(shè)：A=Sum[i=0 to p](A[i]*0x100000000**i)B=Sum[i=0 to q](B[i]*0x100000000**i)，p=qC=Sum[i=0 to n](C[i]*0x100000000**i)=A%B求模與求商的過程一致，只是由于不需要記錄商而更加簡單：重復(fù)：A=A(A[p]/B[q]1)*0x100000000**(pq)*B，直到AB則有：A=C二元一次方程：在RSA 算法中，往往要在已知A、M的情況下，求 B，使得 (A*B)%M=1。即相當(dāng)于求解B、N都是未知數(shù)的二元一次不定方程 A*BM*N=1，的最小整數(shù)解。而針對不定方程axby=1 的最小整數(shù)解，古今中外都進行過詳盡的研究，西方有著名的歐幾里德算法，即輾轉(zhuǎn)相除法，中國有秦九韶的“大衍求一術(shù)”。歐幾里德算法是一種遞歸算法，比較容易理解：例如：11x49y=1，求x（a） 11 x 49 y = 149%11=5 （b） 11 x 5 y = 111%5 =1 （c）x 5 y = 1令y=0 [來源：]代入（c）得x=1令x=1 代入（b）得y=2令y=2 代入（a）得x=9同理可使用遞歸算法求得任意 axby=1（a、b互質(zhì)）的解，實際上通過分析歸納將遞歸算法轉(zhuǎn)換成非遞歸算法就變成了大衍求一術(shù)。冪模運算：冪模運算是RSA 核心算法，最直接地決定了RSA 算法的性能，針對快速冪模運算這一課題，許多西方現(xiàn)代數(shù)學(xué)家提出了大量的解決方案。通常都是先將冪模運算化簡為乘模運算。例如求D=C**15 % N，由于：a*b % n = (a % n)*(b % n) % n所以：C1=C*C % N =C**2 % N1