CNSS-Recruit2025-Crypto-WriteUp

Crypto

🌟栖居于可能性之中

MNZWK327L5SW6ZDGOJ2GQZLPMNPWS5LOPNWG25DUL5ZF6X3ZN5XV65LBNJXHG43XMNSW62DXNRXWG4C7OB4V63TPL56Q====

Base32 + (Fence=3)
cnss{welcome_to_the_world_of_crypto_hope_you_can_join_us}

🎏波兰来客

from Crypto.Util.number import *
from sage.all import *
from secret import flag11

p = getPrime(512)
m = bytes_to_long(flag11)
e = 0x10001

c = pow(m, e, p)
print(f'c = {c}')
print(f'p = {p}')

#RSA is the most commonly used asymmetric encryption, you can study it clearly

'''
c = 857160393763200018136243293304734832626469366898671548658063982128301976510619912965430915666613801166650348101081196429027045093249075734871210100148502
p = 13144680786411281909389708068802789151202603464528138622729955260404242510138660030278439234468305471409260753796094593554849276654701859454461337034174099
'''

单素数RSA，phi=p-1
太简单就不放代码了
cnss{welcome_to_the_world_of_number_theory}

🪄贝阿朵莉切的传说

from sage.all import*
from Beatrices_magic import magic_of_love
from secret import flag10
from Crypto.Util.number import *

n = prod([magic_of_love('This function can find a 512-bit prime within the consecutive digits of π, and you will never be able to decrypt it!') for _ in range(6)])
m = bytes_to_long(flag10)
assert m < n
c = power_mod(m, 0x10001, n)

with open('output10.txt', 'w') as f:
    f.write(f'n = {n}\n')
    f.write(f'c = {c}\n')
"""
n = 521918091937867626454155236624054544603510014039284694091636699437510894391152159211125227423542579838154927599065336125096528001249561366603662452297166996584681134504824972567965819751814858534655055084423547289276630393826952546685534329235118520697172050439155214602603881552385389099474083637082166573036865307157645837184525760963062765716230623357954202242424789293750862836579062199128743608184334985642380401359931662411542641662525882519015888888152718325353530420919100598407845631758819769876654881166740227951871744111204484767596423474757389815535953291982473519122137034530070651746586885076335553540700572697842608743426749662045740260754604875331910940467862656556013856400735800258067377736544159184376805934344571975446770537058595274440355028547881344205554402726825306139031704869478515819223028865435892887668130594346970335394289274650157484920887903423491772068385257952792337043832826461986365683321
c = 459551483703398969753583509531156753644834356994813274637718869401770559618414838203635094684391673443234656865447628776624317350837495974978140684572398589157547348990178078284470951181081027372730225337943341978361779537898715003764518073079546174747729803505861949752589995848366196573243164634829553158093887746572161845602226954758541479519080294093286689766767449360598345571320518741821108090435338536630509932993229075615206434774578764078184331827963144487808801131957283893003259264922902700862655251047873003145835458015801076344223798970767266322778905512791112615303289850362924887105863748039809266973137138293737758372194503724596551602550703162050906442611755576947937309195772803617436971835647038618852514871688085575259922642871036768937712536129329294607754153502344983130258047646801229084104924162171527038601693128642395022554302792717460774515300980203494167056499312325186874022086701501029428210810
"""

找圆周率小数部分中的6个512bits的素数

• 圆周率小数一百万位
• 一千万位

实际上能找出前3个因子就够了(只要m小于当前选择的n=pqr即可，这也是一个很常规的应用，有的时候是不需要知道全部因子才能求的，m小于当前选择的模数即可)，区间应该在1w-100w

import gmpy2
import time
from Crypto.Util.number import *

n = 521918091937867626454155236624054544603510014039284694091636699437510894391152159211125227423542579838154927599065336125096528001249561366603662452297166996584681134504824972567965819751814858534655055084423547289276630393826952546685534329235118520697172050439155214602603881552385389099474083637082166573036865307157645837184525760963062765716230623357954202242424789293750862836579062199128743608184334985642380401359931662411542641662525882519015888888152718325353530420919100598407845631758819769876654881166740227951871744111204484767596423474757389815535953291982473519122137034530070651746586885076335553540700572697842608743426749662045740260754604875331910940467862656556013856400735800258067377736544159184376805934344571975446770537058595274440355028547881344205554402726825306139031704869478515819223028865435892887668130594346970335394289274650157484920887903423491772068385257952792337043832826461986365683321
c = 459551483703398969753583509531156753644834356994813274637718869401770559618414838203635094684391673443234656865447628776624317350837495974978140684572398589157547348990178078284470951181081027372730225337943341978361779537898715003764518073079546174747729803505861949752589995848366196573243164634829553158093887746572161845602226954758541479519080294093286689766767449360598345571320518741821108090435338536630509932993229075615206434774578764078184331827963144487808801131957283893003259264922902700862655251047873003145835458015801076344223798970767266322778905512791112615303289850362924887105863748039809266973137138293737758372194503724596551602550703162050906442611755576947937309195772803617436971835647038618852514871688085575259922642871036768937712536129329294607754153502344983130258047646801229084104924162171527038601693128642395022554302792717460774515300980203494167056499312325186874022086701501029428210810
e = 0x10001

def find_prime_factors_in_pi(pi_digits_file, prime_digit_length, num_factors_to_find=6):

    print(f"开始在文件 '{pi_digits_file}' 中搜索 {prime_digit_length} 位的素数因子...")
    print(f"目标是找到 {num_factors_to_find} 个因子。")

    try:
        with open(pi_digits_file, 'r') as f:
            pi_str = f.read()

        found_factors = []
        current_n = n
        start_pos = 0
        global_start_time = time.time()

        while len(found_factors) < num_factors_to_find:
            factor_found_in_this_pass = False

            if len(pi_str) - start_pos < prime_digit_length:
                print("\nPi文件剩余位数不足，无法继续搜索。")
                break

            print(
                f"\n--- 正在搜索第 {len(found_factors) + 1} 个因子 (剩余 n 的位数: {current_n.bit_length()}) ---")
            print(f"从π小数第 {start_pos + 1} 位开始搜索...")

            pass_start_time = time.time()

            for i in range(start_pos, len(pi_str) - prime_digit_length + 1):
                candidate_str = pi_str[i: i + prime_digit_length]
                candidate_num = gmpy2.mpz(candidate_str)

                if gmpy2.is_prime(candidate_num):
                    if current_n % candidate_num == 0:
                        factor = candidate_num
                        found_factors.append(factor)

                        pass_end_time = time.time()
                        print("\n" + "="*50)
                        print(f"成功找到第 {len(found_factors)} 个素数因子！")
                        print(f"因子: {factor}")
                        print(f"它位于π小数部分的第 {i + 1} 位开始。")
                        print(
                            f"查找此因子用时: {pass_end_time - pass_start_time:.4f} 秒")
                        print("="*50)

                        current_n //= factor
                        start_pos = i + 1
                        factor_found_in_this_pass = True

                        break

            if not factor_found_in_this_pass:
                print(f"\n在从位置 {start_pos + 1} 开始的剩余Pi数字中未找到更多因子。")
                break

        global_end_time = time.time()
        print("\n" + "#"*50)
        print("所有搜索完成。")
        print(f"总用时: {global_end_time - global_start_time:.4f} 秒")
        phi = 1
        N = 1
        if found_factors:
            print(f"共找到 {len(found_factors)} 个因子:")
            for i, factor in enumerate(found_factors):
                print(f"  因子 {i+1}: {factor}")
                phi *= (factor - 1)
                N *= factor
            d = inverse(e, phi)
            flag = pow(c, d, N)
            print(f"计算得到的 flag: {long_to_bytes(flag).decode()}")
        else:
            print("未找到任何因子。")
        print("#"*50)

        return found_factors

    except FileNotFoundError:
        print(f"错误：找不到文件 '{pi_digits_file}'。请确保文件存在于正确的位置。")
        return None

found_factors_list = find_prime_factors_in_pi(
    pi_digits_file="pai.txt",
    prime_digit_length=155,
    num_factors_to_find=6
)
# cnss{Umineko is a good game, If you've played this game, I might consider giving you some extra points (just kidding, but the game is really fun!)}

🌧️November Rain

from Crypto.Cipher import AES
from Crypto.Util.number import*
import os
import base64
from secret import  flag8
iv = long_to_bytes(int(flag8.strip(b'cnss{').strip(b'}')))
key = os.urandom(16)

hint = os.urandom(4) * 8
print(bytes_to_long(hint) ^ bytes_to_long(key))
msg = b'CNSS is a big happy family, and we hope you can successfully join us. CNSS-chan has been looking forward to your arrival :))))!!'

def encrypto(message):
    aes = AES.new(key,AES.MODE_CBC,iv)
    return aes.encrypt(message)

print(base64.b64encode(encrypto(msg)[-48:]))

'''
7247074606860797347397352236235906489165611013788020866468477972070266910937

b'PW7xp+ScMUPvssOTxynA0vmLSedY4wox/Xkr49uGmoxOmr/dKBoZ2REEimTv7v1A'
'''

hint xor key结果的高十六字节异或低十六字节即可恢复key（异或运算的规则下，key高十六字节为全0）
通过已知的全部明文和最后的三个密文块，结合key（AES-ECB-decrypt）向前推导（xor），恢复iv

from Crypto.Cipher import AES
from Crypto.Util.number import long_to_bytes, bytes_to_long
from Crypto.Util.Padding import pad
import base64

def xor(a, b):
    return bytes(x ^ y for x, y in zip(a, b))

def encrypto(message):
    aes = AES.new(key, AES.MODE_CBC, iv_bytes)
    return aes.encrypt(message)

hint_xor_key = 7247074606860797347397352236235906489165611013788020866468477972070266910937
b64_ciphertext = b'PW7xp+ScMUPvssOTxynA0vmLSedY4wox/Xkr49uGmoxOmr/dKBoZ2REEimTv7v1A'
msg = b'CNSS is a big happy family, and we hope you can successfully join us. CNSS-chan has been looking forward to your arrival :))))!!'

hint_xor_key = long_to_bytes(hint_xor_key)
key = xor(hint_xor_key[:16], hint_xor_key[16:])

cipher_blocks = [base64.b64decode(b64_ciphertext)[i:i+16]
                 for i in range(0, 48, 16)]
cipher_blocks = cipher_blocks[::-1]
msg_blocks = [msg[i:i+16] for i in range(0, len(msg), 16)]

aes = AES.new(key, AES.MODE_ECB)
for i in range(5, -1, -1):
    temp = aes.decrypt(cipher_blocks[-1])
    cipher_blocks.append(xor(temp, msg_blocks[i]))

iv_bytes = cipher_blocks[-1]

assert base64.b64encode(encrypto(msg)[-48:]) == b64_ciphertext

iv = bytes_to_long(iv_bytes)
flag = f"cnss{{{iv}}}"
print(flag)
# cnss{259936502081082258767763063599318618259}

🎡Ever17

from Crypto.Util.number import*
from secret import FLAG
from sage.all import*
from gmpy2 import*

flag1 = FLAG[:13]
flag2 = FLAG[13:]
#FLAG = cnss{xxx}

a = bytes_to_long(flag1)
b = bytes_to_long(flag2)
print(b)
assert a.bit_length() + b.bit_length() <= 230

p = next_prime(a)
q = next_prime(p)
n = p * q
e = p - a

t = getPrime(127)  
pp = getPrime(128)
R = Integers(t)
d = power_mod(13, R(b**3-b+1), pp)
print(R(b**3 - b + 1))

print("n = {}".format(n))
print("e = {}".format(e))
print("pp = {}".format(pp))
print("d = {}".format(d))
print("t = {}".format(t))

'''
n = 62059276114488335404539537873896627084226282430239010310558911
e = 39
pp = 312259503360917714041582848661140302699
d = 210422286411000941403494297143869304854
t = 124465960300667960302951153129553600783
'''

$相邻的两个素数：开平方找下一个素数即可，或者费马分解法$

$d\equiv 13^{b^3-b+1}\equiv 13^B\pmod {pp}$
$DLP求解B$

$b^3-b+1=B\pmod t$
$f(b)\equiv 0\equiv b^3-b+1-B\pmod t$
$通过多项式环的根，求解b$

# sage
from sympy import nextprime, prevprime
from Crypto.Util.number import *

n = 62059276114488335404539537873896627084226282430239010310558911
pp = 312259503360917714041582848661140302699
d = 210422286411000941403494297143869304854
t = 124465960300667960302951153129553600783

n2 = sqrt(n)
p = nextprime(n2)
q = n//p
flag1 = long_to_bytes(min(p, q)-39).decode()

R = GF(pp)
B = R(d).log(R(13))
PolyRing = PolynomialRing(Zmod(t), 'b')
b = PolyRing.gen()
f = b^3 - b + 1 - B
roots = f.roots()
flag2 = long_to_bytes(int(roots[0][0])).decode()

print(flag1 + flag2)
# cnss{Live1sSh0r7,Y0un33dSa9e}

📻坏掉的收音机

from secret import FLAG4
from Crypto.Util.number import *
from sage.all import*

m = bytes_to_long(FLAG4)

p = getPrime(1024)
q = getPrime(1024)  
N = p * q
phi = (p-1) * (q-1)

d = getRandomNBitInteger(500)  
assert GCD(d, phi) == 1 
e = inverse(d, phi)
c = power_mod(m, e, N)
print("c = {}".format(c))
print("e = {}".format(e))
print("N = {}".format(N))

'''
c = 8593625836367917764986091537862661394327845125958492795352878044172899648510875879133512661014999777302814930717163447720774860586907847681466581673038469991865927343725317629832933726187701382821083817561174786833492609115270480453109104538437515403110732126788196704586145936288552936640919531366811895714904827689397219311679095253607533956536809523167055725880185938101621676100671431648900864949379940933213077053652267092900963895945525437638158045737486550900359435298370224477273147512654096329734627945308150919670603172469135775474607423778358900151823484950999883188363171092959718200419629869054434944384
e = 1442973038831134781460545372668079573791255089510655684278169469518912344749453458527088628470363767104256664623064615249201126365247301906994228337491351910766820781592919954944540203871005778312943861046561877144710178914425186934644106916241015271110026033506622787659963342121470374665194430565858920858930941905531265541417128036020226443397870780895679565107220766770064617603043374136075499771747782563506316373720220877801857709735087319543656430075257981135224646591210239275335059365770992064147754537760540339692837252836885650096625839221047936662519348425289556777515319440792080034245198540405529479523
N = 10864811587894087046912389551445784477443478981530416841951072489270014664625868038611938460346743770608824515132925518342460413354827851767413150762025536287317538557271656618262172933337517229049499712951738056866379457624619837197764161456176413247466972758765501483282288192647013542746965392115684146291803209523100433142063984408890127553887512053367391034721571868380432612782024648063590732495824077292627245149142473617621479947679459677428299115294783881029177338636558399567530359530552401953931661755828342984316976497592368390287838236503122722531045894613429408246557048894016811755207012570359840134849
'''

$en大小近似：Winner\ Attack$
$套板子即可$

from Crypto.Util.number import *

def continuedFra(x, y):
    cf = []
    while y:
        cf.append(x // y)
        x, y = y, x % y
    return cf

def gradualFra(cf):
    numerator = 0  # 分子
    denominator = 1  # 分母
    for x in cf[::-1]:
        numerator, denominator = denominator, x * denominator + numerator
    return numerator, denominator

def getGradualFra(cf):
    gf = []
    for i in range(1, len(cf) + 1):
        gf.append(gradualFra(cf[:i]))
    return gf

def wienerAttack(e, n):
    cf = continuedFra(e, n)
    gf = getGradualFra(cf)
    for d, k in gf:
        if d.bit_length() == 500:
            return d

c = 8593625836367917764986091537862661394327845125958492795352878044172899648510875879133512661014999777302814930717163447720774860586907847681466581673038469991865927343725317629832933726187701382821083817561174786833492609115270480453109104538437515403110732126788196704586145936288552936640919531366811895714904827689397219311679095253607533956536809523167055725880185938101621676100671431648900864949379940933213077053652267092900963895945525437638158045737486550900359435298370224477273147512654096329734627945308150919670603172469135775474607423778358900151823484950999883188363171092959718200419629869054434944384
e = 1442973038831134781460545372668079573791255089510655684278169469518912344749453458527088628470363767104256664623064615249201126365247301906994228337491351910766820781592919954944540203871005778312943861046561877144710178914425186934644106916241015271110026033506622787659963342121470374665194430565858920858930941905531265541417128036020226443397870780895679565107220766770064617603043374136075499771747782563506316373720220877801857709735087319543656430075257981135224646591210239275335059365770992064147754537760540339692837252836885650096625839221047936662519348425289556777515319440792080034245198540405529479523
N = 10864811587894087046912389551445784477443478981530416841951072489270014664625868038611938460346743770608824515132925518342460413354827851767413150762025536287317538557271656618262172933337517229049499712951738056866379457624619837197764161456176413247466972758765501483282288192647013542746965392115684146291803209523100433142063984408890127553887512053367391034721571868380432612782024648063590732495824077292627245149142473617621479947679459677428299115294783881029177338636558399567530359530552401953931661755828342984316976497592368390287838236503122722531045894613429408246557048894016811755207012570359840134849
d = wienerAttack(e, N)
flag = long_to_bytes(pow(c, d, N)).decode()
print(flag)
# cnss{R5A_4as_Many_D1fferent_attacks,and_w1ener_Attack_is_on3_0f_the_cla5s1c_0nes}

🌸鲜花盛开的森林

from sage.all import*
from Crypto.Util.number import*
from secret import FlAG3

def gen_ecc_key(nbits):
    p = getPrime(nbits)
    q = getPrime(nbits)
    r = getPrime(nbits)
    n = p * q * r

    while True:
        a = getRandomInteger(nbits)
        b = getRandomInteger(nbits)
        if gcd(4 * a ** 3 + 27 * b ** 2, n) == 1:
            break
    E = EllipticCurve(Zmod(n), [a, b])
    e = getPrime(10)
    return n, E, e, p, q, r, a, b

x = bytes_to_long(FlAG3)
n, E, e, p, q, r, a, b = gen_ecc_key(83)
pt = E.lift_x(Integer(x))
ct = pt * e
print("p = {}".format(p))
print("q = {}".format(q))
print("r = {}".format(r))
print("a = {}".format(a))
print("b = {}".format(b))
print("e = {}".format(e))
print("cc = {}".format(Integer(ct[0])))

'''
p = 15078272222950150537
q = 16351967803352092039
r = 14892319684336011143
a = 196082585826675836
b = 17207772750460583034
e = 719
cc = 2733006338538398832311230797238861624963229236397553282448
'''

这题就是简单的ECDLP+CRT

$ct=e*pt$

已知的是ct的横坐标x，但pt也恰好是横坐标满足flag的点，因此只需要找到逆元即可恢复pt

但整数环的阶并不方便计算，n还不是素数，E.order() sage会直接报错，因此得借助n的三个小素数crt恢复flag

在素数域下E.lift_x(cc)会得到两个点(加参数：all=True)，但这道题目只需要考虑横坐标x，因此任意一个点都可以恢复flag，不用这么麻烦

from sage.all import *
from Crypto.Util.number import *

p = 15078272222950150537
q = 16351967803352092039
r = 14892319684336011143
a = 196082585826675836
b = 17207772750460583034
e = 719
cc = 2733006338538398832311230797238861624963229236397553282448

E_p = EllipticCurve(GF(p), [a, b])
E_q = EllipticCurve(GF(q), [a, b])
E_r = EllipticCurve(GF(r), [a, b])

cc_p = cc % p
cc_q = cc % q
cc_r = cc % r

ct_p = E_p.lift_x(cc_p)
ct_q = E_q.lift_x(cc_q)
ct_r = E_r.lift_x(cc_r)

ord_p = E_p.order()
ord_q = E_q.order()
ord_r = E_r.order()

d_p = inverse(e, ord_p)
d_q = inverse(e, ord_q)
d_r = inverse(e, ord_r)

pt_p = d_p * ct_p
pt_q = d_q * ct_q
pt_r = d_r * ct_r

x_p = int(pt_p[0])
x_q = int(pt_q[0])
x_r = int(pt_r[0])

x = CRT([x_p, x_q, x_r], [p, q, r])
flag = long_to_bytes(x).decode()
print(flag)
# cnss{ECC_is_1mp0r7ant!}

☀️20世纪少年

from Crypto.Util.number import*
from sage.all import*
from gmpy2 import*
from secret import FLAG2

p = getPrime(512)
q = getPrime(512)
r = getPrime(1024)
e = inverse(p * q, (p - 1) * (q - 1) * (r - 1))
n = p * q * r
d = p + q
m = bytes_to_long(FLAG2)
s = power_mod(m, e, n)

print("n = {}".format(n))
print("e = {}".format(e))
print("s = {}".format(s))
print("d = {}".format(d))

'''
n = 15460604532082022434447863191746096818395661654297811880153990430863210612174052905555714015509847983227922731985805451566885438246073982317155764958607807463544152653155702577302575656182513381836991406523433266793119819185584376348037239549027416676171243322427349503055393544314474433946388808819598676724602650885133527239213413115146892925897991299204757484271877122801914656196861364799755269353045413845589939222288386263094455792083439269571935284462746834265445496565656118946138440230994554776548484087051061415867095941661099297732697948916320877191187214389659572458105131795310932003795716041528518251941
e = 13940114669559785089994553152874911462940185353147358440009590357834922865336404876719637090024264992962184861192638247597372209967459869749194244465260953044000183317893672096208967428126445377096537005168617988464052526406368772412537919110909060208138238030652281948324581646558211129104247037132298412417172744788757010196622920732697739095428731091596465587412712381491216899946004892922552544731485012511684144239855310953043849248672859510381535454364398697606848031134430896051118472429827695939338707989876780783248817638991659244222120749409089321952224619559064398092617057670283889416528439717138717995857
s = 14436062168996812757448978634831237229195135681077168433473497830888912794696005628949569566794349552002820680818345145826875735180690372095069427004291147123823010127757927789077150634742490721462494058656713817380439365831415732859543831260752645041568489636069163348097951597380179104599459542104274137394129695774232058230330143354788514163385430667854735092964129335328317784514975463904093605317949683146759250761012903992658965223491078918554276878242413994075346941061182583256569289854517558518297889654324509358209488417569632054635659293200983687292855929334851057163469447744217570357813831833471135699358
d = 21350669355110305992341560079027226419143640868010921167513050762215638726238423136488099036393086297496778272900027817220956144964297086100210835932132994
'''

出题人老坏了，用了个d=p+q来迷惑我们，让我们觉得这玩意一定有用，实则一点用都没有

真正的d=p*q

$e*n\equiv e*p*q*r\equiv e*d*r\equiv r\pmod {\phi(n)}$
$2^{e*n}\equiv 2^{r}\pmod n\equiv 2\pmod r$
$2^{e*n}-2\equiv 0\pmod r$
$r=gcd(2^{e*n}-2,n)$

至于为什么有这样的想法，请见⛏️ 铜匠的艺术Ⅰd=p

from Crypto.Util.number import *

n = 15460604532082022434447863191746096818395661654297811880153990430863210612174052905555714015509847983227922731985805451566885438246073982317155764958607807463544152653155702577302575656182513381836991406523433266793119819185584376348037239549027416676171243322427349503055393544314474433946388808819598676724602650885133527239213413115146892925897991299204757484271877122801914656196861364799755269353045413845589939222288386263094455792083439269571935284462746834265445496565656118946138440230994554776548484087051061415867095941661099297732697948916320877191187214389659572458105131795310932003795716041528518251941
e = 13940114669559785089994553152874911462940185353147358440009590357834922865336404876719637090024264992962184861192638247597372209967459869749194244465260953044000183317893672096208967428126445377096537005168617988464052526406368772412537919110909060208138238030652281948324581646558211129104247037132298412417172744788757010196622920732697739095428731091596465587412712381491216899946004892922552544731485012511684144239855310953043849248672859510381535454364398697606848031134430896051118472429827695939338707989876780783248817638991659244222120749409089321952224619559064398092617057670283889416528439717138717995857
s = 14436062168996812757448978634831237229195135681077168433473497830888912794696005628949569566794349552002820680818345145826875735180690372095069427004291147123823010127757927789077150634742490721462494058656713817380439365831415732859543831260752645041568489636069163348097951597380179104599459542104274137394129695774232058230330143354788514163385430667854735092964129335328317784514975463904093605317949683146759250761012903992658965223491078918554276878242413994075346941061182583256569289854517558518297889654324509358209488417569632054635659293200983687292855929334851057163469447744217570357813831833471135699358
d = 21350669355110305992341560079027226419143640868010921167513050762215638726238423136488099036393086297496778272900027817220956144964297086100210835932132994
r = GCD(pow(2, e*n, n) - 2, n)
pq = n // r
print(long_to_bytes(pow(s, pq, n)).decode())
# cnss{Numb3r_the0ry_is_very_1mp0rtan7}

🗡️浪客剑心

from secret import FLAG5
from Crypto.Util.number import *
from sage.all import*

flag = bytes_to_long(FLAG5)

def get_key():
    p = getPrime(350)
    q = getPrime(350)
    n = p * q
    e = 65537
    c = power_mod(flag, e, n)
    return c, e, n, p, q

c, e, n, p, q = get_key()

def encrypt(cc):
    r = getPrime(1024)
    b = getPrime(1024)
    c = getPrime(400)
    a = (b * cc + c) % (r + 114514)
    return a, b, r

a, b, r = encrypt(p)

print(f'n = {n}')
print(f'a = {a}')
print(f'b = {b}')
print(f'r = {r}')
print(f'c = {c}')

'''
n = 2314232752348000703811317912334402763615478308933971928710910633640091497393933452660470400460670669229825820726684917641957868679591574569744319470988346467820849084043572349113116939127726604435635412508804749
a = 162692322323586802074386952755522700717697316490871403094518723606942744838127063892213054703396812980166290765292703817217786974098504727770137328613222422574338067616547577184493251751000945269866089804886945110012659954353764032840846077267561151860254358914153128169553167447927935668393279891549921838912
b = 174674697360208988817251037685496800037103378707423965562910954552671346989439923191189782561262195557901654530734008377543626433846127293265586040655464010300131022932041823292905983528587644255884548112625689263464131538814939442396914807219207412202291863568005684641978513851601172987052988719164013107171
r = 178534190472770502696125197412294935081706601609513013480795382874074454502094081633534639367840273482000377953076377575521697726959431607766078248234666603928672996483452614347182842727817578761136718036543157023105731109960369588108444158349734477741554268025459673362430762378211703130821195121993016030039
c = 2205748594770191270343865509517182739761150493011420819438179859733956601324122825198415775517884973774371846803243450746740088519056921297474783600678957159078914824495945802451555553013561689047402517932148973
'''

a = (b * cc + c) % (r + 114514)

$其实是，a\equiv b*p+c\pmod{(r+114514)}$

这里就两个未知的变量pc
正好，p是350位，c是400位，还等什么呢，二元copper端上来，直接秒了

cuso应该也能直接出

# sage
from sage.all import *
from Crypto.Util.number import *
import itertools

def small_roots(f, bounds, m=1, d=None):
    if not d:
        d = f.degree()

    R = f.base_ring()
    N = R.cardinality()

    f /= f.coefficients().pop(0)
    f = f.change_ring(ZZ)

    G = Sequence([], f.parent())
    for i in range(m + 1):
        base = N ^ (m - i) * f ^ i
        for shifts in itertools.product(range(d), repeat=f.nvariables()):
            g = base * prod(map(power, f.variables(), shifts))
            G.append(g)

    B, monomials = G.coefficient_matrix()
    monomials = vector(monomials)

    factors = [monomial(*bounds) for monomial in monomials]
    for i, factor in enumerate(factors):
        B.rescale_col(i, factor)

    B = B.dense_matrix().LLL()

    B = B.change_ring(QQ)
    for i, factor in enumerate(factors):
        B.rescale_col(i, 1 / factor)

    H = Sequence([], f.parent().change_ring(QQ))
    for h in filter(None, B * monomials):
        H.append(h)
        I = H.ideal()
        if I.dimension() == -1:
            H.pop()
        elif I.dimension() == 0:
            roots = []
            for root in I.variety(ring=ZZ):
                root = tuple(R(root[var]) for var in f.variables())
                roots.append(root)
            return roots

    return []

n = 2314232752348000703811317912334402763615478308933971928710910633640091497393933452660470400460670669229825820726684917641957868679591574569744319470988346467820849084043572349113116939127726604435635412508804749
a = 162692322323586802074386952755522700717697316490871403094518723606942744838127063892213054703396812980166290765292703817217786974098504727770137328613222422574338067616547577184493251751000945269866089804886945110012659954353764032840846077267561151860254358914153128169553167447927935668393279891549921838912
b = 174674697360208988817251037685496800037103378707423965562910954552671346989439923191189782561262195557901654530734008377543626433846127293265586040655464010300131022932041823292905983528587644255884548112625689263464131538814939442396914807219207412202291863568005684641978513851601172987052988719164013107171
r = 178534190472770502696125197412294935081706601609513013480795382874074454502094081633534639367840273482000377953076377575521697726959431607766078248234666603928672996483452614347182842727817578761136718036543157023105731109960369588108444158349734477741554268025459673362430762378211703130821195121993016030039
c = 2205748594770191270343865509517182739761150493011420819438179859733956601324122825198415775517884973774371846803243450746740088519056921297474783600678957159078914824495945802451555553013561689047402517932148973
e = 65537
PR.<x,y>=PolynomialRing(Zmod(r + 114514))
f = b*x + y - a
res = small_roots(f, (2^350,2^400), m=2, d=3)
p = int(res[0][0])
q = n // p
d = inverse(e, (p-1)*(q-1))
flag = long_to_bytes(int(pow(c, d, n))).decode()
print(flag)
# cnss{1at7icEs_1s_7he_f0undAti0n_0f_quan7um_CryPtogrAphy}

$既然flag提到了格，就再写一个格的做法吧，正常的格好像规约不出来？$

$a\equiv b*p+c\pmod{(r+114514)}，转化为CVP，最近向量问题$
$可以利用Babai最近平面算法，求解CVP$

$令m=r+114514，有c'=a-b*p\pmod m$
$考虑所有满足y=-b\cdot x\pmod m的整数点(x,y)在二维平面上构成点集，称之为格L$

$目标解(p,c')满足c'=a-b*p\pmod m$
$满足这个方程的点集可以理解为，将整个格L进行平移(y+a)后得到的新点集$

$现在的几何问题被转换为，在这个新点集上找到离(0,0)最近的那个点(p,c')$

$具体一点就是，在原始的、未平移的格L中，找到一个格点v，使得它与目标向量t=(0,-a)的距离∥v−t∥最近$
$我们期望找到的这个最短的向量s=v−t，就等于(p,c′)$

$v_{1}=(1,-b\pmod m)，v_{2}=(0,m)$
$这两个基向量线性无关，可以构造出基矩阵M$

$$M \ = \left [ \begin{matrix} 1&-b\pmod m\\ 0&m\\ \end{matrix} \right ],t=(0,-a)$$

$为了得到一个更优的（向量更短、更接近正交）格基，令L=M.LLL()$
$令t=C\cdot L，用来求向量t在新基L下的坐标C$
$这一步是，Babai算法中进行坐标系转换的核心$
$则，C=t\cdot L^{-1}$
$对C_{i}四舍五入进行取整得到，Z_{i}=[C_{i}]$
$格点v=Z\cdot L$
$s=v-t=(p-0,(-b*p)-(-a))=(p,a-b*p)=(p,c')\pmod m$

from sage.all import *
from Crypto.Util.number import *

n = 2314232752348000703811317912334402763615478308933971928710910633640091497393933452660470400460670669229825820726684917641957868679591574569744319470988346467820849084043572349113116939127726604435635412508804749
a = 162692322323586802074386952755522700717697316490871403094518723606942744838127063892213054703396812980166290765292703817217786974098504727770137328613222422574338067616547577184493251751000945269866089804886945110012659954353764032840846077267561151860254358914153128169553167447927935668393279891549921838912
b = 174674697360208988817251037685496800037103378707423965562910954552671346989439923191189782561262195557901654530734008377543626433846127293265586040655464010300131022932041823292905983528587644255884548112625689263464131538814939442396914807219207412202291863568005684641978513851601172987052988719164013107171
r = 178534190472770502696125197412294935081706601609513013480795382874074454502094081633534639367840273482000377953076377575521697726959431607766078248234666603928672996483452614347182842727817578761136718036543157023105731109960369588108444158349734477741554268025459673362430762378211703130821195121993016030039
c = 2205748594770191270343865509517182739761150493011420819438179859733956601324122825198415775517884973774371846803243450746740088519056921297474783600678957159078914824495945802451555553013561689047402517932148973
e = 65537

m = r + 114514
M = Matrix(ZZ, [[1, -b % m], [0, m]])
L = M.LLL()
t = vector(ZZ, [0, -a])
C = t * L.inverse()
Z = vector([round(c) for c in C])
v = Z * L
s = v - t
p = s[0]
q = n // p
phi = (p - 1) * (q - 1)
d = inverse(e, phi)
flag = long_to_bytes(int(pow(c, d, n))).decode()
print(flag)

🧢棒球英豪

from Crypto.Util.number import *
from secret import flag6, Curve

c, d, p = Curve

def verify(P):
    u, v = P
    return (u**2 + v**2 - c**2 * (1 + d * u**2*v**2)) % p == 0

def add(P, Q):
    u1, v1 = P
    u2, v2 = Q
    u3 = (u1 * v2 + v1 * u2) * inverse(c * (1 + d * u1 * u2 * v1 * v2), p) % p
    v3 = (v1 * v2 - u1 * u2) * inverse(c * (1 - d * u1 * u2 * v1 * v2), p) % p
    return (int(u3), int(v3))

def mul(m, P):
    x, y = P
    PP = (-x, y)
    O = add( P, PP)
    if m == 0:
        return O
    elif m == 1:
        return P
    Q = O
    B = bin(m)[2:]
    l = len(B)
    for i in range(l):
        Q = add(Q, Q)
        if B[i] == '1':
            Q = add(Q, P)

    return Q

flag = flag6.lstrip(b'cnss{').rstrip(b'}')
l = len(flag)
lef, rig = flag[:l // 2], flag[l // 2:]
s, t = bytes_to_long(lef), bytes_to_long(rig)
assert s < p and t < p

P = (398011447251267732058427934569710020713094, 548950454294712661054528329798266699762662)
Q = (139255151342889674616838168412769112246165, 649791718379009629228240558980851356197207)

with open("output6.txt", "w") as f:
    f.write(f'P = {P}\n')
    f.write(f'Q = {Q}\n')
    f.write(f'verify(P) = {verify(P)}\n')
    f.write(f'verify(Q) = {verify(Q)}\n')
    f.write(f's * P = {mul(s, P)}\n')
    f.write(f't * Q = {mul(t, Q)}\n')

"""
P = (398011447251267732058427934569710020713094, 548950454294712661054528329798266699762662)
Q = (139255151342889674616838168412769112246165, 649791718379009629228240558980851356197207)
verify(P) = True
verify(Q) = True
s * P = (298889479660508029507606377651920486175404, 410507058136886341368140950580892999564994)
t * Q = (443179850165927025618537423492534098031604, 364123198944392695945329998024386893104420)
"""

$u^2+v^2=c^2(1+d*u^2*v^2)\pmod p$
$两边同时除以c^2，u=c*x，整理得到$
$x^2+y^2=1+(dc^4)*x^2*y^2\pmod p$
$x^2+y^2=1+d'x^2y^2\pmod p$
$通过缩放可以转换得到，标准的扭曲爱德华兹曲线$
$这里的加法属于扭曲爱德华兹曲线上的加法，与普通的曲线加法相比多乘了一个c$
$P\ Q\ s*P\ t*Q都是曲线上的点，通过这四个点恢复(p\ c\ d)$

具体推导原理参考博客(里面已经很详细了)：
https://www.cnblogs.com/mumuhhh/p/18019200
https://tangcuxiaojikuai.xyz/post/678d5ec.html

$这里求出来的p需要除2才能是素数$

from Crypto.Util.number import *
from math import gcd

def happy(C, P):
    """
    Verification points are on the curve
    """
    c, d, p = C
    u, v = P
    return (u**2 + v**2 - cc * (1 + d * u**2*v**2)) % p == 0

def a_and_b(u1,u2,v1,v2):
    """
    Helper function used to simplify calculations
    """
    a12 = u1**2 - u2**2 + v1**2 - v2**2
    b12 = u1**2 * v1**2 - u2**2 * v2**2
    return a12, b12

def find_modulus(u1,u2,u3,u4,v1,v2,v3,v4):
    """
    Compute the modulus from four points
    """
    a12, b12 = a_and_b(u1,u2,v1,v2)
    a13, b13 = a_and_b(u1,u3,v1,v3)
    a23, b23 = a_and_b(u2,u3,v2,v3)
    a24, b24 = a_and_b(u2,u4,v2,v4)

    p_almost = gcd(a12*b13 - a13*b12, a23*b24 - a24*b23)

    for i in range(2,1000):
        if p_almost % i == 0:
            p_almost = p_almost // i

    return p_almost

def c_sq_d(u1,u2,v1,v2,p):
    """
    Helper function to computer c^2 d
    """
    a1,b1 = a_and_b(u1,u2,v1,v2)
    return a1 * pow(b1,-1,p) % p

def c(u1,u2,v1,v2,p):
    """
    Compute c^2, d from two points and known modulus
    """
    ccd = c_sq_d(u1,u2,v1,v2,p)
    cc = (u1**2 + v1**2 - ccd*u1**2*v1**2) % p
    d = ccd * pow(cc, -1, p) % p
    return cc, d


P = (398011447251267732058427934569710020713094, 548950454294712661054528329798266699762662)
Q = (139255151342889674616838168412769112246165, 649791718379009629228240558980851356197207)
sP = (298889479660508029507606377651920486175404, 410507058136886341368140950580892999564994)
tQ = (443179850165927025618537423492534098031604, 364123198944392695945329998024386893104420)

u1, v1 = P
u2, v2 = Q
u3, v3 = sP
u4, v4 = tQ

p = find_modulus(u1,u2,u3,u4,v1,v2,v3,v4) // 2
cc, d = c(u1,u2,v1,v2,p)

C = cc, d, p

assert happy(C, P)
assert happy(C, Q)
assert happy(C, sP)
assert happy(C, tQ)

print(f'Found curve parameters')
print(f'p = {p}')
print(f'c^2 = {cc}')
print(f'd = {d}')

F = GF(p)
c = F(cc).sqrt()

x1, y1 = P
x2, y2 = Q
x3, y3 = sP
x4, y4 = tQ

R.<x,y> = PolynomialRing(F)
g = (x^2 + y^2 - cc * (1 + d * x^2*y^2))

# Check the mapping worked!
assert g(x=x1, y=y1) == 0
assert g(x=x2, y=y2) == 0
assert g(x=x3, y=y3) == 0
assert g(x=x4, y=y4) == 0

# Scale: x,y,d to remove c:
# x^2 + y^2 = c^2 * (1 + d * x^2*y^2)
# to:
# x^2 + y^2 = (1 + d * x^2*y^2)

d = F(d) * F(cc)^2
x1, y1 = F(x1) / F(c),  F(y1) / F(c)
x2, y2 = F(x2) / F(c),  F(y2) / F(c)
x3, y3 = F(x3) / F(c),  F(y3) / F(c)
x4, y4 = F(x4) / F(c),  F(y4) / F(c)

h = (x^2 + y^2 - (1 + d * x^2*y^2))

# Check the mapping worked!
assert h(x=x1, y=y1) == 0
assert h(x=x2, y=y2) == 0
assert h(x=x3, y=y3) == 0
assert h(x=x4, y=y4) == 0

# Convert from Edwards to Mont. 
# https://safecurves.cr.yp.to/equation.html
def ed_to_mont(x,y):
    u = F(1 + y) / F(1 - y)
    v = 2*F(1 + y) / F(x*(1 - y))
    return u,v

u1, v1 = ed_to_mont(x1, y1)
u2, v2 = ed_to_mont(x2, y2)
u3, v3 = ed_to_mont(x3, y3)
u4, v4 = ed_to_mont(x4, y4)

e_curve = 1 - F(d)
A = (4/e_curve - 2)
B = (1/e_curve)

# Mont. curve: Bv^2 = u^3 + Au^2 + u
R.<u,v> = PolynomialRing(ZZ)
f = B*v^2 - u^3 - A* u^2 - u

# Check the mapping worked!
assert f(u=u1, v=v1) == 0
assert f(u=u2, v=v2) == 0
assert f(u=u3, v=v3) == 0
assert f(u=u4, v=v4) == 0

# Convert from Mont. to Weierstrass
# https://en.wikipedia.org/wiki/Montgomery_curve
a = F(3 - A^2) / F(3*B^2)
b = (2*A^3 - 9*A) / F(27*B^3)
E = EllipticCurve(F, [a,b])

# https://en.wikipedia.org/wiki/Montgomery_curve
def mont_to_wei(u,v):
    t = (F(u) / F(B)) + (F(A) / F(3*B))
    s = (F(v) / F(B))
    return t,s

X1, Y1 = mont_to_wei(u1, v1)
X2, Y2 = mont_to_wei(u2, v2)
X3, Y3 = mont_to_wei(u3, v3)
X4, Y4 = mont_to_wei(u4, v4)

P = E(X1, Y1)
Q = E(X2, Y2)
sP = E(X3, Y3)
tQ = E(X4, Y4)

# Finally we can solve the dlog
s = sP.log(P)
t = tQ.log(Q)

# We have to do this, as we picked the wrong square-root.
flag1 = long_to_bytes(s % Q.order()).decode()
flag2 = long_to_bytes(t).decode()
print("cnss{" + flag1 + flag2 + "}")
# cnss{CurVes_haS_many_u8u5ua1_F0rms}

🌍Rewrite*

from collections import namedtuple
from Crypto.Util.number import *
from secret import flag

inf = -1
Point = namedtuple('Point', ['x', 'y'])
Pubkey = namedtuple('Pubkey', ['n', 'e', 'r'])
Privkey = namedtuple('Privkey', ['p', 'q', 'd'])

class Curve:
    def genkey(self, nbits, dbits):
        while True:
            p = getPrime(nbits // 2)
            if(p % 3 == 1):
                break
        while True:
            q = getPrime(nbits // 2)
            if(q % 3 == 1):
                break
        n = p * q
        while True:
            r = getRandomRange(1,n)
            if((pow(r, (p-1)//3, p) != 1) and (pow(r, (q-1)//3, q) != 1)):
                break
        d = getPrime(dbits)
        e = inverse(d, (p * p + p + 1) * (q * q + q + 1))
        return Pubkey(n, e, r), Privkey(p, q, d)
    
    def __init__(self, nbits, dbits):
        self.Pubkey, self.Privkey = self.genkey(nbits, dbits)
    
    def product(self, a, b):
        n, _, r = self.Pubkey
        if(a == Point(inf, inf)):
            return b
        if(b == Point(inf, inf)):
            return a
        if(a.y == inf):
            a, b = b, a
        u, v = a
        p, q = b
        if(q == inf):
            if(v == inf):
                return Point((u * p) % n, (u + p) % n)
            elif((v + p) % n):
                iv = inverse(v + p, n)
                return Point((u * p + r) * iv % n, (u + v * p) * iv % n)
            elif((u - v * v) % n):
                iv = inverse(u - v * v, n) 
                return Point((u * p + r) * iv % n, inf)
            else:
                return Point(inf, inf)
        else:
            if((u + p + v * q) % n):
                iv = inverse(u + p + v * q, n)
                return Point((u * p + (v + q) * r) * iv % n, (v * p + u * q + r) * iv % n)
            elif((v * p + u * q + r) % n):
                iv = inverse(v * p + u * q + r, n)
                return Point((u * p + (v + q) * r) * iv % n, inf)
            else:
                return Point(inf, inf)

    def encrypt(self, a):
        k = self.Pubkey.e
        res = Point(inf, inf)
        while k:
            if(k & 1):
                res = self.product(res, a)
            a = self.product(a, a)
            k >>= 1
        return res
    
    def decrypt(self, a):
        k = self.Privkey.d
        res = Point(inf, inf)
        while k:
            if(k & 1):
                res = self.product(res, a)
            a = self.product(a, a)
            k >>= 1
        return res

SYS = Curve(512, 256)
msg = Point(bytes_to_long(flag[:len(flag)//2]),bytes_to_long(flag[len(flag)//2:]))
enc = SYS.encrypt(msg)

print(f"pubkey = {SYS.Pubkey}")
print(f"enc = {enc}")

'''
pubkey = Pubkey(n=4873189510606632670051462507037860421077551672164701436608907002436560192840356016750494285565924106988544952397402675547921930867836902302893011890256779, e=13378485234962864327763969254924381829836619219064695812825856516258702951436596931331119028308233868359134774242758549790397497067433124687542530097719178781601238604579006713726763589993220493028013459103929256891706082648574000763659034977028816094438365563682368664776491208827662655323646975736791610283, r=12276290027089634179666721556762461660058574159904682072699747683370547320796053531346228587347389593630764829928291692127976550810879034430985232250912)
enc = Point(x=2091733356436558288163136748650604712672684547651742349852169921359344595959145998331036292720052611932763413100160720842985758067666744134352011068441384, y=3606887286200111465466487525784448417643735862168228528263397534620187006806130329379762200338558634931139253300267143260393005244954232632353514520202318)
'''

$不是哥们，怎么还是这题啊$
$\phi(n)=(p^2+p+1)*(q^2+q+1)$
$r是用来构造三次扩域的，貌似不需要使用到(?)$
$令x=p+q$
$e*d=k*(n^2+x*(x+n+1)-n+1)+1$
$k\in [2^{250},2^{256}],x\in [2^{256},2^{257}]$
$说实话，二元copper也打了，cuso也试过了，真解不出来啊。。。$
这下未完待续了……

下面开始垂死挣扎：

• pbCTF2021-yet another rsa
• maple3142’s wp
• PBCTF 2nd place wp
• paper1-2021
• paper2-2022
• paper3
• paper4
• paper5
• A novel RSA–like cryptosystem based on a product related to the cubic Pell equation and Rédei rational functions

已经很尽力调参了，奈何就是打不出来(尝试了二元copper、连分数分解、论文脚本)，$d=N^{0.5}$，也能满足论文的条件($d<N^{0.569}$)啊，0.4的时候就特别好打。。。。

其实通过搜索Murru-Saettone scheme cubic pell rsa，你会发现大量相关的论文，就不全部罗列出来了

• paper1-2024
• paper1’s attack.py
• paper2-2024
• 还找到了新体系攻击 paper3-2025 phi=(p-1)^n * (q-1)^n
• check

也尝试通过24年的研究优化了22年脚本的一些参数，没出
上面的脚本，也仔细调参数了，也没能出……
What can I say……