随笔-148  评论-223  文章-30  trackbacks-0
  置顶随笔
模板
    1. 空基类优化
    2. 元编程技术
        2.1. 选择API
        2.2. 计算最值
        2.3. 类型选择
    3. 封装GCC原子操作
    4. 定制类对象的内存管理

算法
    1. 排序
        1.1. 改进的快速排序
        1.2. 原位统计排序     
    2. 多叉树
        2.1. 深度优先存储
        2.2. 迭代器的设计
        2.3. 前序遍历
        2.4. 后序遍历
        2.5. 兄弟遍历
        2.6. 叶子遍历
        2.7. 深度遍历 
    3. 优先级队列
        3.1. 原理
        3.2. 内幕
        3.3. 外观
    4. RSA加解密的证明
    5. DSA数字签名的推导
    6. 基于中国剩余定理优化RSA解密推论的证明
    7. 总结AES加密涉及的数学定理
    8. 为什么素检测存在概率多项式时间算法
    9. Blum数的基本定理及应用

GUI 
    1. MFC中的WM_COMMAND传递
    2. ATL和WTL中的消息反射
    3. 工作线程与消息循环
    4. 多窗口的组合与分离
        4.1. 接口
        4.2. 实现

跨平台
    1. 用户态自旋锁
    2. 互斥锁
    3. 信号量
    4. socket管道
    5. 锁框架的设计与实现

网络
    1. 运用状态机异步接收变长包
    2. 基于OpenSSL实现的安全连接
    3. TCP/IP FAQ
        3.1. 链路层、网络层和传输层
        3.2. 插口层和应用层
    4. Linux套接字与虚拟文件系统
        4.1. 初始化和创建
        4.2. 操作和销毁
    5. Linux ICMP消息的产生与转换
    6. nginx iocp
        6.1. tcp异步连接
        6.2. udp异步接收
        6.3. scm服务控制
    7. TCP分组丢失时的状态变迁
    8. 基于ENet实现可靠UDP通信的同步模型

Shell应用
    1. 自动生成并安装服务脚本
    2. nginx升级与恢复
    3. 使用awk定位反汇编输出
    4. 自动化批量编译
posted @ 2014-04-10 16:04 春秋十二月 阅读(1830) | 评论 (0)编辑 收藏
  2024年3月12日
混合线性同余发生器(MLCG)      
      Xn ≡ αXn-1 + c mod m    0<X0, α, c<m,X0为种子,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);则xp=1(mod pα+1), xp≠1(mod pα+2)
    该引理给出了求一个整数的阶的判别方法,是理解MLCG周期等于m的充要条件之关键。
    本文阐述为什么p是使xp=1(mod pα+1)成立的最小正整数,以及一般情形m=pw(w≥1)是使xm=1(mod pα+w)成立的最小正整数;为什么前提条件是pα>2。

    ◆ 先论证不存在一个整数1≤b<p使得xb=1(mod pα+1)成立
       
    ◆ 再证不存在一个整数1≤b<m使得xb=1 (mod pα+w)成立
       
    
     ◆ 为什么前提条件是pα>2
       如果pα=2,x=1(mod 2)且x≠1(mod 22)。令x=1+2q,2 ∤ q。有x2=(1+2q)2=1+4q+4q2,注意到q是奇数,则x2=1(mod22),x2=1(mod23)。故得不到引理的结论

  引理6(改写的等价形式) 如果 α=1(mod 4),则(αm - 1)/(α - 1)=0(mod m) ,m=2w,w>1
     其实这里当α=1(mod 2)且α≠1(mod 4),结论也是成立的。比如取α=3,m=16,则 (316 -1)=814 -1=(-15)4 -1=-15×-7×-7 -1=-15×-15 -1=9×-7 -1=0(mod 32),
     即(316 -1)/(3-1)=0(mod 16)。但只有当α=1(mod 4)时,m才是使结论成立的最小正整数。论证如下
         

参考文献    
     [1] 现代密码学第4版 杨波    
     [2] 混合线性同余发生器的周期分析 张广强、张小彩
posted @ 2024-03-12 17:30 春秋十二月 阅读(106) | 评论 (0)编辑 收藏
  2024年2月25日
【定义】设整数N=P×Q,P与Q皆为素数,如果P≡Q≡3 (mod4),则N为一个Blum(布卢姆)数

【定理】设N为Blum数,N ∤ d,若同余方程x2≡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的二次剩余。从加密流程可知{s1,s2,...,sn+1}正是模N二次剩余类的子集。
    所以从密文中r=sn+1求它的(p+1)/4次幂、(q+1)/4次幂,迭代n次就得到了s1模p的解、s1模q的解,又因p、q、n在迭代中不变,故用欧拉定理预计算dp mod (p-1)、dq mod (q-1)。
    另一种(不太高效而直接的)解密如下
       
    另加密与明文异或的那部分实际是伪随机比特发生器,因为平方模N构成二次剩余类上的单向陷门置换,其最低有效位是核心断言,故从si+1求出lsb(si)是不可行的。简单证明如下
       
      由于均匀选择一个种子s0,所以为概率加密,进而由可证明安全定理(每个概率公钥加密都是多项式安全的,及每个多项式安全的公钥加密都是语义安全的)知满足IND-CPA安全性
    易知IND-CCA2安全性是不满足的,因为敌手可用如下攻击方法获取明文:已知目标密文C=(r, m⊕σ1σ2σn),构造新密文C’=(r, m’⊕m⊕σ1σ2σn),将C’发给解密预言机得到m’’,则m=m’’⊕m’
    由于加密产生的r与σ1σ2σn都是伪随机的,所以密文(r, x⊕σ1σ2σn)的分布是伪随机的,在目标密文前的解密询问会得到若干密文与明文对,无论怎么构造一对明文,任选其一加密得到的密文都不可区分。因此IND-CCA1安全性是满足的

【应用二】无爪函数/置换构造
      
      
    如上构造用到Blum数的上述推论,及基于大整数因子分解的困难假设。这里主要解释下为什么由两个Jacobi符号不同的平方根可计算大整数的素因子
      

【应用三】伪随机数发生器
                Xn+1=Xn2 mod N      n=0、1、2...,X0为种子
     显然种子不为1。若为一个非二次剩余,则从X1开始就为二次剩余子群的元素,但最后必回到X1而非X0;若为二次剩余,则为了安全需要考究随机数数列的周期是否整周期(二次剩余子群的大小减1)。
  下面具体分析周期。先举例几个很小的Blum数
      
     从上面例子可以发现,由二次剩余子群构成的随机数数列不一定是整周期的,对于N=33无论种子怎么选,都是整周期4;对于N=57若种子选-8或7则周期为2,选其它则为6。
  现在一般化考虑,什么情况下才产生整周期?论证如下
       
posted @ 2024-02-25 23:29 春秋十二月 阅读(190) | 评论 (0)编辑 收藏
  2024年2月9日
经典的复杂性关系 
 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?
    

 前文的关系演变图没考虑多项式空间问题类PS与递归问题类(因为那两个条件不会影响到它们),PS(NPS)是带多项式空间限制的确定型(非确定型)图灵机可接受的语言类,但不限制运行时间可能需超多项式或指数时间,在外围加上PS与递归语言类后如下

     

 ◆ 
为什么coNP 属于PS?
   

  用于分析加密
    无论对称还是公钥加密,统一设加密运算为E,解密为D。对于正常用户,E和D皆为DTM(确定性图灵机);对于敌手,若攻击对称加密,则E和D为NTM(非确定性图灵机),攻击公钥则解密为NTM。由于E和D输入为密钥和明文或密文,因此DTM和NTM可采用多道/多带结构。DTM代表P类计算,NTM代表NP类计算,故对于公钥加密安全保障要求P!=NP,这是一个必要条件。另根据计算理论定理,必有L(NTM)=L(DTM),但是它对应的DTM可能要多花费指数时间,这亦说明破解公钥的解密是困难的


零知识复杂性关系
  依据Oded Goldreich的《密码学基础》,关系如下

    
 
  相关原文片段引用如下
 
  BPP是可被概率多项式时间图灵机(即随机化算法)识别的语言类,IP是所有具有交互证明系统的语言构成的类,等于多项式空间语言类即前文经典复杂性关系中的PS,如下图所述
 
   SZK!=CZK是因为计算不可分辨不一定能推出统计不可分辨,BPP!=PZK之原因可理解为BPP是退化的特殊的完备交互证明系统(证明者什么都不做,仅由验证者概率性地决定是否接受或拒绝)。
 当(非均匀)单向函数存在时CZK=IP,涉及的命题与定理如下
 

  



 也就是说PS类中的每种语言都具有零知识证明系统,比如NP有如下构造
 
posted @ 2024-02-09 22:19 春秋十二月 阅读(110) | 评论 (0)编辑 收藏
  2023年12月16日

【定理】设多项式,其中q是某个素数的方幂,Fq为有限域,则    

           

是置换多项式,则


【证明】

         

posted @ 2023-12-16 21:49 春秋十二月 阅读(147) | 评论 (0)编辑 收藏
  2023年11月16日
周知内联是为了消除函数调用的代价,即四大指令序列:调用前序列、被调者起始序列、被调者收尾序列、返回后序列。它们通常对应到体系结构调用者保存/恢复寄存器集合与被调者保存/恢复寄存器集合之约束。这个本质也是内联的前提。试问如果有某体系结构比如S,它任意深度的函数调用代价几乎为零,那么显然内联是没意义没必要的。但是S可能存在吗?我认为不太可能。因为机器的资源比如寄存器集数量与堆栈空间是有限的,且调用需要知晓上下文,所以不能够支持任意深度的调用,但是可以支持有限深度比如4层调用,这4层调用代价几乎为零,假设再来一层,那么第5层调用代价就不为零了,这时如果内联第5层就变成4层调用,代价又几乎为零。综上所述,内联无论在何种体系结构,即使在一定深度内没意义也不会破坏性能。

体系结构直接影响程序性能。主要体现在指令集、寄存器、cache三块。它们对于编译器实现代码优化必须都考虑,尤其cache比如内联优化、循环展开、基本块布局、函数重排,如果不是因为有cache这玩意,内联优化的复杂性会大为降低,因为不用考虑代码膨胀引起的副作用即cache缺失,只要评估函数的指令数与动态执行消耗的关系,指令数很少但执行耗费很多时钟周期的,则不宜内联,尤其函数为非叶子结点;指令数很多但执行耗费较少的,则可仅内联其中的快速路径代码。因现实存在cache这玩意,就必须权衡代码膨胀带来的副作用,是否能接受一定的膨胀,需要精确评估,构建函数调用频率与其静态调用位置的矩阵,计算收益比如平均执行一次的耗时是否减少,若收益为正且明显则可内联,否则不宜内联。

有些编译器为了简单处理,不会内联带静态变量的函数哪怕指令数很少,或者内联不太正确比如LLVM(详见下文)。其实单从技术上可以做到,不过要复杂些,复杂在于链接器的协作。为了保证函数级静态变量的语义,编译时要预留全局唯一标志与构造函数的占位符,在调用者体内插入对全局唯一标志的(位)判断(标志字的一位对应一个静态变量,表明是否已构造或初始化赋值)、构造函数调用/初始化赋值、置位标志,而链接时要确定全局唯一标志及构造函数的地址。静态变量、全局唯一标志放于可执行文件的数据区,全局唯一构造/初始化及析构函数放于代码区,具体布局位置可以灵活,比如. data. static_obj,. text. obj. ctor/dtor。如果这种函数性能影响较大需要内联优化,而编译器不支持,有个替代的办法是用全局变量或文件/类级别的静态变量,辅以对应标志处理一次性构造或初始化赋值(必要时将这处理封装为一个函数以确保目标函数被内联),可达到同样效果不足之处是作用域扩大了。

关于LLVM对于带静态变量的函数之内联的测验结果












posted @ 2023-11-16 23:32 春秋十二月 阅读(159) | 评论 (0)编辑 收藏
  2023年11月9日
谈两个问题:高性能与安全性

先谈高性能:这里指代码实现层面(非数学优化层面),使用寄存器优化,即主密钥/轮密钥、敏感数据比如中间/临时变量必须存于寄存器,明文/密文放在内存(若有够用的寄存器则放寄存器),主密钥用特权寄存器(为支持长期存储,比如调试寄存器、MSR寄存器),轮密钥和敏感数据用通用寄存器。那么怎么做?稳妥快捷的方法是用汇编或内联汇编,手工编排寄存器即构建密钥与敏感数据到寄存器集合的映射,若用普通的汇编指令,则寄存器的映射比较自由;若用专用的加密指令,则映射相对受限。如果用高级语言比如c/c++开发,问题在于register关键字非强制生效,即使强制的,编译器优化(比如公共子表达式消除)产生的中间变量及寄存器分配策略不完全可控,需要修改编译器比如LLVM强制某些变量必须分配(特定的)寄存器,为通用性要从编程语言语法属性到目标机器代码生成都改动支持,这个方法实现成本有点大。下面是摘自LLVM X86RegisterInfo.td的部分寄存器
  1 // 32-bit registers
  2 let SubRegIndices = [sub_16bit, sub_16bit_hi], CoveredBySubRegs = 1 in {
  3 def EAX : X86Reg<"eax", 0, [AX, HAX]>, DwarfRegNum<[-2, 0, 0]>;
  4 def EDX : X86Reg<"edx", 2, [DX, HDX]>, DwarfRegNum<[-2, 2, 2]>;
  5 def ECX : X86Reg<"ecx", 1, [CX, HCX]>, DwarfRegNum<[-2, 1, 1]>;
  6 def EBX : X86Reg<"ebx", 3, [BX, HBX]>, DwarfRegNum<[-2, 3, 3]>;
  7 def ESI : X86Reg<"esi", 6, [SI, HSI]>, DwarfRegNum<[-2, 6, 6]>;
  8 def EDI : X86Reg<"edi", 7, [DI, HDI]>, DwarfRegNum<[-2, 7, 7]>;
  9 def EBP : X86Reg<"ebp", 5, [BP, HBP]>, DwarfRegNum<[-2, 4, 5]>;
 10 def ESP : X86Reg<"esp", 4, [SP, HSP]>, DwarfRegNum<[-2, 5, 4]>;
 11 def EIP : X86Reg<"eip", 0, [IP, HIP]>, DwarfRegNum<[-2, 8, 8]>;
 12 }
 13 
 14 // X86-64 only, requires REX
 15 let SubRegIndices = [sub_16bit, sub_16bit_hi], CoveredBySubRegs = 1 in {
 16 def R8D  : X86Reg<"r8d",   8, [R8W,R8WH]>;
 17 def R9D  : X86Reg<"r9d",   9, [R9W,R9WH]>;
 18 def R10D : X86Reg<"r10d", 10, [R10W,R10WH]>;
 19 def R11D : X86Reg<"r11d", 11, [R11W,R11WH]>;
 20 def R12D : X86Reg<"r12d", 12, [R12W,R12WH]>;
 21 def R13D : X86Reg<"r13d", 13, [R13W,R13WH]>;
 22 def R14D : X86Reg<"r14d", 14, [R14W,R14WH]>;
 23 def R15D : X86Reg<"r15d", 15, [R15W,R15WH]>;
 24 }
 25 
 26 // 64-bit registers, X86-64 only
 27 let SubRegIndices = [sub_32bit] in {
 28 def RAX : X86Reg<"rax", 0, [EAX]>, DwarfRegNum<[0, -2, -2]>;
 29 def RDX : X86Reg<"rdx", 2, [EDX]>, DwarfRegNum<[1, -2, -2]>;
 30 def RCX : X86Reg<"rcx", 1, [ECX]>, DwarfRegNum<[2, -2, -2]>;
 31 def RBX : X86Reg<"rbx", 3, [EBX]>, DwarfRegNum<[3, -2, -2]>;
 32 def RSI : X86Reg<"rsi", 6, [ESI]>, DwarfRegNum<[4, -2, -2]>;
 33 def RDI : X86Reg<"rdi", 7, [EDI]>, DwarfRegNum<[5, -2, -2]>;
 34 def RBP : X86Reg<"rbp", 5, [EBP]>, DwarfRegNum<[6, -2, -2]>;
 35 def RSP : X86Reg<"rsp", 4, [ESP]>, DwarfRegNum<[7, -2, -2]>;
 36 
 37 // These also require REX.
 38 def R8  : X86Reg<"r8",   8, [R8D]>,  DwarfRegNum<[ 8, -2, -2]>;
 39 def R9  : X86Reg<"r9",   9, [R9D]>,  DwarfRegNum<[ 9, -2, -2]>;
 40 def R10 : X86Reg<"r10", 10, [R10D]>, DwarfRegNum<[10, -2, -2]>;
 41 def R11 : X86Reg<"r11", 11, [R11D]>, DwarfRegNum<[11, -2, -2]>;
 42 def R12 : X86Reg<"r12", 12, [R12D]>, DwarfRegNum<[12, -2, -2]>;
 43 def R13 : X86Reg<"r13", 13, [R13D]>, DwarfRegNum<[13, -2, -2]>;
 44 def R14 : X86Reg<"r14", 14, [R14D]>, DwarfRegNum<[14, -2, -2]>;
 45 def R15 : X86Reg<"r15", 15, [R15D]>, DwarfRegNum<[15, -2, -2]>;
 46 def RIP : X86Reg<"rip",  0, [EIP]>,  DwarfRegNum<[16, -2, -2]>;
 47 }
 48 
 49 // XMM Registers, used by the various SSE instruction set extensions.
 50 def XMM0: X86Reg<"xmm0", 0>, DwarfRegNum<[17, 21, 21]>;
 51 def XMM1: X86Reg<"xmm1", 1>, DwarfRegNum<[18, 22, 22]>;
 52 def XMM2: X86Reg<"xmm2", 2>, DwarfRegNum<[19, 23, 23]>;
 53 def XMM3: X86Reg<"xmm3", 3>, DwarfRegNum<[20, 24, 24]>;
 54 def XMM4: X86Reg<"xmm4", 4>, DwarfRegNum<[21, 25, 25]>;
 55 def XMM5: X86Reg<"xmm5", 5>, DwarfRegNum<[22, 26, 26]>;
 56 def XMM6: X86Reg<"xmm6", 6>, DwarfRegNum<[23, 27, 27]>;
 57 def XMM7: X86Reg<"xmm7", 7>, DwarfRegNum<[24, 28, 28]>;
 58 
 59 // X86-64 only
 60 def XMM8:  X86Reg<"xmm8",   8>, DwarfRegNum<[25, -2, -2]>;
 61 def XMM9:  X86Reg<"xmm9",   9>, DwarfRegNum<[26, -2, -2]>;
 62 def XMM10: X86Reg<"xmm10", 10>, DwarfRegNum<[27, -2, -2]>;
 63 def XMM11: X86Reg<"xmm11", 11>, DwarfRegNum<[28, -2, -2]>;
 64 def XMM12: X86Reg<"xmm12", 12>, DwarfRegNum<[29, -2, -2]>;
 65 def XMM13: X86Reg<"xmm13", 13>, DwarfRegNum<[30, -2, -2]>;
 66 def XMM14: X86Reg<"xmm14", 14>, DwarfRegNum<[31, -2, -2]>;
 67 def XMM15: X86Reg<"xmm15", 15>, DwarfRegNum<[32, -2, -2]>;
 68 
 69 def XMM16:  X86Reg<"xmm16", 16>, DwarfRegNum<[67, -2, -2]>;
 70 def XMM17:  X86Reg<"xmm17", 17>, DwarfRegNum<[68, -2, -2]>;
 71 def XMM18:  X86Reg<"xmm18", 18>, DwarfRegNum<[69, -2, -2]>;
 72 def XMM19:  X86Reg<"xmm19", 19>, DwarfRegNum<[70, -2, -2]>;
 73 def XMM20:  X86Reg<"xmm20", 20>, DwarfRegNum<[71, -2, -2]>;
 74 def XMM21:  X86Reg<"xmm21", 21>, DwarfRegNum<[72, -2, -2]>;
 75 def XMM22:  X86Reg<"xmm22", 22>, DwarfRegNum<[73, -2, -2]>;
 76 def XMM23:  X86Reg<"xmm23", 23>, DwarfRegNum<[74, -2, -2]>;
 77 def XMM24:  X86Reg<"xmm24", 24>, DwarfRegNum<[75, -2, -2]>;
 78 def XMM25:  X86Reg<"xmm25", 25>, DwarfRegNum<[76, -2, -2]>;
 79 def XMM26:  X86Reg<"xmm26", 26>, DwarfRegNum<[77, -2, -2]>;
 80 def XMM27:  X86Reg<"xmm27", 27>, DwarfRegNum<[78, -2, -2]>;
 81 def XMM28:  X86Reg<"xmm28", 28>, DwarfRegNum<[79, -2, -2]>;
 82 def XMM29:  X86Reg<"xmm29", 29>, DwarfRegNum<[80, -2, -2]>;
 83 def XMM30:  X86Reg<"xmm30", 30>, DwarfRegNum<[81, -2, -2]>;
 84 def XMM31:  X86Reg<"xmm31", 31>, DwarfRegNum<[82, -2, -2]>;
 85 
 86 // YMM0-15 registers, used by AVX instructions and
 87 // YMM16-31 registers, used by AVX-512 instructions.
 88 let SubRegIndices = [sub_xmm] in {
 89   foreach  Index = 0-31 in {
 90     def YMM#Index : X86Reg<"ymm"#Index, Index, [!cast("XMM"#Index)]>,
 91                     DwarfRegAlias("XMM"#Index)>;
 92   }
 93 }
 94 
 95 // ZMM Registers, used by AVX-512 instructions.
 96 let SubRegIndices = [sub_ymm] in {
 97   foreach  Index = 0-31 in {
 98     def ZMM#Index : X86Reg<"zmm"#Index, Index, [!cast("YMM"#Index)]>,
 99                     DwarfRegAlias("XMM"#Index)>;
100   }
101 }
102 
103 // Debug registers
104 def DR0  : X86Reg<"dr0",   0>;
105 def DR1  : X86Reg<"dr1",   1>;
106 def DR2  : X86Reg<"dr2",   2>;
107 def DR3  : X86Reg<"dr3",   3>;
108 def DR4  : X86Reg<"dr4",   4>;
109 def DR5  : X86Reg<"dr5",   5>;
110 def DR6  : X86Reg<"dr6",   6>;
111 def DR7  : X86Reg<"dr7",   7>;
112 def DR8  : X86Reg<"dr8",   8>;
113 def DR9  : X86Reg<"dr9",   9>;
114 def DR10 : X86Reg<"dr10", 10>;
115 def DR11 : X86Reg<"dr11", 11>;
116 def DR12 : X86Reg<"dr12", 12>;
117 def DR13 : X86Reg<"dr13", 13>;
118 def DR14 : X86Reg<"dr14", 14>;
119 def DR15 : X86Reg<"dr15", 15>;
120 
121 def GR32 : RegisterClass<"X86", [i32], 32,
122                          (add EAX, ECX, EDX, ESI, EDI, EBX, EBP, ESP,
123                               R8D, R9D, R10D, R11D, R14D, R15D, R12D, R13D)>;
124 
125 // GR64 - 64-bit GPRs. This oddly includes RIP, which isn't accurate, since
126 // RIP isn't really a register and it can't be used anywhere except in an
127 // address, but it doesn't cause trouble.
128 // FIXME: it *does* cause trouble - CheckBaseRegAndIndexReg() has extra
129 // tests because of the inclusion of RIP in this register class.
130 def GR64 : RegisterClass<"X86", [i64], 64,
131                          (add RAX, RCX, RDX, RSI, RDI, R8, R9, R10, R11,
132                               RBX, R14, R15, R12, R13, RBP, RSP, RIP)>;

再谈安全性
:为保障安全就复杂了,由于密钥及敏感数据存于寄存器,首先要防止寄存器交换/拷贝到内存(为避免读取内存的冷启动攻击、基于cache的侧信道攻击)的一切可能因素,比如进程调度、由信号或异步中断引起的处理器模式切换、系统休眠,如果在用户态实现加解密,就避免不了被调度或切换,因为单核上不可能只运行加解密进程,所以得实现在内核态。这样一来就要在加解密中禁止抢占与中断,考虑到系统响应,禁止的粒度不能过大最小为一个分组,分组加解密前禁止抢占与中断(比如调用linux内核接口preempt_disablelocal_irq_save),解除禁止(比如调用linux内核接口preempt_enablelocal_irq_restore)前必须清零寄存器。在系统休眠时,禁止寄存器复制到内存,休眠恢复时在所有用户态进程恢复前执行密钥初始化,同理系统启动时的密钥初始化也得在用户态进程运行前执行。其次要防止其它用户态进程/内核线程/中断服务程序读写寄存器尤其特权寄存器(为避免用户态或内核态rootkit),所以要修改内核,过滤相关系统调用比如linux的ptrace,过滤相关内核函数比如linux的native_set_debugreg/native_get_debugreg。对于不可屏蔽的中断靠禁止是无效的,只能修改中断处理程序避免寄存器中的密钥数据被扩散到内存,比如在中断处理函数入口处清零相关寄存器。综上基于已知代码修改的防御不能防御恶意加载/修改代码之类的攻击,比如动态安装的内核模块/驱动,但可有效防御冷启动攻击、只读DMA攻击、基于cache的侧信道攻击、用户态权限的软件攻击、内核态的仅运行已有代码的软件攻击
posted @ 2023-11-09 16:39 春秋十二月 阅读(2189) | 评论 (0)编辑 收藏
  2023年10月4日
​1. 区间图:用于局部寄存器分配,基本块内的每个活跃范围看作一个区间(最早定义位置+最新使用位置),所有活跃范围构成区间图。区间图是一种不精确的冲突图(因为高估了活跃范围的范围而导致伪冲突,比如认为一个复制操作连接的或两个源相同目标不同的复制操作产生重叠的两个活跃范围冲突,但实际没有冲突),优势在于着色是P(复杂度O(|V|)或O(|E|))而非NP问题。llvm早期的线性扫描分配器是基于区间图在全局的扩展,比较适用于JIT编译(减少编译时间)
​2. 一般图:用于全局寄存器分配,是一种精确的冲突图(由一组定义与一组使用构成的网络)。优势在于努力最小化溢出活跃范围而生成高效执行的代码,但会牺牲编译时间。llvm的greedy寄存器分配是基于一般图的代表。编译器使用的冲突图可能会将机器约束条件比如多寄存器值/调用约定编码进去而存在重复边,导致不满足图论中的简单图定义,故这里采用一般图
​3. 弦图:定义详见https://oi-wiki.org/graph/chord。基于静态单赋值形式名建立的冲突图是弦图。优势在于可以做到最佳着色(复杂度O(|V|+|E|))而非启发式(基于一般图的全局寄存器分配使用启发式),利于减少寄存器压力。劣势在于必须将指派寄存器后的仍然为静态单赋值代码转换为机器码,而这种转换可能增加寄存器压力,以及插入一些可能非必要的复制操作,若复制操作实现的数据流与ssa phi函数对应,则分配器无法合并这种复制,这将破坏弦图的性质
​4. 冲突图拆分:查找其中的团分割即连通子图,移除它划分得到不相交的一些子图,这样一来,各子图可独立着色(有点类似活跃范围拆分)而利于减少寄存器压力,另外实现上还能节省下三角布尔矩阵(用于快速判断两结点是否冲突)的规模
​#############################
寄存器分配与图论的染色理论相关。其它的比如常量传播与格代数及不动点相关,循环优化与多面体、矩阵相关。这三方面是我目前看到的编译器所用数学理论
posted @ 2023-10-04 13:08 春秋十二月 阅读(2802) | 评论 (0)编辑 收藏
  2023年9月30日



posted @ 2023-09-30 08:47 春秋十二月 阅读(56) | 评论 (0)编辑 收藏
  有单向、双向、三向3种认证方式,前两者必须检查时间戳以防重放攻击,单向因为只有一个消息传递,如果仅靠一次性随机数是无法判断消息是否重放。双向有两个消息传递,一来一回,仅靠一次性随机数只能检测到发响应那方的重放。最后者则不必,可仅通过一次性随机数检测自己是否遭遇重放攻击,因为接收第二个消息的那方,通过判断第二个消息中随机数是否等于自己先前已发送第一个消息中的那个,若不等于则为重放,若等于则发第三个确认消息给对方,对方收到并判断确认消息中的随机数是否等于先前它已发送第二个消息中的随机数,若等于则说明第它收到的第一个消息的确是另一方发送的即非重放,否则为重放。因此三向认证可不必同步双方时钟。但正因为不强制检查时间戳而可能导致中间人攻击:假设通信双方为A、B,中间人为C,攻击步骤如下
 1. C与B认证时,发送先前已截获的A到B请求消息给B
 2. 截获并存储B到A的响应消息x,但不转发,开始与A认证
 3. 收到A的请求消息后,解密x取出其中的随机数Rb作为响应给A消息中的随机数,用自己私钥签署整个消息后发给A
 4. 收到并转发A的确认消息给B
以上完成后,C就能冒充A与B通信了。一种简单的改进方法是先用对方的公钥加密消息中的随机数,再用自己的私钥签署整个消息。关于网络协议的安全性分析,主流方法是形式化分析,可以借助相关工具来验证找出漏洞
posted @ 2023-09-30 08:00 春秋十二月 阅读(334) | 评论 (0)编辑 收藏
仅列出标题  下一页