WP_2024HSCCTF_CRYPTO_STAR_CHASING_DIARY

题目

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
"""
小肖在学习的过程中,了解到了一种填充图片的算法,兴奋的她用它和RSA加密了偶像的照片,
但是在传输的过程中丢失了一部分加密算法,你能帮她补全,并解出来偶像的照片吗?
"""
from PIL import Image


def f(n, x, y):
if n == 0:
return 1
m = 1 << (n - 1)


j = 128
mm = []
for i in range(1, 257):
for s in range(1, 257):
mm.append(f(j, i, s) - 1)

img = Image.open('flag.jpg')
pixels = list(img.getdata())
data = [pixel for pixel in pixels]

img = Image.open('key.png')
pixels = list(img.getdata())
png_key = [pixel for pixel in pixels]

enc = [0] * 65536
for i in range(65536):
enc[i] = data[mm[i]]
for s in range(65536):
enc[s] = enc[s] ^ png_key[s]

image = Image.new('L', (256, 256))
image.putdata(enc)
image.save('enc.jpg')

一张图片 enc.ipg

alt text

还有一个压缩包

另外一个解密压缩包密码的文件

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

p = getPrime(512)
q = getPrime(512)
print("p =", p)
print("q =", q)
n = p * q
key = '********************'
m = bytes_to_long(key.encode())
assert m.bit_length() < 300
r = randint(1, n)
c = (pow(n + 1, m, n * n) * pow(r, n, n * n)) % (n * n)
print("c =", c)

# p = 7828612943367317778189697443061863547768704021648982642807960201410438190347546379219450386530108335470584219657007036386835647156694512102467911388214639
# q = 11560196429251786803557082533869761370530605728500211999842201987445533038949033226473164866960007192683170489064961432891988337343103657552186800680461299
# c = 768905250861905487717845092484035532140840941871031779930259407348955511757335716790249355464829607714399266689960353955065504221985891074636544161678177920296971444880997864168042745264256952808480926755620637239135808617643874771066244234690401223758004286234917537720362007827248701308605961814972773704288547887039586934111562590676930853945316673164146667949991176600280451163710564978897622310650541491271961315592017251211248379608602287809736613530069187936569470129814949302440734244885473716072898519354127964155042421376782226235081303957997587618278341829891036314980185040102049478608445519994654780162

这是一个 Paillier 加密,参考

https://zhuanlan.zhihu.com/p/106340045

解密分为以下几个步骤:

生成私钥: 私钥包含两个大质数 p 和 q。在本题中,p 和 q 已经给出了。

计算 Carmichael λ 函数的值:其中 λ(n) = lcm(p-1, q-1),lcm 是最小公倍数函数。

计算 μ: μ 是 n 的欧拉函数的模反元素,满足

(L(g^λ(n) mod n2))-1 mod n

其中

L(x) = (x - 1) / n

g 是一个随机选择的整数且满足

gcd(L(g^λ(n) mod n^2), n) = 1

解密密文: 密文 c 可以通过以下公式计算得到明文 m:

m = L(c^λ(n) mod n^2) * μ mod n

代码参考:

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
from Crypto.Util.number import *
import math
p = 7828612943367317778189697443061863547768704021648982642807960201410438190347546379219450386530108335470584219657007036386835647156694512102467911388214639
q = 11560196429251786803557082533869761370530605728500211999842201987445533038949033226473164866960007192683170489064961432891988337343103657552186800680461299
c = 768905250861905487717845092484035532140840941871031779930259407348955511757335716790249355464829607714399266689960353955065504221985891074636544161678177920296971444880997864168042745264256952808480926755620637239135808617643874771066244234690401223758004286234917537720362007827248701308605961814972773704288547887039586934111562590676930853945316673164146667949991176600280451163710564978897622310650541491271961315592017251211248379608602287809736613530069187936569470129814949302440734244885473716072898519354127964155042421376782226235081303957997587618278341829891036314980185040102049478608445519994654780162
n = p * q

# 计算λ(n)
def lcm(a, b):
return abs(a*b) // math.gcd(a, b)

lambda_n = lcm(p-1, q-1)

# 计算μ
def mod_inverse(a, m):
m0, x0, x1 = m, 0, 1
while a > 1:
q = a // m
m, a = a % m, m
x0, x1 = x1 - q * x0, x0
return x1 + m0 if x1 < 0 else x1

mu = mod_inverse(lambda_n, n)

# 解密密文
def decrypt(c, lambda_n, n, mu):
return (pow(c, lambda_n, n*n) - 1) // n * mu % n

ciphertext = 768905250861905487717845092484035532140840941871031779930259407348955511757335716790249355464829607714399266689960353955065504221985891074636544161678177920296971444880997864168042745264256952808480926755620637239135808617643874771066244234690401223758004286234917537720362007827248701308605961814972773704288547887039586934111562590676930853945316673164146667949991176600280451163710564978897622310650541491271961315592017251211248379608602287809736613530069187936569470129814949302440734244885473716072898519354127964155042421376782226235081303957997587618278341829891036314980185040102049478608445519994654780162

plaintext = decrypt(ciphertext, lambda_n, n, mu)
print("明文为:", long_to_bytes(plaintext))
# 明文为: b'HSCCTF{this_is_a_fake_flag}'

得到的 flag 为压缩包的密码,打开压缩包,发现了另外半份图片 key.png alt text

下面的首要问题是补全这个加密函数

1
2
3
4
5
def f(n, x, y):
if n == 0:
return 1
m = 1 << (n - 1)
# 这里少了一句话

出题人用这个函数来对两张图片 flag.jpg 和 key.png 的像素点进行异或得到了 enc.jpg

但是这个函数我不知道是什么。。。。

over !


WP_2024HSCCTF_CRYPTO_STAR_CHASING_DIARY
http://jrhu0048.github.io/2024/03/10/ctf/wp-2024hscctf-crypto-star-chasing-diary/
作者
JR.HU
发布于
2024年3月10日
更新于
2024年4月8日
许可协议