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

【攻击方法】 
     1）用欧几里得算法计算e/N的各个渐近分数k_i/d_i，i>=1，直至d_i>=(1/3)N^1/4，记录此时的i为m。令i=1  
     2）计算T=(e*d_i-1)/k_i，若T不为整数则转到4），否则转到3）  
     3）解方程f(x)=x²-(N-T+1)x+N=0的根，如果有正整数根且两个根皆小于N，则输出p、q，并返回成功。否则转到4）  
     4）递增i，若i<m则转回2），否则返回失败
   该方法即Wiener算法用到了关于连分数的一个定理：若α为任一实数，有理数p/q适合|α-(p/q)|<1/(2q²)，则p/q必为α的某一渐近分数。证明详见参考文献[2]。
   由定理可知攻击方法是可行的，必能找到使f(x)=0有合理解的某渐近分数。下面证明：攻击迭代次数的上界为

【证明】
     


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

参考文献
     [1] 公钥密码学的数学基础  王小云、王明强、孟宪萌
     [2] 算法数论                   裴定一、祝跃飞 群结构  
  定理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的侧信道攻击、用户态权限的软件攻击、内核态的仅运行已有代码的软件攻击

---

---

---

---