一种数值型的保留格式加密算法_王浩.pdf

网址 http:/|745学 术 论 文Research PapersDOI:10.12379/j.issn.2096-1057.2023.08.05 收稿日期:2 0 2 2-0 8-1 7 基金项目:河北省自然科学基金项目(A 2 0 1 9 5 0 7 0 0 2)引用格式:王浩,张永平,李同寒,等.一种数值型的保留格式加密算法J.信息安全研究,2 0 2 3,9(8):7 4 57 5 3一种数值型的保留格式加密算法王 浩 张永平 李同寒 樊林畅(中国人民警察大学智慧警务学院 河北廊坊 0 6 5 0 9 9)(2 0 2 0 2 0 5 0 0 3c p p u.e d u.c n)AF o r m a t-p r e s e r v i n gE n c r y p t i o nA l g o r i t h mf o rN u m e r i cD a t aW a n gH a o,Z h a n gY o n g p i n g,L iT o n g h a n,a n dF a nL i n c h a n g(S c h o o l o fI n t e l l i g e n tP o l i c i n g,C h i n aP e o p l esP o l i c eU n i v e r s i t y,L a n g f a n g,H e b e i0 6 5 0 9 9)A b s t r a c t W es t u d yF P E(f o r m a t-p r e s e r v i n ge n c r y p t i o n)a n dp r o p o s ean e w n u m e r i c a lf o r m a t-p r e s e r v i n ge n c r y p t i o na l g o r i t h m,w h i c hs i g n i f i c a n t l yi m p r o v e st h ep e r f o r m a n c eo ft h ef o r m a t-p r e s e r v i n ge n c r y p t i o na l g o r i t h mb yn o tu s i n gC y c l e-W a l k i n g.T h eb l o c kl e n g t hi sd e t e r m i n e db yd e c i m a l n u m b e ro f p l a i n t e x t d i g i t s,i n c l u d i n ge v e na n do d d l e n g t h s.T h e c o r e i s t o r e a l i z e c o n f u s i o na n dd i f f u s i o nb yc o n s t r u c t i n ga d d i t i v eg r o u p s,f i n i t ef i e l d s,a n dS-b o x,a n du s ep e r m u t a t i o na l g o r i t h ma n ds k i p p i n ga l g o r i t h mt or e a l i z et h ep r e s e r v a t i o no ft h ef o r m a t.T h ek e ye x p a n s i o na l g o r i t h mo u t p u t st h eb l o c kl e n g t ho ft h ep l a i n t e x tf l e x i b l ya n du s e st h ek e yg e n e r a t o ro ft h es t r e a mc i p h e rt o g e n e r a t es u b-k e y s.A s p e c i f i ce x a m p l ei su s e dt ov e r i f yt h a tt h ep r o p o s e da l g o r i t h mc a nc o r r e c t l yi m p l e m e n tf o r m a t-p r e s e r v i n ge n c r y p t i o n,a n dd i f f e r e n ta l g e b r a i cg r o u po p e r a t i o n sa n dn o n l i n e a rt r a n s f o r m a t i o no fS-b o xi n c r e a s et h es e c u r i t yo ft h ea l g o r i t h m.S e c u r i t ya n a l y s i s i l l u s t r a t e s t h a t t h e a l g o r i t h mc a nm e e t t h e a c t u a l s e c u r i t y r e q u i r e m e n t s.F i n a l l y,c o m p a r e dw i t ht h eF P Ea l g o r i t h ms t a n d a r d,F F X,w h i c hi sp r o p o s e db yN I S T,t h er e s u l ts h o w st h a tt h ep r o p o s e da l g o r i t h mi s a b o u t 3 0t i m e s f a s t e r t h a nF F Xf o r a1 2 8 bb l o c k(3 2d e c i m a l d i g i t s)o fF F X.K e yw o r d s f o r m a t-p r e s e r v i n ge n c r y p t i o n;n u m e r i c t y p e;d i f f e r e n t a l g e b r a i cg r o u p;S-b o x;f l e x i b l eb l o c kl e n g t h摘 要 对保留格式加密(f o r m a t-p r e s e r v i n ge n c r y p t i o n,F P E)进行了研究,提出一种新的数值型保留格式加密算法,未使用C y c l e-W a l k i n g,显著提高了保留格式加密算法的性能.通过明文位数确定分组长度,包括偶数长度和奇数长度,其核心思想是通过构造加法群、有限域、S盒实现混淆和扩散,利用置换算法和跳过算法实现保留格式.密钥扩展算法按照明文的分组长度弹性输出,使用流密码的密钥生成器生成子密钥.用具体实例验证了所提出的算法能正确实现保留格式加密,且不同代数群运算和S盒的非线性变换增加了算法的安全性,安全性分析表明该算法可以达到实际安全性的要求.最后,将提出的算法和N I S T提出的F P E算法标准F F X进行了比较,结果表明,对于F F X的一个1 2 8 b的分组(3 2位十进制数字),所提出的算法比F F X快约3 0倍.746|信 息 安 全 研 究Journal of Information Security Research第 9 卷 第 8 期 2023 年 8 月Vol.9 No.8 Aug.2023关键词 保留格式加密;数字型;不同代数群;S盒;弹性长度分组中图法分类号 T P 3 0 9 随着信息科技快速发展,大量数据在互联网中流通,数据泄露事件层出不穷.数据库中的数据大多是以明文形式存储,如学习通的数据库泄露事件.传统的加密方法通常会扩展数据,需要通过修改数据库结构或应用程序存储加密后的数据.保留格式加密(f o r m a t-p r e s e r v i n ge n c r y p t i o n,F P E)已形成一类新兴的加密方式,专门用于保护加密后数据与原始数据格式相同.保留格式加密系统地提出是在2 0 0 2年,B l a c k等人1在密码学领域研究出3种基本的F P E构建方法:P r e f i x,C y c l e-W a l k i n g和G e n e r a l i z e d-F e i s t e l,这3种方法奠定了保留格式加密算法的基本框架.之后,F P E加密主要研究不同数据类型数据加密算法、改进已有加密算法存在的问题以及F P E的具体应用场景.解决整数域的F P E算法主要有F F S E M2和基于T y p e-2F e i s t e l网络的整数F P E3,S M 4-F P E4;解决字符域的F P E算法主要有F F X5、B P S6、变长字符加密7等;解决任意正则语言的有C t E8和R t E9;解决数据库中日期类型数据的有基于随机基准值的加密方案1 0;解决中文域的F P E算法通过建立姓名域与整数域的双射,再利用改进的C y c l e-P r e f i x方法进行加密的方案1 1,还有使用C t E将中文编码为整数之后,再使用现有的整数F P E加密算法1 2.这些F P E算法都是基于基础分组密码设计的.现在的研究趋向于把复杂域的问题转换为简单域,即建立复杂型数据类型与数字型数据的双射关系,本质上这些算法都属于C t E.2 0 1 6年,F F X被N I S T收录,F F X在实际应用中比较广泛.之前提出的一些保留格式加密方案仍存在一些安全隐患,如使用相同的密钥和相同的明文总会产生相同的密文,所以近几年提出加入调整因子、基于泛化的方法使明文和密文呈现1对多的关系1 3.在应用场景方面,F P E可以用于增强数据库的安全性1 4、数据脱敏1 5、金融信息安全、数据消毒、水印技术以及物联网通信1 6等.可见,现有保留格式加密算法大多基于F e i s t e l结构,使用基础分组密码构造伪随机函数,并且使用C y c l e-W a l k i n g方法确保密文输出,执行1次保留格式加密算法需要执行多次基础分组密码算法,比基础分组密码效率低.每个F P E操作所需要的分组密码的迭代次数是不可预测的,存在不确定的 性能问题.所以本文 提出一种新 的数值 型F P E算法,通过构造多个不同的有限域使得每次运算都在数值型数据的消息空间内,从而避免使用C y c l e-W a l k i n g,效率优于F F X算法.1 算法描述数值型消息空间为=0,1,2,3,4,5,6,7,8,9,消息空间的大小为|=1 0,明文是消息空间内的元素组成的字符串,即明文只包含来自消息空间中的元素.以下的消息空间指的就是大小为1 0的数字集合.为了避免使用C y c l e-W a l k i n g,在算法中构造有限域Fpb,其中p是素数,b是整数.由于消息空间大小为1 0,故选取F3上的不可约多项式P(x)=x2+1,构造F32=ZZ3x(x2+1)=0,1,2,x,x+1,x+2,2x,2x+1,2x+2 域和F1 1域.F32一一对应F9=0,1,2,3,4,5,6,7,8 中这9个元素,F1 1=0,1,2,3,4,5,6,7,8,9,1 0,如无特殊说明,以下所说的F9都指F32=ZZ3x(x2+1).本文提出的数值型F P E算法在下文缩写为G F P E,表示基于不同代数群的保留格式加密算法.G F P E加密算法由1 0轮相同的混合变换和1个输出变换组成,是一种迭代型分组密码算法.该算法的明文长度为n,n2,初始密钥长度为1 2 8b.混合变换采用有限域和消息空间大小的群的代数运算,密钥扩展算法采用序列密码密钥生成器生成轮密钥,数据解密和数据加密的算法结构大致相同,只是轮密钥的使用顺序有所差异,部分运算使用其逆运算;最后通过一个输出变换获得密文.下面介绍加密算法、解密算法和密钥扩展算法.网址 http:/|747学 术 论 文Research Papers1.1 加密算法G F P E加密流程中主要用到3种运算和S盒非线性变换.1)模(x2+1)加运算+:a+b=(a+b)m o d(x2+1);2)模1 1乘运算:ab=(ab)m o d1 1;3)模1 0加运算:ab=(a+b)m o d1 0.F9域中的元素进行模加运算,明文中有可能出现不属于F9中的元素,为了保留格式提出置换算法(p e r m u t a t i o na l g o r i t h m,P A)和 跳 过 算 法(s k i p p i n ga l g o r i t h m,S A).F1 1域中的元素进行模乘运算,对任意1x1 0中的x模1 1乘法均有逆元,而0没有逆元,所以当输入为0时将其映射为1 0,输出为1 0时将其映射为0.通过3种不兼容的运算实现分组密码所需的混淆和扩散,首先3种运算相互之间不满足“分配律”,即a(b+c)(ab)+(ac),其中aF1 1,b,cF9.例如a=b=c=2,上述不等式左边为2,而不等式的右边分别为8.同样地,对于aF1 1,b,cZZ1 0,a(b+c)(ab)+(ac),例如a=b=c=3,上述不等式左边为7,而不等式的右边为8.其次,3种运算之间部分不满足“广义结合律”,a+(b+c)(a+b)+c,其中aF9,b,cZZ1 0,例如a=b=c=1,上述不等式左边为0,而不等式的右边分别为3.同样地,对于aF9,b,cZZ1 0,a(b+c)(ab)+c,例如a=b=c=2,上述不等式左边为8,而不等式的右边为6.1.1.1 置换算法消息空间大小为1 0,构造的有限域F9的大小为9,为了达到混淆和保证所有格式都存在的目的,在每轮轮函数的开始,根据置换密钥k0F9,使用元素9代替k0进行模加运算,即aZZ1 0.对于k09的情况,如果a和k0的值相同,则进行跳过算法,如果a=9,使用k0代替a进行模9加运算;对于k0=9的情况,如果a=9,则进行跳过算法.例如移位密钥为k0=1,则F9中的元素1不参与本轮的模F9加运算中,如果输入为1,则执行跳位算法,如果输入为9,此时使用1代替9参与F9域模加运算.通过在某一轮使用置换密钥代替不在F9有限域中的消息空间元素9,增加了混淆的不确定性,具有一定的非线性.1.1.2 跳过算法根据置换算法,在运算过程会出现置换密钥需要参与运算情况,如果使用置换密钥进行运算,则在解密时会出现1对多的现象,置换就没有意义,所以置换算法和跳过算法往往是同时出现的,两者相辅相成.每轮的输入和中间输出都可能包含不在F9域中的元素,通过置换密钥,可知每轮不参与F9域运算的元素k0,当需要参与F9域运算且遇到k0时,则不作任何运算,中间结果就是其本身,即跳过运算,中间输出为k0,等到在其他代数群中进行状态转换运算.例如k0=1,当F9域模加运算时的元素为1时,此时不加密,输出结果为1,1会在本轮之后的ZZ1 0群或者F1 1域中进行运算.在每轮使用置换算法和跳过算法,对某些状态没有进行转换,所以会泄露轮函数的某些输入状态或者中间状态,即有可能泄露明文的某些信息,可能会降低每轮算法的复杂度,但是在不知道置换密钥的情况下会增加混淆的程度,则两者是成正比的.1.1.3 S盒非线性变换S盒通过置换产生混淆的非线性变换,主要目的是在密文中制造混乱.S盒的选择对分组密码的安全性至关重要,具有高差分均匀度和非线性度是S盒安全性的2个重要目标,体现了S盒的抗差分分析攻击和抗线性分析攻击的能力.构造S盒主要有2种方法:第1种是数学构造法,使用布尔函数或者有限域中的乘法逆函数;第2种方法是随机构造法,适用于较小的格式,可以穷举所有的S盒,分析线性和差分均匀性并选择高差分均匀度和非线性度的S盒.本文使用随机构造法,在加密算法的设计中S盒不用可逆,故S盒是一个满射映射,即S:ZZ1 02ZZ1 0,S盒的大小是1 01 0的.使用09之间的置换,建立一一映射关系,这样就会有1 0!中置换的方法,对S的所有可能的映射进行了差分和线性分析,构造的S盒如图1所示,S盒的最大差分概率为2-2.4 7.1.1.4 加密流程设明文为X=x1x2xnZZn1 0,明文长度为n,根据n的奇偶性使用不同的轮函数结构.748|信 息 安 全 研 究Journal of Information Security Research第 9 卷 第 8 期 2023 年 8 月Vol.9 No.8 Aug.2023012345678904316702859139672845102164359702837098156234457348201965247501968369521648307701893657428825047396196802931475图1 S盒置换 S t e p 1.将明文数据划分为n段,即X=x1x2xn,其中xiZZ1 0.根据本轮置换密钥生成新的F9域元素F*9.S t e p 2.判断i的奇偶性:若i为偶数,进行S t e p 3中的F*9域模加运算;若i为奇数,进行域F1 1模1 1乘运算,即z1i=xiki.S t e p 3.F*9域运算中包括置换算法R A()和跳位算法S A():若xiF*9,z1i=R A(xi)+ki;若xiF*9,z1i=xi(下面关于F9域模加运算都与此步骤一样).这3步得到Z1=z1 1z1 2z1n.S t e p 4.判断n的奇偶性:若n为偶数,进行S t e p 5;若n为奇数,分组个数加1,把z1 1连接在z1n之后,即Z1=Z1z1 1=z1 1z1nz1 1,然后进行S t e p 5.S t e p 5.Z1为偶数,相邻的奇偶位两两相减,即Z2i=z1iz1(i+1),i=i+2,Z2=z2 1z2 3z2(|Z1|-1).S t e p 6.Z3i=Z2iki+n,Z3(i+1)=Z3i+Z2(i+2),进行F*9有限域运算,和S t e p 3同样的步骤,i=i+2;在最后一次中,Z2(i+2)不存在,用Z2 1代替Z2(i+2),即Z2(i+2)=Z2 1,得到Z3=z3 1z3 2z3(|Z1|).S t e p 7.Z3为偶数,两两放入S盒,奇数取S盒的行,偶数取S盒的列.即Si=S(z3i,z3(i+1),i=i+2,则S=S1S3S|Z3|-1.S t e p 8.判断n的奇偶性:若n为奇数,Z4i=Si-Si+2,i=i+2;若n为偶数,Z4i=Si.S t e p 9.S t e p 3得到的结果 加上Z4i,即yi=z1iZ4i,yi+1=z1(i+1)Z4i.S t e p 1 0.若n为奇数,最后一个yn=z1nZ4 1.得到第r轮的输出结果为Yr=y1y2yn,这也是下一轮的输入.将(Yr)按照上述定义的轮变换进行迭代1 0轮,对第1 0轮的结果作最终的输出变换.判断xi是 否 属 于 有 限 域F9,若xiF9,z1i=xi,若xiF9,判断i的奇偶性:若i为偶数,z1i=xi+ki;若i为奇数,z1i=xiki.最后,连接n个分组产生密文.1.2 解密算法本文提出的算法G F P E的解密过程和加密过程一样,不同的是轮密钥的顺序和置换密钥使用的位置.表1给出了解密密钥和加密密钥之间的关系.其中i代表第i轮运算,偶数位的K-1表示K的模(x2+1)的 加 法 逆,即K+K-10 m o d(x2+1),奇数位的K-1表示K模1 1的乘法逆,即KK-11m o d1 1.则加密密钥和解密密钥的对应关系如表1所示(以4轮为例):表1 加密轮密钥和解密轮密钥对应关系轮数i与变换加密子密钥解密子密钥移位密钥K(1)0K(2)0K(3)0K(4)0K(5)0K(5)0K(4)0K(3)0K(2)0K(1)01K(1)1K(1)2K(1)nK(1)n+1K(1)n2K(5)-11K(5)-12K(5)-1nK(4)n+1K(4)n22K(2)1K(2)2K(2)nK(2)n+1K(2)n2K(4)-11K(4)-12K(4)-1nK(3)n+1K(3)n23K(3)1K(3)2K(3)nK(3)n+1K(3)n2K(3)-11K(3)-12K(3)-1nK(2)n+1K(2)n24K(4)1K(4)2K(4)nK(4)n+1K(4)n2K(2)-11K(2)-12K(2)-1nK(1)n+1K(1)n2输出变换密钥K(5)1K(5)2K(5)nK(1)-11K(1)-12K(1)-1n 网址 http:/|749学 术 论 文Research Papers 由于置换密钥在1轮中,而输出变换中置换密钥也使用了置换密钥,所以进行解密时,置换密钥的顺序是相反的,在S t e p 4之后,使用下一轮的置换密钥,最后的输出变换使用最后一轮的置换密钥.1.3 密钥扩展算法由于密钥格式不确定,针对G F P E密码本文提出一种新的保留格式密钥扩展算法.加密算法中使用的密钥由初始密钥生成,初始密钥K的长度为1 2 8b,如果明文的长度较长,可以对明文进行分段分别加密或者使用2 5 6b的初始密钥,本文以1 2 8b的长度为例.加密过程需要用到2种密钥:移位密钥和轮密钥.移位密钥用于确定每轮的有限域中的元素,保证这一轮不在有限域中的元素会出现在下一轮中;轮密钥用于每轮轮函数的加密,轮密钥的长度需要根据明文分组的长度决定.每轮需要的加密密钥长度为明文的长度加上明文长度的一半向上取整.2类密钥的生成算法基本一致,子密钥长度不确定,使用流密码密钥生成器产生子密钥.本文通过改进S a l s a 2 0算法的密钥生成函数,生成r轮子密钥.子密钥的长度取决于明文的长度,设明文长度为n,消息空间大小为N,有限域为Fpb,加密算法的轮数位为r,初始密钥K=k0k1k1 2 7F1 2 82,密钥扩展算法以初始密钥K、轮数r和有限域大小pb作为输入,生成r+2轮子密钥,具体生成算法如下:1)将1 2 8 b初始密钥分为4组,每组3 2 b,分别为k0=K1 2 7K9 6,k1=K9 5K6 4,k2=K6 3K3 2,k3=K3 1K0.2)首先运算Ri=z1=k3(k1+k0)7),z2=(k2+z1)9)(i+1),z3=k1(k3+z2)1 3),z0=(k0+z3 1 8)(i+4),其中在密钥扩展算法中表示为二进制异或运算,+表示模23 2加运算,表示3 2 b二进制数循环左移.3)移位密钥K0=1 0r-1+(z0z1z2z3)m o d(1 0r-1 0r-1).4)加密密钥生成方式如下:迭代上述步骤生成r+1个子密钥.k0=z0,k1=z1,k2=z2,k3=z3,(z0,z1,z2,z3)=Ri(k0,k1,k2,k3).第i轮密钥为Ki=pb(n-1)+(z0z1z2z3)m o d(pb n-pb(n-1).加密的轮密钥生成后,解密的轮密钥根据表1可以求出.2 正确性验证对于G F P E加密算法的具体实例,以偶数明文长度和奇数明文长度为例,为了说明过程,设定初始密钥为K=1 2 3 4 5 6 7 8 9 0 9 8 7 6 5 4,每个十进制数转换为8b二进制数,一共1 2 8b的密钥,轮数r=4,实际应用中的轮数应根据明文长度来确定.2.1 明文长度为偶数输入:明文X=1 5 7 4 8 2 6 3,8位十进制数.输出:8位十进制数.2.1.1 加密把明文X=1 5 7 4 8 2 6 3划分为8个1 0以内的数字:x1=1,x2=5,x3=7,x4=4,x5=8,x6=2,x7=6,x8=3.当r=1时,置换密钥k(1)0=3,所以新的F*9=0,1,2,9,4,5,6,7,8,第1轮运算结果为:Z(1)1=(8,9,4,8,1,6,6,9);Z(1)2=(9,6,5,7);Z(1)3=(9,0,3,3,5,0,6,0);Z(1)4=(3,4,6,2);Z(1)5=(1,2,8,2,7,2,8,1).当r=2,3,4时,前一轮的输出作为下一轮的输入,同理得到输出结果为:Z(2)5=(9,8,6,2,3,6,9,4);Z(3)5=(6,2,0,7,1,4,5,0);Z(4)5=(7,1,8,8,0,2,5,4).最后进行输出变换,置换密钥k(5)0=4,所以新的F*9=0,1,2,3,9,5,6,7,8,输出变换运算结果为:750|信 息 安 全 研 究Journal of Information Security Research第 9 卷 第 8 期 2023 年 8 月Vol.9 No.8 Aug.2023Y=(2,6,3,5,6,9,2,6).最终得到密文Y=2 6 3 5 6 9 2 6.2.1.2 解密把密文Y=2 6 3 5 6 9 2 6划分为8个1 0以内的数字:x1=2,x2=6,x3=3,x4=5,x5=6,x6=9,x7=2,x8=6.当r=1时,置换密钥k(5)0=4,所以新的F*9=0,1,2,3,9,5,6,7,8,第1轮运算结果为:Z(1)1=(7,1,8,8,0,2,5,4),下面运算中的置换密钥为k(4)0=3,F*9=0,1,2,9,4,5,6,7,8.结果为:Z(1)2=(6,0,8,1);Z(1)3=(7,7,7,3,1,2,7,4);Z(1)4=(2,4,5,6);Z(1)5=(5,9,4,5,7,9,8).当r=2,3,4时,前一轮的输出作为下一轮的输入,同理得到输出结果为:Z(2)5=(8,4,1,8,8,1,4,9);Z(3)5=(2,1,0,6,8,1,1,6);Z(4)5=(8,9,4,8,1,6,6,9).最后进行输出变换,置换密钥k(1)0=3,F*9=0,1,2,9,4,5,6,7,8,输出变换运算结果为:X=(1,5,7,4,8,2,6,3).最终得到明文X=1 5 7 4 8 2 6 3.2.2 明文长度为奇数输入:明文X=1 5 7 4 8,5位十进制数.输出:5位十进制数.2.2.1 加密把明文X=1 5 7 4 8划分为5个1 0以内的数字:x1=1,x2=5,x3=7,x4=4,x5=8.当r=1时,置换密钥k(1)0=3,所以新的F*9=0,1,2,9,4,5,6,7,8,第1轮运算结果为:Z(1)1=(6,4,7,1,6);Z(1)2=(2,6,0);Z(1)3=(1,7,6,6,7,6);Z(1)4=(0,2);Z(1)5=(6,4,9,3,6).当r=2,3,4时,前一轮的输出作为下一轮的输入,同理得到输出结果为:Z(2)5=(1,7,6,1,1);Z(3)5=(4,0,4,1,7);Z(4)5=(4,5,8,3,0).最后进行输出变换,置换密钥k(5)0=4,所以新的F*9=0,1,2,3,9,5,6,7,8,输出变换运算结果为:Y=(4,8,8,3,0).最终得到密文Y=4 8 8 3 0.2.2.2 解密把密文Y=4 8 8 3 0划分为5个1 0以内的数字:x1=4,x2=8,x3=8,x4=3,x5=0.当r=1时,置换密钥k(5)0=4,所以新的F*9=0,1,2,3,9,5,6,7,8,第1轮运算结果为:Z(1)1=(4,5,8,6,5),下面运算中的置换密钥为k(4)0=3,F*9=0,1,2,3,9,5,6,7,8.结果为:Z(1)2=(9,2,1);Z(1)3=(3,5,3,4,7,1);Z(1)4=(4,3);Z(1)5=(0,1,5,3,1).当r=2,3,4时,前一轮的输出作为下一轮的输入,同理得到输出结果为:Z(2)5=(7,3,8,5,0);Z(3)5=(6,2,2,7,6);Z(4)5=(6,4,7,1,6).最后进行输出变换,置换密钥k(1)0=3,F*9=0,1,2,9,4,5,6,7,8,输出变换运算结果为:X=(1,5,7,4,8).最终得到明文X=1 5 7 4 8.3 安全性分析对于保留格式加密安全性的描述最早是由B l a c k等人1提出的P R P(p s e u d or a n d o mp e r m u-t a t i o n)安全,即伪随机置换安全.要求攻击者把保留格式加密方案和消息空间内的随机置换区分开.本文通过差分密码分析和相关密钥攻击,得出r=1 0对所有的实例是安全的结论.3.1 差分密码分析差分密码攻击是迭代型分组密码最有效的攻击方式之一.差分分析主要关注的是非线性函数,本文提出的G F P E算法的非线性过程包括S盒、F9域模加和F1 1域模乘.网址 http:/|751学 术 论 文Research Papers在差分密码分析中,通过选择具有特定输入差分的明文对(X,X*)使得最后一轮的差分Y(r-1)以高概率输出为特定的值.给出以下的定义:定义1.差分对.(,)为分组密码的1个i轮差分对,其中是1对不同的明文X和X*的差分值,经过i轮加密,输出对Y(i)和Y(i)*的可能差分值为.定义2.差分概率.当明文X和轮密钥K1,K2,Ki取值独立且均匀分布的情形下,给定明文对(X,X*)的差分值为X=,则第i轮输出对(Y(i),Y(i)*)的差分值为Y(i)=的概率为迭代分组密码的1条i轮差分(,)的概率,记为DP(,).特别地,当i=1时,DP(,)表示轮函数的差分传播概率.定义3.差分特征的级联.给定2条差分特征1=(0,1,s),2=(0,1,t),若s=0,则称=(0,1,s,1,2,t)为1和2的级联,记为=12,此时,DP()=DP(1)DP(2).由文献1 7 可知,具有弱轮函数的m位十进制数的r轮迭代密码抵抗差分攻击的充分必要条件是r-1轮差分中没有一个概率显著大于1 0-m.所以需要找到r-1轮中的最大差分传播概率小于1 0-m,这样进行差分密码攻击所需的数据就会超过可用数据.使用G F P E(m)代表G F P E算法加密m位十进制数,以G F P E(2)为例进行差分分析,F9域和F1 1域的差分最后会和S盒进行一个复合运算,S盒和这两者相互独立.分析经过F9域和F1 1域的运算后再复合到S盒输出差分的基本性质:r o w=(x1+k1-x2k2)k3;r o w*=(x*1+k1-x*2k2)k3;c o l u m n=r o w+r o w;c o l u m n*=r o w*+r o w*;S=SB o x(r o w,c o l u m n);S*=SB o x(r o w*,c o l u m n*).根据上述描述,对G F P E(2)进行穷举实验,计算出9 09 0的差分传播概率矩阵,得到1轮G F P E(2)算法的最大差分概率为0.0 4 1 7 5 9.根据差分特征的级联定义,可以得出对于G F P E(2)加密算法,任意4轮进行差分密码攻击所需的数据超过可用数据.同理,对G F P E(4)进行差分分析,输入差分和输出差分的性质与G F P E(2)类似,仅仅增加了位数和密钥.对于G F P E(4),其差分传播概率矩阵大小为90 0 090 0 0,穷举实验时间较长,故在文献1 7 提出的“随机等价假设”原则 之 下,讨 论G F P E(4)算法的差分传播概率,即假设对大多数密钥而言,固定密钥下的差分传播概率与各轮密钥相互独立且随机均匀分布时的差分传播概率近似相等,表 示 为DPk1,k2,kr-1(,)DP(,).在“随机等价 假设”原 则 之 下,计 算 出 一 轮G F P E(4)算法的最大差分概率为0.1 4 1 2 2,则对任意6轮进行差分密码攻击的数据需求将超过可用数据.3.2 相关密钥攻击相关密钥攻击是最重要的密钥相关攻击之一.为了发起相关的密钥攻击,攻击者利用不同子密钥之间有意义的关系,从而可以在一定轮次上构造相关的密钥差异.G F P E算法的密钥扩展算法中使用非线性加运算和异或运算,为了能够弹性输出固定位数的轮密钥,在密钥调度算法的每轮使用了模运算,攻击者不能从1轮子密钥中推导出其他所有轮的密钥,更不可能推导出主密钥.特别是模运算使得攻击者不能确定不同轮的差异传播规律,主密钥依然是安全的.此外,对于消息空间大小为1 0的数值型数据,密钥扩展算法在第5轮中使用初始密钥K的每一位.基于密钥扩展算法可以得出结论,该密钥扩展算法能够抵抗相关的密钥攻击.而且G F P E算法的密钥长度是1 2 8b,对于穷举密钥搜索攻击来说,需要进行21 2 8次加密运算,则使用1 0亿个每秒能测试1 0亿个密钥的芯片并行处理需要花费1 01 3年破解出密钥.即1 02 4个这样的芯片在1天内能找出密钥,显然目前没有这样的实力造这样的一个机器,故G F P E算法可以达到实际安全性的要求.4 效率分析应用最广泛的保留格式加密算法是N I S T保留格式加密标准F F X1 8,基于F e i s t e l结构,轮数752|信 息 安 全 研 究Journal of Information Security Research第 9 卷 第 8 期 2023 年 8 月Vol.9 No.8 Aug.2023为8,需要调用8次基础分组密码,会降低基础密码算法的效率,本文实验选用基础分组密码A E S,分组长度是1 2 8 b,1 2 8 b可以转换为3 2位十进制数字.本文提出的保留格式加密算法不需要结合C y c l e-W a l k i n g,只需要进行多次轮函数运算,效率显著降低.实验环境为:M a t l a bR 2 0 1 8 a,C P U为I n t e lC o r eTMi 7-1 0 7 5 0H,主 频 为2.6 0GH z,内存为3 2.0G B.G F P E的密钥为1 2 8 b,加密3 2位十进制数字时每轮会使用到密钥的所有位数,所以分别计算1 0 0 0条23 2位不同明文长度下算法的加密时间,计算其平均时间,实验的效率对比如图2所示:图2 效率对比实验结果表明:随着明文长度的增加,本文提出的算法用时缓慢增加,F F X用时基本稳定;在相同明文长度下,算法效率远远大于F F X的效率.在一个分组1 2 8b数字(3 2位十进制数)下,本文算法效率大约是F F X的3 0倍,显著提高了保留格式加密算法的效率,应用前景广泛.为了增强数据库系统的安全,大多数应用依赖数据库系统.金融支付1 9、电子商务2 0、社保、教育系统以及网上支付等数据库应用系统中存在大量敏感信息,如银行卡号、电话号码、身份证号等,保留格式加密算法不破坏数据库结构和不改动软件代码,加强数据库安全的同时节省大量资源.此外,还可用于数据遮蔽和支付卡行业,将真实数据伪装为加密之后的数据,使假数据看起来是真数据,保护个人信息.5 结 语本文提出了一种数值型数据保留格式加密算法,能对超过1位的任意位数值型明文进行保留格式加密,保证数值型明文加密为长度相同的数值型密文,且在有限的计算能力范围内达到实际安全性的要求.和传统的保留格式加密算法相比,该算法不使用C y c l e-W a l k i n g,极大地提高了F P E算法的效率,具有广阔的应用前景,能增强数据库中数值型敏感数据的安全,也可在数据遮蔽和金融支付中避免数据泄露,保护隐私.下一步要做的工作是优化算法的结构,使随着明文数据长度的增加,算法使用的时间是趋于稳定的,并且探究如何对所有数据类型都适用的保留格式加密算法.参考文献1B l a c kJ,R o g a w a yP.C i p h e r sw i t ha r b i t r a r yf i n i t ed o m a i n sC P r o co fC r y p t o g r a p h e r sT r a c ka tt h eR S A C o n f.B e r l i n:S p r i n g e r,2 0