近期比赛复现Vol.4

RITSEC CTF

Crypto

[WarmUp]Words

X marks the spot, but not where the Pigpen lies; there, secrets hide in plain sight.

猪圈密码。

[WarmUp]Emails

We’ve recovered some of Chase’s emails from his inbox. It seems he was conspiring with someone, but the last email is encrypted. Maybe the other emails contain clues that will help us decrypt it?

题目给了一些明文，还有一组密文，根据文章内容发现是MTP。

Good morning,

How are you?
I've become concerned about the security of this email service. It's only a matter of time before your inbox gets leaked.
To deal with this, I suggest we encrypt our emails. If you have any further ideas, please let me know.

Thanks,
- Your Secret Conspirator

Good morning,

I need to send you the flag, but as I mentioned in my last email, I don't want to send it unencrypted.
Please continue to look into possible encryption methods.

Thanks,
- Your Secret Conspirator

Good evening,

I see you mentioned a One Time Pad. Looking into it, that might be useful.
It apparently is secure against infinite computational resources. Do you think we can use that?

Thanks,
- Your Secret Conspirator

Good afternoon,

Okay so I have developed a secure channel for sending the key to the one time pad.
The only problem is it's really slow. I'll send you the key, but I think we should limit the key size to 32 bytes.

Thanks,
- Your Secret Conspirator

Good evening,

It's simple. Just repeat the key over the whole message. That way you can encrypt the whole email with the smaller key.

Thanks,
- Your Secret Conspirator

在几篇文章中发现I think we should limit the key size to 32 bytes.，MTP的key长度为32，从网上找了个MTP的模版，根据已知分组的内容推测相同的内容，进而求出所有的明文：

import Crypto.Util.strxor as xo
import numpy as np


def isChr(x):
    if ord("a") <= x and x <= ord("z"):
        return True
    if ord("A") <= x and x <= ord("Z"):
        return True
    return False


def infer(index, pos):
    if msg[index, pos] != 0:
        return
    msg[index, pos] = ord(" ")
    for x in range(len(c)):
        if x != index:
            msg[x][pos] = xo.strxor(c[x], c[index])[pos] ^ ord(" ")


def know(index, pos, ch):
    msg[index, pos] = ord(ch)
    for x in range(len(c)):
        if x != index:
            msg[x][pos] = xo.strxor(c[x], c[index])[pos] ^ ord(ch)


dat = []


def getSpace():
    for index, x in enumerate(c):
        res = [xo.strxor(x, y) for y in c if x != y]
        f = lambda pos: len(list(filter(isChr, [s[pos] for s in res])))
        cnt = [f(pos) for pos in range(len(x))]
        for pos in range(len(x)):
            dat.append((f(pos), index, pos))


# get cipher
f = open("email5.enc", "rb").read()
c = [
    b"[P\xc9I\xb2\x16S \x0f=\x99|\x7f\x931\x0cI\x83p\xffMX[,\xc0\x15\xab\xee\x87\xe2\xe7\x16",
    b"<S\xcfF\xf7SL1F'\xd7h2\xf8^!7\xaa9\xe2IZSu\x95Z\x97\xee\x95\xef\xe7Z",
    b"zS\xc7J\xbcSl1F'\xcd\x16Y\xcchz\x17\xad-\xc5\x0bGh;\xdca\xbd\xa6\xd1\xf0\xdd#",
    b",J\xf9X\xa7@z\n5\x04\x8a\x16Y\xdaTod\xb19\xe2DUE0\xcc\\\x96\xee\x96\xee\xf6\x12",
    b"<^\xc8T\xfd\x1d@d@t\xbeot\xed\x1bw&\xb7`\xb1_QT'\x89A\xc3\xc3\xeb\x8a\x88.",
    b"t^\xc8F\xe1_(OLt\xaet&\xec\x1bR&\xa6k\xf4X\x14t:\x82F\x92\xa7\x93\xe6\xf6\x15",
]

# infer possible bytes
msg = np.zeros([len(c), len(c[0])], dtype=int)
getSpace()
dat = sorted(dat)[::-1]
for w, index, pos in dat:
    infer(index, pos)

# MTP know bytes
know(0, 0, "G")
know(0, 1, "o")
know(0, 2, "o")
know(0, 3, "d")
know(0, 4, " ")
know(0, 5, "e")
know(0, 6, "v")
know(0, 7, "e")
know(0, 8, "n")
know(0, 9, "i")
know(0, 10, "n")
know(0, 11, "g")
know(0, 12, ",")
know(4, 13, "s")
know(4, 14, " ")
know(5, 15, "S")
know(5, 16, "e")
know(5, 17, "c")
know(5, 18, "r")
know(5, 19, "e")
know(5, 20, "t")
know(5, 21, " ")
know(5, 22, "C")
know(5, 23, "o")
know(5, 24, "n")
know(5, 25, "s")
know(5, 26, "p")
know(5, 27, "i")
know(5, 28, "r")
know(5, 29, "a")
know(5, 30, "t")
know(5, 31, "o")

# show results
print("".join(["".join([chr(c) for c in x]) for x in msg]))
key = xo.strxor(c[5], "".join([chr(c) for c in msg[5]]).encode())
print(key)

Failed File Transfer

Hello, Investigator,

We have intercepted a transmission that was sent to the thief of Anthon‘s invention. We believe it may contain information pertinent to your investigation! Additionally, the sender accidentally failed to encrypt the file with the thief’s most recent provisioned key, requiring them to resend the message. I am not sure why, but the keys don’t seem all that different. There may be a vulnerability with the provisioning process. Nevertheless, we have provided you with all attempts captured in transmission and the keys used for posterity. Good luck!

提取公钥之后发现是共模攻击：

from Crypto.PublicKey import RSA
from Crypto.Util.number import *
import gmpy2

key1 = RSA.import_key(open("pk1.pem").read()).export_key
n1 = RSA.import_key(open("pk1.pem").read()).n
print(n1)
e1 = RSA.import_key(open("pk1.pem").read()).e
print(e1)

key2 = RSA.import_key(open("pk2.pem").read()).export_key
n2 = RSA.import_key(open("pk2.pem").read()).n
print(n2)
e2 = RSA.import_key(open("pk2.pem").read()).e
print(e2)

key3 = RSA.import_key(open("pk3.pem").read()).export_key
n3 = RSA.import_key(open("pk3.pem").read()).n
print(n3)
e3 = RSA.import_key(open("pk3.pem").read()).e
print(e3)

with open('file1.txt','rb') as f:
    f=f.read()
c1=bytes_to_long(f)

with open('file2.txt','rb') as f:
    f=f.read()
c2=bytes_to_long(f)

s,s1,s2 = gmpy2.gcdext(e1,e2)
print(long_to_bytes(pow(c1,s1,n1)*pow(c2,s2,n1)%n1))

Dastardly Evil Scientists

Oh no! A brilliant scientist with questionable ethics has encrypted Anthony’s important research. Luckily, the scientist who did this was overconfident, and gave us both the encrypted research and the contraption used to encrypt it. Can you get Anthony’s research back before it’s too late?

from Crypto.Cipher import DES
from Crypto.Util.Padding import pad
from secret import KEY, FLAG

BLOCK_SIZE = 64

key = bytes.fromhex(KEY)
cipher = DES.new(key, DES.MODE_ECB)
flag = cipher.encrypt(pad(bytes(FLAG, "utf-8"), BLOCK_SIZE))

print("Here's the flag (in hex):", flag.hex())
print("=" * 64)
print("Encrypt something if you want, you can choose the key and the plaintext :)")
while True:
    try:
        key = bytes.fromhex(input("Key (in hex): "))
        plaintext = bytes.fromhex(input("Message to encrypt (in hex): "))
        print("=" * 64)
        cipher = DES.new(key, DES.MODE_ECB)
        ciphertext = cipher.encrypt(pad(plaintext, BLOCK_SIZE))
        print("Here's your message! (in hex):", ciphertext.hex())
        print("Here's your message! (in bytes):", ciphertext)
        print("=" * 64)
    except KeyboardInterrupt:
        break

利用了DES的弱密钥攻击，出题人加密时的key为某个弱密钥，挨个试就能出了。

Here's the flag (in hex): 28e3a0ff9089aecc83465e470624a89253a1aac856a4f7ff08b4648b7c5eff9aa41a0dd1c7fc15995382dc3149dfcccf82241fb566fb5a0382241fb566fb5a03
================================================================
Encrypt something if you want, you can choose the key and the plaintext :)
Key (in hex): 0101010101010101
Message to encrypt (in hex): 28e3a0ff9089aecc83465e470624a89253a1aac856a4f7ff08b4648b7c5eff9aa41a0dd1c7fc15995382dc3149dfcccf82241fb566fb5a0382241fb566fb5a03
================================================================
Here's your message! (in hex): 76d130969ee4b561b2f06fdd76172ddb8ad06cef10c62fa36eab80f508a94c7b02767cd689836c5b5e4e1cd11a794155cea388ef1fd8d5f9cea388ef1fd8d5f9e32a4d9e277d5a85e32a4d9e277d5a85e32a4d9e277d5a85e32a4d9e277d5a85e32a4d9e277d5a85e32a4d9e277d5a85e32a4d9e277d5a85e32a4d9e277d5a85
Here's your message! (in bytes): b"v\xd10\x96\x9e\xe4\xb5a\xb2\xf0o\xddv\x17-\xdb\x8a\xd0l\xef\x10\xc6/\xa3n\xab\x80\xf5\x08\xa9L{\x02v|\xd6\x89\x83l[^N\x1c\xd1\x1ayAU\xce\xa3\x88\xef\x1f\xd8\xd5\xf9\xce\xa3\x88\xef\x1f\xd8\xd5\xf9\xe3*M\x9e'}Z\x85\xe3*M\x9e'}Z\x85\xe3*M\x9e'}Z\x85\xe3*M\x9e'}Z\x85\xe3*M\x9e'}Z\x85\xe3*M\x9e'}Z\x85\xe3*M\x9e'}Z\x85\xe3*M\x9e'}Z\x85"
================================================================
Key (in hex): FEFEFEFEFEFEFEFE
Message to encrypt (in hex): 28e3a0ff9089aecc83465e470624a89253a1aac856a4f7ff08b4648b7c5eff9aa41a0dd1c7fc15995382dc3149dfcccf82241fb566fb5a0382241fb566fb5a03
================================================================
Here's your message! (in hex): 7cfa67f67ea05058ddeee341128568201e578b8fd2c28d09cbb9493a6210513fef4d20ba1175ea8bdb4134891e589f6682ef96dc95c3ff6a82ef96dc95c3ff6ad3256ca1b68f5658d3256ca1b68f5658d3256ca1b68f5658d3256ca1b68f5658d3256ca1b68f5658d3256ca1b68f5658d3256ca1b68f5658d3256ca1b68f5658
Here's your message! (in bytes): b'|\xfag\xf6~\xa0PX\xdd\xee\xe3A\x12\x85h \x1eW\x8b\x8f\xd2\xc2\x8d\t\xcb\xb9I:b\x10Q?\xefM \xba\x11u\xea\x8b\xdbA4\x89\x1eX\x9ff\x82\xef\x96\xdc\x95\xc3\xffj\x82\xef\x96\xdc\x95\xc3\xffj\xd3%l\xa1\xb6\x8fVX\xd3%l\xa1\xb6\x8fVX\xd3%l\xa1\xb6\x8fVX\xd3%l\xa1\xb6\x8fVX\xd3%l\xa1\xb6\x8fVX\xd3%l\xa1\xb6\x8fVX\xd3%l\xa1\xb6\x8fVX\xd3%l\xa1\xb6\x8fVX'
================================================================
Key (in hex): E0E0E0E0F1F1F1F1
Message to encrypt (in hex): 28e3a0ff9089aecc83465e470624a89253a1aac856a4f7ff08b4648b7c5eff9aa41a0dd1c7fc15995382dc3149dfcccf82241fb566fb5a0382241fb566fb5a03
================================================================
Here's your message! (in hex): 52537b5730575f544831535f4b335953503443335f31535f34535f464c34545f34535f33345254487d1717171717171717171717171717171717171717171717c205d5d08d44e30bc205d5d08d44e30bc205d5d08d44e30bc205d5d08d44e30bc205d5d08d44e30bc205d5d08d44e30bc205d5d08d44e30bc205d5d08d44e30b
Here's your message! (in bytes): b'RS{W0W_TH1S_K3YSP4C3_1S_4S_FL4T_4S_34RTH}\x17\x17\x17\x17\x17\x17\x17\x17\x17\x17\x17\x17\x17\x17\x17\x17\x17\x17\x17\x17\x17\x17\x17\xc2\x05\xd5\xd0\x8dD\xe3\x0b\xc2\x05\xd5\xd0\x8dD\xe3\x0b\xc2\x05\xd5\xd0\x8dD\xe3\x0b\xc2\x05\xd5\xd0\x8dD\xe3\x0b\xc2\x05\xd5\xd0\x8dD\xe3\x0b\xc2\x05\xd5\xd0\x8dD\xe3\x0b\xc2\x05\xd5\xd0\x8dD\xe3\x0b\xc2\x05\xd5\xd0\x8dD\xe3\x0b'
================================================================

Forensics

Ransom Note

After the break-in to his lab Anthony found a suspicious new file on his desktop named README.txt. Anthony opened the file and found that it was a ransom demand from whomever stole his invention. Perhaps the contents of the ransom note contain a clue to the attacker’s identity.

提供了一些信息：

-----BEGIN BITCOIN SIGNED MESSAGE-----
Your invention has been taken.
If you ever want to see it again send 10 BTC to this address:

bc1qd7qtdayjnl382qmfl4tl4yaejuv5py0n3uwq6p

You have 3 days.
-----BEGIN BITCOIN SIGNATURE-----
H3zAMJyVW2j1+Y7A+w8wflZRUmggR+Sn532ZuAGtGLcxEERvymcPrtnXVkB+0mBqCUAb0AQwyPFJfGxvIeQDPpE=
-----END BITCOIN SIGNATURE-----

给出了一个交易地址，使用Blockchain Explorer可以查到这个地址，进入交易查看详细信息，发现flag。

[Warm Up] Decrypt the Flood

Dive into the digital currents of Decrypt the Flood! Navigate through encrypted waters, uncovering clues hidden within the network flow. Will you decrypt the mystery behind Anthony’s vanished invention, or will it remain lost in the flood?

提供了一个流量包，直接搜索字符串flag头RS{就能找到flag。

B01lersCTF

choose_the_param

I wounder why we need to specify parameter length in the spec…

nc gold.b01le.rs 5001

#!/usr/bin/python3
from Crypto.Util.number import long_to_bytes, bytes_to_long, getPrime
import os
from secret import flag

padded_flag = os.urandom(200) + flag + os.urandom(200)
m = bytes_to_long(padded_flag)

def chal():
    print("""Choose your parameter
Enter the bit length of the prime!
I'll choose two prime of that length, and encrypt the flag using rsa.
Try decrypt the flag!    
""")
    while True:
        bits = input("Enter the bit length of your primes> ")
        try:
            bit_len = int(bits)
        except:
            print("please enter a valid intergar")
            continue

        p1 = getPrime(bit_len)
        p2 = getPrime(bit_len)

        n = p1 * p2
        e = 65537
        c = pow(m, e, n)
        print(f"n = {n:x}")
        print(f"e = {e:x}")
        print(f"c = {c:x}")

if __name__ == "__main__":
    chal()

发现填充了一个非常长的flag信息，我们只提供生成大素数的位数并不知道具体的两个因子， 但是发现可以多次获得密文，猜测使用中国剩余定理求解，每次生成位数的较小即可：

from pwn import *
from Crypto.Util.number import *
import gmpy2
from sympy import *
from libnum import *
from tqdm import *

r = remote("gold.b01le.rs", 5001)
n_list = []
c_list = []

for i in tqdm(range(50)):
    r.recvuntil(b"Enter the bit length of your primes> ", drop=1)
    r.sendline(b"48")
    n = int(r.recvline().strip().decode().split("=")[-1], 16)
    e = int(r.recvline().strip().decode().split("=")[-1], 16)
    c = int(r.recvline().strip().decode().split("=")[-1], 16)
    n_list.append(n)
    c_list.append(c)

C = solve_crt(c_list, n_list)
phi = 1
for i in tqdm(n_list):
    phi *= int(totient(i))
N = 1
for i in n_list:
    N *= i
d = gmpy2.invert(e, phi)
print(long_to_bytes(pow(C, d, N))[200:-200])

half-big-rsa

Prime numbers are the best numbers. So, you should let me use it for my modulus!

import math
from Crypto.Util.number import getPrime, bytes_to_long, long_to_bytes
import os

num_bits = 4096
e = (num_bits - 1) * 2
n = getPrime(num_bits)

with open("flag.txt","rb") as f:
    flag = f.read()

m = bytes_to_long(flag)
c = pow(m, e, n)
print(c)

with open("output.txt", "w") as f:
	f.write("e = {0}\n".format(e))
	f.write("n = {0}\n".format(n))
	f.write("c = {0}\n".format(c))

e = 8190
n = 665515140120452927777672138241759151799589898667434054796291409500701895847040006534274017960741836352283431369658890777476904763064058571375981053480910502427450807868148119447222740298374306206049235106218160749784482387828757815767617741823504974133549502118215185814010416478030136723860862951197024098473528800567738616891653602341160421661595097849964546693006026643728700179973443277934626276981932233698776098859924467510432829393769296526806379126056800758440081227444482951121929701346253100245589361047368821670154633942361108165230244033981429882740588739029933170447051711603248745453079617578876855903762290177883331643511001037754039634053638415842161488684352411211039226087704872112150157895613933727056811203840732191351328849682321511563621522716119495446110146905479764695844458698466998084615534512596477826922686638159998900511018901148179784868970554998882571043992165232556707995154316126421679595109794273650628957795546293370644405017478289280584942868678139801608538607476925924119532501884957937405840470383051787503858934204828174270819328204062103187487600845013162433295862838022726861622054871029319807982173856563380230936757321006235403066943155942418392650327854150659087958008526462507871976852849
c = 264114212766855887600460174907562771340758069941557124363722491581842654823497784410492438939051339540245832405381141754278713030596144467650101730615738854984455449696059994199389876326336906564161058000092717176985620153104965134542134700679600848779222952402880980397293436788260885290623102864133359002377891663502745146147113128504592411055578896628007927185576133566973715082995833415452650323729270592804454136123997392505676446147317372361704725254801818246172431181257019336832814728581055512990705620667354025484563398894047211101124793076391121413112862668719178137133980477637559211419385463448196568615753499719509551081050176747554502163847399479890373976736263256211300138385881514853428005401803323639515624537818822552343927090465091651711036898847540315628282568055822817711675290278630405760056752122426935056309906683423667413310858931246301024309863011027878238814311176040130230980947128260455261157617039938807829728147629666415078365277247086868327600962627944218138488810350881273304037069779619294887634591633069936882854003264469618591009727405143494184122164870065700859379313470866957332849299246770925463579384528152251689152374836955250625216486799615834558624798907067202005564121699019508857929778460

看了一下想用e和phi不互素的板子解，发现解公因子18次方没有解出来，看来flag位数比较长，看了一下可以用nth_root解，大概等个十来分钟的样子：

from Crypto.Util.number import *

e = 8190
n = 665515140120452927777672138241759151799589898667434054796291409500701895847040006534274017960741836352283431369658890777476904763064058571375981053480910502427450807868148119447222740298374306206049235106218160749784482387828757815767617741823504974133549502118215185814010416478030136723860862951197024098473528800567738616891653602341160421661595097849964546693006026643728700179973443277934626276981932233698776098859924467510432829393769296526806379126056800758440081227444482951121929701346253100245589361047368821670154633942361108165230244033981429882740588739029933170447051711603248745453079617578876855903762290177883331643511001037754039634053638415842161488684352411211039226087704872112150157895613933727056811203840732191351328849682321511563621522716119495446110146905479764695844458698466998084615534512596477826922686638159998900511018901148179784868970554998882571043992165232556707995154316126421679595109794273650628957795546293370644405017478289280584942868678139801608538607476925924119532501884957937405840470383051787503858934204828174270819328204062103187487600845013162433295862838022726861622054871029319807982173856563380230936757321006235403066943155942418392650327854150659087958008526462507871976852849
c = 264114212766855887600460174907562771340758069941557124363722491581842654823497784410492438939051339540245832405381141754278713030596144467650101730615738854984455449696059994199389876326336906564161058000092717176985620153104965134542134700679600848779222952402880980397293436788260885290623102864133359002377891663502745146147113128504592411055578896628007927185576133566973715082995833415452650323729270592804454136123997392505676446147317372361704725254801818246172431181257019336832814728581055512990705620667354025484563398894047211101124793076391121413112862668719178137133980477637559211419385463448196568615753499719509551081050176747554502163847399479890373976736263256211300138385881514853428005401803323639515624537818822552343927090465091651711036898847540315628282568055822817711675290278630405760056752122426935056309906683423667413310858931246301024309863011027878238814311176040130230980947128260455261157617039938807829728147629666415078365277247086868327600962627944218138488810350881273304037069779619294887634591633069936882854003264469618591009727405143494184122164870065700859379313470866957332849299246770925463579384528152251689152374836955250625216486799615834558624798907067202005564121699019508857929778460

res = Zmod(n)(c).nth_root(e, all=True)
for m in res:
    flag = long_to_bytes(int(m))
    print(flag)

Fetus-RSA

from Crypto.Util.number import bytes_to_long, getPrime, isPrime
from sage.all import matrix, Zmod
from flag import flag


def nextPrime(prim):
    if isPrime(prim):
        return prim
    else:
        return nextPrime(prim+1)

p1 = getPrime(128)
p2 = nextPrime(p1 * 1)
p3 = nextPrime(p2 * 3)
p4 = nextPrime(p3 * 3)
p5 = nextPrime(p4 * 7)

primes = [p1, p2, p3, p4, p5]

n = p1 * p2 * p3 * p4 * p5

fragments = [bytes_to_long(flag[5*i:5*i+5]) for i in range(25)]

e = 31337

topG = matrix(Zmod(n), [[fragments[5*i + j] for j in range(5)] for i in range(5)])
bottomG = topG ** e

with open("output.txt", "w") as file:
    file.write(f"n = {n}\n\n")
    file.write("Ciphertext Matrix:\n\n")
    for row in bottomG:
        for num in row:
            file.write(str(num) + " ")
        file.write("\n\n")

n = 515034877787990680304726859216098826737559607654653680536655175803818486402820694536785452537613547240092505793262824199243610743308333164103851365420630137187276313271869670701737383708742526677

Ciphertext Matrix:

247714609729115034577268860647809503348452679955541765864525644036519903244610407544592438833012659821363982836831477850927621505723503202914955484784761468695340160789629882004055804409080695867 331625142917011732363496584111977497826539848810596405639715608289185491230192921594585113936516744954068559616963395888825085234835086592835782522823153199824647815923311303312529222423487842184 55437288185949549641415195099137917985198178875175317590356850868652628068256771878957686344008331498612071069691453711091201145528626750365270496738628725699281809961803599963127434726167609435 514660916099185196031776141538776359410382339048282799109733569738126784171011249457518653961429789338579350043906060924939800730829826389077489637524528092592193187169747629063004980325000389554 432908737089369750416720813650504950741227543859957288298129130571557758647818791153409184252564534925607409378801765727301405467691263041798341098982058861749568674152447781841703730861074171486 

104171307746966345345857299403770324392522334886728513788970028646835780770090370816961277474173463662053179135418083415763603092683905102293259569143230591686555033557056635683615214642425173517 281995809329109899498417283591516891672267505291547187769414960759245222376040526984420670509684233818236456944690830422135256653807646369718495017051487254128669606210585168140190305476396414836 448210297704655248563230644309382726474650012116320871206976601497778210586480264554625801730855872456388662647389829317946932942681549854741993522145903386318540208729036379511878276729211658861 399193502999265141959383452857091791757532600793923480036782294759164203783245516880539439411508616363396395258745387111132143827593272610961260623660064934154238955120293971424750525097551648180 448909699677346701183758951038319440723583288307818355958233994863175886710495171317606803723159576428485212274726596045235998230677229224379125716760136092533604817049730746550292371970711497032 

10383824979618791372207750490225860866360446289011667617367731854443817405025701872398853456038612719059056477356275566409859556622099910727870579661815727983662245805512246175424036918556245316 3042212133475156282375315438954933898496627384941849067508473136817427432524109900983912625376319043681252528210663860374506706029777992048856493297280439498831646567645849063286941560111486091 303901520908845557762276355500926092138935908381564097855093945643653520650021074626397106363589843089839561176214123648988682404983806374183953260408815900582907133898417354283905163971086566554 385414980407334346707284477209921028250475161696209076212214696858828374481374774762344617183479700018626970039426895699261230837253656355202103718574806419224338390036737550645417315148014935208 172437598435610362668691083369422058178612127588567286669952095014310724933793758671802664372505747578789080527221296229242137567445447449560987571505575740311394634799579166058011734727404038041 

459726837943530454128170171077760511486009487765694189770202436458018005866133157577824055980174845256397040485330898693944501922148000904627621334536523927325451030816598478315788682056071758797 318766645374831072244114015670117551595181174553017703335802708316885112551395705202907958737214488185739954176085085611052360624160681549561415131064529778955941226762589967588568203157586014646 485361005374731090711430490780588207888099824436671620066599360058262282812311497518237782819588602409946446254729349547214950452718084694554650900064587640931729162822096611158015732013679765115 442488981185685119421099225895492967006907103880489001122993678677306129218035946328038537612725434883858276836497639772750576738969390151812664236525222680918250542360570252193283310559820113337 294017672174100375503817924437430140826863578191649796300540064690169411498877218939778928997294952104395700469268399214549954967540991489929488976904050382049934179672641195866868009511101289284 

394288980150370144394508377797340867635320394706221783789360450886862330500083595146934277232717671435601428999455723360437715407992902972393377872146437245909234935183690525050686313034961250106 174537062539250527750306397111216900339583030576848484858177223085331307339246744122607759453386390209872407563526999813562242756044330978624067706177762337375480164381575660119163723806663394768 167378817268639407255382001659131271694745168867873206910416580974376327982114272760583238198872032832961214636912981493082249850676384736073683786291369414678559758485110038329085571864758144806 479478683656492256273719495784577239188841595512723735000697935028851355713461770920044121053505358284609828319371252306609569657211738503902322975549066701614139339082341370785743668742796520457 468925056254460005965810812432459057693038841264871939568448625553319440670497244388153862616274082271409346691280049609288322448351851208172939513793874861880752049454593563028452119997997329883 

题目首先通过p生成了一个模数n，可以大致观察到：
$$
n≈p\cdot p\cdot 3p\cdot3(3p)\cdot7(9p)≈1701p^5
$$
可以先大致爆破出p的大小，由于使用的是next_prime所以相差不大，简单估计一下发现实际的p值应该要略小一些，简单爆破一下即可：

from Crypto.Util.number import *
import gmpy2
from libnum import *
from tqdm import *

n = 515034877787990680304726859216098826737559607654653680536655175803818486402820694536785452537613547240092505793262824199243610743308333164103851365420630137187276313271869670701737383708742526677
res = gmpy2.iroot(n // 1701, 5)[0]
for i in range(1000):
    if n % (res - i) == 0:
        p = res - i
        break
print(p)

接下来的操作是进行了一个矩阵运算：

fragments = [bytes_to_long(flag[5*i:5*i+5]) for i in range(25)]
e = 31337
topG = matrix(Zmod(n), [[fragments[5*i + j] for j in range(5)] for i in range(5)])
bottomG = topG ** e

fragments数组是flag每五个分一组转码得到的结果（好像flag挺长），然后转换成模n下的一个矩阵，给了一个已知的指数e，计算了矩阵的e次方。

题目给了bottomG矩阵的元素，没有给topG，发现：
$$
bottom= top^e\pmod n
$$
长得神似RSA，也需要我们求出一个类似于逆元私钥d的东西满足：
$$
top= bottom^d\pmod n
$$
但是问题来了，这里的d是像RSA那样的在模欧拉函数的逆元吗？这里的底都是矩阵，不确定是否满足欧拉定理，推不出相等。

这里的$ed=1$其实是在模一个模n下一般线性群的阶。也就是矩阵在多少次自乘之后变成单位元（单位矩阵），类似于椭圆曲线阶之类的，在这篇文章有比较实用的一些结论：

GL(n,Fp)群阶的研究 | Tover’s Blog

简单记一下怎么计算一个素数$p$的线性群阶吧：

$n_{i+1}$项的阶是在$n_i$项上乘上分圆多项式$\Phi_n(i+1)$。

默认零维矩阵单独乘$p$，一维矩阵就是$p(p-1)$，二维矩阵就是$p(p-1)(p+1)$，然后不断迭代。

在这个题目中，我们是五维的矩阵，所以需要计算出五维矩阵下的线性群阶。

题目中用的模数并不是素数而是多个素数的乘积$n$，但是可以发现flag其实是五位字节转码得到的整数值，其实是非常小的，跟RSA的思路相同，可以直接把这个矩阵运算的域简化到模$p$上，最后还是能解出模$p$下的flag矩阵。

from Crypto.Util.number import *
import gmpy2
from libnum import *
from tqdm import *

n = 515034877787990680304726859216098826737559607654653680536655175803818486402820694536785452537613547240092505793262824199243610743308333164103851365420630137187276313271869670701737383708742526677
res = gmpy2.iroot(n // 1701, 5)[0]
for i in range(1000):
    if n % (res - i) == 0:
        p = int(res - i)
        break

p_order = (
    p * (p - 1) * (p + 1) * (p**2 + p + 1) * (p**2 + 1) * (p**4 + p**3 + p**2 + p + 1)
)
e = 31337
C = matrix(
    Zmod(int(p)),
    [
        [
            247714609729115034577268860647809503348452679955541765864525644036519903244610407544592438833012659821363982836831477850927621505723503202914955484784761468695340160789629882004055804409080695867,
            331625142917011732363496584111977497826539848810596405639715608289185491230192921594585113936516744954068559616963395888825085234835086592835782522823153199824647815923311303312529222423487842184,
            55437288185949549641415195099137917985198178875175317590356850868652628068256771878957686344008331498612071069691453711091201145528626750365270496738628725699281809961803599963127434726167609435,
            514660916099185196031776141538776359410382339048282799109733569738126784171011249457518653961429789338579350043906060924939800730829826389077489637524528092592193187169747629063004980325000389554,
            432908737089369750416720813650504950741227543859957288298129130571557758647818791153409184252564534925607409378801765727301405467691263041798341098982058861749568674152447781841703730861074171486,
        ],
        [
            104171307746966345345857299403770324392522334886728513788970028646835780770090370816961277474173463662053179135418083415763603092683905102293259569143230591686555033557056635683615214642425173517,
            281995809329109899498417283591516891672267505291547187769414960759245222376040526984420670509684233818236456944690830422135256653807646369718495017051487254128669606210585168140190305476396414836,
            448210297704655248563230644309382726474650012116320871206976601497778210586480264554625801730855872456388662647389829317946932942681549854741993522145903386318540208729036379511878276729211658861,
            399193502999265141959383452857091791757532600793923480036782294759164203783245516880539439411508616363396395258745387111132143827593272610961260623660064934154238955120293971424750525097551648180,
            448909699677346701183758951038319440723583288307818355958233994863175886710495171317606803723159576428485212274726596045235998230677229224379125716760136092533604817049730746550292371970711497032,
        ],
        [
            10383824979618791372207750490225860866360446289011667617367731854443817405025701872398853456038612719059056477356275566409859556622099910727870579661815727983662245805512246175424036918556245316,
            3042212133475156282375315438954933898496627384941849067508473136817427432524109900983912625376319043681252528210663860374506706029777992048856493297280439498831646567645849063286941560111486091,
            303901520908845557762276355500926092138935908381564097855093945643653520650021074626397106363589843089839561176214123648988682404983806374183953260408815900582907133898417354283905163971086566554,
            385414980407334346707284477209921028250475161696209076212214696858828374481374774762344617183479700018626970039426895699261230837253656355202103718574806419224338390036737550645417315148014935208,
            172437598435610362668691083369422058178612127588567286669952095014310724933793758671802664372505747578789080527221296229242137567445447449560987571505575740311394634799579166058011734727404038041,
        ],
        [
            459726837943530454128170171077760511486009487765694189770202436458018005866133157577824055980174845256397040485330898693944501922148000904627621334536523927325451030816598478315788682056071758797,
            318766645374831072244114015670117551595181174553017703335802708316885112551395705202907958737214488185739954176085085611052360624160681549561415131064529778955941226762589967588568203157586014646,
            485361005374731090711430490780588207888099824436671620066599360058262282812311497518237782819588602409946446254729349547214950452718084694554650900064587640931729162822096611158015732013679765115,
            442488981185685119421099225895492967006907103880489001122993678677306129218035946328038537612725434883858276836497639772750576738969390151812664236525222680918250542360570252193283310559820113337,
            294017672174100375503817924437430140826863578191649796300540064690169411498877218939778928997294952104395700469268399214549954967540991489929488976904050382049934179672641195866868009511101289284,
        ],
        [
            394288980150370144394508377797340867635320394706221783789360450886862330500083595146934277232717671435601428999455723360437715407992902972393377872146437245909234935183690525050686313034961250106,
            174537062539250527750306397111216900339583030576848484858177223085331307339246744122607759453386390209872407563526999813562242756044330978624067706177762337375480164381575660119163723806663394768,
            167378817268639407255382001659131271694745168867873206910416580974376327982114272760583238198872032832961214636912981493082249850676384736073683786291369414678559758485110038329085571864758144806,
            479478683656492256273719495784577239188841595512723735000697935028851355713461770920044121053505358284609828319371252306609569657211738503902322975549066701614139339082341370785743668742796520457,
            468925056254460005965810812432459057693038841264871939568448625553319440670497244388153862616274082271409346691280049609288322448351851208172939513793874861880752049454593563028452119997997329883,
        ],
    ],
)

d = gmpy2.invert(e, p_order)
M = C**d
flag = b""
for row in M:
    for i in range(len(row)):
        flag += long_to_bytes(int(row[i]))
print(flag)

schnore

I can’t seem to adapt to my new sleep schedule, too tired to interact right now…

#!/usr/bin/python3

import sys
from Crypto.Util import number
from Crypto.Hash import SHA512

with open("flag.txt") as f:
    flag = f.read()

# FIPS 186-4 Appendix A.1/A.2 compliant prime order q group and prime order p field
#from Crypto.PublicKey import DSA as FFCrypto
#(p,q,g) = FFCrypto.generate(2048).domain()
p = 32148430219533869432664086521225476372736462680273996089092113172047080583085077464347995262368698415917196323365668601969574610671154445337781821758494432339987784268234681352859122106315479086318464461728521502980081310387167105996276982251134873196176224643518299733023536120537865020373805440309261518826398579473063255138837294134742678213639940734783340740545998610498824621665838546928319540277854869576454258917970187451361767420622980743233300167354760281479159013996441502511973279207690493293107263225937311062981573275941520199567953333720369198426993035900390396753409748657644625989750046213894003084507
q = 25652174680121164880516494520695513229510497175386947962678706338003
g = 23174059265967833044489655691705592548904322689090091191484900111607834369643418104621577292565175857016629416139331387500766371957528415587157736504641585483964952733970570756848175405454138833698893579333073195074203033602295121523371560057410727051683793079669493389242489538716350397240122001054430034016363486006696176634233182788395435344904669454373990351188986655669637138139377076507935928088813456234379677586947957539514196648605649464537827962024445144040395834058714447916981049408310960931998389623396383151616168556706468115596486100257332107454218361019929061651117632864546163172189693989892264385257

def prove():
    print("The oracles say that X is g^x and A is g^a. Be that as it may...")
    print("Perhaps there exists a way to make their confidence sway!")

    # (Sorry, can't choose a :)
    A = 30210424620845820052071225945109142323820182565373787589801116895962027171575049058295156742156305996469210267854774935518505743920438652976152675486476209694284460060753584821225066880682226097812673951158980930881565165151455761750621260912545169247447437218263919470449873682069698887953001819921915874928002568841432197395663420509941263729040966054080025218829347912646803956034554112984570671065110024224236097116296364722731368986065647624353094691096824850694884198942548289196057081572758803944199342980170036665636638983619866569688965508039554384758104832379412233201655767221921359451427988699779296943487

    h = SHA512.new(truncate="256")
    h.update(number.long_to_bytes(g) + number.long_to_bytes(p) + number.long_to_bytes(A))
    c = number.bytes_to_long(h.digest()) % p

    z = int(input("a + cx = ")) % p
    
    return (A,c,z)


def setup():
    print("> I'm so sleepy, I almost forgot; we should share what we ought.")
    print("> Just between you and me, can we agree on a verifying key...?")
    X = int(input("> X = ")) % p
    
    return X

def verify(A,c,z,X):
    h = SHA512.new(truncate="256")
    h.update(number.long_to_bytes(g) + number.long_to_bytes(p) + number.long_to_bytes(A))
    cp = number.bytes_to_long(h.digest()) % p
    
    if c != cp or pow(g, z, p) != ((A * pow(X, c, p)) % p):
        print("> Oh, even my bleary eyes can tell your evidence is fau x !!")
        print("> Are you sure that what you say is what you truly know?")
        sys.exit()
    else:
        print("> ", end="")
        print(flag)

if __name__ == "__main__":
    (A,c,z) = prove()
    X = setup()
    verify(A,c,z,X)

这题实现了一个验证程序，简单看了下代码发现需要验证c != cp or pow(g, z, p) != ((A * pow(X, c, p)) % p)，前半部分发现计算都用的程序内部的数据，不需要管，主要是后面这个计算：
$$
g^z\equiv AX^c\pmod p
$$
在这个题目中，$z,X$是我们需要给的，$c$是可以通过计算得到的。剩下的就是提供这两个值满足方程，考虑特殊值$z=0$，移项得到：
$$
A^{-1}\equiv X^c\pmod p
$$
发现这样可以通过RSA解密直接计算出一个$X$，有$cd\equiv 1\pmod {p-1}$：
$$
X\equiv (A^{-1})^d\pmod p
$$
事实上这个$c$经过计算后发现不互素，并不能计算出逆元，也不能直接求解不互素问题，因为是进行交互验证。还注意到题目还给了一个$q$值，注释中提到了这个模$p$下的阶为$q$：

# FIPS 186-4 Appendix A.1/A.2 compliant prime order q group and prime order p field
#from Crypto.PublicKey import DSA as FFCrypto
#(p,q,g) = FFCrypto.generate(2048).domain()

直接尝试用$cd\equiv 1\pmod q$，计算出$X$，发送相关参数得到flag：

from Crypto.Util.number import *
from Crypto.Hash import SHA512
import gmpy2

p = 32148430219533869432664086521225476372736462680273996089092113172047080583085077464347995262368698415917196323365668601969574610671154445337781821758494432339987784268234681352859122106315479086318464461728521502980081310387167105996276982251134873196176224643518299733023536120537865020373805440309261518826398579473063255138837294134742678213639940734783340740545998610498824621665838546928319540277854869576454258917970187451361767420622980743233300167354760281479159013996441502511973279207690493293107263225937311062981573275941520199567953333720369198426993035900390396753409748657644625989750046213894003084507
q = 25652174680121164880516494520695513229510497175386947962678706338003
g = 23174059265967833044489655691705592548904322689090091191484900111607834369643418104621577292565175857016629416139331387500766371957528415587157736504641585483964952733970570756848175405454138833698893579333073195074203033602295121523371560057410727051683793079669493389242489538716350397240122001054430034016363486006696176634233182788395435344904669454373990351188986655669637138139377076507935928088813456234379677586947957539514196648605649464537827962024445144040395834058714447916981049408310960931998389623396383151616168556706468115596486100257332107454218361019929061651117632864546163172189693989892264385257
A = 30210424620845820052071225945109142323820182565373787589801116895962027171575049058295156742156305996469210267854774935518505743920438652976152675486476209694284460060753584821225066880682226097812673951158980930881565165151455761750621260912545169247447437218263919470449873682069698887953001819921915874928002568841432197395663420509941263729040966054080025218829347912646803956034554112984570671065110024224236097116296364722731368986065647624353094691096824850694884198942548289196057081572758803944199342980170036665636638983619866569688965508039554384758104832379412233201655767221921359451427988699779296943487

h = SHA512.new(truncate="256")
h.update(long_to_bytes(g) + long_to_bytes(p) + long_to_bytes(A))
c = bytes_to_long(h.digest()) % p

d = gmpy2.invert(c, q)
X = pow(pow(A, -1, p), d, p)
print(X)

PaluCTF

Misc

FM 145.8

给了一段音频，听了一下发现是某种电波之类的，之前似乎了解过，简单百度了一下发现是业余无线电SSTV（慢扫描电视）。

找了一下有关工具，一个是e2eSoft（虚拟声卡，把电脑自己发出的声音方便接收进电脑，就不需要接收无线电时手动录音了），一个是MMSSTV，用来解码音频的软件，一顿配置之后开始解码，得到flag：

Misc-签到

27880
30693
25915
21892
38450
23454
39564
23460
21457
36865
112
108
98
99
116
102
33719
21462
21069
27573
102
108
97
103
20851
27880
79
110
101
45
70
111
120
23433
20840
22242
38431
22238
22797
112
108
98
99
116
102
33719
21462
21518
27573
102
108
97
103

里面看到一些ASCII码，还有一部分五位数的，转一下十六进制发现刚好都是两位字节，猜测用Unicode解码得到中文：

l = [
    27880,
    30693,
    25915,
    21892,
    38450,
    23454,
    39564,
    23460,
    21457,
    36865,
    112,
    108,
    98,
    99,
    116,
    102,
    33719,
    21462,
    21069,
    27573,
    102,
    108,
    97,
    103,
    20851,
    27880,
    79,
    110,
    101,
    45,
    70,
    111,
    120,
    23433,
    20840,
    22242,
    38431,
    22238,
    22797,
    112,
    108,
    98,
    99,
    116,
    102,
    33719,
    21462,
    21518,
    27573,
    102,
    108,
    97,
    103,
]

print(''.join(chr(i) for i in l))

Crypto

Crypto-签到

nc之后直接给了RSA的参数和p，直接求解即可：

from Crypto.Util.number import *
import gmpy2

c=46033491535672328787762120337720689372102694148558997466700972904675969189424889727370306184069567785363467322963865622665472691215201150379508692286476494457405393181859824733115746182801224600622332819739450793916262765934917943697900177464160910498606182295227921671533603639628786984397655926177302285242
p=6792925221030199703787753788974701116945119371151461096727414831561730846375326806018823625595219148625198864456983306394012441500923194767219630945760317
e=65537
n=46143833058508187500054035910237985967015621026835859473569335142012287039140842552665824708588735827252348846347389189115624698937906662352896753524242557006556251981608771491468704096028186928357333079494674089386305595211993678293958254123716856607301063172002892450178858536553608733657849307997211940489

print(long_to_bytes(pow(c,gmpy2.invert(e,(p-1)),p)))

01110

from Crypto.Util.number import getPrime, getRandomRange, bytes_to_long
from random import randrange
from flag import flag

p = getPrime(512)
q = getPrime(512)
n = p * (q**2)
e = 65537

while True:
    z = randrange(1, n)
    if all(pow(z, (x - 1) // 2, x) == x - 1 for x in (p, q)):
        break


def encrypt_bit(m, n, z):
    secret = getRandomRange(1, n - 1)
    return (pow(secret, 2, n) * pow(z, m, n)) % n

m = int(bin(bytes_to_long(flag))[2:])
c = []
while m:
    bit = m % 10
    c.append(encrypt_bit(bit, n, z))
    m //= 10

print("n=", n)
print("gift1=", pow((p + q), e, n))
print("gift2=", pow((p - q), e, n))
print("z=", z)
print("c=", c)

一道二次剩余的题目，由于之前做过类似的题目直接照抄板子了：

#!/usr/bin/python3
from Crypto.Util.number import long_to_bytes
import os, gmpy2

n= 390643660915400759356028673149168279560687093035302974183909784119138903637101610150171466601442693220550718178154721365461636077209566533154335718201358899342358662848545345180263124134588375803369006010468316238614932369094974862842683683363587543473163915923045398254122306762084945489324575516415794686273949909352344088141474136179402651003388916093283318052977257982248730053350207666237541564674407802737159850168950514444047006592253696165165211262564161
gift1= 32067630145194486197869898082792881486345407200841825390940826089427239649416054110498486063596896368139581845859589332623752888475777930460226997075808233361458808953738363465850038435022164249226553675803062077379730757819488835524247023444067200989550624564241576252328987234115650966021592200858415400936060124848932240676555851487611581747426910966215267899848677827717134935394140676907205949272295818931351260125664718836934006595227163332021922793094033
gift2= 360493111446954743089613557546255044580147549879914031885888612983915832801317562493262579318700361535235974926894917441900224383457881583908919796292980255740269141443269989241112607942630801453841312099803377070956814325684224703690945608807249955033708638867801274649951783273121564119003959043436094415277220587048874802005046122593965637505645589540819610843556397562603505871652532810819966500201506579689076122826479639855824062732793008776052114122129242
z= 125642008135714615180213096249137152053115250051522617677314358748237310710789919544835495128416024573426354601401805582762210636992771173353416049709248105313072995883562275997465786188780917691922457873978391968469742497804449004021873976270245824209039689163464526556006144010645842669088688094789118554551432204100714771685410129670324600557416214170112821842457120893768538678579835619119629796141436191683473943786441689431247088202876541012556271689042631
c= [...]
inv_2=gmpy2.invert(2,n)
print(gmpy2.gcd(gift1+gift2,n))
p = 7699027864713744714474575418517692932595873934013280614373014145797040181966218023796197860529736181587616308826370529874482751538853034839916548040256129
q=gmpy2.iroot(n//p,2)[0]
print(q)

phi = (p-1)*q*(q-1)
flag=""
for i in c:
    if int(i)!=n:
        res=gmpy2.jacobi(int(i),n)
        if res == -1:
            flag+='1'
        else:
            flag+='0'

print(long_to_bytes(int(flag[::-1],2)))

两元钱的铜匠

from secret import flag
from Crypto.Util.number import *
m = bytes_to_long(flag)
p = getPrime(512)
q = getPrime(512)
n = p*q
c = pow(m, 65537, n)
N = getPrime(1024)
leak = (pow(9999, 66666)*p + pow(66666, 9999)*q) % N
print(f'n={n}')
print(f'c={c}')
print(f'N={N}')
print(f'leak={leak}')
"""
n=80916351132285136921336714166859402248518125673421944066690210363157948681543515675261790287954711843082802283188843248579293238274583917836325545166981149125711216316112644776403584036920878846575128588844980283888602402513345309524782526525838503856925567762860026353261868959895401646623045981393058164201
c=22730301930220955810132397809406485504430998883284247476890744759811759301470013143686059878014087921084402703884898661685430889812034497050189574640139435761526983415169973791743915648508955725713703906140316772231235038110678219688469930378177132307304731532134005576976892978381999976676034083329527911241
N=175887339574643371942360396913019735118423928391339797751049049816862344090324438786194807609356902331228801731590496587951642499325571035835790931895483345540104575533781585131558026624618308795381874809845454092562340943276838942273890971498308617974682097511232721650227206585474404895053411892392799799403
leak=161177488484579680503127298320874823539858895081858980450427298120182550612626953405092823674668208591844284619026441298155371399651438065337570099147890081125477609238234662000811899869636390550619251741676887565983189442613760093303841954633720778312454175652907352477365434215186845209831284593041581382419
"""

找一下题目的公式：
$$
leak=9999^{66666}p+66666^{9999}q\pmod N
$$
两边同时乘$p$，得到：
$$
leak\cdot p=9999^{66666}p^2+66666^{9999}n\pmod N
$$
可以用sage解方程：

import gmpy2
from Crypto.Util.number import *

n=80916351132285136921336714166859402248518125673421944066690210363157948681543515675261790287954711843082802283188843248579293238274583917836325545166981149125711216316112644776403584036920878846575128588844980283888602402513345309524782526525838503856925567762860026353261868959895401646623045981393058164201
c=22730301930220955810132397809406485504430998883284247476890744759811759301470013143686059878014087921084402703884898661685430889812034497050189574640139435761526983415169973791743915648508955725713703906140316772231235038110678219688469930378177132307304731532134005576976892978381999976676034083329527911241
N=175887339574643371942360396913019735118423928391339797751049049816862344090324438786194807609356902331228801731590496587951642499325571035835790931895483345540104575533781585131558026624618308795381874809845454092562340943276838942273890971498308617974682097511232721650227206585474404895053411892392799799403
leak=161177488484579680503127298320874823539858895081858980450427298120182550612626953405092823674668208591844284619026441298155371399651438065337570099147890081125477609238234662000811899869636390550619251741676887565983189442613760093303841954633720778312454175652907352477365434215186845209831284593041581382419

tmp1 = 9999**66666
tmp2 = 66666**9999

R.<p> = PolynomialRing(Zmod(N))

f = tmp1*p**2 + tmp2*n - leak*p
root = f.roots()

p = int(root[1][0])
q = n // p 
d = gmpy2.invert(65537,(p-1)*(q-1))
m = pow(c,d,n)
print(long_to_bytes(int(m)))

江枫渔火对愁眠

from Crypto.Util.number import *
flag = b'paluctf{******************}'
p = getPrime(512)
q = getPrime(512)
m = bytes_to_long(flag)
n = p * q
e = 0x10001
c = pow(m, e, n)
leak1 = p & q
leak2 = p | q
print(n)
print(leak1)
print(leak2)
print(c)

# 116117067844956812459549519789301338092862193317140117457423221066709482979351921356314593636327834899992321545232613626111009441254302384449742843180876494341637589103640217194070886174972452908589438599697165869525189266606983974250478298162924187424655566019487631330678770727392051485223152309309085945253
# 8605081049583982438298440507920076587069196185463800658188799677857096281403951362058424551032224336538547998962815392172493849395335237855201439663804417
# 13407373154151815187508645556332614349998109820361387104317659096666170318961881115942116046384020162789239054091769561534320831478500568385569270082820389
# 77391898018025866504652357285886871686506090492775075964856060726697268476460193878086905273672532025686191143120456958000415501059102146339274402932542049355257662649758904431953601814453558068056853653214769669690930883469679763807974430229116956128100328073573783801082618261383412539474900566590518020658

剪枝爆破：

leak1 = 8605081049583982438298440507920076587069196185463800658188799677857096281403951362058424551032224336538547998962815392172493849395335237855201439663804417
leak2 = 13407373154151815187508645556332614349998109820361387104317659096666170318961881115942116046384020162789239054091769561534320831478500568385569270082820389
N = 116117067844956812459549519789301338092862193317140117457423221066709482979351921356314593636327834899992321545232613626111009441254302384449742843180876494341637589103640217194070886174972452908589438599697165869525189266606983974250478298162924187424655566019487631330678770727392051485223152309309085945253
c = 77391898018025866504652357285886871686506090492775075964856060726697268476460193878086905273672532025686191143120456958000415501059102146339274402932542049355257662649758904431953601814453558068056853653214769669690930883469679763807974430229116956128100328073573783801082618261383412539474900566590518020658

# 低位往高位爆

def findp(p,q):
    if len(p) == 512:
        pp = int(p,2)
        if N % pp == 0:
            print("p = ",pp)
            print("q = ",N // pp)

    else:
        l = len(p)
        pp = int(p,2)
        qq = int(q,2)
        if (pp & qq) % (2 ** l) == leak1 %(2**l) and pp * qq %(2 ** l) == N % (2**l) and (pp | qq) % (2 ** l) == leak2 % (2**l):
            findp('1' + p,'1' + q)
            findp('1' + p,'0' + q)
            findp('0' + p,'1' + q)
            findp('0' + p,'0' + q)
            
findp('1','1')

gcccd

from Crypto.Util.number import getStrongPrime, GCD, bytes_to_long
import os
from flag import flag

def long_to_bytes(long_int, block_size=None):
    """Convert a long integer to bytes, optionally right-justified to a given block size."""
    bytes_data = long_int.to_bytes((long_int.bit_length() + 7) // 8, 'big')
    return bytes_data if not block_size else bytes_data.rjust(block_size, b'\x00')

def gen_keys(bits=512, e=5331):
    """Generate RSA modulus n and public exponent e such that GCD((p-1)*(q-1), e) == 1."""
    while True:
        p, q = getStrongPrime(bits), getStrongPrime(bits)
        n = p * q
        if GCD((p-1) * (q-1), e) == 1:
            return n, e

def pad(m, n):
    """Pad the message m for RSA encryption under modulus n using PKCS#1 type 1."""
    mb, nb = long_to_bytes(m), long_to_bytes(n)
    assert len(mb) <= len(nb) - 11
    padding = os.urandom(len(nb) - len(mb) - 3).replace(b'\x01', b'')
    return bytes_to_long(b'\x00\x01' + padding + b'\x00' + mb)

def encrypt(m, e, n):
    """Encrypt message m with RSA public key (e, n)."""
    return pow(m, e, n)

n, e = gen_keys()
m = pad(bytes_to_long(flag), n)
c1, c2 = encrypt(m, e, n), encrypt(m // 2, e, n)

print(f"n = {n}\ne = {e}\nc1 = {c1}\nc2 = {c2}")

# n = 128134155200900363557361770121648236747559663738591418041443861545561451885335858854359771414605640612993903005548718875328893717909535447866152704351924465716196738696788273375424835753379386427253243854791810104120869379525507986270383750499650286106684249027984675067236382543612917882024145261815608895379
# e = 5331
# c1 = 60668946079423190709851484247433853783238381043211713258950336572392573192737047470465310272448083514859509629066647300714425946282732774440406261265802652068183263460022257056016974572472905555413226634497579807277440653563498768557112618320828785438180460624890479311538368514262550081582173264168580537990
# c2 = 43064371535146610786202813736674368618250034274768737857627872777051745883780468417199551751374395264039179171708712686651485125338422911633961121202567788447108712022481564453759980969777219700870458940189456782517037780321026907310930696608923940135664565796997158295530735831680955376342697203313901005151

题目进行了两次加密：对m和m//2进行了加密，注意到flag最后是以}结尾的，所以明文为奇数，整除2之后会少一个1，如果我们设$\frac m2=x$，那么可以得到一组多项式：
$$
f_1=(2x+1)^e-c_1
$$

$$
f_2=x^e-c_2
$$

发现是相关消息攻击：

from Crypto.Util.number import *
from tqdm import trange
    
n = 128134155200900363557361770121648236747559663738591418041443861545561451885335858854359771414605640612993903005548718875328893717909535447866152704351924465716196738696788273375424835753379386427253243854791810104120869379525507986270383750499650286106684249027984675067236382543612917882024145261815608895379
e = 5331
c1 = 60668946079423190709851484247433853783238381043211713258950336572392573192737047470465310272448083514859509629066647300714425946282732774440406261265802652068183263460022257056016974572472905555413226634497579807277440653563498768557112618320828785438180460624890479311538368514262550081582173264168580537990
c2 = 43064371535146610786202813736674368618250034274768737857627872777051745883780468417199551751374395264039179171708712686651485125338422911633961121202567788447108712022481564453759980969777219700870458940189456782517037780321026907310930696608923940135664565796997158295530735831680955376342697203313901005151

def gcd(g1, g2):
    while g2:
        g1, g2 = g2, g1 % g2
    return g1.monic()

    
P.<x> = PolynomialRing(Zmod(n))
f1 = (2*x+1) ^ e - c1
f2 = x ^ e - c2
m = -gcd(f1,f2)[0]
print(long_to_bytes(int(2*m+1)))

peeeq

import gmpy2
from Crypto.Util.number import *


def check(m, p, q):
    if m == 0: return True
    if m >= p and check(m-p, p, q) : return True
    if m >= q and check(m-q, p, q) : return True
    return False

flag = b"paluctf{***********************}"

p = getPrime(1024)
q = getPrime(1024)
e = getPrime(17)
n = p*q


leak = 20650913970072868759959272239604024297420806808659110564312051736808778949599012338389873196411652566474168134639876252857623310159737758732845898956842366935678501021994729279299799994075598575657211550223683499328614158165787416177094173112167115888930719187253398687736037116845083325669521670262760600243895871953940839864925909273175442587377607028910874730344252804963645659770898616148180806608083557249713184454706023876544328444568520666837841566163924062054001534893538655581481021600384148478571641075265311650046699619525464106135807483192890198614434965478741402348088647355476402189540171838712520668315
pinv_e = gmpy2.invert(p, q)*e
qinv_e = gmpy2.invert(q, p)*e
m = bytes_to_long(flag)
c = pow(m, e, n)
print(c)
print(pinv_e)
print(qinv_e)
m = 0
while True:
    assert m <= leak or check(m, p, q)
    m += 1
# 14656499683788461319601710088831412892194505254418064899761498679297764485273476341077222358310031603834624959088854557947176472443021560072783573052603773463734827298069959304747376040480522193600487999140388188743055733577433643210327070027972481119823973316743393323273128561824747871183252082782459568278265418266528855123687868624734106855360408027492126167597948385055908257193701028960507382053300960017612431744000472268868103779169759349652561826935960615964589526055579319224213399173783902104833907847546751649110661705034653912439791460180154034041113546810232929706136321281991114377628823527206109309013
# 12474140378771043865022148848078136936465079800066130234618983104385642778672967864991495110508733111980066517889153671507701349679185396054215439179349403857665966245686661757089470553109534987101888628107055364941617805783362125836104920292552457095662777743387917809524955960583091720618281570118299619677634759
# 1647206449953560407401595632741127506095799998014240087894866808907042944168674423038307995055460808040825182837354682801054048594394389801771888111156812819183105159993880849157459496014737241461466870906700457127028184554416373467332704931423207098246831148428600375416541264997943693621557486559170922000282251

题目提供了一个leak，根据leak和相关的check函数检验一下，发现$leak=\phi(n)-1$。

根据pinv_e = gmpy2.invert(p, q)*e和qinv_e = gmpy2.invert(q, p)*e求公因数处理一下可以得到$e$。

根据题目的计算逆元，得到：
$$
pp^{-1}=k_1q+1
$$

$$
qq^{-1}=k_2p+1
$$

相乘移项得到：
$$
k_1k_2n=pp^{-1}qq^{-1}-(pp^{-1}+qq^{-1})+1
$$

$$
(p^{-1}q^{-1}-k_1k_2)n=pp^{-1}+qq^{-1}-1
$$

有$p^{-1}<p$，$q^{-1}<q$，所以在上面的式子中：
$$
p^{-1}q^{-1}-k_1k_2=1
$$
有方程：
$$
n=p^{-1}p+q^{-1}q-1
$$

$$
phi=pq-p-q+1
$$

联立解方程，两个未知数两个方程：

import gmpy2

leak = 20650913970072868759959272239604024297420806808659110564312051736808778949599012338389873196411652566474168134639876252857623310159737758732845898956842366935678501021994729279299799994075598575657211550223683499328614158165787416177094173112167115888930719187253398687736037116845083325669521670262760600243895871953940839864925909273175442587377607028910874730344252804963645659770898616148180806608083557249713184454706023876544328444568520666837841566163924062054001534893538655581481021600384148478571641075265311650046699619525464106135807483192890198614434965478741402348088647355476402189540171838712520668315
c = 14656499683788461319601710088831412892194505254418064899761498679297764485273476341077222358310031603834624959088854557947176472443021560072783573052603773463734827298069959304747376040480522193600487999140388188743055733577433643210327070027972481119823973316743393323273128561824747871183252082782459568278265418266528855123687868624734106855360408027492126167597948385055908257193701028960507382053300960017612431744000472268868103779169759349652561826935960615964589526055579319224213399173783902104833907847546751649110661705034653912439791460180154034041113546810232929706136321281991114377628823527206109309013
pinv_e = 12474140378771043865022148848078136936465079800066130234618983104385642778672967864991495110508733111980066517889153671507701349679185396054215439179349403857665966245686661757089470553109534987101888628107055364941617805783362125836104920292552457095662777743387917809524955960583091720618281570118299619677634759
qinv_e = 1647206449953560407401595632741127506095799998014240087894866808907042944168674423038307995055460808040825182837354682801054048594394389801771888111156812819183105159993880849157459496014737241461466870906700457127028184554416373467332704931423207098246831148428600375416541264997943693621557486559170922000282251

t = gmpy2.gcd(pinv_e,qinv_e)
# 307689
e = 102563
phi = leak + 1

pinv = pinv_e // e
qinv = qinv_e // e

# var("p q")
# f1 = p*pinv + q*qinv - 1 == p*q
# f2 = (p-1)*(q-1) == phi
# res = solve([f1,f2],[p,q])
# print(res)

p = 151832619619952089992267716058068444251307600220706203871589765844990819175654042917774490787590849720202969240992246624166668570786235406779778934647681250166384828094778797880304323848041273713831052602978130708287523575488166230706021974231380611512371425017998262828486267505916086636495016213117818476079
q = 136011049679334940861511595857042329781653809853866436171389745534855895446196665892885140663304371230055953209984856118200410958041858815679721863717912611066674050454954534686280510303474769670492647228370259394337403855556056590338482704020086450814990436480639792318856245688841995452742464887239898730723
n = p*q
d = gmpy2.invert(e,phi)
m = pow(c,d,n)
print(bytes.fromhex(hex(int(m))[2:]))