SCHNIEBOW

模式匹配自动机 什么是有限状态自动机？定义n个不同状态，记为{1,2…n}，在状态i时输入s，达到状态j，记为goto(i,s)=j对于字符串s而言，在一个状态i下输入一个字符ch，也会达到一个指定状态 ：假定新的状态为串s[1,i]+ch的最长相等前后缀 ，便能够用这个状态机模拟KMP算法匹配字符串的过程。当字符集仅为a、b时，有：其中goto(4,a)=3，也就是说abab+a的最长相等前后缀 对应的状态是状态3 ，也即表示字符串“aba”的状态。似乎这样就足够了。我们获得了goto函数，定义为： goto(Si,a)：串s[1,i]a的最长相等前后缀。 为了得到这个goto函数的值，我们需要定义fail函数： fail(Si):串s[1,i]的最长相等前后缀。 因为得到goto(i,a)的前提是，知道s[1,i]的最长相等前后缀s\[1,j] ：若s[j+1]与a相同，则goto(i,a)=j+1，否则求s[1,j]的最长相等前后缀，直到长度为0。为了表示“s[j+1]与a相同”这一条件，定义函数： follow(Si, a):状态Si输入 ...

BM算法 BM算法是一种字符串匹配的算法。与KMP相比，BM算法不扫描全部输入字符，平均匹配时间c·n, 常量 c <1 (随机或真实文本), 但最坏情况是O(n·m).可以将BM算法的最坏情况改进到O(n)：通过记录文本后缀中最长的模式后缀。要使用BM算法，需要知道两个信息：1.用于坏字符规则的bc数组2.用于好后缀规则的gs数组 坏字符规则 坏字符规则分为两种情况：1.失配位置指向的文本串中对应的字符 ，不存在于模式串中。如上图所示，在这种情况下，直接将整个模式串移动到失配位置 之后。 2.失配位置指向的文本串中对应的字符 ，存在于模式串中，且在失配位置 的左边。如上图所示，在这种情况下，将模式串中的文本串中对应的字符 放在失配位置 上。需要注意两个问题：1.这个“模式串中的文本串中对应的字符 ”，是整个模式串从右往左数的第一个符合的字符。否则会造成过度左移。2.模式串中最后一个字符，不能和任何的失配位置 匹配。这是因为“失配”的前提是有匹配，而右边第一个字符必然被匹配；否则在右边第一个字符失配，那说明所需要的字符不是这个右边的第一个字符。故最后一个字符对应的位置是从右边数 ...

入侵检测系统概念 入侵：未经授权的计算机使用者以及不正当使用(misuse)计算机的合法用户(内部威胁)，危害或试图危害资源的完整性、保密性、可用性的行为。入侵检测：通过监测计算机系统的某些信息，加以分析，检测入侵行为，并作出反应。入侵检测系统：实现入侵检测功能的硬件与软件。核心问题：降低误报率结构：事件产生器（Event generater， E-box）收集入侵检测事件,并提供给IDS其他部件处理。事件可以是网络活动，也可是系统调用序列等系统信息。事件分析器（Analysis engine, A-box）对输入的事件进行分析并检测入侵。事件数据库（Event database, D-box）存储和管理E-boxes 和 A-boxes 产生的大量数据，用于IDS(入侵检测系统)的训练和证据保存。事件响应器（Response unit, C-box）对入侵做出响应，包括向管理员发出警告，切断入侵连接，根除入侵者留下的后门以及数据恢复等。分类：误用检测(基于特征的检测)：判别当前行为是否符合已知攻击的知识库中记录的的攻击模式。机制：状态模型、专家系统、正则表达式匹配异常检测(基于行为的 ...

堆栈构造 静态存储可变存储函数调用text segment存放代码；data segment存放初始化了的静态变量；BSS segment存放未初始化的静态变量。Heap存放需要长期保存的变量；Stack存放临时变量。调用函数时，如f(int a,int b)：则b放在大的正地址如ebp+12，a放在小的正地址如ebp+8，临时变量放在负地址如ebp-4。旧的ebp放在ebp+0，返回地址放在ebp+4。这些数据构成一个栈帧。 内存分配 攻击方式 攻击原理：栈溢出时，能把以前的数据覆盖。 -攻击步骤1：在return address和攻击代码之间可写NOP；如果return address域指向的地址高于其自身的地址，则程序会沿着NOP走到攻击代码。(攻击代码足够短的话，也能放在return address之前)-攻击步骤2：确定return address到栈底的偏移量，在这里将存放新的返回地址。-攻击步骤3：在堆栈空间内找到存放攻击代码(操作寄存器的汇编代码)的地址。 注意：字符串中的0会将字符串截断。解决：寄存器与寄存器自身异或获得数据0。例子：execve()的 ...

(t-n)门限方案 n个人中的t个人能还原秘密。 用对称密钥实现shamir方案实现使用几何学实现基于中国剩余定理略用拉格朗日插值定理实现。考试重点t-1阶的多项式P(x)，P(0)=s秘密。所有运算都是模p的，且s，n＜p。表达式：f(x)=∑i=0nyili(x),其中li(x)=∏j=0,j!=in(x−xj)(xi−xj)例子：p=7,f(1)=2,f(2)=1,f(4)=5:ff(1)=2*(x-2)(x-4)/(1-2)(1-4)=10(x-2)(x-4);ff(2)=1(x-1)(x-4)/(2-1)(2-4)=3(x-1)(x-4);ff(3)=5(x-1)(x-2)/(4-1)(4-2)=30(x-1)*(x-2);相加得：x²-4x+5(mod 7)略任选n个俩俩互质的数，任意k个数的乘积＞m，s＜m。原理：少于k个时，得到的s‘比真正的s小，不能唯一地确认真正的s。

什么是安全策略 计算机安全的一般定义：你可以依赖计算机，且计算机如你预料的那样行动。不同的计算机对安全有更精确的划分，描述这种安全的方式叫做安全策略。安全机制：实现安全策略的机制。攻击破坏安全机制，使计算机在预料之外行动。 计算机安全基本问题 在什么条件下，一个计算机算法可判定一个计算机系统是否安全？结论：安全模型表达能力越强，验证安全性越难。简单模型描述能力有限，但存在有效验证安全性的方法。 访问控制模型 访问控制矩阵ACMHaarrion-Ruzzo-Ullman模型Take-Grant模型保护状态：涉及安全保护的状态ACM是描述当前保护状态的最精确的模型，主体与主体之间也存在不同权限。 文件f 文件g 进程p 进程q 进程p 读写 读写 读写添加创建 写 进程q 读写 读写 读 读写添加创建 ACM的行称为能力表，ACM的列称为访问控制列表(常用)。基本命令：创建主体客体、删除主客体、增加权限，删除权限。单步命令：包含一条基本命令(基本命令不可直接调用)的命令。单步命令系统的可靠性问题可判定。 证明：1.delete操作可忽略：因为状态数固定2.所有cre ...

前置知识 在量子理论中，用向量表示0比特和1比特。量子比特qubit的叠加可能性：a0+b1，其中a²+b²=1。测量此比特，得到1比特的可能性。(a,b为几率幅，结果为0的可能性为a²，结果为1的可能性为b²。a，b是复数)测量对qubit的影响：使叠加态不可逆地坍缩到测出的态。不可克隆：不能精确复制量子态，但能移动。光子通过光栅，是对光子的测量。光子通过光栅后，光子偏振方向与光栅方向相同。如果偏振方向和光栅方向的角度为a，则该光子通过光栅的可能性为cos²a。 BB84协议实现密钥分配B92协议(更优)光子的编码方式：以一个方向代表1，与其垂直的方向代表0。BB84只采用两种：x或者＋。(垂直的或45°倾斜的) 1.A选择一个比特b。 2.A选择一个发送方式：x或者＋。 3.B选择一个接收方式：x或者＋。 4.A公布发送方式，B公布接收方式。如果两个方式不同，则抛弃接收结果。 重复以上过程4N次，最终，A有2N比特，B有2N比特，随机选择N比特作为秘密(如果两方的N比特完全一致，则大概率认为没有窃听者存在(如果窃听者选择了错误的接收方式，则会破坏信息，使接 ...

公钥算法的优化 加密算法的两个重要指标是加密强度和速度。在实现上，可以用各种技术来提高算法速度。加密算法分为密钥生成和加解密，主要优化加解密部分。Amdahl定律：优化一段代码的效果，取决于其执行时间占全部执行时间的比例。 优化工作的方向 充分利用CPU特性，如流水线和指令并行 针对加密算法本身做一些优化 编译器也会做一些优化：编译器的优化很保守(保证正确性)，且一些优化对于程序员来说简单，对编译器来说很难 软件优化一般方法代码移动预计算指令替换共享子表达式减少多余过程调用限制变量利用指令并行：调整代码顺序，使相近的两条指令的数据不相关将条件分支指令按照概率和计算量排列次序如先计算一个定值，先计算一个字符串的长度避免使用耗时的指令：如左右移指令不能与任何其他指令配对形成流水，阻断了流水线在循环中避免使用条件跳转指令：条件跳转指令会产生不可预见的指令流，容易分支预测失败展开加密循环和函数：减少了条件指令和计算指令，将变量转化为常量，减少流水线的阻断和指令预取的作废限制变量的数量：寄存器有限变量长度与CPU内部寄存器长度相同:否则，需要用别的指令来辅助存取，增加了指令周期数 ...

身份证明协议 两个参与者：证明者，验证者。 采用方式：挑战-响应协议-证明者向验证者通过展示与身份相关的秘密知识，证明自己的身份。 关键：不泄露秘密，且能够抵抗攻击。 双向认证(基于共享密钥)基于整数模p的阶为q的乘法循环群基于公钥的认证 挑战：一方传送给对方一个随机数 响应：对方对这个数进行特定处理再返回 双向认证协议(1) 假设A也是可接受多个会话的通用计算机 考虑当攻击者伪装B的身份 受到反射攻击： 关键：1.攻击者伪装B，建立一个同A的会话；2.攻击者拦截一个A向B的会话；3.攻击者利用A的自动加密，分别套出两个随机数的加密值。 双向认证协议(2) 受到反射攻击： 改进方式：在每个加密消息里加入发送者、接收者在协议中的角色(这样攻击者就无法利用消息2)。 双向认证协议(3)基于HMAC，对HMAC的 攻击难于对对称密钥算法的攻击。 双向认证协议(4)Andrew安全RPC协议。 攻击： 重放攻击：重放4给A；4中没有注明这个会话密钥和此次通信的关联。 类型缺陷攻击：攻击者在第四步重放2给A：虽然攻击者不一定知道RA+1，但猜测nonce ...