私鑰分組加密  

  

  
   上圖的證明中，r^(j)兩兩不同的概率計(jì)算是關(guān)鍵，下面給出詳細(xì)過(guò)程
       
  Construction 5.3.9一次只能加密與密鑰等長(zhǎng)的明文，如果要加密更長(zhǎng)的明文，怎么辦？一個(gè)簡(jiǎn)單直接
  的方法是將明文分成多個(gè)大小為n的塊，對(duì)每個(gè)塊調(diào)用上述加密步驟，那么就得到形如下的密文塊序列
       
  密文塊序列從Proposition 5.3.10的證明中可知是計(jì)算不可分辨的，滿足「多組消息安全性」。但對(duì)于解密
  需要存儲(chǔ)每一塊的隨機(jī)數(shù)，因此比較占空間，所以衍生出下面更高效的方案Construction 5.3.12

定義
    

Berlekamp分解算法
    

AES有限域
   

  不可約性證明
       

  非本原性驗(yàn)證
      

  找出本原元
      

  不可約多項(xiàng)式個(gè)數(shù)
       

線性移位寄存器m序列
     根據(jù)參考文獻(xiàn)1知線生移位寄存器產(chǎn)生m序列的充要條件是特征多項(xiàng)式f(x)為本原多項(xiàng)式。而確立有限域上的本原多項(xiàng)式，主要有兩種方法：
      一種方法是根據(jù)F_q上所有次數(shù)為n的本原多項(xiàng)式的乘積正好等于割圓多項(xiàng)式Q_e，其中e=qⁿ-1，從而所有次數(shù)為n的本原多項(xiàng)式可以通過(guò)分解Q_e得到。
      另一種方法是通過(guò)構(gòu)造本原元再求本原元的極小多項(xiàng)式，先素因子分解qⁿ-1=p₁p₂...p_k，如果對(duì)每一p_i都有ord(α_i)=p_i，那么α=α₁α₂...α_k的階就是qⁿ-1，
      因此是F_q上的本原元，則f(x)=(x-α)(x-α²)...(x-α^r)，r=qⁿ-1（因?yàn)?span style="color: #4b4b4b; font-family: Verdana, Geneva, Arial, Helvetica, sans-serif; font-size: 13px; background-color: #ffffff;">α是本原元，所以n是使α^{q^n}=α成立的最小正整數(shù)）。
   
    求解本原多項(xiàng)式
       假設(shè)線性移位寄存器的級(jí)數(shù)為4，這里使用上述二種方法求F₁₆上的本原多項(xiàng)式，過(guò)程如下
       分解割圓多項(xiàng)式法
          

        
         
   
  本原多項(xiàng)式個(gè)數(shù)
        

   m序列示例
       


【適用前提】大整數(shù)N=pq的素因子p<q<2p，解密指數(shù)d<(1/3)N^1/4

【攻擊方法】 
     1）用歐幾里得算法計(jì)算e/N的各個(gè)漸近分?jǐn)?shù)k_i/d_i，i>=1，直至d_i>=(1/3)N^1/4，記錄此時(shí)的i為m。令i=1  
     2）計(jì)算T=(e*d_i-1)/k_i，若T不為整數(shù)則轉(zhuǎn)到4），否則轉(zhuǎn)到3）  
     3）解方程f(x)=x²-(N-T+1)x+N=0的根，如果有正整數(shù)根且兩個(gè)根皆小于N，則輸出p、q，并返回成功。否則轉(zhuǎn)到4）  
     4）遞增i，若i<m則轉(zhuǎn)回2），否則返回失敗
   該方法即Wiener算法用到了關(guān)于連分?jǐn)?shù)的一個(gè)定理：若α為任一實(shí)數(shù)，有理數(shù)p/q適合|α-(p/q)|<1/(2q²)，則p/q必為α的某一漸近分?jǐn)?shù)。證明詳見參考文獻(xiàn)[2]。
   由定理可知攻擊方法是可行的，必能找到使f(x)=0有合理解的某漸近分?jǐn)?shù)。下面證明：攻擊迭代次數(shù)的上界為

【證明】
     


【例子】N = 9449868410449，e = 6792605526025，d<(1/3)N^1/4≈584，試分解N
     

參考文獻(xiàn)
     [1] 公鑰密碼學(xué)的數(shù)學(xué)基礎(chǔ)  王小云、王明強(qiáng)、孟憲萌
     [2] 算法數(shù)論                   裴定一、祝躍飛 群結(jié)構(gòu)  
  定理1：若G為一個(gè)循環(huán)群，則G內(nèi)每個(gè)滿足ord(α)=s的元素α都是擁有s個(gè)元素的循環(huán)子群的生成元
  證明：
      

  定理2：若G為一個(gè)階為n的有限循環(huán)群，g為對(duì)應(yīng)的生成元，則對(duì)整除n的每個(gè)整數(shù)k，G都存在一個(gè)唯一的階為k的循環(huán)子群H。
    這個(gè)子群是由g^n/k生成的。H是由G內(nèi)滿足條件α^k=1的元素組成的，且G不存在其它子群
  證明：
     

  推論：從上述兩定理可知有限循環(huán)群、子群及生成元的關(guān)系如下
      
  例子：依據(jù)上述推論得如下
      

生成元判定算法
  輸入：循環(huán)群G、某子群的階k  
    1）若k=1，則直接輸出e。否則轉(zhuǎn)到2）
    2）隨機(jī)從G-{e}中選擇一元素x
    3）若x^k≠e，則轉(zhuǎn)回2）。否則若k為素?cái)?shù)，則跳到5）；若k為合數(shù)，則轉(zhuǎn)到4）  
    4）遍歷整除k的真因子d，若x^d=e，則轉(zhuǎn)回2）    
    5）輸出x 混合線性同余發(fā)生器（MLCG）      
      X_n ≡ αX_n-1 + c mod m    0<X₀, α, c<m，X₀為種子，n=1、2、3...

定理 如果下列3個(gè)條件都滿足，則 MLCG達(dá)到滿周期(即周期d=m)
     (1) (c, m)=1，即 c、m互素
     (2) 對(duì) m的任一素因子p，有α≡1 mod p
     (3) 如果4|m，則 α≡1 mod 4
  該定理的證明在參考文獻(xiàn)[2]中證明并用到如下兩個(gè)引理：
  引理5 設(shè)p為素?cái)?shù)，α∈Z⁺且p^α>2，如果 x=1(mod p^α)，x≠1(mod p^α+1)；則x^p=1(mod p^α+1)， x^p≠1(mod p^α+2)
    該引理給出了求一個(gè)整數(shù)的階的判別方法，是理解MLCG周期等于m的充要條件之關(guān)鍵。
    本文闡述為什么p是使x^p=1(mod p^α+1)成立的最小正整數(shù)，以及一般情形m=p^w(w≥1)是使x^m=1(mod p^α+w)成立的最小正整數(shù)；為什么前提條件是p^α>2。

    ◆ 先論證不存在一個(gè)整數(shù)1≤b<p使得x^b=1(mod p^α+1)成立
       
    ◆ 再證不存在一個(gè)整數(shù)1≤b<m使得x^b=1 (mod p^α+w)成立
       
     其實(shí)這里當(dāng)α=1(mod 2)且α≠1(mod 4)，結(jié)論也是成立的。比如取α=3，m=16，則 (3¹⁶ -1)=81⁴ -1=(-15)⁴ -1=-15×-7×-7 -1=-15×-15 -1=9×-7 -1=0(mod 32)，
     即(3¹⁶ -1)/(3-1)=0(mod 16)。但只有當(dāng)α=1(mod 4)時(shí)，m才是使結(jié)論成立的最小正整數(shù)。論證如下
         

參考文獻(xiàn)    
     [1] 現(xiàn)代密碼學(xué)第4版 楊波    
     [2] 混合線性同余發(fā)生器的周期分析 張廣強(qiáng)、張小彩 【定義】設(shè)整數(shù)N=P×Q，P與Q皆為素?cái)?shù)，如果P≡Q≡3 (mod4)，則N為一個(gè)Blum（布盧姆）數(shù)

【定理】設(shè)N為Blum數(shù)，N ∤ d，若同余方程x²≡d (mod N)有解，則d的平方根中有一半的Jacobi符號(hào)為1，另一半Jacobi符號(hào)為-1；且僅有一個(gè)平方根為模N的二次剩余
    證明：
    

【推論】設(shè)N為Blum數(shù)，N=P×Q，令
    
   證明：
    

【例子】由定義知N=21=3×7為Blum數(shù)，則相關(guān)乘法群、二次剩余子群、Jacobi集合如下
   


【應(yīng)用一】Blum-Goldwasser公鑰加密
      
    解密正確性是因?yàn)椴襟E1用到了歐拉定理及求平方根的如下算法，步驟2用到了中國(guó)剩余定理

       
       從上可得x=s^(P+1)/4 mod P或x=P-s^(P+1)/4 mod P，因(-1)^(P-1)/2等于-1 mod P，故前者為模P的二次剩余。從加密流程可知{s₁,s₂,...,s_n+1}正是模N二次剩余類的子集。
    所以從密文中r=s_n+1求它的(p+1)/4次冪、(q+1)/4次冪，迭代n次就得到了s₁模p的解、s₁模q的解，又因p、q、n在迭代中不變，故用歐拉定理預(yù)計(jì)算d_p mod (p-1)、d_q mod (q-1)。
    另一種（不太高效而直接的）解密如下
       
    另加密與明文異或的那部分實(shí)際是偽隨機(jī)比特發(fā)生器，因?yàn)槠椒侥構(gòu)成二次剩余類上的單向陷門置換，其最低有效位是核心斷言，故從s_i+1求出lsb(s_i)是不可行的。簡(jiǎn)單證明如下
       
      由于均勻選擇一個(gè)種子s₀，所以為概率加密，進(jìn)而由可證明安全定理（每個(gè)概率公鑰加密都是多項(xiàng)式安全的，及每個(gè)多項(xiàng)式安全的公鑰加密都是語(yǔ)義安全的）知滿足IND-CPA安全性
    易知IND-CCA2安全性是不滿足的，因?yàn)閿呈挚捎萌缦鹿舴椒ǐ@取明文：已知目標(biāo)密文C=(r, m⊕σ₁σ₂⋯σ_n)，構(gòu)造新密文C’=(r, m’⊕m⊕σ₁σ₂⋯σ_n)，將C’發(fā)給解密預(yù)言機(jī)得到m’’，則m=m’’⊕m’。
    由于加密產(chǎn)生的r與σ₁σ₂⋯σ_n都是偽隨機(jī)的，所以密文(r, x⊕σ₁σ₂⋯σ_n)的分布是偽隨機(jī)的，在目標(biāo)密文前的解密詢問(wèn)會(huì)得到若干密文與明文對(duì)，無(wú)論怎么構(gòu)造一對(duì)明文，任選其一加密得到的密文都不可區(qū)分。因此IND-CCA1安全性是滿足的

【應(yīng)用二】無(wú)爪函數(shù)/置換構(gòu)造
      
      
    如上構(gòu)造用到Blum數(shù)的上述推論，及基于大整數(shù)因子分解的困難假設(shè)。這里主要解釋下為什么由兩個(gè)Jacobi符號(hào)不同的平方根可計(jì)算大整數(shù)的素因子
      

【應(yīng)用三】偽隨機(jī)數(shù)發(fā)生器
                X_n+1=X_n² mod N      n=0、1、2...，X₀為種子
     顯然種子不為1。若為一個(gè)非二次剩余，則從X₁開始就為二次剩余子群的元素，但最后必回到X₁而非X_0；若為二次剩余，則為了安全需要考究隨機(jī)數(shù)數(shù)列的周期是否整周期（二次剩余子群的大小減1）。
  下面具體分析周期。先舉例幾個(gè)很小的Blum數(shù)
      
     從上面例子可以發(fā)現(xiàn)，由二次剩余子群構(gòu)成的隨機(jī)數(shù)數(shù)列不一定是整周期的，對(duì)于N=33無(wú)論種子怎么選，都是整周期4；對(duì)于N=57若種子選-8或7則周期為2，選其它則為6。
  現(xiàn)在一般化考慮，什么情況下才產(chǎn)生整周期？論證如下
        經(jīng)典的復(fù)雜性關(guān)系 
 P是多項(xiàng)式時(shí)間確定型圖靈機(jī)可識(shí)別的語(yǔ)言類，NP是多項(xiàng)式時(shí)間非確定型圖靈機(jī)可識(shí)別的語(yǔ)言類，NPC表示NP完全問(wèn)題類，coNP表示NP的補(bǔ)，coNPC表示NPC的補(bǔ)。確定型圖靈機(jī)是一種從不選擇移動(dòng)的特殊的非確定型圖靈機(jī)，故自然有P屬于NP

     
 
 coNP、coNPC的定義之集合表述
      
 上面頂部的圖有個(gè)假設(shè)前提是：coNPC不屬于NP，即我們相信NP完全問(wèn)題的補(bǔ)都不屬于NP。但當(dāng)P=NP或NP=coNP時(shí)，可以發(fā)現(xiàn)coNPC屬于NP

 ◆ 為什么coNPC屬于coNP？
   

 ◆ 為什么NPC 不屬于coNP？
   

 ◆ 為什么P屬于coNP?
   

 ◆ 當(dāng)P=NP時(shí)，為什么NP=coNP？
   
 ◆ 當(dāng)NP=coNP時(shí)，為什么NPC=coNPC？
    

【定理】設(shè)多項(xiàng)式，其中q是某個(gè)素?cái)?shù)的方冪，F(xiàn)_q為有限域，則    

           

若是置換多項(xiàng)式，則

【證明】
         

周知內(nèi)聯(lián)是為了消除函數(shù)調(diào)用的代價(jià)，即四大指令序列：調(diào)用前序列、被調(diào)者起始序列、被調(diào)者收尾序列、返回后序列。它們通常對(duì)應(yīng)到體系結(jié)構(gòu)調(diào)用者保存/恢復(fù)寄存器集合與被調(diào)者保存/恢復(fù)寄存器集合之約束。這個(gè)本質(zhì)也是內(nèi)聯(lián)的前提。試問(wèn)如果有某體系結(jié)構(gòu)比如S，它任意深度的函數(shù)調(diào)用代價(jià)幾乎為零，那么顯然內(nèi)聯(lián)是沒(méi)意義沒(méi)必要的。但是S可能存在嗎？我認(rèn)為不太可能。因?yàn)闄C(jī)器的資源比如寄存器集數(shù)量與堆棧空間是有限的，且調(diào)用需要知曉上下文，所以不能夠支持任意深度的調(diào)用，但是可以支持有限深度比如4層調(diào)用，這4層調(diào)用代價(jià)幾乎為零，假設(shè)再來(lái)一層，那么第5層調(diào)用代價(jià)就不為零了，這時(shí)如果內(nèi)聯(lián)第5層就變成4層調(diào)用，代價(jià)又幾乎為零。綜上所述，內(nèi)聯(lián)無(wú)論在何種體系結(jié)構(gòu)，即使在一定深度內(nèi)沒(méi)意義也不會(huì)破壞性能。

體系結(jié)構(gòu)直接影響程序性能。主要體現(xiàn)在指令集、寄存器、cache三塊。它們對(duì)于編譯器實(shí)現(xiàn)代碼優(yōu)化必須都考慮，尤其cache比如內(nèi)聯(lián)優(yōu)化、循環(huán)展開、基本塊布局、函數(shù)重排，如果不是因?yàn)橛衏ache這玩意，內(nèi)聯(lián)優(yōu)化的復(fù)雜性會(huì)大為降低，因?yàn)椴挥每紤]代碼膨脹引起的副作用即cache缺失，只要評(píng)估函數(shù)的指令數(shù)與動(dòng)態(tài)執(zhí)行消耗的關(guān)系，指令數(shù)很少但執(zhí)行耗費(fèi)很多時(shí)鐘周期的，則不宜內(nèi)聯(lián)，尤其函數(shù)為非葉子結(jié)點(diǎn)；指令數(shù)很多但執(zhí)行耗費(fèi)較少的，則可僅內(nèi)聯(lián)其中的快速路徑代碼。因現(xiàn)實(shí)存在cache這玩意，就必須權(quán)衡代碼膨脹帶來(lái)的副作用，是否能接受一定的膨脹，需要精確評(píng)估，構(gòu)建函數(shù)調(diào)用頻率與其靜態(tài)調(diào)用位置的矩陣，計(jì)算收益比如平均執(zhí)行一次的耗時(shí)是否減少，若收益為正且明顯則可內(nèi)聯(lián)，否則不宜內(nèi)聯(lián)。

有些編譯器為了簡(jiǎn)單處理，不會(huì)內(nèi)聯(lián)帶靜態(tài)變量的函數(shù)哪怕指令數(shù)很少，或者內(nèi)聯(lián)不太正確比如LLVM（詳見下文）。其實(shí)單從技術(shù)上可以做到，不過(guò)要復(fù)雜些，復(fù)雜在于鏈接器的協(xié)作。為了保證函數(shù)級(jí)靜態(tài)變量的語(yǔ)義，編譯時(shí)要預(yù)留全局唯一標(biāo)志與構(gòu)造函數(shù)的占位符，在調(diào)用者體內(nèi)插入對(duì)全局唯一標(biāo)志的（位）判斷（標(biāo)志字的一位對(duì)應(yīng)一個(gè)靜態(tài)變量，表明是否已構(gòu)造或初始化賦值）、構(gòu)造函數(shù)調(diào)用/初始化賦值、置位標(biāo)志，而鏈接時(shí)要確定全局唯一標(biāo)志及構(gòu)造函數(shù)的地址。靜態(tài)變量、全局唯一標(biāo)志放于可執(zhí)行文件的數(shù)據(jù)區(qū)，全局唯一構(gòu)造/初始化及析構(gòu)函數(shù)放于代碼區(qū)，具體布局位置可以靈活，比如. data. static_obj，. text. obj. ctor/dtor。如果這種函數(shù)性能影響較大需要內(nèi)聯(lián)優(yōu)化，而編譯器不支持，有個(gè)替代的辦法是用全局變量或文件/類級(jí)別的靜態(tài)變量，輔以對(duì)應(yīng)標(biāo)志處理一次性構(gòu)造或初始化賦值（必要時(shí)將這處理封裝為一個(gè)函數(shù)以確保目標(biāo)函數(shù)被內(nèi)聯(lián)），可達(dá)到同樣效果不足之處是作用域擴(kuò)大了。

關(guān)于LLVM對(duì)于帶靜態(tài)變量的函數(shù)之內(nèi)聯(lián)的測(cè)驗(yàn)結(jié)果












談兩個(gè)問(wèn)題：高性能與安全性

先談高性能：這里指代碼實(shí)現(xiàn)層面（非數(shù)學(xué)優(yōu)化層面），使用寄存器優(yōu)化，即主密鑰/輪密鑰、敏感數(shù)據(jù)比如中間/臨時(shí)變量必須存于寄存器，明文/密文放在內(nèi)存（若有夠用的寄存器則放寄存器），主密鑰用特權(quán)寄存器（為支持長(zhǎng)期存儲(chǔ)，比如調(diào)試寄存器、MSR寄存器），輪密鑰和敏感數(shù)據(jù)用通用寄存器。那么怎么做？穩(wěn)妥快捷的方法是用匯編或內(nèi)聯(lián)匯編，手工編排寄存器即構(gòu)建密鑰與敏感數(shù)據(jù)到寄存器集合的映射，若用普通的匯編指令，則寄存器的映射比較自由；若用專用的加密指令，則映射相對(duì)受限。如果用高級(jí)語(yǔ)言比如c/c++開發(fā)，問(wèn)題在于register關(guān)鍵字非強(qiáng)制生效，即使強(qiáng)制的，編譯器優(yōu)化（比如公共子表達(dá)式消除）產(chǎn)生的中間變量及寄存器分配策略不完全可控，需要修改編譯器比如LLVM強(qiáng)制某些變量必須分配(特定的)寄存器，為通用性要從編程語(yǔ)言語(yǔ)法屬性到目標(biāo)機(jī)器代碼生成都改動(dòng)支持，這個(gè)方法實(shí)現(xiàn)成本有點(diǎn)大。下面是摘自LLVM X86RegisterInfo.td的部分寄存器
再談安全性：為保障安全就復(fù)雜了，由于密鑰及敏感數(shù)據(jù)存于寄存器，首先要防止寄存器交換/拷貝到內(nèi)存（為避免讀取內(nèi)存的冷啟動(dòng)攻擊、基于cache的側(cè)信道攻擊）的一切可能因素，比如進(jìn)程調(diào)度、由信號(hào)或異步中斷引起的處理器模式切換、系統(tǒng)休眠，如果在用戶態(tài)實(shí)現(xiàn)加解密，就避免不了被調(diào)度或切換，因?yàn)閱魏松喜豢赡苤贿\(yùn)行加解密進(jìn)程，所以得實(shí)現(xiàn)在內(nèi)核態(tài)。這樣一來(lái)就要在加解密中禁止搶占與中斷，考慮到系統(tǒng)響應(yīng)，禁止的粒度不能過(guò)大最小為一個(gè)分組，分組加解密前禁止搶占與中斷（比如調(diào)用linux內(nèi)核接口preempt_disable、local_irq_save），解除禁止（比如調(diào)用linux內(nèi)核接口preempt_enable、local_irq_restore）前必須清零寄存器。在系統(tǒng)休眠時(shí)，禁止寄存器復(fù)制到內(nèi)存，休眠恢復(fù)時(shí)在所有用戶態(tài)進(jìn)程恢復(fù)前執(zhí)行密鑰初始化，同理系統(tǒng)啟動(dòng)時(shí)的密鑰初始化也得在用戶態(tài)進(jìn)程運(yùn)行前執(zhí)行。其次要防止其它用戶態(tài)進(jìn)程/內(nèi)核線程/中斷服務(wù)程序讀寫寄存器尤其特權(quán)寄存器（為避免用戶態(tài)或內(nèi)核態(tài)rootkit），所以要修改內(nèi)核，過(guò)濾相關(guān)系統(tǒng)調(diào)用比如linux的ptrace，過(guò)濾相關(guān)內(nèi)核函數(shù)比如linux的native_set_debugreg/native_get_debugreg。對(duì)于不可屏蔽的中斷靠禁止是無(wú)效的，只能修改中斷處理程序避免寄存器中的密鑰數(shù)據(jù)被擴(kuò)散到內(nèi)存，比如在中斷處理函數(shù)入口處清零相關(guān)寄存器。綜上基于已知代碼修改的防御不能防御惡意加載/修改代碼之類的攻擊，比如動(dòng)態(tài)安裝的內(nèi)核模塊/驅(qū)動(dòng)，但可有效防御冷啟動(dòng)攻擊、只讀DMA攻擊、基于cache的側(cè)信道攻擊、用戶態(tài)權(quán)限的軟件攻擊、內(nèi)核態(tài)的僅運(yùn)行已有代碼的軟件攻擊