最近有点颓废了,想学内核很难进行,逆向光刷题看着也很难,pwn刷题就是处于刷的感觉似曾相识,没有一点提升的感觉,所以我决定先攻一下逆向,把常见加解密算法先学了,今天先来这个RC4

RC4加密

我初识RC4是在国赛,记得很清楚的一点就是不停地取模256,那题当时靠着网上资料勉强算过去了。但是还是想系统地学一下,网上教程千篇一律,我决定自己模拟一边它的算法过程然后再理解一遍。

既然是加密,脱离不了三个概念,明文,密文,密钥。RC4是对称加密,我也才知道,一直以为是不可逆的那种hash加密,所以既然它是对称加密,那么对于加密和解密过程,他们所用的密钥相同。它生成密钥的过程如下:

生成密钥需要一个长度不多于256长度的字符串作为种子生成随机密钥,这是我自己的理解,因为它确实给我的感觉就是这样的随机。它初始生成了一个长度为256的S串,初始S[i]=i,后面根据用字符串种子作为一个变换规则T,交换S密钥里的各个值,这样的交换好处在于我们可以保证S串密钥为一个双射(满足单射和满射,这个概念高中应该讲过,不赘述)。然后给的一个字符串种子呢,就会被放进T中,T的长度也为256,如果所给字符串种子长度小于256,则会进行轮换,直到它长度严格等于256为止。举个例子,在RC4加密中,如果我给定字符串种子为abcd,那么T的值将是[‘a’,’b’,’c’,’d’,’a’,’b’,’c’,’d’,’a’,’b’,’c’,’d’,……’a’,’b’,’c’,’d’],对于任意0<=i<256,

T[i]=Seed[i%len(Seed)]

那么有了这个T之后呢,我们可以开始进行密钥变换了,做以下规则的变换(字符串均转成ASCII码计算):

1
2
3
4
j=0
for i in range(256):
j=(j+S[i]+T[i])%256
swap(S[i],S[j])

从这一步我们也可以看出来,S初值我们都是知道的,T在确定了字符串种子之后也是确定的,那么由此可以算出密钥S。我们平时习惯说那个字符串是密钥,但是从这里可以看出来,字符串只是用来确定密钥的,因为在这之后,T和给的字符串已经都用不到了。所以这也是我为什么说那个字符串是种子而不是密钥,因为它没有参与加密的运算,我们刚刚算的那么快乐压根都没有出现明文这种,没有明文怎么能算加密呢对吧。

最后我们看看它是如何加密的。

1
2
3
4
5
for k in range(len(m)):
i=(i+1)%256
j=(j+S[i])%256
c[k]=m[k]^S[(S[i]+S[j])%256]

有木有感觉很熟悉,跟前面生成密钥的算法差不多。这个算法如果不了解RC4,直接逆上去的话,怕能直接破防。我有体会我给你们演示一遍,首先i初值知道,c[k]知道,然后要算明文的话m[k]=c[k]^S[(S[i]+S[j])%256]然后呢,i最终值不知道,j最终值不知道,就,时间静止了呗。但是其实它最后就做一个异或,就不用管它了呗,跟它一样从头往后再异或一遍,不就回来了吗。这也就是它为什么也叫对称加密,它不仅密钥用的是一个,加密解密算法都是一样的,没错,加密即解密。RC4解密只需要对密文再加密一次就可以得到明文了。

demo

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
m='I love xia0ji233'
S=[i for i in range(256)]
key='cat flag'
T=[]
for i in S:
T.append(key[i%len(key)])
j=0
for i in range(256):
j=(j+S[i]+ord(T[i]))%256
t=S[i]
S[i]=S[j]
S[j]=t

i,j=0,0
for k in range(len(m)):
i=(i+1)%256
j=(j+S[i])%256
t=ord(m[k])^S[(S[i]+S[j])%256]
print(hex(t)[2:],end='')
#2ef1bae658e6e938ca2af63e95e372d

把它放到CyberChef中加密发现结果一致,本次可能说就是学了个寂寞吧,因为我最后只要知道它加密解密算法一致这个结论就可以了。但是最重要的还是学会了如何分辨这样的加解密以及它加解密的一个特性,也算小有成就吧,瞬间不emo了哈哈哈哈。