2024-Hgame-week2-wp-crypto

2024-Hgame-week2-wp-crypto

奇怪的图片plus很有意思。

midRSA

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
from Crypto.Util.number import *
from secret import flag
m=bytes_to_long(flag)
p=getPrime(1024)
q=getPrime(1024)
e=5
n=p*q
c=pow(m,e,n)
m0=m>>128

print(f'n={n}')
print(f'c={c}')
print(f'm0={m0}')

"""
n=27814334728135671995890378154778822687713875269624843122353458059697288888640572922486287556431241786461159513236128914176680497775619694684903498070577307810263677280294114135929708745988406963307279767028969515305895207028282193547356414827419008393701158467818535109517213088920890236300281646288761697842280633285355376389468360033584102258243058885174812018295460196515483819254913183079496947309574392848378504246991546781252139861876509894476420525317251695953355755164789878602945615879965709871975770823484418665634050103852564819575756950047691205355599004786541600213204423145854859214897431430282333052121
c=456221314115867088638207203034494636244706611111621723577848729096069230067958132663018625661447131501758684502639383208332844681939698124459188571813527149772292464139530736717619741704945926075632064072125361516435631121845753186559297993355270779818057702973783391589851159114029310296551701456748698914231344835187917559305440269560613326893204748127999254902102919605370363889581136724164096879573173870280806620454087466970358998654736755257023225078147018537101
m0=9999900281003357773420310681169330823266532533803905637
"""

一眼coppersmith，没什么好说的，真要说这里也装不下（

直接上脚本了

sagemath是个好东西

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
from Crypto.Util.number import *
from sage.all import *
from random import *


n=27814334728135671995890378154778822687713875269624843122353458059697288888640572922486287556431241786461159513236128914176680497775619694684903498070577307810263677280294114135929708745988406963307279767028969515305895207028282193547356414827419008393701158467818535109517213088920890236300281646288761697842280633285355376389468360033584102258243058885174812018295460196515483819254913183079496947309574392848378504246991546781252139861876509894476420525317251695953355755164789878602945615879965709871975770823484418665634050103852564819575756950047691205355599004786541600213204423145854859214897431430282333052121
c=456221314115867088638207203034494636244706611111621723577848729096069230067958132663018625661447131501758684502639383208332844681939698124459188571813527149772292464139530736717619741704945926075632064072125361516435631121845753186559297993355270779818057702973783391589851159114029310296551701456748698914231344835187917559305440269560613326893204748127999254902102919605370363889581136724164096879573173870280806620454087466970358998654736755257023225078147018537101
m0=9999900281003357773420310681169330823266532533803905637
m = m0<<128

PR.<x> = PolynomialRing(Zmod(n))
f = (m + x)^5 - c
f = f.monic()
roots = f.small_roots(X = 2^128,beta = 0.4)

m = m + int(roots[0])
print(long_to_bytes(m))

babyRSA

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
from Crypto.Util.number import *
from secret import flag,e
m=bytes_to_long(flag)
p=getPrime(64)
q=getPrime(256)
n=p**4*q
k=getPrime(16)
gift=pow(e+114514+p**k,0x10001,p)
c=pow(m,e,n)
print(f'p={p}')
print(f'q={q}')
print(f'c={c}')
print(f'gift={gift}')
"""
p=14213355454944773291
q=61843562051620700386348551175371930486064978441159200765618339743764001033297
c=105002138722466946495936638656038214000043475751639025085255113965088749272461906892586616250264922348192496597986452786281151156436229574065193965422841
gift=9751789326354522940
"""

这一题我是爆破出的e，但实际上稍微想一想，用逆元是完全可以做的。

但是从时间角度考虑的话，用爆破也无可厚非，但是关键的是要想到如果e大到没法爆破该怎么办，所以还是学一学为好。

众所周知$e$和$p$互素，那么有
$$
e^{p-1} \equiv 1 \quad(\bmod p)
$$
那么就有一种可能使得
$$
e^{65537x} \equiv e \quad(\bmod p)
$$
此时$65537x=1+k(p-1)$

这个形式很接近逆元的形式 转换一下 $65537x=1(\bmod p-1)$

65537对$p-1$求逆元就可以了

（题解里面为什么会对phi求逆元呢，虽然也是对的但是不明白思路

然后就是一个域下开高次根，比较模板

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
from Crypto.Util.number import *
from tqdm import tqdm
p=14213355454944773291
q=61843562051620700386348551175371930486064978441159200765618339743764001033297
c=105002138722466946495936638656038214000043475751639025085255113965088749272461906892586616250264922348192496597986452786281151156436229574065193965422841
phi=p^3*(p-1)*(q-1)
gift=9751789326354522940
d1=inverse(0x10001,p-1)
e=pow(gift,d1,p)-114514
n=p^4*q
K=Zmod(n)
x=K(c).nth_root(e,all=True)
for i in tqdm(x):
	m=long_to_bytes(int(i))
	if b"hgame" in m:
		print(m)
		break

Backpack

一个构造LLL的背包密码题，比较模板，不多赘述

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
from Crypto.Util.number import *
from sage.all import *
from random import *
import hashlib

from Crypto.Util.number import *
c = 1202548196826013899006527314947
a = [74763079510261699126345525979, 51725049470068950810478487507, 47190309269514609005045330671, 64955989640650139818348214927, 68559937238623623619114065917, 72311339170112185401496867001, 70817336064254781640273354039, 70538108826539785774361605309, 43782530942481865621293381023, 58234328186578036291057066237, 68808271265478858570126916949, 61660200470938153836045483887, 63270726981851544620359231307, 42904776486697691669639929229, 41545637201787531637427603339, 74012839055649891397172870891, 56943794795641260674953676827, 51737391902187759188078687453, 49264368999561659986182883907, 60044221237387104054597861973, 63847046350260520761043687817, 62128146699582180779013983561, 65109313423212852647930299981, 66825635869831731092684039351, 67763265147791272083780752327, 61167844083999179669702601647, 55116015927868756859007961943, 52344488518055672082280377551, 52375877891942312320031803919, 69659035941564119291640404791, 52563282085178646767814382889, 56810627312286420494109192029, 49755877799006889063882566549, 43858901672451756754474845193, 67923743615154983291145624523, 51689455514728547423995162637, 67480131151707155672527583321, 59396212248330580072184648071, 63410528875220489799475249207, 48011409288550880229280578149, 62561969260391132956818285937, 44826158664283779410330615971, 70446218759976239947751162051, 56509847379836600033501942537, 50154287971179831355068443153, 49060507116095861174971467149, 54236848294299624632160521071, 64186626428974976108467196869]
n = len(a)
L = Matrix(ZZ, n+1, n+1)

for i in range(n):
    L[i,i] = 2
    L[i,-1] = a[i]
    L[-1,i] = 1
L[-1,-1] = c

res = L.LLL()
a = list(res[0])
for i in range(len(a)):
    if a[i] == -1:
        a[i] = 0
print(a)


a = 0b111101000010110101010001010011000111000100100001
n = 0
alist = [1, 0, 0, 0, 0, 1, 0, 0, 1, 0, 0, 0, 1, 1, 1, 0, 0, 0, 1, 1, 0, 0, 1, 0, 1, 0, 0, 0, 1, 0, 1, 0, 1, 0, 1, 1, 0, 1, 0, 0, 0, 0, 1, 0, 1, 1, 1, 1]
anum=[74763079510261699126345525979, 51725049470068950810478487507, 47190309269514609005045330671, 64955989640650139818348214927, 68559937238623623619114065917, 72311339170112185401496867001, 70817336064254781640273354039, 70538108826539785774361605309, 43782530942481865621293381023, 58234328186578036291057066237, 68808271265478858570126916949, 61660200470938153836045483887, 63270726981851544620359231307, 42904776486697691669639929229, 41545637201787531637427603339, 74012839055649891397172870891, 56943794795641260674953676827, 51737391902187759188078687453, 49264368999561659986182883907, 60044221237387104054597861973, 63847046350260520761043687817, 62128146699582180779013983561, 65109313423212852647930299981, 66825635869831731092684039351, 67763265147791272083780752327, 61167844083999179669702601647, 55116015927868756859007961943, 52344488518055672082280377551, 52375877891942312320031803919, 69659035941564119291640404791, 52563282085178646767814382889, 56810627312286420494109192029, 49755877799006889063882566549, 43858901672451756754474845193, 67923743615154983291145624523, 51689455514728547423995162637, 67480131151707155672527583321, 59396212248330580072184648071, 63410528875220489799475249207, 48011409288550880229280578149, 62561969260391132956818285937, 44826158664283779410330615971, 70446218759976239947751162051, 56509847379836600033501942537, 50154287971179831355068443153, 49060507116095861174971467149, 54236848294299624632160521071, 64186626428974976108467196869]
for i in range(48):
    n+=alist[i]*anum[i]
print(n)
print(int(a))
flag='hgame{'+hashlib.sha256(str(a).encode()).hexdigest()+'}'
print(flag)

#但是我就是想问为什么这么做啊？

详见《格理论与密码学》5.3.4 基于格的背包密码学分析，笔者水平有限 T-T

奇怪的图片plus

这也是hgame2024四周以来做出人数最少的密码题

题目太长，抓不到重点，笔者也是反反复复看了四天才发现破解方法，其实没有什么技术上的难度，只不过是思路不好把握。

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
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
#client.py
import websocket # pip install websocket-client
import re
from PIL import Image # pip install pillow
import struct
import threading


def image_to_bytes(image):
    width, height = image.size
    pixel_bytes = []
    for y in range(height):
        for x in range(width):
            pixel = image.getpixel((x, y))
            pixel_bytes.extend(struct.pack('BBB', *pixel))
    image_bytes = bytes(pixel_bytes)
    return image_bytes

def handle_input(ws):
    try:
        while True:
            message = input()
            if message.lower() == 'exit':
                ws.close()
                break
            elif message.lower() == 'help':
                print("send_img: send_img <path_to_img_1> <path_to_img_2>")
                print("check: check")
                print("help: help")
                print("exit: exit")
            elif message[:8] == 'send_img':
                try:
                    pattern = re.compile(r'\s(.*?)\s(.*?)$')
                    match = pattern.search(message)
                    if match:
                        path_1 = match.group(1)
                        path_2 = match.group(2)
                        image_1 = Image.open(path_1)
                        image_2 = Image.open(path_2)
                        ws.send_binary(b"B1" + image_1.width.to_bytes(4, "big") + image_1.height.to_bytes(4, "big") + image_to_bytes(image_1))
                        ws.send_binary(b"B2" + image_2.width.to_bytes(4, "big") + image_2.height.to_bytes(4, "big") + image_to_bytes(image_2))
                    else:
                        raise FileNotFoundError("Command format error")
                except FileNotFoundError as err:
                    print(err)
            elif message == 'check':
                ws.send_binary(b"B3")
    except websocket.WebSocketException as err:
        print(err)

def handle_recv(ws):
    try:
        while True:
            msg = ws.recv()
            print("Msg from server: {}".format(msg))
    except websocket.WebSocketException as err:
        print(err)

def main():
    # uri = "ws://localhost:10002"
    uri = input("input uri: ")
    print("type 'help' to get help")
    ws = websocket.create_connection(uri)
    input_thread = threading.Thread(target=handle_input, args=(ws,), daemon=True)
    recv_thread = threading.Thread(target=handle_recv, args=(ws,), daemon=True)
    recv_thread.start()
    input_thread.start()
    recv_thread.join()
    input_thread.join()

if __name__ == "__main__":
    main()
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
49
50
51
52
53
54
55
56
57
#encryption.py
from Crypto.Cipher import AES
from Crypto.Util.Padding import pad
import os
from PIL import Image, ImageFont, ImageDraw
import struct
import random


def image_to_bytes(image):
    width, height = image.size
    pixel_bytes = []
    for y in range(height):
        for x in range(width):
            pixel = image.getpixel((x, y))
            pixel_bytes.extend(struct.pack('BBB', *pixel))
    image_bytes = bytes(pixel_bytes)
    return image_bytes


def bytes_to_image(image_bytes, width, height):
    pixel_bytes = list(image_bytes)
    reconstructed_image = Image.new('RGB', (width, height))
    for y in range(height):
        for x in range(width):
            start = (y * width + x) * 3
            pixel = struct.unpack('BBB', bytes(pixel_bytes[start:start + 3]))
            reconstructed_image.putpixel((x, y), pixel)
    return reconstructed_image


def draw_text(image, width, height, token):
    font_size = 20
    font = ImageFont.truetype("arial.ttf", font_size)
    text_color = (255, 255, 255)
    x = 0
    y = (height // 2) - 10
    draw = ImageDraw.Draw(image)
    draw.text((x, y), token, font=font, fill=text_color)
    pixels = image.load()
    for x in range(width):
        for y in range(height):
            if pixels[x, y] != (0, 0, 0):
                pixels[x, y] = (random.randint(0, 255), random.randint(0, 255), random.randint(0, 255))
    return image


flag = "hgame{fake_flag}"
flag_image = Image.new("RGB", (200, 150), "black")
flag_image = draw_text(flag_image, 200, 150, flag[6:-1])
key = os.urandom(16) # gift
iv = os.urandom(16)
F = AES.new(key=key, mode=AES.MODE_OFB, iv=iv)
m = pad(image_to_bytes(flag_image), F.block_size)
c = F.encrypt(m)
encrypted_image = bytes_to_image(c, 200, 150)
encrypted_image.save("encrypted_flag.png")
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
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
#server.py
import asyncio
import os
import websockets
from PIL import Image
import struct
from Crypto.Cipher import AES
from Crypto.Util.Padding import pad


gift = b''.hex() # hide here
pos_list = [] # hide here


def bytes_to_image(image_bytes, width, height):
    pixel_bytes = list(image_bytes)
    reconstructed_image = Image.new('RGB', (width, height))
    for y in range(height):
        for x in range(width):
            start = (y * width + x) * 3
            pixel = struct.unpack('BBB', bytes(pixel_bytes[start:start + 3]))
            reconstructed_image.putpixel((x, y), pixel)
    return reconstructed_image


def xor_images(image1, image2):
    if image1.size != image2.size:
        raise ValueError("Images must have the same dimensions")
    xor_image = Image.new("RGB", image1.size)
    pixels1 = image1.load()
    pixels2 = image2.load()
    xor_pixels = xor_image.load()
    for x in range(image1.size[0]):
        for y in range(image1.size[1]):
            r1, g1, b1 = pixels1[x, y]
            r2, g2, b2 = pixels2[x, y]
            xor_pixels[x, y] = (r1 ^ r2, g1 ^ g2, b1 ^ b2)
    return xor_image


def check_pixels(image, positions):
    pixels = image.load()
    count = 0
    for x in range(image.size[0]):
        for y in range(image.size[1]):
            if (x, y) in positions:
                if pixels[x, y] != (0, 0, 0):
                    return False
            else:
                if pixels[x, y] == (0, 0, 0):
                    count += 1
                    if count == 10:
                        return False
    return True


async def handle_client(websocket):
    await websocket.send("Pls send two images that meet the following conditions")
    await websocket.send("The black pixels in 'xor_images(image_1, image_2)' should match those in 'target'")
    await websocket.send("Note: The server has scaling function during validation! XD")
    image_1, image_2 = None, None
    image_1_w, image_1_h, image_2_w, image_2_h = 0, 0, 0, 0
    async for message_raw in websocket:
        try:
            if message_raw[:2] == b"B1":
                image_1_w = int.from_bytes(message_raw[2:6], "big")
                image_1_h = int.from_bytes(message_raw[6:10], "big")
                image_1 = message_raw[6:]
                await websocket.send("Image_1 received")
            elif message_raw[:2] == b"B2":
                image_2_w = int.from_bytes(message_raw[2:6], "big")
                image_2_h = int.from_bytes(message_raw[6:10], "big")
                image_2 = message_raw[6:]
                await websocket.send("Image_2 received")
            elif message_raw[:2] == b"B3":
                if image_1 and image_2:
                    F = AES.new(key=os.urandom(16), mode=AES.MODE_ECB)
                    image_1_encrypted = bytes_to_image(F.encrypt(pad(image_1, F.block_size)), image_1_w, image_1_h)
                    image_2_encrypted = bytes_to_image(F.encrypt(pad(image_2, F.block_size)), image_2_w, image_2_h)
                    xor_image = xor_images(image_1_encrypted, image_2_encrypted)
                    xor_image = xor_image.resize((16, 9), Image.NEAREST)
                    xor_image.show()
                    if check_pixels(xor_image, pos_list):
                        await websocket.send("Here is your gift: {}".format(gift))
                    else:
                        await websocket.send("Verification failed")
                else:
                    await websocket.send("Pls send two images first!!")
        except ValueError as err:
            await websocket.send(err)

async def main():
    server = await websockets.serve(handle_client, "localhost", 10002)
    await server.wait_closed()


asyncio.run(main())

到底要让我们干什么呢？

上传两张图片给服务器，服务器会先AES-ECB加密两张图片，然后异或两张加密图片(指异或图片的像素)，最后把得到的图片恢复成16*9，如果这张图片中的黑色像素和target.png完全对应，那么就会给你一个在encryption.py中用到的key，最后用这个key去破解flag。

突破点是什么？

其实看来看去，没有什么地方不严谨，最有问题的地方就是用了ecb分块，那就试试从ecb分块入手。

如果是ecb分块的话，那就意味着原始图片中相同的块加密的结果一定相同，它采用16字节分块，也就意味着每5个像素又一个字节为一组。

如果是异或图片，那最后的异或结果其实只能是黑色，其他颜色都是不可控的，这也在题目中有所提示，只要求黑色像素对应。

仔细揣摩一番我们会发现，若想让位置不同但颜⾊相同的像素在加密后都得到相同的结果，我们就要把一个像素扩大为至少六个像素(16个字节)，所以只要上传扩大到800*9的纯黑色图片和同样扩大之后的target.png，经过服务器的resize()，就可以拿到key。

（贴个官方解吧，我的脚本不见了）

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
49
50
51
52
53
54
55
56
57
from Crypto.Cipher import AES
from Crypto.Util.Padding import pad
import os
from PIL import Image, ImageDraw
import struct
def xor(a, b):
	result = bytes(x ^ y for x, y in zip(a, b))
	return result
def xor_images(image1, image2):
	if image1.size != image2.size:
		raise ValueError("Images must have the same dimensions.")
    xor_image = Image.new("RGB", image1.size)
    pixels1 = image1.load()
    pixels2 = image2.load()
    xor_pixels = xor_image.load()
    for x in range(image1.size[0]):
    	for y in range(image1.size[1]):
    		r1, g1, b1 = pixels1[x, y]
    		r2, g2, b2 = pixels2[x, y]
    		xor_pixels[x, y] = (r1 ^ r2, g1 ^ g2, b1 ^ b2)
    return xor_image
def image_to_bytes(image):
    width, height = image.size
    pixel_bytes = []
    for y in range(height):
    	for x in range(width):
    		pixel = image.getpixel((x, y))
    		pixel_bytes.extend(struct.pack('BBB', *pixel))
    image_bytes = bytes(pixel_bytes)
    return image_bytes
def bytes_to_image(image_bytes, width, height):
	pixel_bytes = list(image_bytes)
	reconstructed_image = Image.new('RGB', (width, height))
	for y in range(height):
		for x in range(width):
			start = (y * width + x) * 3
			pixel = struct.unpack('BBB', bytes(pixel_bytes[start:start + 3]))
			reconstructed_image.putpixel((x, y), pixel)
	return reconstructed_image
# black pixels in target.png
pos_list = [(1, 1), (1, 2), (1, 3), (1, 4), (1, 5), (1, 6), (1, 7), (2, 1),
(2, 4), (3, 1), (3, 4), (4, 1), (4, 2), (4, 3), (4, 4), (4, 5), (4, 6), (4,
7), (6, 1), (6, 2), (6, 3), (6, 4), (6, 5), (6, 6), (6, 7), (7, 1), (7, 4),
(7, 7), (8, 1), (8, 4), (8, 7), (9, 1), (9, 4), (9, 7), (11, 2), (11, 3), (11,
7), (12, 1), (12, 4), (12, 7), (13, 1), (13, 4), (13, 7), (14, 1), (14, 5),
(14, 6)]
image_1 = Image.new("RGB", (16, 9), "black")
image_2 = Image.new("RGB", (16, 9), "white")
draw_1 = ImageDraw.Draw(image_1)
draw_2 = ImageDraw.Draw(image_2)
for pos in pos_list:
draw_1.point(pos, (255, 255, 255))
draw_2.point(pos, (255, 255, 255))
image_1 = image_1.resize((48 * 16, 48 * 9), Image.NEAREST)
image_2 = image_2.resize((48 * 16, 48 * 9), Image.NEAREST)
image_1.save("image_1.png")
image_2.save("image_2.png")

Msg from server: Here is your gift: 8693346e81fa05d8817fd2550455cdf6

第二步就相对简单很多

img

由ofb模式我们发现，我们已知部分明文，那么将明文前16字节和密文前16字节异或就是加密一次的iv向量，且key已知，我们就有办法解密出原始的iv向量。

还是上官方解，，

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
from Crypto.Cipher import AES
from PIL import Image
import struct
def xor(a, b):
    result = bytes(x ^ y for x, y in zip(a, b))
    return result
def image_to_bytes(image):
    width, height = image.size
    pixel_bytes = []
    for y in range(height):
    	for x in range(width):
    		pixel = image.getpixel((x, y))
    		pixel_bytes.extend(struct.pack('BBB', *pixel))
    image_bytes = bytes(pixel_bytes)
    return image_bytes
def bytes_to_image(image_bytes, width, height):
    pixel_bytes = list(image_bytes)
    reconstructed_image = Image.new('RGB', (width, height))
    for y in range(height):
    	for x in range(width):
    		start = (y * width + x) * 3
    		pixel = struct.unpack('BBB', bytes(pixel_bytes[start:start + 3]))
    		reconstructed_image.putpixel((x, y), pixel)
    return reconstructed_image
key = b'\x86\x934n\x81\xfa\x05\xd8\x81\x7f\xd2U\x04U\xcd\xf6' # gift
encrypted_image = Image.open("encrypted_flag.png")
c = image_to_bytes(encrypted_image)
iv_ = xor(c[:16], b"\x00" * 16)
F = AES.new(key=key, mode=AES.MODE_OFB, iv=iv_)
m_ = F.decrypt(c[16:])
bytes_to_image((b"\x00" * 16) + m_, 200, 150).show()
#CTF #Crypto #Web #Misc #Hgame
2024-Hgame-week2-wp-crypto
https://py-thok.github.io/2024/02/25/2024-Hgame-week2-wp-crypto/
作者
PYthok-Ptk
发布于
2024年2月25日
许可协议