13.1 超越基 定义 13.1.1 代数相关 代数无关 注 例 13.1.1 定理 13.1.1 证明 13.2 有限域的构造 定理 13.2.1 证明 定理8.2.2 推论 定理 5.1.1 定义 13.2.1 本原元 生成元 本原多项式 注 定义 11.5.1 定理 13.2.2 证明 推论1 推论 2 定理 13.2.3 证明 13.5 习题 （1） Solution （2） Solution

12.1 域的扩张 12.1.1 域的有限扩张 定义 12.1.1 扩域 首先,从集合的包含关系的角度来讨论域的性质. 设F是一个域.如果K是F的子域,则称F为K的扩域. 其次,从线性空间的角度来讨论域的性质. 12.4 习题 (1) Solution (2) Solution

Lecture 谓词逻辑 需要更丰富的语言 谓词逻辑作为一种形式语言 术语-变量、函数 公式-谓词、量词 自由变量和约束变量 替代 谓词逻辑的证明理论 自然演绎规则 需要更丰富的语言 命题逻辑： 研究陈述句，关于世界的陈述，这些陈述可以被赋予真理值 能很好地处理句子成分，如：not，and，or，if then 限制：无法处理修改器，如存在、全部、中间、仅。 例子：“每个学生都比一些老师年轻。” 我们可以用命题符号p来识别整个短语。 然而，这个短语有更精细的逻辑结构。它是关于以下属性的声明： 作为一名学生 当讲师 比别人年轻 谓词、变量和...

Assignment 下载并安装VanetMobiSim，http://vanet.eurecom.fr/ 使用道路地图（VanetMobiSim can import maps from the US Census Bureau TIGER/Line） 地图范围截取1km*1km，车辆密度300，车速30-80km/h 模拟时间60s Guide VanetMobiSim is an extension for the CANU Mobility Simulation Environment (CanuMobiSim), a flexible framework for user ...

Assignment 通过证明以下情况，补充命题逻辑的可靠性和完整性证明： 对于可靠性证明，请完成以下证明规则案例的证明： ∧e1 Solution ，其中出现在l<k行。公式具有较短的证明，因此使用归纳假设，它具有真值T。根据∧的真值表，我们可以得出结论，具有真值T。 ∧e2 Solution 同上。 ⊥e Solution ⊥ 出现在第l<k行。这意味着我们在行出现。利用归纳假设，同时具有真值T。在这样的真值表中，任何公式都可以有真值T。 ¬i Solution ，以φ作为第l<k行的假设，以及⊥ 出现在第m<k行，。如果φ是T，那么归纳假设告诉我们⊥ 是T，因为它...

Lecture 命题逻辑 学习逻辑的动机：获得模拟现实生活情景的能力，使我们能够正式地对其进行推理。 例1：如果火车晚点，而且车站没有出租车，那么约翰开会就迟到了。约翰开会没有迟到。火车确实晚点了。因此，车站有出租车。 例2：如果下雨，简没有带雨伞，她就会淋湿。简没有淋湿。下雨了。因此，简随身带着雨伞。 我们能正式验证这些论点的有效性吗？ 我们需要把英语句子转换成公式（建模）。 然后，我们可以将数学推理应用到公式中 造型 编码： 模式： If p and not q, then r. Not r. p. Therefore q. 我们将研究推理模式。 陈述句 陈述句（我们可以考虑...

22.4 拓扑排序 拓扑排序 本节阐述如何使用深度优先搜索来对有向无环图进行拓扑排序。对于一个有向无环图G=(V,E)来说，其拓扑排序是G中所有结点的一种线性次序，该次序满足如下条件:如果图G包含边(u，v)，则结点u在拓扑排序中处于结点v的前面(如果图G包含环路，则不可能排出一个线性次序)。可以将图的拓扑排序看做是将图的所有结点在一条水平线上排开，图的所有有向边都从左指向右。因此，拓扑排序与本书第二部分所讨论的通常意义上的“排序”是不同的。 下面的简单算法可以对一个有向无环图进行拓扑排序: TOPOLOGICAL-SORT(G) call DFS(G) to compute finis...

验证方法 Verification Methods 验证方法可根据以下主要标准进行分类： 基于证明与基于模型-如果可靠性和完整性定理成立，则： 证明=有效公式=适用于所有型号； 基于模型=检查一个模型的可满足性 自动化程度-完全自动化、部分自动化或手动 完整-与属性验证-单个属性与完整行为 应用领域-硬件或软件；连续的或并发的；反应的或终止的；等 前期开发与后期开发 模型检查 1 Model Checking 模型检查是一种验证方法，即： 基于模型的自动化，使用属性验证方法，主要用于验证并发程序和反应式系统，通常在后开发阶段。 程序验证（稍后研究）是： ...

我们从讨论基于RSA假设的签名方案开始考虑具体的签名方案。 12.4.1 普通RSA Plain RSA 我们首先描述一个简单的、基于RSA的签名方案。虽然该方案不安全，但它是一个有用的起点。 通常，让GenRSA作为一种ppt算法，在输入上，输出两个N位素数（概率可以忽略不计的除外）的乘积的模N，以及满足ed = 1 mod φ（N）的整数e，d。普通RSA中的密钥生成只需要运行GenRSA，并输出< N，e>作为公钥，< N，d>作为私钥。签名，签名者计算。通过检查来验证消息m上关于公钥< N，e>的签名σ。参见构造12.5。 构造 12.5 纯RSA签...

在公钥与私钥加密的情况下，“本机”签名方案的效率比消息认证码低几个数量级。幸运的是，与混合加密一样（见第11.3节），至少对于足够长的消息，可以以私钥操作的渐进成本获得数字签名的功能。这可以使用下面讨论的哈希和签名方法来完成。 散列和符号方法背后的直觉是直截了当的。假设我们有一个长度为l的消息的签名方案，并希望对一个（较长的）消息进行签名. 我们可以使用散列函数H将消息散列到长度为l的固定长度摘要，然后对结果摘要进行签名，而不是对m本身进行签名。该方法与第5.3.1节中讨论的哈希和MAC方法完全类似。 构造 12.3 哈希和符号范式 设∏=（Gen，Sign，Vrfy）是长度为了l（n）的消息...

数字签名是消息身份验证码的公钥对应物，其语法和安全保证类似。发送方应用于消息的算法在这里表示为Sign（而不是Mac），该算法的输出现在称为签名（而不是标记）。接收方应用于消息和签名以验证有效性的算法仍然表示为Vrfy。 定义 12.1 （数字）签名方案由三种概率多项式时间算法（Gen、Sign、Vrfy）组成，其中： 密钥生成算法Gen将安全参数作为输入，并输出一对密钥（pk，sk）。它们分别称为公钥和私钥。我们假设pk和sk的长度至少为n，并且n可以由pk或sk确定。 签名算法Sign从某些消息空间（可能取决于pk）获取私钥sk和消息m作为输入。它输出一个签名σ，我们把它写成。 ...

在上一章中，我们探讨了如何使用公钥加密在公钥设置中实现保密性。使用数字签名方案提供公钥设置中的完整性（或真实性）。这些可被视为消息身份验证码的公钥模拟，尽管我们将看到，这些原语之间有几个重要的区别。签名方案允许已建立公钥pk的签名者使用相关私钥sk对消息进行“签名”，其方式使任何知道pk的人（并且知道此公钥是由S建立的）可以验证消息是否源自S且在传输过程中未被修改。（请注意，与公钥加密不同，在数字签名的上下文中，公钥的所有者充当发送者。）作为一个典型的应用程序，考虑一个软件公司想要以一种经过验证的方式传播软件更新；也就是说，当公司发布更新时，任何一个客户都有可能验证更新是真实的，恶意的第三方永...

4.3 恶意节点防范 4.3.1 背景及相关工作 无线传感器网络中的节点很容易被攻击者俘获而成为内部恶意节点 一方面，由内部恶意节点发起的这些攻击行为通常会严重影响网络的性能 另一方面，由内部恶意节点发起的攻击往往比攻击者在外部发起的攻击更难防范，这是由于传统的一些密钥机制在此时将会失效。 如何有效地防范内部恶意节点的攻击行为，对于提高无线传感器网络的性能和安全性都具有十分重要的意义。 本节基于演化博弈的思想 从经济学的角度深入分析恶意节点获利的动机 在理性节点的策略空间上增加一个防御策略 建立起相应的防范机制，使得恶意节点无利可图，放弃攻击甚至转而合作 有效地提高网络的性能。 ...

在本节中，我们将关注基于第8.2.4节中定义的RSA假设的加密方案。我们注意到，尽管基于RSA的加密在今天得到了广泛的使用，但由于基于RSA的方案需要更长的密钥长度，目前也逐渐从使用RSA转向使用依赖于椭圆曲线组的基于CDH/DDH的加密系统。我们参考第9.3节进行进一步讨论。 11.5.1 普通RSA Plain RSA 我们首先描述一个基于RSA问题的简单加密方案。尽管该方案是不安全的，但它为随后的安全方案提供了一个有用的起点。假设GenRSA是一个ppt算法，它在输入1n上输出一个模N，该模N是两个N位素数的乘积，以及满足ed=1 mod φ（N）的整数e，d。（通常，该算法失败的概率可...