第四讲单钥体制二分组密码.ppt
《第四讲单钥体制二分组密码.ppt》由会员分享,可在线阅读,更多相关《第四讲单钥体制二分组密码.ppt(97页珍藏版)》请在三一文库上搜索。
1、2019/4/10,1,第四讲 单钥体制(二) 分组密码,一、分组密码概述 二、代换网络 三、迭代分组密码 四、DES 五、IDEA 六、其它重要分组密码 七、分组密码运行模式 八、分组密码的组合 九、分组密码的分析 十、 AES,2019/4/10,2,第四讲 单钥体制(二) 分组密码,分组密码:单钥分组密码是许多系统安全的一个重要组成部分。分组密码易于构造拟随机数生成器、流密码、消息认证码(MAC)和杂凑函数等,还可进而成为消息认证技术、数据完整性机构、实体认证协议以及单钥数字签字体制的核心组成部分。实际应用中对于分组码可能提出多方面的要求,除了安全性外, 还有运行速度、存储量(程序的长度
2、、数据分组长度、高速缓存大小)、实现平台(硬、软件、芯片)、运行模式等限制条件。这些都需要与安全性要求之间进行适当的折衷选择。 内容:分组密码的基本概念、设计原理、工作原理、运行模式、以及一些标准算法, DES、IDEA、SAFER K-64、RC-5、Twofish等。,2019/4/10,3,第四讲 单钥体制(二)分组密码 一、分组密码概述,分组密码:明文序列x1, x2, xi, 加密函数E: VnKVn 1这种密码实质上是字长为m的数字序列的代换密码。 密钥k=(k0, k1, kt-1 ) 密钥k=(k0, k1, kt-1 ) 明文 密文 明文 x=(x0, x1, xm-1) y
3、=(y0, y1, , yn-1) x=(x0, x1, xm-1) 加密算法 解密算法 图4-1-1 分组密码框图,2019/4/10,4,第四讲 单钥体制(二)分组密码 一、分组密码概述,通常取n=m。若nm,则为有数据扩展的分组密码。若nm,则为有数据压缩。在二元情况下,x和y均为二元数字序列,它们的每个分量xi,yiGF(2)。我们将主要讨论二元情况。将长为n的二元x和y表示成小于2n的整数,即: (411) (412) 则分组密码就是将 映射为 , 即为到其自身的一个置换,即 y=(x) (413),2019/4/10,5,第四讲 单钥体制(二)分组密码 一、分组密码概述,置换的选择
4、由密钥k决定。所有可能置换构成一个对称群SYM(2n),其中元素个数或密钥数为 (414) 例如n=64 bit时, (264)!10347380000000000000000(1010)20 为表示任一特定置换所需的二元数字位数为 log2(2n!)(n1.44)2n=O(n2n) (bit) (415) 即密钥长度达n2 n bit,n=64时的值为64264=270 bit,DES的密钥仅为56 bit,IDEA的密钥也不过为128 bit。实用中的各种分组密码(如后面要介绍的DES、IDEA、RSA和背包体制等)所用的置换都不过是上述置换集中的一个很小的子集。,2019/4/10,6,
5、第四讲 单钥体制(二)分组密码 一、分组密码概述,分组密码的设计问题在于找到一种算法,能在密钥控制下从一个足够大且足够好的置换子集中,简单而迅速地选出一个置换,用来对当前输入的明文的数字组进行加密变换。设计的算法应满足下述要求: (1) 分组长度n要足够大,防止明文穷举攻击法奏效。 (2) 密钥量要足够大,尽可能消除弱密钥并使所有密钥同等地好,以防止密钥穷举攻击奏效。 (3) 由密钥确定置换的算法要足够复杂,充分实现明文与密钥的扩散和混淆,没有简单的关系可循,要能抗击各种已知的攻击。,2019/4/10,7,第四讲 单钥体制(二)分组密码 一、分组密码概述,设计的算法应满足下述要求: (4)
6、加密和解密运算简单,易于软件和硬件高速实现。 (5) 数据扩展。一般无数据扩展,在采用同态置换和随机化加密技术时可引入数据扩展。 (6) 差错传播尽可能地小。 实现上述几点要求并不容易。首先,图8-1-1的代换网络的复杂性随分组长度n呈指数增大,常常会使设计变得复杂而难以控制和实现;实际中常常将n分成几个小段,分别设计各段的代换逻辑实现电路,采用并行操作达到总的分组长度n足够大,这将在下面讨论。其次,为了便于实现,实际中常常将较简单易于实现的密码系统进行组合,构成较复杂的、密钥量较大的密码系统。,2019/4/10,8,第四讲 单钥体制(二)分组密码 一、分组密码概述,Shannon曾提出了以
7、下两种可能的组合方法: “概率加权和”的方法。设有r个子系统,以T1, T2, Tr表示,相应被选用的概率为p1, p2, , pr,其中。其概率和系统可表示成 T=p1T1+p2T2+prTr (416) 显然,系统T的密钥量将是各子系统密钥量之和。 “乘积”方法。设有两个子密码系统T1和T2,则先以T1对明文进行加密,然后再以T2对所得结果进行加密。其中,T1的密文空间需作为T2的“明文”空间。乘积密码可表示成 T=T1T2 (417) 利用这两种方法可将简单易于实现的密码组合成复杂的更为安全的密码。,2019/4/10,9,第四讲 单钥体制(二)分组密码二、代换网络,代换网络。在密码学研
8、究中,代换网络起着中心作用。明文和密文字母之间的双射变换可以由一个输入和输出字母表相同的代换网络实现。一个代换网络可看作是有n个多元输入和n个多元输出变量的黑盒子,其每个输出变量都是n个输入的布尔函数。代换网络的研究涉及电话交换、开关函数理论和密码学等多个领域。 代换是输入集A到输出A上的双射变换: fk:AA (421) 式中,k是控制输入变量,在密码学中则为密钥。实现代换fk的网络称作代换网络。双射条件保证在给定k下可从密文惟一地恢复出原明文。,2019/4/10,10,第四讲 单钥体制(二)分组密码 二、代换网络,代换fk的集合: S=fkkK (422) K是密钥空间。S完全表示了一个
9、代换网络特性。如果网络可以实现所有可能的2n!个代换,则称其为全代换网络。显然,密钥个数必须满足条件: k2n! (423) 密码设计中需要先定义代换集S,即确定加密用的代换网络,而后还需定义解密变换集,即逆代换网络S-1,它以密文y作为输入矢量,其输出为恢复的明文矢量x。如前所述,实用密码体制的集合S中的元素个数都远小于2n!。要实现全代换网络并不容易。因此实用中常常利用一些简单的基本代换,通过组合实现较复杂的、元素个数较多的代换集。,2019/4/10,11,第四讲 单钥体制(二)分组密码 二、代换网络,常用的基本代换有下述几种。 1 左循环移位(Shift left circular)
10、2 右循环移位(Shift right circular)代换 3 模2n加1(Addition with module)代换 4线性变换(Linear transformation)A 5换位(Transposition)代换 6连线交叉或坐标置换T 7仿射变换(Affine transform) 一般二元代换网络可用布尔函数描述。,2019/4/10,12,第四讲 单钥体制(二)分组密码二、代换网络,代换盒:简称为S盒。 在密码设计中,可选n=rn0,其中r和n0都为正整数,将设计n个变量的代换网络化为设计r个较小的子代换网络,而每个子代换网络只有n0个输入变量。称每个子代换网络为代换盒(
11、Substitution Box),例如,在DES的S盒 x5 x4 x3 x2 x1 x0 S盒 图4-2-3 S盒 y3 y2 y1 y0,2019/4/10,13,第四讲 单钥体制(二)分组密码 二、代换网络,DES的S盒设计经验表明,实现代换所需最小的逻辑单元电路(如小项)数目可作为排除弱(安全性差)盒函数的指标或直观依据。如果实现盒的逻辑函数的小项个数低于某个确定的阈值,其安全性就值得怀疑。对S盒提出的设计准则越严格,其逻辑表达式中的小项数就越大,最多可达64项(即所有可能达26个选取)。 以DES体制中的8个S盒之一,即第一个S1盒为例说明其输入输出之间的代换关系,参看图4-2-4
12、。 DES的S盒的最终设计,其小项表达式中的项数在55左右,比开始的增加了10项。从LSI设计角度出发,应使其尽可能在一个基片上实现。小项数越多,实现也就越复杂。有了小项表达式后,还要进行布尔式化简,以利于实现。,2019/4/10,14,第四讲 单钥体制(二)分组密码 二、代换网络,图4-2-4 DES的S1-盒的输入和输出关系 x5 x0 x5 x4 x3 x2 x1 x0 1 0 1 0 1 1 0 0 列号 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 行号 0 14 4 13 1 2 15 11 8 3 10 6 12 5 9 0 7 1 0 15 7
13、4 14 2 13 1 10 6 12 11 9 5 3 8 2 4 1 14 8 13 6 2 11 15 12 9 7 3 10 5 0 3 15 12 8 2 4 9 1 7 5 11 2 14 10 0 6 13 (y3 , y2, y1 , y0)=(0,0,1,0),2019/4/10,15,第四讲 单钥体制(二)分组密码 二、代换网络,根据什么准则设计S盒以保障安全性是一个复杂问题。迄今为止,有关方面未曾完全公开有关DES的S盒的设计准则。Branstead等曾披露过下述准则: P1 S盒的输出都不是其输入的线性或仿射函数。 P2 改变S盒的一个输入比特,其输出至少有两比特产生变
14、化,即近一半产生变化。 P3 当S盒的任一输入位保持不变,其它5位输入变化时(共有25 =32种情况),输出数字中的0和1的总数近于相等。 这三点使DES的S盒能够实现较好的混淆。,2019/4/10,16,第四讲 单钥体制(二)分组密码 二、代换网络,当S盒设计之后,下一个问题是如何将几个S盒组合起来构成一个n值较大的组。一般是将几个S盒的输入端并行,并通过坐标置换(P-盒)将各S盒输出比特次序打乱,再送到下一级各S盒的输入端,起到了Shannon所谓的“扩散”作用。S盒提供非线性变换,将来自上一级不同的S盒的输出进行“混淆”。例如,对于重量为1的输入矢量,经过S盒的混淆作用使1的个数增加,
15、经过P-盒的扩散作用使1均匀地分散到整个输出矢量中,从而保证了输出密文统计上的均匀性,这就是Shannon的乘积密码的作用。这种用S盒和P-盒交替在密钥控制下组成的复杂的、分组长度n足够大的密码设计方法是由IBM的研究人员根据Shannon思想提出的,最初在LUCIFER密码系统中实现,选用n=128,n0 =4,后发展成为DES。,2019/4/10,17,第四讲 单钥体制(二)分组密码二、代换网络,Feistel网络:Feistel提出,将n bit明文分成为左右各半、长为n/2 bit的段,以L和R表示。然后进行多轮迭代,其第i轮迭代的输出为前轮输出的函数 Li =Ri-1 Ri =Li
16、-1 f(Ri-1, Ki) 式中,Ki是第i轮用的子密钥,f是任意密码轮函数。称这种分组密码算法为Feistel网络(Feistel Network) ,它保证加密和解密可采用同一算法实施,因而被广泛用于多种分组密码体制中。 在设计整个分组密码的代换网络时,要求输出的每比特密文都和输入的明文及密钥各比特有关,这对增加密码强度有好处。,2019/4/10,18,第四讲 单钥体制(二)分组密码 三、迭代分组密码,迭代分组密码 迭代密码:若以一个简单函数f,进行多次迭代,如图4-3-1所示,就称其为迭代密码。每次迭代称作一轮(Round)。相应函数f称作轮函数。每一轮输出都是前一轮输出的函数,即y
17、(i)=fy(i-1), k(i),其中k(i)是第i轮迭代用的子密钥,由秘密密钥k通过密钥生成算法(产生。DES为16轮,IDEA为8轮。 y(0) = x y(1) y(2) y(r-1) y(r) = y 图4-3-1 以轮函数 f f f f构造的r轮迭代密码 k(1) k(2) k(r) 子 密 钥 产 生 器 k,2019/4/10,19,第四讲 单钥体制(二)分组密码 三、迭代分组密码,对合密码(Involution Cipher)。它是加密所用的一种加密函数f(x, k),实现F2n F2t F2n的映射。其中,n是分组长,t是密钥长。若对每个密钥取值都有ff(x, k),k=
18、x,即 f(x, k)2 =I (恒等置换) (431) 则称其为对合密码,以fI表示。 I型迭代分组密码:以对合密码函数构造的多轮迭代分组密码。 显然,对合加密函数fI,在子密钥k(1),.,k(r)控制下对明文x进行r轮迭代加密运算E(x ,k)得到密文y;而以密码函数fI在逆序子密钥k(r),k(1)作用下,进行r轮迭代运算,就给出恢复的明文x。后r轮运算就作为解密运算D(y, k)。即有DEx, k,k=fIfIx, k,k=fI 2x, k=Ix=x (432),2019/4/10,20,第四讲 单钥体制(二)分组密码 三、迭代分组密码,其中 Ex, k=fIfI fI fIx, k
19、(1),k(2) ,k(r-1),k(r) (433) Dy, k =fI fI fIfIy, k(r),k(r-1) ,k(2) ,k(1) (434) 缺点:对任意偶数轮变换,若对所有i选择k(2i-1) =k(2i),则加密的变换等价于恒等变换,在实用中需要避免这类密钥选择。 对合置换:令P是对x的置换,即P: F2n F2n ,若对所有xGF(2n),有PPx=x,即PP=I(恒等置换),以PI表示。 II型迭代分组密码:每轮采用对合密码函数和对合置换级连,即 Fx, kPI fI x, k (435) 并选解密子密钥与加密子密钥逆序,则加密解密可用同一器件完成。DES、FEAL和LO
20、KI等都属此类。,2019/4/10,21,第四讲 单钥体制(二)分组密码 三、迭代分组密码,群密码:若密钥与明文、密文取自同一空间GF(2 n),且 y=xk (436) 式中,是群运算,则称其为群密码。显然x可通过k的逆元 求得 x=yk-1 (437) III型迭代分组密码:令xk为一群密码,令fI(x, kB)为一对合密码,以 Fx, kfI (xkA, kB) (438) 为迭代函数,可以构造一种新的多轮迭代分组密码,如图4-3-2所示。注意,在最后一轮中,另外加了一次群密码运算,用以保证整个加、解密的对合性。,2019/4/10,22,第四讲 单钥体制(二)分组密码 三、迭代分组密
21、码,轮函数F F y(1) y(r-1) (a) 加密 x fI fI y kA(1) kB(1) kA(r) kB(r) kA(r+1) F F y fI fI x (b) 解密 kA(r+1) -1 kB(r) (kA(r)-1 kB(1) (kA)-1 图 4-3-2 型迭代分组密码,2019/4/10,23,第四讲 单钥体制(二)分组密码 三、迭代分组密码,IV型迭代分组密码: 显然,若以 kA(1), kB(1), kA(2), kB(2) ,kA(r), kB(r), kA(r+1)作为加密子密钥,以(kA(r+1)-1 , kB(r) ,(kA(r)-1 ,kB(r-1) , (
22、kA(2) -1, kB(1), (kA(1) -1为解密钥,则加、解密类似,可用同一器件实现。PES(Proposal Block Encryption Standard)属此类。 在这类密码的轮函数基础上,再增加一个对合置换PI,构成IV型迭代分组密码的轮函数 Fx, kPIfI xkA, kB (439),2019/4/10,24,第四讲 单钥体制(二)分组密码 三、迭代分组密码,轮函数F y(1) y(r-1) F x fI PI fI PI PI y kA(1) kB(1) kA(r) kB(r) kA(r+1) a) 加密 F F y fI PI fI x (b) 解密 (kA(r
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 第四 讲单钥 体制 分组 密码
链接地址:https://www.31doc.com/p-2573597.html