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