春秋杯 Crypto wp

前两题就不讲了，那种没啥意思

RSA1

加密代码：

from Crypto.Util.number import *
import uuid


p, q = [getPrime(512) for _ in range(2)]
N = p * q

flag = b'flag{' + str(uuid.uuid4()).encode() + b'}'  #335比特
flag += bin(getPrime((1024 - bytes_to_long(flag).bit_length()) // 8)).encode()  #86比特素数

m1 = bytes_to_long(flag)
m2 = bytes_to_long(''.join(chr((ord(i) + 3) % 128) for i in flag.decode()).encode())

e = getPrime(128)
c1 = pow(m1 * e, 2835, N)
c2 = pow(m2, 2025, N)
c3 = pow(m2, 2835, N) + e

print(f'{N = }')
print(f'{c1 = }')
print(f'{c2 = }')
print(f'{c3 = }')

'''
N = 176871561120476589165761750300633332586877708342448994506175624203633860119621512318321172927876389631918300184221082317741380365447197777026256405312212716630617721606918066048995683899616059388173629437673018386590043053146712870572300799479269947118251011967950970286626852935438101046112260915112568392601
c1 = 47280375006817082521114885578132104427687384457963920263778661542552259860890075321953563867658233347930121507835612417278438979006705016537596357679038471176957659834155694284364682759675841808209812316094965393550509913984888849945421092463842546631228640293794745005338773574343676100121000764021207044019
c2 = 176231410933979134585886078013933649498379873444851943224935010972452769899603364686158279269197891190643725008151812150428808550310587709008683339436590112802756767140102136304346001599401670291938369014436170693864034099138767167055456635760196888578642643971920733784690410395944410255241615897032471127315
c3 = 135594807884016971356816423169128168727346102408490289623885211179619571354105102393658249292333179346497415129785184654008299725617668655640857318063992703265407162085178885733134590524577996093366819328960462500124201402816244104477018279673183368074374836717994805448310223434099196774685324616523478136309
'''

一眼就是相关消息攻击类型的

思路肯定就是要把m2化为包含m1的等式

m1对应的字节串本地测试大概长这样

1	b'flag{d3394c7d-6bad-4a6e-8936-2aff5b88842b}0b11100100110000011111111011110011011001010000010111110110100001110111000101000011110011'

m2对应的字节串本地测试大概长这样

1	b'iodj~g66<7f:g09edg07d9h0;<6905dii8e;;;75e\x003e44433433443333344444444344443344344334343333343444443443433334443444333434333344443344'

其中的\x00是因为}的ascii的125，加3模128之后变成0，所以这个我们等一下要做一下调整

我们假设m1从右到左的每个字节分别对应 $t_0$ 到 $t_{129}$ ，那么由此m1对应的值可以表示为

m_1 = t_0 + 256 * t_1 + 256 ^2 * t_2 + \dots + 256 ^ {129} * t_{129}

同理可得 $m_2$ 可以表示为

\begin{array}{l} m_2 = (t_0 + 3) + 256 * (t_1 + 3) + 256 ^2 * (t_2+3) + \dots + 256 ^ {88} * 0 + \dots + 256 ^ {129} * (t_{129} + 3)\\ m_2 = t_0 + 256 * t_1 + 256 ^2 * t_2 + \dots + 256 ^ {88} * 0 + \dots + 256 ^ {129} * t_{129} + H=m_1 + H \end{array}

这边的H很明显可以表示为

H = 3 + 3 * 256 + 3* 256 ^ 2 + \dots + 0 * 256 ^ {88} + 3 * 256 ^ {89} + \dots + 3 * 256 ^ {129}

由此我们便得到了 $m_2$ 的表达式

接下来给出的三个式子

\begin{array}{l} (m_1 * e) ^ {2835} \equiv c_1 \ (mod\ N)\\ m_2 ^ {2025} \equiv c_2\ (mod\ N)\\ m_2 ^ {2835} \equiv c_3 - e\ (mod\ N) \end{array}

代入 $m_2$ ，可得

\begin{array}{l} (m_1 * e) ^ {2835} \equiv c_1 \ (mod\ N)\\ (m_1 + H) ^ {2025} \equiv c_2\ (mod\ N)\\ (m_1 + H) ^ {2835} \equiv c_3 - e\ (mod\ N) \end{array}

拿出第三个式子和第一个式子联立即可

\begin{array}{l} c_3 - (m_1 + H) ^ {2835} \equiv e\ (mod\ N)\\ [c_3 - (m_1 + H) ^ {2835}] * m_1 \equiv e * m_1 \ (mod\ N)\\ [c_3 - (m_1 + H) ^ {2835}] ^ {2835} * m_1 ^ {2835} \equiv c_1 \ (mod\ N)\\ \end{array}

明显这是一个关于 $m_1$ 的等式，然后还有关于 $c_2$ 的一个等式，直接拿去多项式gcd即可

from Crypto.Util.number import *


N = 176871561120476589165761750300633332586877708342448994506175624203633860119621512318321172927876389631918300184221082317741380365447197777026256405312212716630617721606918066048995683899616059388173629437673018386590043053146712870572300799479269947118251011967950970286626852935438101046112260915112568392601
c1 = 47280375006817082521114885578132104427687384457963920263778661542552259860890075321953563867658233347930121507835612417278438979006705016537596357679038471176957659834155694284364682759675841808209812316094965393550509913984888849945421092463842546631228640293794745005338773574343676100121000764021207044019
c2 = 176231410933979134585886078013933649498379873444851943224935010972452769899603364686158279269197891190643725008151812150428808550310587709008683339436590112802756767140102136304346001599401670291938369014436170693864034099138767167055456635760196888578642643971920733784690410395944410255241615897032471127315
c3 = 135594807884016971356816423169128168727346102408490289623885211179619571354105102393658249292333179346497415129785184654008299725617668655640857318063992703265407162085178885733134590524577996093366819328960462500124201402816244104477018279673183368074374836717994805448310223434099196774685324616523478136309


H = 0
for i in range(130):
    tmp = (3 * 256 ^ i) % N
    H += tmp
    H %= N

H -= 128 * 256 ^ 88
H %= N


# print(H)

R.<m1> = Zmod(N)[]
f = (-(m1 + H) ^ 2835 + c3) ^ 2835 * m1 ^ 2835 - c1
g = (m1 + H) ^ 2025 - c2


# 普通gcd
pgcd = lambda g1, g2: g1.monic() if not g2 else pgcd(g2, g1%g2)

pgcd(f, g)
'''
m1 + 7304679824196052935200621143481710020373664415769837839104228433810294890580066953657519799147612912231653945577918347395235631706626884488487300438736077864114863340211194990281871924694412262014210980442205672371597853267122364179017416512675501444788534749375314424907193049548474750058790401660945572953
'''

要跑个几分钟，毕竟等式还是比较复杂的

另外注意这时候的flag的数量级是比N大的，但是大的不是很多，这边得到 $m_1$ % N之后简答爆破一下即可

from Crypto.Util.number import *
from tqdm import trange

N = 176871561120476589165761750300633332586877708342448994506175624203633860119621512318321172927876389631918300184221082317741380365447197777026256405312212716630617721606918066048995683899616059388173629437673018386590043053146712870572300799479269947118251011967950970286626852935438101046112260915112568392601
c1 = 47280375006817082521114885578132104427687384457963920263778661542552259860890075321953563867658233347930121507835612417278438979006705016537596357679038471176957659834155694284364682759675841808209812316094965393550509913984888849945421092463842546631228640293794745005338773574343676100121000764021207044019
c2 = 176231410933979134585886078013933649498379873444851943224935010972452769899603364686158279269197891190643725008151812150428808550310587709008683339436590112802756767140102136304346001599401670291938369014436170693864034099138767167055456635760196888578642643971920733784690410395944410255241615897032471127315
c3 = 135594807884016971356816423169128168727346102408490289623885211179619571354105102393658249292333179346497415129785184654008299725617668655640857318063992703265407162085178885733134590524577996093366819328960462500124201402816244104477018279673183368074374836717994805448310223434099196774685324616523478136309

m1 = -7304679824196052935200621143481710020373664415769837839104228433810294890580066953657519799147612912231653945577918347395235631706626884488487300438736077864114863340211194990281871924694412262014210980442205672371597853267122364179017416512675501444788534749375314424907193049548474750058790401660945572953
m1 %= N

for k in trange(2 ** 22):
    tmp = m1 + k * N
    flag = long_to_bytes(tmp)
    if flag.isascii():
        print(flag)
        break
        

'''
  0%|                                                                                                                                        | 0/4194304 [00:00<?, ?it/s]b'flag{2404dcef-4223-417d-aee0-c236241f2320}0b10110001011010011001000000011011110111111100010110000111000000100100000100011101100011'
  1%|▊   
'''

EzRSA

加密代码：

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


p = getPrime(512)
q = getPrime(512)
N = p * q
e = getPrime(1023)
assert e < N
c = pow(bytes_to_long(flag), e, N)

print(f'{N = }')
print(f'{e = }')
print(f'{c = }')

phi = (p - 1) * (q - 1)
d = inverse(e, phi)
k = (e * d - 1) // phi

dh = d >> 234
dl = d % pow(2, 24)
kh = k >> 999

hash224 = bytes_to_long(hashlib.sha224(long_to_bytes(dl)).digest())
hash512 = bytes_to_long(hashlib.sha512(long_to_bytes(kh)).digest())
leak = hash224 ^ hash512 ^ (k % pow(2, 512))

print(f'{dh = }')
print(f'{leak = }')

'''
N = 136118062754183389745310564810647775266982676548047737735816992637554134173584848603639466464742356367710495866667096829923708012429655117288119142397966759435369796296519879851106832954992705045187415658986211525671137762731976849094686834222367125196467449367851805003704233320272315754132109804930069754909
e = 84535510470616870286532166161640751551050308780129888352717168230068335698416787047431513418926383858925725335047735841034775106751946839596675772454042961048327194226031173378872580065568452305222770543163564100989527239870852223343451888139802496983605150231009547594049003160603704776585654802288319835839
c = 33745401996968966125635182001303085430914839302716417610841429593849273978442350942630172006035442091942958947937532529202276212995044284510510725187795271653040111323072540459883317296470560328421002809817807686065821857470217309420073434521024668676234556811305412689715656908592843647993803972375716032906
dh = 4640688526301435859021440727129799022671839221457908177477494774081091121794107526784960489513468813917071906410636566370999080603260865728323300663211132743906763686754869052054190200779414682351769446970834390388398743976589588812203933
leak = 12097621642342138576471965047192766550499613568690540866008318074007729495429051811080620384167050353010748708981244471992693663360941733033307618896919023
'''

这题其实要用到一个小技巧，我们知道有如下等式

e * d = 1 + k * phi

那么近似来说，也有

e * d \approx k *N

所以可以得到kh为

k_h = \frac{e * d_h}{N}

稍微调整一下，也就是

1	kh = (e * (dh << 234) // N) >> 999

知道了 $k_h$ ，那么根据leak，小爆一下 $d_l$ ，也可以得到k % pow(2, 512)，也就是 $k_l$

这边本地测试的话，确实可以得到 $k_h$ ，不需要进行二次调整

那么现在就是 $k_h$ 、 $k_l$ ， $d_h$ ， $d_l$ 的值都知道了，很明显要构造等式来打多元copper

很简单，我们可以构造出如下的等式

1 + (k_l + 2 ^ {999} * k_h + 2 ^ {512} * k_m) * (N - s + 1) = e * (2 ^ {234} * d_h + d_l + 2 ^ {24} * d_m)

这边的s表示p+q的值，数量级有513比特

$k_m$ 也有487比特

$d_m$ 有210比特

观察一下，s这边其实还可以降数量级的，我们在模 $2^{24}$ 下来运算，可以消掉 $d_m$ 和 $k_m$ （有些已知的可以消掉，但是我们关心的是未知的，已知的让sage自己算就好了），有

1 + (k_l + 2 ^ {999} * k_h) * (N - s_l + 1) \equiv e * (2 ^ {234} * d_h + d_l)\ (mod\ 2 ^ {24})

那么就有

s_l \equiv -((e * (2 ^ {234} * d_h + d_l) - 1) * (k_l + 2 ^ {999} * k_h) ^ {-1} - 1 - N) \ (mod\ 2 ^ {24})

这边因 $d_l$ 是需要爆破的，所以我们自己动手算一下，要不然肯定roots直接解了（不是素数域下算的很慢，还不如自己算）

得到 $s_l$ 之后，带进去，等式可以变为

1 + (k_l + 2 ^ {999} * k_h + 2 ^ {512} * k_m) * (N - s_l - 2 ^ {24} * s_h + 1) = e * (2 ^ {234} * d_h + d_l + 2 ^ {24} * d_m)

$k_m$ 有487比特

$d_m$ 有210比特

$s_h$ 有488比特

似乎不能再降了，直接在模N * e下打三元copper，本地测试发现是可以打的出来的，就是慢，要开的多线程

from multiprocessing import Pool
from Crypto.Util.number import *
from tqdm import trange
import itertools
import hashlib
import sys

def small_roots(f, bounds, m=1, d=None):#多元copper
    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 []





def attack(range_):
    N = 136118062754183389745310564810647775266982676548047737735816992637554134173584848603639466464742356367710495866667096829923708012429655117288119142397966759435369796296519879851106832954992705045187415658986211525671137762731976849094686834222367125196467449367851805003704233320272315754132109804930069754909
    e = 84535510470616870286532166161640751551050308780129888352717168230068335698416787047431513418926383858925725335047735841034775106751946839596675772454042961048327194226031173378872580065568452305222770543163564100989527239870852223343451888139802496983605150231009547594049003160603704776585654802288319835839
    c = 33745401996968966125635182001303085430914839302716417610841429593849273978442350942630172006035442091942958947937532529202276212995044284510510725187795271653040111323072540459883317296470560328421002809817807686065821857470217309420073434521024668676234556811305412689715656908592843647993803972375716032906
    dh = 4640688526301435859021440727129799022671839221457908177477494774081091121794107526784960489513468813917071906410636566370999080603260865728323300663211132743906763686754869052054190200779414682351769446970834390388398743976589588812203933
    leak = 12097621642342138576471965047192766550499613568690540866008318074007729495429051811080620384167050353010748708981244471992693663360941733033307618896919023
    
    kh = (e * (dh << 234) // N) >> 999
    hash512 = bytes_to_long(hashlib.sha512(long_to_bytes(kh)).digest())

    low = range_[0]
    high = range_[1]
    for dl in trange(low, high):
        hash224 = bytes_to_long(hashlib.sha224(long_to_bytes(dl)).digest())
        kl = leak ^^ hash512 ^^ hash224
        if gcd(2 ^ 24, kl + 2 ^ 999 * kh) == 1:
            sl = -((e * (2 ^ 234 * dh + dl) - 1) * inverse(kl + 2 ^ 999 * kh, 2 ^ 24) - 1 - N) % 2 ^ 24
            R.<sh, km, dm> = Zmod(N * e)[]
            f = 1 + (kl + 2 ^ 999 * kh + 2 ^ 512 * km) * (N - sl - 2 ^ 24 * sh + 1) - e * (2 ^ 234 * dh + dl + 2 ^ 24 * dm)
            res = small_roots(f, bounds = (2 ^ 488, 2 ^ 487, 2 ^ 210), m = 3, d = 3)
            if res:
                DM = int(res[0][2])
                d = 2 ^ 234 * dh + dl + 2 ^ 24 * DM
                m = long_to_bytes(int(pow(c, d, N)))
                if m.isascii():
                    print(m)
                    return
                




if __name__ == "__main__":
    ranges = [(i, i + 524288) for i in range(0, 2 ^ 24, 524288)]
    with Pool(32) as pool:    #2 ^ 24 // 32 = 524288
        list(pool.imap(attack, ranges))

理论可行，这个解法，时间就不知道了，但是简答粗暴

其实这题k是可以求出来的，然后我们在模e下只有一个变量，可以直接打copper，可以快很多

上面因为太关注kh了，没好好检验(e * (dh << 234) // N)和真正的k的关系，本地检验一下大概有508比特是一样的（保险起见），然后我们还知道有k的低512位，k应该是1023比特左右，所以实际上只有3个比特位是未知的，也是可以直接爆破

1 + k * (N - s_l - 2 ^ {24} * s_h + 1) = 0\ (mod \ e)

哦，也不用打copper，都可以直接算了打什么copper σ(´∀｀*)

\begin{array}{l} 1 + k * (N - s + 1) = 0\ (mod \ e)\\ s \equiv (1 + N + k^{-1})\ (mod\ e) \end{array}

然后无非就是解方程，这边我们手算检验肯定更快

\begin{array}{l} p + q = s\\ p * q = N\\ p * (s-p)= N\\ p^2-s*p+N = 0\\ p = \frac{s\pm \sqrt{s^2 - 4 * N}}{2} \end{array}

验证 $\Delta$ 能不能开方就行了

exp：

from gmpy2 import iroot
from multiprocessing import Pool
from Crypto.Util.number import *
from tqdm import trange
import hashlib


def attack(range_):
    N = 136118062754183389745310564810647775266982676548047737735816992637554134173584848603639466464742356367710495866667096829923708012429655117288119142397966759435369796296519879851106832954992705045187415658986211525671137762731976849094686834222367125196467449367851805003704233320272315754132109804930069754909
    e = 84535510470616870286532166161640751551050308780129888352717168230068335698416787047431513418926383858925725335047735841034775106751946839596675772454042961048327194226031173378872580065568452305222770543163564100989527239870852223343451888139802496983605150231009547594049003160603704776585654802288319835839
    c = 33745401996968966125635182001303085430914839302716417610841429593849273978442350942630172006035442091942958947937532529202276212995044284510510725187795271653040111323072540459883317296470560328421002809817807686065821857470217309420073434521024668676234556811305412689715656908592843647993803972375716032906
    dh = 4640688526301435859021440727129799022671839221457908177477494774081091121794107526784960489513468813917071906410636566370999080603260865728323300663211132743906763686754869052054190200779414682351769446970834390388398743976589588812203933
    leak = 12097621642342138576471965047192766550499613568690540866008318074007729495429051811080620384167050353010748708981244471992693663360941733033307618896919023
    
    new_kh = int(bin(e * (dh << 234) // N)[2::][:508:], 2)

    kh = (e * (dh << 234) // N) >> 999
    hash512 = bytes_to_long(hashlib.sha512(long_to_bytes(kh)).digest())

    low = range_[0]
    high = range_[1]
    for dl in trange(low, high):
        p = 0 
        for km in range(2 ^ 3):
            hash224 = bytes_to_long(hashlib.sha224(long_to_bytes(dl)).digest())
            kl = leak ^^ hash512 ^^ hash224
            k = kl + 2 ^ 512 * km + 2 ^ (512 + int(km).bit_length()) * new_kh
            s = (inverse(k, e) + N + 1) % e
            Delta = iroot(s ^ 2 - 4 * N, 2)
            if Delta[1]:
                p1 = (s + Delta[0]) // 2
                p2 = (s - Delta[0]) // 2
                if N % p1 == 0:
                    p = p1
                elif N % p2 == 0:
                    p = p2
                q = N // p
                phi = (p - 1) * (q - 1)
                d = inverse(e, phi)
                m = long_to_bytes(int(pow(c, d, N)))
                if m.isascii():
                    print(m)
                    return
                    
    
    
    

if __name__ == "__main__":
    ranges = [(i, i + 524288) for i in range(0, 2 ^ 24, 524288)]
    with Pool(32) as pool:    #2 ^ 24 // 32 = 524288
        list(pool.imap(attack, ranges))

开32线程7分钟可出

signtime

加密代码：

from hashlib import sha1
from Crypto.Util.number import bytes_to_long
from ecdsa.ecdsa import Public_key, Private_key, Signature, generator_192
from datetime import datetime
from random import randrange

banner = """                                                
    //   / /     //   ) )     //    ) )     //   ) )     // | | 
   //____       //           //    / /     ((           //__| | 
  / ____       //           //    / /        \\         / ___  | 
 //           //           //    / /           ) )    //    | | 
//____/ /    ((____/ /    //____/ /     ((___ / /    //     | |  

Welcome to this CTF challenge!
you have THREE choices:
- sign_time to get a signature
- verify to verify the signature
- I kown the secret to get the flag
You only have TWO chances per connection. Best wish for you!
"""


generator = generator_192
order = generator.order()
hint_message = ''
flag_content = ''

private_key_value = randrange(1, order - 1)
public_key = Public_key(generator, generator * private_key_value)
private_key = Private_key(public_key, private_key_value)

def sign_current_time():
    current_time = datetime.now()
    current_month = int(current_time.strftime("%m"))  
    current_seconds = int(current_time.strftime("%S"))  
    formatted_time = f"{current_month}:{current_seconds}"
    message = f"The time is {formatted_time}"
    message_hash = sha1(message.encode()).digest()  
    signature = private_key.sign(bytes_to_long(message_hash), randrange(100, 100 + current_seconds))  
    return {"time": message, "r": hex(signature.r), "s": hex(signature.s)}

def verify_signature():
    user_message = input("Enter the message: ")
    user_r = input("Enter r in hexadecimal form: ")
    user_s = input("Enter s in hexadecimal form: ")
    message_hash = sha1(user_message.encode()).digest() 
    signature_r = int(user_r, 16)
    signature_s = int(user_s, 16)
    signature = Signature(signature_r, signature_s)  
    return public_key.verifies(bytes_to_long(message_hash), signature)

def start_challenge():
    print(banner)
    for _ in range(2):
        user_choice = input("Enter your option: ")
        if user_choice == 'sign_time':
            print(sign_current_time())
        elif user_choice == 'verify':
            if verify_signature():
                print(f"The hint is: {hint_message}")
                exit(0)
            else:
                print("Signature verification failed.")
        elif user_choice  == 'I kown the secret':
                if input("Enter the secret: ") == hex(private_key_value):
                    print(f"The flag is: {flag_content}")
                    exit(0)
        else:
            print("Invalid option!")


    
if __name__ == "__main__":
    start_challenge()

这题的话是基于ECDSA的签名，其实和DSA是差不多的，可以简单了解一下流程

这题的话，我们注意到加密的时候的随机数k是被限制在一个很小的范围之内的，然后这个范围我们是可以控制的，我们只要控制current_seconds为1就可以了

拿到k之后直接根据s的等式拿到d就可以了

d = (s * k - H(m)) * r^ {-1} \ (mod\ n)

这边的n是椭圆曲线的阶，椭圆曲线的直接去实现源码查看即可

exp：

from hashlib import sha1
from Crypto.Util.number import *


p = 6277101735386680763835789423207666416083908700390324961279
b = 0x64210519E59C80E70FA7E9AB72243049FEB8DEECC146B9B1
E = EllipticCurve(GF(p), [-3, b])
n = E.order()

message = 'The time is 1:1'
H = bytes_to_long(sha1(message.encode()).digest())
r = 0xbce1ebbcf6b5e0d4f2c190fd9c33f078230a21f0cef7b151
s = 0x22d47c13fac8721ac71820cec3d0e8278d0cf38825ef517b
k = 100
d = (s * k - H) * inverse(r, n) % n
hex(d)

交互即可拿到flag

funny_rsa

加密代码：

import random
import libnum
from Crypto.Util.number import bytes_to_long, long_to_bytes

print("Welcome to ChunqiuCTF Game!")
print("接下来完成下面的挑战")
print("Good luck!")

# funny
hint = b' '
m = b' '
p = libnum.generate_prime(1024)
q = libnum.generate_prime(1024)
n = p * q

print("give you some funny numbers")
# funny 1
print(p+q - p*q + random.randint(-1025, +1025)) 
# funny 2
print(bytes_to_long(m)*bytes_to_long(hint))
# funny 3
print(bytes_to_long(m)*n*bytes_to_long(hint) - 1025)
# funny 4
print(pow(bytes_to_long(hint), 65537, n))

有非常多种做法，毕竟拿到了p+q 的近似值

拿到p+q的等式

\begin{array}{l} p + q + r = s\\ p * (s - p - r) = n\\ p^2 + (r - s) * p + n = 0 \end{array}

这边r是非常小的，可以简单爆破，然后看 $\Delta$ 里面能不能开根或者直接解方程都是可以的

exp1：

from gmpy2 import iroot
from tqdm import trange

h1 = -17696257697673533517695215344482784803953262308315416688683426036407670627060768442028628137969719289734388098357659521255966031131390425549974547376165392147394271974280020234101031837837842620775164967619688351222631803585213762205793801828461058523503457022704948803795360591719481537859524689187847958423587638744086265395438163720708785636319741908901866136858161996560525252461619641697255819255661269266471689541673348377717503957328827459396677344554172542244540931545166846117626585580964318010181586516365891413041095399344533013057011854734701706641516027767197631044458866554524544179750101814734153116374
h2 = 23686728880494758233026798487859622755203105120130180108222733038275788082047755828771429849079142070779731875136837978862880500205129022165600511611807590195341629179443057553694284913974985006590617143873019530710952420242412437467917519539591683898715990297750494900923245055632544763410401540518654522017115269508183482044872091052235608170710105631742176900306097734799793264202179181242015892763311753674799273300604804820015447161950996038795518844564861004398396796284113803759208011
h3 = 419166458284161364374927086939132546372091965414091344286510440034452974193054721041229068769658972346759176374539266235862042787888391905466876330331208651698002159575012622762558316612596034044109738533275009086940744966244759977014078484433213617582101347769476703012517531619023366639507114909172774156647998737369356116119513795863130218094614475699956104117183821832339358478426978211282822163928764161915824622224165694904342224081321345691796882691318330781141960650263488927837990954860719950761728580780956673732592771855694502630374907978111094148614378212006604233062606116168868545120407836000858982789824582335703891535021579560434875457656655941164757860852341484554015214879991896412137447010444797452119431147303295803678311972500421396900616845556636124424993090559354406417222700637726789045926994792374756038517484548544506630672251868349748176389591615802039026216656891403871728516658502023897343287181822303758976641229952646993446276281728919020747050486979968215989594984778920359425264076558022228448529089047021814759587052098774273578311709416672952218680244714492318709603579024
h4 = 13541898381047120826573743874105965191304100799517820464813250201030319771155430755606644860103469823030581858410957600027665504533335597988508084284252510961847999525811558651340906333101248760970154440885012717108131962658921396549020943832983712611749095468180648011521808106480590665594160479324931351996812185581193608244652792936715504284312172734662364676167010674359243219959129435127950232321130725013160026977752389409620674167037650367196748592335698164875097139931376389630867192761783936757260359606379088577977154378217235326249540098268616890307702288393952949444753648206049856544634755301197410481479
n = (h3 + 1025) // h2
s = h1 + n
for r in trange(-1026, 1026):
    p = 0
    if iroot((r - s) ^ 2 - 4 * n, 2)[1]:
        p1 = (-(r - s) + iroot((r - s) ^ 2 - 4 * n, 2)[0]) // 2
        p2 = (-(r - s) - iroot((r - s) ^ 2 - 4 * n, 2)[0]) // 2
        if p1 and n % p1 == 0:
            p = p1
        elif p2 and n % p2 == 0:
            p = p2
        if p:
            q = n // int(p)
            d = inverse(65537, (p - 1) * (q - 1))
            hint = int(pow(h4, d, n))
            m = long_to_bytes(int(h2 // hint))
            print(long_to_bytes(int(hint)))
            print(m)
            break
            
'''
b'Of course, So good, and enjoy the funny number, it is true flag'
b'fake:flag{5044833682931814367881036090727702841234957943094051805420875375031047763007750978962055801191968383860156687597666360268370292861}'
'''

开多线程爆一下，十几分钟能出

exp2：

from tqdm import trange
from Crypto.Util.number import *
from multiprocessing import Pool

def attack(range_):
    h1 = -17696257697673533517695215344482784803953262308315416688683426036407670627060768442028628137969719289734388098357659521255966031131390425549974547376165392147394271974280020234101031837837842620775164967619688351222631803585213762205793801828461058523503457022704948803795360591719481537859524689187847958423587638744086265395438163720708785636319741908901866136858161996560525252461619641697255819255661269266471689541673348377717503957328827459396677344554172542244540931545166846117626585580964318010181586516365891413041095399344533013057011854734701706641516027767197631044458866554524544179750101814734153116374
    h2 = 23686728880494758233026798487859622755203105120130180108222733038275788082047755828771429849079142070779731875136837978862880500205129022165600511611807590195341629179443057553694284913974985006590617143873019530710952420242412437467917519539591683898715990297750494900923245055632544763410401540518654522017115269508183482044872091052235608170710105631742176900306097734799793264202179181242015892763311753674799273300604804820015447161950996038795518844564861004398396796284113803759208011
    h3 = 419166458284161364374927086939132546372091965414091344286510440034452974193054721041229068769658972346759176374539266235862042787888391905466876330331208651698002159575012622762558316612596034044109738533275009086940744966244759977014078484433213617582101347769476703012517531619023366639507114909172774156647998737369356116119513795863130218094614475699956104117183821832339358478426978211282822163928764161915824622224165694904342224081321345691796882691318330781141960650263488927837990954860719950761728580780956673732592771855694502630374907978111094148614378212006604233062606116168868545120407836000858982789824582335703891535021579560434875457656655941164757860852341484554015214879991896412137447010444797452119431147303295803678311972500421396900616845556636124424993090559354406417222700637726789045926994792374756038517484548544506630672251868349748176389591615802039026216656891403871728516658502023897343287181822303758976641229952646993446276281728919020747050486979968215989594984778920359425264076558022228448529089047021814759587052098774273578311709416672952218680244714492318709603579024
    h4 = 13541898381047120826573743874105965191304100799517820464813250201030319771155430755606644860103469823030581858410957600027665504533335597988508084284252510961847999525811558651340906333101248760970154440885012717108131962658921396549020943832983712611749095468180648011521808106480590665594160479324931351996812185581193608244652792936715504284312172734662364676167010674359243219959129435127950232321130725013160026977752389409620674167037650367196748592335698164875097139931376389630867192761783936757260359606379088577977154378217235326249540098268616890307702288393952949444753648206049856544634755301197410481479
    n = (h3 + 1025) // h2
    p, q = var('p q')
    low = range_[0]
    high = range_[1]
    for r in trange(low, high):
        res = solve([p + q - n + r - h1, p * q - n], p, q)
        if res:
            try:
                for i in res:
                    pp = int(str(i[0]).split('==')[1])
                    if n % pp == 0:
                        qq = n // pp
                        d = inverse(65537, (pp - 1) * (qq - 1))
                        print(long_to_bytes(int(pow(h4, d, n))))
            except:
                pass
if __name__ == "__main__":   
    ranges = [(i, i + 82) for i in range(-1026, 1026, 82)]
    with Pool(25) as pool:    #2050 // 25 = 82
        r = list(pool.imap(attack, ranges))

有点坑的就是得到的flag还要再转一次字节，然后就是爆破范围注意是-1026到1026,1025是爆不出来的

factor

加密代码：

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


def pad(x, n):
    while len(x) < n // 8:
        x += os.urandom(1)
    return x


def genp(p, l):
    while 1:
        r = random.randint(1 << l - 1, 1 << l)
        if isPrime(p + r):
            return p + r


bits = 1024
b = 345
flag = pad(flag, bits * 3)
m = bytes_to_long(flag)
p = getPrime(bits)
q = genp(p, b)
r = genp(q, b)
n = p * q * r
print(n)
print(pow(m, 65537, n))
# 5605777780127871552103278440489930168557569118966981388111283042550796167470265465148458919374665519335013101681890408413810351780671950283765145543168779446153786190869731166707967097095246677053262868926963631796027692694223765625053269102325714361312299011876036815423751522482629914361369303649193526946050137701205931577449326939722902280884984494828850611521784382097900268639648421100760612558110614208245291400961758972415881709281708443424129033685255718996719201537066717587527029554871540574867831957154286334639399985379381455084604901293000229526196544921067214723085504463673412082637877637982771445298815007769526806112008703908400170846707986989384244531990469279604588770393462375930699135443458952703826608237292999895910024613311408883134789788541751697007502656798556053417265191533053158952284994030769145926816478390761642058013769635850833893158830591398862163134753203291719549474871116653745337968227
# 2998195560453407057321637509862236387961676411996988529185696118404592349869917006166370346762261303282478779647282039317061146533808487789458703169149689179547543732935053220010550004328207373171271534689897340156346458951776319267981966893926724550629182100766890856964207263709029611781806548130358294543573874132473259788387939849997550651614987993962540192023207354839106090274252125961835070701748643163379053118598595995782448140944376681636633592442158453965800439960134688017496184195454406927204485213436540382637720118180670197194949275760000729877093621741313147190401896114633643891311672542703928421032698499968701052818985292683628072129271790220674145955527935027879112279336148316425115255710066132502392447843608711463775710558880259205308541126041959858947252063815158749021817255637836170676726466347847422352280599210078359786387419424076245960344657767332883964636288493649066530215094453490169688507988

因为n基本上是p来贡献的，很容易直接想到开三次方，本地测试一下，大概前676个比特左右是一样的，保险起见我们取前675比特，那么思路肯定就是copper了

本地测试一下，在模n下，已知高691位可以打出来的完整的p，因为肯定是要爆破的，所以参数设置尽量松一点

from gmpy2 import iroot

ph = 8229818653479103995390711947901504293503919119002906757692673211141427632782063939852984716570444404226934289053606718145701556343398411948753588481107319458443964825653723814461069089907561271147331899380733
n = 2986320838953528253882088372388442016325702131189458796528478889386461534275868243137030186454014677421405960560420129517431737258060586287510720616925362339564580325699135382324704611097967886112809903433780495166632513358659623215604525475869695604493793719496688912828901066611157659511524094010018402370706635668320270939429024548827363395632537722417508347753006320003084933753707227067786684238723338923166468116221726492642439174999035407862775977166074478066494371695544194092614065064389846880413801217299211968533732898908741776807361345173405861309348701990236175668612631901148614516074252480163129329603341193008669401646046581249007282335880773266653822507540292433792953855683308557641380989619809849873727178552463580223160416783156078325493531359231887810096050566573941392148683582181643948542159792787007634357597305928040455728789658964768517602018312869516429651603393943092568009895086653939828007114801

R.<pl> = Zmod(n)[]
f = 2 ^ (1024 - 691) * ph + pl
f.small_roots(X = 2 ^ (1024 - 691), beta = 0.33)

#[6188152196882872000441434953179177374978694766984828872212991240257465749016224031116965183755089531]

直接爆破即可拿到p

直接跑发现还挺快的，就不开多线程了

from multiprocessing import Pool
from tqdm import trange

n = 5605777780127871552103278440489930168557569118966981388111283042550796167470265465148458919374665519335013101681890408413810351780671950283765145543168779446153786190869731166707967097095246677053262868926963631796027692694223765625053269102325714361312299011876036815423751522482629914361369303649193526946050137701205931577449326939722902280884984494828850611521784382097900268639648421100760612558110614208245291400961758972415881709281708443424129033685255718996719201537066717587527029554871540574867831957154286334639399985379381455084604901293000229526196544921067214723085504463673412082637877637982771445298815007769526806112008703908400170846707986989384244531990469279604588770393462375930699135443458952703826608237292999895910024613311408883134789788541751697007502656798556053417265191533053158952284994030769145926816478390761642058013769635850833893158830591398862163134753203291719549474871116653745337968227
c = 2998195560453407057321637509862236387961676411996988529185696118404592349869917006166370346762261303282478779647282039317061146533808487789458703169149689179547543732935053220010550004328207373171271534689897340156346458951776319267981966893926724550629182100766890856964207263709029611781806548130358294543573874132473259788387939849997550651614987993962540192023207354839106090274252125961835070701748643163379053118598595995782448140944376681636633592442158453965800439960134688017496184195454406927204485213436540382637720118180670197194949275760000729877093621741313147190401896114633643891311672542703928421032698499968701052818985292683628072129271790220674145955527935027879112279336148316425115255710066132502392447843608711463775710558880259205308541126041959858947252063815158749021817255637836170676726466347847422352280599210078359786387419424076245960344657767332883964636288493649066530215094453490169688507988
my_p = iroot(n, 3)[0]


R.<pl> = Zmod(n)[]
ph = int(bin(my_p)[2::][:675:], 2)
for i in trange(2 ^ 16):
    f = pl + 2 ^ 333 * i + 2 ^ 349 * ph
    
    root = f.small_roots(X = 2 ^ (1024 - 691), beta = 0.33)
    if root:
        p = root[0] + 2 ^ 333 * i + 2 ^ 349 * ph
        assert n % p == 0
        print(p)
        break



'''
23%|██▎       | 14984/65536 [01:13<04:08, 203.43it/s]
177641852143539875144076287104359901067433280125353192376052994247805596999311993133680118926203330508832035411734411354655205181670634659281906946269134849688257950688607255823034295123844247237760781276097419942184026876577385488539741117262151706924975877975832474838035368684036367680294369184184885365711
'''

然后直接在模 $q * r$ 下打二元copper就可以了

from Crypto.Util.number import *
import itertools


def small_roots(f, bounds, m=1, d=None):#多元copper
    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 = 5605777780127871552103278440489930168557569118966981388111283042550796167470265465148458919374665519335013101681890408413810351780671950283765145543168779446153786190869731166707967097095246677053262868926963631796027692694223765625053269102325714361312299011876036815423751522482629914361369303649193526946050137701205931577449326939722902280884984494828850611521784382097900268639648421100760612558110614208245291400961758972415881709281708443424129033685255718996719201537066717587527029554871540574867831957154286334639399985379381455084604901293000229526196544921067214723085504463673412082637877637982771445298815007769526806112008703908400170846707986989384244531990469279604588770393462375930699135443458952703826608237292999895910024613311408883134789788541751697007502656798556053417265191533053158952284994030769145926816478390761642058013769635850833893158830591398862163134753203291719549474871116653745337968227
c = 2998195560453407057321637509862236387961676411996988529185696118404592349869917006166370346762261303282478779647282039317061146533808487789458703169149689179547543732935053220010550004328207373171271534689897340156346458951776319267981966893926724550629182100766890856964207263709029611781806548130358294543573874132473259788387939849997550651614987993962540192023207354839106090274252125961835070701748643163379053118598595995782448140944376681636633592442158453965800439960134688017496184195454406927204485213436540382637720118180670197194949275760000729877093621741313147190401896114633643891311672542703928421032698499968701052818985292683628072129271790220674145955527935027879112279336148316425115255710066132502392447843608711463775710558880259205308541126041959858947252063815158749021817255637836170676726466347847422352280599210078359786387419424076245960344657767332883964636288493649066530215094453490169688507988
p = 177641852143539875144076287104359901067433280125353192376052994247805596999311993133680118926203330508832035411734411354655205181670634659281906946269134849688257950688607255823034295123844247237760781276097419942184026876577385488539741117262151706924975877975832474838035368684036367680294369184184885365711
R.<t1, t2> = Zmod(n // p)[]


t1 = 36612637538559704137020978084239164831057486505073569845873637454679077873685259765691802604546779099912
t2 = 86764840482114786370161852859709669396853471381872969412105255376939704081824493999267048666125470182348
q = p + t1
r = p + t2
phi = (p - 1) * (q - 1) * (r - 1)
d = inverse(65537, phi)
print(long_to_bytes(int(pow(c, d, n))))



'''
b'flag{24e33eda-f57c-42da-92c5-e0b39414cded}8^[\xcc\x0c\xd7,=\xba\x8a^\x8b|\'\x02\x92ocX\xc1\xeb\xc9\rL\x9b\xffM2\x97\xd6\xe1*\xa3z2\x8d\xc9c,\xb2\xf3\xff\xd8\x81\xc1\xc5\tN3\xa0\xaeWhg2\x10c\x01\xd1A\x8e~\xccP*U\xfa+\xd3!v\xf0\xfe\x91v\x9c%\x18\xb5\x04y\xe6\xab\xdd\x1f\x97\xf8\x7f\xa0\xe8\x8d*\xb3\xa9}@\xce"er\xdf1\x8e\xe2\x0f}D,\x16\x1d\xb3Fq;\x13\x9e\xbcNI@2\xb6\x05\xe3\xb15qa\x81~b\x95\xce\x01\xf4\x801\xa3f@\xc2\x19\x06\x97j\xe5\x9c\xc8\xa1m\xf5\xea\xa0\x9c\xaa*\x93ZK\xb3^\\}\x80\xecl\x0b.)\xd3(qM\xe5{VdY\x92$\tOQ\x8aybT\xa2A\xe1{\x0c\xe2\x89\xf3R\'\xf7=~\xcdg\x8e\x86\xe5\xa2v\x9f\xf2RU9pL7\x84\xfb#\xc5&\x15\x96\'\xe9/<w\xde\xe8:fp\xb8\x99\xf8\t\x9a\xcb9/p\x0bG\xd3j\x9bP\xab\x95\xae\xed/\x88\xbe\x93\x15\x1cI\xfb\x0eN!O\xccn\xec\xd31\xaf\xa6\xde\xa9\xbeh\xc0j1)z\x90\tK\xcfFJ\x19<a\x96$u+H\x9avL\xa5\xfc\xe1\xb0\xd1n\x8e\xc3\xb8\x02\xa4\xe0\xdeu\x84\xc8\xba^\x954\x07\xc1c6\xd3\x00\x8fMj\x9eS\xdb\xa8\xc2V\xe0\xed \xa9\xf4\x99\x12\x16p\x9a!'
'''

dance

加密代码：

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

m = [int(i) for i in bin(bytes_to_long(flag))[2:].zfill(len(flag) * 8)]

p = 0x1A0111EA397FE69A4B1BA7B6434BACD764774B84F38512BF6730D2A0F6B0F6241EABFFFEB153FFFFB9FEFFFFFFFFAAAB
E = EllipticCurve(GF(p), [0, 4])
G1, G2 = E.gens()
o1, o2 = G1.order(), G2.order()
r = [randint(1, o1 - 1) for _ in range(len(m) + 1)]
c = []
for i in range(len(m)):
    A = r[i] * G1 + m[i] * G2
    B = m[i] * G1 + r[i + 1] * G2
    c.extend(A + B)
open("out.txt", "w").write(f"c = {c}")

这个曲线是配对友好曲线，求配对的速度很快，很明显考点就是配队，那就是要根据比特位来做一个decision

这题和SUCTF的那题不一样，那题是配对的点是未知的，而这题是已知的，很明显就不是从阶来入手了，我们尝试那 $G_1$ 和 $G_2$ 来作为配对点试试

通过尝试

观察m两个相邻的比特位，当他们都是0的时候，有

\begin{array}{l} e(G_1, r_0 * G_1 + r_1 * G_2) = e(G_1, G_2)^{r_1} \\ e(G_2, r_1 * G_1 + r_2 * G_2) = e(G_2, G_1)^{r_1} = e(G_1, G_2)^{-r_1}\\ \end{array}

很明显，当相邻的比特位是0的时候，他们配对后相乘的积为1

同理，当都是1的时候，有

\begin{array}{l} e(G_1, r_0 * G_1 + G_2 + G_1 + r_1 * G_2) = e(G_1, G_2)^{r_1 + 1} \\ e(G_2, r_1 * G_1 + G_2 + G_1 + r_2 * G_2) = e(G_2, G_1)^{r_1 + 1} = e(G_1, G_2)^{-r_1 - 1}\\ \end{array}

这时候也满足相乘的结果是1，本地测试是成立的

from Crypto.Util.number import *

p = 0x1A0111EA397FE69A4B1BA7B6434BACD764774B84F38512BF6730D2A0F6B0F6241EABFFFEB153FFFFB9FEFFFFFFFFAAAB
E = EllipticCurve(GF(p), [0, 4])
G1, G2 = E.gens()
o1, o2 = G1.order(), G2.order()
r = [randint(1, o1 - 1) for _ in range(11)]
c = []

# A1 = r[0] * G1
# B1 = r[1] * G2

# A2 = r[1] * G1
# B2 = r[2] * G2

A1 = r[0] * G1 + G2
B1 = G1 + r[1] * G2

A2 = r[1] * G1 + G2
B2 = G1 + r[2] * G2



tmp1 = G1.weil_pairing(A1 + B1, o1)
tmp2 = G2.weil_pairing(A2 + B2, o2)
tmp1 * tmp2

由这两个作为decision即可，判断一下当前flag的最后一位是1还是0然后就可以判断下一位

exp：

from Crypto.Util.number import *

flag = bin(bytes_to_long(b'flag{'))[2::].zfill(40)
# print(flag) #0110011001101100011000010110011101111011

p = 0x1A0111EA397FE69A4B1BA7B6434BACD764774B84F38512BF6730D2A0F6B0F6241EABFFFEB153FFFFB9FEFFFFFFFFAAAB
E = EllipticCurve(GF(p), [0, 4])
G1, G2 = E.gens()
o1, o2 = G1.order(), G2.order()



with open('out.txt', 'r') as f:  #附件里去掉那个c=就行了
    tmp = f.readlines()
    points = []
    for i in range(0, len(tmp), 3):
        points.append(E(tmp[i].strip().strip('[],'), tmp[i + 1].strip().strip('[],')))

    for i in range(39, len(points) - 1):
        if flag[-1] == '1':
            tmp1 = G1.weil_pairing(points[i], o1)
            tmp2 = G2.weil_pairing(points[i + 1], o2)
            
            if tmp1 * tmp2 == 1:
                flag += '1'
            else:
                flag += '0'
        elif flag[-1] == '0':
            tmp1 = G1.weil_pairing(points[i], o1)
            tmp2 = G2.weil_pairing(points[i + 1], o2)
            if tmp1 * tmp2 == 1:
                flag += '0'
            else:
                flag += '1'
    print(long_to_bytes(int(flag, 2))) #b'flag{0331d347-6fd2-4159-9c84-0f78373933bd}'