硕士论文-Serpent的线性分析.pdf

山东大学 硕士学位论文 Serpent的线性分析 姓名：冯骐 申请学位级别：硕士 专业：基础数学 指导教师：王小云 20040410 原创性声明 本人郑重声明：所呈交的学位论文，是本人在导师的指导下，独立进 行研究所取得的成果。除文中已经注明引用的内容外，本论文不包含任何 其他个人或集体已经发表或撰写过的科研成果。对本文的研究作出重要贡 献的个人和集体，均已在文中以明确方式标明。本声明的法律责任由本人 承担。 论文作者签名：缝日期：巡辛舟枷 关于学位论文使用授权的声明 本人完全了解山东大学有关保留、使用学位论文的规定，同意学校保 留或向国家有关部门或机构送交论文的复印件和电子版，允许论文被查阅 和借阅：本人授权山东大学可以将本学位论文的全部或部分内容编入有关 数据库进行检索，可以采用影印、缩印或其他复制手段保存论文和汇编本 学位论文。 ( 保密论文在解密后应遵守此规定) 论文作者签名：z ! ! 堡：导师签名：量兰：叁日期：卫型! 皇缈曰 S e r p e n t 的线性分析 冯骐 山东大学数学与系统科学学院济南2 5 0 1 0 0 中文摘要 计算机网络通信的发展，促进丁信息安全产业及其标准化的进步。本文就是 作者在关注信息安全标准化发展过程中做的一点工作。 信息安全标准化已经有了三十余年的历史。1 9 7 3 年美国国家标准局( N B S ，美 国国家标准与技术研究所 N I S T 的前身) 公开招标征集一个“适合于商业和非 国防性政府机关使用的”标准密码算法及相应的技术支持。在所有呈送的算法中， 一个由I B M 公司开发的算法一支独秀。1 9 7 6 年，S B S 在国家安全局( N S A ) 的帮 助下，确认将这个分组密码算法采纳为联邦标准，定名为D E S ( D a t ag n c r y p t i o n S t a n d a r d ) 。随后，它又被美国国家标准研究所( A N S I ) 批准作为私营部门的标 准，称为D E A ( D a t aE n c r y p t i o nA l g o r i t h m ) 。在之后的十余年中，D E S 被广泛 的应用在世界各国的金融标准星。对它的研究、分析和改进推动了分组密码的蓬 勃发展。 使用了长达2 0 年之后，随着计算机能力的增强，D E S 的密钥长度( 5 6 比特) 已经不够了。1 9 9 7 年1 月，N I S T 又发动征集新的分组密码算法以替代D E S 。遴 选新标准A E S ( A d v a n c e dE n e r y p t i o nS t a n d a r d ) 的过程被分为若干个阶段，每 个阶段结束前都要召开一次专题讨论会。在第二届A E S 会议后，1 9 9 9 年8 月，5 个进入决赛的算法被确定下来了，它们是S e r p e n t ，M a r s ，T w o f i s h ，R i j n d a e l ，和 R C 6 。又经过一轮全面细致的评估，由比利时学者提出的R i j n d a e l 成为评委们的 首选，并于2 0 0 0 年1 0 月2 日被N I S T 定名为A E S 。 本文所分析的S e r p e n t 正是进入A E S 最后决赛的5 个算法之一，由著名的密 码学家R JA n d e r s o n ，E B i h a m 与LR K n u d s e n 设计。S e r p e m 是一个代表性很 强的分组加密算法，它的安全性分析具有很重要的研究价值。本文对于S e r p e n t 的抗线性分析的强度做了细致的分析。 首先，本文给出了针对S e r p e m 的线性分析方法，步骤如下： 型变查兰竺! ：兰垡堡兰一 第一步，定义了活性S 盒、线陛表示和某个S 盒在一点的线性特征。并提 出S e r p e n t 的s 一盒的构成特性： 性质1 所有的S 盒的线性特征的值为8 ，8 + - 2 或8 4 ；相应的线性表示的 概率为I 2 ，1 2 _ + 1 1 2 3 或1 2 + 1 2 2 。且当d ，6 均为2 的方幂时，特征值不可能为 8 4 。 第二步，分别计算出S e r p e n t 的8 个s 一盒的线性特征分布表。( 正文中的表1 及附录2 ) 第三步，按照S e r p e n t 的算法和上面锝到的线性特征分布表，写出几圈内的 线性表示，并得到了堆积引理，即： 引理1( 堆积引理) 若某一线性表示中共有“ 个活性s - 盒，每个活性S 一盒 特征出现的概率为P 。，则整个线性表示成立的概率为：P = I 2 + 2 ”1 兀( n 一1 1 2 ) 。 由上面几步可以计算线性表示成立的概率。 然后，本文给出了利用计算机统计的4 、5 、6 圈线性表示成立概率最高的实 例( 程序在附录中给出) ： 4 圈线性表示： x ； 1 3 ，1 1 8 1 1 9 】 0 S o 2 6 ，2 7 4 4 ，4 6 ，4 7 ，5 3 ，5 4 ，5 5 6 4 6 5 ，9 2 ，9 4 ，9 5 = K ， 1 ，3 ，1 1 8 1 1 9 o K “3 1 o K 7 【8 2 ，l 0 0 1 0 K o 【2 5 ，2 7 ，4 4 ，5 4 ，6 5 ，9 5 该表示成立的概率为1 2 1 2 ”。 5 圈线性表示： x 。 3 6 ，3 9 ，6 0 ，6 3 ，7 2 ，7 5 ，8 9 ，9 0 ，9 1 ，1 0 0 ，1 1 2 ，11 3 ，1 2 5 ，1 2 6 ，1 2 7 o S o 2 6 ，2 7 ，4 4 ，4 6 ，4 7 ，5 3 ，5 4 ，5 5 ，6 4 ，6 5 ，9 2 ，9 4 ，9 5 = K 。 3 6 ，3 9 ，6 0 ，6 3 ，7 2 ，7 5 ，8 9 ，9 0 ，9 1 ，1 0 0 ，11 2 ，11 3 ，1 2 5 ，1 2 6 ，1 2 7 1 o K ， 1 ，3 ，1 1 7 o K 6 3 1 1 K ， 8 2 ，l 0 0 1 0 K o 【2 5 ，2 7 ，4 4 ，5 4 ，6 5 ，9 5 该表示成立的概率为1 2 1 2 ”。 6 圈线性表示： x 。 3 6 1 3 9 ，6 0 6 3 ，7 2 ，7 5 ，8 9 ，9 0 ，9 1 ，1 0 0 ，11 2 ，11 3 ，1 2 5 ，1 2 6 ，1 2 7 1o s 1 ( 9 ，1 6 , 1 9 ，2 8 3 0 ，3 1 3 8 ，3 9 ，5 8 ，5 9 ，6 7 ，6 8 ，7 0 ，7 l ，7 6 ，7 8 ，7 9 ，8 5 ，8 7 ，1 0 6 1 0 7 ，11 6 ，1 1 8 ，1 2 4 、1 2 7 】 = K 4 【3 6 3 9 6 0 ，6 3 ，7 2 ，7 5 ，8 9 ，9 0 ，9 1 ，1 0 0 1 1 2 ，l1 3 ，1 2 5 1 2 6 ，1 2 7 0 K 5 【1 ，3 ，l17 】oK 6 31 】0K 7 8 2 ，10 0 】0K o 2 5 ，2 7 ，4 4 ，5 4 ，6 5 ，9 5 】 o K t 8 ，9 ，1 8 ，2 9 ，3 9 ，5 9 ，6 5 ，6 6 ，6 7 ，6 9 ，7 7 ，8 4 ，1 0 7 ，1 1 7 ，1 1 9 ，1 2 6 该表示成立的概率为1 2 1 2 ”。 上面结果中，4 圈的线性表示超出了S e r p e n t 作者分析时所给的4 圈的概率 界限，比其估计结果好。而5 圈和6 圈的线性表示也是对S e r p e n t 的线性分析的 精确结果的首次提出。这些结果提高了对S e r p e n t 安全性分析的精确性。 随后，本文从整体上考虑S e r p e n t 的抗线性分析能力。 根据算法对S 一盒的设计，得到了如下定理： 定理1 ：如果第f 圈的输入仅通过一个，两个或三个活性s - 盒，那么，以之为起 始的线性表示满足下列5 种情况之一成立： ( 1 ) 第i ，l 圈的活性s - 盒的个数之和8 ，即7 ，+ n 。8 。 ( 2 ) 当H ，+ “ _ + 1 8 时，门，+ “ + 7 + 2 1 2 。 ( 3 ) 当7 ，+ 7 ，+ 1 8 ，且“ ，+ 7 ，+ 1 + 7 。+ 2 - 1 6 。 ( 4 1 当”，+ ”川 8 ，门，+ 7 川+ 灯，+ 2 1 2 ，且门，+ 7 。+ l + 胛+ ! + i “ + j 1 6 时， “ + n ，+ l + “ r + ! + 一+ 3 + 门1 4 2 0 。 ( 5 ) 当，2 + 门。+ l 8 ，胛+ 订，+ 1 + 玎。+ 2 1 2 ，胛l + ”，+ l + “ ，+ 2 + ”，+ 3 1 6 且 “ 士“ ，+ l + 门f 十2 + “ f + 3 + ”，+ 4 2 4 。 由这定理可以推得：1 6 圈最优线陛表示的概率与1 2 的差不会高于1 2 5 9 ， 即线性分析需要2 “8 个明文，1 7 圈的最好线性表示的概率与1 2 的差不高于l 2 6 3 ， 需要2 个明文。 由于S e r p e n t 的明文分组为1 2 8 比特，因此仅含1 7 圈的S e r p e n t 己具有很强 的抗线性分析能力。 本文的分析结果可以达到以下目的：使人们清楚的掌握S e r p e n t 的抗线性分 析的能力；对S e r p e n t 的整体安全性有更深的了解；进一步掌握目前关于对称密 钥加密算法的一些设计技术及分析技巧。 关键词分组加密算法，S e r p e n t ，线性分析，活性S 一盒。 山东大学颐l 。学位论文 L i n e a r A n a l y s i so f t h eA E S F i n a l i s t ：S e r p e n t F e n g Q i ( S c h o o lo fM a t h e m a t i c s a n dS y s t e mS c i e n c e ，J i n a n ，2 5 0 1 0 0 ) A b s t r a c t W i t ht h ed e v e l o p m e n to fc o m m u n i c a t i o nu s i n gn e t w o r k ，t h ei n f o r m a t i o ns e c u r i t y i n d u s t r ya n di t ss t a n d a r d i z a t i o ni sp r o m o t e dg r e a t l y T h i sp a p e ri s s o m eo f m y w o r k d o n ew h e n1w a s p a y i n g a t t e n t i o nt ot h e p r o g r e s s o fi n f o r m a t i o n s e c u r i t y s t a n d a r d i z a t i o n T h ei n f o r m a t i o ns e c u r i t ys t a n d a r d i z a t i o nh a sah i s t o r yo fm o r et h a n3 0y e a r s I n 1 9 7 3 ，t h eN a t i o n a lB u r e a uo fS t a n d a r d 州B S ) ，n o wt h eN a t i o n a lI n s t i t u t eo f S t a n d a r d a n d T e c h n o l o g yf N I S T ) ，i s s u e d a p u b l i cr e q u e s t f o r p r o p o s a l s f o ras t a n d a r d c r y p t o g r a p h i ca l g o r i t h mt op r o t e c tc o m p u t e r a n dc o m m u n i c a t i o nd a t a A m o n ga l lt h e s u b m i t t e dp r o p o s a l s ，a na l g o r i t h md e v e l o p e db yI B Mw a so u t s t a n d i n g I n19 7 6 ，i tw a s a c c e p t e db y N B Sa sF e d e r a lS t a n d a r da n dw a sn a m e dD E S ( D a t aE n c r y p t i o n S t a n d a r d ) I n t h e f o l l o w i n g s c o r e y e a r s D E S W a su s e d w i d e l y i nw o r l d w i d e c o m m u n i c a t i o ns t a n d a r d s T h ea n a l y s i s ，a t t a c k ，a n di m p r o v e m e n tp r o m o t e dan e w s c i e n c e ，c r y p t a n a l y s i s ，g r e a t l y A f t e rt w od e c a d e s u s i n g ，t h e e n h a n c e d p o w e r o f c o m p u t e r s m a d eD E S v u l n e r a b l eb e c a u s eo fi t s s h o r t k e ys i z e ( 5 6 一b i t ) An e wa n ds a f e r s t a n d a r dw a s d e m a n d e du r g e n t l y I nJ a n 1 9 9 7 N I S Ti s s u e da n o t h e rp r o g r a mf o ran e w a l g o r i t h m t o r e p l a c eD E S T h e p r o c e s sc h o o s i n gA E S ( A d v a n c e dE n c r y p t i o nS t a n d a r d ) w a sd i v i d e di nt h r e e s e c t i o n s B e f o r et h ee n do fe v e r ys e c t i o nt h e r ei sac o n f e r e n c et os u m m a r i z ei t 5 a l g o r i t h m sw e r es e l e c t e dt o i n t e rt h ef n a lc o m p e t i t i o na f t e rt h es e c o n dc o n f e r e n c e ， A u g 19 9 9 T h e y a r e S e r p e n t ，M a r s ，T w o f i s h ，R i j n d a e l ，a n dR C 6 R i j n d a e l ，a n a l g o r i t h mp r o p o s e db yB e l g i a ns c h o l a r s ，w a sf i n a l l ys e l e c t e db yt h ec o m m i t t e ea n d n a m e dA E So nO c t 2 ，2 0 0 0 I nt h i sp a p e rS e r p e n ti sa n a l y z e du s i n gl i n e a ra t t a c k S e r p e n ti sar e p r e s e n t a t i v e b l o c kc i p h e r ，d e s i g n e db yt h r e ef a m o u sc r y p t o g r a p h e r s ，R JA n d e r s o n ，E B i h a m ，a n d 4 山东大学碗I ：学位 它文 L R K n u d s e n T h ea n a l y s i so fi ti s v e r yv a l u a b l e W eh a v es t u d i e dt h i sa l g o r i t h m c a r e f u l l ya n d h a v ed r a w ns o m e g o o d r e s u l t si nl i n e a ra n a l y s i s F i r s to f a l l ，t h i sp a p e rs h o w sh o w t ou s el i n e a ra n a l y s i sa t t a c k i n gS e r p e n t I nt h ef i r s ts t e p ，w eg i v et h ed e f i n i t i o n so fa c t i v e S b o x ，l i n e a rp r e s e n t a t i o n a n dt h el i n e a rc h a r a c t e rf o rac e r t a i nS b o xo nac e r t a i np o i n t A l s ow e g i v et h e s t r u c t u r ec h a r a c t e rf o rS b o x e so f S e r p e n t ，w h i c h i s ： C H A R A C T E R l A l l t h e l i n e a rc h a r a c t e r s f o rS b o x e sa r e8 ，8 2 ，o r8 4 a n dt h e r e s p e c t i v ep r o b a b i l i t i e s t ol i n e a r p r e s e n t a t i o n s a r eI 2 ，1 2 1 2 3a n d 1 2 1 2 2 E s p e c i a l l y , w h e n b b o t ha r et h ep o w e r so f 2 t h el i n e a rc h a r a c t e rc a r l t b e8 4 I nt h es e c o n d s t e p ，w ew o r k O U tt h e8d i s t r i b u t i o nt a b l e so fS b o x e so f S e r p e n t ( T a b l el f o rS oi nt e x ta n do t h e r si nA p p e n d i x ) ，I nt h et h i r ds t e p ，w eg i v es o m ee f f i c i e n tl i n e a rp r e s e n t a t i o n s ，d r a w nf o r mt h e a l g o r i t h m a n d u p p e r d i s t r i b u t i o nt a b l e sW ea l s og i v et h ep i l i n g - u pl e m m af o rS e r p e n t ： L E M M A1 ( p i l i n g - u p e m m a ) I ft h e r ea r e “ a c t i v eS b o x e si nac e r t a i n l i n e a r p r e s e n t a t i o n ，a n d t h ep r o b a b i l i t yh o l df o r e v e r y c h a r a c t e rt h r o u g ha c t i v e S b o x e si s P ，t h e nt h ep r o b a b i l i t yP h o l df o rt h ew h o l el i n e a rp r e s e n t a t i o ni s ： P = 1 2 + 2 ”1 兀( 只一1 2 ) i = 1 N o ww ec a nc a l c u l a t e P f o ra n yl i n e a rp r e s e n t a t i o n A f t e rt h a t ，w ew o r kO U tt h eh i 曲e s tp r o b a b i l i t yh o l di n4 ，5 ，a n d6r o u n d sa n dt h e a c c o r d i n gl i n e a rp r e s e n t a t i o n Su s i n g c o m p u t e r T h e ya r e ： B e s t4r o u n d sl i n e a rp r e s e n t a t i o n 5 1 ，3 ，11 8 ，11 9 】 o S 。 2 6 ，2 7 ，4 4 ，4 6 ，4 7 ，5 3 ，5 4 ，5 5 ，6 4 ，6 5 ，9 2 ，9 4 ，9 5 】 = K 5 1 , 3 ，1 1 8 ，1 1 9 】 0 瓦【3 1 】0 K 。 8 2 ，1 0 0 】o K o 2 s ，2 7 ，4 4 ，5 4 ，6 5 ，9 5 】 I t s p r o b a b i l i t yi s I 2 1 1 2 ” B e s t5r o u n d sl i n e a rp r e s e n t a t i o n X 。 3 6 ，3 9 ，6 0 ，6 3 ，7 2 ，7 5 ，8 9 ，9 0 ，9 1 ，1 0 0 ，11 2 ，11 3 ，1 2 5 ，1 2 6 ，1 2 7 】 o S o 2 6 ，2 7 ，4 4 ，4 6 ，4 7 ，5 3 ，5 4 ，5 5 ，6 4 ，6 5 ，9 2 ，9 4 ，9 5 】 5 一些奎叁兰堕! 堂垡堡苎 。芷4 3 6 ，3 9 ，6 0 ，6 3 ，7 2 ，7 5 ，8 9 ，9 0 ，9 1 ，1 0 0 ，11 2 ，11 3 ，1 2 5 1 2 6 i 2 7 o K 5 【1 ，3 ，117 0K 6 3l ie 五 8 2 ，l0 0 1o K o 2 5 2 7 ，4 4 ，5 4 6 5 ，9 5 I t sp r o b a b i l i t yi s 1 2 1 1 2 ”。 B e s t5r o u n d sl i n e a rp r e s e n t a t i o n z 4 3 6 ，3 9 ，6 0 ，6 3 ，7 2 ，7 5 ，8 9 ，9 0 ，9 1 ，1 0 0 ，1 1 2 ，11 3 ，1 2 5 ，1 2 6 ，1 2 7 o S 1 1 9 ，1 6 ，1 9 ，2 8 ，3 0 ，3 1 ，3 8 ，3 9 ，5 8 ，5 9 ，6 7 ，6 8 ，7 0 ，7 1 ，7 6 ，7 8 ，7 9 ，8 5 ，8 7 ，1 0 6 ，1 0 7 ，1 1 6 ，1 1 8 ，1 2 4 ，1 2 7 1 = K 4 1 3 6 ，3 9 ，6 0 ，6 3 ，7 2 7 5 ，8 9 ，9 0 ，9 1 ，1 0 0 ，11 2 ，11 3 ，1 2 5 ，t 2 6 ，1 2 7 】 o K 5 【1 ，3 117 oK 6 31 oK 7 8 2 ，10 0 0 K o 2 5 ，2 7 ，4 4 ，5 4 ，6 5 ，9 5 0 K 1 1 8 ，9 ，1 8 ，2 9 ，3 9 ，5 9 ，6 5 ，6 6 ，6 7 ，6 9 ，7 7 ，8 4 ，1 0 7 ，1 1 7 ，1 1 9 ，1 2 6 】 I t sp r o b a b i l i t yi s I 2 1 2 气 T h eu p p e r4r o u n d sl i n e a rp r e s e n t a t i o ni sb e t t e rt h a nt h eo r i g i n a la n a l y s i sm a d e b yi t sd e s i g n e r sw i t hh i g h e rp r o b a b i l i t y T h e5r o u n d sa n d6r o u n d sl i n e a rp r e s e n t a t i o n a r ee x a c tr e s u l t sf i r s tp r o p o s e di nl i n e a ra n a l y z i n gS e r p e n t T h e s er e s u l t sp r o m o t e d t h e a c c u r a c yi na n a l y z i n gt h es e c u r i t yo f S e r p e n t F i n a l l y , t h i sp a p e rs t a t et h a tS e r p e n ti ss a f ef o rl i n e a ra t t a c ki nh o l i s t i ca p p r o a c h ， W e p r o v et h a tb yt h i st h e o r e m T H E O R E M1I ft h ei n p u to fi t hr o u n do n l ya f f e c t s 1 ，2 ，o r3a c t i v eS b o x P s t h e nt h el i n e a rp r e s e n t a t i o n sb e g i nf r o mt h i si n p u ts h o u l d s a t i s f yo n eo ft h ef o l l o w i n g c o n d i t i o n s ( 1 ) T h es u mo fa c t i v eS b o x e si nr o u n dia n di + 1i sn o tl e s st h a n 8 ，t h a ti s ”，+ 月，+ 1 8 ( 2 ) I f 行，+ n ，+ 1 1 2 ( 3 ) I f ”，+ 胛，+ 】 8 ，a n da l s o n f + “ J + l + H i 2 1 6 ( 4 ) I f n l + 门。+ l 8 ，九+ 疗“+ n ，+ 2 1 2 ，a n da l s o 门f + 月，“+ 力，+ 2 + 咒，柏 - 2 0 ( 5 ) I 饥+ 门+ l 8 ，珂，+ 玎J + l + 订m 1 2 ，f , + n 川+ 吩+ 2 + q + 3 1 6 ，a n da l s o n J + 摊H l + 片，+ 2 + 聆，。+ 行，+ 4 2 4 F r o mt h i st h e o r e m ，i tC a nb ed e d u c e dt h a tt h ep r o b a b i l i t yh o l di nb e s t16 r o u n d s 1 , i n e a rp r e s e n t a t i o ns h o u l di nt h ei n t e r v a l ( 1 2 I 2 妇，1 2 + I 2 5 9 ) ，w h i c hm e a n s m a cm e 6 山东大学硕卜学位论立 l i n e a ra n a l y s i sn e e d s2 t 1 8p l a i n t e x t s W e C a na l s ok n o wt h a tt h ep r o b a b i l i t yh o l di nb e s t 1 7 一r o u n d sl i n e a r p r e s e n t a t i o ns h o u l di nt h ei n t e r v a l ( 1 2 1 2 6 3 1 2 + 1 2 6 3 1 I tm e a n s t h a t2 1 2 6p l a i n t e x t sa r ed e m a n d e d A sS e r p e n th a s12 8 - b i tb l o c k s i z e ，o n l y 17 r o u n d sa l g o r i t h mi ss t r o n ge n o u g ht o d e f e n dl i n e a ra t t a c k T h a ti sw h yw es a i dS e r p e n th a sa l a r g es a f e t yr e d u n d a n c y T h ea i mo ft h i s p a p e ri s t o c l a r i f yt h ea b i l i t ya g a i n s tl i n e a ra n a l y s i so ft h i s a l g o r i t h ma n dt od e v e l o p t h er e a l i z a t i o no f d e s i g nt e c h n i q u ea sw e l la sa n a l y s i ss k i l l f o rs y m m e t r i ck e y a l g o r i t h m s K E YW O R D Sb l o c k c i p h e r ，S e r p e n t ，l i n e a ra n a l y s i s a c t i v eS - b o x 7 山东，I _ ：= 学颂上学位论义 符号说明 本文中使用的符号意义如下： 注：仅在本文第二章中使用的符号这里没有重复标注。 A ：= B 0 fm o d 8 S 。 X 门 1 E z n n P 将B 的值赋予A 按b i t 进行异或运算。 i 被8 除的最小正剩余。 第f 个S 一盒。 x 循环左移n 比特。 逻辑与。 对所有符合条件 的X 计数。 连续乘积。 山东人学颂卜学位：色丈 第一章S e r p e n t 算法简介 1S e r p e n t 的设计和分析 S e r p e m 是由R J A n d e r s o n 、E B i h a m 和L R K n u d s e n 设计的。该算法的最早 版本于1 9 9 8 年 1 提出，通常称为S e r p e n t o 2 ，而参加A E S 的参赛算法是通过 选取不同璺盒的而改进的，称为s e r p e m ( S e r p e m 一1 ) 。该算法的第二设计者E B i h a m 是差分分析的创始人。S e r p e n t 的设计技巧在很大程度上反映了目前分组 密码的一些设计技巧，因此S e r p e n t 的各种安全性分析不仅对于我们了解该算法 的安全性强度意义重大，而且有助于我们分析与设计其它分组密码算法。 差分、线性分析 对于一个分组密码的安全性分析可以有很多种方法，如差分分析 3 】、不可能 差分 4 】、线性分析 5 】、能量攻击 6 ，7 】等，其中差分分析与线陛分析是最主要的 两种分析技术。关于S e r p e n t 的差分分析，王小云、L C KH u i 等 8 】曾证明了整 个算法的是抗差分分析的，并提供了以概率2 “发生的5 圈差分和概率2 4 7 发生 的6 圈差分分析结果，而在此之前，最好的差分估计是以概率2 “发生的5 圈差 分。E 。B i h a m 等于E u r o c r y p t o 2 0 0 1 9 】对我们的5 圈、6 圈的差分分析结果稍作改 进为2 “o 和2 4 3 。 对于S e r p e n t 的线性分析，己知的结果仅有s e r p e n t 的设计者在设计原文中给 出7 圈之内的线性分析估计表，并猜测2 8 圈的分析需要超出2 n o 条明文。然而 所有这些结果只是粗略的估计，没有详细的计算和实例证明。本文详细而精确地 给出了线性分析结果，是对S e r p e n t 算法安全陛分析的重要补充。 其他攻击方法 由其他方法得到的结果有： 6 轮的中间相遇攻击【1 0 ，需要2 8 3 选择明文，2 ”次加密，2 4 0 位内存。 1 0 轮的“矩形”攻击 9 】，需要2 ”64 选择明文，2 ”14 次加密，2 2 0 8 位内存。 所谓“矩形”攻击实际上是差分分析的延伸，将轮数少而概率高的“小块”差分 特征拼接起来构成攻击。这已经是至今为止对S e r p e n t 轮数最多的攻击了。 然而这些结果也不能动摇S e r p e n t 的整体安全性。 9 山东大学顺L 。学泣论文 2S e r p e n t 算法的描述 S e r p e n t 的明文分组为1 2 8 比特，密钥长度为2 5 6 比特。整个加密算法为3 2 圈。在3 2 圈中，共包含8 个不同的S - 盒( S ，i = O ，l ，7 ) 与3 3 个1 2 8 比特的子 密钥K ，K ，：。 每个S 一盒是一个4 比特到4 比特的非线性变换，同一个s 一盒 在一圈中并行使用3 2 次，不同的8 个S 一盒依次重复循环作用到3 2 圈中，子密 钥由一个2 5 6 比特的密钥推出。 加密算法可描述如下： 设1 2 8 比特的明文为P ，将其加密得到1 2 8 比特的密文C 的过程为： B o ：2 伊( P ) B ：2 I P ( L ( F P ( S ，( B ，0 K ，) ) ) ) ，i = O ，1 ，2 ，3 0 B ：2 S 。( B o K ) 0 K3 2 ，i = 3 1 C ：2 F P ( B 3 2 ) S ( ) 指将x 分为3 2 个半字节( 4 b i t ) ，然后将3 2 个半字节均经过S 盒S “ 的变换。 伊与F P 是两个互逆的置换： 1 P ( b k + 3 2 ，) = b 4 I 叫F P ( b m ) = 巩3 2 ，k = O ，1 ，2 3 1 ，J = 0 ，l ，2 ，3 线性变换如下定义： 若将1 2 8 一比特的块X 分成四个3 2 - 比特的字，X = ( x 。，彳j ，X 2 ，3 ) ，其中 x 。= ( b o 6 。b 3 。) 是的第一个( 最低位) 字( 也为的3 2 个最低位) ， 。Y ，= ( b ，。，b ，。，b 。) 为x 的第四个( 最高位) 字，则上是如下的线性变换： X o ：2 氓 1 3 X 2 ：= 并2 3 l ：。X l0 X 0 0 2 2 X 3 ：= X 30 2o ( X o 3 ) 爿l ：= Z 1 l X 3 ：2 X 3 7 O 山东人学坝 学世l 文 X o ：2 X o o X l 0 X 3 x 2 ：2 x 2o X 3o ( 1 7 ) o ：= d 5 X 2 ：= x 2 2 2 输出：L ( X ) = ( 。，X 1 ，X 2 ，X 3 ) 。 S e r p e n t 的每一圈运算可以简化为三步：第一步是输入值与密钥异或，第二 步是通过S 盒的变换，第三步通过一个线性变换表： L T ( X ) = I P ( L ( F P ( X ) ) ) 。 线性变换表r 参见附录1 。 对于线性分析而言，如果求出线性表示式及表示式成立的概率，那么利用该 表示式推导密钥的时间一般仅与表示式的概率有关。所以文中只是给出线性攻击 所需要的时间，而不给出详细推导密钥的过程。由于线性攻击可以将所有的子密 钥看作不相关的，在此我们不再描述S e r p e n t 的密钥生成过程。 山东大学硕士学位论文 第二章对S e r p e n t 的线性分析 1分析过程中的相关定义 先给出一些本章中用到的表示符号的定义。 X 。= ( ，x ，x 1 2 ，) 表示第i 圈的输入和密钥的异或结果，x l ，x 1 2 7 表示 置的+ 1 2 8 个比特，工。，X 。，x ：，为x ，的四个最低位，也是进入第一个S 一盒( s ) 的 四个比特，X 1 2 4 ，x ，：，x ，_ ：，是四个最高位，也是进入最后一个S - A ( s 。) 的四个 比特。 对应于X 。的定义，S 。= ( ，5 ，。S 。) 表示爿。通过3 2 个S A ( s 。) 变换后的 1 2 8 比特输出，；= ( ? 。，。，。：j ) 表示S ，经过7 1 变换后的1 2 8 比特输出，即进入 下一圈的输入。K ，= ( 七。，女，。! ，) 表示这一圈的子密钥a 于是就有 ，H = x ，ok ， ( ，= 0 , 1 1 2 7 ) ：利用这个式子可以得到线性表示的定义。 定义1 若A = 口。，d l ，：2 ，】，则令4 i ，】- d ，o 口，o o q ，于是在某一 圈中，以下线性方程 s d l ，口2 ，- ，口， o X 6 1 ，6 2 ，6 。】= K c 1 ，c 2 ，c t ( 1 ) ( 0 口l ，口2 ，一，d ，；6 【，6 2 ，一，以；c 【，c 2 ，- 一，c 女1 2 7 ) 称为一个线性表示，方程中a 1d ：，q 所在的S 一盒称为活性S 盒。 注：关于s 盒的定义及其对差分分析和线性分析的意义见参考文献 1 l 】。 下面定义来源于第一篇线性分析的文章 5 。 定义2 对某s 盒( S 。) ，0 口 1 6 ，0 b 1 6 ，令 N S ( 日，6 ) = 1 ，川0 x 1 6 ，o o d ) = o ( s ( x ) 6 ) ) ( 2 ) 其中百( x ) 表示二进制表示的x 各位亦或值。称埘。( n ，6 ) 为s 1 在点( d ，6 ) 的线性特征。 2 线性分布表 在给出S e r p e n t 的几个高概率线性表示之前，首先给出S e r p e n t 的一个特性： 性质1 所有的S - 盒的线性特征的值为8 ，8 2 或8 4 ；相应的线性表示的 概率为1 2 ，1 2 + _ 1 2 3 或1 2 - + 1 2 2 。且当口，b 均为2 的方幂时，特征值不可能为 8 4 。 这条性质是由S - 盒的生成条件【l 】得到的，在下面的线性特征分布表中也可 以得到验证。 所有s - 盒的线性特征可以以其线性特征分布表表示，得到线性分布表是线性 分析过程中至关重要的环节。在此仅给出s o 的线性特征分布表( 表1 ) ，其他分 布表见附录2 。 01234567891 01 11 21 31 41 5 080O0OOOO0OO0000O lO一2- 2020020224- 2O- 42 202- 2O02240- 2240- 22O 30O- 4O2 0 一2O- 4O0222- 2 “ 40OOO0 0OO0 0004444 502- 24- 2- 4O2022020O2 6O- 22OO一22442- 20O220 7O0042- 2224OO022- 2 2 8O- 22O20O2O22- 4- 2- 402 9000O044O0OOO40O4 1 0040O222200- 402- 222 1 l022O42- 2O02240220 1 2O- 2242O42O一2- 2O2002 1 3O- 4 - 4OOOOOO4- 40000 O 1 4OO0422224000- 222- 2 1 50- 220- 4- 220422O0- 22 、o 表1 S o 的线性特征分布表( 第一列为特征的第一坐标) 注：为清晰表示特征值与平均值8 之间的偏差，表中的每一项均为特征值减 8 的结果。 线性分析表达式成立的概率可以由以下引理【5 】推出： 引理1( 堆积引理) 若某线性表示中共有n 个活性S 盒，每个活性S 盒 山东大学碗L 学位论文 特征出现的概率为p ，则整个线性表示成立的概率为：P = 1 2 + 2 n ( 且一1 2 ) 。 引理可对n 做归纳法证明。 3 最优线性表示 表2 - 表4 给出了S e r p e n t 的三个线性表示，根据其概率的算法，表中的P r 是 这一圈中的线+ 1 螨1 2 的差，P , 1 3 2 ”1 r = I ( 只一1 2 ) a 其中表3 、表4 是我们用 r = l