密碼學(xué)基本理論

密碼技術(shù)講義內(nèi)容提要密碼學(xué)基本知識對稱密碼算法公鑰密碼算法密碼學(xué)的發(fā)展歷史第1階段：1949年以前。

第2階段：從1949年到1975年。標(biāo)志：1949年Shanon發(fā)表的《保密系統(tǒng)的信息理論》一文。第3階段：1976年至今。標(biāo)志：1976年Diffie和Hellman發(fā)表了《密碼學(xué)新方向》一文。對稱密碼的模型傳統(tǒng)密碼/常規(guī)密碼/私鑰密碼/單鑰密碼conventional/private-key/single-key發(fā)送方和接收方共享一個共同的密鑰

senderandrecipientshareacommonkey所有的傳統(tǒng)密碼算法都是私鑰密碼20世紀(jì)70年代以前私鑰密碼是唯一類型至今仍廣泛應(yīng)用基本術(shù)語明文，plaintext-originalmessage密文，ciphertext-codedmessage密碼體制，密碼，cipher-algorithmfortransformingplaintexttociphertext密鑰，key-infousedincipherknownonlytosender/receiver加密，encipher(encrypt)-convertingplaintexttociphertext解密，decipher(decrypt)-recoveringciphertextfromplaintext密碼學(xué)

–密碼編碼學(xué)和密碼分析學(xué)密碼編碼學(xué)，cryptography

密碼分析學(xué)，密碼破譯，cryptanalysis(codebreaking)對稱密碼模型（SymmetricCipherModel）信道編碼信源編碼對稱密碼安全的兩個必備條件:加密算法必須是足夠強(qiáng)的

astrongencryptionalgorithm惟有發(fā)送者和接收者知道的秘密密鑰

asecretkeyknownonlytosender/receiver數(shù)學(xué)表示:

C=EK(P) P=DK(C)假設(shè)加/解密算法是已知的擁有一個安全通道用于分發(fā)密鑰安全要求加密算法必須足夠強(qiáng)最低要求：已知密文時不能破譯該密文或由密文推導(dǎo)出密鑰；加強(qiáng)形式：已知某些明、密文對，也不能由此破譯出新的密文或發(fā)現(xiàn)密鑰。算法是基于密鑰的：通信雙方必須在某種安全形式下獲得密鑰并必須保證密鑰的安全密碼編碼學(xué)

Cryptography研究內(nèi)容主要研究對信息進(jìn)行編碼，實現(xiàn)對信息的隱蔽。特征運(yùn)算類型：代換與置換所用的密鑰數(shù)：單鑰與雙鑰處理明文的方法：分組密碼與流密碼密鑰流產(chǎn)生器密鑰k明文m密文c流密碼體制模型異或運(yùn)算流密碼模型密碼分析學(xué)

Cryptanalysis密碼破譯攻擊的一般方法密碼分析學(xué)：cryptanalyticattack窮舉攻擊：brute-forceattack兩個概念絕對安全，unconditionalsecurity

計算安全，computationalsecurity

19世紀(jì)，Kerckhoff原則：系統(tǒng)的保密性不依賴于對加密體制或算法的保密，而依賴于對密鑰的保密。密碼算法分類按照保密內(nèi)容受限制的（restricted）算法：算法的保密性基于保持算法的秘密；基于密鑰的（key-based）算法：算法的保密性基于對密鑰的保密基于密鑰的算法，按照密鑰特點對稱密碼算法（傳統(tǒng)密碼算法或單鑰密碼算法）非對稱算法（公開鑰密碼算法或雙鑰密碼算法）按照明文處理方式分組密碼流密碼對稱密碼算法DESIDEAAES對稱密碼

在密碼體系中，若加密密鑰和解密密鑰相同，則稱此密碼體系為對稱密碼體系。對稱密碼需要滿足的兩個條件：（1）若已知密鑰k，解密過程是相對簡單的；（2）若密鑰k未知,解密過程在現(xiàn)實的時間內(nèi)是不可能實現(xiàn)的。每種現(xiàn)代對稱加密算法都符合兩種基本運(yùn)算方式：擴(kuò)散(diffusion)和替換(substitution)。也就是說，密文的內(nèi)容用不同的位和字節(jié)代替了明文中的位和字節(jié)（替換），并在密文中將這些替換的位和字節(jié)轉(zhuǎn)移到不同的地方（擴(kuò)散）。對稱密碼分類

分組密碼：此密碼體系對加密消息進(jìn)行分組，每次使用相同的密鑰，對其中的一個分組進(jìn)行加密。流密碼：此密碼體系每次對消息的一個比特（字節(jié)或字）進(jìn)行操作，并采用了一些反饋機(jī)制，所以其密鑰在加解密過程中一般是變化的。背景簡介1973年5月15日，NBS(現(xiàn)在NIST，美國國家標(biāo)準(zhǔn)技術(shù)研究所)開始公開征集標(biāo)準(zhǔn)加密算法，并公布了它的設(shè)計要求：（1）算法必須提供高度的安全性（2）算法必須有詳細(xì)的說明，并易于理解（3）算法的安全性取決于密鑰，不依賴于算法（4）算法適用于所有用戶（5）算法適用于不同應(yīng)用場合（6）算法必須高效、經(jīng)濟(jì)（7）算法必須能被證實有效（8）算法必須是可出口的數(shù)據(jù)加密標(biāo)準(zhǔn)(DES)背景簡介1974年8月27日，NBS開始第二次征集，IBM提交了算法LUCIFER，該算法由IBM的工程師在1971~1972年研制1975年3月17日，NBS公開了全部細(xì)節(jié)1976年，NBS指派了兩個小組進(jìn)行評價1976年11月23日，采納為聯(lián)邦標(biāo)準(zhǔn)，批準(zhǔn)用于非軍事場合的各種政府機(jī)構(gòu)1977年1月25日，“數(shù)據(jù)加密標(biāo)準(zhǔn)”FIPSPUB46發(fā)布數(shù)據(jù)加密標(biāo)準(zhǔn)(DES)DES的生命期

NBS最終采納了IBM的LUCIFER方案，于1975年公開發(fā)表。1977年正式頒布為數(shù)據(jù)加密標(biāo)準(zhǔn)（DES-DataEncryptionStandard）。1979年，美國銀行協(xié)會批準(zhǔn)使用DES。1980年，DES成為美國標(biāo)準(zhǔn)化協(xié)會(ANSI)標(biāo)準(zhǔn)。1984年，ISO開始在DES基礎(chǔ)上制定數(shù)據(jù)加密的國際標(biāo)準(zhǔn)。美國國家安全局NSA每隔年對該算法進(jìn)行評估，1994年，決定1998年12月之后不再使用DES?，F(xiàn)已經(jīng)確定了選用Rijndael算法作為高級加密算法AES。背景簡介FIPSPUB46爭論密鑰短：56位S盒未公開數(shù)據(jù)加密標(biāo)準(zhǔn)(DES)DES加密加密算法框架C＝DES（m）＝

初始置換IP(675a69675e5a6b5a)=(ffb2194d004df6fb)單輪變換的詳細(xì)過程單輪操作結(jié)構(gòu)加密：Li

=Ri–1Ri

=Li–1

F(Ri–1,Ki)解密：Ri–1=Li

Li–1

=Ri

F(Ri–1,Ki)＝Ri

F(Li

,Ki)單輪變換的詳細(xì)過程單輪操作結(jié)構(gòu)單輪變換的詳細(xì)過程函數(shù)FExpansion:32->48S-box:6->4Permutation:32->32單輪變換的詳細(xì)過程函數(shù)F第i輪輸入第i輪輸出單輪變換的詳細(xì)過程函數(shù)F單輪變換的詳細(xì)過程擴(kuò)展置換E：32bit→48bit第32比特→第1比特第01比特→第2比特…………第01比特→第48比特單輪變換的詳細(xì)過程壓縮置換（S盒）：6bit→4bit,48bit→32bit8個S盒例：00010203040506070809101112131415012313020804061511011009031405001207011513081003070412050611001409020711040109121402000610131503050802011407041008131512090003050611輸入輸出單輪變換的詳細(xì)過程P置換（P盒）：32bit→32bit第16比特→第1比特第07比特→第2比特…………第25比特→第32比特子密鑰生成算法框架子密鑰生成兩個選擇置換（64bit→56bit，56bit→48bit）第57比特→第1比特第49比特→第2比特…………第04比特→第56比特（舍棄了奇偶校驗位，即第8，16，…，64位）第14比特→第1比特第17比特→第2比特…………第32比特→第48比特（舍棄了第9,18,22,25,35,38,43,54比特位）子密鑰生成循環(huán)移位第3~8，10~15輪，左移2位，其余為1位加密過程:(1)(2)運(yùn)算進(jìn)行16次后就得到密文組。

L0R0

IP(〈64bit輸入碼〉)

LiRi-1

i=1,...,16(1)

RiLi-1f(Ri-1,

ki)i=1,...,16(2)〈64bit密文〉IP-1(R16L16)解密過程:(3)(4)運(yùn)算進(jìn)行16次后就得到明文組。

R16L16

IP(〈64bit密文〉)

Ri-1

Li

i=16,...,1 (3)

Li-1Rif(Li-1,ki)i=16,...,1 (4)〈64bit明文〉IP-1(R0L0)DES解密與加密算法相同，子密鑰倒序。雪崩效應(yīng)56密鑰的使用256=7.2x10161997，幾個月

1998，幾天

1999，22個小時!DES算法的性質(zhì)：S盒構(gòu)造方法未公開！計時攻擊弱密鑰弱密鑰：8個弱密鑰半弱密鑰：2個半弱密鑰DES的強(qiáng)度DESCrackerTheElectronicFrontierFoundationbuilttheso-calledDESCrackersupercomputerin1998tocrack56-bitDESencryption.ItlaterwonRSALaboratory's"DESChallengeII"contestinabout56hours.DESCrackerhad26(andlater27)systemboards,eachwith32or64customAWT-4500DeepCrackchips,foratotalofabout1,500to1,800chips.IDEA

國際數(shù)據(jù)加密算法(InternationalDataEncryptionAlgorithm，IDEA)是由兩位研究員XuejiaLai和JamesL.Massey在蘇黎世的ETH開發(fā)的，一家瑞士公司AscomSystec擁有專利權(quán)。IDEA是作為迭代的分組密碼實現(xiàn)的，使用128位的密鑰和8個循環(huán)。這比DES提供了更多的安全性。和DES一樣，IDEA的加解密過程也是相似的。它基于“相異代數(shù)群上的混合運(yùn)算”設(shè)計思想，用硬件和軟件實現(xiàn)其算法都很容易且比DES在實現(xiàn)上快得多。加密操作

IDEA將輸入的64比特明文組經(jīng)過8輪迭代后產(chǎn)生64比特密文輸出，第r輪使用六個16比特的子密鑰Ki(r)將64比特的輸入轉(zhuǎn)化為4個16比特的輸出。得到第八輪的輸出后，利用4個子密鑰Ki(9)，1≤i≤4對其進(jìn)行輸出變換產(chǎn)生最終的密文Y=(Y1,Y2,Y3,Y4)；

⊕表示模2的加法，⊙表示模216+1的乘法，?表示模216+1的加法。IDEA加密框圖子密鑰產(chǎn)生

以輸入的8×16比特會話密鑰作為前8個子密鑰，而后將128位移存器循環(huán)左移25位，形成子密鑰k9—k16，。這一過程一直重復(fù)，直到給出子密鑰k49—k52。解密操作

解密過程基本和加密過程相同，僅解密子密鑰與加密子密鑰之間具有如表給出的關(guān)系。其中k-1表示k模216+1的乘法逆元，即k⊙k-1=1；-k表示k模216+1的加法逆元，即k?(-k)=0。密鑰擴(kuò)展框圖安全性

IDEA似不夠成群，窮舉破譯IDEA要求進(jìn)行2128次試探，其能抗差值分析和相關(guān)分析。但是在選擇用于IDEA的密鑰時，應(yīng)該排除那些稱為“弱密鑰”的密鑰。IDEA中的弱密鑰數(shù)相當(dāng)可觀，有251個。但是，如果密鑰的總數(shù)非常大，達(dá)到2128，那么仍有277個密鑰可供選擇。AES(AdvancedEncryptionStandard)

隨著計算機(jī)系統(tǒng)能力的不斷發(fā)展，DES的安全性比它剛出現(xiàn)時弱得多，現(xiàn)在DES僅用于舊系統(tǒng)的鑒定，如果DES已經(jīng)到了它使用壽命的盡頭，高級加密標(biāo)準(zhǔn)(AES)會代替DES作為新的安全標(biāo)準(zhǔn)。在1997年，美國國家標(biāo)準(zhǔn)和技術(shù)研究所(USNationalInstituteofStandardsandTechnology，NIST)曾宣布一項競賽，將15個原始項減少到5個。比利時的JoanDaemen和VincentRijmen提交的一個名為Rijndael的算法最終獲勝成為高級加密標(biāo)準(zhǔn)算法。從技術(shù)上講，Rijndael的結(jié)構(gòu)是復(fù)雜的而且有點不同尋常，卻似乎非常安全且通用，因為它的執(zhí)行速度很快，十分適合于現(xiàn)代需求（如智能卡），而且能夠使用的密鑰大小范圍很廣。AES算法的操作都在一個2維矩陣上執(zhí)行，稱之為狀態(tài)(state)。狀態(tài)由4行、Nb列的一個字節(jié)矩陣表示，這里Nb等于明文分組的長度被32整除后的值。我們考慮Nb=4。在加密和解碼的初期，輸入矩陣被復(fù)制到如下圖的狀態(tài)矩陣中，之后所有的加密和解密操作都在狀態(tài)矩陣上進(jìn)行，得到的結(jié)果再被復(fù)制到輸出矩陣，即滿足下式：s[r,c]=in[r+4c]，0≤r<4，0≤c<Nbout[r+4c]=s[r,c]，0≤r<4，0≤c<Nb其中狀態(tài)可記為數(shù)組w0w1w2w3，w0=s0,0s1,0s2,0s3,0w2=s0,2s1,2s2,2s3,2w1=s0,1s1,1s2,1s3,1w3=s0,3s1,3s2,3s3,3

加密操作

首先將輸入復(fù)制到狀態(tài)矩陣。在經(jīng)過10、12或14次（取決于密鑰長度）的輪變換之后將結(jié)果復(fù)制到輸出矩陣，其中最后一次輪變換和前Nr-1次有所不同。加密算法的偽代碼如下，其中w[]是密鑰表。Cipher(bytein[4*Nb],byteout[4*Nb],wordw[Nb*(Nr+1)])beginbytestate[4,Nb]state=inAddRoundKey(state,w[0,Nb-1])forround=1step1toNr–1SubBytes(state)ShiftRows(state)MixColumns(state)AddRoundKey(state,w[round*Nb,(round+1)*Nb-1])endforSubBytes(state)ShiftRows(state)AddRoundKey(state,w[Nr*Nb,(Nr+1)*Nb-1])out=stateend字節(jié)代替SubBytes()

將狀態(tài)陣列的每個字節(jié)做相同的變換，該變換由以下兩個子變換所合成：（1）首先將字節(jié)看作GF(28)上的元素，映射到自己的乘法逆；00字節(jié)映射到它自身。（2）其次，將字節(jié)做如下的仿射變換（GF(2)上）：bi’=b(i+4)mod8+b(i+5)mod8+b(i+6)mod8+b(i+7)mod8+ci行移位ShiftRows()

將狀態(tài)陣列的各行進(jìn)行循環(huán)移位，不同的狀態(tài)行的位移量不同。第0行不移動，第一行循環(huán)左移C1個字節(jié)，第二行循環(huán)左移C2個字節(jié)，第三行循環(huán)左移C3個字節(jié)。位移量的選取與Nb有關(guān)。即行位移滿足下式：sr,c=sr,(c+shift(r,Nb))modNb，0<r<4，0≤c<Nb

對于Nb=4，有shift(1,4)=1，shift(2,4)=2，shift(3,4)=3。列混合MixColumns()

將狀態(tài)陣列的每個列視為系數(shù)在GF(28)上、次數(shù)小于4的多項式，被同一個固定的多項式a(x)進(jìn)行模x4+1乘法。當(dāng)然要求a(x)是模x4+1可逆的多項式，否則列混合變換就是不可逆的，因而會使不同的明文分組具有相同的對應(yīng)密文分組。Rijndael的設(shè)計者所給出的a(x)為（系數(shù)用十六進(jìn)制數(shù)表示）：a(x)={03}x3+{01}x2+{01}x+{02}a(x)是與x4+1互素的，因此是模x4+1可逆的。列混合運(yùn)算可表示為GF(28)上的可逆線性變換：s’(x)=a(x)×s(x)：密鑰擴(kuò)展

AES的密鑰擴(kuò)展算法需要個Nb的初始值，產(chǎn)生Nb(Nr+1)個結(jié)果。每輪操作都需要Nb個字的密鑰數(shù)據(jù)。擴(kuò)展算法的偽代碼如下：KeyExpansion(bytekey[4*Nk],wordw[Nb*(Nr+1)],Nk)beginwordtempi=0while(i<Nk)w[i]=word(key[4*i],key[4*i+1],key[4*i+2],key[4*i+3])i=i+1endwhilei=Nkwhile(i<Nb*(Nr+1)]temp=w[i-1]if(imodNk=0)temp=SubWord(RotWord(temp))xorRcon[i/Nk]elseif(Nk>6andimodNk=4)temp=SubWord(temp)endifw[i]=w[i-Nk]xortempi=i+1endwhileend解密算法

InvCipher(bytein[4*Nb],byteout[4*Nb],wordw[Nb*(Nr+1)])beginbytestate[4,Nb]state=inAddRoundKey(state,w[Nr*Nb,(Nr+1)*Nb-1])forround=Nr-1step-1downto1InvShiftRows(state)InvSubBytes(state)AddRoundKey(state,w[round*Nb,(round+1)*Nb-1])InvMixColumns(state)endforInvShiftRows(state)InvSubBytes(state)AddRoundKey(state,w[0,Nb-1])out=stateend安全性

從技術(shù)上講，Rijndael的結(jié)構(gòu)是非常復(fù)雜的，同時其也非常安全且通用，可以有效的抵抗差分攻擊法，線性攻擊法，平方攻擊法和內(nèi)插攻擊法，而且在Rijndael之中不存在弱密鑰問題。公鑰密碼學(xué)基本原理RSARabinElGamalMcElieceECC2023/1/16西安電子科技大學(xué)計算機(jī)學(xué)院63公鑰密碼體制的基本原理傳統(tǒng)密碼體制只使用一個密鑰；收發(fā)雙方共享這個單一的密鑰；密鑰是對稱的，雙方是對等的；因此，不能確保接收方偽造信息，并聲稱是該信息是發(fā)送方發(fā)送的。2023/1/16西安電子科技大學(xué)計算機(jī)學(xué)院64對稱密碼體制的缺陷2023/1/16西安電子科技大學(xué)計算機(jī)學(xué)院65公鑰密碼體制密碼學(xué)發(fā)展歷史中最偉大的一次革命；采用兩個密鑰：一個公鑰，一個私鑰；參與方不對等，所以是非對稱的；基于數(shù)論中的結(jié)論；是私鑰密碼的補(bǔ)充而不是代替。2023/1/16西安電子科技大學(xué)計算機(jī)學(xué)院66為什么需要公鑰密碼?兩個考慮：密鑰分配-KDC數(shù)字簽名公認(rèn)該發(fā)明屬于StanfordUni的WhitfieldDiffie和

MartinHellman，于1976年。"NewDirectionsinCryptography",IEEETrans.InformationTheory,IT-22,pp644-654,Nov1976JamesEllis(UKCESG)在1970年曾提出此概念2023/1/16西安電子科技大學(xué)計算機(jī)學(xué)院67公鑰密碼體制公鑰/雙鑰/非對稱密碼都是指使用兩個密鑰:公鑰：可以對任何人公開的密鑰，用于加密消息或驗證簽名。

私鑰：只能由接收者私存，用于解密消息或簽名。非對稱：任何只知道公鑰的人，只能加密消息或驗證簽名的，不能進(jìn)行消息的加密或消息的簽名。2023/1/16西安電子科技大學(xué)計算機(jī)學(xué)院68公鑰密碼體制2023/1/16西安電子科技大學(xué)計算機(jī)學(xué)院69公鑰密碼體制特點公鑰密碼算法依賴于:僅僅知道算法和加密密鑰，推導(dǎo)解密密鑰計算上是不可行的；已知加解密密鑰時，進(jìn)行加解密運(yùn)算計算上是容易的；兩個密鑰中的任何一個都可以用來加密，而另一個用來解密。2023/1/16西安電子科技大學(xué)計算機(jī)學(xué)院70公鑰密碼體制特點公鑰密碼算法應(yīng)該滿足的條件:產(chǎn)生一對密鑰（公、私鑰對）在計算上是容易的；已知公鑰和要加密的消息，發(fā)送方產(chǎn)生相應(yīng)的密文在計算上容易的；接收方使用其私鑰對接收的密文解密以恢復(fù)明文在計算上是容易的；已知公鑰時，攻擊者要確定私鑰在計算上不可行的；已知公鑰和密文，攻擊者要恢復(fù)明文在計算上不可行的；加密和解密函數(shù)的順序可以交換（有用但非必要）。2023/1/16西安電子科技大學(xué)計算機(jī)學(xué)院71單向陷門函數(shù)單向陷門函數(shù)：若k和X已知，則容易計算Y=fk(X).若k和Y已知，則容易計算X=fk-1(Y).若Y已知但k未知，則計算出X=fk-1(Y)是不可行的.尋找合適的單向陷門函數(shù)是公鑰密碼體制應(yīng)用的關(guān)鍵單向陷門函數(shù)舉例：離散對數(shù)大整數(shù)分解背包問題2023/1/16西安電子科技大學(xué)計算機(jī)學(xué)院72公鑰密碼體制：保密性和認(rèn)證2023/1/16西安電子科技大學(xué)計算機(jī)學(xué)院73公鑰密碼體制的應(yīng)用分為三類:加密/解密

(提供保密性)數(shù)字簽名(提供認(rèn)證)密鑰交換

(會話密鑰)一些算法可用于上述三類，而有些只適用用于其中一類或兩類。2023/1/16西安電子科技大學(xué)計算機(jī)學(xué)院74公鑰密碼體制安全性分析一樣存在窮舉攻擊但所使用的密鑰一般都非常大(>512bits)安全性基于容易（加解密）和困難（破譯）之間巨大的差別許多算法沒有得到證明是安全的（包括RSA）

需要采用一些特別大的數(shù)字與私鑰密碼體制相比，速度慢2023/1/16西安電子科技大學(xué)計算機(jī)學(xué)院75RSA1977由MIT的Rivest,Shamir和

Adleman發(fā)明已知的且被廣泛使用的公鑰密碼方案有限域中的乘方運(yùn)算乘方運(yùn)算需要O((logn)3)操作(容易的)使用一些大的整數(shù)

(例如.1024bits)安全性基于大數(shù)的素因子分解的困難性素因子分解需要O(elognloglogn)操作(困難的)2023/1/16西安電子科技大學(xué)計算機(jī)學(xué)院762023/1/16西安電子科技大學(xué)計算機(jī)學(xué)院772023/1/16西安電子科技大學(xué)計算機(jī)學(xué)院78RSA密鑰的建立每一個用戶通過以下方法產(chǎn)生一個公鑰/私鑰對:隨機(jī)地選擇兩個大的素數(shù)p,q計算方案中的模數(shù)n=p.q?(n)=(p-1)(q-1)隨機(jī)地選擇一個加密密鑰e滿足1<e<?(n),(e,?(n))=1求解下面的方程，以得到解密密鑰de.d≡1mod?(n)and0≤d≤n公開公鑰:PU={e,n}保密私鑰:PR={d,n}2023/1/16西安電子科技大學(xué)計算機(jī)學(xué)院79RSA的使用為了加密消息M，發(fā)送方:獲得接收方的公鑰PU={e,n}計算:C=Memodn,其中0≤M<n為了解密密文C，接收者:使用自己的私鑰PR={d,n}計算:M=Cdmodn消息M一定要比模數(shù)n小(如果需要的話，可以進(jìn)行分組)2023/1/16西安電子科技大學(xué)計算機(jī)學(xué)院80RSA的工作原理Euler定理:a?(n)modn≡1其中(a,n)=1RSA中:n=p.q?(n)=(p-1)(q-1)仔細(xì)地選擇e和d使得mod?(n)下，兩者互逆因此存在某個整數(shù)k，使得e.d=1+k.?(n)成立所以:

Cd=Me.d=M1+k.?(n)=M1.(M?(n))k

≡M1.(1)k=M1=Mmodn2023/1/16西安電子科技大學(xué)計算機(jī)學(xué)院81RSA舉例–密鑰的建立選擇素數(shù):p=17&q=11計算n=pq=17x11=187計算?(n)=(p–1)(q-1)=16x10=160選擇e:

gcd(e,160)=1;選擇e=7確定d:de=1mod160且

d<160

d=23因為23x7=161=10x160+1公鑰

PU={7,187}私鑰

PR={23,187}2023/1/16西安電子科技大學(xué)計算機(jī)學(xué)院82RSA舉例–加密/加密明文消息M=88(注意88<187)加密:C=887mod187≡11解密:M=1123mod187≡882023/1/16西安電子科技大學(xué)計算機(jī)學(xué)院83冪運(yùn)算可以用平方和乘法運(yùn)算N次方，只需要O(log2n)次乘法運(yùn)算如.75=74.71=3.7=10mod11如.3129=3128.31=5.3=4mod112023/1/16西安電子科技大學(xué)計算機(jī)學(xué)院84冪運(yùn)算c=0;f=1fori=kdownto0doc=2xcf=(fxf)modnifbi==1thenc=c+1f=(fxa)modnreturnf2023/1/16西安電子科技大學(xué)計算機(jī)學(xué)院852023/1/16西安電子科技大學(xué)計算機(jī)學(xué)院86加密的效率加密要計算e次方冪若e較小,計算將很快通常選擇

e=65537(216-1)或選擇

e=3或

e=17但若e太小

(如

e=3)將易受到攻擊用中國剩余定理必須確保(e,?(n))=12023/1/16西安電子科技大學(xué)計算機(jī)學(xué)院87解密的效率解密計算d次方冪看起來很大，否則不安全用中國剩余定理分別計算modp和modq，則可以得到所希望的答案比直接快約4倍只有知道p和q及私鑰的接收者可以直接采用這個技術(shù)進(jìn)行計算2023/1/16西安電子科技大學(xué)計算機(jī)學(xué)院88RSA密鑰的產(chǎn)生RSA的用戶必須:隨機(jī)確定兩個素數(shù)p,q選擇e或d，并求出另一個素數(shù)

p,q一定不能從n=p.q輕易得到意味著數(shù)要足夠大典型地用猜測或可能性測試指數(shù)e,d是互逆的2023/1/16西安電子科技大學(xué)計算機(jī)學(xué)院89RSA安全性分析攻擊RSA可能的方法有:窮舉搜索

(對于給定的數(shù)字規(guī)模是不可行的)數(shù)學(xué)攻擊(基于計算?(n)的困難性,模n的因子分解的困難性)計時攻擊

(基于解密的運(yùn)行情況)選擇密文攻擊(RSA的已知特性)2023/1/16西安電子科技大學(xué)計算機(jī)學(xué)院90RSA系統(tǒng)安全性與系統(tǒng)的參數(shù)RSA系統(tǒng)安全性與系統(tǒng)的參數(shù)有很大關(guān)系，X.931標(biāo)準(zhǔn),ISO/IEC14752對此提出以下幾點：如果公鑰e是奇數(shù)，e應(yīng)與p-1，q-1互質(zhì)；如果公鑰e是偶數(shù)，e必須與(p-1)/2,(q-1)/2互質(zhì)，且pqmod8不成立；模數(shù)的長應(yīng)該為1024+256x，x=0,1??????；質(zhì)數(shù)p，q應(yīng)通過質(zhì)數(shù)檢測，使出錯的概率小于；p-1,q-1,p+1,q+1應(yīng)有大質(zhì)數(shù)因子；gcd(p-1,q-1)應(yīng)該?。籶/q不應(yīng)靠近兩個小整數(shù)比值，且；|p-q|應(yīng)有大質(zhì)數(shù)因子。2023/1/16西安電子科技大學(xué)計算機(jī)學(xué)院91分解因子問題數(shù)學(xué)攻擊的三種形式:分解

n=p.q,計算?(n)從而得到d直接確定

?(n)

并計算

d直接尋找d對于因子分解問題很多年來進(jìn)展很慢用“LatticeSieve”(LS),算法，最好的是分解了200位十進(jìn)制數(shù)(663bit)最大的改進(jìn)就是對改進(jìn)算法的改良

QStoGHFStoLS當(dāng)前假設(shè)1024-2048bitRSA是安全的確保

p,q有相似的大小并滿足其它約束2023/1/16西安電子科技大學(xué)計算機(jī)學(xué)院922023/1/16西安電子科技大學(xué)計算機(jī)學(xué)院93計時攻擊20世紀(jì)90年代由PaulKocher提出探測操作中的時間變化eg.multiplyingbysmallvslargenumberorIF'svaryingwhichinstructionsexecuted基于所耗時間的大小，對操作數(shù)的大小進(jìn)行猜測RSAexploitstimetakeninexponentiationCountermeasures(解決辦法)useconstantexponentiationtime（不變的冪運(yùn)算時間）addrandomdelays（隨機(jī)時延）blindvaluesusedincalculations（隱蔽）2023/1/16西安電子科技大學(xué)計算機(jī)學(xué)院94選擇密文攻擊RSA對于選擇密文來說是易受攻擊的攻擊者選擇密文并得到相應(yīng)明文選擇密文可給密碼分析者探測RSA的特性提供信息optimalasymmetricencryptionpadding(OAEP).練習(xí)題Rabin1979年提出的Rabin公鑰加密是第一個概率安全的公鑰加密體系，對被動攻擊者來說，其困難程度等同于分解大整數(shù)。

Rabin的公鑰只有一部分：正整數(shù)n，同樣作為有效的公鑰，要求n是２個不同的奇素數(shù)p和q的乘積。

Rabin的私鑰也由兩部分組成：正整數(shù)p和正整數(shù)q。加密操作(n,m)：輸入：Rabin公鑰n，明文m

輸出：密文c算法：1.計算c=m2modn；

2.輸出c。解密操作(p,q,c)：輸入：Rabin私鑰(p,q)，密文c輸出：可能的明文m1、m2、m3、m4

算法：1.計算m=c2modn的４個根m1、m2、m3、m4；

2.輸出m1、m2、m3、m4；

3.解密者選擇正確的明文m。安全性

求解Rabin的困難度取決于求解二次平方剩余問題，這等同于分解大整數(shù)的困難度。Rabin公鑰密碼體系只能夠防御被動攻擊者，對于選擇密文攻擊來說，Rabin很容易就會被攻破。所有對RSA公鑰密碼體系的攻擊方法都可以用來攻擊Rabin公鑰密碼體系。

Rabin公鑰密碼體系的一個缺點是解密者必須從4個可能的明文中選擇正確的一個。在實際操作中，人們采用冗余技術(shù)克服這一缺點，如在明文之后加入一些冗余信息，這不僅克服了上述缺點，而且還能防御選擇密文攻擊。ElGamal

TaherElgamal在1984和1985年間提出了一種基于離散對數(shù)問題的公鑰密碼體系，其類似于Diffie-Hellman的密鑰協(xié)商協(xié)議。

ElGamal的私鑰有以下兩部分：大的隨機(jī)素數(shù)p,和上的隨機(jī)數(shù)α