1、序列密码
在对称加密中一般分为分组密码(block cipher)和序列密码(stream cipher),两者最大的区别就是在加密那一块,分组是对一组(一般64位)进行加密,而序列则是对一位或字符加密。
1.1 RC4密码
RC4密码大致过程就是:
-
首先由用户输入任意长度的秘钥K ,一个初始数组S[255]={0, 1, 2,...,255}
-
然后初始化一个种子秘钥 T ,将秘钥 K 的值按位循环赋给T,直到填满T为止。
-
用种子秘钥 T 对 S 表进行初始置换,得到置换后的 S 表。
代码如下:
S = [] T = [] def stream_init(main_key): """ 1、初始化 :parmas main_key: 初始化表 S 和 T,用于后续加密或解密 """ global S, T S = [i for i in range(256)] T = [main_key[i%len(main_key)] for i in range(256)] # 256位 # 对S表进行置换 j = 0 for i in range(256): j = (j + S[i] + ord(T[i])) % 256 S[i], S[j] = S[j], S[i]
-
接下来就是从 S 表中持续获取到不同的一位秘钥(核心:不断进行S表置换),然后与明文中的一位进行异或运算,就得到一位密文。同理获取到的一位秘钥与密文中的一位进行异或运算,将得到一位明文。
def deal_txt(text): """ 2、处理明文→密文或者密文→明文 :param text: 明文或者是密文 :return: 明文加密或密文解密 """ i, j = 0, 0 a_text = '' # 返回处理后的字符串 for each_t in list(text): # 遍历每位要处理的字符 i = (i + 1) % 256 j = (j + S[i]) % 256 S[i], S[j] = S[j], S[i] # 对S表进行置换 t = (S[i] + S[j]) % 256 k1 = S[t] # k1 就是经过置换后得到的一位秘钥 a_text += chr((ord(each_t) ^ k1)) # 将明文与k1的异或值unicode,转成str字母,然后拼接到a_text中。 return a_text
-
对明文中的每一位都和秘钥进行异或操作得到一位密文,然后拼接起来就是最终返回的密文。
if __name__ == '__main__': plaintext = 'zhang' key = 'fwefew' print(f"明文:{plaintext}, 秘钥:{key}") stream_init(key) cipher_txt = deal_txt('zhang') stream_init(key) plaintext2 = deal_txt(cipher_txt) print(f"密文:{cipher_txt}, 解密后明文:{plaintext2}") # 明文:zhang, 秘钥:fwefew # 密文:å¦àÔ, 解密后明文:zhang
将加密后的结果与官方RC4加密结果做了对比,发现是一样的,没毛病。这里注意:官方的RC4返回的结果是用16进制表示的,而我的是用字符表示的,其实本质上都是一样的。
2、费马小定理
定理:如果 p 是一个素数,且 a 不是 p 的倍数,那么有 $a^{p-1}\equiv1(mod p)$
证明费马小定理:
证明方法有很多,其中使用同余性质的方法证明是最精简的。
首先取一个素数 p ,设小于p的数 $x,x\subseteq[0,p-1] $,有$gcd(x, p)=1, x=x mod p$
设集合 $X = {1,2,3,\cdots,{p-1}}$
设集合 $Y = {(a\times1)mod p,(a\times2) mod p, (a\times3) mod p,\cdots,a\times({p-1})mod p}$
这里需要证明 Y 的元素不为零且互不相等,至于为什么等下面揭晓。
-
a 不是 p 的倍数推出 $a mod p\neq 0$,另外根据取模运算中的乘法运算有: $$ (a\times(p-1))mod p = (a mod p) \times (p-1)mod p)\neq0 $$ 推出 Y 的所有元素都不为0。
-
利用反证法证明 Y 的元素都互不相同,设$x, y\subset X$,假设 $ax (mod p)\equiv ay (mod p)$,推出$ax \equiv ay (mod p)$,这一步是用同余的式子对两边化简的。
根据取模定理中的除法性质,若$gcd(a, p)=1$则有 $x\equiv y (mod p)$,进而有$x=y$。
但是由于 X 中的元素都互不相同,所以有$x \neq y$ ,进而$ x\equiv y(mod p)$ 不成立,推出 $ax (mod p)\neq ay (mod p)$。注意:$x, y\subset X$
所以最后得出 Y 中的所有元素都不相同,又因为Y中的所有元素都是对 p 取余,所以 Y 的所有的元素都是属于$[0, p-1]$之间且不同。推出X=Y
所以有: $$ 1\times2\times3\times\cdots(p-1)=(a\times1)(modp)\times(a\times2)(modp)\times\cdots\times(a\times(p-1))(modp) $$ 根据取模运算中的乘法运算有: $$ 1\times2\times3\times\cdots(p-1) \equiv a^{p-1}[1\times2\times3\times\cdots\times(p-1)](modp) $$
$$ (p-1)! \equiv a^{p-1}(p-1)!(modp) $$
有根据模运算中的除法运算,因为 $gcd(i, p)=1,i\subset[0, p-1]$,所以有: $$ 1 \equiv a^{p-1}(modp) $$
$$ a^{p-1} \equiv 1(modp) $$
到此证明费马小定理结束。
3、欧拉函数和欧拉定理
欧拉函数定义:小于n且与n互素的个数称为欧拉函数$\phi(n)$
欧拉定理:任意互素的整数 a 和 n,有$a^{\phi(n)}=1 mod n$,$\phi(n)$ 是欧拉函数。
证明欧拉定理:时间紧张,后续再补。
4、最大公约数定理
如果两个整数 a 和 b,$d=gcd(a, b)$,那么存在整数 x 和 y 有 $ax+by=d$。如果 a 和 b 是互素的,那么有$ax+by=1$
总结:
这些定理都需要记住,在后面学习的 RSA 非对称加密算法中用的很多,从开始的懵逼到写完后的思路清晰,或许这就是学习的魅力吧,多看多练多总结!
参考文章:
https://www.cnblogs.com/gambler/p/9075415.html
https://mirukuchan.github.io/post/fermat-little-theorem/#more