密码学基础教学大纲完整版.doc

1 密码学基础密码学基础课程教学大纲课程教学大纲 （课程代码：（课程代码：0731062007310620） 课程简介课程简介 密码学基础是信息安全专业的一门技术基础课程，该课程的学习将为后续 的信息安全课程打下基础，同时也为将来从事信息安全研究和安全系统的设计 提供必要的基础。该课程主要讲授流密码（古典密码学）分组密码学、公钥密 码学、密钥分配与管理、信息认证和杂凑算法、数字签名以及网络加密与认证 等几个部分，在其中将学习各种加解密、散列函数、单向函数、签名模式及伪 随机发生器等多种密码学工具，以及如何应用这些工具设计一个实现基本信息 安全目标的系统（目前学时不够，没有安排） 。基本密码学工具的掌握和应用这 些工具构造安全服务就是本课程的基本目标。 本课程具有如下特点： （一）依赖很强的数学基础 本课程需要数论、近世代数、概率论、信息论、计算复杂性等数学知识作 为学习的基础。这些数学基础的讲解既要体现本身的体系性，同时还要兼顾密 码学背景。 （二）可扩展性强 各种具体方法的学习不是本课程的最终目标，背后的基本原理以及应用这 些原理设计新工具的能力才是本课程的最终目标。 （三）课程内容复杂且涉及面广 由于密码学内容丰富，且包含许多复杂的知识点，所以本课程的讲授以线 为主，即在基本主线的勾勒基础上对授课内容及复杂程度做出取舍。 本课程先修课程有：数据结构、近世代数、概率论、高等数学、高级语言 程序设计等。后续课程有信息安全扫描技术、PKI 技术、病毒学等专业课程。 课程教材选用国内信息安全优秀教材杨波编著的现代密码学（清华大 学出版社），同时参考国外优秀教材： 经典密码学与现代密码学,Richard Spillman，清华大学出版社、Douglas R. Stinson 著，冯登国译的密码学原 理和实践 ，电子工业出版社,2003 年 2 月第二版。另外还向学生推荐国内的一 些具有特色的操作系统教材如胡向东编写的应用密码学教程（电子工业出 版社）等。 实验教材选用自编的实验指导书，同时参考上海交大的“信息安全综合实 验系统实验指导书” ，除了这些教材之外，学校的图书馆为师生提供了相关的学 术期刊和图书。 课程教学体系：理论课程（34 学时）课程实验（16 学时）。达到从算法 验证、综合设计、到创新应用知识的逐步提高、全面培养的目的。相应的教 学材料由教学大纲、实验大纲、实验指导书等。实践环节的实验条件有：计 算机科学技术系的实验中心（实施课程实验）。 课程教学安排课程教学安排 序号内容课时数备注 一密码学概述 2 二古典密码学算法（一） 2 2 三古典密码学算法（二） 2 课后习题 四 分组密码体制：数论基础 2 五中国剩余定理 2 六Feistel 网络结构 2 七DES 加密算法 2 课后习题 八置换和代换 2 九公钥密码体制的基本原理 2 十RSA 算法 2 十一背包密码体制 2 课后习题 十二DES 算法实验 2 实验课 十三3 DES 算法实验 2 实验课 十四单钥、公钥加密体制的密钥分配 2 十五密钥托管与消息认证码 2 十六杂凑函数 2 课后习题 十七RSA 算法实验 4 实验课 十八数字签字原理 2 十九密码认证协议 2 二十网络通信加密与 PGP 2 二十一AES 算法实验 4 实验课 二十二MD5 算法实验 4 实验课 第一部分：理论课大纲第一部分：理论课大纲 【教学目的及要求】 密码学基础是计算机信息安全中的核心课程，所以改专业的学生均需学习 并掌握密码学的相关技术理论和工具方法，这是深入理解和从事有关信息安全 行业工作的基础。因此密码学基础在信息安全专业课程中占有不可替代的地位。 本课程的先修课程有数据结构 、 概率论 、 高等数学 、 高级语言程 序设计等，学生应掌握程序设计、数据结构、编译原理和计算机组成等方面 的基础知识，具有一定的独立编程能力。通过本课程学习培养学生动手能力， 对密码学的原理、思想和算法都有清晰、深入的理解。让学生通过多个密码算 法的程序设计实现，更好地掌握密码算法设计的机理和方法。同时，基于密码 系统设计的基本方法和基本步骤，帮助学生理解密码学在信息安全中的地位， 并引导了解密码学领域及信息安全领域的新进展、新方向。掌握本课程后，可 以为后期信息安全扫描技术 、 PKI 技术 、 病毒学等课程的学习，以及 网络安全的分析、设计与开发奠定坚实的专业基础。 通过本课程的学习各种加解密、散列函数、单向函数、签名模式及伪随机 发生器等多种密码学工具，培养学生的实际动手能力和提高分析问题解决问题 的能力，为学生今后从事各种实际工作，如设计、分析和改进各种加解密数据 包提供必要的软件基础，以便能得心应手地用好和管好计算机，更好地完成各 种计算机安全保密任务以及如何应用这些工具设计一个实现基本信息安全目标 的系统（目前学时不够，没有安排） 。基本密码学工具的掌握和应用这些工具构 3 造安全服务就是本课程的基本目标。 【重点和难点】 本课程的重点是：密码学中的数论知识，密码学中常见的代数结构，熵理 论概要，加解密都是明密文集合上的数学变换：代换和置换、SPN(代换-置换网)。 两种常见的 DES 分析方法：线性分析和差分分析手段。三种常见的信息认证方 法：加密，消息认证码(MAC)和散列函数，常见的密码学协议，包括密钥分发、 密钥协商、认证等内容。 难点有：移位加密、代换密码、维吉尼亚密码、希尔密码等古典加密算法 与古典置换密码：行置换加密、块置换加密等。数据加密标准(DES)、S-盒设计 方法、高级加密标准(AES)、 RSA 公钥密码算法、ElGamal 公钥密码算法、椭圆 曲线加密算法(ECC)、背包加密算法、MD5 散列算法等。 【教学方法】 在密码学基础教学中采用面授和多媒体教学手段相结合的方式进行。 面授教学是教学相长、教学互动的最好的模式。采用这种教学相长的启发式教 学方法，课堂上组织讨论，使课堂气氛活跃，学生的学习兴趣、能动性大大提 高。实际教学中使用多媒体教学手段在教育多功能教室上课，进行实时的、多 媒体、交互式的教学，以动画生动表现动态过程，以拟人手段讲解难点，提高 学生学习兴趣。 密码学基础实验环境(软件)为上海交大的“信息安全综合实验系统平台” 。 学生利用这个实验环境通过实践进一步掌握密码学领域的基本原理、基本思想 及基本算法原理。使学生对密码系统设计和分析的基本方法和步骤形成一个清 晰、全面的认识。 【课时安排】课时安排（共 50 学时） 【主要参考书】 课程教材选用国内信息安全优秀教材杨波编著的现代密码学（清华大 学出版社），同时参考国外优秀教材： 经典密码学与现代密码学,Richard Spillman，清华大学出版社、Douglas R. Stinson 著，冯登国译的密码学原 理和实践 ，电子工业出版社,2003 年 2 月第二版。另外还向学生推荐国内的一 些具有特色的操作系统教材如胡向东编写的应用密码学教程（电子工业出 版社）等。 实验教材选用自编的实验指导书，同时参考上海交大的“信息安全综合实 验系统实验指导书” ，除了这些教材之外，学校的图书馆为师生提供了相关的学 术期刊和图书。 序号 教 学 内 容讲授学时 试验学时 （一） 第一章 引言 2 （二） 第二章 流密码 4 （三） 第三章 分组密码体制 86 （四） 第四章 公钥密码 88 （五） 第五章 密钥分配与密钥管理 32 （六） 第六章 消息认证与杂凑算法 3 （七） 第七章 数字签字和密码协议 4 （八） 第八章 网络加密与认证 2 4 一、密码学概述 【教学目的及要求】 课前言； 了解信息安全面临的威胁；了解信息安全的模型；了解密码学的基本概念 【重点和难点】 重点：密码学基本概念、术语 【教学方法】多媒体教学 【课时安排】2 学时 【主要参考书】 经典密码学与现代密码学 、 应用密码学教程、密码学原理和实践 【课程主要内容】 课前言： 本章是引言，包括：信息安全面临的威胁 信息安全的模型 密码学基本概念 （一）密码学简介 1.信息安全的模型 信息安全的基本模型。 安全传输技术有以下两个基本成分： （1）消息的安全传输，包括对消息的加密和认证。加密的目的是将消息搞 乱让对手无法读懂，认证的目的是检查发送者的身份。 （2）通信双方共享的某些秘密信息，如加密密钥。 第三方的作用是负责向通信双方发布秘密信息或者在通信双方有争议时进 行仲裁。 安全的网络通信必须考虑的 4 个方面。 （二）若干基本概念 2.密码学基本概念 密码学主要是研究通信安全保密的学科，包括两个分支：密码编码学和密 码分析学。 密码编码学主要研究对信息进行变换，以保护信息在信道的传递过程中不 被他人窃取、解密和利用的方法。 密码分析学主要研究如何分析和破译密码 密码系统的组成： 密码系统由明文空间、密文空间、密码方案和密钥空间组成。 明文空间：待加密的信息称为明文，明文的全体称为明文空间。明文用 M（Message）或 P（Plain Text）表示。 密文空间：经过伪装后的明文，全体可能出现的密文的集合成为密文空间。 用 C（Cipher）表示。 密码方案：密码方案确切地描述了加密变换和解密变换的具体规则。包括 对明文进行加密时所使用的一组规则（加密算法）的描述，以及对密文进行还 原时所使用的一组规则（解密算法）的描述。 5 密钥空间：加密和解密算法的操作通常在称为密钥的元素（加密密钥和解 密密钥）的控制下进行。密钥的全体称为密钥空间。用 K 表示 从数学角度来讲，一个密码系统是一族映射，它在密钥的控制下将明文空 间中的每一个元素映射到密文空间上的某个元素。这族映射由密码方案确定， 具体使用哪一个映射由密钥决定。 二、古典密码学算法（） 【教学目的及要求】 要求学生了解并掌握：流密码的基本概念；掌握线性反馈移位寄存器；了解非 线性序列 【重点和难点】 重点：线性反馈移位寄存器 难点：线性反馈移位寄存器。 【教学方法】多媒体教学 【课时安排】2 学时 【主要参考书】 经典密码学与现代密码学 、 应用密码学教程、密码学原理和实践 【课程主要内容】 本节是流密码，包括：流密码的基本概念 线性反馈移位寄存器 非线性序列 （一）线性反馈移位寄存器 移位寄存器是流密码产生密钥流的一个主要组成部分。GF(2)上一个 n 级反 馈移位寄存器由 n 个二元存储器与一个反馈函数 f(a1,a2,an)组成，如图 2.8 所 示。 图 2.8 GF(2)上的 n 级反馈移位寄存器 每一存储器称为移位寄存器的一级，在任一时刻，这些级的内容构成该反 馈移位寄存器的状态，每一状态对应于 GF(2)上的一个 n 维向量，共有 2n 种可 能的状态。每一时刻的状态可用 n 长序列 a1,a2,an 或 n 维向量 (a1,a2,an) 表示，其中 ai 是第 i 级存储器的内容。 初始状态由用户确定，当第 i 个移位时钟脉冲到来时，每一级存储器 ai 都 将其内容向下一级 ai-1 传递，并根据寄存器此时的状态 a1,a2,an 计算 f(a1,a2,an)，作为下一时刻的 an。反馈函数 f(a1,a2,an)是 n 元布尔函数，即 n 个变元 a1,a2,an 可以独立地取 0 和 1 这两个可能的值，函数中的运算有逻 辑与、逻辑或、逻辑补等运算，最后的函数值也为 0 或 1。 如果移位寄存器的反馈函数 f(a1,a2,an)是 a1，a2，an 的线性函数， 则称之为线性反馈移位寄存器 LFSR（linear feedback shift register） 。此时 f 可写 为 f(a1,a2,an)=cna1cn-1a2c1an 三、古典密码学算法（） 6 【教学目的及要求】 要求学生了解并掌握 ：几种典型的古典密码体制；古典密码的统计分析 【重点和难点】 重点：几种典型的古典密码体制 难点：Playfair 体制 【教学方法】多媒体教学 【课时安排】2 学时 【主要参考书】 经典密码学与现代密码学 、 应用密码学教程、密码学原理和实践 【课程主要内容】 本节是古典密码学，包括：几种典型的古典密码体制 古典密码的统计分析 （一）古典密码学的基本算法 加解密都是明密文集合上的数学变换，古典密码学立足于两类基本操作： 代换和置换。基于这两类操作，产生了相应的古典代换密码：移位加密、代换 密码、仿射密码、维吉尼亚密码、希尔密码等古典加密算法等；和古典置换密 码：行置换加密、块置换加密等。密码编码学和密码分析学是相辅相成的，所 以需对古典密码学进行一定的密码分析。 基于语言中字符概率的密码分析以及各种古典加密算法对该种分析的抵抗 性。 四、分组密码体制：数论基础 【教学目的及要求】 要求学生了解并掌握与课程相关的数学知识。 【重点和难点】 重点：模运算、欧拉定理、中国剩余定理。 难点：乘法逆元。 【教学方法】多媒体教学 【课时安排】2 学时 【主要参考书】 经典密码学与现代密码学 、 应用密码学教程、密码学原理和实践 【课程主要内容】 本节是数论简介，包括：模运算 费尔玛定理和欧拉定理 中国剩余定理 （一）数论简介 密码学中的数论知识，密码学中常见的代数结构，完善保密性，熵理论概 要。 需要让学生认识到基本密码学工具（如加解密算法）都是集合上的数学变换， 而一般都是在某种代数结构上建立若干代数运算。数论是密码学特别是公钥密 码学的基本工具，本章主要介绍密码学中常用的一些数论知识。 1.素数和互素数 因子：设 a，b(b0)是两个整数，如果存在另一整数 m，使得 a=mb，则称 7 b 整除 a，记为 b|a，且称 b 是 a 的因子。 整数具有以下性质： a|1，那么 a=1。 a|b 且 b|a，则 a=b。 对任一 b (b0)，b|0。 b|g，b|h，则对任意整数 m、n 有 b|(mg+nh)。 素数 称整数 p(p1)是素数，如果 p 的因子只有1，p。 互素数 最大公因子定义：称 c 是两个整数 a、b 的最大公因子，如果 c 是 a 的因子也是 b 的因子，即 c 是 a、b 的公因子。 a 和 b 的任一公因子，也是 c 的因子。 互素：如果 gcd(a,b)=1，则称 a 和 b 互素。 2.同余的定义及表示 。 如果(a mod n)=(b mod n)，则称两整数 a 和 b 模 n 同余，记为 ab mod n。 称与 a 模 n 同余的数的全体为 a 的同余类，记为a，称 a 为这个同余类的表示 元素。 注意： 如果 a0(mod n)，则 n|a。 （二）费尔玛定理和欧拉定理 1.费尔玛定理 定理 4.2 (Fermat)若 p 是素数，a 是正整数且 gcd(a, p)=1，则 ap-11 mod p。 2.欧拉函数 设 n 是一正整数，小于 n 且与 n 互素的正整数的个数称为 n 的欧拉函数，记为 (n)。 例如： (6)=2 ，(7)=6 ，(8)=4。 定理 4.3 若 n 是两个素数 p 和 q 的乘积，则 (n)=(p)(q)=(p-1)(q-1)。 3.欧拉定理 若 a 和 n 互素，则 a(n)1 mod n。 欧几里得算法 欧几里得（Euclid）算法是数论中的一个基本技术，是求两个正整数的最 大公因子的简化过程。而推广的 Euclid 算法不仅可求两个正整数的最大公因子， 而且当两个正整数互素时，还可求出其中一个数关于另一个数的乘法逆元。 五、中国剩余定理 8 【教学目的及要求】 要求学生了解并掌握与课程相关的定理知识。 【重点和难点】 重点：中国剩余定理。 【教学方法】多媒体教学 【课时安排】2 学时 【主要参考书】 经典密码学与现代密码学 、 应用密码学教程、密码学原理和实践 【课程主要内容】 中国剩余定理是数论中最有用的一个工具，定理说如果已知某个数关于一 些两两互素的数的同余类集，就可重构这个数。 定理 4.5（中国剩余定理） 设 m1,m2,mk 是两两互素的正整数，则一次同余 方程组对模 M 有惟一解: 中国剩余定理提供了一个非常有用的特性，即在模 M 下可将非常大的数 x 由一组小数(a1,a2,ak)表达。 例 4.5 将 973 mod 1813 由模数分别为 37 和 49 的两个数表示。 解： 取 x=973, M=1813, m1=37,m2=49。 由 a1973 mod m111,a2973 mod m342 得 x 在模 37 和模 49 下的表达为 （11,42） 。 六、Feistel 网络结构 【教学目的及要求】 需要掌握数据加密标准与掌握分组密码的运行模式 【重点和难点】 重点：Feistel 网络结构。 【教学方法】多媒体教学 【课时安排】2 学时 【主要参考书】 经典密码学与现代密码学 、 应用密码学教程、密码学原理和实践 【课程主要内容】 本章是分组密码体制包括：Feistel 网络结构 数据加密标准 DES 分组密码的运行模式 （一）Feistel 网络结构 基于 Shannon 的理论，可通过乘积密码原理来提高密码变换的复杂性和抗 分析性；如果选取置换和代换作为乘积密码的基本单元，就必须采用分组密码。 将二者结合起来，就形成了分组密码学的基本结构：SPN(代换-置换网)。基于 这一核心，Horst Feistel 提出了一个目前分组密码学中最常见的结构，在这一结 构基础上，产生了数据加密标准(DES)。有两种常见的 DES 分析方法：线性分 析和差分分析。两种分析方法都是应用 DES 中 S-盒设计上的某些不均衡性造成 的，所以有必要提出新的 S-盒设计方法。由于 DES 存在安全性问题，产生了高 级加密标准(AES)。 线性密码分析和差分密码分析的工作原理。 AES 的 S-盒设计，它采用了 一套完整的数学计算。 9 （二）分组密码概述 1.分组密码定义： 分组密码是将明文消息编码表示后的数字序列 x0,x1,xi,划分成长为 n 的组 x=(x0,x1,xn-1)，各组（长为 n 的矢量）分别在密钥 k=(k0,k1,kt-1) 控制下变换成等长的输出数字序列 y=(y0,y1,ym-1)（长为 m 的矢量） ，其加密 函数 E：VnKVm，Vn和 Vm分别是 n 维和 m 维矢量空间，K 为密钥空间 通常取 m=n。若 mn，则为有数据扩展的分组密码；若 mn，则为有数据压 缩的分组密码。 2.分组密码和流密码的区别 （1）它与流密码不同之处在于输出的每一位数字不是只与相应时刻输入的明文 数字有关，而是与一组长为 n 的明文数字有关。 在相同密钥下，分组密码对长为 n 的输入明文组所实施的变换是等同的， 所以只需研究对任一组明文数字的变换规则。这种密码实质上是字长为 n 的数 字序列的代换密码。 （2）分组密码每次处理一个输入分组，相应地输出一个输出分组。流密码则是 连续地处理输入元素，每次输出一个元素。 （三）Feistel 密码结构 首先明确输入为明文和密钥，输出为密文。明文在输入时分为左右两半， 密文是将输出的左右两半合并到一起产生的。 加密过程是 n 轮迭代变换,每轮结构相同，只是各轮子密钥彼此不同而且与 K 也不同 每轮迭代满足的规律，其第 i 轮迭代的输入为前一轮输出的函数： Li = Ri-1 Ri = Li-1F (Ri-1,Ki) 其中 Ki 是第 i 轮用的子密钥，由加密密钥 K 得到。 七、DES 加密算法 【教学目的及要求】 掌握数据加密标准的运行步骤 【重点和难点】 重点：DES 加密算法。 难点：S 盒变换。 【教学方法】多媒体教学 【课时安排】2 学时 【主要参考书】 经典密码学与现代密码学 、 应用密码学教程、密码学原理和实践 【课程主要内容】 （一）数据加密标准 数据加密标准（data encryption standard, DES）是迄今为止世界上最为 广泛使用和流行的一种分组密码算法，它的分组长度为64比特，密钥长度为56 比特，它是由美国IBM公司研制的，是早期的称作Lucifer密码的一种发展和修 改。 （二）DES 描述 10 图 3.5 是 DES 加密算法的框图，其中明文分组长为 64 比特，密钥长为 56 比特。 图的左边是明文的处理过程，有 3 个阶段，首先是一个初始置换 IP，用于重排 明文分组的 64 比特数据。然后是具有相同功能的 16 轮变换，每轮中都有置换 和代换运算，第 16 轮变换的输出分为左右两半，并被交换次序。最后再经过一 个逆初始置换 IP-1（为 IP 的逆）从而产生 64 比特的密文。 和 Feistel 密码一样，DES 的解密和加密使用同一算法，但子密钥使用的顺 序相反。 （二）二重 DES 为了提高 DES 的安全性，并利用实现 DES 的现有软硬件，可将 DES 算法 在多密钥下多重使用。 二重 DES 是多重使用 DES 时最简单的形式，如图 3.8 所示。其中明文为 P，两个加密密钥为 K1 和 K2，密文为： C=Ek2Ek1P 解密时，以相反顺序使用两个密钥： P = Dk1Dk2C 因此，二重 DES 所用密钥长度为 112 比特，强度极大地增加。 八、置换和代换 【教学目的及要求】 掌握代换与置换的区别以及实现方法 【重点和难点】 迭代置换与代换 【教学方法】多媒体教学 【课时安排】2 学时 【主要参考书】 经典密码学与现代密码学 、 应用密码学教程、密码学原理和实践 【课程主要内容】 （一）代换 代换法是将明文中的每个元素映射成另一个元素或者说将明文字母替换成 其他字母,数字或符号的方法.如果把明文看做是二进制序列的话,那么代换就是 用密文位串代替明文位串.如 Casear 密码，对字母表中每个字母用它之后的第三 个字母来代换。 Casear 密码是单表代换密码，Playfair 是多表代换密码。 如果明文和密文的分组长为 n 比特,则明文的每一个分组都有 2n个可能的 取值.为使加密运算可逆(使解密运算可行),明文的每一个分组都应产生惟一的一 个密文分组,这样的变换是可逆的,称明文分组到密文分组的可逆变换为代换. 下图表示 n=4 的代换密码的一般结构： 11 如果分组长度太小,系统则等价于古典的代换密码,容易通过对明文的统计 分析而被攻破.这个弱点不是代换结构固有的,如果分组长度足够大,而且从明文 到密文可有任意可逆的代换,那么明文的统计特性将被隐藏而使以上的攻击不能 奏效. （二）置换 另一种加密方法是将明文中的元素重新排列,这种技术称为置换密码. 最简单的例子是栅栏技术,按照对角线的顺序写入明文,而按行的顺序读出作 为密文. 例如:，用深度为 2 的栅栏技术加密信息“meet me after the toga party”,可写 为 m e m a t r h t g p r y e t e f e t e o a a t 加密后的信息是 MEMATRHTGPRYETEFETEOAAT 九、公钥密码体制的基本原理 【教学目的及要求】 要求学生了解并掌握公钥密码体制的基本原理；理解 RSA 算法 【重点和难点】 重点：RSA 算法 【教学方法】多媒体教学 【课时安排】2 学时 【主要参考书】 经典密码学与现代密码学 、 应用密码学教程、密码学原理和实践 【课程主要内容】 本章是公钥密码包括：公钥密码体制的基本原理 RSA 算法 背包密码体制 公钥密码学基于的基本原理是构造单向陷门函数。可以有多种单向陷门函 数来实现公钥密码。基于素数分解的单向性再加上陷门信息就形成了 RSA 公钥 密码算法。基于求解离散对数的单向型再加上陷门信息就形成了 ElGamal 公钥 密码算法，如果离散对数问题作用在椭圆曲线群上，就形成了椭圆曲线加密算 法(ECC)。基于其它复杂问题，如背包问题，可行成背包加密算法。本章还包含 了对于各种公钥加密的基本密码分析及简单结论。 （一）公钥密码体制 在公钥密码体制以前的整个密码学史中，所有的密码算法，都是基于代换 和置换这两个基本工具。而公钥密码体制则为密码学的发展提供了新的理论和 技术基础，一方面公钥密码算法的基本工具不再是代换和置换，而是数学函数； 另一方面公钥密码算法是以非对称的形式使用两个密钥，两个密钥的使用对保 密性、密钥分配、认证等都有着深刻的意义。 可以说公钥密码体制的出现在密码学史上是一个最大的而且是惟一真正的 12 革命。 1产生背景 公钥密码体制的概念是在解决单钥密码体制中最难解决的两个问题时提出 的，这两个问题是密钥分配和数字签字。单钥密码体制在进行密钥分配时（看 第 5 章） ，要求通信双方或者已经有一个共享的密钥，或者可籍助于一个密钥分 配中心。对第一个要求，常常可用人工方式传送双方最初共享的密钥，这种方 法成本很高，而且还完全依赖信使的可靠性。第二个要求则完全依赖于密钥分 配中心的可靠性。第二个问题数字签字考虑的是如何为数字化的消息或文件提 供一种类似于为书面文件手书签字的方法。 1976 年 W.Diffie 和 M.Hellman 对解决上述两个问题有了突破，从而提出了 公钥密码体制。 2公钥密码体制的原理 （1）加密原理 公钥密码算法的最大特点是采用两个相关密钥将加密和解密能力分开，其 中一个密钥是公开的，称为公开密钥，简称公开钥，用于加密；另一个密钥是 为用户专用，因而是保密的，称为秘密密钥，简称秘密钥，用于解密。因此公 钥密码体制也称为双钥密码体制。 算法有以下重要特性： 已知密码算法和加密密钥，求解密密钥在计算上是 不可行的。 （2）加密过程 要求接收消息的端系统，产生一对用来加密和解密的密钥。 端系统 B 将加密密钥（如图中的 PKB）予以公开。另一密钥则被保密（图 中的 SKB） 。 A 要想向 B 发送消息 m，则使用 B 的公开钥加密 m。 B 收到密文 c 后，用自己的秘密钥 SKB 解密。 因为只有 B 知道 SKB，所以其他人都无法对 c 解密。 3）数字签字 公钥加密算法不仅能用于加、解密，还能用于对发方 A 发送的消息 m 提供 认证。用户 A 用自己的秘密钥 SKA 对 m 加密，表示为 c=ESKAm 将 c 发往 B。B 用 A 的公开钥 PKA 对 c 解密，表示为 m=DPKAc 因为从 m 得到 c 是经过 A 的秘密钥 SKA 加密，只有 A 才能做到。因此 c 可当做 A 对 m 的数字签字。另一方面，任何人只要得不到 A 的秘密钥 SKA 就 不能篡改 m，所以以上过程获得了对消息来源和消息完整性的认证。 十、RSA 算法 【教学目的及要求】 要求学生了解并掌握 RSA 算法以及背包密码体制 【重点和难点】 重点：RSA 算法，背包密码体制。 【教学方法】多媒体教学 13 【课时安排】2 学时 【主要参考书】 经典密码学与现代密码学 、 应用密码学教程、密码学原理和实践 【课程主要内容】 （一）RSA 算法 1密钥的产生 （1）选两个保密的大素数 p 和 q。 （2）计算 n=pq，(n)=(p-1)(q-1),其中 (n)是 n 的欧拉函数值。 （3）选一整数 e，满足 1e(n)，且 gcd(n),e)=1。 （4）计算 d，满足 de1 mod (n),即 d 是 e 在模 (n)下的乘法逆元，因 e 与 (n)互素，由模运算可知，它的乘法逆元一定存在。 （5）以e,n为公开钥,d,n为秘密钥。 2加密 加密时首先将明文比特串分组，使得每个分组对应的十进制数小于 n，即 分组长度小于 log2n。然后对每个明文分组 m，作加密运算： cme mod n 3解密 对密文分组的解密运算为： mcd mod n 十一、背包密码体制 【教学目的及要求】 要求学生熟练利用背包密码体制加解密 【重点和难点】 重点：背包密码体制。 【教学方法】多媒体教学 【课时安排】2 学时 【主要参考书】 经典密码学与现代密码学 、 应用密码学教程、密码学原理和实践 【课程主要内容】 （一）背包问题： 设 A=(a1,a2,an)是由 n 个不同的正整数构成的 n 元组，s 是另一已知的正 整数。背包问题就是从 A 中求出所有的 ai，使其和等于 s。其中 A 称为背包向 量，s 是背包的容积。 例如,A=（43, 129, 215, 473, 903, 302, 561, 1165, 697, 1523） ，s=3231。由于 3231=129+473+903+561+1165，所以从 A 中找出的满足要求的数有 129、473、903、561、1165。 原则上讲，通过检查 A 的所有子集，总可找出问题的解（如果有解的话） 。 本例 A 的子集共有 210=1024 个（包括空集） 。然而如果 A 中元素个数 n 很大， 子集个数 2n将非常大。如 A 中有 300 个元素，A 的子集有 2300。寻找满足要求 的 A 的子集没有比穷搜索更好的算法，因此背包问题是 NPC 问题。 如何由背包问题构造公钥密码体制 由背包问题构造公钥密码体制同样是要构造一个单向函数 f，将 x(1x2n-1)写成长为 n 的二元表示 0001,0010，0011,1111。 14 上例中 f(364) = f(0101101100) = 129+473+903+561+1165 = 3231。 由 f 的定义可见，已知 x 很容易求 f(x)，但已知 f(x)求 x 就是要解背包问题。 当然在实际应用中，n 不能太小，比如说，至少为 200。 （二）背包公钥密码系统的实现方案 用 f 对明文消息 m 加密时，首先将 m 写成二元表示，再将其分成长为 n 的 分组（最后一个分组不够长的话，可在后面填充一些 0） ，然后求每一分组的函 数值，以函数值作为密文分组。 超递增背包向量 为使接收方能够解密，就需找出单向函数 f(x)的陷门。为此需引入一种特 殊类型的背包向量。 已知 s 为背包容积，对 A 从右向左检查每一元素，以确定是否在解中。若 san，则 an 在解中，令 xn=1；若 san，则 an 不在解中，令 xn=0。下面令 s, sai，知 ABxk，所以 t-1c mod k=ABx，是惟一的。 十二、单钥、公钥加密体制的密钥分配 【教学目的及要求】 要求学生了解掌握单钥加密体制的密钥分配；掌握公钥加密体制的密钥管理 【重点和难点】 重点：单钥加密体制的密钥分配，公钥加密体制的密钥管理 【教学方法】多媒体教学 【课时安排】2 学时 【主要参考书】 经典密码学与现代密码学 、 应用密码学教程、密码学原理和实践 【课程主要内容】 本章是密钥分配与密钥管理包括：单钥加密体制的密钥分配 公钥加密体制的密钥管理 （一）密钥管理 密码系统的强度也依赖于密钥分配技术。 15 两个用户（主机、进程、应用程序）在用单钥密码体制进行保密通信时， 首先必须有一个共享的秘密密钥，而且为防止攻击者得到密钥，还必须时常更 新密钥。因此，密码系统的强度也依赖于密钥分配技术。 1两个用户 A 和 B 获得共享密钥的方法 （1）密钥由 A 选取并通过物理手段发送给 B。 （2）密钥由第三方选取并通过物理手段发送给 A 和 B。 （3）如果 A、B 事先已有一密钥，则其中一方选取新密钥后，用已有的密钥加 密新密钥并发送给另一方。 （4）如果 A 和 B 与第三方 C 分别有一保密信道，则 C 为 A、B 选取密钥后， 分别在两个保密信道上发送给 A、B。 2密钥分配方法中存在的问题 前两种方法称为人工发送。在通信网中，若只有个别用户想进行保密通信， 密钥的人工发送还是可行的。然而如果所有用户都要求支持加密服务，则任意 一对希望通信的用户都必须有一共享密钥。如果有 n 个用户，则密钥数目为 n(n-1)/2。因此当 n 很大时，密钥分配的代价非常大，密钥的人工发送是不可行 的。 对于第 3 种方法，攻击者一旦获得一个密钥就可获取以后所有的密钥；而 且用这种方法对所有用户分配初始密钥时，代价仍然很大。 第 4 种方法比较常用，其中的第三方通常是一个负责为用户分配密钥的密 钥分配中心。这时每一用户必须和密钥分配中心有一个共享密钥，称为主密钥。 通过主密钥分配给一对用户的密钥称为会话密钥，用于这一对用户之间的保密 通信。通信完成后，会话密钥即被销毁。如上所述，如果用户数为 n，则会话 密钥数为 n(n-1)/2。但主密钥数却只需 n 个，所以主密钥可通过物理手段发送。 十三、密钥托管与消息认证码 【教学目的及要求】 要求学生了解美国国家安全局的密钥托管系统与机制 【重点和难点】 重点：公钥加密体制的密钥管理 【教学方法】多媒体教学 【课时安排】2 学时 【主要参考书】 经典密码学与现代密码学 、 应用密码学教程、密码学原理和实践 【课程主要内容】 （一）密钥托管 补充：密钥托管就是将专用密钥存放在一个高度可信的企业或机构那里以 防万一它们丢失或因其它原因需要恢复。我们举一人个日常生活中的例子来说 明这个问题。用户可以将钥匙存放在附近的警察局里，这样一旦丢失了钥匙他 就可以到警察那里找钥匙开门，或者是如果警察觉得有必要的话他们也可以进 入你的房子。既然你将密钥放到另一个机构那里去保存，这个机构就必须是非 常可信的。密钥托管也叫作密钥恢复。 密钥托管加密技术提供了一个备用的解密途径，政府机构在需要时，可通 过密钥托管技术解密用户的信息，而用户的密钥若丢失或损坏，也可通过密钥 托管技术恢复自己的密钥。所以这个备用的手段不仅对政府有用，而且对用户 16 自己也有用。 1美国托管加密标准简介 1993 年 4 月，美国政府为了满足其电信安全、公众安全和国家安全，提出 了托管加密标准 EES(escrowed encryption standard)。 十四、杂凑函数 【教学目的及要求】 要求学生掌握消息认证码的含义；比较杂凑函数的输出 【重点和难点】 重点：消息认证码、杂凑函数 难点：杂凑函数 【教学方法】多媒体教学 【课时安排】2 学时 【主要参考书】 经典密码学与现代密码学 、 应用密码学教程、密码学原理和实践 【课程主要内容】 本章是消息认证和杂凑函数，包括消息认证码、杂凑函数 （一）杂凑函数的定义 杂凑函数 H 是一公开函数，用于将任意长的消息 M 映射为较短的、固定 长度的一个值 H(M)，作为认证符，称函数值 H(M)为杂凑值、杂凑码或消息摘 要。 杂凑函数的作用 杂凑码是消息中所有比特的函数，因此提供了一种错误检测能力，即改变 消息中任何一个比特或几个比特都会使杂凑码发生改变。 1杂凑函数的基本使用方式 （1）消息与杂凑码链接后用单钥加密算法加密。 （2）用单钥加密算法仅对杂凑码加密。 （3）用公钥加密算法和发送方的秘密钥仅加密杂凑码。 （4）消息的杂凑值用公钥加密算法和发送方的秘密钥加密后与消息链接，再对 链接后的结果用单钥加密算法加密。 （5）使用这种方式时要求通信双方共享一个秘密值 S，A 计算消息 M 和秘密 值 S 链接在一起的杂凑值，并将此杂凑值附加到 M 后发往 B。 （6）这种方式是在中消息与杂凑值链接以后再增加单钥加密运算。 十五、数字签字原理 【教学目的及要求】 要求学生了解掌握数字签字原理 【重点和难点】 重点：数字签字原理 难点：认证协议 【教学方法】多媒体教学 【课时安排】2 学时 【主要参考书】 经典密码学与现代密码学 、 应用密码学教程、密码学原理和实践 17 【课程主要内容】 （一）数字签字 信息认证作为一种基本信息安全服务，有三种常见的方法完成信息认证： 加密，消息认证码(MAC)和散列函数。散列函数是本章讲述的另一个在密码学 中常用的基本工具。和传统的散列函数不同，密码学中用到的散列必须满足一 定的安全特征：单向性、弱碰撞抵抗性和强碰撞抵抗性。为满足这些特征，在 密码学中一般采用一种类似 CBC 操作模式的结构作为安全散列函数的一般框架。 MD5 是一种常用的散列算法，他就基于上述结构；而 SHA 和 MD5 只存在细 微的差别而已。数字签名是实现不可否认性的一种基本手段。和手写的签名从 功能类似，但数字签名的实现必须依靠公钥密码学。所以基于 RSA 算法形成了 RSA 签名方案，基于 ElGamal 方法形成了 ElGamal 签名方案。数字签名标准 (DSS)只是一种较为复杂的组合而已。 有一种强碰撞攻击在分析安全散列算法中常用，就是常说的生日攻击。生 日攻击的原理是基于概率计算获得的，其计算过程比较简单，但出人意料的结 果就是难点所在。由于数字签名基于公钥密码学，所以其安全性分析可以基于 以往的分析进行，但有时也需注意区别。 十六、密码认证协议 【教学目的及要求】 要求学生了解掌握认证协议与数字签字的区别和原理 【重点和难点】 难点：认证协议 【教学方法】多媒体教学 【课时安排】2 学时 【主要参考书】 经典密码学与现代密码学 、 应用密码学教程、密码学原理和实践 【课程主要内容】 （一）认证协议 本节以网络通信的一个基本问题的解决引出认证协议的基本意义，这一基 本问题陈述如下： A 和 B 是网络的两个用户，他们想通过网络先建立安全的 共享密钥再进行保密通信。那么 A(B)如何确信自己正在和 B(A)通信而不是和 C 通信呢？这种通信方式为双向通信，因此，此时的认证称为相互认证。类似 地，对于单向通信来说，认证称为单向认证。 （二）相互认证 A、B 两个用户在建立共享密钥时需要考虑的核心问题是保密性和实时性。 为了防止会话密钥的伪造或泄露，会话密钥在通信双方之间交换时应为密文形 式，所以通信双方事先就应有密钥或公开钥。第 2 个问题实时性则对防止消息 的重放攻击极为重要，实现实时性的一种方法是对交换的每一条消息都加上一 个序列号，一个新消息仅当它有正确的序列号时才被接收。但这种方法的困难 性是要求每个用户分别记录与其他每一用户交换的消息的序列号，从而增加了 用户的负担，所以序列号方法一般不用于认证和密钥交换。 1保证消息的实时性常用以下两种方法： （1）时戳 （2）询问-应答 18 十七、网络通信加密与 PGP 【教学目的及要求】 要求学生了解目前常用的网络通信加密协议和方案 【重点和难点】 重点：网络通信加密 【教学方法】多媒体教学 【课时安排】2 学时 【主要参考书】 经典密码学与现代密码学 、 应用密码学教程、密码学原理和实践 【课程主要内容】 本章是网络加密与认证，包括 网络通信加密、PGP （一）基本方式 为了将数据在网络中传送，需要在数据前面加上它的目的地址，称加在数 据前面的目的地址为报头，用户数据加上报头称为数据报。加强网络通信安全 性的最有效且最常用的方法是加密，网络加密的基本方式有两种：链路加密和 端端加密。 1链路加密 2端端加密 （二）端端加密的逻辑位置 端端加密的逻辑位置是指将加密功能放在 OSI 参考模型的哪一层，可有几 种选择，其中最低层的加密可在网络层进行，这时，被保护的实体数目与网络 中终端数目一样，任意两个终端如果共享同一密钥，就可进行保密通信。一终 端系统若想和另一终端系统进行保密通信，则两个端系统用户的所有处理程序 和应用程序都将使用同一加密方案和同一密钥。 一十八、复习 【教学目的及要求】 要求学生了解并掌握全书中的基本概念和基本思想、基本原理。 【重点和难点】 重点：复习全部教材的第 2，3，4，5，6 章中内容。 【教学方法】多媒体教学 【课时安排】2 学时 【主要参考书】 经典密码学与现代密码学 、 应用密码学教程、密码学原理和实践 【课程主要内容】 对本学期的内容作全面复习。 第二部分：实践教学大纲第二部分：实践教学大纲 一、实验教学内容及方法 密码学基础的实验教学旨在加强实践环节，培养学生动手能力，使学 生学完课程后，对密码学的原理、思想和算法都有清晰、深入的理解。让学生 19 通过多个密码算法的程序设计实现，更好地掌握密码算法设计的机理和方法。 同时，基于密码系统设计的基本方法和基本步骤，帮助学生理解密码学在信息 安全中的地位，并引导了解密码学领域及信息安全领域的新进展、新方向。通 过实践帮助学生进一步掌握密码学领域的基本原理、基本思想及基本算法原理。 使学生对密码系统设计和分析的基本方法和步骤形成一个清晰、全面的认识。 帮助学生认识密码学在信息安全中的地位，引导学生