随笔-163  评论-223  文章-30  trackbacks-0
 
基本原理  
   

   再来看Terr算法用到的如下定理
     定理 (基于参考文献1改正后的描述)对每一正整数t,存在唯一确定的一组整数k和j,0<=k<j,使得t=Tj+1-k,其中T0=0,Tn=Tn-1+n-1,n>=1
    
     如果t=0,那么j在区间[0,1),故只能取0,此时k=0与条件k<j矛盾,若允许k=j,则不保证唯一,比如t=1 => j=1, k=0 或 j=2, k=2。
     所以参考文献1中原来定理的描述“对每一非负整数t”是错误的。下面列举一些实例验证j与k的唯一解
               t=1  =>  j=1, k=0
               t=2  =>  j=2, k=1
               t=3  =>  j=2, k=0
               t=4  =>  j=3, k=2
               t=5  =>  j=3, k=1
               t=6  =>  j=3, k=0
   

算法伪代码

      


例子测验
     


参考文献
   [1] 代数学基础与有限域   林东岱
posted @ 2024-08-15 22:35 春秋十二月 阅读(768) | 评论 (0)编辑 收藏
私钥分组加密  
  
  
   
上图的证明中,r(j)两两不同的概率计算是关键,下面给出详细过程
       
    另外两个分布统计的不同意味着计算可分辨(反之则计算不可分辨),亦即r(j)至少两个相同的概率。
  Construction 5.3.9一次只能加密与密钥等长的明文,如果要加密更长的明文,怎么办?一个简单直接
  的方法是将明文分成多个大小为n的块,对每个块调用上述加密步骤,那么就得到形如下的密文块序列
       
  
密文块序列从Proposition 5.3.10的证明中可知是计算不可分辨的,满足多组消息安全性。但对于解密
  需要存储每一块的随机数,因此比较占空间,所以衍生出下面更高效的方案Construction 5.3.12

私密通用加密
    
     
     语义安全性分析
    
         
          

抗主动攻击安全性
       以上两种构造因满足多组消息安全性,故满足CPACCA1,具体的证明可参考Oded Goldreich《密码学基础》的Proposition 5.4.12Proposition 5.4.18
   但不满足CCA2,因为攻击者拿到挑战密文后,可以修改它再发出解密质疑,得到回答的明文从而异或求解fk(ri),最后与挑战密文异或求解挑战明文
   对于通用加密构造的CCA2攻击细节如下
           
posted @ 2024-06-29 17:00 春秋十二月 阅读(665) | 评论 (0)编辑 收藏
定义
    

Berlekamp分解算法
    

AES有限域
   

  不可约性证明
       

  非本原性验证
      

  
找出本原元
      

  不可约多项式个数
       

线性移位寄存器m序列
     
根据参考文献1知线生移位寄存器产生m序列的充要条件是特征多项式f(x)为本原多项式。而确立有限域上的本原多项式,主要有两种方法:
      一种方法是根据Fq上所有次数为n的本原多项式的乘积正好等于割圆多项式Qe,其中e=qn-1,从而所有次数为n的本原多项式可以通过分解Qe得到。
      另一种方法是通过构造本原元再求本原元的极小多项式,先素因子分解qn-1=p1p2...pk,如果对每一pi都有ord(αi)=pi,那么α=α1α2...αk的阶就是qn-1,
      因此是Fq上的本原元,则f(x)=(x-α)(x-α2)...(x-αr),r=qn-1(因为α是本原元,所以n是使αq^n=α成立的最小正整数)。
   
    求解本原多项式
       假设线性移位寄存器的级数为4,这里使用上述二种方法求F16上的本原多项式,过程如下
       分解割圆多项式法
          

       构造极小多项式法
          
        
         
   
  本原多项式个数
        

   
m序列示例
       


参考文献
    
[1] 代数学基础与有限域    林东岱
posted @ 2024-05-16 13:41 春秋十二月 阅读(960) | 评论 (0)编辑 收藏
【适用前提】大整数N=pq的素因子p<q<2p,解密指数d<(1/3)N1/4

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

【证明】
     


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

参考文献
     [1] 公钥密码学的数学基础  王小云、王明强、孟宪萌
     [2] 算法数论                   裴定一、祝跃飞
posted @ 2024-04-04 18:19 春秋十二月 阅读(697) | 评论 (0)编辑 收藏
群结构  
  定理1
:若G为一个循环群,则G内每个满足ord(α)=s的元素α都是拥有s个元素的循环子群的生成元
  证明
      

  定理2:若G为一个阶为n的有限循环群,g为对应的生成元,则对整除n的每个整数k,G都存在一个唯一的阶为k的循环子群H。
    这个子群是由gn/k生成的。H是由G内满足条件αk=1的元素组成的,且G不存在其它子群
  证明
     

  推论:从上述两定理可知有限循环群、子群及生成元的关系如下
      
  例子:依据上述推论得如下
      

生成元判定算法
  输入:循环群G、某子群的阶k  
    1)若k=1,则直接输出e。否则转到2)
    2)随机从G-{e}中选择一元素x
    3)若xk≠e,则转回2)。否则若k为素数,则跳到5);若k为合数,则转到4)  
    4)遍历整除k的真因子d,若xd=e,则转回2)    
    5)输出x
posted @ 2024-03-20 22:49 春秋十二月 阅读(684) | 评论 (0)编辑 收藏
混合线性同余发生器(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 春秋十二月 阅读(1838) | 评论 (0)编辑 收藏
【定义】设整数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 春秋十二月 阅读(1849) | 评论 (0)编辑 收藏
经典的复杂性关系 
 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 春秋十二月 阅读(1433) | 评论 (0)编辑 收藏

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

           

是置换多项式,则


【证明】

         

posted @ 2023-12-16 21:49 春秋十二月 阅读(229) | 评论 (0)编辑 收藏
周知内联是为了消除函数调用的代价,即四大指令序列:调用前序列、被调者起始序列、被调者收尾序列、返回后序列。它们通常对应到体系结构调用者保存/恢复寄存器集合与被调者保存/恢复寄存器集合之约束。这个本质也是内联的前提。试问如果有某体系结构比如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 春秋十二月 阅读(280) | 评论 (0)编辑 收藏
仅列出标题
共17页: 1 2 3 4 5 6 7 8 9 Last