2024-Hgame-week1-wp-crypto

2024-Hgame-week1-wp-crypto

简单写写。

ezRSA

题目描述：一个简单的RSA

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
from Crypto.Util.number import *
from secret import flag
m=bytes_to_long(flag)
p=getPrime(1024)
q=getPrime(1024)
n=p*q
phi=(p-1)*(q-1)
e=0x10001
c=pow(m,e,n)
leak1=pow(p,q,n)
leak2=pow(q,p,n)

print(f'leak1={leak1}')
print(f'leak2={leak2}')
print(f'c={c}')

"""

leak1=149127170073611271968182576751290331559018441805725310426095412837589227670757540743929865853650399839102838431507200744724939659463200158012469676979987696419050900842798225665861812331113632892438742724202916416060266581590169063867688299288985734104127632232175657352697898383441323477450658179727728908669
leak2=116122992714670915381309916967490436489020001172880644167179915467021794892927977272080596641785569119134259037522388335198043152206150259103485574558816424740204736215551933482583941959994625356581201054534529395781744338631021423703171146456663432955843598548122593308782245220792018716508538497402576709461
c=10529481867532520034258056773864074017027019578041866245400647840230251661652999709715919620810933437191661180003295923273655675729588558899592524235622728816065501918076120812236580344991140980991532347991252705288633014913479970610056845543523591324177567061948922552275235486615514913932125436543991642607028689762693617305246716492783116813070355512606971626645594961850567586340389705821314842096465631886812281289843132258131809773797777049358789182212570606252509790830994263132020094153646296793522975632191912463919898988349282284972919932761952603379733234575351624039162440021940592552768579639977713099971

"""

$p$和$q$互素，所以由费马小定理
$$
p^{q-1} \equiv 1 \quad(\bmod q)
$$
转化一下。
$$
p^{q} \equiv p \quad(\bmod pq)
$$
所以leak1=p， leak2=q.

比较简单。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
from Crypto.Util.number import *
leak1=1491271700736112719681825767512903315590184418057253104260954128375892276
7075754074392986585365039983910283843150720074472493965946320015801246967697998
7696419050900842798225665861812331113632892438742724202916416060266581590169063
867688299288985734104127632232175657352697898383441323477450658179727728908669
leak2=1161229927146709153813099169674904364890200011728806441671799154670217948
9292797727208059664178556911913425903752238833519804315220615025910348557455881
6424740204736215551933482583941959994625356581201054534529395781744338631021423
703171146456663432955843598548122593308782245220792018716508538497402576709461
c=10529481867532520034258056773864074017027019578041866245400647840230251661652
9997097159196208109334371916611800032959232736556757295885588995925242356227288
1606550191807612081223658034499114098099153234799125270528863301491347997061005
6845543523591324177567061948922552275235486615514913932125436543991642607028689
7626936173052467164927831168130703555126069716266455949618505675863403897058213
1484209646563188681228128984313225813180977379777704935878918221257060625250979
0830994263132020094153646296793522975632191912463919898988349282284972919932761
952603379733234575351624039162440021940592552768579639977713099971
n=leak1*leak2
phi=(leak1-1)*(leak2-1)
d=inverse(0x10001,phi)
flag=long_to_bytes(pow(c,d,n))
print(flag)

ezMath

题目描述：一个简单的数学题

pell方程与连分数。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
from Crypto.Util.number import *
from Crypto.Cipher import AES
import random,string
from secret import flag,y,x
def pad(x):
    return x+b'\x00'*(16-len(x)%16)
def encrypt(KEY):
    cipher= AES.new(KEY,AES.MODE_ECB)
    encrypted =cipher.encrypt(flag)
    return encrypted
D = 114514
assert x**2 - D * y**2 == 1
flag=pad(flag)
key=pad(long_to_bytes(y))[:16]
enc=encrypt(key)
print(f'enc={enc}')
#enc=b"\xce\xf1\x94\x84\xe9m\x88\x04\xcb\x9ad\x9e\x08b\xbf\x8b\xd3\r\xe2\x81\x17g\x9c\xd7\x10\x19\x1a\xa6\xc3\x9d\xde\xe7\xe0h\xed/\x00\x95tz)1\\\t8:\xb1,U\xfe\xdec\xf2h\xab`\xe5'\x93\xf8\xde\xb2\x9a\x9a"

引用一下oiwiki。

Pell 方程 - OI Wiki (oi-wiki.org)

定理：记 $x^{2}-D y^{2}=s$。如果有$|s|<\sqrt{D}$，则$\frac{x}{y}$ 一定是$\sqrt{D}$的渐进分数。

证明：分情况讨论。

当$s>0$时，根据，$x^{2}-D y^{2}>0$，有$x>y\sqrt{D}$。并且有
$$
\begin{aligned}\left|\frac xy-\sqrt{D}\right|&=\frac s{y(x+y\sqrt{D})}<\frac s{2y^2\sqrt{D}}<\frac1{2y^2}\end{aligned}
$$
此时根据勒让德判别法，$\frac{x}{y}$是$\sqrt{D}$的渐进分数。

#怎么判别的？

img

摘自《公钥密码学的数学基础》。

所以直接在sagemath跑连分数即可。

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
from Crypto.Util.number import *
from Crypto.Cipher import AES
enc=b"\xce\xf1\x94\x84\xe9m\x88\x04\xcb\x9ad\x9e\x08b\xbf\x8b\xd3\r\xe2\x81\x17
g\x9c\xd7\x10\x19\x1a\xa6\xc3\x9d\xde\xe7\xe0h\xed/\x00\x95tz)1\\\t8:\xb1,U\xfe
\xdec\xf2h\xab`\xe5'\x93\xf8\xde\xb2\x9a\x9a"
def solve_pell(N, num = 100):
	c = continued_fraction(sqrt(N))
	for i in range(num):
		y = c.denominator(i)
		x = c.numerator(i)
		if x^2 - N * y^2 == 1:
			return x, y
	return None, None
def pad(x):
	return x+b'\x00'*((16-len(x))%16)
def decrypt(KEY):
	cipher= AES.new(KEY,AES.MODE_ECB)
	flag =cipher.decrypt(enc)
	return flag
N = 114514
x,y=solve_pell(N)
print(x,y)
y=pad(long_to_bytes(y))[:16]
flag=decrypt(y)
print(flag)

ezPRNG

题目描述：一个简单的随机数

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
from Crypto.Util.number import *
import uuid
def PRNG(R,mask):
    nextR = (R << 1) & 0xffffffff
    i=(R&mask)&0xffffffff
    nextbit=0
    while i!=0:
        nextbit^=(i%2)
        i=i//2
    nextR^=nextbit 
    return (nextR,nextbit)

R=str(uuid.uuid4())
flag='hgame{'+R+'}'
print(flag)
R=R.replace('-','')
Rlist=[int(R[i*8:i*8+8],16) for i in range(4)]

mask=0b10001001000010000100010010001001
output=[]
for i in range(4):
    R=Rlist[i]
    out=''
    for _ in range(1000):
        (R,nextbit)=PRNG(R,mask)
        out+=str(nextbit)
    output.append(out)

print(f'output={output}')
#output=['1111110110111011110000101011010001000111111001111110100101000011110111111100010000111110110111100001001000101101011110111100010010100000011111101101110101011010111000000011110000100011101111011011000100101100110100101110001010001101101110000010001000111100101010010110110111101110011011001011111011010101011000011011000111011011111001101010111100101100110001011010010101110011101001100111000011110111000001101110000001111100000100000101111100010110111001110011010000011011110110011000001101011111111010110011010111010101001000010011110110011110110101011110111010011010010110111111010011101000110101111101111000110011111110010110000100100100101101010101110010101001101010101011110111010011101110000100101111010110101111110001111111110010000000001110011100100001011111110100111011000101001101001110010010001100011000001101000111010010000101101111101011000000101000001110001011001010010001000011000000100010010010010111010011111111011100100100100101111111001110000111110110001111001111100101001001100010', '0010000000001010111100001100011101111101111000100100111010101110010110011001011110101100011101010000001100000110000000011000000110101111111011100100110111011010000100011111000111001000101001110010110010001000110010101011110011101000011111101101011000011110001101011111000110111000011000110011100100101100111100000100100101111001011101110001011011111111011010100010111011000010010101110110100000110100000100010101000010111101001000011000000000111010010101010111101101011111011001000101000100011001100101010110110001010010001010110111011011111101011100111001101111111111010011101111010010011110011111110100110011111110110001000111100010111000101111000011011011111101110101110100111000011100001010110111100011001011010011010111000110101100110100011101101011101000111011000100110110001100110101010110010011011110000111110100111101110000100010000111100010111000010000010001111110110100001000110110100100110110010110111010011111101011110000011101010100110101011110000110101110111011010110110000010000110001', '1110110110010001011100111110111110111001111101010011001111100100001000111001101011010100010111110101110101111010111100101100010011001001011101000101011000110111000010000101001000100111010110001010000111110110111000011001100010001101000010001111111100000101111000100101000000001001001001101110000100111001110001001011010111111010111101101101001110111010111110110011001000010001010100010010110110101011100000101111100100110011110001001001111100101111001111011011010111001001111010001100110001100001100000110000011111010100101111000000101011111010000111110000101111100010000010010111010110100101010101001111100101011100011001001011000101010101001101100010110000010001110011110011100111000110101010111010011010000001100001011000011101101000000011111000101111101011110011000011011000100100110111010011001111101100101100011000101001110101111001000010110010111101110110010101101000000101001011000000001110001110000100000001001111100011010011000000011011101111101001111110001011101100000010001001010011000001', '0001101010101010100001001001100010000101010100001010001000100011101100110001001100001001110000110100010101111010110111001101011011101110000011001000100100101000011011101000111001001010011100010001010110111011100100111110111001010010111010100000100111110101110010010110100001000010010001101111001110100010001011101100111011101011101100100101011010101000101001000101110011011111110110011111111100000000011100000010011000110001000110101010001011000010101000110000101001110101010111011010010111011001010011100010101001100110000110101100010000100110101110100001101001011011110011100110011001010110100101010111110110111100000111010001111101110000000000111011011101000011001010010111001110111000100111011110100101000100011011101100011111000101110110110111111001111000000011100011000010000101001011001101110101000010101001000100110010000101001111100101000001011011010011110001101000001101111010100101001100010100000111000011110101010100011011001110001011110111010111011010101101100000110000001010010101111011']

深入分析CTF中的LFSR类题目（一）-安全客 - 安全资讯平台 (anquanke.com)

几乎是原题。

上面的链接其实讲的很清楚了hh，我就不东施效颦了

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
from Crypto.Util.number import *
output=['1111110110111011110000101011010001000111111001111110100101000011110111111100010000111110110111100001001000101101011110111100010010100000011111101101110101011010111000000011110000100011101111011011000100101100110100101110001010001101101110000010001000111100101010010110110111101110011011001011111011010101011000011011000111011011111001101010111100101100110001011010010101110011101001100111000011110111000001101110000001111100000100000101111100010110111001110011010000011011110110011000001101011111111010110011010111010101001000010011110110011110110101011110111010011010010110111111010011101000110101111101111000110011111110010110000100100100101101010101110010101001101010101011110111010011101110000100101111010110101111110001111111110010000000001110011100100001011111110100111011000101001101001110010010001100011000001101000111010010000101101111101011000000101000001110001011001010010001000011000000100010010010010111010011111111011100100100100101111111001110000111110110001111001111100101001001100010', '0010000000001010111100001100011101111101111000100100111010101110010110011001011110101100011101010000001100000110000000011000000110101111111011100100110111011010000100011111000111001000101001110010110010001000110010101011110011101000011111101101011000011110001101011111000110111000011000110011100100101100111100000100100101111001011101110001011011111111011010100010111011000010010101110110100000110100000100010101000010111101001000011000000000111010010101010111101101011111011001000101000100011001100101010110110001010010001010110111011011111101011100111001101111111111010011101111010010011110011111110100110011111110110001000111100010111000101111000011011011111101110101110100111000011100001010110111100011001011010011010111000110101100110100011101101011101000111011000100110110001100110101010110010011011110000111110100111101110000100010000111100010111000010000010001111110110100001000110110100100110110010110111010011111101011110000011101010100110101011110000110101110111011010110110000010000110001', '1110110110010001011100111110111110111001111101010011001111100100001000111001101011010100010111110101110101111010111100101100010011001001011101000101011000110111000010000101001000100111010110001010000111110110111000011001100010001101000010001111111100000101111000100101000000001001001001101110000100111001110001001011010111111010111101101101001110111010111110110011001000010001010100010010110110101011100000101111100100110011110001001001111100101111001111011011010111001001111010001100110001100001100000110000011111010100101111000000101011111010000111110000101111100010000010010111010110100101010101001111100101011100011001001011000101010101001101100010110000010001110011110011100111000110101010111010011010000001100001011000011101101000000011111000101111101011110011000011011000100100110111010011001111101100101100011000101001110101111001000010110010111101110110010101101000000101001011000000001110001110000100000001001111100011010011000000011011101111101001111110001011101100000010001001010011000001', '0001101010101010100001001001100010000101010100001010001000100011101100110001001100001001110000110100010101111010110111001101011011101110000011001000100100101000011011101000111001001010011100010001010110111011100100111110111001010010111010100000100111110101110010010110100001000010010001101111001110100010001011101100111011101011101100100101011010101000101001000101110011011111110110011111111100000000011100000010011000110001000110101010001011000010101000110000101001110101010111011010010111011001010011100010101001100110000110101100010000100110101110100001101001011011110011100110011001010110100101010111110110111100000111010001111101110000000000111011011101000011001010010111001110111000100111011110100101000100011011101100011111000101110110110111111001111000000011100011000010000101001011001101110101000010101001000100110010000101001111100101000001011011010011110001101000001101111010100101001100010100000111000011110101010100011011001110001011110111010111011010101101100000110000001010010101111011']
flag=''
for j in range(4):
    R = ''
    key=(output[j])[:32]
    temp=key
    for i in range(32):
        out = '?'+key[:31]
        ans=int(temp[-1-i])^int(out[-1])^int(out[-4])^int(out[-8])^int(out[-11])^int(out[-15])^int(out[-20])^int(out[-25])^int(out[-28])
        R += str(ans)
        key = str(ans) + key[:31]
    R = format(int(R[::-1],2),'x')
    flag+=R
print('hgame{'+flag+'}')

奇怪的图片

这题挺有意思，包括后面那个奇怪的图片plus，我觉得都很好

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
import time

from PIL import Image, ImageDraw, ImageFont
import threading
import random
import secrets


flag = "hgame{fake_flag}"


def generate_random_image(width, height):
    image = Image.new("RGB", (width, height), "white")
    pixels = image.load()
    for x in range(width):
        for y in range(height):
            red = random.randint(0, 255)
            green = random.randint(0, 255)
            blue = random.randint(0, 255)
            pixels[x, y] = (red, green, blue)
    return image


def draw_text(image, width, height, token):
    font_size = random.randint(16, 40)
    font = ImageFont.truetype("arial.ttf", font_size)
    text_color = (random.randint(0, 255), random.randint(0, 255), random.randint(0, 255))
    x = random.randint(0, width - font_size * len(token))
    y = random.randint(0, height - font_size)
    draw = ImageDraw.Draw(image)
    draw.text((x, y), token, font=font, fill=text_color)
    return 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 generate_unique_strings(n, length):
    unique_strings = set()
    while len(unique_strings) < n:
        random_string = secrets.token_hex(length // 2)
        unique_strings.add(random_string)
    return list(unique_strings)


random_strings = generate_unique_strings(len(flag), 8)


current_image = generate_random_image(120, 80)
key_image = generate_random_image(120, 80)

def random_time(image, name):
    time.sleep(random.random())
    image.save(".\\png_out\\{}.png".format(name))

for i in range(len(flag)):
    current_image = draw_text(current_image, 120, 80, flag[i])
    threading.Thread(target=random_time, args=(xor_images(current_image, key_image), random_strings[i])).start()

大概意思就是

一张图片，写上一个字，和未知的图片异或，输出。

然后这张写上一个字的图片，再写上一个字，再和未知图片异或，输出。

以此类推。

所以想破解就把一张图片和其他所有图片异或，观察字母的增减即可得到flag

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
import time

from PIL import Image, ImageDraw, ImageFont
import threading
import random
import secrets

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
list = []
list.append(Image.open('1.png'))
list.append(Image.open('2.png'))
list.append(Image.open('3.png'))
list.append(Image.open('4.png'))
list.append(Image.open('5.png'))
list.append(Image.open('6.png'))
list.append(Image.open('7.png'))
list.append(Image.open('8.png'))
list.append(Image.open('9.png'))
list.append(Image.open('10.png'))
list.append(Image.open('11.png'))
list.append(Image.open('12.png'))
list.append(Image.open('13.png'))
list.append(Image.open('14.png'))
list.append(Image.open('15.png'))
list.append(Image.open('16.png'))
list.append(Image.open('17.png'))
list.append(Image.open('18.png'))
list.append(Image.open('19.png'))
list.append(Image.open('20.png'))
list.append(Image.open('21.png'))
for i in range(1,21):
    xor_images(list[0],list[i]).save("1+"+str(i+1)+".png")

这段代码就是一张图片和其他所有图片异或。

大概效果

img

然后找出顺序，前后彼此异或，就能看到flag了，可能是反的，应该看的出来吧（

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
from PIL import Image, ImageDraw, ImageFont
import threading
import random
import secrets
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
list = []
list.append(Image.open('1.png'))
list.append(Image.open('2.png'))
list.append(Image.open('3.png'))
list.append(Image.open('4.png'))
list.append(Image.open('5.png'))
list.append(Image.open('6.png'))
list.append(Image.open('7.png'))
list.append(Image.open('8.png'))
list.append(Image.open('9.png'))
list.append(Image.open('10.png'))
list.append(Image.open('11.png'))
list.append(Image.open('12.png'))
list.append(Image.open('13.png'))
list.append(Image.open('14.png'))
list.append(Image.open('15.png'))
list.append(Image.open('16.png'))
list.append(Image.open('17.png'))
list.append(Image.open('18.png'))
list.append(Image.open('19.png'))
list.append(Image.open('20.png'))
list.append(Image.open('21.png'))
numlist = [14,11,1,6,3,8,17,5,18,10,2,16,13,19,12,9,21,15,20,7,4]
for i in range(20):
    xor_images(list[numlist[i]-1],list[numlist[i+1]-1]).save(str(numlist[i])+"+"+str(numlist[i+1])+".png")
#CTF #Crypto #Web #Misc #Hgame
2024-Hgame-week1-wp-crypto
https://py-thok.github.io/2024/02/25/2024-Hgame-week1-wp-crypto/
作者
PYthok-Ptk
发布于
2024年2月25日
许可协议