信息安全基础全册配套课件

信息安全基础全册配套课件信息安全基础授课教师：刘斌北京邮电大学数学学士、密码学博士计算机学院信息系QQ：283628719课件资料下载：http:///s/1mikhT3a3《密码编码学与网络安全》

WilliamStallings电子工业出版社信息安全基础4课程目标学习并掌握信息安全的基本原理和系统架构学习并掌握密码学与网络安全的基本概念，领会密码体制设计与分析的基本思想与方法，了解相关领域的最新研究成果；了解设计和维护安全的网络及其应用系统的基本手段和常用方法，具备解决网络与信息安全方面的工程实践问题的能力和进行信息安全研究的理论基础。课程内容对称密码※古典密码※分组密码※伪随机数与流密码公钥密码※数论基础※公钥密码与RSA※密钥管理和其他公钥密码数据完整性※Hash※消息认证码※数字签名相互信任※密钥管理与分发※用户认证网络安全与Internet安全※网络访问控制与云安全※传输层安全※无线网络安全※电子邮件安全※IP安全成绩构成平时分（20%）：包括作业与出勤实践项目（20%）20个左右的题目抽签选题4人一组，自行分组实验（20%）：四次实验的平均分分组进行，组别同上期末考试（40%）考核方式第1章概览OSI安全框架7计算机安全概念计算机安全的概念网络安全模型OSI安全框架1-3安全攻击1-4安全服务1-5安全机制网络安全模型（ISO制定的OSI模型）ISO：国际标准化组织InternationalOrganizationofStandardizationOSI：开放式系统互联OpenSystemInterconnection8第1章概览计算机安全的概念OSI安全框架网络安全模型[计算机安全(ComputerSecurity)]对于一个自动化的信息系统，采取保护措施确保信息系统资源（包括硬件、软件、固件、信息/数据和通信）的保密性、完整性、可用性。——NIST《计算机安全手册》[网络安全(NetworkSecurity)]

保护数据在传输中安全的方法[互联网安全(InternetSecurity)]

保护数据安全通过互联网络的方法NIST：美国国家标准与技术研究院NationalInstituteofStandardsandTechnology9第1章概览计算机安全的概念OSI安全框架网络安全模型网络安全核心地位的三个关键目标[保密性(Confidentiality)]数据保密性隐私性[完整性(Integrity)]（包括不可否认性、真实性）数据完整性系统完整性[可用性(Availability)][真实性(Authenticity)][可追朔性(Accountability)]可控性隐私及秘密不泄露、不被非法使用个人自身信息的保护信息和程序只能以特定和授权的方式进行改变确保系统已正常的方式执行预定功能，免于非授权操作确保系统工作迅速，不拒绝正常用户保密性缺失：信息泄露完整性缺失：信息被修改、损坏可用性缺失：访问和使用中断10第1章概览计算机安全的概念OSI安全框架网络安全模型安全泄露事件的影响：低、中、高低中高保密性学生名单注册信息成绩完整性匿名在线民意调查无广告收入的娱乐网站病历过敏信息可用性网上校历、课表查询成绩查询系统选课系统11第1章概览计算机安全的概念OSI安全框架网络安全模型[威胁]：破坏安全的潜在可能，脆弱性被利用而可能带来的危险。[攻击]：具有智能的威胁，有意违反安全服务和侵犯安全策略的智能行为。对于信息系统来说威胁可以是针对物理环境，通信链路，网络系统，操作系统，应用系统以及管理系统等方面物理安全威胁是指对系统所用设备的威胁，包括自然灾害，电源故障，操作系统引导失败或数据库信息丢失，设备被盗，被毁造成数据丢失或信息泄露等通信链路安全威胁如在传输线路上安装窃听装置或对通信链路进行干扰操作系统安全威胁，如在操作系统或硬件芯片中植入“木马”，“陷阱门”等应用系统安全威胁是指对于网络服务或用户业务系统安全的威胁12第1章概览计算机安全的概念OSI安全框架网络安全模型ITU-TX.800“SecurityArchitectureforOSI”即OSI安全框架；给出了一种系统化的定义方法。是提供安全的一种组织方法；提供了一个有用的学习研究的概貌。ITU:国际电信联盟OSI:开放式系统互联安全攻击安全服务安全机制危害信息系统安全的行为预防、阻止攻击或从攻击状态恢复正常的过程提高安全性的处理过程和通信服务13第1章概览计算机安全的概念OSI安全框架网络安全模型安全攻击安全服务安全机制被动攻击主动攻击14第1章概览计算机安全的概念OSI安全框架网络安全模型安全攻击安全服务安全机制被动攻击对传输进行窃听和监测，不对数据信息做任何修改·消息内容的泄露·流量分析(Trafficanalysis)

《特例》量子通信可以有效检测被动攻击特点是难以检测，但可以防范被动攻击15第1章概览计算机安全的概念OSI安全框架网络安全模型安全攻击安全服务安全机制主动攻击主动攻击包括对数据流进行修改和伪造数据流，包括四类·伪装(②有效)

·重播(①②③有效)·消息篡改(①②有效)

·拒绝服务（③有效）

123特点是难以防范，但可以检测16第1章概览计算机安全的概念OSI安全框架网络安全模型安全攻击安全服务安全机制X.800:为系统协议层提供的服务，用来保证系统或数据的传输有足够的安全性。RFC4949:一种由系统提供的对系统资源进行特殊保护的处理或通信服务，安全服务通过安全机制来实现安全策略。17第1章概览计算机安全的概念OSI安全框架网络安全模型安全攻击安全服务安全机制认证服务(Authentication)※同等实体认证※数据源认证访问控制服务(Accesscontrol)数据机密性服务(DataConfidentiality)※连接保密性※无连接保密性※选择域保密性※流量保密性数据完整性服务(DataIntegrity)不可否认性服务(Non-repudiation)※源不可否认性※宿不可否认性可用性服务(Availability)对抗伪装对抗被动对抗篡改对抗拒绝服务18第1章概览计算机安全的概念OSI安全框架网络安全模型安全攻击安全服务安全机制要具备检测、防御或从安全攻击中恢复的能力没有单一的机制能够提供所有的安全服务一个机制往往构成其它安全机制的基础，如:加密技术特定的安全机制（specificsecuritymechanisms）:加密，

数字签名，

访问控制，数据完整性，认证交换，流量填充，路由控制，公证等普遍的安全机制（pervasivesecuritymechanisms）:可信功能，安全标签，事件检测，安全审计跟踪，安全恢复等19第1章概览计算机安全的概念OSI安全框架网络安全模型安全攻击安全服务安全机制安全服务与安全机制之间的关系20第1章概览计算机安全的概念OSI安全框架网络安全模型与待发送信息安全相关的变换（如：加密算法）双方共享某些秘密信息（如：密钥）本书前五部分涉及的网络安全模型21第1章概览计算机安全的概念OSI安全框架网络安全模型与待发送信息安全相关的变换（如：加密算法）双方共享某些秘密信息（如：密钥）设计安全服务应包含四个方面内容：

设计一个攻击者无法攻破的算法，用以执行与安全相关的变换产生算法所使用的秘密信息设计分配和共享秘密信息的方法指明通信双方使用的协议，该协议利用安全算法和秘密信息实现安全服务22第1章概览计算机安全的概念OSI安全框架网络安全模型其他网络安全模型23总结：作业:思考题1.1、1.2、1.4、1.5习题1.1计算机安全OSI安全框架网络安全模型保密性完整性可用性真实性可追溯性安全攻击：被动攻击2类

主动攻击4类安全服务：6类安全机制：2大类8+5小类第1章概览第2章传统加密技术对称加密技术密码学简史242.1对称密码模型2.1.1密码编码学2.1.2密码分析和穷举攻击2.2代替技术2.3置换技术2.4转轮机2.5隐写术密码学简介第2章传统加密技术密码学简史对称加密技术25密码学简介什么是密码？Password、口令第2章传统加密技术密码学简史对称加密技术26密码学简介Password、口令这并不是“密码学”(Cryptography)中的密码第2章传统加密技术密码学简史对称加密技术27密码学简介“密码学”中的“密码”指的是什么？加密(encrypt)：将明文转化为密文的过程解密(decrypt)：将密文转化为明文的过程密码学的两个分支密码编码学密码分析学第2章传统加密技术密码学简史对称加密技术28密码学简介密码学的术语一个密码系统(Cryptosystem)主要涉及以下5个概念明文：需要加密的原始信息，用p表示；明文空间P密文：明文经过变换或伪装，形成密文，用c表示；密文空间C密钥：加密解密算法的输入，独立于明文与算法；包含加密密钥ek和解密密钥dk；密钥空间K加密算法Enc:PxK→C解密算法Dec:CxK→P密钥一般是变化的，而且必须是保密的加密解密算法一般是确定的，是可以公开的第2章传统加密技术密码学简史对称加密技术29密码学简介研究内容主要研究对信息进行编码，实现对信息的隐蔽。特征运算类型：代换与置换（隐写）所用的密钥数：单钥（对称密码）与双钥（公钥密码）处理明文的方法：分组密码、流密码密码编码学密码分析学Cryptography第2章传统加密技术密码学简史对称加密技术30密码学简介破译密码的一般方法密码分析学：cryptoanalyticattack依赖于算法的性质、明文的一般特征或某些明密文对。找规律、利用规律。穷举攻击：ExhaustiveAttack；又称为蛮力攻击：brute-forceattack尝试所有可能的密钥。密码编码学密码分析学CryptographyCryptanalysis第2章传统加密技术密码学简史对称加密技术31密码学简介基于密码分析的攻击惟密文攻击，ciphertextonly

加密算法、密文已知明文攻击，knownplaintext

加密算法、密文、一些明密文对选择明文攻击，chosenplaintext加密算法、密文、分析者选择的明文、及对应的密文选择密文攻击，chosenciphertext

加密算法、密文、分析者选择的一些密文、及对应的明文选择文本攻击，chosentext选择明文攻击+选择密文攻击密码编码学密码分析学CryptographyCryptanalysis第2章传统加密技术密码学简史对称加密技术32密码学简介已知明文攻击密码编码学密码分析学CryptographyCryptanalysis第2章传统加密技术密码学简史对称加密技术33密码学简介选择明文攻击密码编码学密码分析学CryptographyCryptanalysis第2章传统加密技术密码学简史对称加密技术34密码学简介惟密文攻击密码编码学密码分析学CryptographyCryptanalysis第2章传统加密技术密码学简史对称加密技术35密码学简介选择密文攻击密码编码学密码分析学CryptographyCryptanalysis第2章传统加密技术密码学简史对称加密技术36密码学简介穷举攻击第2章传统加密技术密码学简史对称加密技术37密码学简介密码系统安全性评价无条件安全，unconditionalsecurity也称信息理论上安全即使攻击者拥有无限的计算资源，也无法攻破密码系统。计算安全，computationalsecurity攻击者只拥有有限的计算资源，无法攻破密码系统：破译密文的代价超过被加密信息的价值破译密文所花时间超过信息的有效期可证明安全通过归约的方式为安全性提供证据，如果可用某一个具体的方法破译某个密码体制，那么就有可能有效地解决某伞被认为因难的数学问题第2章传统加密技术密码学简史对称加密技术38密码学简介对称密码模型发送方和接收方共享一个共同的密钥20世纪70年代以前，对称密码是唯一的加密类型至今仍广泛应用第2章传统加密技术密码学简史对称加密技术39密码学简介第2章传统加密技术密码学简史对称加密技术密码学简介40对称密码安全的两个必备条件:加密算法必须是足够强的惟有发送者和接收者知道的秘密密钥换句话说假设加/解密算法是已知的且足够安全的拥有一个安全通道用于分发密钥加密解密算法的数学表示: C=EK(P) P=DK(C)第2章传统加密技术密码学简史对称加密技术41密码学简介所有加密技术的两个基本模块代替将字母替换成其他字母、数字或符号的方法。置换对明文置换的方法。隐写术（严格地讲并不是加密）第2章传统加密技术密码学简史对称加密技术密码学简介42密码学简史古典密码：手工密码埃及人、希伯来人、亚述人、希腊人Scytale凯撒密码机械密码单表代替、多表代替、转轮密码ScytaleEnigma密码学简史近、现代密码：DES、AES、RSA、MD、SHAShannon的信息论：只有密钥长度与明文长度一样的加密才是绝对安全的——即一次一密后量子时代：抵御量子计算的威胁量子密码（信息论安全）格密码等（针对shor算法等已知量子算法安全）第2章传统加密技术密码学简史对称加密技术密码学简介43密码系统明文p：消息(秘密)本身，文本等。明文空间P密文c：明文加密后的形式。密文空间C密钥k：加密密钥、解密密钥。密钥空间K加密算法E：根据K将M变为C的算法解密算法D：根据K将C还原为M的算法第2章传统加密技术密码学简史对称加密技术44密码学简介44明文p加密算法模块解密算法模块密文c原式明文p第2章传统加密技术密码学简史对称加密技术45密码学简介45计算机出现之前，人们如何传递秘密信息古典密码时期公元前2000年，古埃及——特殊文字第2章传统加密技术密码学简史对称加密技术46密码学简介46计算机出现之前，人们如何传递秘密信息古典密码时期公元前2000年，古埃及——特殊文字问题：属于什么加密技术？密钥空间是什么？这种方法在近代仍有使用：二战时美国海军陆战队利用印第安语传递信息。（电影《风语者》）语言学在某种意义上也是一种密码分析学第2章传统加密技术密码学简史对称加密技术密码学简介47计算机出现之前，人们如何传递秘密信息古典密码时期公元前2000年，古埃及——特殊文字公元前500年，希伯来人——AtbashABCDEFGHIJKLMNOPQRSTUVWXYZZYXWVUTSRQPONMLKJIHGFEDCBA公元前440年，古希腊人这么做找个奴隶，剃光头发，头皮上写字等奴隶头发长长，将奴隶送至另一个部落再次剃光头发第2章传统加密技术密码学简史对称加密技术密码学简介48中国、印度也有类似的加密手段《六韬》中的“阴书”：敌虽圣智，莫能识之藏头诗第2章传统加密技术密码学简史对称加密技术密码学简介49中国、印度也有类似的加密手段《六韬》中的“阴书”：敌虽圣智，莫能识之藏头诗上述这些都不能算是真正的密码，因为密码的安全性不应依赖于加密体制的保密性而应该依赖于加密算法自含的变化——密钥上述加密算法的密钥空间为0公认的最早的密码——斯巴达的Scytale第2章传统加密技术密码学简史对称加密技术密码学简介50公元前5-7世纪出现的Scytale密钥——棍子的直径密钥空间？加密类型？密文：HENTEIDTLAEAPMRCMUAK置换第2章传统加密技术密码学简史对称加密技术密码学简介51公元前5-7世纪出现的Scytale密钥——棍子的直径密钥空间？加密类型？密文：HENTEIDTLAEAPMRCMUAK置换第2章传统加密技术密码学简史对称加密技术密码学简介52公元前5-7世纪出现的Scytale密钥——棍子的直径密钥空间？加密类型？密文：HENTEIDTLAEAPMRCMUAK置换第2章传统加密技术密码学简史对称加密技术密码学简介53公元前5-7世纪出现的Scytale密钥——棍子的直径密钥空间？加密类型？密文：HENTEIDTLAEAPMRCMUAK置换第2章传统加密技术密码学简史对称加密技术密码学简介54公元前5-7世纪出现的Scytale密钥——棍子的直径密钥空间？加密类型？密文：HENTEIDTLAEAPMRCMUAK|H|E|L|P|M||E|I|A|M|U||N|D|E|R|A||T|T|A|C|K|明文：HelpmeIamunderattack置换第2章传统加密技术密码学简史对称加密技术密码学简介55公元前1世纪出现的Caeser密码EFGHIJK

LMNOP

Q

RS

TUVWXY

ZABCDA

BCDEFG

HI

JKL

MNO

PQRSTUVWXY

Z凯撒密码第2章传统加密技术密码学简史对称加密技术密码学简介56公元前1世纪出现的Caeser密码加密方法——字母按顺序位移密钥空间？密文：QEBNRFZHYOLTKCLUGRJMPLSBOQEBIXWVALD26ABCDEFGHIJKLMNOPQRSTUVWXYZABCDEFGHIJKLMNOPQRSTUVWXYZABCDEFG代替凯撒密码第2章传统加密技术密码学简史对称加密技术密码学简介57公元前1世纪出现的Caeser密码加密方法——字母按顺序位移密钥空间？密文：QEBNRFZHYOLTKCLUGRJMPLSBOQEBIXWVALD26ABCDEFGHIJKLMNOPQRSTUVWXYZABCDEFGHIJKLMNOPQRSTUVWXYZABCDEFG代替凯撒密码第2章传统加密技术密码学简史对称加密技术密码学简介58公元前1世纪出现的Caeser密码加密方法——字母按顺序位移密钥空间？密文：QEBNRFZHYOLTKCLUGRJMPLSBOQEBIXWVALD26ABCDEFGHIJKLMNOPQRSTUVWXYZABCDEFGHIJKLMNOPQRSTUVWXYZABCDEFG代替凯撒密码第2章传统加密技术密码学简史对称加密技术密码学简介59公元前1世纪出现的Caeser密码加密方法——字母按顺序位移密钥空间？密文：QEBNRFZHYOLTKCLUGRJMPLSBOQEBIXWVALD明文：Thequickbrownfoxjumpsoverthelazydog26ABCDEFGHIJKLMNOPQRSTUVWXYZABCDEFGHIJKLMNOPQRSTUVWXYZABCDEFG代替凯撒密码第2章传统加密技术密码学简史对称加密技术密码学简介60凯撒密码方式二：加密：将字母编码：a=0，b=1，…，z=25，则明文P＝p1p2…pn（加密）运算：Ci＝pi+k（mod26）,i＝1,2,…,n解码得密文：C＝c1c2…cn解密：密文C＝c1c2…cn（加密）运算：pi＝ci-k（mod26）,i＝1,2,…,n解码得明文：P＝p1p2…pn方式一：查表第2章传统加密技术密码学简史对称加密技术密码学简介61凯撒密码Caeser密码的密钥空间太小仿射密码（可以看作凯撒密码的推广）加密算法：c=a*p+b(mod26)，a，b<26且a与26互素解密算法：p=a-1*

(c-b)(mod26)密钥空间？a可能的取值：除去13以外的奇数，12种12*26=312第2章传统加密技术密码学简史对称加密技术密码学简介62密钥空间还是不够大单表替换密码26个字母表的随机替换密钥空间？“天河二号”：3.4*10^16次/秒10^10秒>317年26！=4*10^26凯撒密码单表代替密码第2章传统加密技术密码学简史对称加密技术密码学简介63凯撒密码单表代替密码频度攻击（利用了语言学和统计学）公元8世纪，由阿拉伯人首次提出我䨻凯撒密码单表代替密码第2章传统加密技术密码学简史对称加密技术密码学简介64频度攻击e,t,ao,I,n,s,r,h……j,q,x,z明文与密文字母频率不变密文足够长，只需统计每个字母出现的频率即可第2章传统加密技术密码学简史对称加密技术密码学简介65凯撒密码单表代替密码凯撒密码仿射密码穷举攻击单表代替密码频度攻击如果你是密码学家，接下来会怎么做？隐藏频度多字母代替多表代替密码Playfair密码、Hill密码Vigenere密码、Vernam密码第2章传统加密技术密码学简史对称加密技术密码学简介66凯撒密码单表代替密码多字母代替多表代替Playfair密码Playfair的密钥矩阵5X5

I=J构造步骤：填写密钥单词用其他字母按顺序填写剩下的空缺例子：密钥为monarchy时CharlesWheatstone于1854年发明,用其朋友BaronPlayfair

命名。第2章传统加密技术密码学简史对称加密技术密码学简介67凯撒密码单表代替密码多字母代替多表代替Playfair密码加密明文分组（填充）：2个字母／组同行字母对加密：循环向右，ar→RM同列字母对加密：循环向下，cu→EM，xi→AS其它字母对加密：矩形对角线字母，且按行排序，hs→BP，

ea→IM（或JM）解密加密的逆向操作第2章传统加密技术密码学简史对称加密技术密码学简介68凯撒密码单表代替密码多字母代替多表代替Playfair密码Playfair密码在一战和二战中被大量使用安全性分析：安全性优于单表代替密码密钥空间：虽然明文中字母的统计规律在密文中得到了降低，但密文中仍含有明文的部分结构信息给定几百个字母，即可被攻破明、密文字母不是一一对应关系＝25！≈1.6×1025第2章传统加密技术密码学简史对称加密技术密码学简介69凯撒密码单表代替密码多字母代替多表代替Hill密码1929年由数学家LesterHill发明。

第2章传统加密技术密码学简史对称加密技术密码学简介70凯撒密码单表代替密码多字母代替多表代替Hill密码

K第2章传统加密技术密码学简史对称加密技术密码学简介71凯撒密码单表代替密码多字母代替多表代替Hill密码密钥矩阵K＝明文分组P＝“mor”明文编码

P＝＝加密

C≡≡≡

mod26解码

C＝，即C＝“HDL”加密：K－1＝第2章传统加密技术密码学简史对称加密技术密码学简介72凯撒密码单表代替密码多字母代替多表代替Hill密码明文P＝“mor”明文

P＝＝解密

P≡≡≡

mod26C＝C＝“HDL”＝密钥矩阵K＝K－1＝解密：第2章传统加密技术密码学简史对称加密技术密码学简介73凯撒密码单表代替密码多字母代替多表代替Hill密码Hill密码的特点字母的统计规律进一步降低明、密文字母不是一一对应关系加解密算法是线性的安全性分析可以有效抵抗唯密文攻击无法对抗已知明文攻击m×m的密钥，只需要m组线性无关的明文及其对应的密文就足以破解。第2章传统加密技术密码学简史对称加密技术密码学简介74凯撒密码单表代替密码多字母代替多表代替多字母代替密码能够在一定程度上隐藏不同字母的频度。但是仍然有一定的统计特性，比如双字母实质上是把26个字母变成了26*25种双字母（实际上可能更少），三字母可以看作是26*25*24种，当密文足够长时，仍然可以用频度攻击。那么如何彻底地隐藏字母的频度呢？第2章传统加密技术密码学简史对称加密技术密码学简介75多表替换密码表1、表2轮流加密更好地隐藏频度？再多些表！凯撒密码单表代替密码多字母代替多表代替第2章传统加密技术密码学简史对称加密技术密码学简介76凯撒密码单表代替密码多字母代替多表代替76CALCULATEtobeornottobethatisthequestionC：t——VA：o——OL：b——MC：e——G……密钥空间？26+262+263+…+26nVigenere密码第2章传统加密技术密码学简史对称加密技术密码学简介77凯撒密码单表代替密码多字母代替多表代替77Vigenere密码CALCULATEtobeornottobethatisthequestionVOMGICNHXVOMGNSAMMUTSGBFELKOY“VOMG”统计相同字符串之间的间隔确定分组长度分组统计频度例如在密文，FJY相隔的字数分别为：48、72、120、264模8同余位上的密文本质上是单表加密第2章传统加密技术密码学简史对称加密技术密码学简介78凯撒密码单表代替密码多字母代替多表代替Vigenere密码也可以数学公式计算加密：设明文P=p1p2…pn，密钥k=k1k2…kn，密文C=c1c2…cn①明文编码；②计算ci=pi+ki(mod26)，=1，2，…，n；③密文解码。说明：若明文长度大于n，则K重复使用。解密：pi=ci－ki(mod26)，=1，2，…，n第2章传统加密技术密码学简史对称加密技术密码学简介79凯撒密码单表代替密码多字母代替多表代替Vigenere密码

第2章传统加密技术密码学简史对称加密技术密码学简介80凯撒密码单表代替密码多字母代替多表代替Vigenere密码维纳密码的改进利用明文加密明文，具体方法如下将密钥字母加在明文之前，构成没有周期性的密钥，例如上例中的密钥变为：CALCULATEtobeornottobethatisthequestion效果：无论明文有多长，密钥都不会重复。问题：这样又使得密文有了新的统计特性。因为用e加密e的情况会高于用t加密t，使得密文的字符不再是完全随机的了。第2章传统加密技术密码学简史对称加密技术密码学简介81凯撒密码单表代替密码多字母代替多表代替凯撒密码仿射密码单表代替密码多字母代替密码Vigenere密码Enigma一次一密Vernam密码第2章传统加密技术密码学简史对称加密技术密码学简介82凯撒密码单表代替密码多字母代替多表代替Vernam密码基于二进制：ci

=pi

ki

pi

=ci

ki

特点：密钥大周期循环安全性：如果有足够长的密文，无法抵抗已知明文攻击一次一密加解密算法同Vernam特点：密钥长度等于明文长度，且不重复使用。安全性：无条件安全性可以利用Shannon的信息论证明。然而需要共享大量密钥，实现难度太大。第2章传统加密技术密码学简史对称加密技术密码学简介83凯撒密码单表代替密码多字母代替多表代替凯撒密码仿射密码单表代替密码Playfair密码Vigenere密码Enigma一次一密Vernam密码第2章传统加密技术密码学简史对称加密技术密码学简介84转轮机84每加密一个字母，换一个字母表——恩格玛机（1918）第2章传统加密技术密码学简史对称加密技术密码学简介85恩格玛机（1926）ABCDEF……STUVWXYZABCDEF……STUVWXYZABCDEF……STUVWXYZQRSTUV……IJKLMNOPIJKLMN……ABCDEFGHEFGHIJ……WXYZABCD每次输完1个字，轮子1转1格轮子1转完一圈，轮子2转1格轮子2转完一圈，轮子三转1格每次一个表26^3=17576三个轮子顺序可以不同6插线板：最多6组字母对换密码学简史对称加密技术密码学简介86恩格玛机（1926）ABCDEF……STUVWXYZABCDEF……STUVWXYZABCDEF……STUVWXYZQRSTUV……IJKLMNOPIJKLMN……ABCDEFGHEFGHIJ……WXYZABCD每次输完1个字，轮子1转1格轮子1转完一圈，轮子2转1格轮子2转完一圈，轮子三转1格每次一个表26^3=17576三个轮子顺序可以不同6插线板：最多6组字母对换10的16次方！恩格玛机（1926）插线板密码学简史对称加密技术密码学简介8788恩格玛机（1926）ABCDEF……STUVWXYZABCDEF……STUVWXYZABCDEF……STUVWXYZQRSTUV……IJKLMNOPIJKLMN……ABCDEFGHEFGHIJ……WXYZABCD每次输完1个字，轮子1转1格轮子1转完一圈，轮子2转1格轮子2转完一圈，轮子三转1格每次一个表26^3=17576三个轮子顺序可以不同6插线板：最多6组字母对换10的16次方！密码学简史对称加密技术密码学简介89恩格玛机的特点对称性：同一设置下，输入A得B，那么输入B一定得A反自反性：输入A，得到的一定不是A密码学简史对称加密技术密码学简介90恩格玛机加密过程（1926）德军士兵的日常：调整3个转子的顺序调整转子上转轮的位置设置插线板发报时：随机选择三个字母，如THE连续输入两次THETHE→XDRFGH将转轮位置调成THE，开始发送正文密码学简史对称加密技术密码学简介91恩格玛机（二战中）二战开始后，德国人又做了如下改进：轮子3→5、插线板6→101.59*10^20密码学简史对称加密技术密码学简介92恩格玛机的解密过程密码学简史对称加密技术密码学简介93恩格玛机破解波兰人：德国人操作规则的漏洞+纯数学技巧1940年以前，德军使用中的漏洞：发报前连续输入两次同样的3个字母：ABCABC图林：恩格玛的缺陷+德国认得习惯+暴力破解恩格玛机不会将字母映射问字母本身德国人的习惯：早上天气预报会出现wetter；Heil

hitler等常用词汇大约有100万中可能密码学简史对称加密技术密码学简介94Hagelin转轮密码机（盟军）密码学简史对称加密技术密码学简介95M-209

密码机（美国）密码学简史对称加密技术密码学简介96Purple密码机（日本）密码学简史对称加密技术密码学简介97历史上的密码事件公元16世纪晚期，英国人利用频度分析破解苏格兰女王玛丽的密码信，信中策划暗杀英国女王伊丽莎白，这次解密将玛丽送上了断头台。1781年，美军破解了英国的通讯信件，阻止了英军舰队增援约克敦的计划，迫使康华利投降确定了独立战争的胜利一战到关键时刻，英国的“40号房间”用缴获的德国密码本破译了著名的“齐默尔曼电报”，促使美国放弃中立参战，改变了战争进程。二战中，图林破解德军恩格玛机密码学简史对称加密技术密码学简介98栅栏技术思想：以列（行）优先写出明文，以行（列）优先读出各字母作为密文例1：先行后列例2：先列后行改进带有密钥再改进：重复加密，多步置换第2章传统加密技术置换密码99例：栅栏密码(RailFencecipher)明文：meetmeafterthetogaparty写作:mematrhtgpryetefeteoaat读出密文为：MEMATRHTGPRYETEFETEOAAT第2章传统加密技术置换密码100更加复杂的移位以指定的行将明文写作多行按照密钥指定的列读出Key:Plaintext:Ciphertext:TTNAAPTMTSUOAODWCOIXKNLYPETZ

例：行移位密码RowTranspositionCiphers3412567attackpostponeduntiltwoamxyz第2章传统加密技术置换密码101隐藏信息的存在字符标记藏头诗不可见的墨水针刺隐藏在图形图像或声音文件的LSB上缺点需要额外的付出来隐藏相对较少的信息安全性建立在隐写方案的不为人知的条件下可以先加密再隐写与加密方案相比，隐写的通信具有隐蔽性隐写术第2章传统加密技术102第一章命题逻辑作业:思考题2.1、2.3、2.4、2.6、2.12习题2.1、2.4、2.9、2.14总结密码学简介明文空间密文空间密钥空间加密算法解密算法对称加密模型密码编码学密码分析学&代替技术移位密码放射密码多字母代替多表代替转轮机置换技术栅栏密码Scytale隐写术古希腊奴隶图像LSB穷举攻击密码分析唯密文攻击已知明文选择明文选择密文选择文本第3章分组密码与数据加密标准分组密码设计原理DES103传统分组密码结构流密码与分组密码Feistel密码传统分组密码结构数据加密标准DES加密、解密雪崩效应DES强度、算法性质及计时攻击网络安全模型迭代轮数函数F的设计密钥扩展算法104上次说到，仿射密码（含移位密码和凯撒密码）、单表代替密码、多字母代替密码、多表代替密码都不安全；而一次一密虽然安全但并不实用。Shannon提出了乘积密码的思想乘积密码：依次使用两个或两个以上的基本密码，使得密文结构变得更为复杂，达到强于所有单个密码的效果。例如：S1系统的加密解密算法分别为E1k1和D1k1；S2的算法为E2k2和D2k2；S1与S2的乘积密码的加密解密算法为：

E2k2(E1k1

(p))和D1k1(D2k2

(c))注意：并非任何乘积都有效；仿射密码与单表代替密码的乘积仍为单表代替密码分组密码设计原理DES传统分组密码结构105现代的分组密码都是多种变换（包括代替和置换）的乘积那么什么是分组密码呢？加密的两种形式：流密码与分组密码分组密码设计原理DES传统分组密码结构流密码：每次加密数据流的一位或一个字节。106分组密码设计原理DES传统分组密码结构流密码：每次加密数据流的一位或一个字节。分组密码：将一个长度为n的明文组作为整体加密且通常得到的是与之等长的密文组。美国于1973年向社会公开征集数据加密算沽，最后由IBM公司提出的方案中标，由美国国家标准局在1977年颁布成为数据加密标准(DES)。DES是分组加密算法，其分组长度为64，使用56比特密钥。从DES算法投入使用以来，人们一直在试图分析寻找它的弱点，其中差分分析法和线性分析法最具危胁，但这些方法并没有根本性的突破。1997年，在Internet上采用穷举密钥攻击法仅用了96天，即在一台非常普通的PC上成功破译.用专业解密机用56小时(目前仅为几小时)就可破译。107分组密码设计原理DES传统分组密码结构分组密码的历史DES的设计安全期之后设计新的更好的分组密码算法，如IDEA采用多重加密，如TripleDES1997年1月美国回家标准和技术研究所向全世界密码学界发起征集AES(AdvancedEncryptionStandad)算法的公告1999年8月9日NIST宣布第二轮筛选出的5个候选算法，MARS(IBM),RC6(Rivest,RSALab.),RIJI\IDEAL(Rijmen&Daemen),SERPENT(Anderson),TWOFISH(Schiener)2000年10月2日|\IIST宣布比利时密码学专家设计的Rijndael算法作为最终AES的算法108分组密码设计原理DES传统分组密码结构分组密码的历史

109分组密码设计原理DES传统分组密码结构分组密码基本概念理想的分组密码机制密钥太长（分组太短容易被频度分析），难以实现。Feistel指出我们所需要的是对理想分组密码的一个近似体制。只需要找到一种算法，能在密钥控制下从一个足够大且足够好的置换子集中，简单而迅速地选出一个置换，用来对当前输入的明文的数字组进行加密变换回。方法：交替使用代替和置换的乘积密码（方式）交替使用混淆和扩散的乘积密码（效果）110分组密码设计原理DES传统分组密码结构Feistel密码代替：将明文元素或元素组唯一地替换为密文元素或元素组。置换：明文元素的序列被替换为该序列的一个置换。扩散：使明文的统计特征消散在密文中，让每个明文数字尽可能地影响多个密文数字。扩散使明文与密文之间的统计关系尽量复杂。混淆：尽可能使作用于明文的密钥和密文的关系复杂化，使得明文和密文之间，密文和密饲之间的统计相关性极小化，以阻止攻击者发现密钥。111分组密码设计原理DES传统分组密码结构Feistel密码

112分组密码设计原理DES传统分组密码结构Feistel密码结构

113分组密码设计原理DES传统分组密码结构Feistel密码结构分组长度

越长越安全密钥长度越长越安全轮数

多轮加密安全性高子密钥生成算法越复杂，分析难度越大轮函数

越复杂，抗攻击能力越强快速软件加解密易于分析114分组密码设计原理DES传统分组密码结构Feistel密码的参数DES概述DES是一种用56位密钥来加密64位数据的方法。115分组密码设计原理DES传统分组密码结构DES加密算法除了开始和最后的置换，与Feistel结构完全相同。右半部分是使用56为密钥的过程：移位和置换。116分组密码设计原理DES传统分组密码结构117DES算法框图输入64bit明文数据初始置换IP乘积变换（16轮迭代）逆初始置换IP-164bit密文数据输出标准数据加密算法DES的核心部件：两次置换（初始置换和初始逆置换）密钥控制下的十六轮迭代加密轮密钥生成118DES算法框图119初始置换和初始逆置换DES算法明文处理部分120初始置换和初始逆置换DES中的初始置换和初始逆置换121十六轮迭代加密十六轮迭代加密Roundi第i轮加密122DES第i轮迭代加密123F函数124扩展E置换（E-盒）32位分为8组，每组4位（上图一行为一组）第i组左右各扩展一位左扩展为等于第i-1组最后一位右扩展为等于第i+1组第一位125S盒（1）126S-盒是DES加密算法的唯一非线性部件S盒（2）127S盒（3）128

00010203040506070809101112131415012313020804061511011009031405001207011513081003070412050611001409020711040109121402000610131503050802011407041008131512090003050611输入输出S-盒的查表操作S盒（4）129注意：

DES中其它算法都是线性的，而S-盒运算则是非线性的提供了密码算法所必须的混乱作用S-盒不易于分析，它提供了更好的安全性S-盒的设计未公开S盒（5）130P置换131直接P置换（P-盒）P置换132F函数133DES第i轮迭代加密134135子密钥产生器

密钥（64bit）置换选择1，PC1置换选择2，PC2

Ci(28bit)

Di(28bit)循环左移循环左移除去第8,16,

,64位(8个校验位)ki136137置换选择1循环左移的次数（舍弃了奇偶校验位，即第8，16，…，64位）138压缩置换2舍弃了第9,18,22,25,35,38,43,54比特位139加密过程:L0R0

IP(<64bit明文>)Li

Ri-1

i=1,...,16(1)Ri

Li-1

f(Ri-1,

ki)i=1,...,16(2)<64bit密文>

IP-1(R16L16)

(1)(2)运算进行16次后就得到密文组。解密过程:R16L16

IP(<64bit密文>)Ri-1

Li

i=1,...,16(3)Li-1

Ri

f(Li-1,ki)i=1,...,16(4)<64bit明文>

IP-1(R0L0)(3)(4)运算进行16次后就得到明文组。DES加解密的数学表达分组密码设计原理DES传统分组密码结构140安全性DES的安全性完全依赖于所用的密钥。从DES诞生起，对它的安全性就有激烈的争论，一直延续到现在弱密钥和半弱密钥DES算法在每次迭代时都有一个子密钥供加密用。如果给定初始密钥k，各轮的子密钥都相同，即有k1=k2=…=k16，就称给定密钥k为弱密钥(Weakkey)DES的强度分组密码设计原理DES传统分组密码结构141若k为弱密钥，则有DESk(DESk(x))=xDESk-1(DESk-1(x))=x即以k对x加密两次或解密两次都可恢复出明文。其加密运算和解密运算没有区别。而对一般密钥只满足DESk-1(DESk(x))=DESk(DESk-1(x))=x弱密钥下使DES在选择明文攻击下的搜索量减半。如果随机地选择密钥，则在总数256个密钥中，弱密钥所占比例极小，而且稍加注意就不难避开。因此，弱密钥的存在不会危及DES的安全性。DES的强度分组密码设计原理DES传统分组密码结构142雪崩效应分组密码设计原理DES传统分组密码结构14356位密钥的使用256=7.2x10161997，几个月

1998，几天

1999，22个小时!DES算法的性质：S盒构造方法未公开！计时攻击DES的强度分组密码设计原理DES传统分组密码结构144差分密码分析通过分析明文对的差值对密文对的差值的影响来恢复某些密文比特线性密码分析通过寻找DES变换的线性近似来攻击DES的强度分组密码设计原理DES传统分组密码结构145迭代轮数迭代轮数越多，密码分析就越困难。选择标准：使密码分析的难度大于穷举攻击。函数F的设计Feistel密码的核心是函数F。混淆作用必须是非线性的严格雪崩效应为独立标准：对于任意及I,j,k，当输入第i位发生变换时，输出位j和k的变化彼此无关密钥扩展算法严格雪崩效应为独立标准DES传统分组密码结构分组密码设计原理146总结：作业:思考题3.1、3.2、3.4、3.5、3.6、3.7、3.8习题3.2、3.7、3.8,流密码第3章分组密码与数据加密标准分组密码乘积密码分组密码设计原理Feistel密码加密、解密算法分组长度密钥长度迭代轮数子密钥产生算法轮函数F加密、解密算法E盒、S盒、P盒子密钥产生算法雪崩效应DES强度计时攻击DES第4章数论和有限域的基本概念多项式运算与G(2n)群环域及G(p)147数论基本概念模运算欧几里得算法数论基本概念群环域及G(p)群、环、域有限域G(p)多项式运算与G(2n)多项式运算有限域G(2n)

148模运算多项式运算与G(2n)群环域及G(p)数论基本概念

149模运算多项式运算与G(2n)群环域及G(p)数论基本概念以模8运算为例150模运算多项式运算与G(2n)群环域及G(p)数论基本概念模运算的规律151模运算多项式运算与G(2n)群环域及G(p)数论基本概念交换律结合律分配律恒等式加法逆元正整数c称为a和b的最大公因子，如果c是a和b的因子，a和b的任何因子都是c的因子。记为c=gcd(a,b)；等价定义gcd(a,b)=max[k:

k|a

k|b]

定理：设a,b,r是三个不全为0的整数，如果a

=b×q+r，其中q为整数，则gcd(a,

b)=gcd(b,r)Euclidean算法：计算gcd(a,b)152模运算多项式运算与G(2n)群环域及G(p)数论基本概念

153欧几里得算法多项式运算与G(2n)群环域及G(p)数论基本概念gcd(a,b)=gcd(b,r1)gcd(b,r1)=gcd(r1,r2)gcd(r1,r2)=gcd(r2,r3)gcd(rn-2,rn-1)=gcd(rn-1,rn)gcd(rn-1,rn)=gcd(rn,0)=rn154求GCD(1970,1066)1970=1x1066+904 gcd(1066,904)1066=1x904+162 gcd(904,162)904=5x162+94 gcd(162,94)162=1x94+68 gcd(94,68)94=1x68+26 gcd(68,26)68=2x26+16 gcd(26,16)26=1x16+10 gcd(16,10)16=1x10+6 gcd(10,6)10=1x6+4 gcd(6,4)6=1x4+2 gcd(4,2)4=2x2+0 gcd(2,0)欧几里得算法多项式运算与G(2n)群环域及G(p)数论基本概念求GCD(5754,3014)155欧几里得算法多项式运算与G(2n)群环域及G(p)数论基本概念计算GCD(a,b)的欧几里得算法:EUCLID(a,b)1.A=a;B=b2.ifB=0returnA=gcd(a,b)3.R=AmodB4.A=B5.B=R6.goto2

156扩展的欧几里得算法多项式运算与G(2n)群环域及G(p)数论基本概念

157扩展的欧几里得算法多项式运算与G(2n)群环域及G(p)数论基本概念

158扩展的欧几里得算法多项式运算与G(2n)群环域及G(p)数论基本概念

[代数系统]一个非空集合A连同若干个定义在该集合上的运算f1,f2,…,fk所组成的系统就称为一个代数系统，记作<A,f1,f2,…,fk>。[运算封闭]设*是定义在集合A上的二元运算，如果对于任意的x,y∈A,都有x*y∈A,则称二元运算*在A上是封闭的。159多项式运算与G(2n)群环域及G(p)数论基本概念[运算可交换]

设*是定义在集合A上的二元运算，如果对于任意的x,y∈A都有x*y=y*x,则称该二元运算*是可交换的，或运算满足交换律。[运算可结合]

设*是定义在集合A上的二元运算，如果对于任意的x,y,z∈A都有(x*y)*z=x*(y*z),则称该二元运算*是可结合的，或运算满足结合律。160多项式运算与G(2n)群环域及G(p)数论基本概念[运算可分配]

设*，Δ是定义在集合A上的两个二元运算，如果对于任意的x,y,z∈A都有

x*(yΔz)=(x*y)Δ(x*z)(yΔz)*x=(y*x)Δ(z*x)则称运算*对于运算Δ是可分配的。[幺元]

对于任一x∈A,有e*x=x*e=x。[零元]

对于任一x∈A,有θ*x=x*θ=θ。[逆元]

对于x∈A,有y*x=x*y=e，x,y互为逆元。161多项式运算与G(2n)群环域及G(p)数论基本概念[群]

Group,定义了二元运算的集合，记为{G,*}，遵循:封闭性：a,b属于G，则a*b属于G结合律: (a*b)*c=a*(b*c)单位元e: e*a=a*e=a逆元a-1: a*a-1

=e有限群、无限群群的性质：无零元（只有一个等幂元）、满足消去律、a*x=b解唯一如果满足交换律 a*b=b*a则构成阿贝尔群(abeliangroup)162多项式运算与G(2n)群环域及G(p)数论基本概念定义求幂运算为重复运用群中的运算如: a3=a*a*a定义: e=a0称一个群为循环群，如果：群中每个元素都是一个固定元素a的幂，即

b=ak

（forsomeaandeverybingroup）a称为群的一个生成元（generator）163多项式运算与G(2n)群环域及G(p)数论基本概念当考虑两种运算时：加法+和乘法×加法的逆元又称为负元，a关于加法的逆元（负元）记为-ab+(-a)×(c+(-b))可简化为：b-a(c-b)自然而然第引入了减法（条件：每个元素的负元存在）164多项式运算与G(2n)群环域及G(p)数论基本概念[环]Ring，一个集合,记为{R,＋，X}，定义了两种运算(加法和乘法):对加法，构成阿贝尔群对乘法满足:封闭性结合律: a(bc)=(ab)c分配律: a(b+c)=ab+ac如果乘法满足交换律，则称交换环commutativering如果乘法有单位元、满足交换律且无零因子，则称整环integraldomain零因子：Z6中的2和3165多项式运算与G(2n)群环域及G(p)数论基本概念环的性质：（

为加法幺元）a·

=

·a=

（加法幺元必为乘法零元）a·(-b)=(-a)·b=-(a·b)(-a)·(-b)=a·ba·(b-c)=a·b-a·c(b-c)·a=b·a-c·a（减法分配率）无零因子等价于乘法满足消去律166多项式运算与G(2n)群环域及G(p)数论基本概念167[环举例]整数集、有理数集、实数集和复数集关于普通的加法和乘法构成环，分别称为整数环Z，有理数环Q，实数环R和复数环C.n(n≥2)阶实矩阵的集合Mn(R)关于矩阵的加法和乘法构成环，称为n阶实矩阵环.集合的幂集P(B)关于集合的对称差运算和交运算构成环.设Zn＝{0,1,...,n－1}，

和

分别表示模n的加法和乘法，则<Zn,

,

>构成环，称为模n的整数环.系数属于实数的所有x的多项式所组成的集合记作R[x]，那么，R[x]关于多项式的加法和乘法构成多项式环。多项式运算与G(2n)群环域及G(p)数论基本概念[域]Field，集合

，记为{F,＋，X}两种运算:对加法，构成阿贝尔群

对乘法，构成阿贝尔群（除0外）环域比环增加的条件：乘法满足交换律乘法幺元存在除零元外，乘法逆元都存在作加、减、乘和除法（除0外）运算，结果仍在集合中有限整环必是域168多项式运算与G(2n)群环域及G(p)数论基本概念169多项式运算与G(2n)群环域及G(p)数论基本概念

170多项式运算与G(2n)群环域及G(p)数论基本概念域的特征p：最小的正整数p，使得p×1=0,1为×的逆元，0为＋的逆元；如果p不存在，特征为0。Q、R、C特征为0；域的特征只能为0或素数特征暗示了加法的循环性定理：有限域的元素个数必是其特征的幂。对于

1∈F，考虑0，1，1，2

1，…(p-1)

1以上元素互不相同，可能F={0，1，1，2

1，…(p-1)

1}若不是，考虑其他元素

2∈F；考虑任意a1

1+a2

2，系数为0至p-1171多项式运算与G(2n)群环域及G(p)数论基本概念

172多项式运算与G(2n)群环域及G(p)数论基本概念

173多项式运算与G(2n)群环域及G(p)数论基本概念

174扩展的欧几里得算法

多项式运算与G(2n)群环域及G(p)数论基本概念

EXTENDEDEUCLID(a,b)1. (A1,A2,A3)=(1,0,a); (B1,B2,B3)=(0,1,b)2.ifB3=0 returnA3=gcd(a,b);noinverse3.ifB3=1 returnB3=gcd(a,b);B2=b–1moda4.Q=A3divB35.(T1,T2,T3)=(A1–Q

B1,A2–Q

B2,A3–Q

B3)6.(A1,A2,A3)=(B1,B2,B3)7.(B1,B2,B3)=(T1,T2,T3)8.goto

2175利用扩展的欧几里得算法求乘法逆元多项式运算与G(2n)群环域及G(p)数论基本概念176利用扩展的欧几里得算法求乘法逆元求GF(1759)中550的乘法逆元多项式运算与