(五)序列密码

news/2024/4/17 11:22:13

对称加密——序列密码(流密码)

工作原理

序列密码先通过密钥产生一个伪随机序列,然后用这个伪随机序列与明文进行异或运算以产生密文序列,它和一次一密体制的加密原理相同。

相比于伪随机数发生器(PRNG),序列密码更类似于确定性随机比特发生器(DRBG)。和DRBG一样,序列密码是确定性的。这保证了使用者能够重新产生加密序列并用以解密。而PRNG可以实现加密,但无法解密,所以没有用途。

序列密码有两个输入参数:密钥和nonce(有时作为初始值,符号为IV)。密钥需要保密,通常为128比特或256比特。而nonce是公开参数,长度一般在64比特和128比特之间。但在使用时需要注意,nonce不一定是秘密的,但是对于每个密钥它应该是唯一的。

序列密码的密钥序列对密文进行异或即可解密回明文。

序列密码加密过程

上图所示的是序列密码加密过程,其中

SC代表序列密码算法,K是密钥,N是nonce,KS是密钥序列,P是明文,C是密文。

序列密码计算KS=SC(K,N),加密时计算C=P⊕KS,解密时计算P=C⊕KS。加密函数和解密函数运算是相同的,都是与密码序列进行异或运算,只是输入不同。加密函数可同时用来加密和解密。

现在通过一个秘密的密钥K和一个nonce N来对一段消息进行加密。当需要对另外一段消息进行加密时,要么更换K,要么更换N。否则,算法将产生相同的密钥序列KS,由此可以得到两组密文C1 = P1⊕KS和C2 = P2⊕KS。若已知P1,则可以得到P2 = C1⊕C2⊕P1。此时算法已被破解。

基于状态的序列密码

基于状态的序列密码有一个秘密的内部状态,它在整个密钥序列产生的过程中不断演化。这个秘密的内部状态是由密钥和nonce经过初始化得到的,序列密码则通过状态更新函数去更新状态以产生一个或多个密钥系列比特。

RC4算法就是一种基于状态的序列密码。

基于状态的序列密码

基于计数器的序列密码

基于计数器的序列密码通过密钥、nonce和计数器来产生密钥序列,基于计数器的序列密码在密钥序列生成过程中不需要记忆任何秘密状态。

Salsa 20算法就是基于计数器的序列密码。

基于计数器的序列密码

面向硬件的序列密码

密码的硬件实现是一个电子电路,它用以实现比特级别的密码算法,这个电路是专用硬件,由一系列逻辑门电路及其他线路组成,不能用于其他用途;

面向硬件的序列密码的基本机制:反馈移位寄存器

 反馈移位寄存器(FSR)

FSR包含由一些比特构成的数组以及一个更新的反馈函数(记为f)。FSR的状态存储在数组或寄存器中,每次更新就是使用反馈函数改变状态并产生一个输出比特。

FSR作工原理如下:

设FSR的初始状态是R0,它的下一个状态R1是由状态R0左移1比特后,最右侧的空位由f(R0)补充而得到的。这时,左侧移出的比特就作为FSR的输出比特。按照同样的规则,可以依次得到接下来的状态R2、R3等。也就是说,给定FSR在t时刻的状态Rt,下一时刻的状态R(t+1)为:

R(t+1) = (Rt << 1) | f(Rt)。

现在考虑4比特的FSR反馈函数f=L1⊕L2⊕L3⊕L4,(Li代表第i个比特)

设初始状态为R1 = 1100,

R2=R1<<1 | f(R1)=1100<<1 | (1⊕1⊕0⊕0)=1000,输出比特为1。

R3=R2<<1 | f(R2)=1000<<1 | (1⊕0⊕0⊕0)=0001,输出比特为1。

R4=R3<<1 | f(R3)=0001<<1 | (0⊕0⊕0⊕1)=0011,输出比特为0。

R5=R4<<1 | f(R4)=0011<<1 | (0⊕0⊕1⊕1)=0110,输出比特为0。

R6=R5<<1 | f(R5)=0110<<1 | (0⊕1⊕1⊕0)=1100,输出比特为0。

经过5次迭代R6=R1,结论是从上面R1~R5任意一个状态开始,经过5次迭代都将回到初始状态,称它们的周期为5。假设初始为1100,运行15次,输出序列为11000110001100011000

所以,FSR实质上是基于比特的寄存器。每经过一次更新,寄存器输出最左比特,同时,通过更新f函数计算新的值 赋给最右侧比特,寄存器的其他位置左移。给定初始状态,FSR的周期就是回到初始状态所需的更新次数。

线性反馈移位寄存器(LFSR)

LFSR是具有线性反馈函数的FSR,即反馈函数仅仅是状态的某些比特位相异或。

上面的4比特异或的FSR就是一个LFSR的例子。

影响LFSR的周期的关键是选取状态的哪些位置的比特相异或。记最右侧比特的位置记为1,最左侧比特的位置记为n,将位置信息转化为多项式1+X+X^2+…+X^n,其中X^i项当且仅当寄存器的第i位置的比特参与反馈函数的异或运算时出现。寄存器达到最大周期的条件是当且仅当上述形式的多项式是本原的(数学概念)。多项式具有本原性必须满足以下条件:

1.该多项式必须是不可约的,这意味着它不能被因式分解,也即不能表示为一些多项式的乘积。例如,多项式X+X^3不是不可约多项式,因为它等于(1+X)(X+X^2)。

2.该多项式必须满足其他一些数学性质(比较复杂,后面补充)。

一个n比特LFSR的最大周期是2^n−1,而不是2^n,这是因为全0状态经过寄存器更新会回到本身。因为反馈函数是若干位置的0相异或,这个反馈值为0,所以全0状态经过左移和反馈更新后仍是全0状态。

下图考虑一个4比特LFSR,反馈多项式为1+X+X^3+X^4,即位置为1、3和4的比特参与异或运算生成新的反馈比特L1。该寄存器的多项式不是本原的,它可以分解为(1+X^3)(1+X)。

它的周期没有达到最大值15。

再来考虑反馈多项式为1+X^3+X^4的情况,这是本原多项式,该寄存器周期达到最大值15。

不过,在序列密码中使用LFSR并不安全。若一个LFSR的长度为n,攻击者仅仅需要n比特输出就可以还原该寄存器的初始状态,这样就可以反推之前的状态信息并得到之后的输出序列。这个攻击基于Berlekamp-Massey算法(简称为BM算法)。攻击者甚至不需要提前知道寄存器的长度n,可以用BM算法穷举所有可能的长度来实施攻击。

提高LFSR的安全性

为了掩盖LFSR的线性性质,可以对LFSR的输出序列进行非线性过滤以得到非线性程度更高的密钥序列,这被称为过滤生成器

下图所示的函数g必须是非线性函数——变量相异或 进行 逻辑与 及逻辑或操作。例如,L1×L2+L3×L4(多项式为1+XX^2+X^3X^4)是一个非线性函数(×是逻辑与,+是逻辑或)

即便如此,LFSR也仍然会被更复杂的数学计算攻破。

非线性反馈移位寄存器(NFSR)

非线性反馈移位寄存器(NFSR)和LFSR类似,不过NFSR的反馈函数使用非线性函数。这说明,寄存器反馈函数中会进行异或、逻辑与和逻辑或等运算。

设一个4比特的NFSR初始状态R0=(N1,N2,N3,N4),反馈函数f=(N1+N2+N1×N2+N3×N4);

R1=R0<<1 | (N1 + N2 + N1×N2 + N3×N4)=(N1+N2+N1×N2+N3×N4,N1,N2,N3);

R2=R1<<1 | ((N1+N2+N1×N2+N3×N4)+N1+(N1+N2+N1×N2+N3×N4)×N1+N2×N3)

=((N1+N2+N1×N2+N3×N4)+N1+(N1+N2+N1×N2+N3×N4)×N1+N2×N3,N1+N2+N1×N2+N3×N4,N1,N2)

从上面可以看出,通过非线性反馈函数的迭代能够指数级增加方程的规模。

不过,目前还没有有效的方法给出给定NFSR的周期,或者判断它的周期是否达到最大,对一个n比特的NFSR,几乎需要做2^n次试验才能验证它的周期是否最大。

Grain-128a算法

Grain算法是面向硬件实现的算法之一,Grain-128a算法是Grain算法的一个升级版本。

它包括一个128比特的LFSR、一个128比特的NFSR和一个过滤函数h。该LFSR周期达到最大,即2^128−1,而这种LFSR到NFSR的串联结构保证了输出序列的周期至少是2^128−1。同时,NFSR和非线性过滤函数h也增加了密码强度。

Grain-128a算法使用128比特密钥和96比特的nonce。

首先,将128比特密钥填充至NFSR的128比特寄存器中,将96比特的nonce填充至LFSR的前96比特中,LFSR的中间31比特填1,最右比特填0。

接下来的初始化阶段,系统将运行256次后输出第一个密钥比特。在初始化阶段,经非线性过滤函数h作用后得到的比特并不输出,而是反馈到LFSR,用来保证寄存器的状态既依赖密钥也依赖nonce。

LFSR的反馈函数是:f(L) = L32+L47+L58+L90+L121+L128,这个反馈函数是本原多项式。

NFSR的反馈函数是:g(N) = N32+N37+N72+N102+N128

+N44×N60+N61×N125+N63×N67+N69×N101+N80×N88+N110×N111+N115×N117

+N46×N50×N58+N103×N104×N106+N33×N35×N36×N40。

这个函数经过精心挑选以同时兼顾其密码性质和实现效率。它的代数次数是4,变量的最多的项有4个变量(N33×N35×N36×N40)。

过滤函数h也是一个非线性函数;它挑选了NFSR的9个比特和LFSR的7个比特作为输入。

Grain-128a算法通常被用于某些低端嵌入式系统。

Grain-128a工作原理图

A5/1算法(已被攻破)

之前A5/1算法是2G移动通信标准,用于对语音通信进行加密,但现在已被破解。

A5/1算法由三个LFSR组成,三个LFSR的长度分别为19、22和23,寄存器的反馈多项式分别为:

1+X^14+X^17+X^18+X^19

1+X^21+X^22

1++X^8+X^21+X^22+X^23

A5/1算法原理图

 A5/1算法中使用的三个LFSR并非每一时刻都输出,而是通过下面的钟控规则来决定每个寄存器的停走。(由于线性性质决定,如果同步输出就不安全了)

1.分别选取第一个寄存器的第9位置的比特、第二个寄存器的第11位置的比特和第三个寄存器的第11位置的比特作为钟控比特。在上述三个比特位中,或者三个取值都相同,或者有两个取值相同。

2.钟控比特按择多原则取值0或1。当钟控比特与择多函数值一致时寄存器前进一拍,否则寄存器保持当前状态不动。由择多原则可知每次有2个或3个寄存器前进。

针对A5/1算法的攻击主要有以下两类。

细致攻击:挖掘算法内部的线性性质并利用它相对简单的钟控系统。这里采用了猜测确定攻击(穷举),即攻击者猜测一些内部状态比特以确定其他状态比特的攻击方法。

野蛮攻击:只利用A5/1算法的短密钥和帧数变换的可逆性。时间内存折中(TMTO)攻击是针对A5/1算法的野蛮攻击。该攻击不关心A5/1算法的内部状态,只关心它的内部状态是64比特长。TMTO攻击将A5/1算法当作一个64比特输入(内部状态)到64比特(前64比特密钥序列)输出的黑盒。

面向软件的序列密码

软件序列密码并不是基于比特运算的,而是基于字节或32/64比特字运算的。在现代CPU中,基于字和基于比特的算术运算操作所花费的时间成本相当,因此软件序列密码的实现效率更高。相对于硬件序列密码,软件序列密码更适合在个人计算机中运行的服务器或浏览器。在那里,软件序列密码被强大的通用处理器作为本地软件来运行。

最流行的序列密码之一实际上是基于分组密码的计数模式(CTR)的AES算法。

此外还有RC4,Salsa20。

RC4 (已被攻破)

RC4由RSA安全公司的Ron Rivest设计,应用广泛,著名的应用有:第一代WiFi加密标准无线等效协议(WEP,已被攻破)以及用于建立HTTPS连接的传输层安全性(TLS)协议。

RC4的内部状态是一个256字节的数组,记为S,初始赋值S[0]=0,S[1]=1,S[2]=2,…,S[255]=255,然后n字节的密钥K通过密钥编排方案(KSA)进行初始化。一旦KSA结束,数组S的所有字节的值域仍然是0~255,但是顺序看起来很随机。

给定初始状态S,RC4产生一个和明文P等长的密钥序列KS,以便计算密文C=P⊕KS

设明文P的长度为m字节,秘钥序列KS由如下python代码得到:

i = 0
j = 0
# 明文长度为m字节
for b in range(m):i = (i + 1) % 256j = (j + S[i]) % 256# 交换两个位置的值S[i], S[j] = S[j], S[i]KS[b]=S[(S[i] + S[j]) % 256]

RC4的秘钥编排方案 

# RC4的KSA秘钥编排方案
j = 0
# 设置256大小的S数组
S = range(256)
# 遍历S数组
for i in range(256):# 计算vj = (j + S[i] + K[i%n]) % 256# 交换S[i]和S[j]S[i], S[j] = S[j], S[i]

Salsa20 

Salsa20是一个基于计数器的序列密码算法,由著名的密码学家Daniel J.Bernstein设计。通过重复对每一个分组加入新的计数来生成它的密钥序列,它的实现非常简单和快速。

Salsa20核心算法使用密钥(K)、nonce(N)和计数器的数值(Ctr)来变换一个512比特的分组。

Salsa20原理图

Salsa20的核心置换使用了一个名为Quarter-Round(QR)的函数,该函数对4个32比特字(a、b、c和d)进行变换(从上到下计算):

b = b[(a + d) <<< 7]

c = c[(b + a) <<< 9]

d = d[(c + b) <<< 13]

a = a[(d + c) <<< 18]

操作<<<是基于字的指定位数的左循环移位,该位数可以是1到31之间的任何值(32比特字),例如:0x01234567 <<< 8 = 0x23456701。

Salsa20的核心置换针对512比特的内部状态,在变换时将这512比特的内部状态视为4×4的32比特字的阵列。

下图表示salsa20使用256比特的密钥(8个比特字,k0~k7)、64比特的nonce(2个比特字,v0~v1)、64比特的计数器(2个比特字,t0~t1)和128比特的常数字(4个比特字,c0~c3)填充的一个内部状态。常数对于每次加密/解密和所有分组都是唯一的。

Salsa20首先对4列分别独立地进行QR变换(称为列轮),然后对4行做变换(称为行轮)。序列的列轮/行轮被称为双轮。Salsa20共进行10次双轮,也就是共20轮,这也是Salsa20里有个20的原因。

变换4列:

QR(x0,x4,x8,x12)

QR(x1,x5,x9,x13)

QR(x2,x6,x10,x14)

QR(x3,x7,x11,x15)

每一列都是从上到下取值

变换4行:

QR(x0,x1,x2,x3)

QR(x5,x6,x7,x4)

QR(x10,x11,x8,x9)

QR(x15,x15,x13,x14)

第i行取第i个作为第一个元素。

 salsa20的安全性

下图是密钥全是0比特和nonce全是1比特的salsa20的状态,左边和右边只有一个比特不同(黑体部分)。

对左右两组进行差分密码分析(两组做XOR运算)

第一轮之后

 第二轮之后

第三轮之后

 

 第四轮之后

可以看出差分会慢慢完全扩散到512比特的绝大多数中。由于变换函数是异或、加法和乘法的混合,使得状态通过高度的非线性方程得以不断进化更新,使得未来的差分难以预测。


http://www.ppmy.cn/news/865303.html

相关文章

从FPGA说起的深度学习(七)-循环并行化

这是新的系列教程&#xff0c;在本教程中&#xff0c;我们将介绍使用 FPGA 实现深度学习的技术&#xff0c;深度学习是近年来人工智能领域的热门话题。 在本教程中&#xff0c;旨在加深对深度学习和 FPGA 的理解。 用 C/C 编写深度学习推理代码高级综合 (HLS) 将 C/C 代码转换为…

EPSON打印机使用C#自动打印 记录!

EPSON打印机使用C#自动打印 记录&#xff01; 1.安装nuget包 &#xff1a;ESC-POS-USB-NET** 2.windows上查找打印机名称 3.输出测试** Demo&#xff1a; private void button1_Click(object sender, EventArgs e) { Printer printer new Printer(“EPSON TM-L90 Label”); …

Python每日一学 01——输入输出

Python每日一学 01——输入输出 文章目录 Python每日一学 01——输入输出一、前言二、输出函数三、输出格式1、格式化字符串字面值2、str.format() 方法3、字符串拼接的方法 四、输入函数 一、前言 本专栏准备进行长期的Python训练&#xff0c;也正好最近为马上的期末考试而复…

R语言:企业风险分析(3)【蒙特卡罗模拟的可视化,敏感性分析】

简介&#xff1a; 蒙特卡罗方法&#xff08;蒙特卡罗实验&#xff09;是一类广泛的计算方法&#xff0c;它依赖于重复随机抽样来获得数值结果。基本概念是使用随机性来解决原则上可能是确定性的问题。Monte Carlo 方法主要用于三个问题类别&#xff1a;优化、数值积分和从概率…

初探基因组组装——生信原理第四次实验报告

初探基因组组装——生信原理第四次实验报告 文章目录 初探基因组组装——生信原理第四次实验报告实验目的实验内容实验题目第一题题目用SOAPdenovo 进行基因组组装评估组装质量 第二题题目Canu组装Hifiasm组装基于nucmer的基因组比对过滤比对结果转换为可读性强的tab键分隔的文…

tensorflow实现图像增强:Flip and Rotation

#tf.image.rot90()与tf.image.flip_up_down()增加原始数据到8倍 #python 3.6 import matplotlib.pyplot as plt import tensorflow as tfimage_raw_data tf.io.gfile.GFile(r./data/IMG/TaylorSwift.jpg,rb).read()with tf.compat.v1.Session() as sess:img_data tf.image.…

Qt| There‘s no Qtversion assigned to project... 解决方法

问题&#xff1a; 原因&#xff1a;相同工程在不同电脑下qt配置不一致导致&#xff0c;该项目qt setting设置有误。 解决方法&#xff1a;右键项目打开属性 找到Qt Project Settings->Qt Installation&#xff0c;切换到当前电脑所使用的qt版本即可。

7月14日每日两题

第一题:找到最大岛 小哼通过秘密方法得到一张不完整的钓鱼岛航拍地图。钓鱼岛由一个主岛和一些附属岛屿组成,小哼决定去钓鱼岛探险。下面这个10*10的二维矩阵就是钓鱼岛的航拍地图。图中数字表示海拔,0表示海洋,1~9都表示陆地。现在需要计算出最大岛的面积(即有多少个格子…

潮人专属好物!HCK哈士奇x可口可乐联名限量款小冰吧

工业革命之后&#xff0c;人们就进入了大工厂时代&#xff0c;越来越多的东西走上了流水线&#xff0c;千篇一律、毫无新意的东西正在抹杀人们的想象力和审美体验&#xff0c;于是人们对这样的东西越来越拒绝。冰箱也如此&#xff0c;人们看遍了方方正正的白色抑或灰色的“大铁…

虚拟人春节搞事情!先在央视《对话》,又跟李玉刚组团除夕出道

金磊 发自 凹非寺量子位 | 公众号 QbitAI 一个女孩登上了央视《对话》栏目&#xff0c;仅是浅唱了一首歌&#xff0c;便让全场惊叹连连。 讲真&#xff0c;这种reaction还真没有一点夸张。 话不多说&#xff0c;先来感受下这个feel&#xff1a; 或许你会问了&#xff0c;人美歌…

itchat微信助手,kaggle 电影数据集分析,基于内容的电影推荐

项目的github地址&#xff1a;https://github.com/qihe777/itchatApplication 1.项目运行 配置完成环境后&#xff1a;&#xff08;关于调用的服务接口所需要的秘钥我都没有修改&#xff0c;但为了你程序能一直运行最好自己申请相应的服务&#xff09; 运行项目&#xff1a;…

中国首个虚拟学生入学清华大学!双商在线、颜值出众,你想跟她做同学吗?

点击上方“视学算法”&#xff0c;选择加"星标"或“置顶” 重磅干货&#xff0c;第一时间送达 来源&#xff1a;学校共青团、中国新闻网、新浪财经、科技日报、江苏共青团等 6月1日&#xff0c;清华大学迎来一位特殊的学生&#xff0c;名为华智冰&#xff0c;她是一位…

小冰公司CEO李笛:AI不会江郎才尽,创造力只会持续向上攀升丨MEET2022

编辑部 整理自 MEET 2022量子位 报道 | 公众号 QbitAI 从GPT-3到DALLE&#xff0c;AI在创作这件事上的进步速度&#xff0c;远超我们想象。 但有不少观点认为&#xff0c;相比围棋、电子游戏等知识领域&#xff0c;AI在创作上不仅比不过人类&#xff0c;甚至不具备真正的创造力…

【UE4 塔防游戏系列】01-前期准备

UE版本&#xff1a;4.24.3 课程视频链接&#xff1a;【虚幻4】UE4初学者进阶进阶教程&#xff08;合集&#xff09;-制作一个塔防游戏 1-8P&#xff08;全&#xff09;游戏单机游戏 步骤 1. 新建一个空白模板工程 2. 下载游戏资源 百度网盘 请输入提取码 提取码&#xf…

清华大学迎来中国首个原创虚拟学生华智冰:智商、情商双高,颜值出众

2021 年 6 月 1 日&#xff0c;清华大学计算机系知识工程实验室迎来了中国首个原创虚拟学生 — 华智冰&#xff0c;清华大学为她办理了学生证和邮箱。 报道称&#xff0c;华智冰智商和情商双高&#xff0c;可以作诗、作画、创作剧本杀&#xff0c;还具有一定的推理和情感交互的…

unity 通过 dll 传递字符串给python,实现小冰颜值鉴定

传入一个路径字符串&#xff08;C#&#xff09;&#xff1a; public void PassXiaoIce() {try{string img_path "D:\XLS_AI_PRO\FaceTest\photo\11.jpg";Debug.Log(img_path.Length);string str GetIceJson(img_path,img_path.Length);Debug.Log("result_str…

php 颜值测试源码,微软小冰颜值测试PHP最新代码

/** * 微软小冰颜值测试 */ class IceFace { // 颜值测试首页 protected $page http://kan.msxiaobing.com/ImageGame/Portal?taskyanzhi; // 颜值测试接口 protected $api http://kan.msxiaobing.com/Api/ImageAnalyze/Process?serviceyanzhi; // 上传图片接口 protected …

小冰 · 颜值鉴定

标题 请求地址请求方式请求参数请求示例返回说明①.响应数据②.响应示例 请求地址 http://www.dreamling.xyz/API/QQ/facevalue_identification/api.php 请求方式 get/post 请求参数 参数说明必填可能的值imgurl图片链接truetype输出格式/text/json 请求示例 http://www.drea…

C++ 删除文件夹下所有内容

介绍一种删除文件夹下所有内容的实现方式&#xff08;包括删除该文件夹&#xff09;。 注&#xff1a;该文件夹下面&#xff0c;无论嵌套多少层文件夹或文件数据&#xff0c;都可以删掉 直接上代码&#xff1a; Tip&#xff1a; ①以*.*方式查找所有类型文件 ①do while方式进行…

数据结构(王道)——顺序表的定义

线性表和顺序表的关系&#xff1a; 两种实现方式&#xff1a;静态分配、动态分配 总结&#xff1a;
最新文章