第六讲-序列密码基础-武汉大学密码学

武汉大学计算机学院空天信息安全与可信计算教育部重点实验室张焕国第六讲序列密码基础密码学2目录第一讲第一讲信息安全概论信息安全概论第二讲第二讲密码学的基本概念密码学的基本概念第三讲第三讲数据加密标准（数据加密标准（DESDES））第四讲第四讲高级高级数据加密标准（数据加密标准（AESAES））第五讲第五讲中国商用密码中国商用密码SMS4SMS4与分组密码应用技术与分组密码应用技术第六讲第六讲序列密码基础序列密码基础第七讲第七讲祖冲之密码祖冲之密码第第八八讲讲中国商用密码中国商用密码HASHHASH函数函数SM3SM3第九讲第九讲复习复习3目录第十讲第十讲公钥密码基础公钥密码基础第十一讲第十一讲中国商用公钥密码中国商用公钥密码SM2SM2加密算法加密算法第十二讲第十二讲数字签名基础数字签名基础第十三讲第十三讲中国商用公钥密码中国商用公钥密码SM2SM2签名算法签名算法第十四讲第十四讲认证认证第十五讲第十五讲密码协议密码协议第十六讲第十六讲密钥管理：对称密码密钥管理密钥管理：对称密码密钥管理第十七讲第十七讲密钥管理：公钥密码密钥管理密钥管理：公钥密码密钥管理第十八讲第十八讲复习复习4教材与主要参考书教材教材参考书参考书5一、序列密码的基本概念一、序列密码的基本概念二、二、随机序列的安全性随机序列的安全性三、三、线性移位寄存器序列密码线性移位寄存器序列密码四、四、非线性序列密码非线性序列密码本讲内容本讲内容6①定义：明文、密文、密钥以位（或字符）为单位进①定义：明文、密文、密钥以位（或字符）为单位进行加解密行加解密。。zz为了安全，密钥必须有足够的长度、随机性，且经常更换。为了安全，密钥必须有足够的长度、随机性，且经常更换。zz为此，用一个短的种子密钥，通过算法产生好的密钥序列。为此，用一个短的种子密钥，通过算法产生好的密钥序列。②模型②模型密钥序产生器种子密钥种子密钥密钥序列密钥序列kk11,,kk22,,……密文密文cc11,,cc22,,……明文明文mm11,,mm22,,……CCii==mmii⊕⊕kkii一、序列密码的基本概念7③商农证明了③商农证明了““一次一密一次一密””是无条件安全的。于是，人是无条件安全的。于是，人们用序列密码模仿们用序列密码模仿““一次一密一次一密””；；④④加密运算最简单，而且是对合运算；加密运算最简单，而且是对合运算；⑤安全取决于密钥序列产生算法；⑤安全取决于密钥序列产生算法；⑥⑥理论和技术都十分成熟；理论和技术都十分成熟；⑦核心密码的主流密码。⑦核心密码的主流密码。一、序列密码的基本概念811、序列密码的分类、序列密码的分类①①同步序列密码同步序列密码（（SynchronousStreamCipherSynchronousStreamCipher））zz密钥序列产生算法与明文（密文）无关，则所产生密钥序列产生算法与明文（密文）无关，则所产生的密钥序列也与明文（密文）无关的密钥序列也与明文（密文）无关。。zz在通信过程中，通信的双方必须保持精确的同步，在通信过程中，通信的双方必须保持精确的同步，收方才能正确解密，如果失步收方将不能正确解收方才能正确解密，如果失步收方将不能正确解密。例如，如果通信中丢失或增加了一个密文字密。例如，如果通信中丢失或增加了一个密文字符，则收方的解密将一直错误。符，则收方的解密将一直错误。一、序列密码的基本概念9zz举例：输出反馈模式举例：输出反馈模式(OFB)(OFB)移位寄存器S密文S明文明文密文密文种子种子RR00KE一、序列密码的基本概念10①①同步序列密码同步序列密码设设密文密文失步失步cc==cc11,,cc33,,cc44,,……ccnn--11,,ccnn（（cc22丢失丢失））⊕⊕kk==kk11,,kk22,,kk33,,……kknn--22,,kknn--11（（密钥正确）密钥正确）mm==mm11,,××,,××,,……××,,××（（mm11后明文全错后明文全错））密钥序产生算密钥序产生算mm11,,mm22,,……mm11,,mm22,,……cc11,,cc22,,……kk11,,kk22,,……kk11,,kk22,,……CCii==mmii⊕⊕kkii发送端发送端种子密钥种子密钥kk接收端接收端种子密钥种子密钥kk一、序列密码的基本概念11①①同步序列密码同步序列密码zz对失步的敏感性，使我们能够容易检测插入、删对失步的敏感性，使我们能够容易检测插入、删除、重播等主动攻击。除、重播等主动攻击。zz另一个优点是没有错误传播，当通信中某些密文字另一个优点是没有错误传播，当通信中某些密文字符产生了错误（符产生了错误（00错成错成11或或11错成错成00，不是插入和删，不是插入和删除），只影响相应字符的解密，不影响其它字符。除），只影响相应字符的解密，不影响其它字符。zz注意：注意：错误与失步是不同的概念！错误与失步是不同的概念！设密文错误设密文错误cc==cc11,,cc22,,cc33,,……ccnn--11,,ccnn（（cc22错）错）⊕⊕kk==kk11,,kk22,,kk33,,……kknn--11,,kknn（（密钥正确）密钥正确）mm==mm11,,××,,mm33,,……mmnn--11,,mmnn（（仅仅mm22错错））一、序列密码的基本概念12②②自同步序列密码自同步序列密码（（SelfSelf--SynchronousStreamCipherSynchronousStreamCipher））zz密钥序列产生算法与明文（密文）相关，则所产生密钥序列产生算法与明文（密文）相关，则所产生的密钥序列与明文（密文）相关的密钥序列与明文（密文）相关。。zz设密钥序列产生器具有设密钥序列产生器具有nn位存储，则加密时一位密位存储，则加密时一位密错误将影响后面连续错误将影响后面连续nn个密文错误。在此之后恢复个密文错误。在此之后恢复确。确。zz解密时一位密文错误也将影响后面连续解密时一位密文错误也将影响后面连续nn个明文个明文在此之后恢复正确。在此之后恢复正确。zz加解密会造成错误传播。但错误传播有界，在错误加解密会造成错误传播。但错误传播有界，在错误过去之后恢复正确。过去之后恢复正确。一、序列密码的基本概念13②②自同步序列密码自同步序列密码密钥序产生算n位存储密钥序产生算n位存储mm11,,mm22,,……mm11,,mm22,,……cc11,,cc22,,……kk11,,kk22,,……kk11,,kk22,,……发送端发送端种子密钥种子密钥kkCCii的错误将影响的错误将影响nn位位接收端接收端种子密钥种子密钥kk一、序列密码的基本概念14二、随机序列的安全性zz序列密码的安全，取决于密钥序列的安全性序列密码的安全，取决于密钥序列的安全性1.1.随机序列的安全性随机序列的安全性zz在密码学中，对随机序列的基本要求是具有良好的随机性。在密码学中，对随机序列的基本要求是具有良好的随机性。„„长周期性、非线性、统计上的预期性、可伸缩性长周期性、非线性、统计上的预期性、可伸缩性„„不可预测性等不可预测性等zz一个有限长度的数字序列一定是可重复的一个有限长度的数字序列一定是可重复的，即有周期的。例，即有周期的。例如，长度为如，长度为nn的二元序列，其重复周期一定小于等于的二元序列，其重复周期一定小于等于22nn。。zz我们希望密钥的重复周期能够等于我们希望密钥的重复周期能够等于22nn。当。当nn足够大时，足够大时，22nn是一是一很大的数。因为序列的重复周期很长，从而使密钥空间很大。很大的数。因为序列的重复周期很长，从而使密钥空间很大。15二、随机序列的安全性zz非线性是密码学的基本要求非线性是密码学的基本要求„„从计算复杂性角度来看，任何线性的数学问题都从计算复杂性角度来看，任何线性的数学问题都是容易计算的。是容易计算的。„„如果序列的内在数学关系是线性的，则容易受到如果序列的内在数学关系是线性的，则容易受到基于数学的攻击。基于数学的攻击。„„目前数学上求解非线性问题仍是困难的。目前数学上求解非线性问题仍是困难的。„„因此，要求序列的内在数学关系是因此，要求序列的内在数学关系是非线性的非线性的，，而而且具有足够的复杂度且具有足够的复杂度。。16二、随机序列的安全性zz统计上的预期性统计上的预期性„„序列的一些统计指标应达到预期值。序列的一些统计指标应达到预期值。„„例如，二元序列中例如，二元序列中00和和11的频率应是相等的或接近的频率应是相等的或接近相等的，相等的，00游程和游程和11游程的频率的数量也应是相等游程的频率的数量也应是相等的或接近相等的。的或接近相等的。zz可伸缩性可伸缩性zz如果序列是随机的，那么任何从中抽取的子序列如果序列是随机的，那么任何从中抽取的子序列也应该是随机的。也应该是随机的。zz如果任何抽取的子序列不随机，那么这个序列也如果任何抽取的子序列不随机，那么这个序列也不是随机的。不是随机的。17二、随机序列的安全性zz不可预测性不可预测性„„一是指，人们不能人为有意识地重复产生该随机序列，一是指，人们不能人为有意识地重复产生该随机序列，„„二是指，不能由已知的序列数据求出未知的序列数据。二是指，不能由已知的序列数据求出未知的序列数据。„„第一个性质决定是第一个性质决定是““真真””还是还是““伪伪””。。„„第二个性质决定是第二个性质决定是““随机随机””还是还是““不随机不随机””。。„„其他性质决定随机性是其他性质决定随机性是““好好””还是还是““不好不好””。。zz真随机性和伪随机性真随机性和伪随机性„„真随机序列具有上述两方面的不可预测性。真随机序列具有上述两方面的不可预测性。„„伪随机序列，具有第二个性质，但不具有第一个性质。伪随机序列，具有第二个性质，但不具有第一个性质。„„伪随机序列是可以人为有意识地重复的。伪随机序列是可以人为有意识地重复的。„„序列密码只能使用好的伪随机序列！序列密码只能使用好的伪随机序列！18二、随机序列的安全性zz伪随机序列的不可预测性伪随机序列的不可预测性„„伪随机序列是可以人为有意识地重复的。伪随机序列是可以人为有意识地重复的。„„其不可预测性主要强调不可由已知的序列数据求出未知的其不可预测性主要强调不可由已知的序列数据求出未知的序列数据。序列数据。„„为此，把不可预测性划分为为此，把不可预测性划分为前向不可预测性前向不可预测性和和后向不可预后向不可预测性测性。。„„所谓前向不可预测性是指，所谓前向不可预测性是指，如果不知道产生该序列的种如果不知道产生该序列的种子，那么不管知道序列中前面的多少比特都无法预测序列子，那么不管知道序列中前面的多少比特都无法预测序列中的下一比特。中的下一比特。„„所谓后向不可预测性是指，所谓后向不可预测性是指，从产生出的序列不能推断出产从产生出的序列不能推断出产生它的种子值。生它的种子值。19二、随机序列的安全性zz伪随机序列的测试伪随机序列的测试„„我们尚不能从理论上证明一个序列是随机序列。我们尚不能从理论上证明一个序列是随机序列。„„密码界采用的办法是密码界采用的办法是对序列进行一系列的随机性指标测对序列进行一系列的随机性指标测试，如果被测序列通过了这些测试，我们就认为它是随机试，如果被测序列通过了这些测试，我们就认为它是随机的。的。„„20092009年年22月国家密码管理局颁布了月国家密码管理局颁布了《《随机性测试规范随机性测试规范》》，，范给出了范给出了1515项随机性检测。项随机性检测。„„美国美国NISTNIST也有类似规范。也有类似规范。20二、随机序列的安全性①①单比特频率检测单比特频率检测„„对于二元序列，统计被测序列中对于二元序列，统计被测序列中00和和11出现的频率出现的频率。如果。如果00和和11出现的频率相等或接近相等，则认为是合格的。出现的频率相等或接近相等，则认为是合格的。②②游程分布检测游程分布检测„„对于二元序列，统计被测序列中对于二元序列，统计被测序列中00游程和游程和11游程的数目。