历史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^{kr}_r(1 - \frac{1}{p_1})(1 - \frac{1}{p_2})...(1 - \frac{1}{p_r}) $$也就等于$$ φ(n) = n(1 - \frac{1}{p_1})(1 - \frac{1}{p_2})...(1 - \frac{1}{p_r}) $$这就是欧拉函数的通用计算公式。比如，1323的欧拉函数，计算过程如下：$$ φ(1323) = φ(3^3 \times 7^2) = 1323(1 - \frac{1}{3})(1 - \frac{1}{7}) = 756 $$3. 欧拉定理欧拉函数的作用，在于欧拉定理:如果两个正整数 $a$ 和 $n$ 互质，则n的欧拉函数 $\phi(n)$ 可以让下面的等式成立 : $$ a ^ {\phi_{(n)}} \equiv 1 (mod \; n) $$也就是说，$a$ 的 $\phi(n)$ 次方被 $n$ 除的余数为1。或者说，$a$ 的 $\phi(n)$ 次方减去1，可以被 $n$ 整除。比如，3和7互质，而7的欧拉函数 $\phi(7)$ 等于6，所以3的6次方 (729) 减去1，可以被7整除 (728/7=104)。欧拉定理有一个特殊情况。假设正整数 $a$ 与质数 $p$ 互质，因为质数 $p$ 的 $\phi(p)$ 等于 $p-1$ ，则欧拉定理可以写成$$ a^{p-1} \equiv 1 (mod \; p) $$这就是著名的费马小定理。它是欧拉定理的特例。4. 模反元素如果两个正整数 $a$ 和 $n$ 互质，那么一定可以找到整数 $b$ ，使得 $ab-1$ 被 $n$ 整除，或者说 $ab$ 被 $n$ 除的余数是1。$$ ab \equiv 1(mod \; n) $$这时，$b$ 就叫做 $a$ 的"模反元素"。比如，3和11互质，那么3的模反元素就是4，因为 (3 × 4)-1 可以被11整除。显然，模反元素不止一个， 4加减11的整数倍都是3的模反元素 {...,-18,-7,4,15,26,...}，即如果b是a的模反元素，则 $b+kn$ 都是a的模反元素。欧拉定理可以用来证明模反元素必然存在。$$ a^{\phi(n)} = a \times a^{\phi(n) - 1} \equiv 1(mod \; n) $$可以看到，$a$ 的 $\phi(n)-1$ 次方，就是 $a$ 的模反元素。算法流程看完这些数论的知识后，我们就可以理解 RSA 的算法原理了。首先我们先来看一下 RSA 的算法流程:1. 生成密钥假设爱丽丝要与鲍勃进行加密通信，她该怎么生成公钥和私钥呢？第一步，随机选择两个不相等的质数 $p$ 和 $q$ 。爱丽丝选择了61和53。（实际应用中，这两个质数越大，就越难破解。）第二步，计算 $p$ 和 $q$ 的乘积 $n$ 。爱丽丝就把61和53相乘。$$ n = 61×53 = 3233 $$n的长度就是密钥长度。3233写成二进制是110010100001，一共有12位，所以这个密钥就是12位。实际应用中，RSA密钥一般是1024位，重要场合则为2048位。第三步，计算 $n$ 的欧拉函数 $\phi(n)$ 。根据公式：$$ φ(n) = (p-1)(q-1) $$爱丽丝算出 $\phi(3233)$ 等于60×52，即3120。第四步，随机选择一个整数 $e$，条件是 $1< e < \phi(n)$，且 $e$ 与 $\phi(n)$ 互质。爱丽丝就在1到3120之间，随机选择了17。（实际应用中，常常选择65537。）第五步，计算 $e$ 对于 $\phi(n)$ 的模反元素 $d$。所谓"模反元素"就是指有一个整数 $d$，可以使得 $ed$ 被 $\phi(n)$ 除的余数为1。$$ ed ≡ 1 (mod φ(n)) $$这个式子等价于$$ ed - 1 = kφ(n) $$于是，找到模反元素 $d$ ，实质上就是对下面这个二元一次方程求解。$$ ex + φ(n)y = 1 $$已知 $e=17, \phi(n)=3120$，$$ 17x + 3120y = 1 $$这个方程可以用"扩展欧几里得算法"求解，此处省略具体过程。总之，爱丽丝算出一组整数解为 $(x,y)=(2753,-15)$，即 $d=2753$。至此所有计算完成。第六步，将 $n$ 和 $e$ 封装成公钥，$n$ 和 $d$ 封装成私钥。在爱丽丝的例子中，$n=3233$，$e=17$，$d=2753$，所以公钥就是 $(3233,17)$，私钥就是 $(3233, 2753)$ 。实际应用中，公钥和私钥的数据都采用ASN.1格式表达（实例）。2. 加密与解密有了公钥和密钥，就能进行加密和解密了。（1）加密要用公钥 $(n,e)$假设鲍勃要向爱丽丝发送加密信息 $m$，他就要用爱丽丝的公钥 $(n,e)$ 对 $m$ 进行加密。这里需要注意，$m$ 必须是整数（字符串可以取 ascii 值或 unicode 值），且 $m$ 必须小于 $n$。所谓"加密"，就是算出下式的 $c$ ：$$ m^e ≡ c (mod \; n) $$爱丽丝的公钥是 $(3233, 17)$，鲍勃的 $m$ 假设是 65，那么可以算出下面的等式：$$ 65^{17} ≡ 2790 (mod \; 3233) $$于是，$c$ 等于2790，鲍勃就把 2790 发给了爱丽丝。（2）解密要用私钥(n,d)爱丽丝拿到鲍勃发来的 2790 以后，就用自己的私钥 $(3233, 2753)$ 进行解密。可以证明，下面的等式一定成立：$$ c^d ≡ m (mod \; n) $$也就是说，$c$ 的 $d$ 次方除以 $n$ 的余数为 $m$ 。现在，$c$ 等于 2790，私钥是 $(3233, 2753)$ ，那么，爱丽丝算出$$ 2790^{2753} ≡ 65 (mod \; 3233) $$因此，爱丽丝知道了鲍勃加密前的原文就是65。至此，"加密--解密"的整个过程全部完成。算法安全性由上面的流程可以知道，我们总共用了 6 个数字: $ p, q, n, \phi(n), e, d $ 。其中 $n$ 和 $e$ 组成了公钥，其他的四个数字都是不公开的。四个数字中最关键的就是 $d$ 。因为私钥是由 $n, d$ 组成的，所以 $d$ 泄露就相当于私钥泄露。那么，有无可能在已知 $n$ 和 $e$ 的情况下，推导出 $d$ ？ （1）$e ^ d≡1 (mod \; \phi(n))$ 。只有知道 $e$ 和 $\phi(n)$ ，才能算出 $d$ 。 （2）$\phi(n)=(p-1)(q-1)$。只有知道 $p$ 和 $q$ ，才能算出 $\phi(n)$ 。 （3）$n=pq$ 。只有将 $n$ 因数分解，才能算出 $p$ 和 $q$ 。结论：如果 $n$ 可以被因数分解，$d$ 就可以算出，也就意味着私钥被破解。可是，大整数的因数分解，是一件非常困难的事情。目前，除了暴力破解，还没有发现别的有效方法。维基百科这样写道： "对极大整数做因数分解的难度决定了RSA算法的可靠性。换言之，对一极大整数做因数分解愈困难，RSA算法愈可靠。 假如有人找到一种快速因数分解的算法，那么RSA的可靠性就会极度下降。但找到这样的算法的可能性是非常小的。今天只有短的RSA密钥才可能被暴力破解。到2008年为止，世界上还没有任何可靠的攻击RSA算法的方式。 只要密钥长度足够长，用RSA加密的信息实际上是不能被解破的。"证明最后，我们来证明，为什么用私钥解密，一定可以正确地得到 $m$ 。也就是证明下面这个式子：$$ c^d ≡ m (mod \; n) $$因为，根据加密规则$$ ｍ^e ≡ c (mod \; n) $$于是，$c$ 可以写成下面的形式：$$ c = m^e - kn $$将 $c$ 代入要我们要证明的那个解密规则：$$ (m^e - kn)^d ≡ m (mod n) $$它等同于求证$$ m^{ed} ≡ m (mod \; n) $$由于$$ ed ≡ 1 (mod \; φ(n)) $$所以$$ ed = hφ(n)+1 $$将 $ed$ 代入：$$ m^{hφ(n)+1} ≡ m (mod \; n) $$接下来，分成两种情况证明上面这个式子。（1）m与n互质。根据欧拉定理，此时$$ m^{φ(n)} ≡ 1 (mod \; n) $$得到$$ (m^{φ(n)})^h × m ≡ m (mod \; n) $$原式得到证明。（2）m与n不是互质关系。此时，由于 $n$ 等于质数 $p$ 和 $q$ 的乘积，所以 $m$ 必然等于 $kp$ 或 $kq$ 。以 $m = kp$为例，考虑到这时$k$与$q$必然互质，则根据欧拉定理，下面的式子成立：$$ (kp)^{q-1} ≡ 1 (mod \; q) $$进一步得到$$ [(kp)^{q-1}]^{h(p-1)} × kp ≡ kp (mod \; q) $$即$$ (kp)^{ed} ≡ kp (mod \; q) $$将它改写成下面的等式$$ (kp)^{ed} = tq + kp $$这时t必然能被 $p$ 整除，即 $t=t'p$$$ (kp)^{ed} = t'pq + kp $$因为 $m=kp，n=pq$ ，所以$$ m^{ed} ≡ m (mod \; n) $$原式得到证明。代码实现Python 代码实现Miller_Rabin.py# encoding: utf-8 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, times): 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, times) def generateLargePrime(keysize=1024): while True: num = random.randrange(2**(keysize-1), 2**keysize) if isPrime(num, 8): return num if __name__ == "__main__": res = generateLargePrime() print (res)cryptomath.py# encoding: utf-8 def gcd(a, b): # Return the GCD of a and b using Euclid's Algorithm while a != 0: a, b = b % a, a return b def findModInverse(a, m): # Returns the modular inverse of a % m, which is # the number x such that a*x % m = 1 if gcd(a, m) != 1: return None # no mod inverse if a & m aren't relatively prime # Calculate using the Extended Euclidean Algorithm: u1, u2, u3 = 1, 0, a v1, v2, v3 = 0, 1, m while v3 != 0: q = u3 // v3 # // is the integer division operator v1, v2, v3, u1, u2, u3 = (u1 - q * v1), (u2 - q * v2), (u3 - q * v3), v1, v2, v3 return u1 % mRSA.py# encoding: utf-8 import random import cryptomath from Miller_Rabin import generateLargePrime def generateRSAkey(keysize): p = generateLargePrime(keysize) q = generateLargePrime(keysize) n = p * q while True: e = random.randrange(2 ** (keysize - 1), 2 ** keysize) # e 和 \phi(n) 需互素 if cryptomath.gcd(e, (p - 1) * (q - 1)) == 1: break # 计算模反元素 d = cryptomath.findModInverse(e, (p - 1) * (q - 1)) publicKey = (n, e) privateKey =(n, d) return (publicKey, privateKey) def encrypt(plain, publicKey): plain = plain.encode('ascii') plain = list(plain) cipher = [] for e in plain: cipher.append(pow(e, publicKey[1], publicKey[0])) return cipher def decrypt(cipher, privateKey): plain = [] for c in cipher: plain.append(pow(c, privateKey[1], privateKey[0])) res = bytes(plain).decode('ascii') return res if __name__ == '__main__': publicKey, privateKey = generateRSAkey(32) print("public key: ", publicKey) print("private key: ", privateKey) text = "hello world!" cipher = encrypt(text, publicKey) plain = decrypt(cipher, privateKey) print ("cipher = ", cipher) print ("plain = ", plain)Referrerhttp://www.ruanyifeng.com/blog/2013/06/rsa_algorithm_part_one.html http://www.ruanyifeng.com/blog/2013/07/rsa_algorithm_part_two.html
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
快速幂快速幂，二进制取幂（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 % m; }模意义下的大整数乘法与二进制取幂的思想一样，这次我们将其中的一个乘数表示为若干个 2 的整数次幂的和的形式。因为在对一个数做乘 2 并取模的运算的时侯，我们可以转化为加减操作防止溢出。/** * \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 = 0) { 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; }Referrerhttps://oi-wiki.org/math/quick-pow/
在所有的字符串匹配算法中，效率最高的应该是 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]，那么 ptrn(x, i) 就是 ptrn(0, i) 的最长后缀子串。现在的问题就是如何找到这个次长可匹配后缀子串了。通过上面的分析，我们很容易知道: 次长可匹配后缀子串一定是包含于最长可匹配后缀子串中的。而最长可匹配后缀子串 ptrn(r, i) 又对应最长可匹配前缀子串 ptrn(0, y)。所以这个问题就转化为求子串 ptrn(0, y) 的最长后缀子串了。按照这个思路，我们可以遍历 ptrn(0, i-1) 的所有可匹配后缀子串，直到找到一个可匹配的后缀子串 ptrn(y, i-1)，它对应的前缀子串的下一个字符和 ptrn[i] 相同。此时 ptrn(y, i) 就是子串 ptrn(0, i) 的最长可匹配后缀子串。这个失效函数是整个 KMP 算法中最难的一部分了。不理解的话可以动手画一下，加深对 next 数组的理解。这里给出我写的代码:void KMP::generate_next() { next[0] = -1; int k = -1; // 最长可匹配前缀子串的结束下标 for (auto i = 1; i < ptrn.length(); i++) { // 寻找次长可匹配后缀子串 while (k != -1 && ptrn[k + 1] != ptrn[i]) k = next[k]; if (ptrn[k + 1] == ptrn[i]) k++; next[i] = k; } }KMP算法 C++ 实现KMP.h#pragma once #include <string> #include <vector> using std::string; using std::vector; class KMP { private: string ptrn; vector<int> next; void generate_next(); public: KMP(); explicit KMP(const string& p); ~KMP(); bool set_pattern(const string& p); int find(const string& main_string); };KMP.cpp#include "KMP.h" void KMP::generate_next() { next[0] = -1; int k = -1; // 最长可匹配前缀子串的结束下标 for (auto i = 1; i < ptrn.length(); i++) { // 寻找次长可匹配后缀子串 while (k != -1 && ptrn[k + 1] != ptrn[i]) k = next[k]; if (ptrn[k + 1] == ptrn[i]) k++; next[i] = k; } } KMP::KMP() = default; KMP::KMP(const string& p) { set_pattern(p); } KMP::~KMP() = default; bool KMP::set_pattern(const string& p) { ptrn = p; next.resize(ptrn.length()); generate_next(); return true; } 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; }测试代码#include <iostream> #include <chrono> #include "KMP.h" using namespace std; using namespace chrono; int main() { string a, b; while (cin >> a >> b) { auto begin = system_clock::now(); KMP kmp(b); int pos = kmp.find(a); auto end = system_clock::now(); auto duration = duration_cast<microseconds>(end - begin); cout << "查找结果为: " << pos << endl; cout << "一共花费了: " << double(duration.count()) * \ microseconds::period::num / microseconds::period::den \ << "秒" << endl; } return 0; }
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 算法快上十倍左右。实际情况比较复杂，大部分时候不会退化的这么严重。
字符串匹配的算法有很多，本篇文章主要介绍两种比较简单的算法：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 进制数，而是将每个字符转换为整型数后再相加。当然方法不止这一种，这个方法只是举例。散列冲突那么新的问题来了，上面说了我们会有一些散列冲突的情况发生，所以我们需要判定是不是散列冲突的情况。这种其实很好判断。只需要再将子串和模式串逐字节比较一下就好了。因为哈希值不一样的一定不相等，所以还是可以提高一些效率的。代码实现随便写的参考代码，有问题请大佬指正：/** * \brief RK算法 * \param main_string 主串 * \param pattern_string 模式串 * \return 模式串在主串中的偏移量 */ int RK_find(const string& main_string, const string& pattern_string) { const int len = main_string.length() - pattern_string.length(); int refer = 0; // 模式串的哈希值 // 使用字符的 ASCII 码之和当作哈希 for (auto& i : pattern_string) refer += static_cast<int>(i); for (auto i = 0; i <= len; i++) { int cmp = 0; // 子串的 hash 值 for (auto j = 0; j < pattern_string.length(); j++) cmp += static_cast<int>(main_string[i + j]); // 如果哈希值相同，则判断是否为散列冲突 if (cmp == refer) { 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; }
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() { auto j = 0; for (auto i = 0; i < 256; i++) { j = (j + S[i] + T[i]) % 256; std::swap(S[i], S[j]); } } /** * \brief 生成密钥流 * \param len 明文长度 */ void RC4::key_stream_generate(int len) { initial(); rangeS(); auto i = 0, j = 0; while (len--) { i = (i + 1) % 256; j = (j + S[i]) % 256; std::swap(S[i], S[j]); const auto t = (S[i] + S[j]) % 256; key_stream.push_back(S[t]); } } RC4::RC4() = default; RC4::~RC4() = default; RC4::RC4(const string& k) { key = k; } bool RC4::set_key(const string& k) { key = k; return true; } string RC4::encrypt(const string& plain) { string cipher = plain; // 生成密钥流 key_stream_generate(plain.length()); // 将原文与密钥流异或 for (auto i = 0; i < plain.length(); i++) cipher[i] ^= key_stream[i]; return cipher; } string RC4::decrypt(const string& cipher) { string plain = cipher; // 生成密钥流 key_stream_generate(cipher.length()); // 将密文与密钥流异或 for (auto i = 0; i < cipher.length(); i++) plain[i] ^= key_stream[i]; return plain; } void RC4::encrypt(string plain_path, string cipher_path) { std::ifstream in; std::ofstream out; // 打开输入输出文件以及相应的异常处理 in.open(plain_path, std::ios::binary); if (!in.is_open()) throw "Input file open error!"; out.open(cipher_path, std::ios::binary); if (!out.is_open()) throw "Output file open error!"; // 获取文件流的长度 in.seekg(0, std::ios::end); auto file_len = in.tellg(); in.seekg(0, std::ios::beg); // 读入整个文件 string plain((std::istreambuf_iterator<char>(in)), std::istreambuf_iterator<char>()); // 加密并写入文件 for (auto i = 0; i < file_len; i++) out << static_cast<unsigned char>(plain[i] ^ key_stream[i]); } void RC4::decrypt(string cipher_path, string plain_path) { std::ifstream in; std::ofstream out; // 打开输入输出文件以及相应的异常处理 in.open(cipher_path, std::ios::binary); if (!in.is_open()) throw "Input file open error!"; out.open(plain_path, std::ios::binary); if (!out.is_open()) throw "Output file open error!"; // 获取文件流的长度 in.seekg(0, std::ios::end); auto file_len = in.tellg(); in.seekg(0, std::ios::beg); // 读入整个文件 string plain((std::istreambuf_iterator<char>(in)), std::istreambuf_iterator<char>()); // 解密并写入文件 for (auto i = 0; i < file_len; i++) out << static_cast<unsigned char>(plain[i] ^ key_stream[i]); }main.cpp#include <iostream> #include <chrono> #include "RC4.h" using namespace std; RC4 rc4; string k; string plain_path; string cipher_path; int main() { ifstream file; ofstream out; char cmd; CHANGE_KEY: cout << "请输入你的密钥" << endl; cin >> k; rc4.set_key(k); system("cls"); while (true) { cout << "你的密钥为: " << k << endl; cout << "1. 加密\n2. 解密\n3. 修改密钥\n4. 退出" << 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 = std::chrono::system_clock::now(); string cipher; cipher = rc4.encrypt(plain); auto end = std::chrono::system_clock::now(); auto duration = std::chrono::duration_cast<std::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()) * \ std::chrono::microseconds::period::num / std::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 = std::chrono::system_clock::now(); string plain; plain = rc4.decrypt(cipher); auto end = std::chrono::system_clock::now(); auto duration = std::chrono::duration_cast<std::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()) * \ std::chrono::microseconds::period::num / std::chrono::microseconds::period::den \ << "秒" << endl; break; } case '3': goto CHANGE_KEY; case '4': return 0; default: cout << "不要瞎按!" << endl; break; } system("pause"); system("cls"); } return 0; }
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[j] = subKey[round][j][i]; } } } /** * \brief 密钥自混淆用的 G 函数 */ void AES::G(byte k[4], const int round) { // 左移一字节 cyclicShift(k, 1, true); // S 盒替换 for (auto i = 0; i < 4; i++) { const auto row = k[i][7] * 8 + k[i][6] * 4 + k[i][5] * 2 + k[i][4]; const auto column = k[i][3] * 8 + k[i][2] * 4 + k[i][1] * 2 + k[i][0]; k[i] = S_BOX[row][column]; } // 和 RC 常量进行异或 k[0] ^= byte(Rcon[round]); }里面涉及到的 S 盒会在下面提到，可以将其当成一个常量数组。3.3 字节替换 SubBytes字节替换很简单，就是去 S 盒中查表就可以了。S 盒是一个 16 行 16 列的表，表中每个元素都是一个字节。具体流程就是函数 SubBytes() 接受一个 4x4 的字节矩阵作为输入，对其中的每个字节，前四位组成十六进制数 x 作为行号，后四位组成的十六进制数 y 作为列号，查找表中对应的值替换原来位置上的字节。这里我将 S 盒定义为 16x16 的二维数组 S[16][16]，字节替换时取该字节的高4位作为行下标，低4位作为列下标。这种方式因为还得对需要替换字节分别取高低位，所以会使字节替换操作复杂一点。可以采用 S[256] 一维数组省去这些操作，这样进行字节替换时就可以直接把该字节的值作为S盒数组的下标来进行替换。/** * S盒 */ const int S_BOX[16][16] = { {0x63, 0x7c, 0x77, 0x7b, 0xf2, 0x6b, 0x6f, 0xc5, 0x30, 0x01, 0x67, 0x2b, 0xfe, 0xd7, 0xab, 0x76}, {0xca, 0x82, 0xc9, 0x7d, 0xfa, 0x59, 0x47, 0xf0, 0xad, 0xd4, 0xa2, 0xaf, 0x9c, 0xa4, 0x72, 0xc0}, {0xb7, 0xfd, 0x93, 0x26, 0x36, 0x3f, 0xf7, 0xcc, 0x34, 0xa5, 0xe5, 0xf1, 0x71, 0xd8, 0x31, 0x15}, {0x04, 0xc7, 0x23, 0xc3, 0x18, 0x96, 0x05, 0x9a, 0x07, 0x12, 0x80, 0xe2, 0xeb, 0x27, 0xb2, 0x75}, {0x09, 0x83, 0x2c, 0x1a, 0x1b, 0x6e, 0x5a, 0xa0, 0x52, 0x3b, 0xd6, 0xb3, 0x29, 0xe3, 0x2f, 0x84}, {0x53, 0xd1, 0x00, 0xed, 0x20, 0xfc, 0xb1, 0x5b, 0x6a, 0xcb, 0xbe, 0x39, 0x4a, 0x4c, 0x58, 0xcf}, {0xd0, 0xef, 0xaa, 0xfb, 0x43, 0x4d, 0x33, 0x85, 0x45, 0xf9, 0x02, 0x7f, 0x50, 0x3c, 0x9f, 0xa8}, {0x51, 0xa3, 0x40, 0x8f, 0x92, 0x9d, 0x38, 0xf5, 0xbc, 0xb6, 0xda, 0x21, 0x10, 0xff, 0xf3, 0xd2}, {0xcd, 0x0c, 0x13, 0xec, 0x5f, 0x97, 0x44, 0x17, 0xc4, 0xa7, 0x7e, 0x3d, 0x64, 0x5d, 0x19, 0x73}, {0x60, 0x81, 0x4f, 0xdc, 0x22, 0x2a, 0x90, 0x88, 0x46, 0xee, 0xb8, 0x14, 0xde, 0x5e, 0x0b, 0xdb}, {0xe0, 0x32, 0x3a, 0x0a, 0x49, 0x06, 0x24, 0x5c, 0xc2, 0xd3, 0xac, 0x62, 0x91, 0x95, 0xe4, 0x79}, {0xe7, 0xc8, 0x37, 0x6d, 0x8d, 0xd5, 0x4e, 0xa9, 0x6c, 0x56, 0xf4, 0xea, 0x65, 0x7a, 0xae, 0x08}, {0xba, 0x78, 0x25, 0x2e, 0x1c, 0xa6, 0xb4, 0xc6, 0xe8, 0xdd, 0x74, 0x1f, 0x4b, 0xbd, 0x8b, 0x8a}, {0x70, 0x3e, 0xb5, 0x66, 0x48, 0x03, 0xf6, 0x0e, 0x61, 0x35, 0x57, 0xb9, 0x86, 0xc1, 0x1d, 0x9e}, {0xe1, 0xf8, 0x98, 0x11, 0x69, 0xd9, 0x8e, 0x94, 0x9b, 0x1e, 0x87, 0xe9, 0xce, 0x55, 0x28, 0xdf}, {0x8c, 0xa1, 0x89, 0x0d, 0xbf, 0xe6, 0x42, 0x68, 0x41, 0x99, 0x2d, 0x0f, 0xb0, 0x54, 0xbb, 0x16} };解密时的 逆字节替换 就是用 逆S盒 进行字节替换。逆S盒 如下:/** * 逆S盒 */ const int INVERSE_S_BOX[16][16] = { {0x52, 0x09, 0x6a, 0xd5, 0x30, 0x36, 0xa5, 0x38, 0xbf, 0x40, 0xa3, 0x9e, 0x81, 0xf3, 0xd7, 0xfb}, {0x7c, 0xe3, 0x39, 0x82, 0x9b, 0x2f, 0xff, 0x87, 0x34, 0x8e, 0x43, 0x44, 0xc4, 0xde, 0xe9, 0xcb}, {0x54, 0x7b, 0x94, 0x32, 0xa6, 0xc2, 0x23, 0x3d, 0xee, 0x4c, 0x95, 0x0b, 0x42, 0xfa, 0xc3, 0x4e}, {0x08, 0x2e, 0xa1, 0x66, 0x28, 0xd9, 0x24, 0xb2, 0x76, 0x5b, 0xa2, 0x49, 0x6d, 0x8b, 0xd1, 0x25}, {0x72, 0xf8, 0xf6, 0x64, 0x86, 0x68, 0x98, 0x16, 0xd4, 0xa4, 0x5c, 0xcc, 0x5d, 0x65, 0xb6, 0x92}, {0x6c, 0x70, 0x48, 0x50, 0xfd, 0xed, 0xb9, 0xda, 0x5e, 0x15, 0x46, 0x57, 0xa7, 0x8d, 0x9d, 0x84}, {0x90, 0xd8, 0xab, 0x00, 0x8c, 0xbc, 0xd3, 0x0a, 0xf7, 0xe4, 0x58, 0x05, 0xb8, 0xb3, 0x45, 0x06}, {0xd0, 0x2c, 0x1e, 0x8f, 0xca, 0x3f, 0x0f, 0x02, 0xc1, 0xaf, 0xbd, 0x03, 0x01, 0x13, 0x8a, 0x6b}, {0x3a, 0x91, 0x11, 0x41, 0x4f, 0x67, 0xdc, 0xea, 0x97, 0xf2, 0xcf, 0xce, 0xf0, 0xb4, 0xe6, 0x73}, {0x96, 0xac, 0x74, 0x22, 0xe7, 0xad, 0x35, 0x85, 0xe2, 0xf9, 0x37, 0xe8, 0x1c, 0x75, 0xdf, 0x6e}, {0x47, 0xf1, 0x1a, 0x71, 0x1d, 0x29, 0xc5, 0x89, 0x6f, 0xb7, 0x62, 0x0e, 0xaa, 0x18, 0xbe, 0x1b}, {0xfc, 0x56, 0x3e, 0x4b, 0xc6, 0xd2, 0x79, 0x20, 0x9a, 0xdb, 0xc0, 0xfe, 0x78, 0xcd, 0x5a, 0xf4}, {0x1f, 0xdd, 0xa8, 0x33, 0x88, 0x07, 0xc7, 0x31, 0xb1, 0x12, 0x10, 0x59, 0x27, 0x80, 0xec, 0x5f}, {0x60, 0x51, 0x7f, 0xa9, 0x19, 0xb5, 0x4a, 0x0d, 0x2d, 0xe5, 0x7a, 0x9f, 0x93, 0xc9, 0x9c, 0xef}, {0xa0, 0xe0, 0x3b, 0x4d, 0xae, 0x2a, 0xf5, 0xb0, 0xc8, 0xeb, 0xbb, 0x3c, 0x83, 0x53, 0x99, 0x61}, {0x17, 0x2b, 0x04, 0x7e, 0xba, 0x77, 0xd6, 0x26, 0xe1, 0x69, 0x14, 0x63, 0x55, 0x21, 0x0c, 0x7d} };S-BOX 也是通过计算算出来的，具体方法可以参考这里3.4 行移位 ShiftRows前面已经说过，AES运算都是基于4x4二维数组进行的。行移位操作为：第0行不移动，第1行循环左移1字节，第2行循环左移2字节，第3行循环左移3字节。解密时逆行移位操作为：第0行不移动，第1行循环右移1字节，第2行循环右移2字节，第3行循环右移3字节。/** * \brief 循环位移 * \param shift 移动的位数 * \param encrypt true 为左移, false 为右移 */ void AES::cyclicShift(byte row[4], const int shift, const bool encrypt) { byte tmp[4]; for (auto i = 0; i < 4; i++) { if (encrypt) tmp[i] = row[(i + shift) % 4]; else tmp[i] = row[(i - shift + 4) % 4]; } for (auto i = 0; i < 4; i++) row[i] = tmp[i]; } /** * \brief 行位移 */ void AES::shiftRows(byte matrix[4][4], bool encrypt) { // 第一行不需要位移 for (auto i = 1; i < 4; i++) cyclicShift(matrix[i], i, encrypt); }3.5 列混淆 MixColumns列混淆通过矩阵相乘来实现，经过移位后的矩阵左乘一个固定的矩阵，得到混淆后的矩阵，如下公式所示: !> 注意公式中用到的乘法是伽罗华域（GF，有限域）上的乘法，高级加密标准文档 fips-197 上有讲。解密时逆列混淆操作和列混淆一样，只是左乘的矩阵使用如下矩阵。$$ \left[ \begin{matrix} 0E & 0B & 0D & 09\\ 09 & 0E & 0B & 0D\\ 0D & 09 & 0E & 0B\\ 0B & 0D & 09 & 0E \end{matrix} \right] $$可以验证此矩阵B是列混合使用矩阵A的逆矩阵，两者乘积为单位矩阵，即AB=BA=E。/** * \brief 列混淆 */ void AES::mixColumns(byte matrix[4][4], bool encrypt) { for (auto i = 0; i < 4; i++) { byte tmp[4]; for (auto j = 0; j < 4; j++) tmp[j] = matrix[j][i]; // 列混淆的矩阵相乘, 这里直接用了展开后的式子 if (encrypt) { matrix[0][i] = GFMul(0x02, tmp[0]) ^ GFMul(0x03, tmp[1]) ^ tmp[2] ^ tmp[3]; matrix[1][i] = tmp[0] ^ GFMul(0x02, tmp[1]) ^ GFMul(0x03, tmp[2]) ^ tmp[3]; matrix[2][i] = tmp[0] ^ tmp[1] ^ GFMul(0x02, tmp[2]) ^ GFMul(0x03, tmp[3]); matrix[3][i] = GFMul(0x03, tmp[0]) ^ tmp[1] ^ tmp[2] ^ GFMul(0x02, tmp[3]); } else { matrix[0][i] = GFMul(0x0e, tmp[0]) ^ GFMul(0x0b, tmp[1]) ^ GFMul(0x0d, tmp[2]) ^ GFMul(0x09, tmp[3]); matrix[1][i] = GFMul(0x09, tmp[0]) ^ GFMul(0x0e, tmp[1]) ^ GFMul(0x0b, tmp[2]) ^ GFMul(0x0d, tmp[3]); matrix[2][i] = GFMul(0x0d, tmp[0]) ^ GFMul(0x09, tmp[1]) ^ GFMul(0x0e, tmp[2]) ^ GFMul(0x0b, tmp[3]); matrix[3][i] = GFMul(0x0b, tmp[0]) ^ GFMul(0x0d, tmp[1]) ^ GFMul(0x09, tmp[2]) ^ GFMul(0x0e, tmp[3]); } } } /** * \brief GF(2^8) 上的乘法 */ byte AES::GFMul(byte u, byte v) { byte res; for (auto i = 0; i < 8; i++) { if ((v & byte(1)) != 0) res ^= u; byte flag = u & byte(0x80); u <<= 1; if (flag != 0) u ^= 0x1b; // 模素多项式 v >>= 1; } return res; }3.6 轮密钥加 AddRoundKey扩展密钥只参与了这一步。根据当前加密的轮数，用w[]中的 4 个扩展密钥与矩阵的 4 个列进行按位异或。如下图：这里由于我写的代码使用 w11[4] 这样的数组来存放密钥的，所以与图中有所不同。具体代码放在最后一起吧。4. C++ 代码实现下面实现的是 ECB 模式下的 AES-128 加密算法:AES.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; typedef bitset<8> byte; typedef bitset<32> word; class AES { private: byte key[4][4]; byte subKey[11][4][4]; string OFB_stream; // OFB 加密模式用的流 vector<string> CTR_stream; // CTR 加密模式用的流 /** * S盒 */ const int S_BOX[16][16] = { {0x63, 0x7c, 0x77, 0x7b, 0xf2, 0x6b, 0x6f, 0xc5, 0x30, 0x01, 0x67, 0x2b, 0xfe, 0xd7, 0xab, 0x76}, {0xca, 0x82, 0xc9, 0x7d, 0xfa, 0x59, 0x47, 0xf0, 0xad, 0xd4, 0xa2, 0xaf, 0x9c, 0xa4, 0x72, 0xc0}, {0xb7, 0xfd, 0x93, 0x26, 0x36, 0x3f, 0xf7, 0xcc, 0x34, 0xa5, 0xe5, 0xf1, 0x71, 0xd8, 0x31, 0x15}, {0x04, 0xc7, 0x23, 0xc3, 0x18, 0x96, 0x05, 0x9a, 0x07, 0x12, 0x80, 0xe2, 0xeb, 0x27, 0xb2, 0x75}, {0x09, 0x83, 0x2c, 0x1a, 0x1b, 0x6e, 0x5a, 0xa0, 0x52, 0x3b, 0xd6, 0xb3, 0x29, 0xe3, 0x2f, 0x84}, {0x53, 0xd1, 0x00, 0xed, 0x20, 0xfc, 0xb1, 0x5b, 0x6a, 0xcb, 0xbe, 0x39, 0x4a, 0x4c, 0x58, 0xcf}, {0xd0, 0xef, 0xaa, 0xfb, 0x43, 0x4d, 0x33, 0x85, 0x45, 0xf9, 0x02, 0x7f, 0x50, 0x3c, 0x9f, 0xa8}, {0x51, 0xa3, 0x40, 0x8f, 0x92, 0x9d, 0x38, 0xf5, 0xbc, 0xb6, 0xda, 0x21, 0x10, 0xff, 0xf3, 0xd2}, {0xcd, 0x0c, 0x13, 0xec, 0x5f, 0x97, 0x44, 0x17, 0xc4, 0xa7, 0x7e, 0x3d, 0x64, 0x5d, 0x19, 0x73}, {0x60, 0x81, 0x4f, 0xdc, 0x22, 0x2a, 0x90, 0x88, 0x46, 0xee, 0xb8, 0x14, 0xde, 0x5e, 0x0b, 0xdb}, {0xe0, 0x32, 0x3a, 0x0a, 0x49, 0x06, 0x24, 0x5c, 0xc2, 0xd3, 0xac, 0x62, 0x91, 0x95, 0xe4, 0x79}, {0xe7, 0xc8, 0x37, 0x6d, 0x8d, 0xd5, 0x4e, 0xa9, 0x6c, 0x56, 0xf4, 0xea, 0x65, 0x7a, 0xae, 0x08}, {0xba, 0x78, 0x25, 0x2e, 0x1c, 0xa6, 0xb4, 0xc6, 0xe8, 0xdd, 0x74, 0x1f, 0x4b, 0xbd, 0x8b, 0x8a}, {0x70, 0x3e, 0xb5, 0x66, 0x48, 0x03, 0xf6, 0x0e, 0x61, 0x35, 0x57, 0xb9, 0x86, 0xc1, 0x1d, 0x9e}, {0xe1, 0xf8, 0x98, 0x11, 0x69, 0xd9, 0x8e, 0x94, 0x9b, 0x1e, 0x87, 0xe9, 0xce, 0x55, 0x28, 0xdf}, {0x8c, 0xa1, 0x89, 0x0d, 0xbf, 0xe6, 0x42, 0x68, 0x41, 0x99, 0x2d, 0x0f, 0xb0, 0x54, 0xbb, 0x16} }; /** * 逆S盒 */ const int INVERSE_S_BOX[16][16] = { {0x52, 0x09, 0x6a, 0xd5, 0x30, 0x36, 0xa5, 0x38, 0xbf, 0x40, 0xa3, 0x9e, 0x81, 0xf3, 0xd7, 0xfb}, {0x7c, 0xe3, 0x39, 0x82, 0x9b, 0x2f, 0xff, 0x87, 0x34, 0x8e, 0x43, 0x44, 0xc4, 0xde, 0xe9, 0xcb}, {0x54, 0x7b, 0x94, 0x32, 0xa6, 0xc2, 0x23, 0x3d, 0xee, 0x4c, 0x95, 0x0b, 0x42, 0xfa, 0xc3, 0x4e}, {0x08, 0x2e, 0xa1, 0x66, 0x28, 0xd9, 0x24, 0xb2, 0x76, 0x5b, 0xa2, 0x49, 0x6d, 0x8b, 0xd1, 0x25}, {0x72, 0xf8, 0xf6, 0x64, 0x86, 0x68, 0x98, 0x16, 0xd4, 0xa4, 0x5c, 0xcc, 0x5d, 0x65, 0xb6, 0x92}, {0x6c, 0x70, 0x48, 0x50, 0xfd, 0xed, 0xb9, 0xda, 0x5e, 0x15, 0x46, 0x57, 0xa7, 0x8d, 0x9d, 0x84}, {0x90, 0xd8, 0xab, 0x00, 0x8c, 0xbc, 0xd3, 0x0a, 0xf7, 0xe4, 0x58, 0x05, 0xb8, 0xb3, 0x45, 0x06}, {0xd0, 0x2c, 0x1e, 0x8f, 0xca, 0x3f, 0x0f, 0x02, 0xc1, 0xaf, 0xbd, 0x03, 0x01, 0x13, 0x8a, 0x6b}, {0x3a, 0x91, 0x11, 0x41, 0x4f, 0x67, 0xdc, 0xea, 0x97, 0xf2, 0xcf, 0xce, 0xf0, 0xb4, 0xe6, 0x73}, {0x96, 0xac, 0x74, 0x22, 0xe7, 0xad, 0x35, 0x85, 0xe2, 0xf9, 0x37, 0xe8, 0x1c, 0x75, 0xdf, 0x6e}, {0x47, 0xf1, 0x1a, 0x71, 0x1d, 0x29, 0xc5, 0x89, 0x6f, 0xb7, 0x62, 0x0e, 0xaa, 0x18, 0xbe, 0x1b}, {0xfc, 0x56, 0x3e, 0x4b, 0xc6, 0xd2, 0x79, 0x20, 0x9a, 0xdb, 0xc0, 0xfe, 0x78, 0xcd, 0x5a, 0xf4}, {0x1f, 0xdd, 0xa8, 0x33, 0x88, 0x07, 0xc7, 0x31, 0xb1, 0x12, 0x10, 0x59, 0x27, 0x80, 0xec, 0x5f}, {0x60, 0x51, 0x7f, 0xa9, 0x19, 0xb5, 0x4a, 0x0d, 0x2d, 0xe5, 0x7a, 0x9f, 0x93, 0xc9, 0x9c, 0xef}, {0xa0, 0xe0, 0x3b, 0x4d, 0xae, 0x2a, 0xf5, 0xb0, 0xc8, 0xeb, 0xbb, 0x3c, 0x83, 0x53, 0x99, 0x61}, {0x17, 0x2b, 0x04, 0x7e, 0xba, 0x77, 0xd6, 0x26, 0xe1, 0x69, 0x14, 0x63, 0x55, 0x21, 0x0c, 0x7d} }; // 轮常数，密钥扩展中用到。（AES-128只需要10轮） byte Rcon[10] = { 0x01, 0x02, 0x04, 0x08, 0x10, 0x20, 0x40, 0x80, 0x1b, 0x36 }; /**********************************************************************/ /* */ /* AES算法实现 */ /* */ /**********************************************************************/ void keyExpansion(); /* 轮加密所需的函数 */ void subByte(byte matrix[4][4], bool encrypt = true) const; void shiftRows(byte matrix[4][4], bool encrypt = true); void mixColumns(byte matrix[4][4], bool encrypt = true); void addRoundKey(byte matrix[4][4], int round) const; /* 工具函数 */ void cyclicShift(byte row[4], int shift, bool encrypt = true); static byte GFMul(byte u, byte v); void T(byte k[4], int round); static word byteToWord(byte k[4]); protected: void _encrypt(byte plain[4][4]); void _decrypt(byte cipher[4][4]); 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: AES(); explicit AES(const string& k); ~AES(); bool set_key(string k); static string padding(string str, const int& unit = 16); static string depadding(const string& str); 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; } /** * \brief 将 string 转换为 4x4 的矩阵 */ inline void string2matrix(byte matrix[4][4], string plain) { for (auto i = 0; i < 4; i++) { for (auto j = 0; j < 4; j++) matrix[j][i] = byte(plain[i * 4 + j]); } } /** * \brief 将 4x4 的矩阵转换为 string */ inline string matrix2string(byte matrix[4][4]) { string res; for (auto i = 0; i < 4; i++) { for (auto j = 0; j < 4; j++) res += static_cast<char>(matrix[j][i].to_ulong()); } return res; }AES.cpp#include "AES.h" /** * \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) T(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[j] = subKey[round][j][i]; } } } /** * \brief 字节替换 * \param plain 输入的原文 * \param encrypt 标识是否加密 */ void AES::subByte(byte matrix[4][4], bool encrypt) const { for (auto i = 0; i < 4; i++) { for (auto j = 0; j < 4; j++) { // 计算出 S-BOX 中的行列 const int row = matrix[i][j][7] * 8 + matrix[i][j][6] * 4 + matrix[i][j][5] * 2 + matrix[i][j][4]; const int column = matrix[i][j][3] * 8 + matrix[i][j][2] * 4 + matrix[i][j][1] * 2 + matrix[i][j][0]; if (encrypt) matrix[i][j] = S_BOX[row][column]; else matrix[i][j] = INVERSE_S_BOX[row][column]; } } } /** * \brief 循环位移 * \param shift 移动的位数 * \param encrypt true 为左移, false 为右移 */ void AES::cyclicShift(byte row[4], const int shift, const bool encrypt) { byte tmp[4]; for (auto i = 0; i < 4; i++) { if (encrypt) tmp[i] = row[(i + shift) % 4]; else tmp[i] = row[(i - shift + 4) % 4]; } for (auto i = 0; i < 4; i++) row[i] = tmp[i]; } /** * \brief 行位移 */ void AES::shiftRows(byte matrix[4][4], bool encrypt) { // 第一行不需要位移 for (auto i = 1; i < 4; i++) cyclicShift(matrix[i], i, encrypt); } /** * \brief 列混淆 */ void AES::mixColumns(byte matrix[4][4], bool encrypt) { for (auto i = 0; i < 4; i++) { byte tmp[4]; for (auto j = 0; j < 4; j++) tmp[j] = matrix[j][i]; // 列混淆的矩阵相乘, 这里直接用了展开后的式子 if (encrypt) { matrix[0][i] = GFMul(0x02, tmp[0]) ^ GFMul(0x03, tmp[1]) ^ tmp[2] ^ tmp[3]; matrix[1][i] = tmp[0] ^ GFMul(0x02, tmp[1]) ^ GFMul(0x03, tmp[2]) ^ tmp[3]; matrix[2][i] = tmp[0] ^ tmp[1] ^ GFMul(0x02, tmp[2]) ^ GFMul(0x03, tmp[3]); matrix[3][i] = GFMul(0x03, tmp[0]) ^ tmp[1] ^ tmp[2] ^ GFMul(0x02, tmp[3]); } else { matrix[0][i] = GFMul(0x0e, tmp[0]) ^ GFMul(0x0b, tmp[1]) ^ GFMul(0x0d, tmp[2]) ^ GFMul(0x09, tmp[3]); matrix[1][i] = GFMul(0x09, tmp[0]) ^ GFMul(0x0e, tmp[1]) ^ GFMul(0x0b, tmp[2]) ^ GFMul(0x0d, tmp[3]); matrix[2][i] = GFMul(0x0d, tmp[0]) ^ GFMul(0x09, tmp[1]) ^ GFMul(0x0e, tmp[2]) ^ GFMul(0x0b, tmp[3]); matrix[3][i] = GFMul(0x0b, tmp[0]) ^ GFMul(0x0d, tmp[1]) ^ GFMul(0x09, tmp[2]) ^ GFMul(0x0e, tmp[3]); } } } /** * \brief 轮密钥加 */ void AES::addRoundKey(byte matrix[4][4], const int round) const { for (auto i = 0; i < 4; i++) for (auto j = 0; j < 4; j++) matrix[i][j] ^= subKey[round][i][j]; } /** * \brief GF(2^8) 上的乘法 */ byte AES::GFMul(byte u, byte v) { byte res; for (auto i = 0; i < 8; i++) { if ((v & byte(1)) != 0) res ^= u; byte flag = u & byte(0x80); u <<= 1; if (flag != 0) u ^= 0x1b; // 模素多项式 v >>= 1; } return res; } /** * \brief 密钥自混淆用的 T 函数 */ void AES::T(byte k[4], const int round) { // 左移一字节 cyclicShift(k, 1, true); // S 盒替换 for (auto i = 0; i < 4; i++) { const auto row = k[i][7] * 8 + k[i][6] * 4 + k[i][5] * 2 + k[i][4]; const auto column = k[i][3] * 8 + k[i][2] * 4 + k[i][1] * 2 + k[i][0]; k[i] = S_BOX[row][column]; } // 和 RC 常量进行异或 k[0] ^= byte(Rcon[round]); } /** * \brief 将 4 个 byte 类型转换为 word 类型 */ word AES::byteToWord(byte k[4]) { word res(0x00000000); for (auto i = 0; i < 4; i++) { word tmp = k[i].to_ulong(); tmp <<= 24 - 8 * i; res |= tmp; } return res; } /** * \brief padding 函数 */ string AES::padding(string str, const int& unit) { if (unit > BLOCK_SIZE) 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 AES::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 加密 128 位的数据 */ void AES::_encrypt(byte plain[4][4]) { // 第一步: 轮密钥加 addRoundKey(plain, 0); // 第二步: 开始轮加密 for (auto round = 1; round <= 10; round++) { subByte(plain, true); shiftRows(plain, true); // 最后一轮不进行列混淆 if (round != 10) mixColumns(plain, true); addRoundKey(plain, round); } } /** * \brief 解密 128 位的数据 */ void AES::_decrypt(byte cipher[4][4]) { // 第一步: 轮密钥加 addRoundKey(cipher, 10); // 第二步: 开始轮解密 for (auto round = 9; round >= 0; round--) { shiftRows(cipher, false); subByte(cipher, false); addRoundKey(cipher, round); // 最后一轮不进行列混淆 if (round != 0) mixColumns(cipher, false); } } /** * \brief ECB 模式下的 AES 加密 */ string AES::ECB_encryption(const string& plain) { if (plain.length() % BLOCK_SIZE != 0) throw "Plain text's length must be a multiple of 16"; string res; for (auto begin = 0; begin < plain.length(); begin += BLOCK_SIZE) { byte subText[4][4]; string2matrix(subText, string(plain, begin, BLOCK_SIZE)); _encrypt(subText); res += matrix2string(subText); } return res; } /** * \brief ECB 模式下的 AES 解密 */ string AES::ECB_decryption(const string& cipher) { if (cipher.length() % BLOCK_SIZE != 0) throw "Cipher text's length must be a multiple of 16"; string res; for (auto begin = 0; begin < cipher.length(); begin += BLOCK_SIZE) { byte subText[4][4]; string2matrix(subText, string(cipher, begin, BLOCK_SIZE)); _decrypt(subText); res += matrix2string(subText); } return res; } /** * \brief CBC 模式下的 AES 加密 */ string AES::CBC_encryption(const string& plain, const string& IV) { if (plain.length() % BLOCK_SIZE != 0) throw "Plain text's length must be a multiple of 16"; if (IV.length() != BLOCK_SIZE) throw "Initialization vector's length must be 128 bits!"; string res; byte last_matrix[4][4]; // 需要被异或的矩阵 string2matrix(last_matrix, IV); // 将 IV 转换为矩阵形式 for (auto begin = 0; begin < plain.length(); begin += BLOCK_SIZE) { byte subText[4][4]; string2matrix(subText, string(plain, begin, BLOCK_SIZE)); // 将当前需要加密的块与之前的密文块异或 for (auto i = 0; i < 4; i++) { for (auto j = 0; j < 4; j++) subText[i][j] ^= last_matrix[i][j]; } _encrypt(subText); res += matrix2string(subText); // 更新需要异或的矩阵 for (auto i = 0; i < 4; i++) { for (auto j = 0; j < 4; j++) last_matrix[i][j] = subText[i][j]; } } return res; } /** * \brief CBC 模式下的 AES 解密 */ string AES::CBC_decryption(const string& cipher, const string& IV) { if (cipher.length() % BLOCK_SIZE != 0) throw "Cipher text's length must be a multiple of 16"; if (IV.length() != BLOCK_SIZE) throw "Initialization vector's length must be 128 bits!"; string res; byte last_matrix[4][4]; // 需要被异或的矩阵 string2matrix(last_matrix, IV); // 将 IV 转换为矩阵形式 for (auto begin = 0; begin < cipher.length(); begin += BLOCK_SIZE) { byte subText[4][4]; string2matrix(subText, string(cipher, begin, BLOCK_SIZE)); _decrypt(subText); // 将当前需要解密的块与之前的密文块异或 for (auto i = 0; i < 4; i++) { for (auto j = 0; j < 4; j++) subText[i][j] ^= last_matrix[i][j]; } res += matrix2string(subText); // 更新需要异或的矩阵 string2matrix(last_matrix, string(cipher, begin, BLOCK_SIZE)); } return res; } /** * \brief CFB 模式下的 AES 加密 * \param segment_size 每次加密的长度, 单位是位 */ string AES::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 16"; if (IV.length() != BLOCK_SIZE) throw "Initialization vector's length must be 128 bits!"; const int real_size = segment_size / 8; string shift_register = IV; // 模拟移位寄存器 string res; for (auto begin = 0; begin < plain.length(); begin += real_size) { // 对移位器中数据进行加密 byte subText[4][4]; string2matrix(subText, shift_register); _encrypt(subText); // 注意这里不是直接保存在移位寄存器中的 string encrypted_buffer = matrix2string(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 模式下的 AES 解密 * \param segment_size 每次加密的长度, 单位是位 */ string AES::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 16"; if (IV.length() != BLOCK_SIZE) throw "Initialization vector's length must be 128 bits!"; const int real_size = segment_size / 8; string shift_register = IV; // 模拟移位寄存器 string res; for (auto begin = 0; begin < cipher.length(); begin += real_size) { // 对移位器中数据进行加密 byte subText[4][4]; string2matrix(subText, shift_register); _encrypt(subText); // 注意这里不是直接保存在移位寄存器中的 string encrypted_buffer = matrix2string(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 模式下的 AES 加密 */ string AES::OFB_encryption(const string& plain, const string& IV) { if (IV.length() != BLOCK_SIZE) throw "Initialization vector's length must be 128 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 模式下的 AES 解密。 * 由于明文和密文只在最终的异或过程中使用, 故加密与解密是对称的 */ string AES::OFB_decryption(const string& cipher, const string& IV) { if (IV.length() != BLOCK_SIZE) throw "Initialization vector's length must be 128 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 模式下的 AES 加密 */ string AES::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 模式下的 AES 解密 */ string AES::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; } AES::AES() = default; AES::AES(const string& k) { set_key(k); } AES::~AES() = default; bool AES::set_key(string k) { if (k.length() != BLOCK_SIZE) throw "Key length must be 128 bits!"; // 密钥更换后需要重置两个流的状态 OFB_stream.clear(); CTR_stream.clear(); for (auto i = 0; i < 4; i++) { for (auto j = 0; j < 4; j++) key[j][i] = byte(k[i * 4 + j]); } // 生成轮密钥 keyExpansion(); return true; } string AES::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 AES::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 <iomanip> #include <fstream> #include <chrono> #include "AES.h" #include "base64.h" using std::cin; using std::cout; using std::ifstream; using std::ofstream; using std::istreambuf_iterator; using std::ios; using std::endl; AES aes; int mode = -1; string k; string plain_path; string cipher_path; const string MODE[5] = { "ECB", "CBC", "CFB", "OFB", "CTR" }; int main() { ifstream file; ofstream out; char cmd; 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()) { cout << "请输入你的密钥(16个字符)" << endl; cin >> k; try { aes.set_key(k); break; } catch (const char * msg) { cout << msg << endl; k.clear(); system("pause"); } system("cls"); } system("cls"); while (true) { cout << "当前加密模式为: " << MODE[mode] << endl; cout << "你的密钥为: " << k << endl; cout << "1. 加密\n2. 解密\n3. 修改密钥\n4. 修改加密模式\n5. 退出" << 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 = std::chrono::system_clock::now(); string cipher; try { cipher = aes.encrypt(AES::padding(plain, 16)); } catch (const char* msg) { cout << msg << endl; break; } auto end = std::chrono::system_clock::now(); auto duration = std::chrono::duration_cast<std::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()) * \ std::chrono::microseconds::period::num / std::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 = std::chrono::system_clock::now(); string plain; try { plain = AES::depadding(aes.decrypt(cipher)); } catch (const char* msg) { cout << msg << endl; break; } auto end = std::chrono::system_clock::now(); auto duration = std::chrono::duration_cast<std::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()) * \ std::chrono::microseconds::period::num / std::chrono::microseconds::period::den \ << "秒" << endl; break; } case '3': system("cls"); k.clear(); goto CHANGE_KEY; case '4': system("cls"); mode = -1; goto CHANGE_MODE; case '5': return 0; default: cout << "不要瞎按!" << endl; break; } system("pause"); system("cls"); } return 0; }5. Referrerhttps://blog.csdn.net/shaosunrise/article/details/80219950https://boxueio.com/series/let-us-build-an-apn-provider/ebook/564https://www.cnblogs.com/Junbo20141201/p/9369860.html
这学期选了一门课: 计算机安全导论。据说主讲密码学，所以就先学习一下相关的知识啦~ 这几天学的是 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
提到数组，大部分人应该都不会陌生。我们都知道，基本所有的编程语言中都有数组这个数据类型，同时数组也是一个最基本的数据结构。那么现在有一些问题：数组的特性是什么？它是如何实现这个特性的？数组下标为什么要从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开始了。