两道密码题[DASCTF五月赛]

RC4流密码结合图像处理，背包算法

Encrypt_img

题目

from numpy import array
from PIL import Image
from secret import Key

Plaintext1 = "RC4IsInteresting"
Plaintext2 = "ThisIsAEasyGame"
cnt = 0


class RC4():
    def __init__(self, Key):
        self.S = [i for i in range(256)]
        self.K = [ord(Key[i % len(Key)])*2 for i in range(256)]
        self.I, self.J = 0, 0
        self.KSA()

    def KSA(self):
        for i in range(256):
            j = (i+self.K[i]+self.S[i]) % 256
            self.S[i], self.S[j] = self.S[j], self.S[i]

    def next(self):
        self.I = (self.I+1) % 256
        self.J = (self.J+self.S[self.I]) % 256
        self.S[self.J], self.S[self.I] = self.S[self.I], self.S[self.J]
        tmp = (self.S[self.J] + self.S[self.I]) % 256
        return self.S[tmp]


class Encrypt():
    def __init__(self, plain):
        global cnt
        cnt += 1
        self.rc4 = RC4(Key)
        self.testRC4(plain)
        flag_file = Image.open(r"flag.png")
        img = array(flag_file)
        self.enc(img)

    def testRC4(self, plain):
        ciphertext = 0
        for i in plain:
            ciphertext = (ciphertext << 8)+ord(i) ^ self.rc4.next()
        print("ciphertext{} = {}".format(cnt, ciphertext))

    def enc(self, img):
        a, b, _ = img.shape
        for x in range(0, a):
            for y in range(0, b):
                pixel = img[x, y]
                for i in range(0, 3):
                    pixel[i] = pixel[i] ^ self.rc4.next()
                img[x][y] = pixel
        enc = Image.fromarray(img)
        enc.save("enc{}.png".format(cnt))


Encrypt(Plaintext1)
Encrypt(Plaintext2)

# ciphertext1 = 12078640933356268898100798377710191641
# ciphertext2 = 79124196547094980420644350061749775

分析

• 先还原出密钥流的前几位，发现cip1比cip2多出来一位

• enc1[0]=img1[0]^keystream[1]

  enc2[0]=img2[0]^keystream[0]

  keystream[1]=enc1[0]^ enc2[0] ^ keystream[0]

  推算出密钥流的下一位，其中keystream[0]就是多出来的一位密钥

• 反复横跳，求解出全部密钥流进行解密

解题

from PIL import Image
from numpy import array
import string
#推出密钥流前几位
ciphertext1 = 12078640933356268898100798377710191641
ciphertext2 = 79124196547094980420644350061749775
cipher1 = bin(ciphertext1)[2:].zfill(128)
cipher2 = bin(ciphertext2)[2:].zfill(120)
c1 = [int(cipher1[i:i + 8], 2) for i in range(0, len(cipher1), 8)]
c2 = [int(cipher2[i:i + 8], 2) for i in range(0, len(cipher2), 8)]

Plaintext1 = "RC4IsInteresting"
Plaintext2 = "ThisIsAEasyGame"

key1 = []
key2 = []
for i in range(len(c1)):
    key1.append(c1[i] ^ ord(Plaintext1[i]))
for i in range(len(c2)):
    key2.append(c2[i] ^ ord(Plaintext2[i]))
keystream=[126]
f1 = Image.open(r"enc1.png")
img1 = array(f1)
f2 = Image.open(r"enc2.png")
img2 = array(f2)
a, b, _ = img1.shape
#推出解密需要的全部密钥流
k=0
for x in range(0,a):
    for y in range(0, b):
        pixel1=img1[x, y]
        pixel2=img2[x,y]
        for i in range(0,3):
            keystream.append(pixel1[i]^pixel2[i]^keystream[k])
            k+=1
#还原图片
k=1
for x in range(0, a):
    for y in range(0, b):
        pixel = img1[x, y]
        for i in range(0, 3):
            pixel[i] = pixel[i] ^ keystream[k]
            k+=1
        img1[x][y] = pixel
dec = Image.fromarray(img1)
dec.save("dec.png")

knapsack

题目

from Crypto.Util.number import *
from functools import reduce

def genKey(length):
    A, B = getPrime(64), getPrime(1025)

    Rn = getPrime(1024)
    key1 = [Rn//2**i for i in range(1, length+1)]
    key2 = [i*A % B for i in key1] 
    return key1,key2


def encrypt(text,key):
    Sum=0
    for i in range(len(text)):
        Sum+=int(text[i])*key[i]
    return Sum

def save(Ciper,Key):
    f1=open("pub.txt","w")
    for i in range(len(Key)):
        f1.write(str(Key[i])+'\n')
    f2=open("cip.txt","w")
    f2.write(hex(Ciper))


FLAG = bin(bytes_to_long(flag.encode()))[2:]
Key1,Key2 = genKey(len(FLAG))
Ciper = encrypt(FLAG,Key1)
save(Ciper,Key2)

知识点

• 背包问题
• Merkle–Hellman

https://wiki.x10sec.org/crypto/asymmetric/knapsack/knapsack/#merklehellman

鸽了