WP_2024HSCCTF_CRYPTO_STAR_CHASING_DIARY

题目

"""
小肖在学习的过程中,了解到了一种填充图片的算法,兴奋的她用它和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

还有一个压缩包

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

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 n²⁾⁾-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

代码参考：

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

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

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

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

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

over !