pcb2024-WriteUp

Crypto

SOLVED

babyenc-pcb2024

from Crypto.Util.number import *
import random
from gmpy2 import *
from secret import flag

assert len(flag) == 42
flag1 = flag[:len(flag)//2]
flag2 = flag[len(flag)//2:]
print(flag1.encode())
print(flag2.encode())
m1 = bytes_to_long(flag1.encode())
m2 = bytes_to_long(flag2.encode())

def e_gen(bits):
    e = []
    for _ in range(5):
        e.append(getPrime(bits))
    return e

def enc1(m, e, shift):
    n = next_prime(m << shift)
    tmp = getPrime(256)
    cc = []
    for i in range(len(e)):
        cc.append(int(pow(tmp, e[i], n)))
    return cc

def key_gen(nbits):
    p = getPrime(nbits)
    q = getPrime(nbits)
    return p, q

def enc2(m, p, q, n):
    c = [pow(m, p, n),pow(m, q, n)]
    return c

bits = 6
nbits = 1024
e = e_gen(bits)
shift = 310
c1 = enc1(m1,e,shift)
print("e =",e)
print("c1 =",c1)
p, q = key_gen(nbits)
n = p * q

c2 = enc2(m2, p, q, n)
print("n =",n)
print("c2 =",c2)

'''
e = [43, 37, 53, 61, 59]
c1 = [304054249108643319766233669970696347228113825299195899223597844657873869914715629219753150469421333712176994329969288126081851180518874300706117, 300569071066351295347178153438463983525013294497692191767264949606466706307039662858235919677939911290402362961043621463108147721176372907055224, 294806502799305839692215402958402593834563343055375943948669528217549597192296955202812118864208602813754722206211899285974414703769561292993531, 255660645085871679396238463457546909716172735210300668843127008526613931533718130479441396195102817055073131304413673178641069323813780056896835, 194084621856364235027333699558487834531380222896709707444060960982448111129722327145131992393643001072221754440877491070115199839112376948773978]
n = 16175064088648626038689748434699435826247716579187475966092822028609536761351820951820375552440329596553448265674841223230257463367834546091974959931391707199002842774795702094681528411058318007858638798643010942408552063479863545047616823056802010158288409527763686086960916160949496083789920012040215745627854092010308869223489833074860062054019221397227691063339148923860987250696934050122115972982286012688955816234717242567815830341836031567275888691320640526306946586793028267588302696611724356566003447616419092371914903382944112125852939011729294400479171568234647164730191643282793224422368321464125847020067
c2 = [12053085469218650692076937068797478047679005585690696222988148891925249697123080938461512785257424651119325211991331622346111396522606463631848519999574540677285771456451798811902760319940781754940936484802949729402283626052963389539032949160905330315285409948932070460455535716223838438994608837585387741418172014634472651248450564788332400265295308803291229281839428962457585593065595521459963501453576128172245723315811398209056633738967993602668795794847967331946516181453804430961308142497659799416125763566765485760600358126127595222197324155943818136202233758771243043559460620477085689770403810190118485243364, 13878717704635179949812987989626985689079485417345626168168664941124566737996226347895779823781042724620099437593856913505609774929187720381745418166924229828643565384137488017127800518133460531729559408120123922005898834268035918798610962941606864727966963354615441094676621013036726097763695675723672289505864372820096404707522755617527884121630784469379311199256277022770033036782130954108210409787680433301426480762532000133464370267551845990395683108170721952672388388178378604502610341465223041534665133155077544973384500983410220955683686526835733853985930134970899200234404716865462481142496209914197674463932]
'''

flag1，我觉得就是共模攻击，但是不知n要求n，然后去大佬糖醋小鸡块那里翻了一下(共模攻击)，还真有
https://tangcuxiaojikuai.xyz/post/9c1c22d0.html的Middle_RSA2，还是需要多构造的

$c1\equiv m^{e1}mod\ n$
$c2\equiv m^{e2}mod\ n$
$c1^{-e2}*c2^{e1}\equiv 1mod\ n$
$c1^{e2}\equiv c2^{e1}mod\ n$
$c1^{e2}-c2^{e1}=k*n$
$GCD求n即可$

from Crypto.Util.number import *
e = [43, 37, 53, 61, 59]
c1 = [304054249108643319766233669970696347228113825299195899223597844657873869914715629219753150469421333712176994329969288126081851180518874300706117, 300569071066351295347178153438463983525013294497692191767264949606466706307039662858235919677939911290402362961043621463108147721176372907055224,
      294806502799305839692215402958402593834563343055375943948669528217549597192296955202812118864208602813754722206211899285974414703769561292993531, 255660645085871679396238463457546909716172735210300668843127008526613931533718130479441396195102817055073131304413673178641069323813780056896835, 194084621856364235027333699558487834531380222896709707444060960982448111129722327145131992393643001072221754440877491070115199839112376948773978]
k1_n = c1[0]**e[1]-c1[1]**e[0]
k2_n = c1[1]**e[2]-c1[2]**e[1]
n = GCD(k1_n, k2_n)
print(long_to_bytes(n >> 310).decode())
# flag{3e99c26b-efdd-4c

flag2，费马小定理化简得到，$c2[0]\equiv m(mod\ p)$，$c2[1]\equiv m(mod\ q)$
参考博客

$方法1：此处不化简$
$c2[0]^{n}\equiv c2[1]^{p^{2}}mod\ n$
$c2[0]^{n}\equiv c2[1]mod\ p$
$p=GCD(pow(c2[0],n,n)-c2[1],n)$
$之后中国剩余定理求解m$

from Crypto.Util.number import *
from sympy.ntheory.modular import crt
n = 16175064088648626038689748434699435826247716579187475966092822028609536761351820951820375552440329596553448265674841223230257463367834546091974959931391707199002842774795702094681528411058318007858638798643010942408552063479863545047616823056802010158288409527763686086960916160949496083789920012040215745627854092010308869223489833074860062054019221397227691063339148923860987250696934050122115972982286012688955816234717242567815830341836031567275888691320640526306946586793028267588302696611724356566003447616419092371914903382944112125852939011729294400479171568234647164730191643282793224422368321464125847020067
c2 = [12053085469218650692076937068797478047679005585690696222988148891925249697123080938461512785257424651119325211991331622346111396522606463631848519999574540677285771456451798811902760319940781754940936484802949729402283626052963389539032949160905330315285409948932070460455535716223838438994608837585387741418172014634472651248450564788332400265295308803291229281839428962457585593065595521459963501453576128172245723315811398209056633738967993602668795794847967331946516181453804430961308142497659799416125763566765485760600358126127595222197324155943818136202233758771243043559460620477085689770403810190118485243364,
      13878717704635179949812987989626985689079485417345626168168664941124566737996226347895779823781042724620099437593856913505609774929187720381745418166924229828643565384137488017127800518133460531729559408120123922005898834268035918798610962941606864727966963354615441094676621013036726097763695675723672289505864372820096404707522755617527884121630784469379311199256277022770033036782130954108210409787680433301426480762532000133464370267551845990395683108170721952672388388178378604502610341465223041534665133155077544973384500983410220955683686526835733853985930134970899200234404716865462481142496209914197674463932]
p = GCD(pow(c2[0], n, n)-c2[1], n)
q = n // p
flag = crt([p, q], [c2[0], c2[1]])
print(long_to_bytes(flag[0]).decode())
# d2-bbe5-1420eaaa3b30}

$方法2：此次化简得到$
$c2[0]=m+k_{1}p$
$c2[1]=m+k_{2}q$
$1:\ c2[0]*c2[1]=m^{2}+(k_{1}p+k_{2}q)*m+k_{1}p*k2_{q}$
$2:\ m*(c2[0]+c2[1])=2*m^{2}+(k_{1}p+k_{2})*m$
$m^{2}-m*(c2[0]+c2[1])+c2[0]*c2[1]\equiv 0(mod\ n)$

# sage
from Crypto.Util.number import *
P,Q = [12053085469218650692076937068797478047679005585690696222988148891925249697123080938461512785257424651119325211991331622346111396522606463631848519999574540677285771456451798811902760319940781754940936484802949729402283626052963389539032949160905330315285409948932070460455535716223838438994608837585387741418172014634472651248450564788332400265295308803291229281839428962457585593065595521459963501453576128172245723315811398209056633738967993602668795794847967331946516181453804430961308142497659799416125763566765485760600358126127595222197324155943818136202233758771243043559460620477085689770403810190118485243364, 13878717704635179949812987989626985689079485417345626168168664941124566737996226347895779823781042724620099437593856913505609774929187720381745418166924229828643565384137488017127800518133460531729559408120123922005898834268035918798610962941606864727966963354615441094676621013036726097763695675723672289505864372820096404707522755617527884121630784469379311199256277022770033036782130954108210409787680433301426480762532000133464370267551845990395683108170721952672388388178378604502610341465223041534665133155077544973384500983410220955683686526835733853985930134970899200234404716865462481142496209914197674463932]
n = 16175064088648626038689748434699435826247716579187475966092822028609536761351820951820375552440329596553448265674841223230257463367834546091974959931391707199002842774795702094681528411058318007858638798643010942408552063479863545047616823056802010158288409527763686086960916160949496083789920012040215745627854092010308869223489833074860062054019221397227691063339148923860987250696934050122115972982286012688955816234717242567815830341836031567275888691320640526306946586793028267588302696611724356566003447616419092371914903382944112125852939011729294400479171568234647164730191643282793224422368321464125847020067

PR.<m> = PolynomialRing(Zmod(n))
f = m^2 - (P+Q)*m + P*Q
x0 = f.small_roots()
print(long_to_bytes(int(x0[0])).decode())
# d2-bbe5-1420eaaa3b30}

ezrsa-pcb2024

from Crypto.Util.number import *
from random import * 
from secret import flag
import os

def pad_flag(flag, bits=1024):
    pad = os.urandom(bits//8 - len(flag))
    return int.from_bytes(flag + pad, "big")

p,q = [getPrime(1024) for _ in "RSA"[1:]] 
a,b = [randint(0, 2**1024) for _ in "RSA"[:-1]] 

n = p * q
e = 0x10001
m = pad_flag(flag)

assert m < n

c = pow(m, e, n)

print(c)
print(n)
print(p + b * q)
print(a * p + q)

# 11850797596095451670524864488046085367812828367468720385501401042627802035427938560866042101544712923470757782908521283827297125349504897418356898752774318846698532487439368216818306352553082800908866174488983776084101115047054799618258909847935672497139557595959270012943240666681053544905262111921321629682394432293381001209674417203517322559283298774214341100975920287314509947562597521988516473281739331823626676843441511662000240327706777269733836703945274332346982187104319993337626265180132608256601473051048047584429295402047392826197446200263357260338332947498385907066370674323324146485465822881995994908925
# 21318014445451076173373282785176305352774631352746325570797607376133429388430074045541507180590869533728841479322829078527002230672051057531691634445544608584952008820389785877589775003311007782211153558201413379523215950193011250189319461422835303446888969202767656215090179505169679429932715040614611462819788222032915253996376941436179412296039698843901058781175173984980266474602529294294210502556931214075073722598225683528873417278644194278806584861250188304944748756498325965302770207316134309941501186831407953950259399116931502886169434888276069750811498361059787371599929532460624327554481179566565183721777
# 4780454330598494796755521994676122817049316484524449315904838558624282970709853419493322324981097593808974378840031638879097938241801612033487018497098140216369858849215655128326752931937595077084912993941304190099338282258345677248403566469008681644014648936628917169410836177868780315684341713654307395687505633335014603359767330561537038768638735748918661640474253502491969012573691915259958624247097465484616897537609020908205710563729989781151998857899164730749018285034659826333237729626543828084565456402192248651439973664388584573568717209037035304656129544659938260424175198672402598017357232325892636389317
# 9819969459625593669601382899520076842920503183309309803192703938113310555315820609668682700395783456748733586303741807720797250273398269491111457242928322099763695038354042594669354762377904219084248848357721789542296806917415858628166620939519882488036571575584114090978113723733730014540463867922496336721404035184980539976055043268531950537390688608145163366927155216880223837210005451630289274909202545128326823263729300705064272989684160839861214962848466991460734691634724996390718260697593087126527364129385260181297994656537605275019190025309958225118922301122440260517901900886521746387796688737094737637604

懂的都懂，原题，上周的强网杯也上了，apbq，脚本

# sage
from Crypto.Util.number import *
c=11850797596095451670524864488046085367812828367468720385501401042627802035427938560866042101544712923470757782908521283827297125349504897418356898752774318846698532487439368216818306352553082800908866174488983776084101115047054799618258909847935672497139557595959270012943240666681053544905262111921321629682394432293381001209674417203517322559283298774214341100975920287314509947562597521988516473281739331823626676843441511662000240327706777269733836703945274332346982187104319993337626265180132608256601473051048047584429295402047392826197446200263357260338332947498385907066370674323324146485465822881995994908925
n=21318014445451076173373282785176305352774631352746325570797607376133429388430074045541507180590869533728841479322829078527002230672051057531691634445544608584952008820389785877589775003311007782211153558201413379523215950193011250189319461422835303446888969202767656215090179505169679429932715040614611462819788222032915253996376941436179412296039698843901058781175173984980266474602529294294210502556931214075073722598225683528873417278644194278806584861250188304944748756498325965302770207316134309941501186831407953950259399116931502886169434888276069750811498361059787371599929532460624327554481179566565183721777
y=4780454330598494796755521994676122817049316484524449315904838558624282970709853419493322324981097593808974378840031638879097938241801612033487018497098140216369858849215655128326752931937595077084912993941304190099338282258345677248403566469008681644014648936628917169410836177868780315684341713654307395687505633335014603359767330561537038768638735748918661640474253502491969012573691915259958624247097465484616897537609020908205710563729989781151998857899164730749018285034659826333237729626543828084565456402192248651439973664388584573568717209037035304656129544659938260424175198672402598017357232325892636389317
x=9819969459625593669601382899520076842920503183309309803192703938113310555315820609668682700395783456748733586303741807720797250273398269491111457242928322099763695038354042594669354762377904219084248848357721789542296806917415858628166620939519882488036571575584114090978113723733730014540463867922496336721404035184980539976055043268531950537390688608145163366927155216880223837210005451630289274909202545128326823263729300705064272989684160839861214962848466991460734691634724996390718260697593087126527364129385260181297994656537605275019190025309958225118922301122440260517901900886521746387796688737094737637604


e = 65537

R = Integers(n)

P.<a, b, p, q> = PolynomialRing(Integers(n))

f1 = a*p + q

f2 = p + b*q

f3 = p*q

I = Ideal([f1 - x, f2 - y, f3 - n])
B = I.groebner_basis()


g = B[-1]

z = ZZ(g.coefficient({q: 1}))
assert g.constant_coefficient() == R(-y)

_, (z1, _), (z2, _) = list(g)
z1 = ZZ(z1)
z2 = ZZ(z2)

S = 2^1024

for p_upper_bits in range(16):
    p_upper = p_upper_bits << 1020
    for q_upper_bits in range(16):
        q_upper = q_upper_bits << 1020
        M = matrix(ZZ, [[S, -1, 0, 0], [S*z1, 0, -1, 0], [S*(z2 + p_upper + q_upper*z1), 0, 0, S], [S*n, 0, 0, 0]])
        B = M.LLL()
        for b in B:
            if b[-1] == S:
                if b[1] < 0:
                    b *= -1
                p_guess = b[1] + p_upper
                q_guess = b[2] + q_upper

                if p_guess * q_guess == n:
                    d = pow(e, -1, (p_guess - 1)*(q_guess - 1))
                    message = long_to_bytes(int(pow(c, d, n)))
                    if b'flag' in message:
                        print(message)
                        break

奇怪的是，这个脚本好像打不出来，上周强网杯是可以的

Alice’sSecret-pcb2024(after game)

from Crypto.Util.number import *
from Crypto.Cipher import AES
from hashlib import *
import random
import gmpy2
from secrets import iv, KEY

# I think you will definitely be interested in the content in PNG!
def banner():
    print(
        """
=======================================================================================
     _      _   _                 _           ____                                _   
    / \    | | (_)   ___    ___  ( )  ___    / ___|    ___    ___   _ __    ___  | |_ 
   / _ \   | | | |  / __|  / _ \ |/  / __|   \___ \   / _ \  / __| | '__|  / _ \ | __|
  / ___ \  | | | | | (__  |  __/     \__ \    ___) | |  __/ | (__  | |    |  __/ | |_ 
 /_/   \_\ |_| |_|  \___|  \___|     |___/   |____/   \___|  \___| |_|     \___|  \__|
                                                                                      
=======================================================================================
"""
    )

def pad(m):
    return m + (16 - (len(m) % 16)) * b"\x00"

def get_pngdata():
    with open("picture.png", "rb") as f:
        png_data = f.read()
    return pad(png_data)

def get_Key(bits):
    p = getPrime(bits)
    g = getPrime(bits // 2)
    d = random.randint(1, p - 2)
    y = pow(g, d, p)
    public, private = (p, g, y), d
    return public, private

def Signature(m, public, private):
    m = bytes_to_long(m)
    p, g, _ = public
    d = private
    while True:
        k = random.randint(1, p - 1)
        if gmpy2.gcd(k, p - 1) == 1:
            break
    r = pow(g, k, p)
    s = ((m - d * r) * inverse(k, p - 1)) % (p - 1)
    return (r, s)

def Verity(m, sign, public):
    m = bytes_to_long(m)
    p, g, y = public
    r, s = sign
    if pow(g, m, p) == (pow(y, r, p) * pow(r, s, p)) % p:
        return True
    else:
        return False

def chall():
    banner()

    pub, pri = get_Key(512)
    png_data = get_pngdata()
    print(
        "Hello! I'm Alice. To ensure that you are truly Bob, I need to verify your identity first!"
    )
    print("Can I help you sign once? Is there anything you need to sign?")
    print(f"Here are your public key:{pub}")
    message = long_to_bytes(int(input("Give me what you need to sign:")))
    if message == b"Bob":
        print("No, it's not possible!!!")
        exit(1)
    print("Here are your sign:")
    r, s = Signature(message, pub, pri)
    print(f"r = {r}")
    print(f"s = {s}")

    print("Tell me your signature so that I know you are truly Bob.")
    r = int(input("r = "))
    s = int(input("s = "))

    if Verity(b"Bob", (r, s), pub):
        print(
            "I have a great photo that I would like to share with you. Let's send it to you in our old way! Hope you still keep our IV!"
        )
        aes = AES.new(KEY, AES.MODE_CBC, iv)
        enc_data = hex(bytes_to_long(aes.encrypt(png_data)))[2:]
        print(f"Here is my encoded data:{enc_data}")
        print(f"Here is my key:{KEY.decode()}")
        print("In summary, I wish you a wonderful day!")
    else:
        print("Alright, you're not Bob, I don't have anything to chat with anymore.")
        exit(1)

if __name__ == "__main__":
    try:
        chall()
    except:
        exit(1)

这道题(当时好眼熟，没看出来)，ElGamal签名方案，但是环境题，想放后面做，结果没时间看了

赛后再看，应该就是选择签名伪造了，这里我们可以得到消息的签名(即rs)，然后进行验证

https://ctf-wiki.org/crypto/signature/elgamal/#_15
所以关键在于伪造消息b'xxxx'与b'Bob模p-1同余，同时题目还把公钥给了我们(p, g, y)，有p就够了

其实就是费马小定理，可以这样$g^{m}\equiv g^{m+k*(p-1)}(mod\ p)$
代码表示，message = long_to_bytes(bytes_to_long(b'Bob')+pub[0]-1)

后面是AES，题目会给我们KEY，还是CBC mode，所以我们要把iv找出来


还是老样子，png的前十六字节是固定的，0x89504e470d0a1a0a0000000d49484452，我们可以把密文通过key解密之后的数据异或png的文件头，即可拿到题目中的iv
然后，密文通过key解密之后的数据，可以自己把iv设成全零，即可得到

from Crypto.Util.number import *
from Crypto.Cipher import AES

# 消息伪造
pub = ()
message = bytes_to_long(b'Bob')+pub[0]-1
print(message)

# iv恢复
enc_data = ''
key = b''
head = 0x89504e470d0a1a0a0000000d49484452
aes = AES.new(key, AES.MODE_CBC, iv=b'\x00'*16)
data = bytes_to_long(aes.decrypt(bytes.fromhex(enc_data)[:16]))
iv = long_to_bytes(data ^ head)
aes = AES.new(key, AES.MODE_CBC, iv)
png_data =aes.decrypt(bytes.fromhex(enc_data))
with open('picture.png','wb')as f:
    f.write(png_data)

思路跟大致的脚本如上，环境也没有了，就不写交互脚本了

tarssc-pcb2024(复现)

from Crypto.Util.number import *
from secret import flag
import random

nbit  = 1024
beta  = 0.30
delta = 0.10

p = getPrime(int(beta * nbit))
q = getPrime(nbit - int(beta * nbit))

N = p * q
phi = (p-1) * (q-1)
while 1:
    dq = random.randrange(1,int(N ** delta))
    if dq > q-1:
        continue
    dp = random.randrange(1,p-1)
    try:
        d = Integer(crt([dp%(p-1),dq%(q-1)],[p-1,q-1]))
    except:
        continue
    if GCD(d,phi) == 1:
        e = int(inverse(d,phi))
        break

seckey, pubkey = (p,q,d,dp,dq), (N,e)
print(f"N = {N}")
print(f"e = {e}")

c = pow(bytes_to_long(flag), e, N)
print(f"c = {c}")
"""
N = 61857467041120006957454494977971762866359211220721592255304580940306873708357617802596067329984189345493420858543581027612648626678588277060222860337783377316655375278359169520243355170247177279595812282793212550819124960549824278287538977769728573023023364686725321548391592858202718446127851076431000427033
e = 22696852369762746127523066296087974245933137295782964284054040654103039210164173227291367914580709029582944005335464668969366909190396194570924426653294883884186299265660358589254391341147028477295482787041170991166896788171334992065199814524969470117229229967188623636764051681654720429531708441920158042161
c = 41862679760722981662840433621129671566139143933210627878095169470855743742734397276638345217059912784871301273620533442249011607182329472311453700434692358352210197988000738272869600692181834281813995048665466937302183039555350612260646428575598237960405962714063137455677605629008760761743568236135324015278
"""

这题很明显是crtRSA
看到有一题类似的，2021的极客大挑战crtrsa
卡这题卡半天，可以测试一下题目的代码，发现dq是比dp小的，二者不平衡
可以试试dq泄露https://www.cnblogs.com/vconlln/p/17066500.html
还发现了一篇论文
https://dds.sciengine.com/cfs/files/pdfs/1674-7267/6qxpd6SSmokuc5vLD-mark.pdf

# sage
from copy import deepcopy
# https://www.iacr.org/archive/pkc2006/39580001/39580001.pdf
# Author: ZM__________J, To1in
N = 61857467041120006957454494977971762866359211220721592255304580940306873708357617802596067329984189345493420858543581027612648626678588277060222860337783377316655375278359169520243355170247177279595812282793212550819124960549824278287538977769728573023023364686725321548391592858202718446127851076431000427033
e = 22696852369762746127523066296087974245933137295782964284054040654103039210164173227291367914580709029582944005335464668969366909190396194570924426653294883884186299265660358589254391341147028477295482787041170991166896788171334992065199814524969470117229229967188623636764051681654720429531708441920158042161
c = 41862679760722981662840433621129671566139143933210627878095169470855743742734397276638345217059912784871301273620533442249011607182329472311453700434692358352210197988000738272869600692181834281813995048665466937302183039555350612260646428575598237960405962714063137455677605629008760761743568236135324015278
alpha = log(e, N)
beta = 0.30
delta = 0.10
P.<x,y,z>=PolynomialRing(ZZ)
 
X = ceil(2 * N^(alpha + beta + delta - 1))
Y = ceil(2 * N^beta)
Z = ceil(2 * N^(1 - beta))
 
def f(x,y):
    return x*(N-y)+N
def trans(f):
    my_tuples = f.exponents(as_ETuples=False)
    g = 0
    for my_tuple in my_tuples:
        exponent = list(my_tuple)
        mon = x ^ exponent[0] * y ^ exponent[1] * z ^ exponent[2]
        tmp = f.monomial_coefficient(mon)
        
        my_minus = min(exponent[1], exponent[2])
        exponent[1] -= my_minus
        exponent[2] -= my_minus
        tmp *= N^my_minus
        tmp *= x ^ exponent[0] * y ^ exponent[1] * z ^ exponent[2]
        
        g += tmp
    return g
  
m = 5 # need to be adjusted according to different situations
tau = ((1 - beta)^2 - delta) / (2 * beta * (1 - beta))
sigma = (1 - beta - delta) / (2 * (1 - beta))
 
print(sigma * m)
print(tau * m)
 
s = ceil(sigma * m)
t = ceil(tau * m)
my_polynomials = []
for i in range(m+1):
    for j in range(m-i+1):
        g_ij = trans(e^(m-i) * x^j * z^s * f(x, y)^i)
        my_polynomials.append(g_ij)
 
for i in range(m+1):
    for j in range(1, t+1):
        h_ij = trans(e^(m-i) * y^j * z^s * f(x, y)^i)
        my_polynomials.append(h_ij)
        
known_set = set()
new_polynomials = []
my_monomials = []
 
# construct partial order
while len(my_polynomials) > 0:
    for i in range(len(my_polynomials)):
        f = my_polynomials[i]
        current_monomial_set = set(x^tx * y^ty * z^tz for tx, ty, tz in f.exponents(as_ETuples=False))
        delta_set = current_monomial_set - known_set
        if len(delta_set) == 1:
            new_monomial = list(delta_set)[0]
            my_monomials.append(new_monomial)
            known_set |= current_monomial_set
            new_polynomials.append(f)            
            my_polynomials.pop(i)
            break
    else:
        raise Exception('GG')
        
my_polynomials = deepcopy(new_polynomials)
 
nrows = len(my_polynomials)
ncols = len(my_monomials)
L = [[0 for j in range(ncols)] for i in range(nrows)]
 
for i in range(nrows):
    g_scale = my_polynomials[i](X * x, Y * y, Z * z)
    for j in range(ncols):
        L[i][j] = g_scale.monomial_coefficient(my_monomials[j])
        
# remove N^j
for i in range(nrows):
    Lii = L[i][i]
    N_Power = 1
    while (Lii % N == 0):
        N_Power *= N
        Lii //= N
    L[i][i] = Lii
    for j in range(ncols):
        if (j != i):
            L[i][j] = (L[i][j] * inverse_mod(N_Power, e^m))
 
L = Matrix(ZZ, L)
nrows = L.nrows()
 
L = L.LLL()
# Recover poly
reduced_polynomials = []
for i in range(nrows):
    g_l = 0
    for j in range(ncols):
        g_l += L[i][j] // my_monomials[j](X, Y, Z) * my_monomials[j]
    reduced_polynomials.append(g_l)
 
# eliminate z
my_ideal_list = [y * z - N] + reduced_polynomials
 
# Variety
my_ideal_list = [Hi.change_ring(QQ) for Hi in my_ideal_list]
for i in range(len(my_ideal_list),3,-1):
    print(i)
    V = Ideal(my_ideal_list[:i]).variety(ring=ZZ)
    if V:
        p = int(V[0]['y'])
        q = N//p
        from Crypto.Util.number import *
        d = inverse(e,(p-1)*(q-1))
        m = pow(c,d,N)
        print(long_to_bytes(int(m)).decode())
        break

确实是没有想到，比赛时方向一直卡在crtrsa，没太往dp泄露这边想

下面挂的是还没打出来的密码题，都大致看了一眼，当时时间不够了，一堆事围着我，吐了吐了，还是太菜了，不够快

UNSOLVED

polyprime-pcb2024

from Crypto.Util.number import getPrime, isPrime, bytes_to_long
from secret import flag
import random

k = getPrime(333 * 5)
e = 65537
m = bytes_to_long(flag)

def temp_calc(x): 
    return (x * random.randint(2, 5)) ^ random.randint(100, 500)

def some_calc(size, depth):
    def sums_calc(base, degree): 
        result = 0
        for i in range(degree): 
            temp = temp_calc(base ** i)
            result += base ** i + temp // temp_calc(base**(i + 1))
        return result

    while True:
        prime_number = getPrime(size)

        temp_number = temp_calc(prime_number)
        poly_primes = sums_calc(prime_number, depth)  
        if temp_number % 3 == 0: 
            temp_number = temp_calc(poly_primes)
            continue
        
        if isPrime(poly_primes):
            return prime_number, poly_primes

p, q = some_calc(333, 5)

n = p * q * k
c = pow(m, e, n)

print(f"{n = }")
print(f"{e = }")
print(f"{c = }")

# n = 659401821142664131364043958430747314465977448744532421905138184036743766362324320051729418680079590835903781525157600055608268591994754328563246418114269690475272262915661210669701969695314157602927462228079044905276064391615467601628466982949165371933147600418057089432876120807721483665788557812323607370950442342057254926375842684430119320789097029996211564275310819486004520088130146630452262340185192110066151930586956190499953220051855668474863659201165952231016814569364299000130323859609047687714260776467149437031397019411599103716200258382231589757031469168245396061619327867355414287059363691024984066070128364157490336808211223714816668548049472199794493895870662970541167490686648385211854469386812214775829776376273299648505880034651930322294605482489225723014758138525637864689594748771025870209444029669477294995691067669374491852721622469656239730320092112222948718027850386898461208936333788173263904607181823233002355650353116486156927403178510412091666951574340730799316032588099237
# c = 455042981325030540026829365098432813829591020497037525707600104817313008442900331256387443469027825344761381076471749826547710666806180999603254398722965179851898391700090501419875562919365894255855734276825027850795202733875071307773598881254863911398285400038957998385685292965812925607278232164067624548120378758414574370042945538632864154772437639053907149514588502689277630450575630168099810584842881257614115970132960679023265157277718654731105815060916800751033956715430930381384344469220951638102432198422350425390757155267143393385221465041749156153517556389417033187856017198907366720281408810250981776112815100319814215140919133440637395953567624057248002125277569474190364142291136361144552953540727462623677375371327473687508344483184466522697912317252462246054471196345909304668083637177166153036111122244170846815657389873986264187766636830907458940128844256504176917204131708083105093700023335939233711693409336968008112511482237441198116493965744903995545941700742865846469036763734618
# e = 0x10001

rickroll-pcb2024

from Crypto.Util.number import *
from Crypto.Util.Padding import pad
from pwn import xor
import os
from hashlib import *
from random import *

HINT = ?
FLAG = "flag{xxxxxxxx}"
EFFECTIVE_ROW = 6

def rickroll_loader():
    with open("rickroll", "r") as file:
        lines = [line.strip().encode() for line in file if line.strip()]
    return lines

def find_ezprime(size):
    while True:
        prime = getPrime(size)
        if isPrime(prime // 2):
            return prime

def secure_encrypt(message_parts, hint_value):
    modulus = find_ezprime(260)

    key_material = os.urandom(32)
    multipliers = [getrandbits(256) for _ in range(EFFECTIVE_ROW)]

    encrypted_parts = [
        int((multiplier * hint_value + bytes_to_long(xor(pad(chunk, 32)
            [::-1], key_material))) % (modulus - 1))
        for multiplier, chunk in zip(multipliers, message_parts)
    ]

    return encrypted_parts, multipliers, modulus

if __name__ == "__main__":
    rickroll = rickroll_loader()
    m = bytes_to_long(HINT)

    encrypted_lyrics, multipliers, modulus = secure_encrypt(
        rickroll[:EFFECTIVE_ROW], m)

    print("S =", encrypted_lyrics)
    print("V =", multipliers)
    print("n =", modulus)

'''
S = [624073892368439332713131144655355187273652775732037030273908973687487472640419, 1129513550732743550887354593625951854836036688324123410864182971141396110133306, 1117643028354341949186759218964558582164677605237787761003042032239935547551873, 151619055620013230556169740951169935393567570823439146992800622058967940011364, 596106506159944398847755500086869373163910176213091804211992440336880292610397, 685472210701608040945173323626153641749419080165879222271110177606156013942182]
V = [100024809269721744282017864103544473542698741247649693420201028956644193231147, 85493218764912449360009112267171851264674952927507787108286827385372626006804, 75451455656190167222034904545925816909383290106210237096763781707294423744719, 1864420400658866895837249178680154965580281261003086054650703872439476331244, 111069754111223622246512532174936637994215526100226395068812327641951277359169, 88031405587803201423744918486788030404029698214504194443110805396831023823738]
n = 1497114501625523578039715607844306226528709444454126120151416887663514076507099
'''
# rickroll

Never gonna give you up
Never gonna let you down
Never gonna run around and desert you

Never gonna make you cry
Never gonna say goodbye
Never gonna tell a lie and hurt you

--A mysterious singer who does not want to be named.

END

还得找个时间补一下，中大爷Lst4r干了五题，QWQ
（希望可以去线下玩玩吧

听说web有人AK了，指个路
https://infernity.top/2024/11/09/2024鹏城杯web全wp/