第七章 公鑰密鑰體制

第七章 公鑰密鑰體制

公鑰密碼體制概述

• 對稱密碼體制的局限性：

• 密鑰分發問題
• 密鑰管理問題
• 數字簽名問題

• 公鑰加密體制的思想

• 公鑰和私鑰
• 基于陷門單向函數的困難問題

• 公鑰密碼體制的分類

公鑰加密體制介紹

ElGamal	應用	1.加密；2.數字簽名
密鑰生成	随機選擇一個滿足安全要求的1024位的大素數p，并生成有限域Zp的一個生成元g∈Zp*； 選擇一個随機數x(1<x<p-1)，計算y≡gx(mod p),則公鑰為(y,g,p)，私鑰為Sk=x。                           （随機數的選取可以使同一明文在不同時間加密成不同密文）
加解密算法	加密過程：将明文分組比特串分組，是分組長度小于log2p,，然後對每個明文分組分别加密 得到公鑰Pk（y,g,p）； 消息m分組m1m2m3m4······ 對第i塊消息随機選擇整數ri(1<ri<p-1); 計算ci≡gri(mod p),ci'≡miyri(mod p)(1≤i≤t) 将密文C=(c1,c1')()()()····發送給接收方  （可知，密文是明文長度的2倍） 解密過程 接收方接收密文C 使用密鑰x和解密算法mi≡(ci'/cix)(mod p)(1≤i≤t)進行計算 得到明文 正确性
安全性分析	窮舉法和清單法（二分查找算法） O（p） 小步大步算法 來源于生日攻擊的思想， 小步為 序列1：g1,···,gj,···,gm(1≤j≤m) 大步為 序列2：y,y*g-m,···，y*g-im 找到gj≡y*g-im(mod p),即找到y=gj+im(mod p),即x=j+im私鑰被找到 時間複雜度：O(p1/2) 3.指數積分法  選取因子基S 建構同餘方程組：對若幹随機整數k(0≤k≤p)，計算gk，嘗試将gk寫成S中的元素幂次的乘積，即gk=∏piei(mod p),式子兩邊取離散對數k≡∑eilogg(pi)(mod (p-1)),重複這個過程，直到有超過m個方程 求logg(pi) 計算x:随機取整數r，計算ygrmod p，使得其值可表示為S中元素幂次的乘積，即ygr=∏pidi(mod p),取離散對數可得x≡logg(y)≡-r+∑dilogg(pi)(mod (p-1)),如果成功，即求得此解x。
MH背包公鑰加密體制	難題來源	背包問題：∑aixi=b，這是一個NP完全類問題 特例：超遞增序列（每一個元素都比先前的元素和大） 可将背包問題轉化為P類問題
公私鑰對的生成	選取素數p 和u，且bi為超遞增序列 利用uv=1（mod p）可求得v a=ubk(mod p) {ai}和p作為公鑰，{bi}和v作為私鑰
加密和解密	明文消息分組 密文c=a1m1+···+anmn 利用{bi}求v c的解，可得消息m
安全性分析	NP類問題，至今沒有好的求解方法，能經受住窮舉攻擊 隐蔽性不夠，此公鑰密碼是不安全的
地位	第一個公鑰算法
RSA公鑰密碼	理論基礎	數論中的歐拉定理，安全性依賴于大整數的素因子分解的困難性 歐拉定理：若a和n互素，則aΦ(n)≡1(mod n)
密鑰生成算法 加密和解密	（1）生成公私密鑰 選取兩個大素數p和q，至少要1024位 計算n=p*q 随機選取整數e在(1≤e≤Φ(n))作為公鑰，要求滿足gcd(e,Φ(n))=1 用Euclid擴充算法計算私鑰d，滿足d*e≡1(mod Φ(n)),則e和n是公鑰，d是私鑰 （3）明文加密  　c=E(m)=me(mod n) （4）密文解密。    m=D(c)=cd(mod n)
安全性	1.算法正确性的證明 2.攻擊 針對n分解的攻擊 試除法 因子分解分析法：二次篩因子分析法 側信道攻擊            2.針對算法參數的攻擊                        1.對素數p和q選取時的限制；p和q長度相差不大，大小相差要大，否則難以抵禦除法的攻擊；p-1和q-1都應有大的素因子。                        2.共模攻擊（是以不同使用者不用使用相同的p和q）                        3.低指數攻擊
橢圓曲線公鑰加密體制	橢圓曲線	韋爾斯特拉方程 ：E:y²+axy+by=x³+cx²+dx+e。密碼學中，常采用的橢圓曲線為： E:y²=x³+ax+b，并要求4a³+27b²≠0 Hasse定理：如果E是有限域GF(p)上的橢圓曲線，N是E上的點(x,y)（其中x,yξGF(p)）的個數，則：|N-(p+1)|≤2(p)½ 橢圓曲線上的點集合Ep（a,b）對于如下定義的加法規則構成一個Abel群： O+O=O;(O是機關元) 橢圓上的點P，P+O=P； P的逆元是-P； 滿足交換律 滿足結合律 點乘規則： 如果k為整數，kP=P+···+P    （k個P相加） 如果s和t為整數，(s+t)P=sP+tP,s(tP)=t(sP) 橢圓曲線點的計算：
ECC密鑰生成算法	選擇一個橢圓曲線E，構造一個橢圓群Ep(a,b)。  在橢圓群中挑選生成元點G=(x0,y0),需滿足nG=O的最小的n是一個非常大的素數。 選擇一個小于n的整數nB作為私鑰，然後利用PB=nBG算出PB。        公鑰為(E,n,G,PB)，私鑰為nB。
加密過程	A将明文消息編碼成一個數m<p,并在橢圓群Ep(a,b)中任選一點Pt=(xt,yt); 在區間[1,n-1]内，A選取一個随機數k，計算P1：P1=(x1,y1)=kG; 依據接收方B的公鑰PB，A計算點P2：P2=(x2,y2)=kPB； A計算密文C=mxt+yt; A傳送加密資料Cm={kG,Pt+kPB,C}給接收方B。
解密過程	接收方B收到Cm; B使用私鑰nB做運算：Pt+kPB-nB(kG)=Pt+k(nBG)-nB(kG)=Pt; B計算m=(C-yt)/xt,得明文m。
安全性和優勢	安全性基于橢圓曲線上的離散對數問題
應用前景好，尤其是在移動通信和無線裝置上的應用，計算量小，處理速度快，存儲空間占用小，帶寬要求低。
160位的ECC密鑰和1024位的RSA和1024位的ElGamal的安全性等同。
可用于加密、數字簽名。
未申請專利
Rabin公鑰加密體制	前言（學習意義）	具有很好的參考價值
特點	不是以一一對應的陷門單向函數為基礎，同一密文可能有多種明文；
破譯該體制等價于對大整數的因子分解。
密鑰生成算法	随機選取兩個大素數p和q，并且p≡q≡3mod4，将p和q作為私鑰，n=pq作為公鑰
加密算法	設明文塊為m(m<n)，運用公式c=m²modn 進行加密，c為密文。
解密算法