密码学全套课件

第一章概论一、信息安全与密码技术二、密码系统模型和密码体制三、几种简单的密码体制四、初等密码分析五、密码学的信息论基础六、密码学的复杂性理论基础2/26/20241一、信息安全与密码技术信息安全面临的威胁政府宏观调控决策商业经济信息银行资金转账股票证券经济医疗记录科研数据等2/26/20243信息安全有广泛的应用信息安全面临的威胁可能的攻击者：黑客竞争对手间谍媒体政府机构

2/26/20244信息安全面临的威胁信息安全所面临的威胁来自很多方面，并且随着时间的变化而变化。这些威胁可以宏观地分为：自然威胁自然灾害恶劣的场地环境电磁辐射和电磁干扰网络设备自然老化等。2/26/20245人为威胁(对信息的人为攻击。这些攻击手段都是通过寻找系统的弱点，以便达到破坏、欺骗、窃取数据等目的，造成经济上和政治上不可估量的损失。)2/26/202462/26/20247被动攻击消息内容获取监听(保密性）业务流量分析2/26/20248主动攻击伪造(真实性)中断(可用性)篡改(完整性)1.被动攻击被动攻击即窃听(Interception)，是对系统的保密性进行攻击，如搭线窃听、对文件或程序的非法拷贝等，以获取他人的信息。被动攻击因不对消息做任何修改，因而是难以检测的，所以抗击这种攻击的重点在于预防而非检测。2/26/20249被动攻击又分为两类，一类是获取消息的内容，很容易理解；第二类是进行业务流分析，假如我们通过某种手段，比如加密，使得敌手从截获的消息无法得到消息的真实内容，然而敌手却有可能获得消息的格式、确定通信双方的位置和身份以及通信的次数和消息的长度，这些信息可能对通信双方来说是敏感的。2/26/202410主动攻击又可分为以下三个子类(如图1.2所示)：中断（Interruption)：是对系统的可用性进行攻击，如破坏计算机硬件、网络或文件管理系统。2/26/202411篡改(Modification)：是对系统的完整性进行攻击，如修改数据文件中的数据、替换某一程序使其执行不同的功能、修改网络中传送的消息内容等。伪造(Fabication)：是对系统的真实性进行攻击。如在网络中插入伪造的消息或在文件中插入伪造的记录。2/26/2024122/26/202413中断（Interruption）AliceBob图1.22/26/202414窃听(Interception)EveBobAlice2/26/202415篡改(Modification)AliceBobEve2/26/202416BobAliceEve伪造(Fabication)信息安全的要求保密性Confidentiality完整性Integrity不可否认性Non-reputiation可鉴别性Authentication可用性Availability

2/26/202417信息安全的要求2/26/2024182/26/202419图1.3信息安全的基本模型信息系统安全模型和密码技术可信赖的第三方(如仲裁者、秘密信息分布者用户用户攻击者消息秘密信息消息秘密信息信道安全的网络通信必须考虑以下几个方面：加密算法。用于加密算法的秘密信息。秘密信息的分布和共享。使用加密算法和秘密信息以获得安全服务所需的协议。2/26/202420

信息安全可分为：系统安全（包括操作系统安全、数据库系统安全等）数据安全（包括数据的安全存储、安全传输）内容安全（包括病毒的防护、不良内容的过滤等）2/26/202421这3个层次，是一个综合、交叉的学科领域，要利用数学、电子、信息、通信、计算机等诸多学科的长期知识积累和最新发展成果。信息安全研究的内容很多，它涉及安全体系结构、安全协议、密码理论、信息分析、安全监控、应急处理等，其中密码技术是保障数据安全的关键技术。2/26/2024222/26/202423密码学是信息安全的核心部分密码学就是研究与信息安全相关的方面如机密性、完整性、实体鉴别、抗否认等的综合技术。密码并不是提供安全的单一的手段，而是一组技术。二、密码系统模型和密码体制一、密码学的基本概念密码学(Cryptology)：研究信息系统安全保密的科学。它包含两个分支，

密码编码学(Cryptography)，对信息进行编码实现隐蔽信息的一门学问

密码分析学(Cryptanalytics)，研究分析破译密码的学问。2/26/202425一、密码学的基本概念2/26/202426明文(消息)(Plaintext)：被隐蔽消息。密文(Ciphertext)或密报(Cryptogram)：明文经密码变换成的一种隐蔽形式。加密(Encryption)：将明文变换为密文的过程。一、密码学的基本概念解密(Decryption)：加密的逆过程，即由密文恢复出原明文的过程。加密员或密码员(Cryptographer)：对明文进行加密操作的人员。2/26/202427一、密码学的基本概念2/26/202428

加密算法(Encryptionalgorithm)：密码员对明文进行加密时所采用的一组规则。接收者(Receiver)：传送消息的预定对象。解密算法：接收者对密文进行解密时所采用的一组规则。一、密码学的基本概念密钥(Key)：控制加密和解密算法操作的数据处理，分别称作加密密钥和解密密钥。截收者(Eavesdropper)：在信息传输和处理系统中的非受权者，通过搭线窃听、电磁窃听、声音窃听等来窃取机密信息。2/26/202429一、密码学的基本概念2/26/202430密码分析(Cryptanalysis)：截收者试图通过分析从截获的密文推断出原来的明文或密钥。密码分析员(Cryptanalyst)：从事密码分析的人。被动攻击(Passiveattack)：对一个保密系统采取截获密文进行分析的攻击。一、密码学的基本概念主动攻击(Activeattack)：非法入侵者(Tamper)、攻击者(Attcker)或黑客(Hacker)主动向系统窜扰，采用删除、增添、重放、伪造等窜改手段向系统注入假消息，达到利已害人的目的。2/26/202431密码系统模型2/26/202432图1.4非法接入者密码分析员(窃听者)信源M接收者密钥源K1加密器c=EK1(m)密钥源K2解密器m=EK2(c)密钥信道mmcc’搭线信道(主动攻击)K1K2搭线信道(被动攻击)m’明文空间密文空间密码方案密钥空间四个部分组成一个密码系统由：

密码体制密码体制有两类：单钥体制（One-keysystem)加密密钥和解密密钥相同双钥体制（Two-keysystem)加密密钥和解密密钥不同2/26/202434

单钥体制单钥体制的系统的保密性：主要取决于密钥的保密性（与算法的保密性无关）单钥体制研究的主要课题：密钥的产生(Keygeneration)。密钥的管理(Keymanagement)。2/26/202435

单钥体制分类：序列密码(Streamcipher)按字符逐位加密。分组密码(Blockcipher)按分组加密。单钥体制不仅可用于数据加密，也可用于消息的认证。2/26/202436公钥体制双钥体制（Diffie和Hellman1976年引入）每个用户都有一对选定的密钥（公钥：K1，私钥K2）K1是可以公开的，可以像电话号码一样进行注册公布；K2则是秘密的。

2/26/202437公钥体制的主要特点：

将加密和解密能力分开多个用户加密的消息只能由一个用户解读（秘密通信）一个用户加密的消息而使多个用户可以解读（认证）不用事先分配秘钥2/26/202438对密码体制的一般要求：系统即使达不到理论上是不可破的，即pr{m’=m}=0，也应当为实际上不可破的。就是说，从截获的密文或某些已知明文密文对，要决定密钥或任意明文在计算上是不可行的。2/26/202439对密码体制的一般要求：系统的保密性不依赖于对加密体制或算法的保密，而依赖于密钥。这是著名的Kerckhoff原则。加密和解密算法适用于所有密钥空间中的元素。系统便于实现和使用。2/26/202440三、几种简单密码体制几种简单密码体制

1.换位密码

2.仿射密码3.密钥短语密码4.多名代换密码5.多表代换密码2/26/202442换位密码例：给定明文消息thesimplestpossibletranspositionciphers（不计空格符），将它分成长度的段，最后一段长度不足5添加一个字符x，成为8个完整的明文组thesi|mples|tposs|iblet|ransp|ositi|oncip|hersx2/26/202443换位密码加密方法：得到密文：2/26/202444STIEHEMSLPSTSOPEITLBSRPNATOIISIOPCNSHXRE换位密码解密方法：密钥量：2/26/202445换位密码

缺点：当明（密）文字母表内字符数不大时，一味增加分段长度（比如使），可能导致若干对很多明文组的加密结果重合，甚至在局部明文空间上与恒等变换等价，即密文消息等于明文消息，达不到加密的效果。

2/26/202446仿射密码

上的仿射密码的加密变换记为，按计算密文，其中密钥，并且要求gcd以保证加密变换是可逆的。2/26/202447仿射密码

当时密钥量：2/26/202448注意：其中是整数的欧拉函数。这里不取，即不选仿射密码

仿射密码就是乘数密码仿射密码就是移位代换密码或加法密码其全部26个加密变换的代换表整合在一起构成一个密文形如26阶对称矩阵的表（该矩阵的第一行、第一列是从A到Z顺序排列的字母），称为维吉尼亚表2/26/202449仿射密码针对个英文字母,的加法密码则称为凯撒密码仿射密码又是多项式代换密码的特例。2/26/202450仿射密码构造上的仿射密码式中“+”为矢量相加，是上的阶满秩矩阵，即存在使得上的仿射密码，则称为Hill密码

2/26/202451密钥短语密码

密钥短语密码实际上是26个英文字母或上的一种置换。密钥量：2/26/202452密钥短语密码

2/26/202453加密举例：选择一个英文短语作为密钥字或称密钥短语，如HAPPYNEWYEAR，去掉重复的字母得到HAPYNEWR。将它依次写在明文字母表的下面，而后再将字母表中未在短语中出现过的字母依次写在这个短语后面，就可以构造一个代换表，如下所示：多名代换密码

2/26/202454也称为同音代换密码。多名代换是一对多变换，它将明文字母表中的每个字母映射为较大的密文字母表中相应字母分组中的某个字母（一般等概率地选定），各字母分组的大小与相应原明文字母的概率成比例。多名代换密码

2/26/202455例如，字母a，i，e，n，o，p，t的多名集可作如下选择：明文字母出现频度%密文（多名集）a8.167

17，19，34，41，56，60，67，83

c2.782

03，44，76

h6.09408，22，53，65，88，90

i6.966

02，09，15，27，32，40，59

p1.92933，91

r5.987

00，11，23，42，54，70

t9.05605，10，20，29，45，58，64，78，99

多名代换密码

个字母的明文字母表上的二阶多名代换密码的构造方法：将个整数随机地填入一个“二阶多名代换密表”矩阵中，方阵中的行和列都对应于明文字母表的个字母。2/26/202456多名代换密码

2/26/202457多表代换密码

2/26/202458多表代换密码是以两个以上代换表依次对明文消息的字母进行代换的加密方法。令明文字母表为，为代换序列。明文字母序列为，则相应的密文字母序列为多表代换密码

2/26/202459

若是非周期的无限序列，则相应的密码为非周期多表代换密码。这类密码对每个明文字母都采用不同的代换表（或密钥）进行加密，称作一次一密钥密码多表代换密码

2/26/202460

几种历史上较著名的多表代换密码：

维吉尼亚密码（VigenereCipher）博福特密码（BeaufortCipher）滚动密钥密码（running-keyCipher）弗纳姆密码（VernamCipher）转轮密码（rotorCipher）四、初等密码分析基本概念

2/26/202462试图获得加密体制细节、解密密钥和明文等机密信息的过程，通常包括：分析统计截获的密文材料、假设、推断和证实等步骤。基本概念

2/26/202463密码分析方法有传统破译方法和物理破译方法两大类。传统破译方法包括穷举破译法和数学分析法两类。数学分析法又分为确定性分析法的和统计分析法。基本概念

2/26/202464四种破译类型：（1）唯密文破译（ciphertextonlyattacks），分析者仅知道有限数量的密文。（2）已知明文破译（knowplaintextattacks），分析者除了拥有有限数量的密文外，还有数量限定的一些已知“明文—密文”对。基本概念

2/26/202465（3）选择明文破译（chosenplaintextattacks），分析者除了拥有有限数量的密文外，还有机会使用注入了未知密钥的加密机，通过自由选择明文来获取所希望的“明文—密文”对（集合）。（4）选择密文破译（chosenciphertextattacks），分析者除了拥有有限数量的密文外，还有机会使用注入了未知密钥的解密机，通过自由选择密文来获取所希望的“密文—明文”对（集合）。单表代换密码分析

2/26/202466能对密码分析者提供很大帮助的英文统计特性：（1）冠词the对统计特性影响极大，它使t、h、th、he和the在单、双和三字母统计中都为高频度元素。（2）英文中大约有一半的字以e、s、d和t作为字的结尾字母。（3）英文中大约有一半的字以t、a、s或w作为字的开头字母。多表代换密码分析

2/26/202467多表代换密码分析

2/26/202468多表代换密码分析

2/26/202469多表代换密码分析

2/26/202470多表代换密码分析

2/26/202471步骤一：从密文中找出大于等于3的重复图样，对于每种重复图样，列出其间的距离。步骤二：确定具体的密钥。五、密码学的信息论基础

5.1信息量和熵

5.2完善保密性

5.3唯一解距离、理论保密性与实际保密性

2/26/202473信息量和熵

2/26/202474信息量和熵

2/26/202475信息量和熵

2/26/202476信息量和熵

2/26/202477信息量和熵

2/26/202478信息量和熵

2/26/202479完善保密性

2/26/202480基本术语：

密码源解密空间解密变换完善保密性

2/26/202481完善保密性

2/26/202482唯一解距离、理论保密性与实际保密性

2/26/202483由条件熵性质知

若，就可以唯一地确定密钥，从而实现破译。唯一解距离、理论保密性与实际保密性

2/26/202484对于给定的密码系统，我们称

为唯密文破译下的唯一解距离（unicitydistance），式中是正整数集。唯一解距离、理论保密性与实际保密性

2/26/202485理论保密性是假定密码分析者有无限的时间、设备和资金条件下，研究唯密文攻击时密码系统的安全性。实际的密码分析者所具有的资金、设备和时间总是有限的。在这种条件下来研究密码体制的安全保密性，就是研究系统的实际保密性。2/26/202486六、密码学的复杂性理论基础问题与算法所谓问题，是指一个要求给出解释的一般性提问，通常含有若干未定参数或自由变量。两个要素：描述所有的参数解答必须满足的性质

2/26/202487问题与算法所谓算法,是由明确指出操作的规定所组成的若干语句的集合。只要安规则一步一步执行一定数目的语句,便可求出问题的解答。2/26/202488算法的复杂性算法的复杂性表征了算法在执行时所需要计算的能力方面的信息，通常由该算法的所要求的最大时间与存取空间来确定。用“大O”符号来衡量算法的复杂程度.

2/26/202489算法的复杂性按时间(或空间)复杂性对算法分类多项式时间算法指数时间算法超多项式算法等2/26/202490

问题按复杂性分类问题的复杂性由在图灵机上解最难实例所需的最小时间与空间所决定。问题的复杂性可以用理解为由解该问题的最胡效的算法所需时间与空间来度量。2/26/202491问题按复杂性分类P类：在确定图灵机上可用多项式时间求解的问题.称为易处理的问题.易处理的问题的全体称为确定性多项式时间可解类。记为P类。2/26/202492问题按复杂性分类NP类：在非确定图灵机上可用多项式时间求解的问题.称为非确定性多项式时间可解问题.记为NP问题。2/26/202493问题按复杂性分类NPC类：NP完全类记为NPC,属于NP类中困难程度最难的一类问题。已经证明,所有的NP问题都可以在多项式时间内转换为NPC的问题.NPC具有如下性质：若其中的任何一问题属于P，则所有的NP问题都属于P，且P=NP。2/26/202494

序列密码一、序列密码的基本概念二、线性反馈移位寄存器三、B-M综合算法四、非线性序列2/26/202495一、序列密码的基本概念

序列密码的分类同步序列密码SSC(SynchronousStreamCipher)：

i与明文消息无关，密钥流将独立于明文。特点：对于明文而言，这类加密变换是无记忆的。但它是时变的。只有保持两端精确同步才能正常工作。对主动攻击时异常敏感而有利于检测无差错传播(ErrorPropagation)

2/26/202497序列密码的分类自同步序列密码SSSC(Self-SynchronousStreamCipher)

i依赖于(kI,

i-1,mi)，使密文ci不仅与当前输入mi有关，而且由于ki对

i的关系而与以前的输入m1,m2,…,mi-1有关。一般在有限的n级存储下将与mi-1,…,mi-n有关。优点：具有自同步能力，强化了其抗统计分析的能力缺点：有n位长的差错传播。2/26/202498序列密码的分类

n级移存器n

级移存器…………

ki

f

f

ki

ki

kimi

Eki(·)ci

ci

Dki(·)mi

2/26/202499

序列的伪随机性周期

序列{ki}i

0，使对所有i，ki+p=ki成立的的最小整数p长为l的串(run)(kt,kt+1…kt+l-1)

序列{ki}的一个周期中，kt-1

kt=kt+1=…=kt+l-1

kt+l

例：长为l的1串和长为l的0串：

2/26/2024100序列的伪随机性周期自相关函数

周期为p的序列{ki}i

0，其周期自相关函数

R(j)=(A－D)/p，j=0,1,…式中，A=

{0

i<p|：ki=ki+j}

，D=

{0

i<p：ki

ki+j}

。同相自相关函数

当j为p的倍数，即p

j时为，R(j)=1；异相自相关函数

当j不是p的倍数时2/26/2024101例2－2

二元序列111001011100101110010…周期p=7同相自相关函数R(j)=1异相自相关函数R(j)=－1/7。2/26/2024102Golomb随机性假设－PN序列

G1．若p为偶，则0,1出现个数相等，皆为p/2。若p为奇，则0出现个数为(p

1)/2。G2．长为l的串占1/2l，且“0”串和“1”串个数相等或至多差一个。G3．R(j)为双值，即所有异相自相关函数值相等。这与白噪声的自相关函数(

函数)相近，这种序列又称为双值序列(TwoValueSequence)。PN序列可用于通信中同步序列、码分多址(CDMA)、导航中多基站码、雷达测距码等。但仅满足G1～G3特性的序列虽与白噪声序列相似，但远还不能满足密码体制要求。

2/26/2024103满足密码体制的另外三个条件C1．周期p要足够大，如大于1050；C2．序列{ki}i

0产生易于高速生成；C3．当序列{ki}i

0的任何部分暴露时，要分析整个序列，提取产生它的电路结构信息，在计算上是不可行的，称此为不可预测性(Unpredictability)。C3决定了密码的强度，是序列密码理论的核心。它包含了序列密码要研究的许多主要问题，如线性复杂度、相关免疫性、不可预测性等等。2/26/2024104二、线性反馈移位寄存器序列线性反馈移位寄存器序列概念级数(Stages)：存储单元数。状态(State)：n个存储单元的存数(ki,…,ki+n-1)

反馈函数：f(ki,ki+1,…,ki+n-1)是状态(ki,…,ki+n-1)的函数。线性反馈移位寄存器(LFSR)：f

为线性函数非线性反馈移位寄存器：f

为非线性函数2/26/2024106

反馈移位寄存器

x1,x2,…xn

f(ki,ki+1,

…ki+n-1)

ki+n

ki+n-1

ki+n-2

ki+1

ki

ki-1.,…,k1k0

xnxn-1x2

x12/26/2024107

线性反馈移位寄存器

f(x)为线性函数，输出序列满足下式

cn

-cn-1

-cn-2

-c1

-c0

ki+n-1

ki+n-2ki+1

kiki-1,…,k1,

k0xnxn-1

x2

x12/26/2024108二元线性移位寄存器

二元条件下ki

{0,1}，cj

{0,1}，即断开或连通，

为模2加，反馈函数可写成n阶线性递推关系式

cncn-1

cn-2

c1

c0

ki+n-1ki+n-2

ki+1

kiki-1,…,k1,

xn

xn-1

x2

x1

2/26/2024109

线性反馈移位寄存器例n=4的LFSR。输出序列满足ki－4＋ki－3＋ki=0。初始状态为1000。序列的周期为15=24－1。

c4

c3

c2

c1

c0ki0001

线性移存器序列的最长周期为2n－1。

2/26/2024110状态转移和相应输出

时刻状态输出32100000011110000201000300100410011511000601100710111801011910100101101111111001211111130111114001111500011

2/26/2024111m序列

为2n－1的LFSR序列称为m序列。m序列是一类PN序列。

n级m序列{ki}i

0循环地遍历所有2n－1个非零状态，且任一非零输出皆为{ki}i

0的移位，或为其循环等价(Cyclicallyequivalent)序列。初始状态不同2n－1个的m序列共有2n－1个,他们的全体记为

(f),他们只是状态前后次序之别。2/26/2024112

特征多项式以LFSR的反馈系数所决定的多项式

又称反馈多项式。式中，c0=cn=1反多项式

称作是LFSR的联接多项式。cn

0称之为非奇异LFSR。

2/26/2024113特征多项式定义:给定序列{ki}i

0,幂级数

称为该序列的生成函数定理3-1令{ki}i

0

(f)，f(x)是反馈多项式，令k(x)是{ki}i

0的生成函数，则

其中

2/26/2024114特征多项式证：

2/26/2024115a(x)就是移存器初始值所对应的多项式

特征多项式

系:证：

(f)的每个元素均可由a(x)/f

(x)惟一决定，式中，deg(a(x))<n，另一方面，

(f)有2n个元素。而deg(a(x))<n的多项式也恰有2n个。

2/26/2024116多项式的周期多项式f(x)的周期p为使f(x)除尽xn-1的最小整数n的取值。序列的周期与生成序列特征多项式的周期密切相关。引理3-2:令f(x)为n次式，周期为p，令{ki}i

0

(f)，则{ki}i

0的周期p’

p。2/26/2024117多项式的周期引理3-3

令f(x)是周期为p的n次既约多项式，令{ki}i

0

(f)，则{ki}i

0的周期为p。证：令{ki}i

0周期为p’，由引理3-2-3，有p’

p，则有，deg(u(x))<p

，由(3-2-12)式有k(x)=a(x)/f*(x)，故有，由此可得

因为f(x)为n次既约式，

deg(a(x))<n，因此有f(x)

(1＋xp’)但f(x)的周期为p，故有p|p’所以p’=p。

2/26/2024118多项式的周期引理3-4

令f(x)为n次式，令{ki}i

0

(f)为m序列，则f(x)为既约的。证：采用反证法。假定f(x)=f1(x)·f2(x)，f1(x)为既约式，次数为n1,n2>0，n1>n2。由(3-2-14)式，1/f1*(x)

(f1)，故由引理3-2-3及附录3A，1/f1*(x)的周期除尽。类似地有。由定理3-2-1知1/f1*(x)应是{ki}i

0的移位，.因而其周期为2n－1，惟一可能是n=n1，即f(x)=f1(x)。2/26/2024119m序列的性质

定理3-5

以f(x)为特征多项式的LFSR的输出序列是m序列的充要条件为f(x)是本原的。

系n级LFSR生成的不等价m序列共有

(2n－1)/n个。定理3-6

m序列满足Golomb的三条伪随机假设。2/26/2024120m序列的性质m序列否满足密码要求？m-C1：n级m序列的周期为2n－1，n大，周期指数地加大，例如n=166时，p=1050(9.353610465×1049)。m-C2：只要知道n次本原多项式，m序列极易生成。m-C3：m序列极不安全，只要泄露2n位连续数字，就可完全确定出反馈多项式系数。

2/26/2024121

m序列的破译已知ki,ki+1,…,ki+2n，由递推关系式可得出下式

式中有n个线性方程和n个未知量，故可惟一解出ci，0

i

n-1。2/26/2024122三、B-M综合算法

根据密码学的需要，对于LFSR主要考虑下面两问题：(1)如何利用级数尽可能小的LFSR产生周期长、统计特性好的序列；(2)已知一个序列a，如何构造一个尽可能短的LFSR来产生a。2/26/2024124B-M综合算法2/26/20241252/26/20241262/26/2024127B－M综合算法的描述2/26/2024128四、非线性序列

非线性序列线性复杂度：能产生周期序列{ki}i

0的LFSR的最小级数n。

显然，n级m序列的线性复杂度为n。线性复杂度是研究和设计密码的重要指标和工具。一个伪随机序列若其线性复杂度低，就易于由部分序列综合出生成它的LFSR。一般移存器序列的线性复杂度n<L<2n。L大不一定就安全；但L小肯定是不安全的!

2/26/2024130非线性前馈序列LFSR虽然不能直接作为密钥流用，但可作为驱动源以其输出推动一个非线性组合函数所决定的电路来产生非线性序列。这就是所谓非线性前馈序列生成器。LFSR用来保证密钥流的周期长度、平衡性等非线性组合函数用来保证密钥流的各种密码性质，以抗击各种可能的攻击。

2/26/2024131非线性前馈序列

LFSR

…

F

ki研究的中心问题：前馈函数F与输出序列的周期性、随机性、线性复杂度以及相关免疫性之间的关系。

2/26/2024132多路选择(Multiplexing)序列

有n种输入序列b0(t),…,

bn-1(t)

，在地址序列a1(t),…,am-1

(t)的控制下决定输出取自某个输入比特。例如取m级LFSR生成m序列作地址控制，取n级LFSR生成的m序列作为输入序列。2/26/2024133多路选择(Multiplexing)序列

可供选择的输入

…

多路选择器

多路选择密码

2/26/2024134J-K触发器

J-K触发器是一个非线性器件，有两个输入端j，k和一个内部状态，即输出为qi,，其逻辑真值如表3-3-2所示。一般令q-1=0。表3-3-2JK qiGeffe[1973]采用三个LFSR，其中两个的输

00 qi-1

出通过一个J-K触发器进行复合。如图3-3-

901 0 所示。还可进一步推广由s＋1个LFSR10 1 进行复合。LFSR-1的时钟必须较其它s11 个LFSR的时钟快log2(s)倍，其中s为2的幂次。2/26/2024135

Geffe生成器

2中择1多路选择器

LFSR-2

选择b(t)LFSR-3LFSR-1

图3-3-9Geffe生成器

多路复合器输入两两成对，并以J-K触发器进行复合后送入多路复用器。这类生成器的安全性不高，易受相关攻击。

2/26/2024136钟控序列生成器

钟控序列10多年前提出的一种新的密钥流生成法，这种方法所生序列的线性复杂度与生成器输入参数间具有指数的关系。这类序列易于由硬件实现。钟控移位寄存器的级连是一种重要的序列的流密码备选体制。

2/26/2024137

分组密码一、分组密码的一般模型二、DES与IDEA三、AES算法——Rijndael四、分组密码分析方法*五、分组密码工作模式2/26/2024138一、分组密码的一般模型分组密码概述

分组密码：将消息编码表示后的数字（通常是0和1）序列x1,x2,…,xi,…划分为长为n的组，各组（长为n的矢量）分别在密钥的控制下变换成等长的输出数字序列（长为m的矢量）。

2/26/2024140

分组密码是一种满足下列条件的映射E：对每个，是从

到的置换：密钥为时的加密函数：密钥为时的解密函数密钥规模：bit密钥长度等于密钥规模当且仅当：Eg:DES真正的密钥规模=56bit,且也就是密钥长度2/26/2024141分组密码设计问题

分组密码的设计问题在于找到一种算法，能在密钥控制下从一个足够大且足够好的置换子集中，简单而迅速地选出一个置换，用来对当前输入的明文的数字组进行加密变换。2/26/2024142分组密码算法应满足的要求分组长度n要足够大：防止明文穷举攻击法奏效。密钥量要足够大：尽可能消除弱密钥并使所有密钥同等地好，以防止密钥穷举攻击奏效。由密钥确定置换的算法要足够复杂：充分实现明文与密钥的扩散和混淆，没有简单的关系可循，要能抗击各种已知的攻击2/26/2024143分组密码算法应满足的要求加密和解密运算简单：

易于软件和硬件高速实现。数据扩展：一般无数据扩展，在采用同态置换和随机化加密技术时可引入数据扩展。差错传播尽可能地小2/26/2024144二、DES与IDEA数据加密标准（DES）DES的历史1971年IBM，由HorstFeistel领导的密码研究项目组研究出LUCIFER算法，并应用于商业领域;1973年,美国标准局征求标准，IBM提交结果;1977年，被选为数据加密标准;虽然DES已有替代的数据加密标准算法，但它仍是迄今为止得到最广泛应用的一种算法，也是一种最有代表性的分组加密体制。2/26/2024146DES加密过程

DES利用56bit长度的密钥K来加密长度为64bit的明文，得到长度为64bit的密文该算法分三个阶段实现IP和IP-1在密码意义上作用不大，它们的作用在于打乱原来输入x的ASCII码字划分的关系，并将原来明文的校验位x8,x16,

,x64变成为IP输出的一个字节。

2/26/2024147一轮加密的简图

2/26/2024148Li-1Ri-1F+LiRiKiA=R(32bits)J=K(48bits)EE(A)为48bits+B1B2B3B4B5B6B7B8

S1S2S3S4S5S6S7S8C1C2C3C4C5C6C7C8P32bitsF(A,J)B写成8个6比特串对F函数的说明：F（Ri-1,Ki）函数F以长度为32的比特串A=R（32bits）作第一个输入，以长度为48的比特串变元J=K(48bits)作为第二个输入。产生的输出为长度为32的位串。对第一个变元A，由给定的扩展函数E，将其扩展成48位串E（A）；计算E(A)+J，并把结果写成连续的8个6位串,

B=b1b2b3b4b5b6b7b8

2/26/2024149

使用8个S盒，每个Sj是一个固定的416矩阵，它的元素取0到15的整数。给定长度为6个比特串如Bj=b1b2b3b4b5b6,计算Sj(Bj)如下：b1b6两个比特确定了Sj的行r(0<=r<=3);而b2b3b4b5四个比特确定了Sj的列数c（0<=c<=15）。最后Sj(Bj)的值为S-盒矩阵Sj中r行c列的元素（r,c）,得Cj=Sj(Bj)。最后，P为一个固定置换。2/26/2024150选择压缩运算S

2/26/2024151子密钥的生成从密钥K计算子密钥：实际上，K是长度为64的位串，其中56位是密钥，8位是奇偶校验位（为了检错），在密钥编排的计算中，这些校验位可略去。给定64位的密钥K，放弃奇偶校验位（8，16，…，64）并根据固定置换PC-1来排列K中剩下的位。PC-1(K)=C0D0

。其中C0由PC-1（K）的前28位组成；D0由后28位组成。对1<=i<=16，计算

Ci=LSi(Ci-1)Di=LSi(Di-1)

LSi表示循环左移2或1个位置，取决于i的的值。2/26/2024152子密钥的生成

i=1,2,9和16时移1个位置，否则移2位置。

Ki=PC-2(CiDi),

PC-2为固定置换。

一共16轮，每一轮使用K中48位组成一个48比特密钥。可算出16个表，第i个表中的元素可对应上第i轮密钥使用K中第几比特！如：第7轮的表7：K7取K中的比特情况：

52571112659103444512519

941325035364342336018

2871429474622515636139

431

13385362552023373062/26/2024153子密钥的生成

2/26/2024154K(64bit)PC-1C0D0LS1LS1C1D1LS2LS2LS16LS16C16D16PC-2PC-2K1K16…除去第8,16,

,64位(8个校验位)28bitDES加密的一个例子取16进制明文X：0123456789ABCDEF

密钥K为：133457799BBCDFF1

去掉奇偶校验位以二进制形式表示的密钥是00010010011010010101101111001001101101111011011111111000

应用IP，我们得到：

L0=11001100000000001100110011111111

L1=R0=11110000101010101111000010101010

然后进行16轮加密。

最后对L16,R16使用IP-1得到密文：85E813540F0AB405

DES解密和加密使用同一算法，但子密钥使用的顺序相反2/26/2024155DES的安全性互补性：DES算法具有下述性质。若明文组x逐位取补，密钥k逐位取补，即y=DESk(x),则有这种互补性会使DES在选择明文破译下所需的工作量减半。绝大多数消息并无明文补分组。弱密钥和半弱密钥：DES算法在每次迭代时都有一个子密钥供加密用。如果给定初始密钥k，各轮的子密钥都相同，即有k1=k2=…=k16，就称给定密钥k为弱密钥(Weakkey)。2/26/2024156DES的安全性若k为弱密钥，则有：DESk(DESk(x))=xDESk-1(DESk-1(x))=x即以k对x加密两次或解密两次都可恢复出明文。其加密运算和解密运算没有区别。弱密钥下使DES在选择明文攻击下的搜索量减半如果随机地选择密钥，弱密钥所占比例极小，而且稍加注意就不难避开。因此，弱密钥的存在不会危及DES的安全性。2/26/2024157DES的安全性DES的密钥长度可能太小DES的迭代次数可能太少S盒中可能有不安全因素DES的关键部分不应当保密2/26/2024158三重DES

1.两重DES加密的强度一定等价于112bit密钥的密码的强度吗？考虑对任意密钥k1和k2,能够找出另一密钥k3，使

Ek2[Ek1[P]]=Ek3[P],这种假设成立吗？2.若有明文密文对(P,C)满足yi=Ek2[Ek1[P]]，则可得z=Ek1[P]=Dk2[C]。考虑这种攻击的情况。

3.使用三个不同的密钥做三次加密就能抵抗中途相遇攻击吗？2/26/2024159三重DES使用两个密钥做三次加密，实现方法为加密—解密—加密，简记EDE(encrypt-decrypt-encrypt)。2/26/2024160三重DES加密：y=Ek1[Dk2[Ek1[x]]]解密：x=Dk1[Ek2[Dk1[y]]]破译它的穷举密钥搜索量为2112

5×1035量级，而用差分分析破译也要超过1052量级。此方案仍有足够的安全性。没有针对三重DES的攻击方法，它是一种较受欢迎的DES替代方案。此方案已在ANSIX9.17和ISO8732标准中采用，并在保密增强邮递(PEM)系统中得到利用。2/26/2024161IDEA算法IDEA的历史1990年，瑞士的来学嘉（XuejiaLai）和JamesMassey于1990年公布了IDEA密码算法第一版，称为PES(ProposedEncryptionStandard)；1991年，为抗击差分密码攻击，他们增强了算法的强度，称IPES（ImprovedPES)；1992年，改名为IDEA（InternationalDataEncryptionAlgorithm）。2/26/2024162

IDEA加密过程IDEA是一个分组长度为64bit的分组密码算法，密钥长度为128bit（抗强力攻击能力比DES强），同一算法既可加密也可解密。IDEA的“混淆”和“扩散”设计原则来自三种运算，它们易于软、硬件实现（加密速度快）：2/26/2024163Z6F2F1Z5G1G22/26/2024164在IDEA的模乘运算中，为什么将模数取为216+1，而不是216

？

在其模加运算中，为什么模数取为216而不是216+1？

2/26/2024165IDEA加密的总体方案图循环2循环8循环1输出变换64位密文64位明文Z1Z6Z7Z12Z43Z48Z49Z52子密钥生成器128bit密钥Z1Z5216IDEA加密的单个循环图2/26/2024166X1X2X3X4Z1Z2Z3Z4Z5Z6W11W12W13W14IDEA的密钥生成56个16bit的子密钥从128bit的密钥中生成前8个子密钥直接从密钥中取出；对密钥进行25bit的循环左移，接下来的密钥就从中取出；重复进行直到52个子密钥都产生出来。2/26/2024167IDEA的解密加密解密实质相同，但使用不同的密钥；解密密钥以如下方法从加密子密钥中导出：解密循环I的头4个子密钥从加密循环10－I的头4个子密钥中导出；解密密钥第1、4个子密钥对应于1、4加密子密钥的乘法逆元；2、3对应2、3的加法逆元；对前8个循环来说，循环I的最后两个子密钥等于加密循环9－I的最后两个子密钥；2/26/2024168IDEA简介(Cont.)实现上的考虑使用子分组：16bit的子分组；使用简单操作（易于加法、移位等操作实现）；加密解密过程类似；规则的结构（便于VLSI实现）。2/26/2024169IDEA的安全性IDEA能抗差分分析和相关分析；IDEA似乎没有DES意义下的弱密钥；IDEA是PGP的一部分；BruceSchneier认为IDEA是DES的最好替代，但问题是IDEA太新，许多问题没解决。2/26/2024170三、AES算法-RijindaelAES的历史1997年1月，美国NIST向全世界密码学界发出征集21世纪高级加密标准（AES——AdvancedEncryptionStandard）算法的公告，并成立了AES标准工作研究室，稍后制定了对AES的评估标准；1998年8月，在首届AES候选会议上公布了AES的15个候选算法，任由全世界各机构和个人攻击和评论；2000年4月，召开了第三届AES候选会议，继续对最后的五个候选算法进行讨论；

2000年10月，NIST宣布Rijndael作为新的AES，至此，经过三年多的讨论，Rijndael终于脱颖而出。2/26/2024172AES的评估准则AES是公开的；AES为单钥体制分组密码；AES的密钥长度128/192/256bit;AES适于用软件和硬件实现；AES可以自由地使用，或按符合美国国家标准（ANST）策略的条件使用；2/26/2024173AES的评估准则满足以上要求的AES算法，需按下述条件判断优劣安全性

代价：各种实现的计算效率（速度和存储需求），包括软件实现、硬件实现和智能卡实现等；算法和实现特性：包括算法的灵活性、简洁性及其它因素。2/26/2024174Rijndael算法设计原理Rijndeal密码的设计力求满足以下标准：抵抗所有的已知攻击

在多个平台上速度快，编码紧凑设计简单Rijndael没有采用Feistel结构，轮函数由3个不同的可逆均匀变换构成的，称为3个层均匀变换是指状态的每个bit都用类似的方法处理2/26/2024175宽轨迹策略“宽轨迹策略”是针对抗差分分析和线性分析提出的；优点：可以给出算法的最佳差分特征的概率即最佳线性逼近的偏差边界，由此可以分析算法抵抗差分密码及线性密码分析的能力；实现方法：轮函数3层中的每层都有它自己的功能：线性混合层：确保多轮之上的高度扩散；非线性层：将具有最优的“最坏情况非线性特性”的S盒并行使用；密钥加层：单轮子密钥简单的异或到中间状态上，实现一次性掩盖。2/26/2024176Rijndael算法描述Rijndael是分组和密钥都可变的迭代分组加密算法，分组和密钥长度可分别为128，192，256位；加密之前，首先把数据块写成字的形式，其次把字记为列的形式。算法中间的结果也需要分组，称之为状态。状态可以用以字节为元素的矩阵阵列表示，该阵列有4行，列数Nb为分组长度除32；种子密钥类似地以字节为元素的矩阵阵列表示，阵列为4行，列数Nk为密钥长度除32；算法轮数Nr由Nb和Nk共同决定2/26/2024177Nb=6和Nk=4的状态密钥阵列2/26/2024178按此顺序放入和读出按此顺序放入按此顺序放入和读出按此顺序放入按此顺序放入和读出按此顺序放入分组和阵列中元素对应关系分组下标n阵列位置(i,j)i=nmod4,j=[n/4];n=i+4j轮数Nr与Nb和Nk对应关系Nb=4Nb=6Nb=8Nk=4101214Nk=6121214Nk=81414142/26/2024179Rijndael

加密过程2/26/2024180字节代换非线性代换，独立地对状态的每个字节进行，并且代换表(S盒)可逆，记为ByteSub(State),分两步：将字节作为GF(28)上的元素映射到自己的逆元将字节做如下的GF(2)上变换2/26/2024181行移变换将状态阵列的各行进行循环移位，记为ShiftRow(State)。不同行的移位量不同：0行：不动1行：循环左移C1字节2行：循环左移C2字节3行：循环左移C3字节2/26/2024182移位量与分组长度的关系NbC1C2C3412361238134列混合变换列混合变换表示为MixColumn(State)将每列视为GF(28)上多项式，与固定的多项式c(x)进行模x4+1乘法,要求c(x)模x4+1可逆。2/26/2024183密钥加