基本原理

再来看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
私密通用加密
语义安全性分析
抗主动攻击安全性
以上两种构造因满足
「多组消息安全性
」,故满足
CPA与
CCA1,具体的证明可参考Oded Goldreich《密码学基础》的
Proposition 5.4.12、
Proposition 5.4.18。
但不满足
CCA2,因为攻击者拿到挑战密文后,可以修改它再发出解密质疑,得到回答的明文从而异或求解
fk(
ri),最后与挑战密文异或求解挑战明文
对于通用加密构造的CCA2攻击细节如下

posted @
2024-06-29 17:00 春秋十二月 阅读(665) |
评论 (0) |
编辑 收藏
定义

Berlekamp分解算法

AES有限域

不可约性证明
非本原性验证

找出本原元

不可约多项式个数

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

m序列示例

参考文献
[1] 代数学基础与有限域 林东岱
posted @
2024-05-16 13:41 春秋十二月 阅读(960) |
评论 (0) |
编辑 收藏
【适用前提】大整数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
2-(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)N
1/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。
这个子群是由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
posted @
2024-03-20 22:49 春秋十二月 阅读(684) |
评论 (0) |
编辑 收藏
混合线性同余发生器(MLCG)
X
n ≡ αX
n-1 + c mod m 0<X
0, α, c<m,X
0为种子,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是使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)成立
◆ 为什么前提条件是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,则 (3
16 -1)=81
4 -1=(-15)
4 -1=-15×-7×-7 -1=-15×-15 -1=9×-7 -1=0(mod 32),
即(3
16 -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,若同余方程x
2≡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
1,s
2,...,s
n+1}正是模N二次剩余类的子集。
所以从密文中r=s
n+1求它的(p+1)/4次幂、(q+1)/4次幂,迭代n次就得到了s
1模p的解、s
1模q的解,又因p、q、n在迭代中不变,故用欧拉定理预计算d
p mod (p-1)、d
q mod (q-1)。
另一种(不太高效而直接的)解密如下

另加密与明文异或的那部分实际是伪随机比特发生器,因为平方模N构成二次剩余类上的单向陷门置换,其最低有效位是核心断言,故从s
i+1求出lsb(s
i)是不可行的。简单证明如下

由于均匀选择一个种子s
0,所以为概率加密,进而由可证明安全定理(每个概率公钥加密都是多项式安全的,及每个多项式安全的公钥加密都是语义安全的)知满足
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...,X
0为种子
显然种子不为1。若为一个非二次剩余,则从X
1开始就为二次剩余子群的元素,但最后必回到X
1而非X
0;若为二次剩余,则为了安全需要考究随机数数列的周期是否整周期(二次剩余子群的大小减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) |
编辑 收藏