群結構  
  定理1：若G為一個循環群，則G內每個滿足ord(α)=s的元素α都是擁有s個元素的循環子群的生成元
  證明：
      

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

  推論：從上述兩定理可知有限循環群、子群及生成元的關系如下
      
  例子：依據上述推論得如下
      

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

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

    ◆ 先論證不存在一個整數1≤b<p使得x^b=1(mod p^α+1)成立
       
    ◆ 再證不存在一個整數1≤b<m使得x^b=1 (mod p^α+w)成立
       
     其實這里當α=1(mod 2)且α≠1(mod 4)，結論也是成立的。比如取α=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)。但只有當α=1(mod 4)時，m才是使結論成立的最小正整數。論證如下
         

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

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

【推論】設N為Blum數，N=P×Q，令
    
   證明：
    

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


【應用一】Blum-Goldwasser公鑰加密
      
    解密正確性是因為步驟1用到了歐拉定理及求平方根的如下算法，步驟2用到了中國剩余定理

       
       從上可得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在迭代中不變，故用歐拉定理預計算d_p mod (p-1)、d_q mod (q-1)。
    另一種（不太高效而直接的）解密如下
       
    另加密與明文異或的那部分實際是偽隨機比特發生器，因為平方模N構成二次剩余類上的單向陷門置換，其最低有效位是核心斷言，故從s_i+1求出lsb(s_i)是不可行的。簡單證明如下
       
      由于均勻選擇一個種子s₀，所以為概率加密，進而由可證明安全定理（每個概率公鑰加密都是多項式安全的，及每個多項式安全的公鑰加密都是語義安全的）知滿足IND-CPA安全性
    易知IND-CCA2安全性是不滿足的，因為敵手可用如下攻擊方法獲取明文：已知目標密文C=(r, m⊕σ₁σ₂⋯σ_n)，構造新密文C’=(r, m’⊕m⊕σ₁σ₂⋯σ_n)，將C’發給解密預言機得到m’’，則m=m’’⊕m’。
    由于加密產生的r與σ₁σ₂⋯σ_n都是偽隨機的，所以密文(r, x⊕σ₁σ₂⋯σ_n)的分布是偽隨機的，在目標密文前的解密詢問會得到若干密文與明文對，無論怎么構造一對明文，任選其一加密得到的密文都不可區分。因此IND-CCA1安全性是滿足的

【應用二】無爪函數/置換構造
      
      
    如上構造用到Blum數的上述推論，及基于大整數因子分解的困難假設。這里主要解釋下為什么由兩個Jacobi符號不同的平方根可計算大整數的素因子
      

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

     
 
 coNP、coNPC的定義之集合表述
      
 上面頂部的圖有個假設前提是：coNPC不屬于NP，即我們相信NP完全問題的補都不屬于NP。但當P=NP或NP=coNP時，可以發現coNPC屬于NP

 ◆ 為什么coNPC屬于coNP？
   

 ◆ 為什么NPC 不屬于coNP？
   

 ◆ 為什么P屬于coNP?
   

 ◆ 當P=NP時，為什么NP=coNP？
   
 ◆ 當NP=coNP時，為什么NPC=coNPC？
    

【定理】設多項式，其中q是某個素數的方冪，F_q為有限域，則    

           

若是置換多項式，則

【證明】
         

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

體系結構直接影響程序性能。主要體現在指令集、寄存器、cache三塊。它們對于編譯器實現代碼優化必須都考慮，尤其cache比如內聯優化、循環展開、基本塊布局、函數重排，如果不是因為有cache這玩意，內聯優化的復雜性會大為降低，因為不用考慮代碼膨脹引起的副作用即cache缺失，只要評估函數的指令數與動態執行消耗的關系，指令數很少但執行耗費很多時鐘周期的，則不宜內聯，尤其函數為非葉子結點；指令數很多但執行耗費較少的，則可僅內聯其中的快速路徑代碼。因現實存在cache這玩意，就必須權衡代碼膨脹帶來的副作用，是否能接受一定的膨脹，需要精確評估，構建函數調用頻率與其靜態調用位置的矩陣，計算收益比如平均執行一次的耗時是否減少，若收益為正且明顯則可內聯，否則不宜內聯。

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

關于LLVM對于帶靜態變量的函數之內聯的測驗結果












談兩個問題：高性能與安全性

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

---

---

---

---