密码学学习笔记 之 RC4与SM4

Van1sh 密码小屋/ Stream Rc4 SM4
创建时间:
字数:3.4k 阅读:
  1. Rc4
    1. Rc4简介
    2. RC4加密流程
      1. 初始化算法（KSA）
      2. 伪随机子密码生成算法（PRGA)、加密阶段
    3. python代码实现：
    4. 实例：hgame-week2 notRC4
      1. 解密
      2. exp
  2. SM4
    1. SM4简介
    2. SM4加密流程
      1. 轮函数F：
        1. 其中T函数：
        2. 其中τ是非线性变换：
        3. 其中L函数：
      2. 密钥拓展：
        1. 系统参数FK
        2. 固定参数CK
        3. 加密密钥MK
        4. 轮密钥rKi
    3. SM4解密流程
  3. 差分功耗分析攻击（DPA）
  4. 参考资料：

Rc4

在今年寒假hgame week2的密码学中有一道notRC4的题目，说是notRC4，其实整个加密流程还是RC4，所以借此机会学习一下RC4加密。

Rc4简介

​ 在密码学中，RC4（来自Rivest Cipher 4的缩写）是一种流加密算法，由于加解密使用相同的密钥，因此也属于对称加密算法。但是由于RC4算法存在弱点，2015年2月所发布的 RFC 7465 规定禁止在TLS中使用RC4加密算法。

​ RC4由伪随机数生成器和异或运算组成。RC4的密钥长度可变，范围是[1,255]。RC4一个字节一个字节地加解密。给定一个密钥，伪随机数生成器接受密钥并产生一个S盒。S盒用来加密数据，而且在加密过程中S盒会变化。

由于异或运算的对合性，RC4加密解密使用同一套算法。

2015年，比利時魯汶大學的研究人員Mathy Vanhoef及Frank Piessens，公布了針對RC4加密算法的新型攻擊程式，可在75小時內取得cookie的內容。

RC4加密流程

初始化算法（KSA）

首先生成一个key，内容随便定义

然后将key拓展成256位，用key本身来填充，

举个栗子：如果选择key=‘vanish’,拓展后的key即为‘vanishvanishvanish……vani’ (长度为256)

然后生成一个S盒，S盒有256个元素，分别是0，1，2，……，255

接着利用key初始化（打乱）S盒，

初始化的伪代码：

1
2
3
4
5
j = 0
for( i=0 ; i<256 ; i++)
    j = (j + S[i] + key[i]) % 256
    swap (s[i],s[j])	# 交换s[i]和s[j]的值，生成一个新的S盒
endfor

可以看到，由于未初始化的S盒都是确定的，所以j可以看作只受key的值的影响，并且j的值具有“遗传性”，就是会影响后面的j的值，所以，就算只是改动key的某一个值，经过256次变化后的S盒也会由很大不同。

整个初始化抽象一点过程就是，S盒的每一个元素都会和自身的某一个元素进行交换，而和谁交换则由key来决定

伪随机子密码生成算法（PRGA)、加密阶段

伪代码：

1
2
3
4
5
6
7
8
9
i = 0
j = 0
for (i=0 ;i<len(input);i++):
    i = (i + 1) mod 256  
    j = (j + S[i]) mod 256 	#j的值受S盒影响
    swap (s[i],s[j])	# 交换s[i]和s[j]的值，生成一个新的S盒
    k = input[i] ^ S[(S[i] + S[j]) % 256]	#对明文的一个字节进行加密
    output K
endwhile

可以看到，伪随机的子密码的生成只受初始化后的S盒的影响，要加密的明文并不会影响密钥。

从这里便可以看出RC4是一个对称加密，只要拥有初始化后的S盒。那么密钥便是固定的。明文流和密钥流异或得到密文流，密文流和密钥流异或便得到明文流。

python代码实现：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
#创建S盒
s=[0]*256
for i in range(256):	
    s[i]=i
    
#拓展key
key=""
k=[0]*256
for i in range(256):
    k[i]=key[(i)mod(len(key)]
    
#初始化S盒
j=0
for i in range(256):
	j = (j+s[i]+s[j])%256
    s[i],s[j] = s[j],s[i]

#生成密钥，加密明文  
message="" 
cipher
for i in range(len(message))
    i = (i + 1)%256 
    j = (j + s[i])%256
    s[i],s[j] = s[j],s[i]
    t = (s[i] + s[j])%256
    cipher += message[i]^s[t]

实例：hgame-week2 notRC4

题目：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
#!/usr/bin/env python3
# -*- coding: utf-8 -*-
from hashlib import md5
from secret import flag
assert flag.startswith(b'hgame) and flag.endswith(b')

class Oo0:
    def __init__(self):
        self.O0 = [0] * 256
        self.Ooo = 0
        self.Ooo0 = [0] * 256
        for i in range(256):
            self.O0[i] = i
        self.oO0 = 0
    
    def OO0(self, oO0):
        l = len(oO0)
        for i in range(256):
            self.Ooo0[i] = oO0[i%l]
        for i in range(256):
            self.oO0 = ( self.oO0 + self.O0[i] + self.Ooo0[i] ) % 256
            self.O0[i], self.O0[self.oO0] = self.O0[self.oO0], self.O0[i]
        self.Ooo = self.oO0 = 0
    
    def OO0o(self, length):
        O = []
        for _ in range(length):
            self.Ooo = ( self.Ooo + 1 ) % 256
            self.oO0 = ( self.oO0 + self.O0[self.Ooo] ) % 256
            self.O0[self.Ooo], self.O0[self.oO0] = self.O0[self.oO0], self.O0[self.Ooo]
            t = ( self.O0[self.Ooo] + self.O0[self.oO0] ) % 256
            O.append( self.O0[t] )
        print(self.O0)
        return O

def xor(s1, s2):
    return bytes(map( (lambda x: x[0]^x[1]), zip(s1, s2) ))

def enc(msg):
    Oo0oO = Oo0()
    Oo0oO.OO0( md5(msg).digest()[:8] )
    O0O = Oo0oO.OO0o( len(msg) )
    return xor(msg, O0O)

print( enc(flag) )

# [157, 28, 118, 120, 251, 242, 69, 178, 165, 137, 115, 84, 250, 152, 56, 196, 191, 16, 71, 158, 1, 58, 233, 175, 214, 181, 42, 151, 255, 228, 38, 48, 186, 139, 201, 24, 30, 134, 162, 86, 187, 176, 121, 206, 153, 111, 161, 163, 26, 27, 14, 188, 96, 3, 52, 207, 57, 8, 145, 154, 238, 221, 85, 204, 66, 141, 143, 237, 113, 53, 218, 29, 177, 150, 87, 94, 183, 130, 200, 12, 182, 166, 205, 93, 252, 44, 77, 76, 55, 81, 208, 128, 6, 109, 156, 129, 103, 59, 105, 25, 75, 31, 164, 232, 132, 209, 159, 2, 194, 131, 116, 32, 19, 36, 4, 125, 108, 212, 170, 171, 248, 236, 126, 195, 174, 65, 215, 160, 91, 64, 172, 167, 13, 169, 68, 92, 20, 10, 142, 106, 23, 192, 67, 88, 253, 202, 184, 22, 249, 122, 62, 107, 123, 45, 148, 51, 100, 245, 190, 231, 220, 241, 213, 50, 70, 219, 39, 244, 82, 189, 37, 72, 119, 40, 234, 224, 80, 235, 18, 61, 198, 90, 60, 98, 95, 179, 54, 254, 74, 226, 180, 230, 211, 99, 239, 83, 144, 240, 34, 199, 35, 7, 210, 149, 112, 41, 101, 225, 168, 33, 63, 216, 79, 243, 17, 138, 97, 147, 11, 229, 222, 0, 9, 78, 49, 21, 155, 124, 135, 193, 197, 223, 5, 110, 246, 247, 104, 203, 89, 117, 140, 114, 136, 185, 15, 46, 173, 102, 73, 47, 217, 43, 146, 133, 127, 227]
# b'\x14\xe3s,\xcbq\xa8\xd1\x86\x12\xba\x9f\x88\xa9J}\xf5\xd8BF\x93x\x94\x8a\xdc\xdb\xa0\xb9O0SeJ^\xc7\xce\xcf\xe3\x1c\x10s\xe2\xb6\xceA\xfd\xd6\x87\x95W'

程序对函数名做了一些混淆，恢复之后不难看出其实就是RC4的加密流程

利用前面提到的75小时破解RC4的攻击方法破解明文显然不会是题目的本意，毕竟那方法解密的时间是以小时为单位的。

可以发现，本题不仅给出了密文，还给出了加密完成之后S盒的内容，突破点无疑是这里了。

解密

我们看到RC4最后的加密算法部分

1
2
3
4
5
6
for i in range(len(message))
    i = (i + 1)%256 
    j = (j + s[i])%256
    s[i],s[j] = s[j],s[i]
    t = (s[i] + s[j])%256
    cipher += message[i]^s[t]

首先我们可以确定的是，RC4既然是按字节加密。那么明文和密文的长度便是一致的，所以我们便可以确定加密部分经过了几次循环。

其次，与常规解密不同的是，我们显然知道flag的最后一位字符是’}’,由于异或运算的对合性，我们异或密文和明文的最后一位，便可以得到密钥的最后一位，（其实就算最后一位字符不确定，也是可以暴力遍历一百多种可能，找到其中有意义的即可）

知道密钥的最后一位，即s[t]，我们再根据最后给出的S盒就能确定t的值，

我们还知道i的值就代表着循环的次数，所以i的值也是确定的。

t = (s[i] + s[j])%256：S盒确定，i确定，t确定，因此j也是可以推出来。

推出j后，我们就可以进行swap(s[i],[j])，将S盒变回去。

j = (j + s[i])%256：j推出来后，s[i]是确定的，我们就能确定上一轮的j的值

确定了上一轮的j的值，i的值也是确定的，t = (s[i] + s[j])%256，这样就能确定t的值，从而确定s[t]，即密钥的值，有了密钥就能解密密文，推出明文了。

然后再利用s[i]，不断的推出前面的j，就能不断的倒推出明文了。最后将明文逆序一下，就是flag了。

exp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
enc=b'\x14\xe3s,\xcbq\xa8\xd1\x86\x12\xba\x9f\x88\xa9J}\xf5\xd8BF\x93x\x94\x8a\xdc\xdb\xa0\xb9O0SeJ^\xc7\xce\xcf\xe3\x1c\x10s\xe2\xb6\xceA\xfd\xd6\x87\x95W'
s= [157, 28, 118, 120, 251, 242, 69, 178, 165, 137, 115, 84, 250, 152, 56, 196, 191, 16, 71, 158, 1, 58, 233, 175, 214, 181, 42, 151, 255, 228, 38, 48, 186, 139, 201, 24, 30, 134, 162, 86, 187, 176, 121, 206, 153, 111, 161, 163, 26, 27, 14, 188, 96, 3, 52, 207, 57, 8, 145, 154, 238, 221, 85, 204, 66, 141, 143, 237, 113, 53, 218, 29, 177, 150, 87, 94, 183, 130, 200, 12, 182, 166, 205, 93, 252, 44, 77, 76, 55, 81, 208, 128, 6, 109, 156, 129, 103, 59, 105, 25, 75, 31, 164, 232, 132, 209, 159, 2, 194, 131, 116, 32, 19, 36, 4, 125, 108, 212, 170, 171, 248, 236, 126, 195, 174, 65, 215, 160, 91, 64, 172, 167, 13, 169, 68, 92, 20, 10, 142, 106, 23, 192, 67, 88, 253, 202, 184, 22, 249, 122, 62, 107, 123, 45, 148, 51, 100, 245, 190, 231, 220, 241, 213, 50, 70, 219, 39, 244, 82, 189, 37, 72, 119, 40, 234, 224, 80, 235, 18, 61, 198, 90, 60, 98, 95, 179, 54, 254, 74, 226, 180, 230, 211, 99, 239, 83, 144, 240, 34, 199, 35, 7, 210, 149, 112, 41, 101, 225, 168, 33, 63, 216, 79, 243, 17, 138, 97, 147, 11, 229, 222, 0, 9, 78, 49, 21, 155, 124, 135, 193, 197, 223, 5, 110, 246, 247, 104, 203, 89, 117, 140, 114, 136, 185, 15, 46, 173, 102, 73, 47, 217, 43, 146, 133, 127, 227]
t=s.index(ord('}')^ord('W'))  #根据最后一位密钥，确定t

i=50	#密文长度，也就是加密经过的循环的趟数
sj=(t-s[i])%256
j=s.index(sj)   #根据t和s[i]的值，确定j的值
s[i],s[j]=s[j],s[i]		#获取上一轮s盒
j=(j-s[i])%256		#恢复前一个j的值
i=i-1	#i也随着倒推而减少
t=(s[i]+s[j])%256	#倒数第二轮的i值，j值，S盒都确定了，就可以推出t的值，从而获得密钥到数第二位
flag='}'
while i>0:
    flag+=(chr((enc[i-1])^s[t]))	#解密密文
    s[i],s[j]=s[j],s[i]		#获取上一轮S盒.....如此循环
    j=(j-s[i])%256
    i=i-1
    t=(s[i]+s[j])%256

flag=flag[::-1]
print(flag)

SM4

前面按位加密的RC4由于算法弱点已经被停用了，而作为我国的分组密码标准 SM4在算法上目前还没有被破解。（但仍旧面临差分功耗攻击的威胁）

SM4简介

SM4是一种分组密码算法，分组长度为128bit，密钥长度也为128bit。加解密算法结构相同，轮密钥的使用次序则相反。加密算法和解密算法以及密钥拓展算法均采用了32轮的非线性迭代结构

SM4加密流程

SM4加密流程

其中明文被分成四组，每一组32bit即4字节。然后加上轮密钥进行一次轮函数F运算，

$X_{i+4}=F(X_i,X_{i+1},X_{i+2},X_{i+3},rK_i)=X_i ⊕ T( X_{i+1}⊕X_{i+2}⊕X_{i+3}⊕rK_i)$

轮函数F：

其中T函数：

T(x)=L(τ(x))

其中τ是非线性变换：

​ τ由四个并行的S盒构成。

​ 设输入为A，输出为 B(4字节)

​ $B =（b_0,b_1,b_2,b_3）= τ(A)=(Sbox(a_0),Sbox(a_0),Sbox(a_0),Sbox(a_0))$

Sbox

其中L函数：

​ 输入为非线性变换的输出，设输出为C

​ $C = L(B) = B ⊕（B<<<2） ⊕(B<<<10) ⊕(B<<<18) ⊕(B<<<24) $（需要说明的是这里进行的是循环位移操作）

密钥拓展：

系统参数FK

设系统参数$FK = （FK_0,FK_1,FK_2,FK_3）$

FK

固定参数CK

设固定参数$CK = （CK_0,CK_1,CK_2,CK_3）$

CK

加密密钥MK

设加密密钥$MK=（MK_0,MK_1,MK_2,MK_3）$（内容随便定义）（$MK_i$为四字节，所以密钥为128bit）

轮密钥rKi

首先$（K_0,K_1,K_2,K_3）= （MK_0⊕FK_0, MK_1⊕, FK_1, MK_2⊕FK_2, MK_3⊕FK_3）$

然后生成轮密钥$rK_i=K_{i+4}=K_i⊕T’(K_{i+1}⊕K_{i+2}⊕K_{i+3}⊕CK_i) (i=0,1,2,,,31)$

其中T’与上文提到的T函数几乎一致，只是将其中的L函数改为：

$L`(B) = B ⊕(B<<<13)⊕(B<<<23) $

可以看出加密是一组128bit，16字节，但一轮只加密4字节，一共进行32轮加密，最后将结果逆序得到密文。

SM4解密流程

由于异或运算的对合性：

因为$X_{i+4}=F(X_i,X_{i+1},X_{i+2},X_{i+3~}rK_i)=X_i ⊕ T( X_{i+1}⊕X_{i+2}⊕X_{i+3}⊕rK_i)$

所以$X_i=F(X_{i+4},X_{i+1},X_{i+2},X_{i+3},rK_i)=X_{i+4} ⊕ T(X_{i+1}⊕X_{i+2}⊕X_{i+3}⊕rK_i)$

所以解密流程仅是是加密流程的逆序：

先将密文逆序，然后轮密钥也要倒着用$rK_31,rK_30,,,,rK_0$

只不过加密时，轮密钥的生成和密文的加密可以同步进行，而解密时就要一次性先生成好所有的轮密钥，然后倒着用。

差分功耗分析攻击（DPA）

​ 现在的分组密码，包括SM4，AES等算法，都面临着差分功耗攻击的威胁。 通过利用自主设计的功耗攻击平台采集SM4算法加密过程中的功耗曲线，并对采集好的曲线进行差分处理，从而获得了SM4算法的密钥。实验结果表明，当采集400条以上功耗曲线时，即有90%以上的概率破解密钥。

​ 尽管算法本身没有弱点，但是包括差分功耗攻击在内的侧信道攻击却是个巨大威胁

文章提到的对SM4的差分功耗攻击可以分别猜测轮密钥，进而恢复密钥， 验证了SM4算法在面临差分功耗攻击时的脆弱性。也为SM算法的进一步改善和完善提供了依据。能够有效抵御差分功耗攻击应该未来安全加密算法需要考虑的一个重要因素。

参考资料：

https://baike.baidu.com/item/RC4/3454548?fr=aladdin

https://zh.wikipedia.org/wiki/RC4

https://baike.baidu.com/item/SM4.0/3901780?fr=aladdin

https://blog.csdn.net/weixin_37569048/article/details/94983841

https://blog.csdn.net/cg129054036/article/details/83016958

转载请注明来源，欢迎对文章中的引用来源进行考证，欢迎指出任何有错误或不够清晰的表达。可联系QQ 643713081，也可以邮件至 643713081@qq.com

赏

文章标题:密码学学习笔记 之 RC4与SM4

文章字数:3.4k

本文作者:Van1sh

发布时间:2020-01-30, 00:05:00

最后更新:2020-05-24, 18:32:22

原始链接:http://jayxv.github.io/2020/01/30/密码学学习笔记之RC4与SM4/

版权声明: "署名-非商用-相同方式共享 4.0" 转载请保留原文链接及作者。

©2020 Van1sh

Built with Hexo and 3-hexo theme

目录
×

喜欢就点赞,疼爱就打赏