面向SIMD指令集的SM4算法比特切片优化

SM4算法是中国自主设计的商用分组密码算法,其加解密计算性能成为影响信息系统数据机密性保障的重要因素之一.现有SM4算法优化主要面向硬件设计和软件查表等方向展开研究,分别存在依赖特定硬件环境、效率低下且易遭受侧信道攻击等问题.比特切片技术通过对输入数据重组实现了并行化高效分组密码处理,可以抵御针对缓存的侧信道攻击.然而现有切片分组密码研究对硬件平台相关性强、处理器架构支持单一,并且并行化处理流水启动较慢,面向小规模数据的加解密操作难以充分发挥单指令多数据(single instruction multiple data,SIMD)等先进指令集的优势.针对上述问题,首先提出了一种跨平台的通用切片分组密码算法模型,支持面向不同的处理器指令字长提供一致化的通用数据切片方法.在此基础上,提出了一种面向SIMD指令集的细粒度切片并行处理SM4优化算法,通过细粒度明文切片重组与线性处理优化有效缩短算法启动时间.实验结果表明,相比通用SM4算法,优化的SM4比特切片算法加密速率最高可达438.0 MBps,加密每字节所需的时钟周期最快高达7.0 CPB(cycle/B),加密性能平均提升80.4%~430.3%.

基于比特切片的高效动态可搜索加密方案

可搜索加密作为提升云存储中数据安全性的重要技术,得到学界和产业界的持续关注。动态可搜索加密方案指支持数据集合更新的可搜索加密方案。在大型数据集场景中,由于更新操作会造成大量数据的重加密及索引重构,因此更新效率低下成为制约该技术应用的关键瓶颈。文章提出了一种基于比特切片的高效动态可搜索加密方案(BSSE),该方案采用分块并行加密的思想,利用比特切片技术将每个数据块加密单元由字转置为比特,消除了加密过程中的移位操作,并通过将S盒化简为逻辑电路,提升了大数据集场景下的并行效率。实验结果表明,BSSE方案较现有方案更新速度提升59倍,有效地提升了可搜索加密方案的更新效率,具有广泛的应用前景。

TANGRAM:一个基于比特切片的适合多平台的分组密码

本文提出一族新的分组密码算法TANGRAM.TANGRAM包含三个版本:TANGRAM128/128,分组长度和密钥长度均为128比特;TANGRAM 128/256,分组长度为128比特,密钥长度为256比特;TANGRAM 256/256,分组长度和密钥长度均为256比特.TANGRAM分组密码采用SP网络,我们对其S盒的选取以及线性层移位参数的选取进行了深入研究,以使TANGRAM尽可能达到最优的安全性和实现性能的性价比.我们深入分析了TANGRAM针对差分、线性、不可能差分、积分、相关密钥等重要密码分析方法的安全性,为它预留了足够的安全冗余.得益于比特切片方法,TANGRAM在多种软件和硬件平台上都具有很好的表现,可以灵活地适用于多种应用场景.

比特切片型算法差分及线性特征的快速构造

比特切片方法由Biham等人于1997年提出,该方法可以高效提升算法的软件实现性能,后来被广泛应用于Serpent、RECTANGLE、TANGRAM等分组算法.本文针对扩散层采用简单行循环移位的RECTANGLE、TANGRAM等比特切片型分组算法,根据算法S盒的性质以及行移位参数,给出了快速判断其是否存在单轮循环差分/线性特征的方法.基于找到的单轮循环差分/线性特征,结合MILP自动化搜索技术,实现了这类算法长轮数差分/线性特征的快速构造.进一步,我们扩展寻找单轮循环特征的思想,利用MILP方法自动化搜索了不超过4轮的循环差分/线性特征,基于此可以更方便构造长轮数差分/线性特征.利用此方法,我们找到了RECTANGLE算法的14轮差分特征和13轮线性特征, TANGRAM128算法的24轮差分特征和23轮线性特征, TANGRAM 256算法的48轮差分特征和44轮线性特征.特别地,我们找到的TANGRAM 256算法的44轮线性特征是目前找到的最长轮数的线性特征.我们的方法只依赖于算法的结构特点和S盒的性质,该研究对采用这种结构的分组算法长轮数差分/线性特征的寻找和相应算法的设计都有重要意义.

基于寄存器的SM4软件优化实现方法

SM4算法的实现效率是密码算法国产化进程中亟需解决的关键问题,许多学者致力于研究如何提升SM4算法的实现速度.比特切片是目前SM4算法软件实现方法中公认速度较高的一种实现方法,它通过在一次加密运算中并行加密多组明文数据的方式,在处理大批量数据时显著提高了SM4算法的实现速度.使用该方法时,每次加密运算前需一次性将多组数据的相同位加载到CPU的寄存器中,由此会带来CPU寄存器与内存之间数据传输的时间开销.为了减小寄存器一次性加载数据的规模,本文对于比特切片方法中的数据编排方式进行了改进,使得每次CPU执行运算时只加载必要的运算数据,从而减少了内存与寄存器之间的交互操作,进一步提高了用比特切片方法实现SM4时的整体加密效率.采用改进后的比特切片方法实现了SM4算法的64组数据并行加解密,该方法的理论加解密速度可达4.1 cycles/byte,经测试在AMD Ryzen75800H平台上加密速率达到了11162Mb/s.该方法对基于比特切片方法设计的对称加密算法软件优化实现方法具有重要参考价值.

一种基于复合域的国密SM4算法快速软件实现方法

成为ISO/IEC国际标准算法后,SM4的性能受到更多关注.目前针对SM4算法实现效率提升的方法主要集中在缩短S盒的运算时间,其中采用复合域实现的方法大都基于AES算法实现的复合域,而在GF((2^(4))^(2))上鲜有针对SM4算法软件实现的复合域被提出.本文首次在GF((2^(4))^(2))上找到了一个针对SM4算法S盒软件实现的复合域,给出一种基于复合域的SM4算法快速软件实现方法,使用穷举搜索和数学分析优化了算法S盒的复合域数学构造,构建了同构映射矩阵及其最小化目标函数,仅使用175个门函数就完成了S盒运算,平均每个输出比特占用22个门函数.基于比特切片技术,利用扩展指令集AVX2实现了SM4算法256组消息的并行化加密.每字节加解密平均耗时仅6.5个时钟周期.对硬件依赖程度低,经测试在Intel i5、Intel i7和AMD R7环境下均能显著提升SM4算法的计算效率,对有相似S盒结构的密码算法快速软件实现具有重要的参考价值.

轻量级分组密码算法FBC

FBC是一族轻量级分组密码算法,主要包含FBC128-128,FBC128-256和FBC256-256三个版本,可支持128和256两种比特长度的明文分组以及128和256两种比特长度的密钥.FBC算法采用4路两重Feistel结构设计,在结构上通过增加两个异或操作的微小代价较大提高整体结构的扩散特性.非线性函数F采用切片技术,其中,S盒基于NFSR构造,其各项密码学性质达到最优,同时硬件实现代价达到最小,为最轻的S盒之一;线性变换L仅由循环移位和异或构成,具有较好的密码学特性的同时兼顾好的软硬件实现效能.在安全性方面,我们基于混合整数线性规划(MILP)寻找最少活跃S盒个数的方法对其进行差分、线性、不可能差分以及积分等方法的分析.实验结果表明,FBC可以抵抗上述各种攻击方法的攻击.FBC算法不仅具有结构简洁,轻量化,安全性高等特性,还具有灵活高效的软硬件实现方式,可以满足不同平台的应用需求.

SM4算法快速软件实现

SM4是对称分组密码国家标准.加解密计算效率是衡量算法实现性能的重要指标,而目前关于SM4软件实现方法方面的研究不多.利用比特切片技术,结合支持单指令多数据(SIMD)的AVX2指令集,本文提出了一种SM4算法的快速软件优化实现方法,使用256位的YMM寄存器实现了SM4算法的256分组数据并行加解密.首先基于已有的选择函数构造了新的选择函数,之后改进了搜索算法,基于新的选择函数和改进的搜索算法化简了S盒的逻辑表达式,将实现逻辑表达式所需的逻辑门电路数量由3000(最简与或式)降至497.在Intel Core i7-7700HQ(Kabylake)@2.80 GHz处理器上,实现速度达到了2580 Mbps,同公开文献中的最好结果1795 Mbps(Intel Core i7-5500U(Broadwell-U)@2.40 GHz)相比,实现效率提高了43%.基于比特切片技术的软件实现优化方法无需内存或高速缓存查表,因此该方法可抵抗缓存-计时侧信道攻击,从而安全性得到了提升.本文提出的优化方法具有可扩展性,不仅适用于在X86平台上借助拓展指令集AVX2实现,还可利用RISC指令集在资源受限,安全性要求高的ARM等嵌入式平台上实现.此外,新的选择函数和搜索算法具有通用性,可用于其它一般逻辑函数的化简.

基于塔域的SM4算法快速软件实现

传统上的SM4软件优化采用查表法,其性能受到cache大小制约,而且易遭到缓存-计时攻击.本文给出了面向SIMD实现的SM4的S盒优化实现,基于塔域优化技术,将SM4的8比特S盒布尔表达式结果的比特切片门复杂度从497降低到115.使用SIMD技术的AVX512指令集和比特切片技术实现512组SM4分组消息的并行加解密.基于OpenSSL开源库完成了快速SM4不同工作模式和多线程下加密的性能测速.在Intel Core i7-11800H@2.3 GHz处理器上使用本方案对SM4算法进行的软件优化实现,其ECB模式在单线程下的加密峰值速度达到了6671 Mbps.同已公开文献中的最优实现性能2580 Mbps(Intel Core i7-7700HQ@2.8 GHz)/3306 Mbps(Intel Core i7-11800H@2.3 GHz)相比,性能提升了159%/101%.

分组密码算法FESH

我们提出了一个新的分组密码算法FESH,该算法支持128比特和256比特的分组,密钥支持128,192,256,384和512比特,共6个版本.FESH算法采用替换-置换网络(SPN)结构作为算法整体结构,轮函数设计简洁.类似于AES竞赛中的Serpent算法,FESH采用比特切片方式.然而采用了更安全高效的4位S盒以及基于4分支Feistel结构的扩散层.FESH算法可以抵抗差分分析、线性分析等现有的分析并具有足够的安全冗余.FESH算法灵活性强,在软件处理平台和硬件平台上都具有较好的性能.