黑龙江省赛

发表于 分类于 阅读次数： Waline： 本文字数： 964 阅读时长 ≈ 4 分钟

从其他师傅那里拿到一些赛题

初赛

1

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
from Crypto.Util.number import *
from Crypto.Util.Padding import pad
from sage.all import *
flag = open('flag', 'rb').read()

n_bits = 1024
beta = 0.29
delta = 0.45
assert delta < (3/4 - beta)
flag1 = pad(flag[:len(flag)//2], n_bits//16)
p = next_prime(bytes_to_long(flag1))
pqdiff_bound = 1 << int(n_bits * beta)
pqdiff_lower_bound = 1 << int(n_bits * beta - 1)
q = next_prime(p - random_prime(pqdiff_bound, lbound=pqdiff_lower_bound))
n = p*q
phi = (p-1)*(q-1)
d_bound = 1 << int(n_bits*delta)
d_lower_bound = 1 << int(n_bits * delta - 1)

while True:
    d = random_prime(d_bound, lbound=d_lower_bound)
    if gcd(d, phi) == 1:
        e = inverse_mod(d, phi)
        if gcd(e, phi) == 1:
            break

print(f'n = {n}')
print(f'e = {e}')

flag2 = pad(flag[len(flag)//2:], n_bits//8-1)
m = bytes_to_long(flag2)
c = pow(m, e, n)
print(f'c = {c}')


"""
n = 12779292788328507635646485236446323990578456114967808016182263578178494180795370424798860493650480053570371250811905773960481750940458827979861184722353108227092212225595979824252209841697659509529606215126716440565931530812981595774746754816326511322383070955072647153550727568166534351477967896890021106177
e = 9127521457923354456069487334973053064242751338553190692058159575640567634725596267894601092335626785885309669456842153792617210853891969129983736241476545935575261789952791385304618176639748270574246664480305757268659559315780221543289523307886165842999070576207133912422055150609884199685294091097607124409
c = 4715199541938838482829660474842815637758774748907642018610952495675409399919781649074418880398481916563366285817131200590553788510331744823499159289515632966376454919605434679417642103846284370991583023683038608112090557964515005763676931627459252593722505464252259469202165279234233266578704442372964772018
"""

自己拿点数据测试了一下，p.bit_length() = 511

根据

1
2
3
pqdiff_bound = 1 << int(n_bits * beta)
pqdiff_lower_bound = 1 << int(n_bits * beta - 1)
q = next_prime(p - random_prime(pqdiff_bound, lbound=pqdiff_lower_bound))

pqdiff介于$2^{296}—2^{297}$，所以$q$的高(511 - 297)位和$p$一样。

把$n$的高位开根号即可得到$p,q$的高(511-297)位

转成byte即可取出flag1

再把flag1带回

1
2
flag1 = pad(flag[:len(flag)//2], n_bits//16)
p = next_prime(bytes_to_long(flag1))

再爆破一些位数即可得到p

exp:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
from Crypto.Util.number import *
from Crypto.Util.Padding import pad
import gmpy2

n = 12779292788328507635646485236446323990578456114967808016182263578178494180795370424798860493650480053570371250811905773960481750940458827979861184722353108227092212225595979824252209841697659509529606215126716440565931530812981595774746754816326511322383070955072647153550727568166534351477967896890021106177
c = 4715199541938838482829660474842815637758774748907642018610952495675409399919781649074418880398481916563366285817131200590553788510331744823499159289515632966376454919605434679417642103846284370991583023683038608112090557964515005763676931627459252593722505464252259469202165279234233266578704442372964772018
e = 9127521457923354456069487334973053064242751338553190692058159575640567634725596267894601092335626785885309669456842153792617210853891969129983736241476545935575261789952791385304618176639748270574246664480305757268659559315780221543289523307886165842999070576207133912422055150609884199685294091097607124409

n_bits = 1024
n_ = n >> (1024-428)
# print(gmpy2.iroot(n_,2))

p = 7019637774422141444612401478000362521900151189205476410764462730 << (511 - 213)
print(p)
flag1 = long_to_bytes(p)
# print(flag1)

flag1 = b'DASCTF{9a697216-6900-4'
flag1 = pad(flag1, n_bits//16)
# print(flag1)

p = bytes_to_long(flag1)
print(p)

for i in range(2**(511-213)):
    p = p + 1
    if n % p == 0:
        print(i)
        q = n // p
        phi = (p-1)*(q-1)
        d = gmpy2.invert(e,phi)
        m = pow(c,d,n)
        flag2 = long_to_bytes(int(m))
        flag = b'DASCTF{9a697216-6900-4' + flag2
        print(flag)
        break
# DASCTF{9a697216-6900-4a72-92e1-e3eefd98794f}

决赛

1

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
from Crypto.Util.number import *
from secret import FLAG

m = bytes_to_long(FLAG)


def getpq(nbit):
    p = getPrime(nbit)
    q = getPrime(nbit)
    if p > q:
        return p, q
    else:
        return q, p


p, q = getpq(512)
P = (p - q) & ((1 << 130) - 1)
n = p * q

leak_p = p >> 256

c = pow((1 + P * n), m, n ** 3)

print('n =', n)
print('leak_p =', leak_p)
print("c =", c)

# n = 135133139540786818977969958456509467902948924003478556140490841984247464940261764739984274397650928404945721248284577232814352745333641188749824519153271662051302477973525156608141358709265683759057060630360909926255299541198485901065352661702656282587105799982740927802530997159098015074633017964344230291287
# leak_p = 115314121469787984258489158421056136177545051135641551928888818017665807264468
# c = 1836794759996264077871820946090708779709415760553736759453665641907562256633157424959089180650539327925671892742819931875681606982615287882656254828326465758462357812873839261469783652663796071814218493268788421243190729887313099383264588659922912876424206670310928514588754069909128149471326084547056385690037197908766053620702238356084124023146075698878494434053246157524775269473152458661801907641122308756667762880284617915774590075511686821816948174618196839335059944389423693187930672934293905608970421003536691336581450927887931599275461176935079227494931457562345640133982771901848553204154760760399724074615092290799119053032875792219794072963200108352944441876206386518960615891547166767499506114294860833404421893612197040731184031783165365621722947731966143226777081983415797778111715332055871302609049501876860012070502369090417942239749695034267695710324328867728296996779

给出p的高256位，把epsilon改成0.01，爆破8位即可恢复p

根据$c \equiv (1+Pn)^m \mod n^3$

展开得到$c \equiv 1^m + mPn + \frac{m(m-1)}{2}P^2n^2 +…+(Pn)^m\mod n^3$
$\therefore c \equiv 1 + mPn + \frac{m(m-1)}{2}P^2n^2 \mod n^3$

$c-1 = mPn + \frac{m(m-1)}{2}P^2n^2$，这个方程解不出来

同除$n$得到

$\frac{c-1}{n} = mP + \frac{m(m-1)}{2}P^2n$

解这个方程

exp:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
#sage
from tqdm import *
n = 
leak_p = 115314121469787984258489158421056136177545051135641551928888818017665807264468
c = 

pbits = 512

p_high = leak_p

for i in trange(2**8,0,-1):
     p4 = p_high<<8    #这里需要先爆破8位，使得知道264位以后再恢复p
     p4 = p4 + i
     kbits = pbits - p4.nbits()
     p4 = p4 << kbits
     R.<x> = PolynomialRing(Zmod(n))
     f = x + p4
     x1 = f.small_roots(X=2^kbits, beta=0.4, epsilon=0.01)
     if x1:
         p = p4 + int(x1[0])
         if int(p).bit_length() == pbits:
             print("p=",p)
             q = n // p
             print("q=",q)
             break
print('over')

P = (p - q) & ((1 << 130) - 1)

c1 = (c-1) // n
var('m')
f = m*P + (m*(m-1)/2) * P^2*n - c1 
ans = solve(f,m)
print(ans)

#m = 569500674440382718231575264852597803870681506457438686903594776739090860497616821068120838321533
# DASCTF{365d0d2cda3a3836a19bf1f46760d875}

2

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
import libnum
import gmpy2
from Crypto.Util.number import *
import flag, e1, e2

# 生成素数
p = libnum.generate_prime(1024)
q = libnum.generate_prime(1024)
ec1 = pow(bytes_to_long(str(e1).ljust(20, "D").encode()), 3, p * q)
ec2 = pow(bytes_to_long(str(e2).ljust(20, "A").encode()), 5, p * q)
m = libnum.s2n(flag)
n = p * q
c1 = pow(m, e1, n)
c2 = pow(m, e2, n)

print("n1=", n)
print("ec1=", ec1)
print("c1=", c1)
print("n2=", n)
print("ec2=", ec2)
print("c2=", c2)

# n1= 27929259512873502442719286790227037320417984116570178470037376373267390909685621247157535458203218619293705428397911754453556082799420494496904478215709219317542924547049229150153308059698341011305505985823374280465467094476511869541135508518055946815227085548571701115773386101962695795789178321155174729047033298389886321980592410739667139376075568555729949442873964097042006391886635957242436522435588904492484342259494858627609438654632887244523845583473711604632109405043439047289868784236481926074763997559971182741918345193506253460323445846136663027639802131457594564405906763806426256107923417802076262573737
# ec1= 24979839185643431898760549059477070141596292955202172081572583839065034831779499992829742773873064296311713734486020739853343887094398935731264
# c1= 17695186679431856780362905635257355413310120106982055323913669124182832151093921194946365178919380690844190324897933591567360925332869903671651849060145290581360223200011298757871213149464298017718829480721410479504940393501845624196721013966839230696831321482946841011452400364600924503121451272593970649100410603943321149604376033957124800064565646929720179239631538966228020882733213221035707244692798307971636126058586394357032072695921642665492919186476321028415907982915011972040971875733852055633796811898421692604356476773910338982400925245494707729878821466569634334862311750349321720627252469986162120031838
# n2= 27929259512873502442719286790227037320417984116570178470037376373267390909685621247157535458203218619293705428397911754453556082799420494496904478215709219317542924547049229150153308059698341011305505985823374280465467094476511869541135508518055946815227085548571701115773386101962695795789178321155174729047033298389886321980592410739667139376075568555729949442873964097042006391886635957242436522435588904492484342259494858627609438654632887244523845583473711604632109405043439047289868784236481926074763997559971182741918345193506253460323445846136663027639802131457594564405906763806426256107923417802076262573737
# ec2= 2838620519239658396968146844964839207179863729944843241951228382052657801460586137213053314019699976475855578055607417923815486109050614096157077528657405905877896929808094661904905136761365045387901486261011216958309860644255996588189249
# c2= 10770781309274554738409447671578241895686779262243081931452089039730277591151694112684863740412412713684216227740930573490322958500198235497947657939304932868457999239593145330718657422535271157683896034543125292529800047408131765376686654378173684648427311300423776510153307756388404568013401217965931456538849277670384454454507752525534110389604969437991055504757081225690155489265359117617764571537216746554060783131168749700810806387918510612057149583061938836035963175555630655718716139689761210220525955656039741684390906935720406757364893793459339618913268943282961044530062475057887777134887741597041684698119

低加密指数＋共模攻击

需要注意的是$e_1$，$e_2$公因数为3

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
from Crypto.Util.number import *
import gmpy2

n = 
ec1= 
ec2= 
c1= 
c2= 

me1 = gmpy2.iroot(ec1,3)[0]
me2 = gmpy2.iroot(ec2,5)[0]
print(long_to_bytes(me1))
print(long_to_bytes(me2))
e1 = 34967
e2 = 65535

t = gmpy2.gcd(e1,e2)
s,x,y = gmpy2.gcdext(e1,e2)
if t == 1:
    m = (pow(c1,x,n)*pow(c2,y,n)) % n
    print(long_to_bytes(m))
else:
    for k in range(1000):
        m = gmpy2.iroot((pow(c1,x,n)*pow(c2,y,n)%n + k*n),t)
        if m[1]:
            print(long_to_bytes(m[0]))
            break
        else:
             k += 1
# DASCTF{afd2eabdb2be11eda3a094085339ce84}

逆向工程

1
8eeb2dfb89f4b617abf9b6ac7bae3ee2777e85ec7e85a85a

出题人非碳基生物

先转byte，再base64加密

确认一下，你没有看错，就是base64加密，原来逆向工程指的是这个啊

exp:

1
2
3
4
5
6
7
8
9
10
from Crypto.Util.number import *
import base64

c = "8eeb2dfb89f4b617abf9b6ac7bae3ee2777e85ec7e85a85a"
c1 = long_to_bytes(int(c,16))
print(c1)

flag = b"DASCTF{" + base64.b64encode(c1) + b'}'
print(flag)
# DASCTF{just+4n0ther+base64+4nd+hex+haha}
-------------已经到底啦！-------------