NepCTF2022

​ nepnep战队的招新赛，题目出的很用心，师傅们也很可爱(nepnep打钱~)；由于是个人赛，各个方向都会点的我最后卷到了rank5，这大概就是全沾菜鸟的优势吧(笑)。
​ 记录一下密码方向赛题和比赛中没有做出的misc题目。

Crypto

signin

签到，费马分解n，crt求c，然后解。

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 gmpy2 import *
from Crypto.Util.number import *

n = 19955580242010925349026385826277356862322608500430230515928936214328341334162349408990409245298441768036250429913772953915537485025323789254947881868366911379717813713406996010824562645958646441589124825897348626601466594149743648589703323284919806371555688798726766034226044561171215392728880842964598154362131942585577722616354074267803330013886538511795383890371097812191816934883393255463554256887559394146851379087386846398690114807642170885445050850978579391063585254346364297374019309370189128443081285875218288166996242359495992824824109894071316525623741755423467173894812627595135675814789191820979950786791
e = 65537

def fermat(num):
    x = iroot(num, 2)[0]
    if x * x < num:
        x += 1

    # y^2 = x^2 - num
    while (True):
        y2 = x * x - num
        y = iroot(y2, 2)[0]
        if y * y == y2:
            break
        x += 1

    result = [int(x + y), int(x - y)]
    print(result)

if __name__ == '__main__':
    p = 141264221379693044160345378758459195879285464451894666001807667429134348549398732060237738374405784248735752195059908618618110595213605790125890251970818437656069617772772793421437649079362238861287098916200835889507111259332056471215428085418047179545017193159169629731673653136069647622114441162534727202901
    q = 141264221379693044160345378758459195879285464451894666001807667429134348549398732060237738374405784248735752195059908618618110595213605790125890251970818437656069617772772793421437649079362238861287098916200835889507111259332056471215428085418047179545017193159169629731673653136069647622114441162534727202891
    assert p*q == n
    c_mod_p = 32087476819370469840242617415402189007173583393431940289526096277088796498999849060235750455260897143027010566292541554247738211165214410052782944239055659645055068913404216441100218886028415095562520911677409842046139862877354601487378542714918065194110094824176055917454013488494374453496445104680546085816
    c_mod_q = 59525076096565721328350936302014853798695106815890830036017737946936659488345231377005951566231961079087016626410792549096788255680730275579842963019533111895111371299157077454009624496993522735647049730706272867590368692485377454608513865895352910757518148630781337674813729235453169946609851250274688614922

    phi = (p-1)*(q-1)
    d = invert(e,phi)
    from sympy.ntheory.modular import *

    l = crt([q, p], [c_mod_p, c_mod_q])
    t = int(l[0])
    print(long_to_bytes(pow(t,d,n)))
    # b'NepCTF{ju5t_d0_f4ct_4nd_crt_th3n_d3crypt}'

中学数学

推导过程：

这里ph只是损失了低位，对p的影响非常小，可以近似为p计算，所以整体就看做一元二次方程计算了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
from Crypto.Util.number import *
import sympy
import gmpy2
n = 13776679754786305830793674359562910178503525293501875259698297791987196248336062506951151345232816992904634767521007443634017633687862289928715870204388479258679577315915061740028494078672493226329115247979108035669870651598111762906959057540508657823948600824548819666985698501483261504641066030188603032714383272686110228221709062681957025702835354151145335986966796484545336983392388743498515384930244837403932600464428196236533563039992819408281355416477094656741439388971695931526610641826910750926961557362454734732247864647404836037293509009829775634926600458845832805085222154851310850740227722601054242115507
c = 6253975396639688013947622483271226838902346034187241970785550830715516801386404802832796746428068354515287579293520381463797045055114065533348514688044281004266071342722261719304097175009672596062130939189624163728328429608123325223000160428261082507446604698345173189268359115612698883860396660563679801383563588818099088505120717238037463747828729693649297904035253985982099474025883550074375828799938384533606092448272306356003096283602697757642323962299153853559914553690456801745940925602411053578841756504799815771173679267389055390097241148454899265156705442028845650177138185876173539754631720573266723359186
e=65537
t=gmpy2.iroot(4*2**500*(2**500+1)*n,2)[0]
p=t//(2*(2**500+1))
print(p)
while True:
    p=sympy.prevprime(p)
    print(p)
    if n%p==0:
        q=n//p
        phi=(p-1)*(q-1)
        d=inverse(e,phi)
        m=pow(c,d,n)
        print(long_to_bytes(m))
        break
# b'flag{never_ignore_basic_math}'

COA_RSA

题目给了格规约方式，需要利用它的格构造方式去猜想e的形式，从而爆破求phi；出题人测试过，发现论文的攻击方式几乎无法成功，所以还是考虑爆破吧。
给的hint：

由于满足格规约条件，所以A是比较小的，即$A=m^{x-e}modn$比较小，猜想e的结构是这样的，其中k，a，b都不大：

因为这样的结构可以保证A运算以后为：

hash师傅提醒了下，这里需要保证k//a*phi是m的阶的倍数，所以尽量要满足k//a大于1；经查阅论文发现paper中的e确实是这个结构，所以直接进行爆破就好，有趣的是还可以用二分法求出k的值：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
from Crypto.Util.number import *
from tqdm import tqdm
import gmpy2
N=21584562909016222405243274981318074723609424537864138818516166296882870952596923388616896100179452902343709246295468740335682613555154383977025156631083258377497353559709636001246215851357586251697339782140616762844466658464225538929007012548727508420837702781524936615164070353418037478517089569783507555024418411710631778073941565485748505472232785028182423960096719453903248061164351629862893495202801853287312265865916733075532360012981688805080299664971109817752216823608878051817158172160419426189481753020154076548471877219325637944601624370884640014467928928695819398270014246851395540617763179525187009648347
e=3083508987002317486463324997331153531944203505409162688359452328126124421799560484088128014311350414620529892327924105762240373365022054853860736661583322625356764794244233714463745121622512321671048540305802394692066665494889362704143858935532501202976814683074990945023438621916862496931012795683358222146303422749958603642494190335211644060403826011553655733835479351434022282429633638548092493767861402690047591624267078125799219896130381280612151738318061042109602694447606410766564110264194828211637692086652912524063147129310052531789754620749834783108524619617738417203269142329494376062347356009094704271801
c=4350922598266339224026193891975078418170168801819772034264767820713898265684630717877568988722980203827973605369872324389093738872638952249759042892387749292013137399168284781320083750172563798340746904451459359268152189983004829803065811628192447436195347501480101582498240174872791092809557067538800318476384792579696811714128502969704568997167132768453189707964546102168532460995624338582249438596921314744866700025932162716723912105789085167524526913197129852605391260182535842364550510703599942313178440055016324692710162447783500265413604087721982116926701740447032328198647967485123967003172122184982695286738
for i in tqdm(range(1,30)):
    for j in range(1,30):
        for k in range(7,8): # 经测试k很小为 7
            phi=(e+k)*j
            if phi%i==0:
                phi=phi//i
                d=gmpy2.invert(e,phi)
                m=pow(c,d,N)
                if m.bit_length()<200:
                    print(long_to_bytes(m))

P or S

pbox可以对应mod2矩阵，于是计算过程可以归纳为：

由于flag格式startwith flag，足够32bit，所以可以用这一明密文对求出$P^6m$后边加的那一部分，再解出flag其余部分即可。

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
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
Pbox=[
[0, 3, 6, 9, 10, 11, 13, 16, 18, 19, 20, 24, 25, 27, 28, 29, 30, 31],
[0, 1, 3, 8, 9, 11, 12, 14, 16, 18, 19, 23, 24, 25, 26, 28, 29],
[0, 1, 2, 3, 9, 10, 11, 13, 19, 20, 22, 25, 27, 28, 29, 31],
[0, 2, 3, 5, 6, 7, 8, 13, 16, 19, 21, 25, 26, 27, 28],
[2, 4, 6, 7, 9, 11, 12, 13, 16, 17, 20, 21, 22, 23, 24, 25, 27, 31],
[2, 10, 13, 15, 16, 17, 21, 22, 23, 24, 29, 31],
[1, 2, 8, 11, 12, 13, 16, 17, 19, 21, 22, 24, 25, 26, 27, 28, 30, 31],
[0, 3, 6, 13, 14, 17, 19, 21, 22, 23, 26, 27, 28],
[1, 5, 7, 8, 11, 12, 14, 15, 19, 23, 25, 27, 31],
[0, 2, 3, 6, 7, 8, 9, 10, 11, 12, 16, 18, 19, 22, 23, 24, 25, 26, 27, 28],
[0, 1, 6, 7, 10, 15, 16, 21, 24, 25, 29, 30],
[1, 4, 5, 6, 7, 12, 13, 15, 18, 19, 20, 22, 26, 27, 29, 31],
[0, 3, 5, 8, 9, 17, 21, 22, 24, 25, 26, 27, 30],
[0, 2, 3, 4, 5, 6, 7, 8, 11, 17, 19, 20, 24, 25, 26, 27, 30],
[2, 6, 7, 8, 11, 12, 14, 16, 20, 21, 22, 24, 29, 30, 31],
[0, 2, 5, 6, 7, 8, 9, 10, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 25, 29, 31],
[0, 1, 2, 3, 4, 5, 8, 10, 11, 12, 13, 16, 17, 18, 20, 21, 22, 23, 25, 26, 28, 29, 30],
[3, 5, 6, 8, 10, 13, 14, 17, 19, 20, 21, 22, 24, 26, 27, 29, 30],
[1, 3, 6, 12, 14, 15, 16, 17, 18, 21, 24, 25, 26, 27, 28],
[0, 1, 2, 3, 5, 6, 7, 8, 9, 12, 13, 19, 20, 23, 26, 29, 30],
[3, 4, 6, 7, 8, 9, 10, 11, 12, 13, 14, 16, 20, 21, 22, 25, 26, 27, 28, 29, 30],
[0, 1, 2, 4, 6, 7, 9, 10, 11, 13, 15, 16, 18, 19, 20, 21, 25, 31],
[0, 2, 7, 10, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 25, 29, 31],
[1, 2, 3, 5, 7, 8, 18, 19, 21, 22, 23, 25, 31],
[3, 4, 7, 8, 10, 11, 13, 14, 17, 18, 19, 21, 22, 23, 24, 28, 29],
[0, 2, 6, 7, 8, 10, 11, 12, 13, 16, 18, 19, 21, 23, 31],
[0, 1, 3, 4, 8, 13, 14, 16, 18, 19, 21, 26, 27, 30, 31],
[5, 6, 7, 9, 13, 14, 15, 18, 19, 20, 21, 24, 25, 28],
[1, 3, 4, 5, 6, 7, 11, 14, 16, 17, 19, 20, 21, 22, 23, 25, 30, 31],
[2, 3, 4, 6, 7, 11, 13, 17, 18, 19, 20, 23, 24, 25, 26, 28, 29, 30, 31],
[0, 1, 2, 3, 4, 7, 9, 10, 13, 15, 16, 19, 22, 23, 24, 25, 27],
[0, 1, 3, 4, 12, 16, 18, 19, 26, 30]]
P=[]
for i in Pbox:
    tmp=[]
    for j in range(32):
        if j in i:
            tmp.append(1)
        else:
            tmp.append(0)
    P.append(tmp)
P=Matrix(Zmod(2),P)
print(P)
P=P^6
c='0111110000100101000001101011110111101100000010110011101111000101111110111111100100100010001011000101000110110011111101000001001000000101111000001110001111001001100100111000011011101111111101001011100000100100110011111101100111001100111111110001111011101100'
v1='01100110011011000110000101100111'
v2='01111100001001010000011010111101'
tmp1=[int(i) for i in v1]
tmp2=[int(i) for i in v2]

v1=vector(Zmod(2),tmp1)
v2=vector(Zmod(2),tmp2)
T=v2-P*v1
M=[]
for i in range(0,len(c),32):
    tmp=[]
    for j in range(32):
        tmp.append(c[i+j])
    v=vector(Zmod(2),tmp)
    m=list(P^(-1)*(v-T))
    for i in range(len(m)):
        M.append(str(m[i]))
print(bytes.fromhex(hex(int(''.join(M),2))[2:]))
# b'flag{P_has_no_Semantic_Security}'

Misc

太忙了，摸了。

扫一扫，分享到微信

微信分享二维码
本站总访问量： 总访客次数：

tag:

梦想是成为全栈佬并养一只猫