第9章 密码学与信息安全,9.1 密码学的基本概念9.2 对称密码体制9.3 公钥密码体制思考题实验9 简单加解密算法的实现,内容导读密码学在信息安全领域作用巨大，其相关技术能够直接用来实现保密性、数据完整性、可认证性和不可否认服务。加密不仅可以保护存储中的数据，也可以用来保护通信。敌手对加密体制的攻击就是在不知道密钥的情况下想法找出密文对应的明文或密钥。密码体制可分为对称体制和公钥体制，公钥体制能很容易实现不可否认服务。典型的对称密码算法有RC4、DES和AES等，公钥密码算法有RSA、ElGamal和ECC等。,9.1 密码学的基本概念,经典的密码学主要研究加密和解密理论，随着密码学研究领域的扩展，要精确定义现代密码学的研究范围是非常困难的。目前人们一般认为密码学是研究基于困难问题存在性的技术和应用的科学，而一般教科书中讨论的密码学框架如图9-1所示。,图9-1 密码学框架示意图,自从人类有了战争，就有了加密通信，因而也就有了密码学。两千多年前，恺撒大帝在战争中使用了字母变换密码来传递信息，在第二次世界大战中，中国专家池步洲(19082003)成功破译日军密码，促使山本五十六被截杀。,1949年Shannon发表的论文“保密系统的通信原理”奠定了密码学的数学理论基础，1976年Diffie和Hellman的论文“密码学的新方向”奠定了公钥密码学的基础，1977年美国颁布了数据加密标准DES，2001年美国正式颁布AES为新的国家加密标准，近年来，量子密码和DNA密码的研究又把我们带入了一个新的密码时代。,现代密码学在信息安全中占有非常重要的地位，原因在于它能够直接实现保密性、数据完整性、可认证性和不可否认服务，如图9-1所示。,密码学中最基本的概念是加密与解密。假如Alice要把消息m通过不安全的信道保密地传给Bob，那么可按照图9-2方式进行。,图9-2 保密通信示意图,在图9-2中，Alice要发送的消息m叫明文，明文被变换E转化成的看似无意义的随机消息C称为密文，而这个变换E就叫加密。Bob通过变换D把C转化为m的过程称为解密。加密和解密都需要有Key的支持，这个Key称为密钥。如果加密方和解密方使用的是同样的密钥，相应的变换称为对称密钥加(解)密算法；否则称为非对称密钥加(解)密算法或公开密钥加(解)密算法。所谓破解，即是敌手在不知道密钥的情况下，把密文C还原成m或推导出解密密钥。,理想的安全密码算法应该能公开其算法流程，不管敌手采用何种攻击办法，只要不告诉其密钥，敌手就无法通过密文找出对应明文或密钥。也就是说，敌手针对安全密码算法的最好攻击方式就是暴力攻击(即搜索全部密钥空间)。表9-1是敌手攻击密码系统时可能拥有资源的情况。,表9-1 攻击类型与攻击者拥护的资源情况,理论上，只有一次一密(每个密码只使用一次)的密码系统才是不可破解的，没有绝对安全的密码算法。在实际应用中，如果一个密码算法用实际可得到的资源，在相对有限的时间内不能破解，则称该算法是计算上安全的。,9.2 对称密码体制,9.2.1 对称密码体制概述,在对称加密体制中，加密算法E和解密算法D使用相同的密钥k如图9-3所示。发送方Alice利用加密算法E和密钥k将明文m加密成密文c，即c = E(k, m)。接收方Bob利用解密算法D和密钥k将密文c解密成明文m，即m = D(k, c)。因此，在对称加密体制中，对于明文m，有,为了使用对称加密体制，通信双方应提前商定一个会话密钥和使用的具体算法，而后进行秘密通信。图9-3 对称密码体制,对称密码又分为流密码和分组密码两大类。流密码是按比特进行加密，分组密码是若干比特(定长)同时加密，其示意图分别如图9-4和图9-5所示。,图9-4 流密码示意图,图9-5 分组密码示意图,9.2.2 典型算法介绍1维基尼亚密码维基尼亚密码是古典密码的典型代表，这是一个多表替换密码，其基本原理如图9-6所示。图中明文是“MESSAGE FROM”，密钥是“WHITE”，对应的密码文是“ILALECL NKS.”。有关该算法的具体实现可参见本章实验部分的有关内容，请同学们写出加解密算法的具体数学表达式。,图9-6 维基尼亚密码示意图,古典密码在历史上发挥了巨大作用，香农曾把古典密码的编制思想概括为“混淆”和“扩散”，这种思想对于现代密码编制仍具有非常重要的指导意义。,2RC4RC4是美国麻省理工学院Ron Rivest于1987年设计的密钥长度可变的流密码算法。Microsoft Windows系统、安全套接层协议SSL和无线局域网通信协议WEP中均使用了该密码算法。有关RC4算法的详细内容见本章实验。其他流密码算法还有A5、Salsa20等。,3数据加密标准DES数据加密标准(Data Encryption Standard，DES)是最著名的分组加密算法之一。1977年的FIPS PUB 46中给出了DES的完整描述。,DES的明文分组长度n为64 bit，密钥为56 bit，加密后产生64 bit的密文分组。加密分为三个阶段，首先是一个初始置换IP，用于重排64 bit的明文分组；然后进行相同功能的16轮变换，第16轮变换的输出分左右两半，并被交换次序；最后经过一个逆置换，产生最终的64 bit密文。DES加密算法的框图如图9-7所示。,图9-7 DES加密算法框图,DES的16轮加密变换中每一轮变换的结构如图9-8所示。,图9-8 DES加密算法的轮结构,每一轮加密过程可用数学表达式表述为：Li=Ri-1，Ri=Li-1F(Ri-1, Ki)。图9-7和图9-8中用到的初始置换IP、逆初始置换IP-1、扩展运算表E和置换运算P分别见表9-2至表9-5，函数F(R，K)的计算过程如图9-9所示。,表9-2 初始置换IP,表9-3 逆初始置换IP-1,表9-4 轮结构中扩展置换E,表9-5 轮结构中置换运算,图9-9 函数F(R，K)的计算过程,在计算F(R，K)的过程中，要用到8个S盒。这8个S盒的具体定义见表9-6。,表9-6 DES的S盒,对每个盒Si，其6 bit输入中，第1个和第6个比特形成一个2位二进制数，用来选择Si的4个代换中的一个。6 bit输入中，中间4位用来选择列。行和列选定后，得到其交叉位置的十进制数，将这个数表示为4位二进制数即得这一S盒的输出。例如，S1的输入为011001，行选为01(即第1行)，列选为1100(即第12列)，行列交叉位置的数为9，其4位二进制表示为1001，所以S1的输出为1001。,DES16轮迭代中，每一轮子密钥Ki的长度都是48 bit。输入的56 bit密钥首先经过一个置换PC-1，然后将置换后的56 bit分为各为28 bit的左、右两半，分别记为C0和D0。在第i轮分别对Ci-1和Di-1进行左循环移位，所移位数由表给出。移位后的结果作为求下一轮子密钥的输入，同时也作为置换选择PC-2的输入。通过置换选择2产生的48 bit的Ki，即为本轮的子密钥，作为函数F(Ri-1，Ki)的输入。两个置换PC-1和PC-2分别见表9-7和9-8，每一轮左循环移位数见表9-9。,表9-7PC-1,表9-8PC-2,表9-9 左循环移位数,DES的解密和加密使用同一算法，但子密钥使用的顺序相反。DES已走到了它生命的尽头，其56 bit密钥实在太小。2000年10月，美国国家标准技术研究所(NIST)选择Rijndael密码作为高级加密标准AES。Rijndael密码是一种迭代型分,组密码，由比利时密码学家Joan Daemon和Vincent Rijmen设计，使用了有限域GF(28)上的算术运算。数据分组长度和密钥长度都可变，并可独立指定为128 bit、192 bit或256 bit比特，随着分组长度不同迭代次数也不同。Rijndael密码可在很多处理器和专用硬件上高效地实现。,对称密码具有加密速度快、密钥短、易于硬件或其他机械装置实现等优点，但这种算法初始化比较困难，系统需要的密钥量也很大。表9-10给出了一些历史上著名的分组密码算法，著名的电子邮件安全软件PGP(Pretty Good Privacy)就采用了IDEA算法进行数据加密。,表9-10 一些著名的分组密码算法,9.3 公钥密码体制,9.3.1 公钥密码体制概述,在公钥密码体制中，每一个用户都拥有一对个人密钥k=(pk, sk)，其中pk是公开的，任何用户都可以知道，sk是保密的，只有拥有者本人知道。假如Alice要把消息m保密地发送给Bob，则Alice利用Bob的公钥pk加密明文m，得到密文c:=E(pk, m)，并把密文传送给Bob。Bob得到Alice传过来的c后，利用自己的私钥sk解密密文c得到明文m=D(sk, c)，如图9-10所示。,图9-10 公钥密码工作原理图,公钥密码体制与对称密码体制的主要区别是前者的加密密钥和解密密钥是不同的。这个不同导致了： 在公钥密码系统中，密钥维护总量大大减少； 在公钥密码系统中可以很容易实现抗否认性。,在公钥体制中，用户的公钥pk和私钥sk是紧密关联的，否则加密后的数据是不可能解密的。但在安全的体制中，这种关联也是敌手无法利用的，即想通过公钥获取私钥或部分私钥在计算上是不可行的。公钥和私钥的关联性设计一般是建立在诸如大整数分解、离散对数求解、椭圆曲线上的离散对数求解等困难问题上的，假如敌手能通过公钥想办法获取私钥信息，则敌手应该能解决数千年没解决的数学难题。,9.3.2 RSA公钥密码体制RSA密码体制是世界上应用最为广泛的公钥密码体制。RSA体制的安全性基于大整数分解的困难性，即已知两个大素数p和q，求n=pq是容易的，而由n求p和q则是困难的。,RSA算法包括密钥生成算法和加解密算法两部分。密钥生成算法如下：(1) 选择不同的大素数p和q，计算，。(2) 选择e，满足1e，且，(n,e)作为公钥。(3) 通过计算d，且，(n,d)作为私钥。,RSA加解密算法如下：RSA加密：RSA解密：加密时首先对明文比特串分组，使得每个分组对应的十进制数小于n，即分组长度小于。,基于安全考虑，目前RSA密码体制使用的大素数至少要在512 bit以上。由于要进行大数的计算，RSA运算速度较慢，其软件实现大概要比DES慢100倍。读者可以对有关RSA算法的安全性作进一步分析，也可参阅其他文献。,除了RSA以外，著名的公钥密码算法还有Rabin算法(1979)、ElGamal算法(1985)、椭圆曲线算法ECC(1985)、基于格的NTRU算法(1996)和基于6次扩域上的离散对数XTR算法(2000)等。,思 考 题,(1) 密码学主要包含哪些内容，密码技术能提供哪些安全服务?(2) 古典密码体制的主要思想是什么，如何理解密码算法的安全性？ (3) 简述DES加解密算法流程。,(4) 对称密码体制和公钥密码体制的主要区别是什么？(5) 简述公钥密码算法的基本原理。(6) 简述RSA算法及其安全性。,实验9 简单加解密算法的实现,一、实验目的(1) 掌握对称加密算法的基本思想。(2) 深入理解Vigenere 算法和RC4算法的算法流程。(3) 了解DES、AES等算法的加解密过程。,二、实验准备(1) 查阅有关资料，熟悉古典加密算法中单表代换与多表代换算法，掌握Vigenere算法。(2) 查阅有关资料，熟悉流密码的基本思想，掌握RC4算法。(3) 查阅有关资料，熟悉DES和AES加解密程。,三、实验内容(1) 分析、调试运行下面代码，并写出代码的算法流程图。#include#includevoid main(),