信息安全导论(4-2_密码基础-对称密码)

1、1密码基础对称密码信息安全导论（模块信息安全导论（模块4密码基础）密码基础）2现代密码学n密码体制的分类：密码体制的分类：n对称、非对称对称、非对称n分组、序列分组、序列3分组密码的设计原则n混乱混乱：所设计的密码应使得：所设计的密码应使得密钥密钥、明文明文以及以及密密文文之间的依赖关系相当复杂，以至于这种依赖之间的依赖关系相当复杂，以至于这种依赖性对密码分析者来说是无法利用的性对密码分析者来说是无法利用的n扩散扩散：所设计的密码应使得：所设计的密码应使得密钥的每一位密钥的每一位数字数字影响影响密文的许多位密文的许多位数字，以防止对密钥进行逐数字，以防止对密钥进行逐段破译，而且段破译，而且明文

2、的每一位明文的每一位数字也应影响数字也应影响密文密文的许多位的许多位数字，以便隐蔽明文数字统计特性数字，以便隐蔽明文数字统计特性4典型的分组密码算法DESnDES的历史的历史n1971年，年，IBM，由，由Horst Feistel领导的密领导的密码研究项目组研究出码研究项目组研究出LUCIFER算法，并应算法，并应用于商业领域用于商业领域n1973年美国标准局征求标准，年美国标准局征求标准，IBM提交结提交结果，之后被选为数据加密标准果，之后被选为数据加密标准5分组密码的例子DESnDES是是1975年被美国联邦政府确定为年被美国联邦政府确定为非敏感信息的加密标准，它利用非敏感信息的加密标准

3、，它利用64比特比特长度的密钥长度的密钥K来加密长度为来加密长度为64比特的明比特的明文，得到文，得到64比特长的密文比特长的密文n1997年，由于计算机技术迅速发展，年，由于计算机技术迅速发展，DES的密钥长度已经太短，的密钥长度已经太短，NIST建议建议停止使用停止使用DES算法作为标准算法作为标准. 目前，二目前，二重重DES和三重和三重DES仍然广泛使用仍然广泛使用56nDES算法的整体结构算法的整体结构Feistel结构结构nDES算法的轮函数算法的轮函数nDES算法的密钥编排算法算法的密钥编排算法nDES的解密变换的解密变换7DES算法的整体结构Feistel结构7K1K168DE

4、S算法的整体结构Feistel结构1. 1. 给定明文，通过一个固定的初始置换给定明文，通过一个固定的初始置换IPIP来重排输来重排输入明文块入明文块P P中的比特，得到比特串中的比特，得到比特串P P0 0=IP(P)=L=IP(P)=L0 0R R0 0，这里这里L L0 0和和R R0 0分别是分别是P P0 0的前的前3232比特和后比特和后3232比特比特8IP58504234261810260524436282012462544638302214664564840322416857494133251791595143352719113615345372921135635547393

5、123157初始置换初始置换IP9DES算法的整体结构Feistel结构2. 2. 按下述规则进行按下述规则进行1616次迭次迭代，即代，即 1i16 1i16 这里这里 是对应比特的模是对应比特的模2 2加，加，f f是一个函数（称为轮函是一个函数（称为轮函数）；数）；1616个长度为个长度为4848比特的子密钥比特的子密钥K Ki i(1i16)(1i16)是由密钥是由密钥k k经密钥编排函数计算出来经密钥编排函数计算出来的的. .ii-1ii-11LR RL(,)iif RKLi-1Ri-1f+LiRiki第第16轮迭代左右两块不交轮迭代左右两块不交换换10DES算法的整体结构Feist

6、el结构10IP-140848165624643239747155523633138646145422623037545135321612936444125220602835343115119592734242105018582633141949175725初始置换的初始置换的逆置换逆置换IP3.3.对比特串对比特串R R1616L L1616使用逆置换使用逆置换IPIP-1-1得到密文得到密文C C，即，即C=IPC=IP-1 -1 (R(R1616L L1616) )。11分组密码的轮函数n函数函数f f以长度为以长度为3232比特串比特串R Ri-1i-1作为第一输入，作为第一输入，以长

7、度为以长度为4848比特串比特串K Ki i作为第二个输入，产生作为第二个输入，产生长度为长度为3232比特的输出：比特的输出：1112分组密码的轮函数Ri-1KiE (Ri-1)B1B2B3B4B5B6B7B8S1S2S3S4S5S6S7S8C1C2C3C4C5C6C7C8f (Ri-1 ,Ki)+PEE扩展扩展S盒代换盒代换P置换置换32323246484848密钥加密钥加13分组密码的轮函数E扩展扩展：Ri-1根据扩展规则扩展为根据扩展规则扩展为48比特长度的串；比特长度的串；E：比特：比特选择表选择表3212345456789891011121312131415161716171819

8、20212021222324252425262728292829303132114E扩展（32bit扩展到48bit）1234567812345679884599132323215分组密码的轮函数密钥加密钥加：计算：计算 ，并将结果写成，并将结果写成8个比个比特串，每个特串，每个6比特，比特，B=B1B2B3B4B5B6B7B8.1()iiE RK16分组密码的轮函数nS盒代换盒代换：6入入4出，查表出，查表n8个个S盒盒S1S8. 每个每个S盒是一个固定的盒是一个固定的4*16阶矩阵，其元素取阶矩阵，其元素取015之间的整数之间的整数.n输入输入6比特比特b1b2b3b4b5b6，输出如下，

9、输出如下 1) b1b6两个比特确定了两个比特确定了S盒的行盒的行 2) b2b3b4b5四个比特确定了四个比特确定了S盒的列盒的列 3) 行、列确定的值即为输出行、列确定的值即为输出161717S1 1441312151183106125907015741521311061211953841148136211151297310501512824917511314100613S2 1518146113497213120510313471528141201106911501471110413158126932151381013154211671205149S3 10091463155113127

10、11428137093461028514121115113649815301112125101471101306987415143115212S4 7131430691012851112415128115615034721211014910690121171315131452843150610113894511127214S52124171011685315130149141121247131501510398642111101378159125630141181271142136150910453S61211015926801334147511101542712956113140113891

11、415528123704101131164321295151011141760813S74112141508133129751061130117491101435122158614111312371410156805926111381410795015142312S813284615111109314501271151381037412561101492711419121420610131535821147410813151290356111818S1 14413121511831061259070157415213110612119538411481362111512973105015128

12、24917511314100613例如：输入例如：输入101100，行，行”10“2，列，列”0110“6 输出输出2，即，即0010例如：输入例如：输入111001，行，行”11“3，列，列”1100“12 输出输出10，即，即101019分组密码的轮函数19P置换置换1672021291228171152326518311028241432273919133062211425P置换置换：长度为：长度为32比特串比特串C=C1C2C3C4C5C6C7C8, 根据固定置换根据固定置换P(*)进行置换，得到比特串进行置换，得到比特串P(C).20DES算法的密钥编排算法根据密钥根据密钥K来获得来

13、获得每轮中所使用每轮中所使用的子密钥的子密钥Ki20KPC-1C0D0C1D1C16D16LS1LS1LS2LS16LS2LS16PC-2PC-2K1K16642828564821DES算法的密钥编排算法1. 给定给定64比特密比特密钥钥K，根据固定，根据固定的置换的置换PC-1来来处理处理K得到得到C0D0，其中，其中C0和和D0分别由最分别由最前和最后前和最后28比比特组成特组成PC-15749413325179158504234261810259514335271911360524436635547393123157625446383022146615345372921135282012

14、422DES算法的密钥编排算法2. 计算计算Ci=LSi(Ci-1)和和Di=LSi(Di-1)， 且且Ki=PC-2(CiDi)，LSi表示表示循环左移循环左移两个或一两个或一个位置，具体地，如果个位置，具体地，如果i=1,2,9,16就移一个位就移一个位置，否则就移两个位置置，否则就移两个位置 PC-2是另一个固定的置换是另一个固定的置换.23DES算法的密钥编排算法PC-2141711241532815621102319124268167272013241523137475530405145334844493956345346425036293224DES的解密变换DES的解密与加密一样

15、使用的解密与加密一样使用相同的算法相同的算法，它以密文它以密文y作为输入，但以相反的作为输入，但以相反的顺序使顺序使用密钥用密钥编排编排K16,K15,K1, 输出的是明文输出的是明文x25DES加密的例子n设设16进制明文进制明文X为：为：0123456789ABCDEFn密钥密钥K为：为：133457799BBCDFF1n去掉奇偶校验位后，以二进制表示的去掉奇偶校验位后，以二进制表示的Kn加密后的密文为：加密后的密文为：26nDES的的核心核心是是S盒，除此之外的计算是线性的盒，除此之外的计算是线性的nS盒作为该密码体制的盒作为该密码体制的非线性非线性组件对安全性至组件对安全性至关重要。关

16、重要。nS盒的设计准则：盒的设计准则：nS盒不是它输入变量的线性函数盒不是它输入变量的线性函数n改变改变S盒的一个输入位至少要引起两位的输出改变盒的一个输入位至少要引起两位的输出改变n对任何一个对任何一个S盒，如果固定一个输入比特，其它输盒，如果固定一个输入比特，其它输入变化时，输出数字中入变化时，输出数字中0和和1的总数近于相等。的总数近于相等。27分组密码的分析方法n如果密码分析者能够确定正在使用的密如果密码分析者能够确定正在使用的密钥，则他就可以像合法用户一样阅读所钥，则他就可以像合法用户一样阅读所有消息，则称该密码是有消息，则称该密码是完全可破译完全可破译的的n如果密码分析者仅能从所窃

17、获的密文恢如果密码分析者仅能从所窃获的密文恢复明文，却不能发现密钥，则称该密码复明文，却不能发现密钥，则称该密码是是部分可破译部分可破译的的28DES的破解nDES的实际密钥长度为的实际密钥长度为56-bit，就目前计算机的计算，就目前计算机的计算能力而言，能力而言，DES不能抵抗对密钥的不能抵抗对密钥的穷举搜索攻击穷举搜索攻击。 n1997年年1月月28日，日，RSA数据安全公司在数据安全公司在RSA安全年会安全年会上悬赏上悬赏10000美金破解美金破解DES，克罗拉多州的程序员，克罗拉多州的程序员Verser在在Inrernet上数万名志愿者的协作下用上数万名志愿者的协作下用96天天的时间

18、找到了密钥长度为的时间找到了密钥长度为40-bit和和48-bit的的DES密钥。密钥。n1998年年7月电子边境基金会（月电子边境基金会（EFF）使用一台价值）使用一台价值25万美元的计算机在万美元的计算机在56小时之内破译了小时之内破译了56-bit的的DES。n1999年年1月电子边境基金会（月电子边境基金会（EFF）通过互联网上的）通过互联网上的10万台计算机合作，仅用万台计算机合作，仅用22小时小时15分就破解了分就破解了56-bit的的ES。n不过这些破译的前提是，破译者能识别出破译的结果不过这些破译的前提是，破译者能识别出破译的结果确实是明文，也即破译的结果必须容易辩认。如果明确

19、实是明文，也即破译的结果必须容易辩认。如果明文加密之前经过压缩等处理，辩认工作就比较困难。文加密之前经过压缩等处理，辩认工作就比较困难。29DES算法的公开性与脆弱性nDES的两个主要弱点：的两个主要弱点：n密钥容量：密钥容量：56位不太可能提供足够的位不太可能提供足够的安全性安全性nS盒：可能隐含有陷井（盒：可能隐含有陷井（Hidden trapdoors）nDES的半公开性：的半公开性：S盒的设计原理至盒的设计原理至今未公布今未公布30DES小结n充分混乱：密钥、明文以及密文之间的充分混乱：密钥、明文以及密文之间的依赖关系相当复杂依赖关系相当复杂n充分扩散：密钥的每一位数字影响密文充分扩散

20、：密钥的每一位数字影响密文的许多位数字，明文的每一位数字也应的许多位数字，明文的每一位数字也应影响密文的许多位数字影响密文的许多位数字31密码分析的几种情况n根据攻击者掌握的信息，密码分析分为根据攻击者掌握的信息，密码分析分为n仅知密文攻击：攻击者除了所截获的密文外，仅知密文攻击：攻击者除了所截获的密文外，没有其他可以利用的信息没有其他可以利用的信息n已知明文攻击：攻击者仅知道当前密钥下的已知明文攻击：攻击者仅知道当前密钥下的一些明密文对一些明密文对n选择明文攻击：攻击者能获得当前密钥下的选择明文攻击：攻击者能获得当前密钥下的一些特定的明文所对应的密文一些特定的明文所对应的密文n选择密文攻击：

21、攻击者能获得当前密钥下的选择密文攻击：攻击者能获得当前密钥下的一些特定的密文所对应的明文一些特定的密文所对应的明文32n分组密码分组密码n序列密码（流密码）序列密码（流密码）33流密码（序列密码）n分组密码分组密码n将待加密的明文分为若干个字符一组，逐组将待加密的明文分为若干个字符一组，逐组进行加密进行加密n流密码流密码n将待加密的明文分成连续的字符或比特，然将待加密的明文分成连续的字符或比特，然后用相应的密钥流对其进行加密后用相应的密钥流对其进行加密n密钥流由种子密钥通过密钥流由种子密钥通过密钥流生成器密钥流生成器产生产生34流密码基本原理n通过随机数发生通过随机数发生器产生性能优良器产生性

22、能优良的的伪随机序列伪随机序列（密钥流）（密钥流），使，使用该序列加密信用该序列加密信息流（逐比特加息流（逐比特加密），得到密文密），得到密文序列序列种子密钥种子密钥K随机数发生器随机数发生器加密变换加密变换密钥流密钥流Ki明文流明文流mi密文流密文流Ci35n按照加解密的工作方式，流密码分为同按照加解密的工作方式，流密码分为同步流密码和自同步流密码步流密码和自同步流密码36n同步流密码同步流密码n密钥流的产生完全独立于消息流（明文流或密钥流的产生完全独立于消息流（明文流或者密文流）者密文流）n特点：无错误扩散。如果传输过程产生一位特点：无错误扩散。如果传输过程产生一位错误，只影响当前位的解密

23、结果，不影响后错误，只影响当前位的解密结果，不影响后续位续位n自同步流密码自同步流密码37n同步流密码同步流密码1(, )(, )( ,)( ,)iiiiiiiiiiFkkGkcE k mmD k c密钥流生成器密钥流生成器ki种子密钥种子密钥k安全信道安全信道cikiim解密变换解密变换密钥流生成器密钥流生成器 ci公 开 信公 开 信道道加密变换加密变换种子密钥种子密钥Kimi：密钥流生成器的内部状态：密钥流生成器的内部状态F：状态转移函数：状态转移函数G：密钥流产生函数：密钥流产生函数38n同步流密码同步流密码n自同步流密码自同步流密码n每一个密钥字符是由前面每一个密钥字符是由前面n个密

24、文字符参与个密文字符参与运算得到的运算得到的n特点：有错误扩散。如果传输过程中产生特点：有错误扩散。如果传输过程中产生1位错误，则错误会传播位错误，则错误会传播n个字符。个字符。n收到收到n个正确的密文字符后，密码系统会实个正确的密文字符后，密码系统会实现重新同步现重新同步39n自同步流密码自同步流密码),(),(),(),(111iiiiiiiiniiiiickDmmkEckGkkcccF密钥流生成器密钥流生成器ki种子密钥种子密钥k安全信道安全信道cikiim解密变换解密变换密钥流生成器密钥流生成器 ci公开公开信道信道加密变换加密变换im种子密钥种子密钥ki：密钥流生成器的内部状态：密钥

25、流生成器的内部状态F：状态转移函数：状态转移函数G：密钥流产生函数：密钥流产生函数40二元加法流密码n目前使用最多的流密码目前使用最多的流密码n明文明文m、密文、密文c、密钥、密钥k都为都为0，1序列，序列，运算为模运算为模2加（异或）加（异或）n加密：加密：n解密：解密：iiicmkiiimck41二元加法流密码符号描述与示例符号描述与示例加密操作：加密操作： 密钥流：k1,k2,k3, 明文流：m1,m2,m3, 密文流：c1,c2,c3,解密操作：解密操作： 密钥流：k1,k2,k3, 密文流：c1,c2,c3, 明文流：m1,m2,m3,例电报内容电报内容“专列下午专列下午2点到达。点

26、到达。”的加密过程如下的加密过程如下：密钥流：78,35,02,E4,B2 明文流：D7,A8,C1,D0,CF,C2,CE,E7,32,B5,E3,B5,BD,B4,EF,A1,A3 密文流：AF,9D,C3,34,7D42n二元加法流密码算法的安全强度完全取决于二元加法流密码算法的安全强度完全取决于密密钥流的特性钥流的特性n如果密钥流是如果密钥流是无限长、无周期的完全随机的无限长、无周期的完全随机的序序列，则这种密码就是列，则这种密码就是“一次一密一次一密”的密码体制。的密码体制。仙农曾证明它是不可破译的仙农曾证明它是不可破译的n但实际应用中，密钥流都是由有限存储和有限但实际应用中，密钥流

27、都是由有限存储和有限复杂的逻辑电路产生的字符序列，因此是有周复杂的逻辑电路产生的字符序列，因此是有周期性的，期性的，不是真正的随机序列不是真正的随机序列n要设计周期尽可能长、随机性尽可能好的，近要设计周期尽可能长、随机性尽可能好的，近似真正的随机序列，做密钥流似真正的随机序列，做密钥流43Golomb随机性假设n在序列的一个周期内，在序列的一个周期内，0与与1的个数相差至的个数相差至多为多为1n在序列的一个周期圈内，长为在序列的一个周期圈内，长为1的游程数的游程数占总游程数的占总游程数的1/2，长为，长为2的游程数占总的游程数占总游程数的游程数的 ，长为，长为i的游程数占的游程数占总游程数的总

28、游程数的 且在等长的游程中，且在等长的游程中，0，1游程各占一半游程各占一半n序列的异相自相关函数为一个常数序列的异相自相关函数为一个常数22/11 2/,i44n第一个条件说明，第一个条件说明，01序列中序列中0和和1出现的出现的概率概率“基本基本”相同相同n第二个条件说明：在已知位置第二个条件说明：在已知位置n前若干位前若干位置上的值的条件下，置上的值的条件下，0与与1在第在第n位置上位置上出现的概率是相同的出现的概率是相同的n第三个条件说明：若将原序列第三个条件说明：若将原序列(ai)与序列与序列的移位的移位(ai+j)比较，无法得到关于比较，无法得到关于ai的实的实质性信息（如：周期）

29、质性信息（如：周期）45n把满足把满足Golomb随机性假设的序列称为伪随机随机性假设的序列称为伪随机序列序列n流密码最核心的问题是密钥流生成器的设计流密码最核心的问题是密钥流生成器的设计n密钥流生成器一般由密钥流生成器一般由线性反馈移位寄存器线性反馈移位寄存器(Linear Feedback Shift Register, LFSR)和一个和一个非线性组合函数非线性组合函数构成构成驱动部分驱动部分（LFSR）非线性非线性组合部分组合部分密钥流密钥流 ki46n反馈移位寄存器：由寄存器和反馈函数组成反馈移位寄存器：由寄存器和反馈函数组成n移位寄存器：可用来存储数据，脉冲到来时，移位寄存器：可用

30、来存储数据，脉冲到来时，移位寄存器所有位右移一位；最右边移出位为移位寄存器所有位右移一位；最右边移出位为输出，最左边输入位由反馈函数的输出填充输出，最左边输入位由反馈函数的输出填充n反馈函数是反馈函数是n元（元（a1,a2,an)的布尔函数的布尔函数an-1a3a2a1an反馈函数反馈函数 f(a1, ,an)输出位输出位oi47二元加法流密码（续）n工作原理工作原理 移位寄存器中所有位右移一位，最移位寄存器中所有位右移一位，最右边移出的位是输出位，最左端的一位右边移出的位是输出位，最左端的一位由反馈函数的输出填充。反馈函数由反馈函数的输出填充。反馈函数f(a1, ,an)是是n元元(a1 ,

31、an)的布尔函的布尔函数。移位寄存器根据需要不断地进动数。移位寄存器根据需要不断地进动m拍，便有拍，便有m位的输出，形成输出序列位的输出，形成输出序列o1 o2 om 。48二元加法流密码（续）n例：图示为一个例：图示为一个3-级反馈移位寄存器，反馈函数级反馈移位寄存器，反馈函数f(x)=b3 b2，初态为：，初态为：100。输出序列生成过程：。输出序列生成过程：n状态状态 输出位输出位n100 0n110 0n011 1n101 1n110 0n011 1n101 1n110 0n因此，对应初态因此，对应初态(100)的输出序列为：的输出序列为：n0011011011 （周期为（周期为3）b

32、3b2b1t2t3(a) 移位寄存器结构图移位寄存器结构图(110)(011)(101)初态初态(100)(b) 状态转移图状态转移图110(c) 序列圈序列圈049二元加法流密码（续）n当反馈移位寄存器的反馈函数是异或变当反馈移位寄存器的反馈函数是异或变换时，这样的反馈移位寄存器叫线性反换时，这样的反馈移位寄存器叫线性反馈移位寄存器，如图所示：馈移位寄存器，如图所示： 50二元加法流密码（续） 移位寄存器中存储器的个数称为移位寄移位寄存器中存储器的个数称为移位寄存器的级数，移位寄存器存储的数据为存器的级数，移位寄存器存储的数据为寄存器的状态，状态的顺序从左到右依寄存器的状态，状态的顺序从左到

33、右依次为从最高位到最低位。次为从最高位到最低位。 在所有状态中，在所有状态中， 叫初态，并且从叫初态，并且从左到右依次称为第一级、第二级、左到右依次称为第一级、第二级、第第n级，亦称为抽头级，亦称为抽头1、抽头、抽头2、抽头、抽头3、.、抽头、抽头n。n级线性反馈移位寄存级线性反馈移位寄存器的有效状态为器的有效状态为 个。它主要是用来个。它主要是用来产生周期大，统计性能好的序列。产生周期大，统计性能好的序列。 ),.,(21naaa12n51二元加法流密码（续）n非线性组合部分主要是增加密钥流的复非线性组合部分主要是增加密钥流的复杂程度，使密钥流能够抵抗各种攻击杂程度，使密钥流能够抵抗各种攻击（对流密码的攻击手段主要是对密钥流对流密码的攻击手段主要是对密钥流进行攻击进行攻击）。）。 n以线性反馈移位寄存器产生的序列为基以线性反馈移位寄存器产生的序列为基序列，经过不规则采样、函数变换等序列