欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

python(N1CTF)详解

程序员文章站 2022-05-11 20:29:12
...

python(N1CTF)详解

前言

本来想晚上记录的,但是一看明天高考,想早点起来记录,结果睡到九点多。。。赶紧爬起来记录下这题,这题综合考察了一些,说难最后写exp基本上没改,说不难你得把python全看一遍,加密方式也要了解才能解出来。下面来看看这个题。

正文

题目给了两个python文件,一个是加密的,一个是加密后base64给的密文,这里贴一下:

#challenge.py
from N1ES import N1ES
import base64
key = "wxy191iss00000000000cute"
n1es = N1ES(key)
flag = "N1CTF{*****************************************}"
cipher = n1es.encrypt(flag)
print base64.b64encode(cipher)  # HRlgC2ReHW1/WRk2DikfNBo1dl1XZBJrRR9qECMNOjNHDktBJSxcI1hZIz07YjVx

N1ES.py:

# -*- coding: utf-8 -*-
def round_add(a, b):
    f = lambda x, y: x + y - 2 * (x & y)
    res = ''
    for i in range(len(a)):
        res += chr(f(ord(a[i]), ord(b[i])))
    return res

def permutate(table, block):
	return list(map(lambda x: block[x], table))

def string_to_bits(data):
    data = [ord(c) for c in data]
    l = len(data) * 8
    result = [0] * l
    pos = 0
    for ch in data:
        for i in range(0,8):
            result[(pos<<3)+i] = (ch>>i) & 1
        pos += 1
    return result

s_box = [54, 132, 138, 83, 16, 73, 187, 84, 146, 30, 95, 21, 148, 63, 65, 189, 188, 151, 72, 161, 116, 63, 161, 91, 37, 24, 126, 107, 87, 30, 117, 185, 98, 90, 0, 42, 140, 70, 86, 0, 42, 150, 54, 22, 144, 153, 36, 90, 149, 54, 156, 8, 59, 40, 110, 56,1, 84, 103, 22, 65, 17, 190, 41, 99, 151, 119, 124, 68, 17, 166, 125, 95, 65, 105, 133, 49, 19, 138, 29, 110, 7, 81, 134, 70, 87, 180, 78, 175, 108, 26, 121, 74, 29, 68, 162, 142, 177, 143, 86, 129, 101, 117, 41, 57, 34, 177, 103, 61, 135, 191, 74, 69, 147, 90, 49, 135, 124, 106, 19, 89, 38, 21, 41, 17, 155, 83, 38, 159, 179, 19, 157, 68, 105, 151, 166, 171, 122, 179, 114, 52, 183, 89, 107, 113, 65, 161, 141, 18, 121, 95, 4, 95, 101, 81, 156, 17, 190, 38, 84, 9, 171, 180, 59, 45, 15, 34, 89, 75, 164, 190, 140, 6, 41, 188, 77, 165, 105, 5, 107, 31, 183, 107, 141, 66, 63, 10, 9, 125, 50, 2, 153, 156, 162, 186, 76, 158, 153, 117, 9, 77, 156, 11, 145, 12, 169, 52, 57, 161, 7, 158, 110, 191, 43, 82, 186, 49, 102, 166, 31, 41, 5, 189, 27]

def generate(o):
    k = permutate(s_box,o)
    b = []
    for i in range(0, len(k), 7):
        b.append(k[i:i+7] + [1])
    c = []
    for i in range(32):
        pos = 0
        x = 0
        for j in b[i]:
            x += (j<<pos)
            pos += 1
        c.append((0x10001**x) % (0x7f))
    return c



class N1ES:
    def __init__(self, key):
        if (len(key) != 24 or isinstance(key, bytes) == False ):
            raise Exception("key must be 24 bytes long")
        self.key = key
        self.gen_subkey()

    def gen_subkey(self):
        o = string_to_bits(self.key)
        k = []
        for i in range(8):
	        o = generate(o)
        	k.extend(o)
        	o = string_to_bits([chr(c) for c in o[0:24]])
        self.Kn = []
        for i in range(32):
            self.Kn.append(map(chr, k[i * 8: i * 8 + 8]))
        return 

    def encrypt(self, plaintext):
        if (len(plaintext) % 16 != 0 or isinstance(plaintext, bytes) == False):
            raise Exception("plaintext must be a multiple of 16 in length")
        res = ''
        for i in range(len(plaintext) / 16):
            block = plaintext[i * 16:(i + 1) * 16]
            L = block[:8]
            R = block[8:]
            for round_cnt in range(32):
                L, R = R, (round_add(L, self.Kn[round_cnt]))
            L, R = R, L
            res += L + R
        return res

题目将flag加密得到密文,那么自然我们需要做的就是解密。现在来一步一步分析N1ES.py

分析

首先给了key,接着在构造函数后调用了gen_subkey()方法,然后

o = string_to_bits(self.key)

我们来看一下这个方法:

def string_to_bits(data):
    data = [ord(c) for c in data]
    l = len(data) * 8
    result = [0] * l
    pos = 0
    for ch in data:
        for i in range(0,8):
            result[(pos<<3)+i] = (ch>>i) & 1
        pos += 1
    return result

根据名称也能猜出来,大概是将字符串转二进制,因为每个字符占八个位置,将字符串转成ascii码进行左移和按位与运算

result[(pos<<3)+i] = (ch>>i) & 1,是将字符的二进制逐个填入result的操作,例:
ch=w(119,0111 0111),i=3,pos=0,pos<<3+3=3,ch>>3=0000 1110&1=0,最后得出result,前八位为1110 1110,正好是w字符二进制的翻转,每八位代表着一个字符,这就完成了字符串到二进制的转换。

接下来调用了genarate()并且调用了八遍之后加到了k列表上,但是又调用了其他方法:

def permutate(table, block):
	return list(map(lambda x: block[x], table))
def generate(o):
    k = permutate(s_box,o)
    b = []
    for i in range(0, len(k), 7):
        b.append(k[i:i+7] + [1])
    c = []
    for i in range(32):
		pos = 0
		x = 0
		for j in b[i]:
			x += (j<<pos)
			pos += 1
		c.append((0x10001**x) % (0x7f))
    return c
s_box = [54, 132, 138, 83, 16, 73, 187, 84, 146, 30, 95, 21, 148, 63, 65, 189, 188, 151, 72, 161, 116, 63, 161, 91, 37, 24, 126, 107, 87, 30, 117, 185, 98, 90, 0, 42, 140, 70, 86, 0, 42, 150, 54, 22, 144, 153, 36, 90, 149, 54, 156, 8, 59, 40, 110, 56,1, 84, 103, 22, 65, 17, 190, 41, 99, 151, 119, 124, 68, 17, 166, 125, 95, 65, 105, 133, 49, 19, 138, 29, 110, 7, 81, 134, 70, 87, 180, 78, 175, 108, 26, 121, 74, 29, 68, 162, 142, 177, 143, 86, 129, 101, 117, 41, 57, 34, 177, 103, 61, 135, 191, 74, 69, 147, 90, 49, 135, 124, 106, 19, 89, 38, 21, 41, 17, 155, 83, 38, 159, 179, 19, 157, 68, 105, 151, 166, 171, 122, 179, 114, 52, 183, 89, 107, 113, 65, 161, 141, 18, 121, 95, 4, 95, 101, 81, 156, 17, 190, 38, 84, 9, 171, 180, 59, 45, 15, 34, 89, 75, 164, 190, 140, 6, 41, 188, 77, 165, 105, 5, 107, 31, 183, 107, 141, 66, 63, 10, 9, 125, 50, 2, 153, 156, 162, 186, 76, 158, 153, 117, 9, 77, 156, 11, 145, 12, 169, 52, 57, 161, 7, 158, 110, 191, 43, 82, 186, 49, 102, 166, 31, 41, 5, 189, 27]

用一个匿名函数和map映射来将result重新打乱,按照s_box列表中给出的顺序进行重新排序,进入for循环,每7个后再加上一个1构成八位,第二个for循环中,b中32组元素,而每一组元素都有八位,每一个进行运算后在放到C中。

现在在来看

def gen_subkey(self):
        o = string_to_bits(self.key)
        k = []
        for i in range(8):
	        o = generate(o)
        	k.extend(o)
        	o = string_to_bits([chr(c) for c in o[0:24]])
        self.Kn = []
        for i in range(32):
            self.Kn.append(map(chr, k[i * 8: i * 8 + 8]))
        return 

先将o进行genarate(),然后放到k列表中,再将o的前24个变成字符后在转为二进制,重新赋值给o,这样重复八次,每次generate()都是产生了32个数字,这样一共32*8个数字,在进入第二个for循环中,分为32组,将每组的数字变成字符后给K,这样K一共有32个元素

看完这些后我们回到最后的关键上,就是encrypt是如何工作的:

看到这里,先要介绍一下什么是Feistel加密结构

构造过程:

令F 为轮函数;令K1,K2,……,Kn 分别为第1,2,……,n 轮的子**。那么基本构造过程如下:

(1)将明文信息均分为两块:(L0,R0);

(2)在每一轮中,进行如下运算(i 为当前轮数):

Li+1 = Ri;

Ri+1 = Li ⊕F (Ri,Ki)。(其中⊕为异或操作)

所得的结果即为:(Ri+1,Li+1)。

解密过程:

对于密文(Rn+1,Ln+1),我们将i 由n 向0 进行,即, i = n,n-1,……,0。然后对密文进行加密的逆向操作,如下:

(1)Ri = Li+1;

(2)Li = Ri+1⊕F (Li+1,Ki)。(其中⊕为异或操作)

所得结果为(L0,R0),即原来的明文信息。

python(N1CTF)详解

知道了这种加密结构后我们再来看

def encrypt(self, plaintext):
        if (len(plaintext) % 16 != 0 or isinstance(plaintext, bytes) == False):
            raise Exception("plaintext must be a multiple of 16 in length")
        res = ''
        for i in range(len(plaintext) / 16):
            block = plaintext[i * 16:(i + 1) * 16]
            L = block[:8]
            R = block[8:]
            for round_cnt in range(32):
                L, R = R, (round_add(L, self.Kn[round_cnt]))
            L, R = R, L
            res += L + R
        return res

首先明文肯定是16的倍数,然后将明文分成len(plaintext)/16组,每组分为L,R两边,在循环中,第一次L1=R1,R1=E1,第二次L2=R1=E1,R2=E2,…进行32次循环后,L32=E31,R32=E32,res = E32+E31

只有这段才是真正的加密过程(Feistel加密结构),之前的所有都是为了产生self.Kn,为这次加密助力。

最后一次加密是在challenge.py文件中的base64加密。

至此全部的加密过程已经明晰,接下来就是解密了。

真正的加密只在这一个公式:
f = lambda x, y: x + y - 2 * (x & y)

而Feistel解密只要将循环式改为:

for round_cnt in range(32):
    	L, R = R, (round_add(L, self.Kn[31-round_cnt]))
12

利用原式就能进行解密,举个实例演示一下加密和解密:(下面参考了大佬写的,看了好久才想明白,不得不说密码果然很顶)

  • 假设这是最后一次加密循环

假设L31=110(0110 1110),Kn[31]=126(0111 1110)
R32=E32=L31+Kn[31]-2*(L31&Kn[31])=110+126-2*(110&126)=16(0001 0000)
(其中L31=E30)
加密后得L32=R31=E31,R32=E32

  • 这是第一次解密循环

    L0=E32,R0=E31(因为之前加密后还有一次互换的操作)
    L1=R0=E31
    R1=L0+Kn[31]-2*(L0&Kn[31])
    现在已知的是Kn[31]=126,因为整个Kn表都可得出。以及L0,这里L0是flag加密后的左边部分,题目已给出。L0=E32=16.
    R1=16+126-2*(16&126)=110
    解密后的结果正好就是L31,即E30
    这次解密后得到
    L1=E31,R1=E30

    由结果可看出,只要逆一下加密的kn顺序就变成了解密的kn顺序,这是feistel神奇的地方。

    最后只需要加一个decrypt即可:

      def decrypt(self,plaintext):
            if (len(plaintext) % 16 != 0 or isinstance(plaintext, bytes) == False):
                raise Exception("plaintext must be a multiple of 16 in length")
            res = ''
            for i in range(len(plaintext) / 16):
                block = plaintext[i * 16:(i + 1) * 16]
                L = block[:8]
                R = block[8:]
                for round_cnt in range(32):
                    L, R = R, (round_add(L, self.Kn[31-round_cnt]))
                L, R = R, L
                res += L + R
            return res
    
    #challenge.py
    from N1ES import N1ES
    import base64
    key = "wxy191iss00000000000cute"
    n1es = N1ES(key)
    flag = "N1CTF{*****************************************}"
    cipher = n1es.encrypt(flag)
    print base64.b64encode(cipher)  # HRlgC2ReHW1/WRk2DikfNBo1dl1XZBJrRR9qECMNOjNHDktBJSxcI1hZIz07YjVx
    bdecodecipher = base64.b64decode(cipher)
    flag = n1es.decrypt(bdecodecipher)
    

python(N1CTF)详解

相关标签: 密码学 python