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 long_t& p, const int& times);Miller-Rabin.cpp#include "Miller-Rabin.h" #include <ctime> #include <cstdlib> /** * \brief 模意义下的大整数乘法 * \param factor_1 因数 1 * \param factor_2 因数 2 * \param m 取模, 值为0表示不取模 */ inline long_t multiply_mod(const long_t& factor_1, const long_t& factor_2, const long_t& m) { long_t a = factor_1 % m; long_t b = factor_2 % m; long_t res = 0; // 和快速幂模一样的原理 while (b != 0) { if ((b & 1) == 1) res = (m == 0 ? res + a : (res + a) % m); a <<= 1; if (m != 0 && a > m) a %= m; b >>= 1; } return res; } /** * \brief 一个简单的快速幂模 * \param _base 底数 * \param _index 指数 * \param m 取模, 防溢出, 值为0表示不取模 */ inline long_t quick_pow_mod(const long_t& _base, const long_t& _index, const long_t& m) { long_t index = _index; long_t base = _base; long_t res = 1; while (index != 0) { if ((index & 1) == 1) res = multiply_mod(res, base, m); index >>= 1; base = multiply_mod(base, base, m); } return (m == 0 ? res : res % m); } /** * \brief Miller-Rabin 素性探测 * \param p 需要判断的数 * \param times 判断次数, 减少误差用 */ bool MillerRabin(const long_t& p, const int& times) { // 判断特殊情况 if (p == 2) return true; if (p < 2 || p % 2 == 0) return false; long_t r = p - 1; while (r % 2 == 0) r /= 2; // 播种子 srand(static_cast<unsigned>(time(nullptr))); for (auto i = 0; i < times; i++) { long_t a = rand() % (p - 1) + 1; long_t x = quick_pow_mod(a, r, p); for (auto u = 1; u * r < p; u *= 2) { const long_t tmp = multiply_mod(x, x, p); // 不满足二次探测定理 if (tmp == 1 && x != 1 && x != p - 1) return false; x = tmp; } if (x != 1) return false; } return true; }Python 实现import random def MillerRabin(num, times): if num == 2: return True if num < 2 or num % 2 == 0: return False r = num - 1 k = 0 while r % 2 == 0: r /= 2 k += 1 for t in range(times): a = random.randrange(2, num - 1) x = pow(a, r, num) for i in range(1, k + 1): tmp = x * x % num if tmp == 1 and x != 1 and x != num - 1: return False x = tmp if x != 1: return False return True def isPrime(num): if num<2: return False lowPrimes = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 103, 107, 109, 113, 127, 131, 137, 139, 149, 151, 157, 163, 167, 173, 179, 181, 191, 193, 197, 199, 211, 223, 227, 229, 233, 239, 241, 251, 257, 263, 269, 271, 277, 281, 283, 293, 307, 311, 313, 317, 331, 337, 347, 349, 353, 359, 367, 373, 379, 383, 389, 397, 401, 409, 419, 421, 431, 433, 439, 443, 449, 457, 461, 463, 467, 479, 487, 491, 499, 503, 509, 521, 523, 541, 547, 557, 563, 569, 571, 577, 587, 593, 599, 601, 607, 613, 617, 619, 631, 641, 643, 647, 653, 659, 661, 673, 677, 683, 691, 701, 709, 719, 727, 733, 739, 743, 751, 757, 761, 769, 773, 787, 797, 809, 811, 821, 823, 827, 829, 839, 853, 857, 859, 863, 877, 881, 883, 887, 907, 911, 919, 929, 937, 941, 947, 953, 967, 971, 977, 983, 991, 997] if num in lowPrimes: return True for prime in lowPrimes: if num % prime==0: return False return MillerRabin(num, 8) if __name__ == '__main__': while True: num = input() print (isPrime(int(num)))Referrerhttps://www.cnblogs.com/zwfymqz/p/8150969.html#_labelTop https://en.wikipedia.org/wiki/Fermat%27s_little_theorem https://en.wikipedia.org/wiki/Miller%E2%80%93Rabin_primality_test https://blog.csdn.net/alps1992/article/details/51588971
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 个字符发生了不匹配的情况。这个时候该如何滑动模式串呢？当然，我们还可以利用坏字符规则来计算模式串的滑动位数，不过，我们也可以使用好后缀处理规则。两种规则如何抉择放在后面讲吧，这里我们先看看好后缀规则是如何做的: 我们把已经匹配的 bc 叫作好后缀，记作{u}。我们拿它在模式串中查找，如果找到了另一个跟{u}相匹配的子串{u*}，那我们就将模式串滑动到子串{u*}与主串中{u}对齐的位置。主串: a b c d s a d b b c c a b d c d 模式串: a b c d a b c 滑动后: a b c d a b c如果在模式串中找不到另一个等于{u}的子串，我们就直接将模式串，滑动到主串中{u}的后面，因为之前的任何一次往后滑动，都没有匹配主串中{u}的情况。主串: a b c d s a d b b c c a b d c d 模式串: a d c d a b c 滑动后: a d c d a b c不过直接将模式串向后滑动到主串中{u}的后面就可以了吗？举个例子：主串: a b c d s a d b b a d c d a b a d 模式串: a d c d a b a 这时候如果我们将模式串直接滑到 {u} 之后的位置，我们就会错过匹配的情况:主串: a b c d s a d b b a d c d a b a d 模式串: a d c d a b a 过度滑动: a d c d a b a 合理滑动: a d c d a b a所以，针对这种情况，我们不仅要看好后缀在模式串中，是否有另一个匹配的子串，我们还要考察好后缀的后缀子串，是否存在跟模式串的前缀子串匹配的。 所谓某个字符串 s 的后缀子串，就是最后一个字符跟 s 对齐的子串，比如 abc 的后缀子串就包括 c, bc。所谓前缀子串，就是起始字符跟 s 对齐的子串，比如 abc 的前缀子串有 a，ab。我们从好后缀的后缀子串中，找一个最长的并且能跟模式串的前缀子串匹配的，假设是{v}，然后将模式串滑动到前缀对齐的情况。那么坏字符规则和好后缀规则都分析的差不多了，下面就是如何实现的问题了。BM算法代码实现BM算法类我将这个算法封装成了一个类。所以先放出类的声明:class BM { private: string ptrn; // 模式串 int skip[SIZE] = {}; // 坏字符表 vector<int> suffix; // 好后缀表 vector<bool> prefix; //前缀子串 void generate_skip(); // 建立坏字符表 void generate_suffix(); // 建立好后缀表 int shift_by_good_suffix(const int& begin); public: BM(); explicit BM(const string& p); ~BM(); void set_pattern(const string& p); int find(const string& main_string, const int& pos = 0); };坏字符规则实现“坏字符规则”本身不难理解。当遇到坏字符时，要计算往后移动的位数 si-xi，其中 xi 的计算是重点，我们如何求得 xi 呢？或者说，如何查找坏字符在模式串中出现的位置呢？如果每次都要遍历一遍查找 xi 的话，那算法的效率就会变得很低。所以我们可以事先进行一个预处理，建立一个哈希表来记录坏字符对应的 xi。这里我建立一个最简单的哈希表，也就是将 256 个字符的位移都记录下来:/** * \brief 生成坏字符预处理表 */ void BM::generate_skip() { // 初始化坏字符表为模式串的长度 std::fill(skip, skip + SIZE, -1); // 从小到大的顺序可以在同一字符多次出现的时候以最靠右的那个字符到尾部距离为最终的距离 for (auto i = 0; i < ptrn.length(); i++) skip[ptrn[i]] = i; }好后缀规则实现好后缀规则应该是 BM 算法中最难理解的部分了。我们先回忆一下好后缀规则的核心思想:在模式串中，查找跟好后缀匹配的另一个子串；在好后缀的后缀子串中，查找最长的、能跟模式串前缀子串匹配的后缀子串；如果不考虑效率的话，这两部分都可以用暴力的方法解决。但如果不考虑效率，我为什么不用 BF 算法呢？所以我们需要一些技巧来完成这两个操作。因为好后缀也是模式串本身的后缀子串，所以，我们可以在模式串和主串正式匹配之前，通过预处理模式串，预先计算好模式串的每个后缀子串，对应的另一个可匹配子串的位置。下面我们就来讨论一下这个预处理如何实现。首先，如何表示模式串中不同后缀的子串呢？我们很容易看出，同一模式串的后缀子串最后一个字符的位置是固定的，所以我们可以用长度来作为一个后缀子串的标识:模式串：a s d a s d 后缀子串长度d1s d2a s d3d a s d4s d a s d5现在，我们要引入最关键的变量 suffix 数组。suffix 数组的下标 k，表示后缀子串的长度，下标对应的数组值存储的是，在模式串中跟好后缀{u}相匹配的子串{u*}的起始下标值。举个例子:模式串： a s d a s d编号: 0 1 2 3 4 5后缀子串长度suffixd1suffix[1] = 2s d2suffix[2] = 1a s d3suffix[3] = 0d a s d4suffix[4] = -1s d a s d5suffix[5] = -1那么这样是否就可以实现好后缀规则了呢？之前讨论核心思想的时候讲过，我们不仅要在模式串中，查找跟好后缀匹配的另一个子串，还要在好后缀的后缀子串中，查找最长的能跟模式串前缀子串匹配的后缀子串。所以我们还需要一个 bool 类型的数组，来记录模式串的后缀子串是否可以匹配其前缀子串。模式串： a s d a s d编号: 0 1 2 3 4 5后缀子串长度suffixprefixd1suffix[1] = 2prefix[1] = falses d2suffix[2] = 1prefix[2] = falsea s d3suffix[3] = 0prefix[3] = trued a s d4suffix[4] = -1prefix[4] = falses d a s d5suffix[5] = -1prefix[5] = false接下来就是如何填充这两个数组了。这个计算非常的巧妙: 我们拿下标从 0 到 i 的子串（i 可以是 0 到 m-2）与整个模式串，求公共后缀子串。如果公共后缀子串的长度是 k，那我们就记录 suffix[k]=j（j 表示公共后缀子串的起始下标）。如果 j 等于 0，也就是说，公共后缀子串也是模式串的前缀子串，我们就记录 prefix[k]=true。代码实现如下:/** * \brief 生成好后缀和前缀子串预处理表 */ void BM::generate_suffix() { const int len = ptrn.length(); // 初始化 for (auto i = 0; i < len; i++) { suffix[i] = -1; prefix[i] = false; } // 遍历找出所有公共后缀子串 for (auto i = 0; i < len - 1; i++) { int j = i; // 公共后缀子串子串的起始位置 int suffix_len = 0; // 后缀子串长度 // 求公共后缀字串，同时记录公共后缀字串的位置 while (j >= 0 && ptrn[j] == ptrn[len - 1 - suffix_len]) suffix[++suffix_len] = j--; // 如果公共后缀子串也是模式串的前缀子串 if (j == -1) prefix[suffix_len] = true; } }这两个数组处理完后，我们就可以讨论遇到不能匹配的字符时，如何根据好后缀规则计算模式串往后滑动的位数了。假设好后缀的长度是 len。我们先拿好后缀，在 suffix 数组中查找其匹配的子串。如果 suffix[len] 不等于 -1（-1 表示不存在匹配的子串），那我们就将模式串往后移动 pos-suffix[len]+1 位（pos 表示坏字符对应的模式串中的字符下标）。如果 suffix[len] 等于 -1，表示模式串中不存在另一个跟好后缀匹配的子串片段。我们可以用下面这条规则来处理:令模式串的长度为 plen。好后缀的后缀子串 b[r, plen-1]（其中，r 取值从 pos+2 到 plen-1）的长度 len=plen-r，如果 prefix[len] 等于 true，表示长度为 len 的后缀子串，有可匹配的前缀子串，这样我们可以把模式串后移 r 位。如果两条规则都没有找到可以匹配好后缀及其后缀子串的子串，我们就将整个模式串后移 plen 位。这一段也不是很好理解。解释一下这个 r 从 pos+2 开始是因为 pos 是坏字符的下标，所以好后缀的长度应该是 plen - 1 - (pos + 1)，也就是 plen - (pos + 2)。所以 r 要从 pos+2 开始。代码实现:/** * \brief 由好后缀规则得到的位移数 * \param pos 坏字符对应模式串中的字符下标 */ int BM::shift_by_good_suffix(const int& pos) { // 好后缀长度 int len = ptrn.length() - 1 - pos; // 模式串中还存在和好后缀一样的子串 if (suffix[len] != -1) return pos - suffix[len] + 1; for (auto r = pos + 2; r < ptrn.length(); r++) { // 如果好后缀有可匹配的前缀子串 if (prefix[ptrn.length() - r] == true) return r; } // 没有前缀子串则移动整个模式串的字节数 return ptrn.length(); }BM查找实现实现了两种规则之后，查找就很好写了:/** * \brief BM算法寻找模式串 * \param main_string 主串 * \param begin 寻找的起始位置, 默认为0 * \return 模式串在主串中的下标, -1 表示未找到 */ int BM::find(const string& main_string, const int & begin) { const int plen = ptrn.length(); // 模式串长度 const int mlen = main_string.length(); // 主串长度 for (auto i = begin; i <= mlen - plen; ) { int pos; // 从后向前匹配 for (pos = plen - 1; pos >= 0; pos--) { // 找到坏字符对应的下标 if (main_string[i + pos] != ptrn[pos]) break; } // 匹配成功 if (pos < 0) return i; // 坏字符规则的位移 int bad_shift = pos - skip[static_cast<int>(main_string[i + pos])]; int good_shift = 0; // 好后缀规则的位移 if (pos < plen - 1) good_shift = shift_by_good_suffix(pos); // 向后位移两种规则中较大的数 i += std::max(good_shift, bad_shift); } return -1; }整体代码 C++ 实现BM.h#pragma once #include <string> #include <vector> #include <algorithm> using std::string; using std::vector; const int SIZE = 256; class BM { private: string ptrn; // 模式串 int skip[SIZE] = {}; // 坏字符表 vector<int> suffix; // 好后缀表 vector<bool> prefix; //前缀子串 void generate_skip(); // 建立坏字符表 void generate_suffix(); // 建立好后缀表 int shift_by_good_suffix(const int& begin); public: BM(); explicit BM(const string& p); ~BM(); void set_pattern(const string& p); int find(const string& main_string, const int& pos = 0); };BM.cpp#include "BM.h" /** * \brief 生成坏字符预处理表 */ void BM::generate_skip() { // 初始化坏字符表为模式串的长度 std::fill(skip, skip + SIZE, -1); // 从小到大的顺序可以在同一字符多次出现的时候以最靠右的那个字符到尾部距离为最终的距离 for (auto i = 0; i < ptrn.length(); i++) skip[ptrn[i]] = i; } /** * \brief 生成好后缀和前缀子串预处理表 */ void BM::generate_suffix() { const int len = ptrn.length(); // 初始化 for (auto i = 0; i < len; i++) { suffix[i] = -1; prefix[i] = false; } // 遍历找出所有公共后缀子串 for (auto i = 0; i < len - 1; i++) { int j = i; // 公共后缀子串子串的起始位置 int suffix_len = 0; // 后缀子串长度 // 求公共后缀字串，同时记录公共后缀字串的位置 while (j >= 0 && ptrn[j] == ptrn[len - 1 - suffix_len]) suffix[++suffix_len] = j--; // 如果公共后缀子串也是模式串的前缀子串 if (j == -1) prefix[suffix_len] = true; } } /** * \brief 由好后缀规则得到的位移数 * \param pos 坏字符对应模式串中的字符下标 */ int BM::shift_by_good_suffix(const int& pos) { // 好后缀长度 int len = ptrn.length() - 1 - pos; // 模式串中还存在和好后缀一样的子串 if (suffix[len] != -1) return pos - suffix[len] + 1; for (auto r = pos + 2; r < ptrn.length(); r++) { // 如果好后缀有可匹配的前缀子串 if (prefix[ptrn.length() - r] == true) return r; } // 没有前缀子串则移动整个模式串的字节数 return ptrn.length(); } BM::BM() = default; BM::BM(const string& p) { set_pattern(p); } BM::~BM() = default; /** * \brief 设置模式串并初始化 */ void BM::set_pattern(const string& p) { ptrn = p; // 分配内存 suffix.resize(p.length()); prefix.resize(p.length()); // 预处理对应的表 generate_skip(); generate_suffix(); } /** * \brief BM算法寻找模式串 * \param main_string 主串 * \param begin 寻找的起始位置, 默认为0 * \return 模式串在主串中的下标, -1 表示未找到 */ int BM::find(const string& main_string, const int & begin) { const int plen = ptrn.length(); // 模式串长度 const int mlen = main_string.length(); // 主串长度 for (auto i = begin; i <= mlen - plen; ) { int pos; // 从后向前匹配 for (pos = plen - 1; pos >= 0; pos--) { // 找到坏字符对应的下标 if (main_string[i + pos] != ptrn[pos]) break; } // 匹配成功 if (pos < 0) return i; // 坏字符规则的位移 int bad_shift = pos - skip[static_cast<int>(main_string[i + pos])]; int good_shift = 0; // 好后缀规则的位移 if (pos < plen - 1) good_shift = shift_by_good_suffix(pos); // 向后位移两种规则中较大的数 i += std::max(good_shift, bad_shift); } return -1; }BM算法性能分析空间复杂度我这里实现的 BM 算法使用了三个额外的数组: skip, suffix, prefix。其中 skip 数组和字符集的大小有关；suffix 数组和 prefix 数组都和模式串的大小有关。时间复杂度这里实现的 BM 算法是没有做什么优化的，所以极端情况下预处理的时间会比较长。比如模式串为 aaaaaaa 这种包含许多重复字符的字符串，预处理的时间复杂度就会比较高，约为 O(n^2)。但即便如此，我在测试的时候还是比 BF 算法快上十倍左右。实际情况比较复杂，大部分时候不会退化的这么严重。
这学期选了一门课: 计算机安全导论。据说主讲密码学，所以就先学习一下相关的知识啦~ 这几天学的是 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 加密处理-迭代这个过程中数据和子密钥将通过 f 函数结合在一起。下面来分析一下这个 f 函数。2.3.1 E扩展置换我们上面生成的子密钥都是48位的，而输入的数据则是32位的，所以我们需要将数据扩展成48位再进行运算。扩展置换目的有两个：生成与密钥相同长度的数据以进行异或运算；提供更长的结果，在后续的替代运算中可以进行压缩。扩展的原理如下表:// 扩展置换表，将 32位 扩展至 48位 const int E[48] = { 32, 1, 2, 3, 4, 5, 4, 5, 6, 7, 8, 9, 8, 9, 10, 11, 12, 13, 12, 13, 14, 15, 16, 17, 16, 17, 18, 19, 20, 21, 20, 21, 22, 23, 24, 25, 24, 25, 26, 27, 28, 29, 28, 29, 30, 31, 32, 1 };2.3.2 S盒替换压缩后的密钥与扩展分组异或以后得到48位的数据，将这个数据送人S盒，进行替代运算。替代由8个不同的S盒完成，每个S盒有6位输入4位输出。48位输入分为8个6位的分组，一个分组对应一个S盒，对应的S盒对各组进行代替操作。一个S盒就是一个4行16列的表，盒中的每一项都是一个4位的数。S盒的6个输入确定了其对应的输出在哪一行哪一列，输入的高低两位做为行数H，中间四位做为列数L，在S-BOX中查找第H行L列对应的数据(<32)。 // S盒，每个S盒是4x16的置换表，6位 -> 4位 const int S_BOX[8][4][16] = { { {14,4,13,1,2,15,11,8,3,10,6,12,5,9,0,7}, {0,15,7,4,14,2,13,1,10,6,12,11,9,5,3,8}, {4,1,14,8,13,6,2,11,15,12,9,7,3,10,5,0}, {15,12,8,2,4,9,1,7,5,11,3,14,10,0,6,13} }, { {15,1,8,14,6,11,3,4,9,7,2,13,12,0,5,10}, {3,13,4,7,15,2,8,14,12,0,1,10,6,9,11,5}, {0,14,7,11,10,4,13,1,5,8,12,6,9,3,2,15}, {13,8,10,1,3,15,4,2,11,6,7,12,0,5,14,9} }, { {10,0,9,14,6,3,15,5,1,13,12,7,11,4,2,8}, {13,7,0,9,3,4,6,10,2,8,5,14,12,11,15,1}, {13,6,4,9,8,15,3,0,11,1,2,12,5,10,14,7}, {1,10,13,0,6,9,8,7,4,15,14,3,11,5,2,12} }, { {7,13,14,3,0,6,9,10,1,2,8,5,11,12,4,15}, {13,8,11,5,6,15,0,3,4,7,2,12,1,10,14,9}, {10,6,9,0,12,11,7,13,15,1,3,14,5,2,8,4}, {3,15,0,6,10,1,13,8,9,4,5,11,12,7,2,14} }, { {2,12,4,1,7,10,11,6,8,5,3,15,13,0,14,9}, {14,11,2,12,4,7,13,1,5,0,15,10,3,9,8,6}, {4,2,1,11,10,13,7,8,15,9,12,5,6,3,0,14}, {11,8,12,7,1,14,2,13,6,15,0,9,10,4,5,3} }, { {12,1,10,15,9,2,6,8,0,13,3,4,14,7,5,11}, {10,15,4,2,7,12,9,5,6,1,13,14,0,11,3,8}, {9,14,15,5,2,8,12,3,7,0,4,10,1,13,11,6}, {4,3,2,12,9,5,15,10,11,14,1,7,6,0,8,13} }, { {4,11,2,14,15,0,8,13,3,12,9,7,5,10,6,1}, {13,0,11,7,4,9,1,10,14,3,5,12,2,15,8,6}, {1,4,11,13,12,3,7,14,10,15,6,8,0,5,9,2}, {6,11,13,8,1,4,10,7,9,5,0,15,14,2,3,12} }, { {13,2,8,4,6,15,11,1,10,9,3,14,5,0,12,7}, {1,15,13,8,10,3,7,4,12,5,6,11,0,14,9,2}, {7,11,4,1,9,12,14,2,0,6,10,13,15,3,5,8}, {2,1,14,7,4,10,8,13,15,12,9,0,3,5,6,11} } };代替过程产生8个4位的分组，组合在一起形成32位数据。S盒代替是 DES 算法的关键步骤，所有的其他的运算都是线性的，易于分析，而S盒是非线性的，相比于其他步骤，提供了更好安全性。2.3.3 P盒置换S盒代替运算的32位输出按照P盒进行置换。该置换把输入的每位映射到输出位，任何一位不能被映射两次，也不能被略去，映射规则如下表：// P置换，32位 -> 32位 const int P[32] = { 16, 7, 20, 21, 29, 12, 28, 17, 1, 15, 23, 26, 5, 18, 31, 10, 2, 8, 24, 14, 32, 27, 3, 9, 19, 13, 30, 6, 22, 11, 4, 25 };最后，P盒置换的结果与最初的64位分组左半部分L0异或，然后左、右半部分交换。至此，f 函数就执行了一遍。按照上述方法执行16轮即可。2.4 IP-1末置换末置换是初始置换的逆过程，DES最后一轮后，左、右两半部分并未进行交换，而是两部分合并形成一个分组做为末置换的输入。末置换规则如下表： // 结尾置换表 const int IP_1[64] = { 40, 8, 48, 16, 56, 24, 64, 32, 39, 7, 47, 15, 55, 23, 63, 31, 38, 6, 46, 14, 54, 22, 62, 30, 37, 5, 45, 13, 53, 21, 61, 29, 36, 4, 44, 12, 52, 20, 60, 28, 35, 3, 43, 11, 51, 19, 59, 27, 34, 2, 42, 10, 50, 18, 58, 26, 33, 1, 41, 9, 49, 17, 57, 25 };!> 注意合并的时候顺序不能反，R16 在前，L16 在后。经过以上步骤即可得到密文。3. C++ 代码实现网上找的代码好多都是有问题的，搞得我对着python的代码 debug 了几天才修完。这里放上我写的 DES 加密代码吧。有问题的话希望大佬指正。(不要问为什么用C++不用python，问就是快 (ಡωಡ) )DES.h#pragma once #include <iostream> #include <bitset> #include <string> #include <vector> #define ECB 0 // 电子密码本模式(Electronic Codebook Book) #define CBC 1 // 密码分组链接模式(Cipher Block Chaining) #define CFB 2 // 密码反馈模式(Cipher FeedBack) #define OFB 3 // 输出反馈模式(Output FeedBack) #define CTR 4 // 计算器模式(Counter) using std::bitset; using std::string; using std::vector; using std::cout; using std::endl; const int BLOCK_SIZE = 8; class DES { private: // 输入的64位密钥和子密钥 bitset<64> key; bitset<48> subKey[16]; string OFB_stream; // OFB 加密模式用的流 vector<string> CTR_stream; // CTR 加密模式用的流 // 初始置换表 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 }; // 结尾置换表 const int IP_1[64] = { 40, 8, 48, 16, 56, 24, 64, 32, 39, 7, 47, 15, 55, 23, 63, 31, 38, 6, 46, 14, 54, 22, 62, 30, 37, 5, 45, 13, 53, 21, 61, 29, 36, 4, 44, 12, 52, 20, 60, 28, 35, 3, 43, 11, 51, 19, 59, 27, 34, 2, 42, 10, 50, 18, 58, 26, 33, 1, 41, 9, 49, 17, 57, 25 }; /*------------------下面是生成密钥所用表-----------------*/ // 密钥置换表，将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 }; // 压缩置换，将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 }; // 每轮左移的位数 const int shiftBits[16] = { 1, 1, 2, 2, 2, 2, 2, 2, 1, 2, 2, 2, 2, 2, 2, 1 }; /*------------------下面是密码函数 f 所用表-----------------*/ // 扩展置换表，将 32位 扩展至 48位 const int E[48] = { 32, 1, 2, 3, 4, 5, 4, 5, 6, 7, 8, 9, 8, 9, 10, 11, 12, 13, 12, 13, 14, 15, 16, 17, 16, 17, 18, 19, 20, 21, 20, 21, 22, 23, 24, 25, 24, 25, 26, 27, 28, 29, 28, 29, 30, 31, 32, 1 }; // S盒，每个S盒是4x16的置换表，6位 -> 4位 const int S_BOX[8][4][16] = { { {14,4,13,1,2,15,11,8,3,10,6,12,5,9,0,7}, {0,15,7,4,14,2,13,1,10,6,12,11,9,5,3,8}, {4,1,14,8,13,6,2,11,15,12,9,7,3,10,5,0}, {15,12,8,2,4,9,1,7,5,11,3,14,10,0,6,13} }, { {15,1,8,14,6,11,3,4,9,7,2,13,12,0,5,10}, {3,13,4,7,15,2,8,14,12,0,1,10,6,9,11,5}, {0,14,7,11,10,4,13,1,5,8,12,6,9,3,2,15}, {13,8,10,1,3,15,4,2,11,6,7,12,0,5,14,9} }, { {10,0,9,14,6,3,15,5,1,13,12,7,11,4,2,8}, {13,7,0,9,3,4,6,10,2,8,5,14,12,11,15,1}, {13,6,4,9,8,15,3,0,11,1,2,12,5,10,14,7}, {1,10,13,0,6,9,8,7,4,15,14,3,11,5,2,12} }, { {7,13,14,3,0,6,9,10,1,2,8,5,11,12,4,15}, {13,8,11,5,6,15,0,3,4,7,2,12,1,10,14,9}, {10,6,9,0,12,11,7,13,15,1,3,14,5,2,8,4}, {3,15,0,6,10,1,13,8,9,4,5,11,12,7,2,14} }, { {2,12,4,1,7,10,11,6,8,5,3,15,13,0,14,9}, {14,11,2,12,4,7,13,1,5,0,15,10,3,9,8,6}, {4,2,1,11,10,13,7,8,15,9,12,5,6,3,0,14}, {11,8,12,7,1,14,2,13,6,15,0,9,10,4,5,3} }, { {12,1,10,15,9,2,6,8,0,13,3,4,14,7,5,11}, {10,15,4,2,7,12,9,5,6,1,13,14,0,11,3,8}, {9,14,15,5,2,8,12,3,7,0,4,10,1,13,11,6}, {4,3,2,12,9,5,15,10,11,14,1,7,6,0,8,13} }, { {4,11,2,14,15,0,8,13,3,12,9,7,5,10,6,1}, {13,0,11,7,4,9,1,10,14,3,5,12,2,15,8,6}, {1,4,11,13,12,3,7,14,10,15,6,8,0,5,9,2}, {6,11,13,8,1,4,10,7,9,5,0,15,14,2,3,12} }, { {13,2,8,4,6,15,11,1,10,9,3,14,5,0,12,7}, {1,15,13,8,10,3,7,4,12,5,6,11,0,14,9,2}, {7,11,4,1,9,12,14,2,0,6,10,13,15,3,5,8}, {2,1,14,7,4,10,8,13,15,12,9,0,3,5,6,11} } }; // P置换，32位 -> 32位 const int P[32] = { 16, 7, 20, 21, 29, 12, 28, 17, 1, 15, 23, 26, 5, 18, 31, 10, 2, 8, 24, 14, 32, 27, 3, 9, 19, 13, 30, 6, 22, 11, 4, 25 }; /**********************************************************************/ /* */ /* 下面是DES算法实现所需的函数 */ /* */ /**********************************************************************/ protected: bitset<32> f(bitset<32> R, bitset<48> k); // 加密时的 f 函数 static bitset<28> left_shift(bitset<28> k, int shift); // 循环左移 static string padding(string str, const int& unit = 8); string depadding(const string& str); void generate_key(); // 生成子密钥 bitset<64> _encrypt(bitset<64> & plain); // 对 64位 数据进行加密用的函数 bitset<64> _decrypt(bitset<64> & plain); // 对 64位 数据进行解密用的函数 string ECB_encryption(const string& plain); string ECB_decryption(const string& cipher); string CBC_encryption(const string& plain, const string& IV); string CBC_decryption(const string& cipher, const string& IV); string CFB_encryption(const string& plain, const string& IV, const int& segment_size = 8); string CFB_decryption(const string& cipher, const string& IV, const int& segment_size = 8); string OFB_encryption(const string& plain, const string& IV); string OFB_decryption(const string& cipher, const string& IV); string CTR_encryption(const string& plain, const string& nonce); string CTR_decryption(const string& cipher, const string& nonce); public: DES(); explicit DES(const string& key); ~DES(); /* 工具函数 */ static bitset<64> char_to_bitset(const char s[8]); static string bitset64_to_string(bitset<64> bit); static string bitset64_to_hex(bitset<64> bit); bool set_key(const string& _key); string encrypt(const string& plain, int mode = ECB, const string& IV = "", const int& segment_size = 8); string decrypt(const string& cipher, int mode = ECB, const string& IV = "", const int& segment_size = 8); }; /** * \brief string 转换为 hex */ inline string string2hex(const 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; } inline string hex2string(const string& in) { // 长度不是偶数说明有问题 if (in.length() % 2 != 0) throw "Hex length error!"; string res; for (auto i = 0; i < in.length(); i += 2) { int tmp = 0; tmp += (in[i] - '0' > 10) ? (in[i] - 'a' + 10) * 16 : (in[i] - '0') * 16; tmp += (in[i + 1] - '0' > 10) ? (in[i + 1] - 'a' + 10) : (in[i + 1] - '0'); res += static_cast<char>(tmp); } return res; }DES.cpp#include "DES.h" /** * \brief 密码函数 f * \param R 输入的 32 位数据 * \param k 48 位子密钥 * \return 32 位的输出 */ bitset<32> DES::f(bitset<32> R, bitset<48> k) { bitset<48> expandR; //第一步: 扩展置换 R for (auto i = 0; i < 48; i++) expandR[i] = R[E[i] - 1]; //第二步: 异或 expandR ^= k; //第三步: 送入S盒 置换 int pos = 0; //在 output 中应输入的位置 bitset<32> output; for (auto i = 0; i < 48; i += 6) { // 计算 S盒 中的行列 int row = expandR[i] * 2 + expandR[i + 5]; int column = expandR[i + 1] * 8 + expandR[i + 2] * 4 \ + expandR[i + 3] * 2 + expandR[i + 4]; int num = S_BOX[i / 6][row][column]; bitset<4> tmp(num); for (auto j = 0; j < 4; j++) output[pos + j] = tmp[3 - j]; pos += 4; } // 第四步: P置换 bitset<32> tmp = output; for (auto i = 0; i < 32; i++) output[i] = tmp[P[i] - 1]; return output; } /** * \brief 对密钥的两部分进行左移 * \param k 56位密钥的一部分 * \param shift 左移位数 * \return 位移后的数据 */ bitset<28> DES::left_shift(bitset<28> k, int shift) { bitset<28> tmp = k; for (auto i = 0; i < 28; i++) k[i] = tmp[(i + shift) % 28]; return k; } /** * \brief 生成16个48位子密钥 */ void DES::generate_key() { bitset<56> realKey; bitset<28> left, right; bitset<48> compressKey; // 去除奇偶校验位 for (auto i = 0; i < 56; i++) realKey[i] = key[PC_1[i] - 1]; // 生成子密钥 for (auto round = 0; round < 16; round++) { // 前28位 与 后28位 for (auto i = 28; i < 56; i++) right[i - 28] = realKey[i]; for (auto i = 0; i < 28; i++) left[i] = realKey[i]; // 左移 left = left_shift(left, shiftBits[round]); right = left_shift(right, shiftBits[round]); // 压缩置换 for (auto i = 28; i < 56; i++) realKey[i] = right[i - 28]; for (auto i = 0; i < 28; i++) realKey[i] = left[i]; for (auto i = 0; i < 48; i++) compressKey[i] = realKey[PC_2[i] - 1]; subKey[round] = compressKey; } return; } /** * \brief 对明文进行 padding */ string DES::padding(string str, const int& unit) { if (unit > 16) throw "Unit error!"; const int n = unit - (str.length() % unit); const char pad = static_cast<char>(n); for (auto i = 0; i < n; i++) str += pad; return str; } /** * \brief 去除 padding */ string DES::depadding(const string& str) { string res = str; const auto mark = str[str.length() - 1]; for (auto i = 0; i < mark; i++) res.pop_back(); return res; } /** * \brief DES加密 * \param plain 输入的明文 * \param status 真为加密，假为解密 * \return 加密后的密文 */ bitset<64> DES::_encrypt(bitset<64> & plain) { bitset<64> cipher, currentBits; bitset<32> left, right; // 第一步: 置换IP for (auto i = 0; i < 64; i++) currentBits[i] = plain[IP[i] - 1]; // 第二步: 获取 L0 和 R0 for (auto i = 0; i < 32; i++) left[i] = currentBits[i]; for (auto i = 32; i < 64; i++) right[i - 32] = currentBits[i]; // 第三步: 十六轮迭代 for (const auto k : subKey) { const auto new_left = right; right = left ^ f(right, k); left = new_left; } // 第四步: 合并 R16 和 L16 (顺序不能反) for (auto i = 0; i < 32; i++) cipher[i] = right[i]; for (auto i = 32; i < 64; i++) cipher[i] = left[i - 32]; //第五步: 末置换 IP-1 currentBits = cipher; for (auto i = 0; i < 64; i++) cipher[i] = currentBits[IP_1[i] - 1]; //返回密文 return cipher; } bitset<64> DES::_decrypt(bitset<64> & plain) { bitset<64> cipher, currentBits; bitset<32> left, right; // 第一步: 置换IP for (auto i = 0; i < 64; i++) currentBits[i] = plain[IP[i] - 1]; // 第二步: 获取 L0 和 R0 for (auto i = 0; i < 32; i++) left[i] = currentBits[i]; for (auto i = 32; i < 64; i++) right[i - 32] = currentBits[i]; // 第三步: 十六轮迭代 for (auto i = 15; i >= 0; i--) { const auto new_left = right; right = left ^ f(right, subKey[i]); left = new_left; } // 第四步: 合并 R16 和 L16 (顺序不能反) for (auto i = 0; i < 32; i++) cipher[i] = right[i]; for (auto i = 32; i < 64; i++) cipher[i] = left[i - 32]; //第五步: 末置换 IP-1 currentBits = cipher; for (auto i = 0; i < 64; i++) cipher[i] = currentBits[IP_1[i] - 1]; //返回密文 return cipher; } /** * \brief ECB 模式下的 DES 加密 */ string DES::ECB_encryption(const string& plain) { if (plain.length() % BLOCK_SIZE != 0) throw "Plain text's length must be a multiple of 8"; string res; res.clear(); for (auto i = 0; i < plain.length(); i += 8) { string subText(plain, i, 8); bitset<64> tmp = char_to_bitset(subText.c_str()); tmp = _encrypt(tmp); res += bitset64_to_string(tmp); } return res; } /** * \brief ECB 模式下的 DES 解密 */ string DES::ECB_decryption(const string& cipher) { if (cipher.length() % BLOCK_SIZE != 0) throw "Cipher text's length must be a multiple of 8"; string res; res.clear(); for (auto i = 0; i < cipher.length(); i += 8) { string subText(cipher, i, 8); bitset<64> tmp = char_to_bitset(subText.c_str()); tmp = _decrypt(tmp); res += bitset64_to_string(tmp); } return res; } /** * \brief CBC 模式下的 DES 加密 */ string DES::CBC_encryption(const string& plain, const string& IV) { if (plain.length() % BLOCK_SIZE != 0) throw "Plain text's length must be a multiple of 8"; if (IV.length() != BLOCK_SIZE) throw "Initialization vector's length must be 64 bits!"; string res; res.clear(); string last = IV; // 需要被异或的字符串 for (auto i = 0; i < plain.length(); i += BLOCK_SIZE) { string subText(plain, i, BLOCK_SIZE); for (auto i = 0; i < BLOCK_SIZE; i++) subText[i] ^= last[i]; bitset<64> tmp = char_to_bitset(subText.c_str()); tmp = _encrypt(tmp); // 更新需要异或的字符串 last = bitset64_to_string(tmp); res += last; } return res; } /** * \brief CBC 模式下的 DES 解密 */ string DES::CBC_decryption(const string& cipher, const string& IV) { if (cipher.length() % BLOCK_SIZE != 0) throw "Cipher text's length must be a multiple of 8"; if (IV.length() != BLOCK_SIZE) throw "Initialization vector's length must be 64 bits!"; string res; res.clear(); string last = IV; // 需要被异或的字符串 for (auto i = 0; i < cipher.length(); i += BLOCK_SIZE) { string subText(cipher, i, BLOCK_SIZE); for (auto i = 0; i < BLOCK_SIZE; i++) subText[i] ^= last[i]; bitset<64> tmp = char_to_bitset(subText.c_str()); tmp = _encrypt(tmp); // 更新需要异或的字符串 last = string(cipher, i, BLOCK_SIZE); res += bitset64_to_string(tmp); } return res; } /** * \brief CFB 模式下的 DES 加密 * \param segment_size 每次加密的长度, 单位是位 */ string DES::CFB_encryption(const string& plain, const string& IV, const int& segment_size) { if (segment_size % 8 != 0) throw "Segment size must be a multiple of 8!"; if (plain.length() % BLOCK_SIZE != 0) throw "Plain text's length must be a multiple of 8"; if (IV.length() != BLOCK_SIZE) throw "Initialization vector's length must be 64 bits!"; const int real_size = segment_size / 8; string shift_register = IV; // 模拟移位寄存器 string res; for (auto begin = 0; begin < plain.length(); begin += real_size) { // 对移位器中数据进行加密 bitset<64> subText = char_to_bitset(shift_register.c_str()); subText = _encrypt(subText); // 注意这里不是直接保存在移位寄存器中的 string encrypted_buffer = bitset64_to_string(subText); string tmp; // 从Encrypted Buffer左侧取出Real Size个字节，与长度为Real Size的Plain Block进行异或操作 for (auto i = 0; i < real_size; i++) tmp += plain[begin + i] ^ encrypted_buffer[i]; res += tmp; // 将移位器中的数据左移Real Size个字节 shift_register = string(shift_register, real_size); // 将前面的加密结果从右侧移入寄存器 shift_register += tmp; } return res; } /** * \brief CFB 模式下的 DES 解密 * \param segment_size 每次加密的长度, 单位是位 */ string DES::CFB_decryption(const string& cipher, const string& IV, const int& segment_size) { if (segment_size % 8 != 0) throw "Segment size must be a multiple of 8!"; if (cipher.length() % BLOCK_SIZE != 0) throw "Cipher text's length must be a multiple of 8"; if (IV.length() != BLOCK_SIZE) throw "Initialization vector's length must be 64 bits!"; const int real_size = segment_size / 8; string shift_register = IV; // 模拟移位寄存器 string res; for (auto begin = 0; begin < cipher.length(); begin += real_size) { // 对移位器中数据进行加密 bitset<64> subText = char_to_bitset(shift_register.c_str()); subText = _encrypt(subText); // 注意这里不是直接保存在移位寄存器中的 string encrypted_buffer = bitset64_to_string(subText); string tmp; // 从Encrypted Buffer左侧取出Real Size个字节，与长度为Real Size的Plain Block进行异或操作 for (auto i = 0; i < real_size; i++) tmp += cipher[begin + i] ^ encrypted_buffer[i]; res += tmp; // 将移位器中的数据左移Real Size个字节 shift_register = string(shift_register, real_size); // 将密文从右侧移入寄存器 shift_register += string(cipher, begin, real_size); } return res; } /** * \brief OFB 模式下的 DES 加密 */ string DES::OFB_encryption(const string& plain, const string& IV) { if (IV.length() != BLOCK_SIZE) throw "Initialization vector's length must be 64 bits!"; string res; // 流为空代表之前没有使用过 OFB 加密模式, 需设置 IV if (OFB_stream.empty()) OFB_stream = ECB_encryption(IV); // 如果明文长度小于等于流的长度则直接加密 if (plain.length() <= OFB_stream.length()) { for (auto i = 0; i < plain.length(); i++) res += plain[i] ^ OFB_stream[i]; return res; } // 如果明文长度大于流的长度则继续生成流 for (auto i = OFB_stream.length(); i < plain.length(); i += BLOCK_SIZE) OFB_stream += ECB_encryption(string(OFB_stream, i - BLOCK_SIZE, BLOCK_SIZE)); for (auto i = 0; i < plain.length(); i++) res += plain[i] ^ OFB_stream[i]; return res; } /** * \brief OFB 模式下的 DES 解密。 * 由于明文和密文只在最终的异或过程中使用, 故加密与解密是对称的 */ string DES::OFB_decryption(const string& cipher, const string& IV) { if (IV.length() != BLOCK_SIZE) throw "Initialization vector's length must be 64 bits!"; string res; // 流为空代表之前没有使用过 OFB 加密模式, 需设置 IV if (OFB_stream.empty()) OFB_stream = ECB_encryption(IV); // 如果密文长度小于等于流的长度则直接解密 if (cipher.length() <= OFB_stream.length()) { for (auto i = 0; i < cipher.length(); i++) res += cipher[i] ^ OFB_stream[i]; return res; } // 如果密文长度大于流的长度则继续生成流 for (auto i = OFB_stream.length() - BLOCK_SIZE; i < cipher.length(); i += BLOCK_SIZE) OFB_stream += ECB_encryption(string(OFB_stream, i, BLOCK_SIZE)); for (auto i = 0; i < cipher.length(); i++) res += cipher[i] ^ OFB_stream[i]; return res; } /** * \brief CTR 模式下的 DES 加密 */ string DES::CTR_encryption(const string& plain, const string& nonce) { if (nonce.length() >= BLOCK_SIZE) throw "Nonce's length must be less than 128 bits!"; string res; // 如果明文长度小于等于流的长度则直接加密 if (plain.length() <= OFB_stream.length()) { for (auto i = 0; i < plain.length() / BLOCK_SIZE; i++) { for (auto j = 0; j < BLOCK_SIZE; j++) res += plain[i * BLOCK_SIZE + j] ^ CTR_stream[i][j]; } return res; } // 如果明文长度大于流的长度则继续生成流 for (auto i = CTR_stream.size(); i < plain.length() / BLOCK_SIZE; i++) { // 计数器的值即为 vector 下标的 hex 值 string counter = string2hex(std::to_string(CTR_stream.size())); int counter_len = BLOCK_SIZE - nonce.length(); string input; // 需被加密的输入 if (counter.length() > counter_len) input = nonce + string(counter, counter.length() - counter_len); else { input = nonce; // 补零 for (auto i = 0; i < counter_len - counter.length(); i++) input += static_cast<char>(0); input += counter; } CTR_stream.push_back(ECB_encryption(input)); } for (auto i = 0; i < plain.length() / BLOCK_SIZE; i++) { for (auto j = 0; j < BLOCK_SIZE; j++) res += plain[i * BLOCK_SIZE + j] ^ CTR_stream[i][j]; } return res; } /** * \brief CTR 模式下的 DES 解密 */ string DES::CTR_decryption(const string& cipher, const string& nonce) { if (nonce.length() >= BLOCK_SIZE) throw "Nonce's length must be less than 128 bits!"; string res; // 如果明文长度小于等于流的长度则直接加密 if (cipher.length() <= OFB_stream.length()) { for (auto i = 0; i < cipher.length() / BLOCK_SIZE; i++) { for (auto j = 0; j < BLOCK_SIZE; j++) res += cipher[i * BLOCK_SIZE + j] ^ CTR_stream[i][j]; } return res; } // 如果明文长度大于流的长度则继续生成流 for (auto i = CTR_stream.size(); i < cipher.length() / BLOCK_SIZE; i++) { // 计数器的值即为 vector 下标的 hex 值 string counter = string2hex(std::to_string(CTR_stream.size())); int counter_len = BLOCK_SIZE - nonce.length(); string input; // 需被加密的输入 if (counter.length() > counter_len) input = nonce + string(counter, counter.length() - counter_len); else { input = nonce; // 补零 for (auto i = 0; i < counter_len - counter.length(); i++) input += static_cast<char>(0); input += counter; } CTR_stream.push_back(ECB_encryption(input)); } for (auto i = 0; i < cipher.length() / BLOCK_SIZE; i++) { for (auto j = 0; j < BLOCK_SIZE; j++) res += cipher[i * BLOCK_SIZE + j] ^ CTR_stream[i][j]; } return res; } /** * \brief 将 8 位字符数据转换为 bitset 类型 */ bitset<64> DES::char_to_bitset(const char s[8]) { bitset<64> res; for (auto i = 0; i < 8; i++) { for (auto j = 0; j < 8; j++) res[8 * i + 7 - j] = (s[i] >> j) & 1; } return res; } /** * \brief 将 bitset<64> 类型的数据转换为 string */ string DES::bitset64_to_string(bitset<64> bit) { string res; for (auto i = 0; i < 64; i+=8) { char tmp = 0; for (auto j = 0; j < 8; j++) { tmp = tmp << 1; tmp += bit[i + j]; } res += tmp; } return res; } /** * \brief 将 bitset<64> 类型的数据转换为 HEX */ string DES::bitset64_to_hex(bitset<64> bit) { string res; for (auto i = 0; i < 64; i+=4) { int tmp = 0; for (auto j = 0; j < 4; j++) { tmp = tmp << 1; tmp += bit[i + j]; } if (tmp < 10) res += '0' + tmp; else res += 'a' + tmp - 10; } return res; } /** * \brief 默认构造函数 */ DES::DES() = default; /** * \brief 构造时设置 key * \param _key 传入的密钥 */ DES::DES(const string& _key) { set_key(_key); } DES::~DES() = default; /** * \brief 修改 key 的值 */ bool DES::set_key(const string& _key) { if (_key.length() != BLOCK_SIZE) throw "Key length must be 128 bits!"; // 密钥更换后需要重置两个流的状态 OFB_stream.clear(); CTR_stream.clear(); generate_key(); return true; } string DES::encrypt(const string& plain, const int mode, const string& IV, const int& segment_size) { switch (mode) { case ECB: { try { return ECB_encryption(plain); } catch (const char* msg) { cout << msg << endl; return string(); } } case CBC: { try { return CBC_encryption(plain, IV); } catch (const char* msg) { cout << msg << endl; return string(); } } case CFB: { try { return CFB_encryption(plain, IV, segment_size); } catch (const char* msg) { cout << msg << endl; return string(); } } case OFB: { try { return OFB_encryption(plain, IV); } catch (const char* msg) { cout << msg << endl; return string(); } } case CTR: { try { return CTR_encryption(plain, IV); } catch (const char* msg) { cout << msg << endl; return string(); } } default: { cout << "Unsupported mode!" << endl; return string(); } } } string DES::decrypt(const string& cipher, const int mode, const string& IV, const int& segment_size) { switch (mode) { case ECB: { try { return ECB_decryption(cipher); } catch (const char* msg) { cout << msg << endl; return string(); } } case CBC: { try { return CBC_decryption(cipher, IV); } catch (const char* msg) { cout << msg << endl; return string(); } } case CFB: { try { return CFB_decryption(cipher, IV, segment_size); } catch (const char* msg) { cout << msg << endl; return string(); } } case OFB: { try { return OFB_decryption(cipher, IV); } catch (const char* msg) { cout << msg << endl; return string(); } } case CTR: { try { return CTR_decryption(cipher, IV); } catch (const char* msg) { cout << msg << endl; return string(); } } default: { cout << "Unsupported mode!" << endl; return string(); } } }测试用的 main.cpp#include <iostream> #include <fstream> #include <chrono> #include "DES.h" #include "3DES.h" #include "base64.h" using namespace std; DES des; TDES tdes; int mode = -1; string k; string IV; string plain_path; string cipher_path; const string method[2] = { "DES", "3DES" }; const string MODE[5] = { "ECB", "CBC", "CFB", "OFB", "CTR" }; int main() { ifstream file; ofstream out; char cmd; int status = 0; // 是否使用 3DES CHANGE_METHOD: while (status == 0) { system("cls"); cout << "DES or 3DES ?" << endl; cout << "1. DES\n2. 3DES" << endl; cin >> status; if (status != 1 && status != 2) { cout << "Method not allow!" << endl; status = 0; system("pause"); } system("cls"); } CHANGE_MODE: while (mode < 0 || mode >= 5) { cout << "请选择加密模式" << endl; cout << "1. ECB\n2. CBC\n3. CFB\n4. OFB\n5. CTR" << endl; cin >> mode; mode--; if (mode < 0 || mode >= 5) { cout << "不支持的加密模式! 请重试" << endl; system("pause"); } system("cls"); } CHANGE_KEY: while (k.empty()) { if (status == 1) { cout << "请输入你的密钥(8个字符)" << endl; cin >> k; if (k.length() < 8) { cout << "密钥不得小于 8 个字符! " << endl; system("pause"); k.clear(); } des.set_key(k); } else if (status == 2) { cout << "请输入你的密钥(24个字符)" << endl; cin >> k; if (!tdes.set_key(k)) { cout << "密钥必须是 24 个字符! " << endl; system("pause"); k.clear(); } } else { cout << "不要乱按哦~" << endl; system("pause"); k.clear(); } system("cls"); } CHANGE_IV: while (IV.empty()) { if (mode == ECB) break; cout << "请输入初始向量 IV: " << endl; cin >> IV; if (IV.length() != BLOCK_SIZE && mode != CTR) { cout << "Initialization vector must be 128 bits!" << endl; IV.clear(); system("pause"); } if (mode == CTR && IV.length() >= BLOCK_SIZE) { cout << "Nonce must be less than 16 bytes!" << endl; IV.clear(); system("pause"); } system("cls"); } system("cls"); while (true) { cout << "当前加密方法为: " << method[status - 1] << endl; cout << "当前加密模式为: " << MODE[mode] << endl; cout << "你的密钥为: " << k << endl; cout << "当前 IV 为: " << IV << endl; cout << "1. 加密\n2. 解密\n3. 修改密钥\n4. 修改加密方式\n5. 修改加密模式\n6. 修改 IV\n7. 退出" << endl; cin >> cmd; switch (cmd) { case '1': { cout << "输入明文所在文件的绝对路径" << endl; cin.get(); getline(cin, plain_path); file.open(plain_path, ios::binary); if (!file.is_open()) { cout << "打开明文文件时发生错误!" << endl; break; } cout << "输入密文输出文件的绝对路径" << endl; getline(cin, cipher_path); out.open(cipher_path, ios::binary); if (!out.is_open()) { cout << "打开输出文件时发生错误!" << endl; break; } // 一次读入整个文件，之后再分组加密 string plain((istreambuf_iterator<char>(file)), istreambuf_iterator<char>()); auto begin = chrono::system_clock::now(); string cipher; if (status == 1) cipher = des.encrypt(plain, mode, IV); else if (status == 2) cipher = tdes.encrypt(plain, mode, IV); auto end = chrono::system_clock::now(); auto duration = chrono::duration_cast<chrono::microseconds>(end - begin); out.write(cipher.c_str(), cipher.length()); file.clear(); file.close(); out.clear(); out.close(); cout << "加密成功!" << endl; cout << "一共花费了" << double(duration.count()) * \ chrono::microseconds::period::num / chrono::microseconds::period::den \ << "秒" << endl; break; } case '2': { cout << "输入密文所在文件的绝对路径" << endl; cin.get(); getline(cin, cipher_path); file.open(cipher_path, ios::binary); if (!file.is_open()) { cout << "打开明文文件时发生错误!" << endl; break; } cout << "输入明文输出文件的绝对路径" << endl; getline(cin, plain_path); out.open(plain_path, ios::binary); if (!out.is_open()) { cout << "打开输出文件时发生错误!" << endl; break; } string cipher((istreambuf_iterator<char>(file)), istreambuf_iterator<char>()); auto begin = chrono::system_clock::now(); string plain; if (status == 1) cipher = des.decrypt(cipher, mode, IV); else if (status == 2) cipher = tdes.decrypt(cipher, mode, IV); auto end = chrono::system_clock::now(); auto duration = chrono::duration_cast<chrono::microseconds>(end - begin); out.write(plain.c_str(), plain.length()); file.clear(); file.close(); out.clear(); out.close(); cout << "解密成功!" << endl; cout << "一共花费了" << double(duration.count())* \ chrono::microseconds::period::num / chrono::microseconds::period::den \ << "秒" << endl; break; } case '3': system("cls"); k.clear(); goto CHANGE_KEY; case '4': system("cls"); status = 0; goto CHANGE_METHOD; case '5': system("cls"); mode = -1; goto CHANGE_MODE; case '6': system("cls"); IV.clear(); goto CHANGE_IV; case '7': return 0; default: cout << "不要瞎按!" << endl; break; } system("pause"); system("cls"); } return 0; }!> 里面的 base64 是我网上找的 base64 编码，这里就不放出来了吧。Referrerhttps://www.cnblogs.com/songwenlong/p/5944139.html