到目前为止，我们已经抽象地讨论了公钥加密，但还没有看到任何公钥加密方案（或KEMs）的具体示例。在这里，我们探讨了一些基于Diffie–Hellman问题的构造。（Diffie–Hellman问题在第8.3.2节中介绍。） 11.4.1 El Gamal加密 El Gamal Encryption 1985年，Taher El-Gamal观察到Diffie–Hellman密钥交换协议（参见第10.3节）可适用于提供公钥加密方案。回想一下，在Diffie–Hellman协议中，Alice向Bob发送一条消息，然后Bob向Alice回复一条消息；基于这些消息，Alice和Bob可以导出一个共享值k...

11.3 混合加密和KEM/DEM范式 Hybrid Encryption and the KEM/DEM Paradigm

11.1 公钥加密–概述 Public-Key Encryption – An Overview 公钥加密的引入标志着密码学的一场革命。在此之前，密码学家完全依靠共享的秘密密钥来实现私人通信。相比之下，公钥技术使双方能够私下通信，而无需事先商定任何秘密信息。正如我们已经注意到的，这是非常令人惊讶的，也是非常直观的：这意味着一个房间对面的两个人只能通过大声喊叫进行交流，并且没有最初的秘密，他们可以以这样的方式交谈，以至于房间里的其他人都不知道他们在说什么！ 在私钥加密的设置中，双方同意一个可由任何一方用于加密和解密的密钥。公钥加密在这两方面都是不对称的。一方（接收方）生成一对密钥（pk，sk），...

11.2 定义 Definitions 我们首先定义公钥加密的语法。该定义与定义3.7非常相似，只是不再使用一个密钥，而是使用不同的加密和解密密钥。 定义11.1公钥加密方案 定义11.1公钥加密方案是概率多项式时间算法（Gen、Enc、Dec）的三倍，因此：  密钥生成算法Gen将安全参数1^n作为输入，并输出一对密钥（pk，sk）。我们将其中的第一个称为公钥，第二个称为私钥。为了方便起见，我们假设pk和sk的长度至少为n，并且n可以由pk，sk确定。 加密算法Enc将公钥pk和来自某个消息空间（可能取决于pk）的消息m作为输入。它输出一个密文c，我们把它写成 。（展望未来，为了实现有意义的...

7.1 快速排序的描述 分解：数组 A[p..r]被划分为两个(可能为空)子数组 A[p..q-1]和A[q+1..r]，使得A[p..q-1]中的每一个元素都小于等于 A[q]，而A[q]也小于等于A[q+1..r]中的每个元素。其中，计算下标q也是划分过程的一部分。 解决：通过递归调用快速排序，对子数组A[p..q-1]和A[q+1..r]进行排序。 合并：因为子数组都是原址排序的，所以不需要合并操作:数组A[p..r]已经有序。 下面的程序实现快速排序: 伪代码 过程 QUICKSORT //初始调用QUICKSORT(A,1,A.length) QUICKSORT(A,p,r) if ...

3.1 渐进记号 渐进记号 Θ, O, o, Ω, ω  Θ记号 渐进紧确界 =  O记号 渐进上界 ≤  Ω记号 渐进下界 ≥  o记号 非渐进紧确的上界 ＜  ω记号 非渐进紧确的下界 ＞  比较各种函数 传递性  自反性  对称性  转置对称性  类比两个函数f与g的渐进比较和两个实数a与b的比较  定理 3.1  3.2 标准记号与常用函数 单调性 【单调递增/减 严格递增/减】  向下取整与向上取整  模运算  多项式   指数   阶乘  多重函数  多重对数   斐波那契数   思考题 3-2 相对渐进增长  Indicate for each pair of expressio...

2.1 插入排序 排序问题 输入：n个数的一个序列<a1,a2,……,an>。 输出：输出序列的一个排列<a1',a2',……,an'>，满足a1'≤a2'≤……≤an'。 希望排序的数称为关键词。 伪代码 过程 INSERTION-SORT(A) INSERTION-SORT(A) for j = 2 to A.length key = A[j] //Insert A[j] into the sorted sequence A[1……j-1]. i = j - 1 while i > 0 and A[i] > key A[i+1] = A [i] i = ...

4.1 最大子数组问题 使用分治策略的求解方法  伪代码 过程 FIND-MAX-CROSSING-SUBARRAY(A,low,mid,high) //接受数组A和下标low,mid,high为输入 //返回一个下标元组跨越中点的最大子数组的边界 //并返回最大子数组中值的和 FIND-MAX-CROSSING-SUBARRAY(A,low,mid,high) //求出左半部A[low..mid]的最大子数组 left-sum = - ∞//初始化变量left-sum，保存目前为止找到的最大和 sum = 0//初始化变量sum，保存A[i..mid]中所有值的和 for i = mid d...

6.1 堆 伪代码 过程 PARENT(i) //父节点的下标 PARENT(i) return ⌊i/2⌋  伪代码 过程 LEFT(i) //左孩子的下标 LEFT(i) return 2i  伪代码 过程 RIGHT(i) //右孩子的下标 RIGHT(i) return 2i+1  6.2 维护堆的性质 伪代码 过程 MAX-HEAPIFY(A,i) //维护最大堆性质的重要过程 //最大堆性质：A[PARENT(i)] ≥ A[i] MAX-HEAPIFY(A,i) l = LEFT(i) r = RIGHT(i) if l ≤ A.heap-size and A[l] > A...

8.1 排序算法的下界 插入排序算法作用域包含三个元素的输入序列的决策树情况  最坏情况的下界 在决策树中，从根节点到任意一个可达叶结点之间最长简单路径的长度，表示的是对应的排序算法中最坏情况下的比较次数。 因此，一个比较排序算法中的最坏情况比较次数就等于其决策树的高度。 同时，当决策树中每种排列都是以可达的叶结点的形式出现时，该决策树高度的下界也就是比较排序算法运行时间的下界。 下面的定理给出这样的一个下界。 定理 8.1 在最坏情况下，任何比较排序算法都需要做Ω (nlgn)次比较。  推论 8.2 堆排序和归并排序都是渐进最优的比较排序算法。 证明 堆排序和归并排序的运行时间上界为O(n...

16.1 活动选择问题 伪代码 递归贪心算法 //输入：两个数组s和f，表示活动的开始和结束时间 //输入：下标k指出要求解的子问题S[k]，以及问题规模n //返回：S[k]的一个最大兼容活动集 //假定输入的n个活动已经按结束时间的单调递增顺序排列好 RECURSIVE-ACTIVITY-SELECTOR(s,f,k,n) //结束时间相同的活动可以任意排列 //为了方便算法初始化，添加一个虚拟活动a[0]，其结束时间f[0]=0,这样子子问题S[0]就是完整的活动集S //求解原问题即可调用RECURSIVE-ACTIVITY-SELECTOR(s,f,0,n) m = k + 1 //...

9.1 最小值和最大值 伪代码 过程 MINIMUM(A) MINIMUM(A) min = A[1] for i = 2 to A.length if min > A[i] min = A[i] return min  同时找到最大值和最小值 事实上，我们只需要最多3⌊n/2⌋次比较就可以同时找到最小值和最大值。具体的方法是记录已知的最小值和最大值。但我们并不是将每一个输人元素与当前的最小值和最大值进行比较——这样做的代价是每个元素需要2次比较，而是对输入元素成对地进行处理。首先，我们将一对输人元素相互进行比较，然后把较小的与当前最小值比较，把较大的与当前最大值进行比较。这样，对每两个...

动态规划方法通常用来求解最优化问题（optimization problem）。 我们通常按如下4个步骤来设计一个动态规划算法： 动态规划算法求解问题的基础。  刻画一个最优解的结构特征 递归地定义最优解的值 计算最优解的值，通常采用自底向上的方法  维护一些额外信息，以便用来构造一个最优解  利用计算出的信息构造一个最优解  15.1 钢条切割 研究如何将长钢条切割成短钢条，使得总价值最高 钢条切割问题 给定一段长度为n英寸的钢条和一个价格表pi(i=1,2,……,n)，求切割钢条方案，使得销售收益rn最大。注意，如果长度为n英寸的钢铁的价格pn足够大，最优解可能就是完全不需要切割。 最优子...

Chapter 16 Greedy Algorithms 贪婪算法 Greedy Algorithms  与动态规划类似，但方法更简单  –也用于优化问题  想法：当我们有选择的时候，现在就做一个看起来最好的  –做出局部最优选择，希望获得全局最优解决方案   贪婪算法并不总是产生最优解   当问题具有某些一般特征时，贪婪算法给出最优解   选择活动 Activity Selection  计划n需要独占使用公共资源的活动 ——一套活动 【compatible（可共用的）】【overlap（重叠）】  活动选择问题 Activity Selection Problem 选择最大可能的不重叠（相...