第3章 分组密码理论

1古典密码和现代密码（Cont.）现代密码算法把算法和密钥分开

密码算法可以公开，密钥保密密码系统的安全性在于保持密钥的保密性发送方接收方mm加密E解密Dc=Ek(m)m=Ek(c)密码分析密钥分配（秘密信道）kk第三章分组密码理论分组密码概述数据加密标准公开密钥算法3.1分组密码概述分组密码，就是一个明文分组被当作一个整体来产生一个等长（通常）的密文分组的密码，通常使用的是128位分组大小。分组密码的实质是，设计一种算法，能在密钥控制下，把n比特明文简单而又迅速地置换成唯一n比特密文，并且这种变换是可逆的（解密）。3.1分组密码概述(Cont.)分组密码的设计思想（C.E.Shannon)：扩散(diffusion)将明文及密钥的影响尽可能迅速地散布到较多个输出的密文中（将明文冗余度分散到密文中）。产生扩散的最简单方法是通过“置换(Permutation)”（比如：重新排列字符）。信息论的创始人克劳德·艾尔伍德·香农(ClaudeElwoodShannon)

分组密码的设计思想(Cont.)混淆(confusion)其目的在于使作用于明文的密钥和密文之间的关系复杂化，是明文和密文之间、密文和密钥之间的统计相关特性极小化，从而使统计分析攻击不能奏效。通常的方法是“代换（Substitution)”（回忆恺撒密码）。3.1分组密码概述(Cont.)分组密码设计的要求：分组长度足够大（64~128比特）密钥量要足够大（64~128）算法足够复杂（包括子密钥产生算法）加密、解密算法简单，易软、硬件实现便于分析（破译是困难的，但算法却简洁清晰）73.2DES算法原理IBM公司，70年代初提出，80年代成为国家标准DES是一种对称密钥算法，密钥长度为56bits(加上奇偶校验，通常写成64bits)是一种分组加密算法，64bits为一个分组基本思想：混乱（Confusion）和扩散（Diffusion）使用标准的算术和逻辑运算成为标准的过程发明人：IBM公司W.Tuchman和C.Meyer1971-72年研制。产生：美国商业部的国家标准局NBS1973年5月到1974年8月两次发布通告，公开征求用于电子计算机的加密算法。经评选从一大批算法中采纳了IBM的LUCIFER方案。标准化：于1976年11月被美国政府采用，DES随后被美国国家标准局和美国国家标准协会(AmericanNationalStandardInstitute，ANSI)承认。1977年1月以数据加密标准DES（DataEncryptionStandard）的名称正式向社会公布。于1977年7月15日生效。3.2数据加密标准（Cont.)3.2.1简化的DES

SimplifiedDES方案，简称S-DES方案。它是一个供教学而非安全的加密算法，它与DES的特性和结构类似，但参数小。注：1.*加密算法涉及五个函数：

(1)初始置换IP(initialpermutation)

(2)复合函数fk1，它是由密钥K确定的，具有置换和代换的运算。(3)置换函数SW

(4)复合函数fk2

(5)初始置换IP的逆置换IP-1

加密10bit密钥

解密8bit明文P108bit明文IP移位IP-1P8fkfkSWSW移位P8fkfkIPIP-18bit密文8bit密文K2K2K1K1S-DES方案示意图2*.加密算法的数学表示：

IP-1*fk2*SW*fk1*IP

也可写为

密文=IP-1（fk2(SW(fk1(IP(明文)))))

其中K1=P8(移位(P10(密钥K)))

K2=P8(移位(移位(P10(密钥K))))

解密算法的数学表示：

明文=IP-1（fk1(SW(fk2(IP(密文)))))对S-DES的深入描述（1）S-DES的密钥生成：设10bit的密钥为（k1,k2,…,k10)置换P10是这样定义的P10(k1,k2,…,k10)=(k3,k5,k2,k7,k4,k10,k1,k9,k8,k6)LS-1为循环左移1位，LS-2为循环左移2位P8=(k1,k2,…,k10)=(k6,k3,k7,k4,k8,k5,k10,k9)

按照上述条件,若K选为(1010000010),产生的两个子密钥分别为K1=(10100100),K2=(01000011)S-DES的密钥生成

10-bit密钥P10LS-1LS-1LS-2LS-2P8P8K18K255558(2)S-DES的加密运算:

初始置换用IP函数:IP=12345678 26314857

末端算法的置换为IP的逆置换:

IP-1=1234567841357286

易见IP-1(IP(X))=XS-DES加密图

8-bit明文IPE/P+S0S1P4+LR4K1844fkF4E/P+S0S18K2P4+IP-18-bit密文4844fkF44228SW中间各级算法说明Ki：每级密钥不同

数据加密标准Li-1LiRi-1Ri

Li-1

f(Ri-1,Ki)19一个简单的加密算法—异或20一个简单的加密算法—异或异或

密文：0110解密：密钥：

0101

明文：0011

已知明文、密文，怎样求得密钥？C=PKP=CK异或运算（不带进位加法）： 明文:

0011

加密： 密钥:

0101

密文：0110K=CP只知道密文，如何求得密文和密钥？函数fk，是加密方案中的最重要部分，它可表示为：fk(L,R)=(LF(R,SK),R)

其中L，R为8位输入,左右各为4位,F为从4位集到4位集的一个映射,并不要求是1-1的。SK为子密钥。对映射F来说：首先输入是一个4-位数（n1,n2,n3,n4），第一步运算是扩张/置换（E/P）运算：

E/P 41232341事实上，它的直观表现形式为：n4n1n2n3n2n3n4n18-bit子密钥：K1=(k11,k12,k13,k14,k15,k16,k17,k18),然后与E/P的结果作异或运算得：

n4+k11n1+k12 n2+k13 n3+k14 n2+k15n3+k16 n4+k17 n1+k18把它们重记为8位：

P0,0P0,1P0,2 P0,3P1,0P1,1P1,2P1,3上述第一行4位输入进S-盒S0，产生2-位的输出；第二行的4位输入进S盒S1，产生2-位的输出。两个S盒按如下定义：S盒按下述规则运算：将第1和第4的输入比特做为2-bit数，指示为S盒的一个行；将第2和第3的输入比特做为S盒的一个列。如此确定为S盒矩阵的（i,j）数。例如：（P0,0,P0,3）=(00),并且(P0,1,P0,2)=(10)确定了S0中的第0行2列（0，2）的系数为3，记为（11）输出。由S0,S1输出4-bit经置换

P4

243 1

它的输出就是F函数的输出。数据加密标准使用选择函数S将以上第j个(1≤j≤6)二进制的块（记为Zj=zj1zj2zj3zj4zj5zj6）输入第j个选择函数Sj。各选择函数Sj的功能是把6位数变换成4位数，做法是以zj1zj6为行号，zj2zj3zj4zj5为列号，查找Sj，行列交叉处即是要输出的4位数。在此以S1为例说明其功能，我们可以看到：在S1中，共有4行数据，命名为0，1、2、3行；每行有16列，命名为0、1、2、3，......，14、15列。现设输入为：

D＝101100令：列＝0110行＝10坐标为（2，6），然后在S1表中查得对应的数为2，以4位二进制表示为0010，此即选择函数S1的输出。数据加密标准012345678910111213141501441312151183106125907101574142131106121195382411481362111512973105031512824917511314100613S11011001020010输入6位输出4位使用选择函数S的例子DES概述分组加密算法：明文和密文为64位分组长度对称算法：加密和解密除密钥编排不同外，使用同一算法密钥长度：56位，但每个第8位为奇偶校验位，可忽略密钥可为任意的56位数，但存在弱密钥，容易避开采用混乱和扩散的组合，每个组合先替代后置换，共16轮只使用了标准的算术和逻辑运算，易于实现DES加密算法的一般描述输入64比特明文数据初始置换IP在密钥控制下16轮迭代初始逆置换IP-1输出64比特密文数据交换左右32比特DES加密过程初始置换IP和初始逆置换IP—1

逆初始变换。用IP-1表示，它和IP互逆。例如，第58位经过初始置换后，处于第1位，而通过逆置换，又将第1位换回到第58位。可见输入组m和IP(IP-1(m))是一样的。IP和IP—1IPIP—1Li-1（32比特）Ri-1（32比特）Li（32比特）48比特寄存器选择扩展运算E48比特寄存器子密钥Ki（48比特）32比特寄存器选择压缩运算S置换运算PRi（32比特）Li=Ri-1DES的一轮迭代扩展置换Ｅ-盒－32位扩展到48位扩展压缩替代S-盒－48位压缩到32位共8个S盒S-盒1S-盒2S-盒3S-盒4S-盒5S-盒6S-盒7S-盒8S-盒的构造S-盒的构造DES中其它算法都是线性的，而S-盒运算则是非线性的S-盒不易于分析，它提供了更好的安全性所以S-盒是算法的关键所在S-盒的构造准则S盒的每一行是整数0，…，15的一个置换没有一个S盒是它输入变量的线性函数改变S盒的一个输入位至少要引起两位的输出改变对任何一个S盒和任何一个输入X，S（X）和

S(X001100）至少有两个比特不同（这里X是长度为6的比特串）对任何一个S盒，对任何一个输入对e,f属于{0,1},

S(X)S(X11ef00)

对任何一个S盒，如果固定一个输入比特，来看一个固定输出比特的值，这个输出比特为0的输入数目将接近于这个输出比特为1的输入数目S-盒的构造要求S-盒是许多密码算法的唯一非线性部件,因此,它的密码强度决定了整个算法的安全强度提供了密码算法所必须的混乱作用如何全面准确地度量S-盒的密码强度和设计有效的S-盒是分组密码设计和分析中的难题非线性度、差分均匀性、严格雪崩准则、可逆性、没有陷门置换p-盒的构造p-盒的构造准则P置换的目的是提供雪崩效应明文或密钥的一点小的变动都引起密文的较大变化DES中的子密钥的生成密钥置换算法的构造准则设计目标：子密钥的统计独立性和灵活性实现简单速度不存在简单关系：(给定两个有某种关系的种子密钥,能预测它们轮子密钥之间的关系)种子密钥的所有比特对每个子密钥比特的影响大致相同从一些子密钥比特获得其他的子密钥比特在计算上是难的没有弱密钥Li-1（32比特）Ri-1（32比特）Li（32比特）48比特寄存器选择扩展运算E48比特寄存器子密钥Ki（48比特）32比特寄存器选择压缩运算S置换运算PRi（32比特）Li=Ri-1DES的一轮迭代DES加密算法的一般描述DES的工作模式电子密码本ECB(electroniccodebookmode)密码分组链接CBC(cipherblockchaining)密码反馈CFB(cipherfeedback)输出反馈OFB(outputfeedback)两重DES50双密钥的三重DES

（TripleDESwithTwoKeys)C=EK1(DK2(EK1(P)))P=DK1(EK2(DK1(C)))51三密钥的三重DES

（TripleDESwithThreeKeys)C=EK3(DK2(EK1(P)))=DK3(EK2(DK1(C)))DES的安全性

F函数(S-Box)设计原理未知密钥长度的争论

DES的破译

弱密钥与半弱密钥DES密钥长度关于DES算法的另一个最有争议的问题就是担心实际56比特的密钥长度不足以抵御穷举式攻击，因为密钥量只有个

早在1977年，Diffie和Hellman已建议制造一个每秒能测试100万个密钥的VLSI芯片。每秒测试100万个密钥的机器大约需要一天就可以搜索整个密钥空间。他们估计制造这样的机器大约需要2000万美元VLSI:very-large-scale-integration

（超大规模集成电路）DES密钥长度在CRYPTO’93上，Session和Wiener给出了一个非常详细的密钥搜索机器的设计方案，这个机器基于并行运算的密钥搜索芯片，所以16次加密能同时完成。花费10万美元，平均用1.5天左右就可找到DES密钥.CRYPTO是国际密码讨论年会(AnnualInternationalCryptologyConference)的常用英文缩写。它是密码学中最大的研讨会

美国克罗拉多洲的程序员Verser从1997年2月18日起，用了96天时间，在Internet上数万名志愿者的协同工作下，成功地找到了DES的密钥，赢得了悬赏的1万美元DES密钥长度1998年7月电子前沿基金会（EFF）使用一台25万美圆的电脑在56小时内破译了56比特密钥的DES1999年1月RSA数据安全会议期间，电子前沿基金会用22小时15分钟就宣告破解了一个DES的密钥弱密钥与半弱密钥弱密钥:EKEK=I

，DES存在4个弱密钥即：半弱密钥:EK1=EK2

，至少有12个半弱密钥即：弱密钥•初始密钥被分成两部分，每部分都单独做移位。如果每一部分的每一位都是0或都是1，则每一圈的子密钥都相同。这样的密钥被称为弱密钥。•DES存在4个弱密钥半弱密钥•有些成对的密钥会将明文加密成相同的密文，即一对密钥中的一个能用来解密由另一个密钥加密的消息，这种密钥称作半弱密钥。其它常规分组加密算法TripleDESIDEARC5RC6AES其他一些较实用的算法，如Blowfish，CAST，以及RC2等目录分组密码概述数据加密标准公开密钥算法63密钥分配（KeyDistribution）保密通信双方需共享密钥共享密钥要经常更换A选择密钥并手工传递给B第三方C选择密钥分别手工传递给A,B用A,B原有共享密钥传送新密钥与A,B分别有共享密钥的第三方C传送新密钥给A和/或BN个用户集需要N(N-1)/2个共享密钥密钥分发中心(KeyDistributionCenter)64密钥分发中心（KDC）每个用户与KDC有共享密钥(MasterKey)N个用户,KDC只需分发N个MasterKey两个用户间通信用会话密钥(SessionKey)用户必须信任KDCKDC能解密用户间通信的内容（1）密钥管理量的困难传统密钥管理：两两分别用一对密钥时，则n个用户需要C(n,2)=n(n-1)/2个密钥，当用户量增大时，密钥空间急剧增大。如:n=100时，C(100,2)=4,995n=5000时，C(5000,2)=12,497,500（2）数字签名的问题传统加密算法无法实现抗抵赖的需求。问题的提出公开密钥算法

公开密钥算法是非对称算法，即密钥分为公钥和私钥，因此称双密钥体制双钥体制的公钥可以公开，因此也称公钥算法公钥算法的出现，给密码的发展开辟了新的方向。公钥算法虽然已经历了20多年的发展，但仍具有强劲的发展势头，在鉴别系统和密钥交换等安全技术领域起着关键的作用公开密钥算法的提出公钥密码学是1976年由Diffie和Hellman在其“密码学新方向”一文中提出的，见文献：

W.DiffieandM.E.Hellman,NewDirectrionsinCryptography，

IEEETransactiononInformationTheory,V.IT-22.No.6,Nov1976,PP.644-654公开密钥算法的提出RSA公钥算法是由Rivest,Shamir和Adleman在1978年提出来的参见CommunitionsoftheACM.Vol.21.No.2.Feb.1978,PP.120-126该算法的数学基础是初等数论中的Euler（欧拉)定理，并建立在大整数因子的困难性之上加密与解密由不同的密钥完成加密：解密：知道加密算法，从加密密钥得到解密密钥在计算上是不可行的两个密钥中任何一个都可以作为加密而另一个用作解密公开密钥算法的基本要求基于公开密钥的加密过程用公钥密码实现保密

用户拥有自己的密钥对(KU,KR)

公钥KU公开，私钥KR保密

基于公开密钥的鉴别过程用公钥密码实现鉴别

条件：两个密钥中任何一个都可以用作加密而另外一个用作解密鉴别：

鉴别＋保密

公开密钥算法公钥算法的种类很多，具有代表性的三种密码：

基于整数分解难题（IFP）的算法体制基于离散对数难题（DLP）算法体制基于椭圆曲线离散对数难题（ECDLP）的算法体制RSA算法76基本思想和要求涉及到各方：发送方、接收方、攻击者涉及到数据：公钥、私钥、明文、密文公钥算法的条件：产生一对密钥是计算可行的已知公钥和明文，产生密文是计算可行的接收方利用私钥来解密密文是计算可行的对于攻击者，利用公钥来推断私钥是计算不可行的已知公钥和密文，恢复明文是计算不可行的(可选)加密和解密的顺序可交换•1977年由RonRivest、AdiShamir和LenAdleman发明，1978年公布•是一种分组加密算法。

–明文和密文在0~n-1之间,n是一个正整数•应用最广泛的公钥密码算法•只在美国申请专利，且已于2000年9月到期RSA算法RSA算法的实现实现的步骤如下：Bob为实现者

(1)Bob寻找出两个大素数p和q(2)Bob计算出n=pq和φ(n)=(p-1)(q-1)(3)Bob选择一个随机数e(0<e<φ(n))，满足gcd(e,φ(n))=1(4)Bob使用辗转相除法计算d=e-1(modφ(n))(5)Bob将n和e设为公钥,在目录中公开,将p、q、d设为秘密的Alice将m加密为c≡me(modn)，并将c发送给Bob；Bob通过计算m≡cd(modn)解密。素数：只能被1和它本身整除的自然数；否则为合数。每个合数都可以唯一地分解出素数因子6=2·3999999=3·3·3·7·11·13·3727641=131·121GCD通常表示最大公约数(greatestcommondivisor，简写为gcd

辗转相除法,又名欧几里得算法（Euclideanalgorithm）乃求两个正整数之最大公因数的算法。这是已知最古老的算法,其可追溯至前300年。首次出现于欧几里得的《几何原本》（第VII卷，命题i和ii）中，而在中国则可以追溯至东汉出现的《九章算术》。这算法并不需要把二数作质因数分解。

辗转相除法求最大公约数，是一种比较好的方法，比较快。对于52317和75569两个数，你能迅速地求出它们的最大公约数吗？一般来说你会找一找公共的因子，这题可麻烦了，不好找，质因子大。现在教你用辗转相除法来求最大公约数。先用较大的75569除以52317，得商1，余数23252，再以52317除以23252，得商2，余数是5813，再用23252做被除数，5813做除数，正好除尽得商数4。这样5813就是5569和52317的最大公约数。算法描述:

a÷b，令r为所得余数（0≤r＜b）若r=0，算法结束；b

即为答案。a

mod

b”是指取a÷b

的余数。例如，123456和7890的最大公因数是6,这可由下列步骤看出：

RSA算法编制参数T={N}；私钥SK=P,Q,D；公钥PK=E；设：明文M，密文C，那么：用公钥作业：MEmodN=C

用私钥作业：CDmodN=MRSA算法举例设p=7,q=17,n=7*17=119;参数T={n=119};φ(n)=(7-1)(17-1)=96;选择e=5,gcd(5,96)=1;公钥pk=5;计算d,(d*e)mod96=1;d=77;私钥sk=77;设:明文m=19

加密：（19）5mod119=66

脱密：（66）77mod119=19模p运算

给定一个正整数p，任意一个整数n，一定存在等式

n=kp+r

其中k、r是整数，且0≤r<p，称呼k为n除以p的商，r为n除以p的余数。

对于正整数p和整数a,b，定义如下运算：

取模运算：amodp表示a除以p的余数。

模p加法：(a+b)modp，其结果是a+b算术和除以p的余数，也就是说，(a+b)=kp+r，则(a+b)modp=r。

模p减法：(a-b)modp，其结果是a-b算术差除以p的余数。

模p乘法：(a×b)modp，其结果是a×b算术乘法除以p的余数。

86RSA:例2选择两个素数:p=17&q=11计算

n=pq=17×11=187计算ø(n)=(p–1)(q-1)=16×10=160选择e:gcd(e,160)=1;其中e=787如果待加密的消息M=88(注意：88<187)加密：C=887mod187=11

解密:M=1123mod187=88

RSA：例2RSA：例3Bob选择p=885320693，q=238855417，则可以计算

n=p*q=211463707796206571，设加密系数为e=9007，将n和e发送给Alice。假设Alice传递的信息是cat。令a=01c=03t=20，则cat=030120=30120。

Alice计算：c≡me≡301209007≡113535859035722866(modn)

她将c传给Bob。RSA：例3Bob已知p和q的值，他用扩展欧几里德算法计算d：

de≡1(mod(p-1)(q-1))，得到

d=116402471153538991

然后Bob计算：

cd≡113535859035722866116402471153538991≡30120(modn)

由此他可以得到最初的信息。RSA算法的安全性分析密码分析者攻击RSA体制的关键点在于如何分解n若分解成功使n=pq，则可以算出φ(n)＝（p-1)(q-1)，然后由公开的e，解出秘密的d若使RSA安全，p与q必为足够大的素数，使分析者没有办法在多项式时间内将n分解出来RSA算法的