信安读书笔记06-序列密码_RC4_费马小定理_欧拉定理

1,289次阅读
没有评论

1、序列密码

在对称加密中一般分为分组密码(block cipher)和序列密码(stream cipher),两者最大的区别就是在加密那一块,分组是对一组(一般64位)进行加密,而序列则是对一位或字符加密。

1.1 RC4密码

RC4密码大致过程就是:

  1. 首先由用户输入任意长度的秘钥K ,一个初始数组S[255]={0, 1, 2,...,255}

  2. 然后初始化一个种子秘钥 T ,将秘钥 K 的值按位循环赋给T,直到填满T为止。

  3. 用种子秘钥 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]
    
  4. 接下来就是从 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
  5. 对明文中的每一位都和秘钥进行异或操作得到一位密文,然后拼接起来就是最终返回的密文。

    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进制表示的,而我的是用字符表示的,其实本质上都是一样的。

信安读书笔记06-序列密码_RC4_费马小定理_欧拉定理

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 的元素不为零且互不相等,至于为什么等下面揭晓。

  1. a 不是 p 的倍数推出 $a mod p\neq 0$,另外根据取模运算中的乘法运算有: $$ (a\times(p-1))mod p = (a mod p) \times (p-1)mod p)\neq0 $$ 推出 Y 的所有元素都不为0。

  2. 利用反证法证明 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://latex.vimsky.com/

https://mirukuchan.github.io/post/fermat-little-theorem/#more

2
西园公子
版权声明:本站原创文章,由西园公子2021-05-06发表,共计2696字。
转载提示:除特殊说明外本站文章皆由CC-4.0协议发布,转载请注明出处。
评论(没有评论)
载入中...