Richardの小小杂货铺 - 数据结构与算法
type: channel
link: https://blog.domineto.top/category/algorithm/
items: RSA 算法学习记录
items: [素性探测] Miller-Rabin 算法
items: 浅谈快速幂及其应用
items: [字符串匹配] KMP算法
items: [字符串匹配] BM算法
items: [字符串匹配] BF算法 && RK算法
items: RC4加密算法学习记录
items: [分组密码] AES加密算法学习记录
items: [分组密码] DES算法学习记录
items: 【数据结构】数组

RSA 算法学习记录
type: item
date: 2019-10-27T03:30:00+00:00
description: 历史1976年，两位美国计算机学家Whitfield Diffie 和 Martin Hellman，提出了一种崭新构思，可以在不直接传递密钥的情况下，完成解密。这被称为"Diffie-Hellman密钥交换算法"。这个算法启发了其他科学家。人们认识到，加密和解密可以使用不同的规则，只要这两种规则之间存在某种对应关系即可，这样就避免了直接传递密钥。这种新的加密模式被称为"非对称加密算法"。非对称加密传输的大致流程如下:A 生成一对密钥 (公钥和私钥)，然后将公钥公开出去，私钥自己保存。B 获取 A 的公钥，用它加密一段信息，再发送给 A。A 收到 B 发送的信息，再用自己的私钥解密。1977年，三位数学家Rivest、Shamir 和 Adleman 设计了一种算法，可以实现非对称加密。这种算法用他们三个人的名字命名，叫做RSA算法。准备在开始 RSA 算法原理之前，我们先来看一点数论的知识：1. 互质关系如果两个正整数，除了1以外，没有其他公因子，我们就称这两个数是互质关系（coprime）。比如，15和32没有公因子，所以它们是互质关系。这说明，不是质数也可以构成互质关系。 关于互质关系，不难得到以下结论： 1. 任意两个质数构成互质关系，比如13和61。 2. 一个数是质数，另一个数只要不是前者的倍数，两者就构成互质关系，比如3和10。 3. 如果两个数之中，较大的那个数是质数，则两者构成互质关系，比如97和57。 4. 1和任意一个自然数是都是互质关系，比如1和99。 5. p是大于1的整数，则p和p-1构成互质关系，比如57和56。 6. p是大于1的奇数，则p和p-2构成互质关系，比如17和15。2. 欧拉函数在看欧拉函数之前我们先看一个问题:任意给定正整数n，请问在小于等于n的正整数之中，有多少个与n构成互质关系？（比如，在1到8之中，有多少个数与8构成互质关系？）计算这个值的方法就叫做欧拉函数，以 $\phi(n)$ 表示。 在 1 到 8 之中，与8形成互质关系的是 1、3、5、7，所以 $\phi(n) = 4$ 。 $ \phi(n) $ 的计算方法并不复杂，但是为了得到最后那个公式，需要一步步讨论。第一种情况如果 $n=1$ ，则 $\phi(1) = 1$ 。因为1与任何数（包括自身）都构成互质关系。第二种情况如果n是质数，则 $\phi(n)=n-1$ 。因为质数与小于它的每一个数，都构成互质关系。比如 5 与1、2、3、4都构成互质关系。第三种情况如果n是质数的某一个次方，即 $n = p^k (p为质数，k为大于等于1的整数)$，则$$ φ(p^k) = p^k - p^{k-1} $$比如 $\phi(8) = \phi(2^3) =2^3 - 2^2 = 8 -4 = 4$。这是因为只有当一个数不包含质数 $p$ ，才可能与 $n$ 互质。而包含质数 $p$ 的数一共有 $p^{(k-1)}$ 个，即 $1×p、2×p、3×p、...、p^{(k-1)}×p$ ，把它们去除，剩下的就是与 $n$ 互质的数。上面的式子还可以写成下面的形式：$$ φ(p^k) = p^k - p^{k-1} = p^k(1 - \frac{1}{p}) $$可以看出，上面的第二种情况是 $k=1$ 时的特例。第四种情况如果 $n$ 可以分解成两个互质的整数之积，$$ n = p1 × p2 $$则$$ φ(n) = φ(p1p2) = φ(p1)φ(p2) $$即积的欧拉函数等于各个因子的欧拉函数之积。比如，$\phi(56)=\phi(8×7)=\phi(8)×\phi(7)=4×6=24$ 。这一条的证明要用到"中国剩余定理"，这里就不展开了，只简单说一下思路：如果 $a$ 与 $p1$ 互质 $(a<p1)$ ，$b$ 与 $p2$ 互质 $(b<p2)$ ，$c$ 与 $p1p2$ 互质 $(c<p1p2)$ ，则 $c$ 与数对 $(a,b)$ 是一一对应关系。由于 $a$ 的值有 $\phi(p1)$ 种可能， $b$ 的值有 $\phi(p2)$ 种可能，则数对 $(a,b)$ 有 $\phi(p1)\phi(p2)$ 种可能，而 $c$ 的值有 $\phi(p1p2)$ 种可能，所以 $\phi(p1p2)$ 就等于 $\phi(p1)\phi(p2)$ 。第五种情况因为任意一个大于1的正整数，都可以写成一系列质数的积。$$ n = p^{k1}_1p^{k2}_2...p^{kr}_r $$根据第4条的结论，得到$$ φ(n) = φ(p^{k1}_1)φ(p^{k2}_2)...φ(p^{kr}_r) $$再根据第3条的结论，得到$$ φ(n) = p^{k1}_1p^{k2}_2...p^…

[素性探测] Miller-Rabin 算法
type: item
date: 2019-10-19T18:05:00+00:00
description: Miller-Rabin 素性检验是一种素数判定法则，利用随机化算法判断一个数是合数还是可能是素数。卡内基梅隆大学的计算机系教授Gary Lee Miller首先提出了基于广义黎曼猜想的确定性算法，由于广义黎曼猜想并没有被证明，其后由以色列耶路撒冷希伯来大学的Michael O. Rabin教授作出修改，提出了不依赖于该假设的随机化算法。算法原理费马小定理Miller-Rabin 算法的依据是费马小定理: 假如 $a$ 是一个整数，$p$ 是一个质数，那么 $a^p$ 是 $p$ 的倍数，可以表示为$$ a^{p-1} \equiv 1(mod \; p) $$证明过程去 Wiki 上面看吧。那是不是当一个数 $p$ 满足任意 $a$ ，使得 $a^{p-1} \equiv 1(mod \; p)$ 成立时，它就一定是素数呢？答案是否定的，因为有些合数也满足费马小定理，比如 卢卡斯-卡米切尔数。虽然说费马小定理有一定概率误判，但如果我们通过一些操作，将这个误判的概率降低至非常小呢？比如对于一个数，我们的算法可以保证 99.99999% 的概率做出正确的判断，那么这个算法不也是很优秀的吗？所以我们有了 Miller-Rabin 算法。二次探测定理Miller-Rabin 算法在费马小定理的基础上加了一个二次探测定理:若 $p$ 是一个奇素数，则由费马小定理可知: 对于任意 $0 < x < p$ ，有 $x^2 \equiv 1(mod \; p)$ 。由此可推出 $x \equiv \pm 1 (mod \; p)$ 。证明如下:$$ x^2 \equiv 1(mod \; p) $$$$ x^2 - 1 \equiv 0(mod \; p) $$$$ (x + 1) (x - 1) \equiv 0(mod \; p) $$由以上式子可知:$$ (x + 1) \equiv 0(mod \; p) 或 (x - 1) \equiv 0(mod \; p) $$即$$ x \equiv \pm 1(mod \; p) $$二次探测定理的前提是这个数满足费马小定理，所以它可以看作是对费马测试的一个补充，减少它误判概率的。同费马小定理，我们这里用的也是它的逆否命题，即不满足二次探测定理的数一定不是素数。算法步骤上面介绍了 Miller-Rabin 算法的两个重要的定理，下面我们来讨论一下它是怎么通过这两个定理来判断一个数是否为素数的。因为 2 是唯一一个偶数素数，所以它需要单独判断。下面所说的素数都是不包括 2 的。我们假设需要判断的数是 $p$ 。由于 $p$ 是一个奇数，所以 $p - 1$ 是一个偶数。那么它就可以被分解为 $2^u * r$ 的形式(其中 $u, r$ 都是整数且 $r$ 为奇数)。为什么要分解成这种形式呢？不急，我们先继续往下看。根据费马小定理，如果 $p$ 是素数，那么一定有 $a^{2^k * t} \equiv 1 (mod \; p)$ 。这时候是不是很明显了？回头看看刚才的二次探测定理，把 $a^{2^k * t}$ 提出一个平方，不就刚好是它的形式吗？所以我们随机选择一个数 $a$ ，计算出 $a^t (mod \; p)$ ，然后让其不断自乘，同时结合二次探测定理进行判断。如果我们自乘后的数模 $p$ 的结果为 1 ，而之前的数模 $p$ 不为 $\pm 1$ ，就表明数 $p$ 是个合数(不满足二次探测定理)如此循环 $k$ 次，最后得到的数就是 $a^{p-1}$ 。如果这个数模 $p$ 的结果不为 1 的话，就表明 $p$ 是合数(不满足费马小定理)至此，我们就完成了一次素性探测了。当然，一次探测的误判率还是很高。所以我们需要多判断几次。正确率网上找的资料显示: 经过独立 $k$ 轮的 Miller-Rabin 算法误判的概率大约为 $1 / 4^k$ 。代码实现素数判断时需要用到快速幂。这个比较简单，不懂的可以看我之前写的快速幂C++ 实现由于我是用 C++ 实现的，大整数类懒得写上去，所以使用的时候要注意越界问题。(其实写好大整数类后把数据类型改一下就行了)Miller-Rabin.h#pragma once typedef long long long_t; inline long_t multiply_mod(const long_t& factor_1, const long_t& factor_2, const long_t& m = 0); inline long_t quick_pow_mod(const long_t& _base, const long_t& _index, const long_t& m = 0); bool MillerRabin(const l…

浅谈快速幂及其应用
type: item
date: 2019-10-19T13:22:00+00:00
description: 快速幂快速幂，二进制取幂（Binary Exponentiation，也称平方法），是一个在 $O(logn)$ 的时间内计算 $a^n$ 的小技巧，而暴力的计算需要 $O(n)$ 的时间。而这个技巧也常常用在非计算的场景，因为它可以应用在任何具有结合律的运算中。算法原理计算 $a^n$ ，最简单的方法就是将 n 个 a 相乘:typedef long long long_t; long_t pow(const long_t& base, const long_t& index) { long_t res = 1; for (auto i = 0; i < index; i++) res *= base; return res; }但如果 $a$ 和 $n$ 的值比较大的时候，这个方法就不是很适用了。不过我们知道:$$ a^{b+c} = a^b · a^c, a^{2b} = a^b · a^b = (a^b)^2 $$这样的话，我们就可以将指数拆成二进制来减少运算次数。举个例子:$$ 3^{13} = 3^{(1101)_2} = (1*3^1) * (0*3^2) * (1*3^4) * (1*3^8) $$任意一个数 $n$ 都有 $log_2(n-1) + 1$ 个二进制位，所以如果我们知道了 $a^1$ , $a^2$ , $a^4$ , ... , $a^{2^{log_2n}}$ , 我们就只需 $O(log n)$ 次计算就可以算出 $a^n$ 。那么问题就转化为了如何求出 $a^1$ , $a^2$ , $a^4$ , ... , $a^{2^{log_2n}}$。这个问题很简单，因为这个数列中任意一个数(除了第一个)都是其前一个数的平方。根据这个很容易得到计算这个数列的时间复杂度也是 $O(log n)$ 。将上述过程说得形式化一些，如果把 $n$ 写作二进制为 $(n_tn_{t-1}...n_1n_0)_2$，那么有：$$ n = n_t2^t + n_{t-1}2^{t-1} + ... + n_12^1 + n_02_0 $$其中 $n_i \in \{0, 1\}$ 。那么就有$$ a^n = a^{n_t2^t + n_{t-1}2^{t-1} + ... + n_12^1 + n_02_0} = a^{n_t2^t} \times a^{n_{t-1}2^{t-1}} \times ... \times a^{n_12^1} \times a^{n_02_0} $$根据上式我们发现，原问题被我们转化成了形式相同的子问题的乘积，并且我们可以在常数时间内从 $2_i$ 项推出 $2_{i+1}$ 项。算法实现递归版本typedef long long long_t; long_t quick_pow(const long_t& base, const long_t& index) { if (index == 0) return 1; const long_t res = quick_pow(base, index / 2); if (index % 2 == 1) return res * res * base; else return res * res; }非递归版本typedef long long long_t; long_t quick_pow(const long_t& _base, const long_t& _index) { long_t index = _index; long_t base = _base; long_t res = 1; while (index != 0) { if ((index & 1) == 1) res *= base; index >>= 1; base *= base; } return res; }两种实现方法理论上计算次数是一样的。但由于递归会有一些额外的开销，所以非递归的版本会快一点。快速幂模我们知道取模不会干涉乘法的运算，所以我们直接在计算的过程中取模即可。typedef long long long_t; long_t quick_pow_mod(const long_t& _base, const long_t& _index, const long_t& m) { long_t index = _index % m; long_t base = _base % m; long_t res = 1; while (index != 0) { if ((index & 1) == 1) res = res * base % m; index >>= 1; base = base * base % m; } return res %…

[字符串匹配] KMP算法
type: item
date: 2019-10-17T07:58:00+00:00
description: 在所有的字符串匹配算法中，效率最高的应该是 BM 算法。但其中最有名的算法应该就是 KMP 算法了。很多时候我们提到字符串匹配，第一个想到的就是 KMP 算法。那么 KMP 算法有什么奇妙的思想呢？本篇文章就来讨论一下 KMP 算法的原理和实现吧。KMP 算法原理KMP 算法全称 Knuth-Morris-Pratt 字符串查找算法， 由Donald Knuth、Vaughan Pratt、James H. Morris三人于1977年联合发表，故取这3人的姓氏命名此算法。在具体讨论 KMP 算法的原理之前，我们先了解两个概念: 好前缀和坏字符。在模式串和主串匹配的时候，我们将不能匹配的那个字符叫做坏字符，已经匹配的字符串叫做好前缀。遇到坏字符的话，我们就需要将模式串向后滑动。在这个过程中，如果模式串与好前缀有重合，那么前几个字符的比较就相当于我们拿好前缀的后缀子串和模式串的前缀子串进行对比: 既然如此，我们是不是可以找到一些规律，让这个过程更加的高效呢？KMP 算法就是在寻找这样一种规律: 在模式串和主串匹配的过程中，如果遇到坏字符，如何根据已匹配的前缀向后滑动最多的位数？我们只需要在好前缀的后缀子串中查找最长可与好前缀的前缀子串匹配的即可。假设最长的可匹配前缀子串{v}的长度为 k，坏字符的位置为 j，那么最大的滑动位数就是 j - k。也就是说，我们每次遇到坏字符的时候，就可以将模式串的位置更新为 k，再继续匹配。可以看到，我们滑动的位数只和模式串有关。那么我们是不是可以通过一些预处理，将不同最长可匹配前缀的位移记录下来，匹配的时候直接滑动呢？这样的话效率就可以提升许多了。我们将这个预处理的数组叫做 next 数组。有些书中也给它取了个名字，叫做失效函数(failure function)。这个数组的下标就是好前缀的长度，里面的值储存的是模式串中每个前缀子串的最长可匹配子串的结尾下标。这个有点不好理解，我们看个例子:模式串: a b a b c a模式串前缀子串(好前缀候选)前缀字符串结尾下标最长可匹配前缀子串结尾下标next值a0-1next[0] = -1ab1-1next[1] = -1aba20next[2] = 0abab31next[3] = 1ababc4-1next[4] = -1有了这个 next 数组后，KMP 算法就很好实现了。我们先假设 next 数组已经求出来了，将 KMP 的框架实现出来:int KMP::find(const string& main_string) { int match = 0; // 好前缀的长度 for (auto i = 0; i < main_string.length(); i++) { while (match > 0 && main_string[i] != ptrn[match]) match = next[match - 1] + 1; if (main_string[i] == ptrn[match]) match++; // 找到匹配的字符串 if (match == ptrn.length()) return i - match + 1; } return -1; }失效函数的计算方法前面已经写好了 KMP 算法的框架，那么剩下的问题就是这个 next 数组是怎么计算出来的了。最简单的方法当然是暴力搜索所有子串，看看有没有和前缀相同的子串。但是这样肯定会影响 KMP 算法的执行效率。那有没有更好的方法呢？KMP 使用的方法非常巧妙，用到了一些动态规划的思想。下面我们就来看看它是怎么实现高效构建 next 数组的。我们假设模式串为 ptrn。如果说 next[i - 1] = k - 1，也就是说子串 ptrn(0, k-1) 是 ptrn(0, i-1) 的最长可匹配前缀子串。然后我们看 ptrn[i] 和 ptrn[k]。如果他们两个相等的话，那么毫无疑问 ptrn(0, k) 就是 ptrn(0, i) 的最长可匹配前缀子串。所以 next[i] = k。那么如果 ptrn[i] 和 ptrn[k] 不相等呢？我们就不可以简单的通过 next[i - 1] 计算出 next[i] 了。这个时候该怎么办呢？我们假设子串 ptrn(r, i) 为子串 ptrn(0, i) 的最长可匹配后缀子串，那么 ptrn(r, i-1) 一定是 ptrn(0, i-1) 的可匹配后缀子串，但不一定是最长的。所以如果 ptrn[i] != ptrn[k] 的话，我们就可以去找 ptrn(0, i-1) 的次长可匹配后缀子串 ptrn(x, i-1) 对应的前缀子串 ptrn(0, i - 1 - x)。如果 ptrn[i - x] == ptrn[i]，那么 p…

[字符串匹配] BM算法
type: item
date: 2019-10-14T05:24:00+00:00
description: BM 算法全称 Boyer-Moore 算法。它是一种非常高效的字符串匹配算法，有实验统计，它的性能是著名的KMP 算法的 3 到 4 倍。下面我们来讨论一下它是如何实现这么高的效率的。BM 算法核心思想我们把模式串和主串的匹配过程，看作模式串在主串中不停地往后滑动。当遇到不匹配的字符时，BF 算法和 RK 算法的做法是，模式串往后滑动一位，然后从模式串的第一个字符开始重新匹配。举个例子:主串: a b c d s a b d f n 模式串: a b d 滑动后: a b d在这个例子里，主串中的 'c'，在模式串中是不存在的，所以，模式串向后滑动的时候，只要 'c' 与模式串有重合，肯定无法匹配。所以，我们可以一次性把模式串往后多滑动几位，把模式串移动到 'c' 的后面:主串: a b c d s a b d f n 模式串: a b d 滑动后: a b d根据这个例子，很容易想到: 如果我们有办法找出一种规律，每次让模式串多向后滑动几位，那么匹配的效率不久大幅提升了吗？本篇文章所探讨的 BM 算法，本质上其实就是在寻找这种规律。借助这种规律，在模式串与主串匹配的过程中，当模式串和主串某个字符不匹配的时候，能够跳过一些肯定不会匹配的情况，将模式串往后多滑动几位。BM 算法原理分析BM 算法包含两部分，分别是坏字符规则（bad character rule）和好后缀规则（good suffix shift）。我们下面依次来探讨一下，这两个规则都是怎么工作的。坏字符规则之前学习的 BF 算法和 RK 算法在匹配的过程中，都是按模式串的下标从小到大的顺序，依次与主串中的字符进行匹配的。这种匹配顺序比较符合我们的思维习惯，而 BM 算法的匹配顺序比较特别，它是按照模式串下标从大到小的顺序，倒着匹配的:主串: a b c d s a b d f n 模式串: a b d 匹配顺序: 1 2 3我们从模式串的末尾往前倒着匹配，直到我们发现某个字符没法匹配的时候。我们把这个没有匹配的字符叫作坏字符（主串中的字符）。主串: a b c d s a b d f n 模式串: a b d这里面主串中的 'c' 就是坏字符。我们拿坏字符 'c' 在模式串中查找，发现模式串中并不存在这个字符，也就是说，字符 'c' 与模式串中的任何字符都不可能匹配。这个时候，我们可以将模式串直接往后滑动三位，将模式串滑动到 'c' 后面的位置，再从模式串的末尾字符开始比较。主串: a b c d s a b d f n 模式串: a b d 滑动后: a b d这是我们发现：模式串的最后一位 'd' 还是与主串中的字符 'a' 不匹配。那么我们还能向后滑动三位吗？答案是不行。我们很容易看出：坏字符 a 在模式串中是存在的，模式串中下标是 0 的位置也是字符 a。这种情况下，我们可以将模式串往后滑动两位，让两个 a 上下对齐，然后再从模式串的末尾字符开始，重新匹配。主串: a b c d s a b d f n 模式串: a b d 滑动后: a b d那么新的问题来了：第一次出现坏字符的时候，我们向后滑动了三位; 第二次出现坏字符的时候我们却只向后滑动了两位。那么这其中有没有什么规律呢？当发生不匹配的时候，我们把坏字符对应的模式串中的字符下标记作 si。如果坏字符在模式串中存在，我们把这个坏字符在模式串中的下标记作 xi。如果不存在，我们把 xi 记作 -1。那模式串往后移动的位数就等于 si-xi。!> 这里说的下标，都是字符在模式串的下标主串: a b c d s a b d f n 模式串: a b d xi=0 si=2这里需要说明一下：如果坏字符在模式串里多处出现，那我们在计算 xi 的时候，选择最靠后的那个，因为这样不会让模式串滑动过多，导致本来可能匹配的情况被滑动略过。利用坏字符规则，BM 算法在最好情况下的时间复杂度非常低，是 O(n/m)。比如，主串是 aaabaaabaaabaaab，模式串是 aaaa。每次比对，模式串都可以直接后移四位，所以，匹配具有类似特点的模式串和主串的时候，BM 算法非常高效。不过，单纯使用坏字符规则还是不够的。因为根据 si-xi 计算出来的移动位数，有可能是负数，比如主串是 aaaaaaaaaaaaaaaa，模式串是 baaa。不但不会向后滑动模式串，还有可能倒退。所以，BM 算法还需要用到“好后缀规则”。好后缀规则好后缀规则和坏字符规则思路很相似。举个例子:主串: a b c d s a d b b c c a b d c d 模式串: a b c d a b c 可以看到：模式串和主串有 2 个字符是匹配的，倒数第 3 个字符发生了不匹配的情况。这个时候该如何滑动模式串呢？当然，我们还可以利用坏字符规则来计…

[字符串匹配] BF算法 && RK算法
type: item
date: 2019-10-12T05:04:00+00:00
description: 字符串匹配的算法有很多，本篇文章主要介绍两种比较简单的算法：BF算法和RK算法。准备在开始讲解算法之前，我们先了解两个概念：主串和模式串。这俩概念很好理解，我举个例子你就懂了：我们在字符串 A 中查找字符串 B，那字符串 A 就是主串，字符串 B 就是模式串。BF算法BF 算法的全称为 Brute Force 算法，中文叫做暴力匹配算法，也叫朴素匹配算法。顾名思义，这个算法简单暴力。但同样的，算法效率也不是很高。算法思想既然是简单暴力的算法，BF算法的思想也可以用一句话概括：在主串中，依次遍历起始位置为0，1，2，……，n - m 且长度为 m 的 n - m + 1 个子串，看是否有和模式串相同的子串。(其中 n 为主串的长度，m 为模式串的长度)代码实现这里放一份我顺手写的代码吧(仅供参考)：/** * \brief BF算法 * \param main_string 主串 * \param pattern_string 模式串 * \return 主串中是否存在模式串 */ int BF_find(const string& main_string, const string& pattern_string) { const int len = main_string.length() - pattern_string.length(); for (auto i = 0; i <= len; i++) { // 找到和模式串第一个字符相同的 if (main_string[i] == pattern_string[0]) { bool same = true; // 判断剩下的是否相同 for (auto j = 0; j < pattern_string.length(); j++) { if (main_string[i + j] != pattern_string[j]) { same = false; break; } } // 相同则返回偏移量 if (same) return i; } } return -1; }可以很容易看出：在极端情况下，比如在 aaa……aaaa 这样一个字符串中匹配 aaab 这样的字符串，我们就需要匹配 n - m + 1 次，每次匹配 m 个字符。所以该算法的最坏时间复杂度就是 O(m*n)。RK算法RK算法全称叫做 Rabin-Karp算法。是由 Rabin 和 Karp 共同提出的一个算法。RK算法是对BF算法的一个改进：在BF算法中，每一个字符都需要进行比较，并且当我们发现首字符匹配时仍然需要比较剩余的所有字符。而在RK算法中，就尝试只进行一次比较来判定两者是否相等。那么它是如何做到一次比较就判断相等呢？让我们来看看它是怎么做的：算法思想BF算法在检查子串和模板串是否相同的时候是逐字符比对的，这就导致了它的时间复杂度比较高。但如果我们稍微改造一下对比的方法，引入哈希算法，复杂度就会降低许多。所以RK算法的思路如下：将模式串的 hash 值跟主串中的每一个长度为 m 的子串的 hash 值比较。如果不同，则它们肯定不相等；如果相同，由于哈希冲突存在，再逐字符的比较。 因为哈希后是一个数字，数字之间的比较是非常快的，所以模式串和子串的比较就快了很多。不过虽然模式串和子串的比较变快了，但是计算哈希需要遍历子串，所以整体时间复杂度似乎还是不变。这个如何解决呢？这就需要哈希函数设计的有技巧了。我们可以假设我们要匹配的字符串只包含 K 个字符，那么我们就可以将其转化为一个 K 进制数，然后转化为十进制作为子串的哈希值。举个小例子：假设我们要处理的的字符串只包含 a-z 这 26 个小写字母，那我们就用26进制来表示这个字符串。a 表示 0，b 表示 1，以此类推。比如字符串 "cba" 进行运算的过程为："cba" = 'c' 26 26 + 'b' * 26 + 'a' = 2 * 26 * 26 + 1 * 26 + 0 = 1353时间复杂度上面说 RK 算法比 BF 算法更快，那我们就来分析一下 RK算法的时间复杂度吧：计算哈希值可以通过一些方法，比如查表，快速的算出哈希值，复杂度约为 O(n)模式串和子串哈希值比较的时间复杂度为 O(1)总共需比较 n - m + 1 次所以整体的时间复杂度大约为 O(n)。数据溢出我们刚才使用的 K 进制的方法是没有散列冲突的。但是有一个问题，如果字符串过长，很可能超过计算机中整型数据的最大值的。这里哦我们可以通过允许一些散列冲突，让转换后的数可以存在整型数据中。比如不将字符串当成一个 K 进制数，而是将每个字符转换为整型数后再相加。当然方法不止这一种，这个方法只是举例。散列冲突那么新的问题来了，上面说了我们会有一些散列冲突的情况发生，所以…

RC4加密算法学习记录
type: item
date: 2019-10-08T13:39:00+00:00
description: RC4于1987年提出，和DES算法一样，是一种对称加密算法，也就是说使用的密钥为单钥（或称为私钥）。但不同于DES的是，RC4不是对明文进行分组处理，而是字节流的方式依次加密明文中的每一个字节，解密的时候也是依次对密文中的每一个字节进行解密。算法特点RC4算法的特点是算法简单，运行速度快，而且密钥长度是可变的，可变范围为1-256字节(8-2048比特)，在如今技术支持的前提下，当密钥长度为128比特时，用暴力法搜索密钥已经不太可行，所以可以预见RC4的密钥范围任然可以在今后相当长的时间里抵御暴力搜索密钥的攻击。算法原理转载一张图片(图片来源): 前提在讲 RC4 的算法之前，先看几个里面的关键变量：密钥流：RC4算法的关键是根据明文和密钥生成相应的密钥流，密钥流的长度和明文的长度是对应的;状态向量S：长度为256，S[0],S[1]....S[255]。每个单元都是一个字节，算法运行的任何时候，S都包括0-255的8比特数的排列组合，只不过值的位置发生了变换;临时向量T：长度也为256，每个单元也是一个字节。如果密钥的长度是256字节，就直接把密钥的值赋给T，否则，循环将密钥的每个字节赋给T;密钥K：长度为1-256字节，注意密钥的长度与明文长度、密钥流的长度没有必然关系，通常密钥的长度取16字节（128比特）。原理RC4 的原理分为三步:1. 初始化 S 和 T伪代码如下:for i=0 to 255 do S[i]=i; T[i]=K[ i mod key_len ];2. 初始化排列 S伪代码如下:j=0; for i=0 to 255 do j= ( j + S[i] + T[i])mod256; swap(S[i], S[j]);3. 产生密钥流伪代码如下:i, j=0; for r=0 to len do //r为明文长度，r字节 i=(i + 1) mod 256; j=(j + S[i])mod 256; swap(S[i], S[j]); t=(S[i] + S[j]) mod 256; k[r] = S[t];C++ 实现RC4.h#pragma once #include <fstream> #include <string> #include <vector> using std::string; using std::vector; class RC4 { private: string key; // 可变长度密钥 string key_stream; // 密钥流 unsigned char S[256]; // 状态向量 S unsigned char T[256]; // 临时向量 T void initial(); // 初始化 void rangeS(); // S 的初始置换 void key_stream_generate(int len); public: RC4(); ~RC4(); RC4(const string& k); bool set_key(const string& k); string encrypt(const string& plain); string decrypt(const string& cipher); void encrypt(string plain_path, string cipher_path); void decrypt(string cipher_path, string plain_path); }; /** * \brief 工具函数, string 转换为 hex */ string string2hex(string in) { string res; for (auto i : in) { int tmp = static_cast<int>(i); int high = (tmp & 0xf0) >> 4; int low = (tmp & 0x0f); res += (high < 10 ? '0' + high : 'a' + high - 10); res += (low < 10 ? '0' + low : 'a' + low - 10); } return res; }RC4.cpp#include "RC4.h" /** * \brief 初始化状态向量S和临时向量T */ void RC4::initial() { // 清空密钥流 key_stream.clear(); for (auto i = 0; i < 256; i++) { S[i] = i; T[i] = key[i % key.length()]; } } /** * \brief 初始排列状态向量S */ void RC4::rangeS…

[分组密码] AES加密算法学习记录
type: item
date: 2019-10-04T06:41:00+00:00
description: 1. AES 介绍AES（高级加密标准，Advanced Encryption Standard），在密码学中又称 Rijndael 加密法，是美国联邦政府采用的一种分组加密标准。这个标准用来替代原先的 DES，目前已经广为全世界所使用，成为对称密钥算法中最流行的算法之一。鉴于这三种模式的算法在本质上没有区别，所以本文主要介绍 AES-128 (数据分组为16字节，秘钥长度为16字节，加密轮数为10轮) ，并给出 ECB 模式下的 C++ 实现。2. AES算法流程AES算法主要可以分为秘钥扩展、字节替换、行移位、列混合和轮秘钥加这5个步骤。秘钥扩展（KeyExpansions：给定的初始秘钥一般比较短，比如16字节，而算法如果进行10轮运算的话就需要16x(10+1)字节长度的秘钥，需要对原始秘钥进行秘钥扩展。字节替换（SubBytes）：一个非线性的替换步骤，根据查表把一个字节替换为另一个字节。行移位（ShiftRows）：将数据矩阵的每一行循环移位一定长度。列混淆（MixColumns）：将数据矩阵乘以一个固定的矩阵，增加混淆程度。轮秘钥加（AddRoundKey）:将数据矩阵与秘钥矩阵进行异或操作。具体的加解密流程可以见下图: 3. AES 算法步骤3.1 前提AES 加密都是以一个 4x4 的状态矩阵为单位加密的。例如，将一串十六字节的字符串 0123456789abcdef 放入状态矩阵如下:$$ \left[ \begin{matrix} 0 & 4 & 8 & c\\ 1 & 5 & 9 & d\\ 2 & 6 & a & e\\ 3 & 7 & b & f \end{matrix} \right] $$!> 注意这里的排列的顺序是竖排而不是横排3.2 密钥扩展根据上面的流程图可以看出，AES 原始密钥是 16 个字节的， 而进行一次 AES 加密需要 11 个矩阵大小的密钥，所以多出来的密钥肯定要通过一系列运算求出来。下面我们来讨论一下这些密钥是怎么来的。首先，先给出 AES 密钥扩展的图解: 由图可以看到，我们将密钥矩阵中每一列的 4 个字节都记为一个 bitset<32> w，这样就得到了 w[0] - w[3]。得到了 w[0] - w[3] 之后，就可以根据它们计算出剩下的密钥了。计算方式如下:W(4i) = G(W(4i-1)) xor W(4i-4) W(4i+1) = W(4i) xor W(4i-3) W(4i+2) = W(4i+1) xor W(4i-2) W(4i+3) = W(4i+2) xor W(4i-1) (其中 i = 1, 2, 3, …… , 10)具体的流程这时候已经明确了。剩下的问题就是这个混淆函数 G 了。那么它做了什么呢？这个 G 函数做了以下几件事:RotWord 循环左移: 将输入循环左移一个字节。如 输入0x12345678，输出0x34567812。SubWord 字节替代: S 盒替代。这个可以参考下面的字节替代。Rcon 轮常量异或: 将输入的第一个字节和轮常量 Rcon 异或。这个 Rcon 数组是通过计算算出来的，不过它不会变，所以可以直接当常量数组用。想了解它的算法可以参考这里流程大概说完了，下面放出密钥扩展的代码实现吧:// 轮常数，密钥扩展中用到。（AES-128只需要10轮） byte Rcon[10] = { 0x01, 0x02, 0x04, 0x08, 0x10, 0x20, 0x40, 0x80, 0x1b, 0x36 }; /** * \brief 密钥扩展, 生成轮密钥 */ void AES::keyExpansion() { // 最开始就是初始的 key for (auto i = 0; i < 4; i++) for (auto j = 0; j < 4; j++) subKey[0][i][j] = key[i][j]; // 计算轮密钥 for (auto round = 1; round <= 10; round++) { byte last[4]; // 前一个密钥 for (auto i = 0; i < 4; i++) last[i] = subKey[round - 1][i][3]; for (auto i = 0; i < 4; i++) { // 每轮密钥的前 4 byte 要进行自混淆 if (i == 0) G(last, round - 1); // 计算轮密钥 for (auto j = 0; j < 4; j++) subKey[round][j][i] = last[j] ^ subKey[round - 1][j][i]; for (auto j = 0; j < 4; j++) last…

[分组密码] DES算法学习记录
type: item
date: 2019-09-16T01:16:00+00:00
description: 这学期选了一门课: 计算机安全导论。据说主讲密码学，所以就先学习一下相关的知识啦~ 这几天学的是 DES算法。初学只写了 ECB 模式下的 DES。其他的等以后再说吧 XD1. 算法原理1.1 什么是 DES ?数据加密标准（英语：Data Encryption Standard，缩写为 DES）是一种对称密钥加密块密码算法，1976年被美国联邦政府的国家标准局确定为联邦资料处理标准（FIPS），随后在国际上广泛流传开来。它基于使用56位密钥的对称算法。这个算法因为包含一些机密设计元素，相对短的密钥长度以及怀疑内含美国国家安全局（NSA）的后门而在开始时有争议，DES因此受到了强烈的学院派式的审查，并以此推动了现代的块密码及其密码分析的发展。——Wikipedia1.2 算法流程DES 是一个分组加密算法，典型的 DES 以64位为分组对数据加密，加密和解密用的是同一个算法。其大致加密流程如下图:下面我来慢慢分析这些都是什么意思吧~2. 算法实现2.1 IP置换IP置换目的是将输入的64位数据块按位重新组合，并把输出分为L0、R0两部分，每部分各长32位。置换规则如下表所示：// 初始置换表 const int IP[64] = { 58, 50, 42, 34, 26, 18, 10, 2, 60, 52, 44, 36, 28, 20, 12, 4, 62, 54, 46, 38, 30, 22, 14, 6, 64, 56, 48, 40, 32, 24, 16, 8, 57, 49, 41, 33, 25, 17, 9, 1, 59, 51, 43, 35, 27, 19, 11, 3, 61, 53, 45, 37, 29, 21, 13, 5, 63, 55, 47, 39, 31, 23, 15, 7 }; 表中的数字代表新数据中此位置的数据在原数据中的位置，即原数据块的第58位放到新数据的第1位，第50位放到第2位，……依此类推。置换后的数据分为 L0 和 R0 两部分， L0 为新数据的左32位，R0 为新数据的右32位。!> 要注意一点，位数是从左边开始数的，即最0x0000 0080 0000 0002最左边的位为1，最右边的位为64。2.2 生成子密钥从流程图中可以看出，我们在进行下一步加密的时候需要一个密钥 K，且之后的每一轮都需要密钥。我们知道 DES 需要输入一个64位的密钥，那剩余的密钥就肯定是从这个密钥变化来的。下面就讨论一下这些子密钥是怎么来的。2.2.1 去除奇偶校验位不考虑每个字节的第8位，将 DES 的密钥由64位减至56位，每个字节的第8位作为奇偶校验位。产生的56位密钥由下表生成（注意表中没有8,16,24，32,40,48,56和64这8位）： // 密钥置换表，将64位密钥变成56位 const int PC_1[56] = { 57, 49, 41, 33, 25, 17, 9, 1, 58, 50, 42, 34, 26, 18, 10, 2, 59, 51, 43, 35, 27, 19, 11, 3, 60, 52, 44, 36, 63, 55, 47, 39, 31, 23, 15, 7, 62, 54, 46, 38, 30, 22, 14, 6, 61, 53, 45, 37, 29, 21, 13, 5, 28, 20, 12, 4 };2.2.2 循环左移在DES的每一轮中，从56位密钥产生出不同的48位子密钥，确定这些子密钥的方式如下：将56位的密钥分成两部分，每部分28位。根据轮数，这两部分分别循环左移1位或2位。每轮移动的位数如下表：// 每轮左移的位数 const int shiftBits[16] = { 1, 1, 2, 2, 2, 2, 2, 2, 1, 2, 2, 2, 2, 2, 2, 1 };2.2.3 压缩置换移动后，从56位中选出48位。这个过程中，既置换了每位的顺序，又选择了子密钥，因此称为压缩置换。压缩置换规则如下表（注意表中没有9，18，22，25，35，38，43和54这8位）：// 压缩置换，将56位密钥压缩成48位子密钥 const int PC_2[48] = { 14, 17, 11, 24, 1, 5, 3, 28, 15, 6, 21, 10, 23, 19, 12, 4, 26, 8, 16, 7, 27, 20, 13, 2, 41, 52, 31, 37, 47, 55, 30, 40, 51, 45, 33, 48, 44, 49, 39, 56, 34, 53, 46, 42, 50, 36, 29, 32 };至此，新的密钥就已经计算出来了。按照这个方法进行16轮，就可以得到16个子密钥。2.3 加密处…

【数据结构】数组
type: item
date: 2019-07-17T12:22:00+00:00
description: 提到数组，大部分人应该都不会陌生。我们都知道，基本所有的编程语言中都有数组这个数据类型，同时数组也是一个最基本的数据结构。那么现在有一些问题：数组的特性是什么？它是如何实现这个特性的？数组下标为什么要从0开始？如果答不上来的话，就请往下看吧 :D1. 数组的定义数组是个什么东西想必大家都很清楚。这里我就放上专业的定义吧：数组(Array)是一种线性表数据结构。它用一组连续的内存空间，来储存一组具有类型的数据。这个定义里面有一些关键词，下面我来解释一下这些关键词的意思吧。2. 数组的特性线性表线性表顾名思义，就是一种将数据排成一条线的数据结构。比如链表，数组。对于线性表中的任意一个数据，它们都只有前，后两个方向。(图是随手画的看看就好了 XD)与线性表相对应的就是非线性表。如 二叉树，堆这类数据结构。对于非线性表而言，数据之间并不是只有简单的前后关系。如下图：可以看到里面节点的关系并不是简单地前后可以表示的。连续的内存空间和相同类型的数据这两个性质很重要，因为它们让数组有了一个“杀手锏”般的特性：随机访问。平时我们使用下标来访问数组的元素就是利用了数组的随机访问特性。但是有利必有弊，随机访问带来的弊端就是数组需要连续的内存，同时为了保证这个特性，数组的很多操作变得十分低效。比如在数组中插入和删除，就要对目标位置以后的所有数据进行数据搬移。那么数组是如何实现这个根据下标随机访问的特性的呢？我们开一个大小为10的数组 int *a = new int [10];根据上图可以看出计算机分配了一片连续的空间 1000~1039 (十进制) 给a[10]。其中1000为首地址。如果我们想要访问a[5]的内容，计算机会用下列公式计算出该元素的内存地址：a[i]_address = a[0]_adress + i * type_size其中 type_size 为数组中每个元素所占的大小。我们开的是 int 型数组，所以 type_size = 4 。至此a[5] 的地址就计算出来了，为 1020~1023 。数组的随机访问特性就是这么实现的。3. 数组操作的时间复杂度增加与删除前面说了，数组在进行增加或删除的时候需要对后面的数据进行搬移。按照之前的复杂度分析，最好的情况是在数组末尾增加或删除，此时复杂度是 O(1)。最坏的情况是在数组头进行增删，此时的复杂度是 O(n)。均摊下来，忽略系数之类的，数组的增加和删除的平均时间复杂度为 O(n)。但是，在某些情况下，数组增删的时间复杂度是可以降低的。对于增加来说，如果对数组的有序没有要求的话，可以将需插入的数插入到数组尾部，再将其和需插入位置的数进行交换。由于数组随机访问的特性，时间复杂度就降低到了O(1)。对于删除来说，如果有一段连续的数据要被删除，我们可以先标记其为“可删除的数据”，在空间不够时就可以一次性释放掉。举个例子：我们现在有一个数组 a[10]，里面有五个数据：a, b, c, d, e。如果我们需要依次删除a, b, c的话，就会触发三次数据搬移。如果我们标记了它们是可删除的，在空间不够用的时候再进行删除，就可以减少两次数据搬移。这样可以节省很多时间。查找如果被问到数组和链表的区别的话，我想很多人会说：“数组适合查找，而链表适合插入和删除，它们的时间复杂度都是O(1)”吧？(我原先也是这么认为的 XD) 但事实上，即使是一个有序的数组，利用二分查找也需要 O(nlogn) 的时间复杂度。所以，正确的说法应该是：数组支持随机访问，其利用下标随机访问的时间复杂度是O(1)。4. 数组越界问题在谈这个问题之前我们先来看一段代码吧：#include <cstdio> int main() { int i = 0; int a[3] = {0}; for (i = 0;i <= 3; i++) { arr[i] = 0; printf("Hello world!\n"); } return 0; }发现问题了吗？这段代码会在屏幕上无限输出 "Hello world!" 。这是为什么呢？对于C语言来说，只要访问的不是受限的内存，都是合法的。数组的本质就是一段连续的内存，只要计算出来是合法的地址就可以访问。所以数组访问越界在C中是一种“未决”的行为。这就导致数组越界会发生一些神奇的逻辑错误，甚至对电脑系统造成损害。5. 随便写写开头有一个问题：数组下标为什么以0开始？我去查了些资料，大概有以下几点：数组下标本质上是偏移量，而数组首地址就是数组第一个元素的内存地址，此时偏移量为0。数组下标从1开始的话，会增加一个 “-1”的操作，导致多一次运算。C语言最开始的标准数组下标就是从0开始的，而后面的语言基本都有参照C语言，所以数组下标都从0开始了。