m路搜索树
定义
一般定义：一棵 m 路搜索树, 它或者是一棵空树, 或者是满足如下性质的树：
- 根最多有 m 棵子树, 并具有如下的结构：
其中， 是指向子树的指针， ； 是关键码， 。 - 在子树
中所有的关键码都小于 ，且大于 ， 。 - 在子树
中所有的关键码都大于 - 在子树
中的所有关键码都小于 - 子树
也是 路搜索树，
Author: Eric Li
Copyright Notice: All articles on this blog are licensed under CC BY-NC-SA 4.0 unless otherwise stated.
Related Articles
2023-10-18
Block cipher
什么是Block Cipher依赖工作流（Mode of operation），加密定长明文的算法 常见的工作模式ECB 模式按照可加密的长度切分明文之后，直接进行加密因为该模式可能泄露明文之间的关系，可被选择明文攻击不应该使用 CBC 模式每次先把明文和一个随机生成的 做异或，然后放到函数 里面做加密，得到结果 使用 再输入 做加密得到下一段密文 优点 加密是基于概率的 如果函数 满足PRF 安全，那么CBC模式满足CPA安全，即豁免选择明文攻击 缺点 整个加密流程是串行（sequential）的，并且无法进行并行化 OFB 模式首先生成随机的串，经过 加密之后作为输入传给下一个 同时用作密钥给明文做异或操作。 优点 密钥生成的部分是可以预处理的，所以理论上可以更快 函数 不要求是可逆的（因为此时其实只需要正向运用 得到每一次的密文就可以了） 如果函数 是满足 PRF 的，那么加密算法满足 PCA 安全 CTR 模式首先生成一个串 ctr 然后依次使用 作为输入给 获得密钥对对应的明文进行加密 优点 如果函数 是满足 PRF...
2023-10-26
Computational security, CPA security and CCA security
negl 可忽视函数定义一个定义在自然数集上的非负函数 是可忽视的当且仅当对任意的正多项式 都存在一个自然数 使得对于任意的大于 的整数，满足 一个等价的定义： 如果对任意一个 满足 那么就是可忽视的 计算安全The Adeversarial indistinguishable experiment (计算安全实验)对于模式 实验 首先输入参数 攻击者 给出两个等长的明文 然后输出给加密算法 加密算法随机依据安全参数调用生成器 Gen 随机生成密钥 key 然后随机采样 加密 并把密文给到 输出一个 如果 那么 赢得这个实验，即 否则为0 计算安全定义如果上面的实验满足对于任意的PPT时间内的敌手，都有那么这个加密方式是满足 eav 不可区分的。 CPA 安全CPA安全实验 首先运行密钥生成器 Gen 生成一个密钥 key 攻击者有向加密器 Enc 加密长度为 神谕机访问权限，并且可以根据访问得到的明文-密文对决定输出一对消息 ，长度也是 的 加密算法随机生成一个bit，即随机采样 然后输出密文 给到 攻击者 ...
2023-10-26
Message Authentication （消息认证）
Definition of MAC一个消息认证码(Message authentication code or MAC) 算法包括三个部分，即 Gen: 通过输入安全参数，输出一个 key，长度是 Mac: 生成认证码的算法，输入一个 key 和一个消息 然后输出一个tag: Vrfy: 通过输入k,m,t，判断消息是不是有效的(Valid) 如果是，输出1否则输出0 Secure MAC消息认证实验 通过 生成一个key 记为k，k对于攻击者是保密的 攻击者对于标签生成器 MAC 有神谕机的访问权限，可以获取多项式对 记所有的攻击者访问的明文的集合为 攻击者获胜当且仅当 如果攻击者获胜输出1，否则输出0整个实验记作 Plain secure如果一个标签算法是在选择明文攻击下不可伪造的(unforgeable) 当且仅当对于任意PPT的敌手，有 定义的缺陷攻击者可能可以给出以前已经认证过的消息一个新的标签，所以需要定义一个更强的安全性 Strong MACStrong unforgeable 实验 通过 生成一个key...
2023-10-24
PRG and PRF
PRGBackground提出的背景是生成真随机函数的速度太慢了，如果通过CPU温度来生成真随机，那么不能满足加密的速度要求，进而提出一种伪随机方法，来通过比较短的随机种子生成更长的随机串 Definition定义一个多项式 和一个确定的多项式时间的算法 ，对于输入 ， 输出一个长度为 的字符串，如果算法 满足以下性质，那么就称 是满足 PRG 的： 拓展性(Expansion): 对于任意PPT时间范围内的区分器 ,都有一个可忽略函数 使得其中的 均匀且随机，是真随机，而 是独立采样的，注意区分器是看不到 的，也不能看到 具体是什么 但是你构造反证的时候，是能够知道G的特征的，并且需要依据G的特殊性构造 这不是扯淡，因为你只需要证明存在一个D就可以了 ——By Danny 这里的实验分两种情况: 如果是走前半边，那么就是随机等可能从 里面采样出一个 出来，然后传给 输出一个数给判别器。 后半边是随机从 里面采样出一个 ，传给判别器 。 判别器 输出 ...
2023-10-27
Stream cipher
What is it 流密码是一种确定性的算法，通过输入一个随机的种子，输出一串看起来像是随机的比特串 用处是替代PRG，更快地加密 缺点是并没有严格的安全性证明 Definition一个 stream cipher 包括两个部分: Init: GetBits: 此处的 表示状态信息 Init 算法通过输入种子 和一个随机的向量 来输出一个初始状态 GetBits 操作通过获取当前状态输出一个看起来随机的bit 并更新状态为
2023-10-24
Heap
堆的概念堆是满足一下性质的树： 堆中某个节点的值总是不大于或不小于其父节点的值 堆总是一棵完全二叉树 堆的分类根据堆的节点大小关系，分为大根堆和小根堆。大根堆中每个节点都比它的子节点大，小根堆则是每个节点都比它的两个子节点小 大根堆示意图 小根堆示意图 在数组中储存的下标特征在储存堆的时候，一个节点如果下标是 那么它的父节点的下标是 。左子节点的下标是 ，右子节点的下标是 。 堆的操作以下操作均以大根堆为例 堆的插入 每次把一个节点放到数组的最后 依次比较它和其父节点的值，如果父节点更小，那么使用 shift up 操作，把当前节点和父节点交换，然后向上递归 如果父节点已经比此时调整的调整节点大了，调整结束时间复杂度是 级别的。 堆的删除堆只支持删除堆顶端的元素 找到最后一个插入的元素 将最后一个元素和顶部的元素互换 向下递归调整进行 shift down 相关文章[[Leftist heap]]
Announcement
The blog is now under construction