(应用数学专业论文)分组密码的设计与分析(1).pdf_第1页
(应用数学专业论文)分组密码的设计与分析(1).pdf_第2页
(应用数学专业论文)分组密码的设计与分析(1).pdf_第3页
(应用数学专业论文)分组密码的设计与分析(1).pdf_第4页
(应用数学专业论文)分组密码的设计与分析(1).pdf_第5页
已阅读5页,还剩40页未读, 继续免费阅读

下载本文档

版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领

文档简介

国 防 科 学 技 术 大 学 研 究 生 院 学 位 论 文摘 要 本文在跟踪美国a e s 计划和欧洲n e s s i e计划的基础上, 对分组密码进行了总体上的概述,介绍了 分组密码在通信系统中的作用, 分组密码的整体结构特征,分组密码的设计原理以 及分组密码的分析方法。 在此基础上, 对a e s 的候选算法t w o f i s h 和n e s s i e 计划的候选算法i d e a进行研究,得到了一些有意义的结果。 t w o f i s h 是f e i s t e l 网络型密码算法,它的分组长度为1 2 8 e 匕 特, 支持1 2 8 , 1 9 2 和2 5 6比特长的密钥, 它的s 一 盒采用密钥相关s 一 盒, 不同长度的密钥构造的s 一 盒稍有不同。 我们从理论上证明了 密钥越长, 所对应的密钥相关s 一 盒的最大差分概率越小。 并且给出了一种新的密钥相关s 一 盒的构造方法, 理论分析与实验数据表明在密钥长度为1 2 8 比特的情况下,新的s 一 盒比原来的s 一 盒的最大差分概率要小。 i d e a是一个比较优秀的密码算法,进入了n e s s i e计划的第二轮。直接对它进行分析是比较困难的,将 i d e a的某些环节进行简化,并称简化后的算法为变种 i d e a。利用乘积差分对变种i d e a进行了有效的分析, 我们能攻破1 4 圈的变种算法: i d e a - x 1 4 和8圈的变种算法:i d e a - m8 ,关键词:分组密码;密钥相关s 一 盒;t w o f i s h ; i d e a ;乘积差分;差分概率第 i页国 防 科 学 技 术 大 学 研 究 生 院 学 位 论 文ab s t r a c t i n t h i s p a p e r w e i n t r o d u c e t h e c o n c e p t o f t h e b l o c k c i p h e r a n d i t s p o s i t i o n i n t h ec o m m u n i c a t i o n s y s t e m s . a c c o r d in g t o t h e a e s a n d n e s s i e p r o j e c t s , w e p r o p o s e t h e s t ru c t u r e s ,s o m e d e s i g n p r i n c i p l e s a n d s o m e a n a l y s i s m e t h o d s o f t h e b lo c k c i p h e r . o u r m a i n w o r k i s o nt w o fi s h a n d ide a a n d w e g e t s o m e in t e r e s t i n g r e s u l t s . t w o f i s h i s a f e i s t e l c i p h e r , a n d t h e l e n g t h o f t h e k e y i s 1 2 8 . 1 9 2 o r 2 5 6 b i t s , a n d t h e l e n g th o ft h e b l o c k i s 1 2 8 b i t s . t h e s - b o x e s a r e t h e k e y - d e p e n d e n t s - b o x e s t h a t a r e d e r i v e d fr o m t h e k e y .w e s h o w t h a t t h e l o n g e r t h e k e y o f t w o fi s h i s , t h e s m a l l e r t h e d i ff e r e n t i a l p r o b a b i l i t i e s o f t h ek e y - d e p e n d e n t s - b o x e s a r e . a n d w e p r o p o s e a n e w m e t h o d t o c o n s t r u c t t h e k e y - d e p e n d e n ts - b o x e s , a n d g e t t h a t t h e m o d i f i e d s - b o x e s a r e b e t t e r t h a n t h e o r i g i n a l s - b o x e s i n x o r d i ff e r e n t i a la n d m o d u l a r a d d i t i o n d i ff e r e n t i a l p r o p e rt i e s fr o m t h e t h e o r y a n d s i m u l a t i o n r e s u l t s . ide a i s a g o o d b lo c k c i p h e r , a n d i t h a s n o o b v i o u s w e a k n e s s i n t h e s a f e t y . i t w e n t i n t o t h ep h a s e i i o f t h e n e s s i e p r o j e c t s u c c e s s f u l ly . t o a n a l y z e t h e a l g o r i t h m , w e s i m p l i f y it . a n d w er e f e r t o t h e s i m p l i f i e d a l g o r i t h m a s v a r i a n t ide a . w e b r e a k t h e v a r i a n t ide a 一ide a - x 1 4 o f1 4 r o u n d s a n d i d e a - m8 o f 8 r o u n d s 一 b y a n e w a n a l y s i s m e t h o d c a l l e d mu l t i p l i c a t i v ed i ff e r e n t i a l s . f o rt u n a t e l y , t h e o r i g i n a l ide a i s s t i l l s a f e t o t h e mu l t i p l i c a t i v e d i ff e r e n t i a l s .k e y w o r d s : b l o c k c i p h e r ; k e y - d e p e n d e n t s - b o x e s ; t w o f i s h ; ide a ; m u l t i p l i c a t i v e d i ff e r e n t i a l s ; d i ff e r e n t i a l p r o b a b i l i t y . 一一一一-一_ _ 第 i f页独创性声明 本人声明 所呈交的 学 位论文是我本人在导师 指导下进行的研究工作及取得的 研究成果. 尽我所知, 除了 文中 特别加以 标注 和致 谢的 地方外, 论文中 不 包含其 他 人已 经发表和撰写 过 的 研究成 果, 也 不 包 含为 获 得 国 防 科学 技 术大学 或其它教育 机构的学位或证书而 使 用过的材料. 与我一 同 工 作的 同 志对本研究所做的 任何贡献均已 在论文中 作了 明 确的 说明并表示谢意 . 学位论文题目 : _分组密码的设计与 分析学位论文作者签名:日 期: 2 0 8 ;年1 1月莎日学位论文版权使用授权书 本人完全了 解国防 科学 技 术大学有关保留 、 使用学 位论文的规定. 本人 授权国防 科学技术大学可以 保留 并向国家有关部门 或机构送交论文的复印 件和电 子文 档, 允许论文被查阅 和 借阅 ; 可以将学位论 文的 全部 或部 分内 容编入有关数据库进行检索,可以 采用影印 、 缩印 或扫描等复制手 段 保存、汇 编学 位论文. ( 保密学位论文在解密 后适用本授权书. ) 学 位论文题目 : 一 一 一 里 座 旦 生码的设计与 分 析学 位 论 文 作 者 签 名 : 周礼作者指导教师签名:日 期 :z w o 3 年1 1 月 厅日日 期 : , 。 。 年i i 月 1犷 日国 防 科 学 技 术 大 学 研 究 生 院 学 位 论 文插图目录数字通信系统模型.密码系统 . . . . . . , 一一轮一轮f e i s t e l 型密码的加密过程 . . . . . , . , . , . . . . . . . . . 一s p型密码的加密过程. . . . . . . , , . . . . . . . . . . ,. . , . . . . . . . . . . . . . , 61,一内、月峪5 l m结构中的轮函数框图 , ,. , . . . . . . . . . . . , , , . . . . . . . . , ., , . 76 三轮的迭代型分组密码. . . . . . . . . . . . . . . . . , . . , . . . . . . . . . . . . , . , . . . . . . . . . . . . 77 两轮的密钥交替分组密码. . . . . , . , . . . . . . . . . . . . . , 二 , . . . . . . . . . . . . . . . . . . . . . . 88 回旋攻击示意图一,. , , , 二 . . . . . . , , , , . . . . - . . . . . . , ., . , 二, . . . . . . . 1 41 t w o f r s h 算法中密钥相关s 一 盒的形成过程, . . . ., , . . . . . . . . . . . . . . . . . . . . . . . . 2 1i i d e a算法加密流程图. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . , , . . . . . . . . 3 02 变种i d e a算法i d e a - x流程图. . . . . . . . . . . . . ,. . 价 . . . . . . . . . . , , ., . . 3 23 乘积差分与异或运算的关系. . . . . . , ,. . , , . . . . . . . . . . . . . . . . . . 几. . . . , . 3 3,乙汽2,性勺气乙,伟j4月,月斗图图图图图图图图图图图图表格目录原s 一 盒与改进s 一 盒的对照表二 , 二 , , ,. ,二 , . . . . . . . . 改进环节与原环节的最大差分概率对照表 . . . . . . . . . . , . , . . _ _ . _. , 二 , , 二 2 2. . , 2 5尹07今,改进s 一 盒与原s 一 盒对应不同最大差分概率的个数分布统计表改进s 一 盒与原s 一 盒差分概率统计表 . . . . . . . . . . . . . . . _ _ _ _ _ _ _ _ _ _ _ _1,一、j4内j,j八j月j表表表表 一 一 一 一 一 一 - - - - - 一 一 - 一 , 第 i i页国 防 科 学 技 术 大 学 研 究 生 院 学 位 论 文第一章引言 1 . 1 分组密码的研究现状及发展趋势 分组密码是现代密码学研究的一个重要分支,其诞生和发展有着重要的理论价值和广泛的实用背景。 最初出现的密码本质上是序列密码, 它已 广泛的应用于军事、 外交等方面。分组密码是以 二 十世纪七十年代d e s ( d a t a e n c ry p t i o n s t a n d a r d ) 的出 现为 标志, 在这以 后得到了广泛的的讨论和发展。 由 于d e s 的 秘钥量只有2 5 6 , 在计 算机 技术高 度发展的 今天, d e s 受到严重的安 全 威胁,事实上,1 9 9 7 年人们已成功破译由d e s 加密后的信息。1 9 9 7 年9月,美国国家标准技术研究 所( k i s t : n a t i o n a l i n s t i t u t e o f s t a n d a r d s a n d t e c h n o l o g y ) 为了 履行其 法定职责, 发 起了一场推选用于保护敏感的联帮信息的对称密钥加密算法的活动。1 9 9 8 年8月,n i s t宣布接受十五个候选算法并提请全世界密码研究界协助分析这些候选算法,包括对每个算法的安全性和效率特性进行初步检验。n i s t 考察了 这些初步的研究结果,并且选定ma r s ,r c 6 , 助n d a e l , s e r p e n t 和t w o f i s h 等 五个 算 法 作为 参加决 赛的 算 法, 经 公 众对决 赛 算法 进行更进一 步的 分析 评论, 2 0 0 0 年1 0 月, n i s t 决定 推荐助n d a e l 作为高 级 加密标准( a e s :a d v a n c e d e n c r y p tio n s t a n d a r d ) , 2 0 0 1 年1 1 月 , 殉n d a e l 被 采 纳 作 为 高 级 加 密 标 准 。 继 美 国推出a e s 计划以 后, 欧洲于2 0 0 0 年i 月 启 动了 新欧 洲签名、 完整 性和加密计划一 n e s s i e( n e w e u r o p e a n s c h e m e s f o r s i g n a t u r e s ,i n t e g r ity , a n d e n c r y p t io n ) 计 划, 以 适 应2 1 世纪 信息 安全发展的全面需求。 该计划为期三年, 投资3 3 亿欧元, 主要目 的就是通过公开征集和进行公开的、透明的测试、评估提出一套高效的密码标准,以保持欧洲工业界在密码学研究领域的领先地位。 2 0 0 1 年底, n e s s i e工作组在十七种候选的分组密码算法中, 选定了i d e a ,k h a z a d , mi s t y i , c a m e l l i a , s h a c a l , r c 6 , s a f e r + +等七种分组密码算法为分组密码的第二轮决赛算法, 2 0 0 3 年2 月2 7 日 , n e s s i e 工作组公布了 包括分组密码、认证码、杂凑函数和数字签名等在内的十七个标准算法, 其中m i s t y i , c a m e l l i a , s h a c a l三个分组密码算 法连同a e s 算法助n d a e l 一 起作 为欧洲新世纪的 分组 密码 标准 算法. 由 此可见,分组密码的设计与分析是目前国际信息安全领域的前沿热点问题。 a e s 计划和n e s s i e计划吸引了 全世界众多的密码学专家与密码学爱好者, 极大的促进了 分组密码的研究,新的设计理论和分析方法不断出现。近年我国也提出要制定相应的密码标准,其中分组密码的设计也是重要部分。 从设计角度来看,为了灵活、有效的在不同平台上进行移植,多数算法采用的是字节运算或字运算,为了有效的软件实现,采用比特运算的算法已经很少。而且由于计算机的普遍使用,多数分组算法的分组长度, 密钥长度都是字节的整数倍。由于新的分析方法不断出现,在设计时除了要能抗现有的已知攻击外,还要留有一定的余地,以抵抗以后可能会出现的未知攻击。- 第 1页国 防 科 学 技 术 大 学 研 究 生 院 学 位 论 文 从现在常见的一些分组密码算法中我们可以看出,s 一 盒是一个关键的环节。 s 一 盒的性能决定了整个密码体制的安全性。 因此设计密码性质良 好的s 一 盒具有重要的理论价值与实用价值。 为更好的设计分组密码,需要研究满足不同性质的函数类。 特别是其存在性、构造和计数问 题,以及不同性质之间的关系, 如等价、 相容、 相斥、 折衷等。 希望在一定条件下,一个函数能满足更多的性质,如高非线性正交( 多输出 ) 函数的构造就是一个值得研究的问题。 国内有一部分学者用演化理论对s 一 盒的安全性进行研究, 即由己知的s 一 盒构造具有相同密码指标或是密码性质更好的 s 一 盒。目 前对分组密码的攻击主要集中在对 s 一 盒的攻击上,如差分密码分析、线性密码分析等。 除了 对s 一 盒的 研究以 外, 现 在 对于p 置 换的 研究 也 很 多, j o a n d a e m e n 和v i n c e n t 助m e n在设计助n d a e l 就考虑到了最佳扩散的情形, 它除了 依赖于分支数外, 还与列的数目 有关。 另一方面,新的分析方法不断出现:利用密码算法的结构与采用的运算来进行分析的方法也逐步出现, 如针对基于字节运算算法的渗透攻击, 针对乘法运算出现的乘积差分等。从理论上证明抗某种分析方法的算法有可能被别的分析方法所攻破。例如:c o c o n u t 9 8算法从理论上证明了 抗差分分析, 却被回旋 攻击 ( b o o m e r a n g a t t a c k ) 攻破。 目前在分组密码的设计与分析方面还有许多理论和实际问题待继续研究和完善,这些问题主要包括: 算法部件方面:对多输出布尔函数的各种性质进行探索,如何对各种性质进行折衷而增强s 一 盒的实质安全性; 对p 置换进行研究, 采取什么样的 方式来加快扩散速度,以 增强轮函数的安全性。 算法结构方面,设计出的算法如果能证明抗某种攻击, 算法则不会太复杂,有可能存在别的分析方法; 但是算法过于复杂又不利于设计者本身分析其密码性质。如何折衷也是值得考虑的问题。 分析方面,除了从差分分析和线性分析发展起来的各种分析方法外,针对算法的整体结构,密钥扩展算法等方面的分析方法也不断出现,因此各个部分的设计准则也相应的在不断更新。 1 . 2 本文的组织与安排 本文的主要内容是对分组密码的设计与分析做一定的概括, 在此基础上, 结合t w o f i s h算法与id e a算法进行了一些初步的研究。主要创新结果如下: ( 1 ) t w o fi s h 算法中 密 钥相关s 一 盒的差 分概率 与密 钥长 度有关, 从理论上 证明了 密钥越长,所得到的s 一 盒的最大差分概率越小。 ( 2 )对t w o f i s h 算法中的密钥相关s 一 盒进行改进, 改进后的s 、 盒的最大差分概率变小。增强了抗差分分析的能力。 ( 3 )利用乘积差分对i d e a的两种变种进行分析, 分别攻破了1 4 圈的变种: i d e a - x 1 4和 8 圈的变种:i d e a - m8 , 本文的安排如下:第 2页 国 防 科 学 技 术 大 学 研 究 生 院 学 位 论 文呈 二 二 二 二 二 二 二 二 二 二 二 二 二 竺 第二章, 首先对密码及分组密码作了 一个总的概述, 然后讨论了 分组密码的设计原则与主要的分析方法。 第三章,介绍了t w o fi s h算法及其各个部分的安全设计原则,着重讨论了其密钥相关s 一 盒的差分性质,并结合i d e a算法实现混乱的原则,提出了一种新的构造密钥相关s 一 盒的方法, 理论与实验数据表明我们所构造的新的s 一 盒比原s 一 盒抗差分分析的能力更强, 而且由于混合不同群的运算,使得新构造的s 一 盒对于抗未知攻击的能力也有所增强。 第四章, 介绍了i d e a算法。自i d e a提出以来, 还没有公开报道的有效的分析方法,为了 对其进行分析, 我们利用差分分析的一种变种( 乘积差分) 对简化的i d e a进行了分析,并取得了较好的效果。i d e a 中减少一种运算,其安全性大为降低,因此,再一次的证实原来i d e a的设计是巧妙的。密码环节的少许改动可能会为安全带来巨大的隐患,所以在改动密码算法的某些环节后,必须进一步仔细分析以确保算法的安全性。第 3页国 防 科 学 技 术 大 学 研 究 生 院 学 位 论 文第二章分组密码介绍 2 . 】 分组密码的定义2 . 1 . 1 密码的作用在军事、外交与商业方面,信息的安全保密起着十分重要的作用,要达到信息保密的目的除了人员管理,政策法规的制定外,技术手段尤其是密码起着十分重要的作用。所有信息传输、 存储系统如通信、雷达、遥测遥控、计算机的内 外存储系统和内部运算,以 及计算机 通信网中的信息传输等, 都可归 结 成图2 . 1 所示的 数 字通信 系统 模型n 1纠错编码器调制器信道匿 -l ! -信宿露藻丽目丽燕阵陌藻蘸解调器 图2 . , 数字通信系统模型 在信息的传输或处理过程中,除了 指定的接收者外, 还有非指定的或非授权的用户,他们通过各种技术手段企图窃取机密信息。因此,为了保证被传送信息的安全和隐私,必须在信源编码器输出通过加密器时,用编码方法对信息进行隐藏。我们仅关心通信系统的安全性, 或说是仅分析加、解密体制, 则可把图2 . 1 简化成图2 . 2 所示的密码系统。信宿图2 . 2 密码系统图2 . 2 中的 信源包括信源编码器, 它送出的是二进制或9 进制的 信息流m 。 信息流可第 4页 国 防 科 学 技 术 大 学 研 究 生 院 学 位 论 文二二二二二二二二二二二二二二二二以被分组或不分组, 今后称信息流为明文。明文m送入加密器, 在密钥k 控制下被加密得到二进制或4 进制的序列,称为密文, 密文经信道传输到 达收端。这里的信道包括图2 . 1中的纠错编译码器、调制解调器和传输媒质,因此这是一个更为广泛义的信道。由于信道是不安全的,除了各种自 然和人为的干扰以外,还存在各种非法入侵者的主动攻击和被动攻击。因为我们只关心整个密码系统的安全性,信道中的噪声或干扰对被传送信号的影响不予考虑,认为信道中输出的二进制序列没有错误。为了 保证密钥的安全,还有一个安全的密钥信道,以传送密钥 k给指定的接收者。 密码除了上述传统的安全保密外,还逐渐的有了身份认证,数字签名等功能。2 . 1 . 2 分组密码的定义 分组密码是将明文编码后的消息按固定的长度进行分组,在密钥的作用下变换成固定长度的密文分组,每一组明文对应一组密文。当密文分组长度较长时,称为有信息扩张的分组密码:当密文长度短于明文长度时, 称为有信息压缩的分组密码;当密文长度等于明文长度时, 称为无信息扩张和压缩的分组密码。常见分组密码的明文与密文具有相同的长度,在本文中我们只考虑这种情形。 分组密码是一个函数: e : ( 0 , 1 ) k x ( o , l ) n - ( 0 , 1 ) n 有两个输入;一个k比 特的密钥k和一个n比特的明文p ,返回一个n比 特的密文c = e (k ,p ) 。 对 任 一 分 纽 密 码 和 任 一 密 钥k , 函 数e k 是 ( 0 , 1 ) “ 上 的 一 个 置 痪 。 这 意 味 着 它 是一 个 双 射, 即 0 , 1 ) n 到( 0 . 1 ) n 上的 一一 映 射, 相 应的 , 它 有逆e k i , 密 文及 其逆 都 是比 较 容易 计 算的 , 给定k ,p 可以 算出c = e ( k ,p ) , 给定k ,c 可以 算出p = e ( k ,c ) 。 由 于 安 全 性的 要 求,它 应当 还 要满 足:已 知c 和p , 从c = e ( k ,p ) 和p = e - ( k ,c ) 求出k 是困 难的。 分组密码的设计就是找到一种算法,在密钥k 的控制下从一个足够大的且够 “ 好”的置换子集合中简单灵活的选出一个置换,用来对当前输入的明文进行加密变换。 2 . 2 分组密码的整体结构特征 根据轮函数的结构, 将比较常见的密码算法分为f e i s t e l 网络结构、 s p网络结构和l m结构:按照轮变换与密钥作用的方式,又将常见的密码结构分为迭代型和密钥交替的分组密 码 。2 .2 . 1 f e i s t e l 网络结构 很多分组密码算法都是f e i s t e l 网络,这个思想要追溯到7 0 年代的早期,取一个长度为n的分组,然后把它分成长度为n / 2的两半部分:l和r ,当然 n必须是偶数。可以定义一个迭代型的分组密码算法,其第1 轮的输入取决于前一轮的输出:l ,- r ;_ , ; r ,- l 卜 , . f ( r ;. 1 , k ;)第 5页国 防 科 学 技 术 大 学 研 究 生 院 学 位 论 文 k ; 是第i 轮使用的子密钥,f 是任意轮函数。d e s ,l u c i f e r , f e al , k h u f u , k h a f r e , l ok i , gos t , c as t ,b l o w f i s h和其他分组密码算法中 看到这个概念。 它为什么会有这么大的作用?因为该函数保证了它的可逆性,异或被用来合并左半部分和轮函数的输出, 它肯定满足: l ;_ , . f ( r ;. , , k ;) . f ( r ;_ , , k ;) = l ;_ , 只要在每轮中f 的输入能重新构造,使用了这种结构的密码就可保证它是可逆的。它不管 f 函数如何,也不需要它可逆。我们能将f 函数设计成我们希望的那样复杂,并且不必实现两个不同 算法( 分别用于加解密) 。f e i s t e l 网络的结构将自 动实现这些。 总的说来: f e i s t e l 网络的优点在于加解密的相似性,少需要两轮才能改变每一个比 特5 1图2 . 3 一轮f e i s t e l 型密码 的加密过程缺点在于扩散较慢,如, 算法至2 .2 .2 s p网络结构 s p网络是 f e i s t e l网络的一种推广,s a f e r ,s h a r k , 助n d a e l 等 著 名密 码算 法 都 采 用 此结 构。 每 一轮中, 首先轮输入被作用于一个由子密钥控制的可逆函数s ( 非线性变换) , 然后再被作用于一个置换( 或一个可逆的 线性变换) p . s p 网络的结构非常清晰, s 一般被称为混淆层,主要起混淆作用。 p一般被称为扩散层, 主要起扩散作用。 这与s h a n n o n 关于密码安全性的设计原则吻合得较好。 s p网络的优点在于在明确了部件s 和p的某些密码指标后,设计者能估计s p网络的抵抗差分密码分析和线性密码分析的能力。而且与 f e i s t e l 网络相比可以得到更快的扩散速度。其缺点是加解密很难达到一致。x 川s :子密钥控制下的替换p :置换或可逆的线性变换图2 . 4 一轮s p 型密码的加密过程2 . 2 . 3 l m 结构 x u e j i a l a i 和j a m e s m a s s e y 在1 9 9 0 年公布的p e s 和1 9 9 1 年公布的i p e s 即i d e a算法在结构上为图2 . 5 所示,它与f e i s t e l 网络和s p网络都有区别,把这种类型的密码单独归为l m结构,这类密码的混乱与扩散都是来自 于ma结构,其中采用了混合不同群的运算。 当s t , s 2 , s 3 和s ; 用t , , t z , t 3 和t 4 代替时, 图2 . 5 中 所示的m a结构的 输入不第 6页国 防 科 学 技 术 大 学 研 究 生 院 学 位 论 文变, 当z 5 和z 6 不 变时, m a结 构的 输出 也 不 变, 这 种结 构 保 证了 加 解密 是 相 似的, 其安全性基于ma结构。( s i , s 2 )ma( z 5 ,z 6 )( t i ,毛)图2 . 5 l m结构中的轮函数框图 由于ma结构采用的数学运算较多,因 此软件实现时, 在一部分处理器上的效率可能不是 太高,比助n d a e l 和t w o f i s h 算法的 实 现效 率较 低, 但是这样的 设 计使 得攻 击者对算法本身进行分析变得困难。2 .2 . 4 迭代型分组密码 在迭代型分组密码中, 布尔置换是迭代的。 这种分组密码可以定义为许多与密钥相关的布尔置换的作用。 这样的布尔置换称为分组密码的轮变换。 每使用一次轮变换称为一轮。 如d e s 有1 6 轮。由于每轮均使用相同的轮变换,因此称 d e s仅有一个轮变换。 用r 表示分组密码的轮数,则有: b k = p ()k () 2 - m,那么s 一 盒的输入和输出存在着明显的线性关系;如果n 2 ,那么仅在s 一 盒的输出位中就存在着线性关系。 关于s 一 盒研究的大部分工作涉及到布尔函数的研究。 为了 保证安全, 在s 一 盒中使用的布尔函数必需满足特定的条件,它们不是线性的或仿射的,甚至也不能接近线性或仿射。0 和 i 是平衡的, 在不同的位组合中没有相关性。 这些设计准则也与b e n t 函数的研究有关:能证明b e n t 函数是一个最优的非线性函数。 虽然它们的定义很简单平直, 但研究却非常复杂。 有一个特性似乎非常重要,即是雪崩效应:当一些s 一 盒的输入位发生改变时, s 一 盒的输出位改变了多少。对布尔函数来说很容易给出条件使它满足某些雪崩特性,但构造它们非常困 难。严格雪崩准则( s t ri c t a v a l a n c h e c ri t e ri a . s a c ) 保证了当一个输入位发生改变时,输出位将有一半要发生改变。 多年前密码设计人员提出了选择s 一 盒以使其差分分布表均匀。 这将通过抹平任何特定轮的差分来使差分攻击无效。l o k i是该设计的一个例子,然而这个方法有时对差分攻击- 第 1 0 贡国 防 科 学 技 术 大 学 研 究 生 院 学 位 论 文来说 是有帮 助的,实际上更好的 方 法是 保证最大差分 概率尽可能小。 k w a n g j o k i m提出了5 个类似d e s 的s 一 盒设计准则的s 一 盒构造法则 选择一个 “ 好”的s 一 盒的方法如下4 种: ( 1 ) 随机选择。显然小的随机s 一 盒是不安全的, 但大的随 机s 一 盒可足够强。 有8 个或更多输入位的随机s 一 盒是相当强的, 1 2 一 位的s 一 盒更好。 如果s 一 盒是随机的且与密钥相关,那么s 一 盒将更强。i d e a即使用大的且与密钥相关的s 一 盒。 ( 2 ) 选择和测试。某些密码产生随机的s 一 盒, 然后根据需要的 特性来测试它。 ( 3 ) 人为构造。这个技术几乎不使用数学方法,而是使用更 直接的方法来产生 s 一 盒。b a r t p r e n e e l 认为 有趣的准则在理 论上是 不充分的 ( 对于 选择布尔 函 数的 方法来产生s 一 盒 ) ,并且需要专门的设计准则 ( 4 ) 数学方法构造。根据数学原理来产生 s 一 盒使得它们能 抗差分攻击和线性攻击,且具有好的 扩散,比 较详细的论述可参见文献 5 0 还有一些人为构造和数学构造的组合方法, 但实际争论发生在随机选择的s 一 盒和满足某些特性的 s 一 盒之间。当 然后一种方法对于抗已 知攻击( 差分 攻击和线性攻击) 来说是最优的, 但还不知道它能否提供抗未知攻击。 d e s 的设计者了解差分攻击,它的s 一 盒对于抗该攻击来说是最优的。 他们似乎是不知道线性攻击, 故d e s的s 一 盒对于抗线性攻击来说是非常弱的 6 。 在d e s 中随机选择的s 一 盒对于抗差分攻击来说更弱, 而对于抗线性攻击来说更强。p置换的设计原则 产生扩散最简单的方法是通过p 置换。最初的置换中只是将明文的位置进行置换,如换位密码将明文按字符进行换位, d e s 将明文按照比特进行换位。 现在的密码则把置换扩展 成为 整 个明 文空间 上的置换, 而 不只是 简单的 位置 换位, 如r ij n d a e l , t w o f i s h , c a m e l l i a等最近提出的分组密码。这样能起到更快的扩散作用,使一个比特的变化,影响到更多比特的变化。 p置换的作用是提供快速的扩散,实现雪崩效应。置而成, 则p 置换设计成( f z n ) m ( f z 0 ) 的一个置换,如果混淆层是m个n xn的s 一 盒并其中 ( f z n ) m = f z n x . . . x f 2 % 定义 2 . 1 令 p : ( f 2 ) a 、 的个数,称( f 2 0 ) . 是一个置换, a = ( a i , . . . , a m ) e ( f 2 ) .叭( a ) 表示非零b ( p ) =( 肠( a ) + 叭( p ( a ) ) )为置换p 的 分支数( b r a n c h n u m b e r ) .定义2 . 2 设s ( .y ) = ( f j ( x ) , . . . , f m ( x ) ) : f e n - f 2 m 是一个多 输出函 数,令-m a x m ax2 a - f 6 - f a , 0 x 。 凡 ” : s ( x 。 。 ) 。 s (x ) 一 ,8 11那么称s s 为s (.r ) 的差分均匀性。一一- 一一一-. 一.一. 一- . 一 第1 1币国 防 科 学 技 术 大 学 研 究 生 院 学 位 论 文定 义2 .3 设s ( x ) = u ( x ) , . . . , f( x ) ) : f 2 n - f 2 是一 个多 输出函数, 令n s 二m mi e l ,0 - 凡用d , ( u s(x)ax) ) 1 nsn s=万 一二二 厂 乙艺则 称n s 为s (x ) 的 非 线性 度,9 : 为s (x ) 的 最 佳 优 势。对于s p 型网 络型密码来说, 令t = b ( p ) 。 在一个差分特征中, 如果s 一 盒的输入差分不为零,涉及到则称此s 一 盒是活动的。 在线性密码分析中, 如果某个s 一 盒的一些输入或输出比特被,则称此s 一 盒是活动的。显然,对于2 轮s p网络型来说,其活动s 一 盒不少于t 个。因 此; 轮的 活 动s 一 盒 个 数 , 满 足: 当: 是 偶 数时 , r l r x t/ 2 ; r 是奇 数时, r l -l ( r - 1 ) x t/ 2 + 1 0因 此 任 意 差 分 特 征 的 概 率 ( ( s s ) ” ; 任 意 线 性 逼 近 的 优 势 - 2 ” 一 , ( q s ) ” 。 p 的 分 支 数t 越 大 ,则月 越大,分析时所需的选择明文或明 文就越多, 这增加了分析的难度,因此可以 将 p的分支数t 作为p 置换设计的一个准则5 1 。p置换的构造 对于 p置换, 显然有分支数 b ( p ) - m +1 。利用纠错码中的极大距离可分码( m d s :ma x im u m d i s t a n c e s e p a r :b l e ) 可以构造出分支数达到最佳的置换, 即t = m +1 二 如s h a r k ,s q u a r e , r ij n d a e l 和t w o f i s h 等算法中都通过列混合达到m二4 , t =5 。 还可以 利用与h a d a m a r d 矩阵有关的一些方法来保证分支数, 如在s a f e r系列密码中, 用的是多维2 一 点变 换 器 ( m u l t i- d im e n s i o n a l 2 - p o in t t r a n s f o r m d if f u s e r ) ,其中 的 混 乱 过 程 保 证有 性 质: 第 一 个 盒子到最后有一个盒子均有一条路径,而盒子本身的变换用的是 p h t ( p s e u d o h a d a m a r dt r a n s f o r m ) ; s a f e r + + 算法以 前的s a f e r 系列密码用的是2 - p h t , s a f e r + + 用的是4 - p h t 7 1 , 此时,m = 1 6 , t =i 0 ; t w o f i s h 算法在对两个3 2比特字的进行混合时也用使用了2 - p h t 。还可以利用字节之间的逻辑运算来实现 p置换,如 c a m e l l i a 和 e 2 算法考虑到字节的多个平台的有效实现, 为了 构建p 置换, 将它表示为 0 , 1 上的8“8 的矩阵p , 用字节异或就能实现。z = o+ t .z;=o u i二 z 勺 一 了 这里线性变换t为 矩 阵p 的i 行j列上的 元 素。 p 置 换的 每 个 输出 字节 都 是 输入 字 节的 一 个。这种结构中m= 8 , t =5 r,在上面叙述的三种结构中只有利用极大距离可分码使得分支数达到最佳,但它也需要达到最佳扩散的情形才能 使明文尽可能的扩散到密文中去, 具体讨论可参见文献 4 1 , 另外的两种情况没有使分支数达到最大,但分别达到1 0 和5 ,因而也能起到较快的扩散作用。-一一- 一一- 一- 一 第 1 2币国 防 科 学 技 术 大 学 研 究 生 院 学 位 论 文 2 . 4 分组密码的分析方法 线性密码分析和差分密码分析首先是针对d e s密码而提出来, 后来发展成为对众多分组密码极具威胁的分析方法,现在己经成为分组密码设计中十分重要的衡量条件,一般要求设计者 提供密码抗此两种攻击的能力。渗透攻击是针对如r ij n d a e l 等基于字块结构的 算法而提出 来的, 在对助n d a e l 的 攻击中, 这种方法要比 线性分析 和差分分析都有效,因 此在后来的设计中 ( 如t w o f i s h与c a m e l l i a 等算法) ,设计者往往会加入一些比 特操作, 如移位、循环等。随着对分组密码研究的不断深入,各种各样的新的分析方法不断出现,在n e s s i e的安全评估报告中就出现了近二十种的分析方法。2 .4 . 1 线性密码分析 线性密码分析本质上是一种己 知明文攻击, 它首先被m a t s u i 和y a m a g i s h i 用来对f e a l进行分 析8 1 , m a t s u i 也用它来对d e s 进行分析9 1 . 从概念上来说,线性分析类似于差分分析。它是要建立一个与密钥本身没有什么关系的明 密 文 之间的 概率关 系。 即 是如 果线性关系x = y 成 立的 概率为1 1 2 十疾 那么x 二 y + k成立的概率为1 / 2 士 s ,它们偏离1 / 2 的程度均为戊 可以看出没有受密钥变化的影响。 可能存在一些线性逼近,使得上述的冼e 较大,将这个线性逼近用于密码中间的几圈。在输入时设置掩码 i , 在输出置掩码 。 , 这样就可以建立一个线性关系。 这时攻击者可以 对第一圈或最后一圈的密钥比特进行猜测。 然后根据所猜测的密钥来计算i 和o处的比 特值, 如果 猜测是正 确的, 且( 1 ,0 ) 处的 实际 值( 没 有密钥猜测 ) 与 ( 1 ,0 ) 处的 希望值( 有密钥猜测 ) 符合的概率为1 1 2 1 b 。 如果偏差b 比 较大, 则通过足够多的明密文对就可以确定所猜测的密钥值是否正确,在确定了最外层的密钥以后,可以向中间的几层递进,这样最终可以破译整个密 码。 线 性 攻击的 复 杂 度 约为c / ( b 2 ) ,这里的。 是 某 个 常 数, 这 里的b 称为 偏差。 线 性 外壳技术是前 述分析方法的 扩展 1 0 , 在 相同 的 起点 和终点, 密 码中 可能 存在着多个线性特征 ( 传播路 径 ) , 这样攻击者可以 将这 些 特征的 所有偏差求和, 当 然有可能 会互相抵消 ( 有负有正 ) 。最大平均线性外壳的概率可以 用来度量线性密码分析的能力。线性密码分析仅用到一个线性逼近, 从这个基础上发展出 了 多 重线 性密码分 析1 1 1 1 1 2 1 , 如果一 个密码中 存在多 个偏差 较大的线性逼近,则用这种方法是一种较好的选择。还有一种推广方式,即是非线性密码分析,虽然有时密码的一部分可能不存在好的线性逼近,但它们通常不能保证与密钥无关,因此常把它用在密码的两端用以加强线性偏差 1 3 14 12 .4 .2 差分密码分析 差分密码分析本质上是一种选择明文攻击。 它最先是由 b i h a m 和s h a m i r 在分析d e s 时提出的 1 5 1 ,是第一个理论上可以比穷尽密钥更快恢复d e s 密钥的攻击方法。有一 对选择明文对( p o ,p ) , 它们有固定的差分 二 p o - p i , 这里的“ 一” 与明 文密钥的群运算“ + ” 互为逆。 因此有 二 ( p o + k ) 一( p i + k ) , 所以 可以 看出差分 与密钥k 的 选择无关, 第 1 3 贡国 防 科 学 技 术 大 学 研 究 生 院 学 位 论 文输入差分 在通过密码的最后一圈后将会达到某一个输出差分 ,如果这个概率足够大,则可以剥离最外面的圈, 而将攻击用于中间的圈。 做法是在第一圈处设置掩码1 , 在最后一圈设置掩码o , 这时可以猜测第一圈或最后一圈的密钥比特值,根据猜测的值可以计算在i或。 处的差分 值,如果猜测是正确的。 在有猜测的情况与没有猜测的 情况下,在( 1 ,o ) 处的吻合率 将为 p 。 如果 p 足够大, 只要有 足 够多的明密文对, 就可以 确定 猜 测是否正 确。 在确定了密码的外圈密钥以后,就可以 依次向里边的各圈进行分析,最终能够确定各圈的子密钥。差分分析的处理得杂度为c / p , 这里 c 是一个较小的常数。一般情况下,明文与密钥的结合方式为 x o r ,因此明文对之间的差分也用x o r 来计算, 在文献 1 6 1 中, 定义的群运算为模2 5 6 加,因此明文对之间的差分即为模2 5 6 减。 特征与差分是两个不同的概念,特征指的是差分在一个密码中特定的演化过程,而差分只考虑输入与最后输出的差分值。因此差分的概率实际上是众多特征概率的一种组合形式的和,因此分析时常用差分的概率而不用特征的概率。 很多时候,可以

温馨提示

  • 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
  • 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
  • 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
  • 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
  • 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
  • 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
  • 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。

最新文档

评论

0/150

提交评论