信息论与编码技术教学课件7密码学基础

1、第七章 密码学基础,参考资料： 信息安全技术,数据加密是计算机安全领域中的最重要的技术之一。 口令加密是防止文件中的密码被人偷看。 文件加密主要应用于因特网上的文件传输，防止文件被看到或劫持。 电子邮件是不安全的。通过引入数字签名等加密技术，可以保证邮件的保密性和真实性。 数据加密也使因特网上的电子商务成为可能。,本章主要内容,密码学概述 传统密码学(字符加密) 现代计算机密码学：对称密码体制 现代计算机密码学：非对称密码体制 密钥的管理 消息认证 散列函数 数字签名 数字证书与公开密钥基础设施PKI,7.1 密码学概述,密码学是一门古老而又年轻的科学。 密码的历史十分悠久，早在公元前4000多年，人们就开始使用各种原始的消息加密方法。例如，四千年前古埃及就开始使用密码传递消息、中国古代利用烽火台传递情报等，基本上依靠人工对消息加密、传输和防破译。 第一次、第二次世界大战促进了密码学的飞速发展。,密码学的发展阶段,密码学的发展可以分为两个阶段。 1.传统密码学阶段： 2.现代计算机密码学阶段，包括两个方向： 基于传统方法的计算机密码体制对称密码体制。对称：解密是加密的逆过程，两者所用的

2、密钥是可以简单地互相推导的，因此无论加密密钥还是解密密钥都必须严格保密。 对称的、公开/私有密钥密码体制。,现代密码学涉及数学、物理学、信息论和计算机科学等多个学科。 两篇论文构成了现代密码学的理论基础和基本内容：香农信息论；非对称密码体制。,基本概念,明文：受保护的原始的可读消息。 密文：加密后无法直接读取的信息。 加密：对明文进行处理、转换为密文的过程。 解密：将密文恢复为原来的明文的过程，是加密的逆过程。,密码体制：一个加密系统采用的基本工作方式。 密码体制的基本要素：密码算法和密钥。 其中，密码算法是一些数学公式和函数、数据处理的规则； 密钥是密码算法中的可变参数(或特殊的处理过程)。,密码算法分为：加密算法(加密函数)和解密算法(解密函数)； 相应地，密钥也分为：加密密钥和解密密钥。 所谓的密码的含义不是很确切，有时是指密文，有时也指算法，有时是指密钥，有时是指密码体制。,加密函数E作用于明文 M得到密文C，可用数学公式表示：E(M)=C。 相反地，解密函数D作用于C产生M：D(C)=M。 当加密过程可逆时，先加密后再解密，原始的明文将恢复，故下面的等式必须成立：D(E(M)

3、=M。,密钥用 K表示。K可以是很多数值里的任意值。 密钥 K的可能取值的范围叫做密钥空间。加密和解密运算都使用这个密钥(即运算都依赖于密钥，并用 K作为下标表示)。显然，密钥空间越大，密钥越不容易被猜测出来。 加/解密函数现在变成：EK(M)=C和DK(C)=M。这些函数具有的特性：DK(EK(M)=M 当然，加密密钥与解密密钥可以相同(对称)、也可以不相同(非对称)。,现代密码学的一个基本原则：算法可以公开，安全性蕴含在密钥中。 即：在设计加密系统时，加密算法通常是公开的，而真正需要保密的是密钥，密钥是保密的。 密码算法的基本特点是：在已知密钥条件的下，计算(解密)应该是简洁有效的；在不知道密钥的条件下，从密文计算出明文(解密)实际上是不可能的。,密码体制的五元组(明文P空间，密文C空间，密钥K空间，加密算法E，解密算法D)。 密码体制的评价：保密强度、密钥长度和更换频率、算法复杂性、差错的传播性、加密消息的冗余程度。 密码体制安全性的评价：无条件安全性、计算安全性、可证明安全性。 数据加密的实现层次：端到端、链路加密。,密码学的研究内容,古典密码学包括密码编码学和密码分析学。 密

4、码编码学的主要内容是：密码体制的设计； 密码分析学的主要内容是：密码体制的破译； 密码编码技术和密码分析技术是相互依存、相互支持、密不可分的两个方面。 除了信息加密、解密问题之外，现代密码学还包括更多内容，例如消息认证(包含身份认证、完整性认证)。,密码分析,密码分析学是在不知道密钥的情况下，恢复出明文的科学。成功的密码分析能恢复出消息的明文或密钥。密码分析也可以发现密码体制的弱点，最终得到上述结果。 对密码进行分析的尝试通常称为攻击。 一般假定攻击者知道算法。通常，试图对密钥的所有可能取值(密钥空间一般很大)进行穷举式的尝试是不太可能。所以，攻击者往往通过对窃取的密文进行分析。 常用的密文分析攻击包括几种类型。,7.2 传统密码学,数据的表示有多种形式，使用最多的是文字，还有图形、声音、图像等。在计算机系统中，各种信息都是以某种编码的方式来存储的。 传统加密方法的主要应用对象是对文字消息进行加密解密。 文字就是一个一个的字符。 以下的加密方法通常都是以英文字符为例。,7.2.1 置换法,又称换位法。 基本思想：不改变明文字符本身，仅仅改变明文字符在原始消息中的位置。,(1)铁轨法(R

5、ailroad Method) 铁轨法是置换法最基本的形式。首先，它要求明文的长度必须是4的倍数，不符合要求则在明文最后加上一些字符以符合加密的条件。 例如，明文“STRIKE WHILE THE IRON IS HOT”就不满足条件(空白不计)，故在尾端加上字符“”使明文的长度变成4的倍数，接着将明文以从上到下的顺序逐列(此例约定为2行)写出，表示如下： S R K W I E H I O I H T T I E H L T E R N S O E,然后，依序由左而右、再由上而下地写出字符的序列，即为密文，表示如下： SRKWIEHIOIHTTITIEHLTERNSOE 为方便起见,将密文每4个字符一数，其间用空格隔开： SRKW IEHI OIHT TIRH LYRT NSOE 这就是为什么要使密文长度为4的倍数的原因了。,接收方收到此密文后，因为知道加密的顺序，因此，接收方可将密文以一直线从中分为两个部分，如下所示： SRKW IEHI OIHT TIRH LYRT NSOE 解密时再按照相应方法读出即可。,(2)路游法,路游法是铁轨法的一种推广。同样，此法也必须将明文的长度调整

6、为4的倍数。之后将调整过的明文依由左而右、由上而下的顺序(此顺序称之为排列顺序)填入方格矩阵中。依前例，可以得到如下矩阵。,图7.2 游走路径,然后，依照事先规定的路径(称为游走路径)来游走矩阵并输出所经过的字符，此即为密文。 如果以如图7.2所示的游走路径来走，则可以得到如下的密文： ETNETOEKILROHIIRTHESIHWS,(3)密钥法,密钥法最大的好处是就是将加密者和解密者双方所持有的加、解密密钥具体化。 密钥法大致来说与路游法相似，首先也是将明文填入一个矩阵(见路游法中的矩阵)，接着，任意挑选一个密钥，如以“PREDIC”这个英文单字为加、解密双方所协议的共同密钥，然后，将密钥写于矩阵上方，如下所示。,接着依照加密密钥字符的字母表顺序，分别依序读出其相对应的列便可得到密文，即根据PREDIC，先读出字符C对应的列，再依次读出字符DEIPR对应的列，得到密文如下： E T N E I L R O R I I HKE O TSWH I H T ES,7.2.2 替换法,替换法的基本思想：明文中每一个字符在密文中的对应位置不变，但是每个明文字符按照某种约定(另一个密钥字母表)

7、替换为密文中的另外一个字符。接收者对密文进行逆替换就恢复出明文来。 密钥字母表可以与明文字母表相同(如26个字符构成的字母表)，也可以由多个字母表组合构成。 如果是由一个字母表构成的替代密码，称为单表密码，其替代过程是在明文和密码字符之间进行一对一的映射。如果是由多个字母表构成的替代密码，称为多表密码。,图2.3 密码转盘图 图2.4 旋转后的密码转盘,(1)旋转替换法,假设有一个由两个同心圆所组成的密码转盘，如图2.3所示。通过旋转其中一个园，就能得到与一个明文字符相对应的密文字符。,等价的处理办法：引入数学处理的手段。 一条消息是由若干个字符构成的。为了便于数学处理，针对英文字母表中每个字符，根据所在字母表中的位置指定一个数字 (如A=1，B=2，) 。并且把字母表看成是循环的(比如字母Z的下一个字符是A ) 。 旋转替换加密方法就是把明文中所有字符都用它右边的第k个字符替代。这种映射关系表示为如下函数： F(明文字符) (明文字符+k) mod 26 其中：n为字符集中字符个数26；k为密钥。,例如，设k3，明文PCOMPUTE SYSTEMS，则 f(C)=(3+3) mod

8、26=6=F f(O)=(15+3)mod 26=18=R f(M)=(13+3)mod 26=16=P f(S)=(19+3) mod 26=22=V 所以，密文C= Ek(P)=FRPSXRWH UVBVWHPV。,这种方法有时称为恺撒密码。 凯撤密码的优点是密码简单易记。缺点是密文与明文的对应关系过于简单。故安全性很差。,除了凯撒密码，在其他的单表替代法中，有的字母表被打乱。 比如，在字母表中首先排列出密钥中出现的字符，然后在密钥后面填上剩余的字符。如密钥是HOW，那么新的字母表和原始字母表分别是： HOWABCDEFGIJKLMNPQRSTUVXYZ ABCDEFGHIJKLMNOPQRSTUVWXYZ 这个密钥很短，多数明文字符离开其密文等价字符，仅有一个或几个位置。若用长的密钥字，则距离变大，因而便难于判断是何文字密钥。,使用这种算法进行加密或解密可以看成是直接查类似上面的表来实现的。变换一个字符只需要一个固定的时间，这样加密M个字符的时间与M成正比。 短字、有重复模式的字词，以及常用的起始和结束字符都给出猜测字母表排列的线索。英语字符的使用频率可以明显地在密文中体现出来，

9、这是单表密码代替法的主要缺点。 多表替代密码通过给每个明文字符定义密文元素消除了这种分布。,(2)维吉利亚替换法,首先，加解密双方必须同时握有如表7.1所示的表格，另外还必须商议出一把共同密钥，这里必须强调的是表7.1并非密钥的一部分，也就是说，即使表7.1被公开，也不会影响系统的安全性。假设通信双方均已握有表7.1，且已互相约定好一把秘密密钥“CRYPTOGRAPHY”，接着便可将明文“STRIKE WHILE THE IRON IS HOT”加密了。,首先，将密钥重复地写在明文的上方。 CR YP TO GR AP HY CR YP TO GR AP H ST RI KE WH IL ET HE IR ON IS HO T 然后以上下两个字符为指针去查表7.1，例如第一个字符对为(C,S)，此即表示在表7.1中查找行为C且列为S为元素，即为，此字符就是相对于明文S的密文，其他的明文字符转换成密文可依次类推，从而得到以下密文： UKPXDSCYIAIRJVGGHBOTHDA,7.2.3 一次性密钥的密码,一次密码本是一个很大的、不重复的密钥(字符串)集，这个密钥字符集被写在不同的多张纸上，并被粘成一个密码本。它最初的形式是用于电传打字机。 每次发送者用密码本中的一个密钥字符串加密明文字符。加密是明文字符和一次密码本密钥字符的模26加法。 每个密钥对一个消息仅使用一次。发送者对所发送的消息加密，然后销毁密码本中用过的一页或磁带部分。接收者有一个相同的密码本，并依次使用密码本上的每个密钥去解密密文的每个字符。接收者在解密消息后销毁密码本中用过的一页或磁带部分。新的消息则用密码本中新的密钥加密。,一次性密码方法并不是指密文绝对无法破译成明文，而是指：由特定密文获得原始明文的可能性有无穷多种，因此实际上是无法破译的。 因为每次密钥只使用一次，破译者没有其他用相同密钥加密的明文、密文做参照，所以永远无法判断真实的明文。,7.2.4 简单异或,针对二进制信息，最简单的加密方法就是引入异或运算。 异或(XOR)运算可以用或者“”表示，是针对二进制信息位进行的标准操作，如 00=0 01=1 10=1 11=0,

《信息论与编码技术教学课件7密码学基础》由会员E****分享，可在线阅读，更多相关《信息论与编码技术教学课件7密码学基础》请在金锄头文库上搜索。