• [HITCON CTF 2022] Superprime，rev Meow_way，BabySSS格基约减法，Secret共模攻击模未知

    目录

    Superprime

    Reverse Meow_way

    BabySSS

    Secret

    Superprime

    这个题5层RSA加密，很简单就是要带条件爆破5组p,q，一开始看错了，对为5组是一一对应的，回头发现后边两对不是对应的。

    1. from Crypto.Util.number import getPrime, isPrime, bytes_to_long
    2.  
    3.  
    4. def getSuperPrime(nbits):
    5.     while True:
    6.         p = getPrime(nbits)
    7.         pp = bytes_to_long(str(p).encode())
    8.         if isPrime(pp):
    9.             return p, pp
    10.  
    11.  
    12. p1, q1 = getSuperPrime(512)  #ok
    13. p2, q2 = getSuperPrime(512)  
    14. p3, q3 = getSuperPrime(512)
    15. p4, q4 = getSuperPrime(512)
    16. p5, q5 = getSuperPrime(512)
    17.  
    18. n1 = p1 * q1
    19. n2 = p2 * p3 #明显很小，不是 p2*q2是p2*q3
    20. n3 = q2 * q3
    21. n4 = p4 * q5
    22. n5 = p5 * q4
    23.  
    24. e = 65537
    25. c = bytes_to_long(open("flag.txt", "rb").read().strip())
    26. for n in sorted([n1, n2, n3, n4, n5]):
    27.     c = pow(c, e, n)
    28.  
    29. print(f"{n1 = }")
    30. print(f"{n2 = }")
    31. print(f"{n3 = }")
    32. print(f"{n4 = }")
    33. print(f"{n5 = }")
    34. print(f"{e = }")
    35. print(f"{c = }")

    对三种情况对应3种爆破姿势。

    数据部分，方便哪们想复现的话可以用。hitcon的题目会放到googleapis上，但这个地址对国内极不稳定，明通明不通

    1. n1 = 132240475872174910020944408159013384770525986234801028624784519134365862704105251340824787510945183963356820885920367304711310957365047441178683686926111455575911962257698539064559510444855775549001648292058855493337857073693460061212792795075263084221929517773754699732129582794061997056827998985829666251060653380798686353779510948629280009197715644814616657550158740378670095210797455828266323922570838468050733341304227070902756780052159113811360169205531739117518635829837403006788948761106892086004133969899267757339921
    2. n2 = 95063555614573541810575593850289506856925979977609991181205616159125089261546784721154599484613262518469706157215924537125160406418217535531993036958388330505871763176297570429533467696205928686731756713059807727405313286020007347211892135226632724359291407913539632339885950358476265995466145680878334722001
    3. n3 = 59077122528757446350604269162079270359932342538938986760275099248290981958441838384256597839386787448447136083450980256330743221155636885358548541847176342745397373638152767362253944731433134474562146358334422503033973244936835557423934491676324297243326613498319086748647812745223753746779568080090592100960499863677438403657325762852705171109382084916335379889394829715777901290096314487661584614712488781379507151355301063123233880909931925363322846957197537676660047824476129446066149857051131731840540157488590899311381370266592295206055792990886734933291304077440476730373491475852882163732120626849448728573574411786320772125534383707413572678316508826450778346723441956945169297689138799298561759843280317867927205551400065163199599457
    4. n4 = 24589423756497058585126900932611669798817346035509889383925628660158156567930038333401661451846451875869437263666365776498658699865323180836374906288949824205543130261556051807217164348291174483234810669420041361857307271050079366739157441129916338485838528114129985080841445467007786565727910355311119650431197742495274527401569906785121880408809802492383216836691265423297722021017515667257863302820657924121913047547741420413553737917632809270380269758313556777803344394624408862183672919570479289614998783678080936272369083
    5. n5 = 185885020243714550225131939334004568560534422416697599024696590344782893162219788079305752632863387855011040772104676488940707663157284194641170875157382507202789029285286466326803699701161968587945867047101502048926016515139728368809523009828247173096909917611001113266938209226483162533302629909322412013492978440863258135181226831155024690292336026753678424906151360739424148666951389956182136072508650529271179749569637083537783283360860102371562796635391549934474381821125255176073752645643893294533330184238070085333427
    6. e = 65537
    7. c = 44836759088389215801662306050375432910426695023654894661152471598197009644316944364461563733708795401026569460109604554622161444073404474265330567406370705019579756826106816505952084633979876247266812002057927154389274998399825703196810049647324831928277737068842860115202258059693760003397831075633707611377854322143735834890385706873765241863615950449707047454133596389612468366465634011925228326638487664313491916754929381088396403448356901628825906815317934440495749705736715790281606858736722493438754469493049523175471903946974639097168758949520143915621139415847104585816466890751841858540120267543411140490236193353524030168152197407408753865346510476692347085048554088639428645948051171829012753631844379643600528027854258899402371612
    8.  
    9. from Crypto.Util.number import getPrime, isPrime, bytes_to_long,long_to_bytes 
    10. from gmpy2 import invert, iroot 
    11.  
    12. def getSuperPrime(nbits):
    13.     while True:
    14.         p = getPrime(nbits)
    15.         pp = bytes_to_long(str(p).encode())
    16.         if isPrime(pp):
    17.             return p, pp

    第1种，最简单，因为q = bytes_to_long(str(p)),p,q是相关的可以直接爆破，原先经常用的是2进制的，现在这个是10进制的，就乘pow(10,i)

    1. #1,
    2. #n1 = p1 * q1
    3. def get_sq(n, l):
    4.     p = 0
    5.     for i in range(l,-1,-1):
    6.         for j in range(9,-1,-1):
    7.             sp = p + j*pow(10, i)
    8.             sq = bytes_to_long(str(sp).encode())
    9.             if sp*sq<= n:
    10.                 p = sp 
    11.                 print("", i, j)
    12.                 break 
    13.     print(p)
    14.     return p
    15.  
    16. p1 = get_sq(n1, 220)
    17. #p1 = 8146548592442976266345996123132853490697005499246649457977706700220974227149533573761967281334961993159106889103915430835029497970085237349414587895387361
    18. q1 = bytes_to_long(str(p1).encode())

    对于n2,n3来说由于p,q并不对应，所以这里从后向前爆破，正好通过n3尾部判断。如果没有这人实际上只通过n2尾部的话是不能爆破的，有数不清的组合。

    从后爆破的话还有一个问题，就是不足位时前被0，但如果是最后一位就不再被0，所以这里对小的做了能分解直接退出，避免无法判断的补0出现。

    1. #2,
    2. #n2 = p2 * p3
    3. #n3 = q2 * q3
    4. def get_tail(p2,p3, idx):
    5.     print(f"{idx}\n{p2=}\n{p3=}")
    6.     tn2 = p2*p3 
    7.     if tn2>n2:
    8.         return False
    9.     if p2>1 and n2%p2 == 0:
    10.         print(f"OK\n{p2=}\n{n2//p2}")
    11.         exit()
    12.     for i in range(10):
    13.         for j in range(10):
    14.             tp2 = p2+i*pow(10,idx)
    15.             tp3 = p3+j*pow(10,idx) 
    16.             if str(tp2*tp3)[-(idx+1):] == ('000'+str(n2))[-(idx+1):]:
    17.                 if idx == 154:
    18.                     print('x', str(tp2*tp3)[-(idx+1):], ('000'+str(n2))[-(idx+1):])
    19.                 #爆到的 idx 字节 * 8 位 与n3 比较
    20.                 sq2 = bytes_to_long(str(tp2).zfill(idx+1).encode())
    21.                 sq3 = bytes_to_long(str(tp3).zfill(idx+1).encode()) #当不足时补0，当足时补0错
    22.                 mask = (1<<((idx+1)*8))-1
    23.                 if ((sq2*sq3)^n3) & mask == 0:
    24.                     #print(hex(mask), tp2,tp3)
    25.                     get_tail(tp2,tp3, idx+1)
    26.  
    27. get_tail(0,0,0)
    28. p2 = 8896291584885417569104339023688932443326753617531842711599106401724528341937087331194574622599888534531753509912922572906401573640791655490141830263538581
    29. q2 = bytes_to_long(str(p2).encode())
    30. p3 = 10685750878049478986600454022422733804784834227531623991827538970867377925593354382775253050419846972347584519245766235538419501021140939003899401773087821
    31. q3 = bytes_to_long(str(p3).encode())

    第3种由于p4*q5没有尾部特征，只能从头开始爆破。需要判断上下边界，即后部全0大于n和后部全9小于n的情况剪掉。

    1. #n4 = p4 * q5
    2. #n5 = p5 * q4
    3. def get_45(p4,p5,idx):
    4.     if idx<0:
    5.         return False
    6.     if idx<153 and (p4==0 or p5 == 0):  #154-155位10进制
    7.         return False
    8.     if p4>1 and n4%p4 == 0:
    9.         print(f'OK\n{p4 = }\np5 = {long_to_bytes(n4//p4)}')
    10.         exit()
    11.     #print(idx,p4,p5)
    12.     q4 = bytes_to_long(str(p4).encode())
    13.     q5 = bytes_to_long(str(p5).encode())
    14.     if p4*q5 > n4 or p5*q4 > n5:
    15.         #print('>')
    16.         return False 
    17.     if idx>0:
    18.         sp4 = str(p4).encode()[:-idx]+b'9'*(idx)
    19.         sp5 = str(p5).encode()[:-idx]+b'9'*(idx)
    20.         #if idx<2:
    21.         #    print(idx,sp4,sp5)
    22.         rp4 = int(sp4)
    23.         rp5 = int(sp5)
    24.         rq4 = bytes_to_long(sp4)
    25.         rq5 = bytes_to_long(sp5)
    26.         if idx<154 and p4>0 and p5>0 and (rp4*rq5or rp5*rq4
    27.             #print(f"{idx} ,{rp4} ,{rp5} , {rq4}, {rq5}, {n4}, {n5}, {p4*rq5
    28.             return False
    29.     
    30.     for i in range(10):
    31.         for j in range(10):
    32.             #print('>>>>>',idx,i,j)
    33.             tp4 = p4+i*pow(10,idx-1)
    34.             tp5 = p5+j*pow(10,idx-1) 
    35.             get_45(tp4,tp5, idx-1)
    36.  
    37. #get_45(0,0,155)
    38. p4 = 6759224678814800913204473280361658486772650199941114505283409645622497866148765146601841353932633241398607040792961131806556756943022446601137737571037341
    39. p5 = 11868750061342011267437975338788313730068511026231254554820987614699325962867540061083226545014725808842166519144882448332395484715124334891963558447955747
    40. q4 = bytes_to_long(str(p4).encode())
    41. q5 = bytes_to_long(str(p5).encode())
    42. #print(n4%p4, n5%p5)

    最后是5个已经分解n的RSA按从大到小顺序解密

    1. d1 = invert(e, (p1-1)*(q1-1))
    2. d2 = invert(e, (p2-1)*(p3-1))
    3. d3 = invert(e, (q2-1)*(q3-1))
    4. d4 = invert(e, (p4-1)*(q5-1))
    5. d5 = invert(e, (p5-1)*(q4-1))
    6.  
    7. #加密顺序 2,1,5,4,3
    8. m = pow(pow(pow(pow(pow(c,d3,n3),d4,n4),d5,n5),d1,n1),d2,n2)
    9. print(long_to_bytes(m))
    10. #b"hitcon{using_different_combinations_of_primes_still_doesn't_make_this_bad_prime_generation_method_any_safer...}"

    Reverse Meow_way

    这个题一看就用了复杂的东西。

    1. int __cdecl main(int argc, const char **argv, const char **envp)
    2. {
    3.   char v4; // [esp+0h] [ebp-24h]
    4.   int v5; // [esp+0h] [ebp-24h]
    5.   int v6; // [esp+14h] [ebp-10h]
    6.   int v7[2]; // [esp+18h] [ebp-Ch] BYREF
    7.  
    8.   v7[0] = -1;
    9.   v7[1] = -1;
    10.   if ( argc < 2 )
    11.   {
    12.     sub_401340("Usage: %s \n", (char)*argv);
    13.     exit(1);
    14.   }
    15.   if ( strlen(argv[1]) != 48 )
    16.   {
    17.     sub_401340("Wrong length\n", v4);
    18.     exit(1);
    19.   }
    20.   v6 = (int)argv[1];
    21.   dword_40544C(v6, v6 >> 31, v6, v6 >> 31, 196, 0, v7, (int)v7 >> 31);
    22.   ++v6;
    23. ......
    24.   dword_4053F4(v6, v6 >> 31, v6, v6 >> 31, 152, 0, v7, (int)v7 >> 31);
    25.   dword_405438(v6 + 1, (v6 + 1) >> 31, v6 + 1, (v6 + 1) >> 31, 101, 0, v7, (int)v7 >> 31);
    26.   v5 = memcmp(&unk_405018, argv[1], 0x30u);     // 将0x30依次修改为1,2,...仅判断1个字节，爆破得到flag
    27.   if ( v5 )
    28.   {
    29.     sub_401340("Wrong\n", v5);
    30.     exit(-1);
    31.   }
    32.   sub_401340("I know you know the flag!\n", 0);
    33.   return 0;
    34. }

    用了48个函数，和参数，每个函数又都是指针，还被隐藏了。

    不过最后有个问题memcmp对全部进行比较，这里如果将0x30改为1，他就仅对第1个字符比较。这样通过修改比较的长度就可以实现爆破了。

    这个字节在0x401bf5在文件里的偏移是0xff5

    后来看了别人的帖子，这里用push 0x33;retf将32位转64位执行，可惜没有get到出题人的用心。

    1. import subprocess
    2.  
    3. data = list(open('meow_way.exe', 'rb').read())
    4.  
    5. flag = ''
    6. for i in range(1, 0x31):
    7.     fname = f'meow_{i}.exe'
    8.     data[0xff5] = i 
    9.     open(fname, 'wb').write(bytes(data))
    10.     for v in range(0x21, 0x7f):
    11.         tmp = (flag+chr(v)).ljust(0x30, '0')
    12.         rc,out= subprocess.getstatusoutput(f"{fname} {tmp}") 
    13.         if 'I know you know the flag!' in out:
    14.             flag += chr(v)
    15.             print(flag)
    16.             break            
    17.  
    18. print(flag)
    19. #hitcon{___7U5T_4_S1mpIE_xB6_M@G1C_4_mE0w_W@y___} 提交不正确，把两头的下划开线删掉
    20. #hitcon{7U5T_4_S1mpIE_xB6_M@G1C_4_mE0w_W@y}

    BabySSS

    看到一个大牛博客 ，里边有3道，说是后两道以后上，关注中。

    这个题我用的crt方法，他还提到格基约减法。

    M=[11...11...x1x2...x81........................x1128x2128...x81281−y1−y2...−y81]" role="presentation" style="position: relative;">M=[11...11...x1x2...x81........................x1128x2128...x81281−y1−y2...−y81]

    由于并没有取模，只是限制在64位，所以把右部单位阵的1部分改为2^-63 

    然后进行约减，结果中前8位为0的行对应的值再乘2**63就得到对应的一组v

    1. #LLL法
    2. V = matrix(QQ, 130,8+130)
    3. for i in range(8):
    4.     for j in range(129):
    5.         V[j,i] = pow(a[i][0], j)
    6.     V[129,i] = -a[i][1]
    7.  
    8. for i in range(129):
    9.     V[i, 8+i] = pow(2, -63)
    10. V[129,8+129] = 1
    11.  
    12. k = V.LLL()
    13. #前8位全0的行
    14. v = k[1][8:-1]*9223372036854775808  #2**63

    Secret

    看上去挺简单，就是个共模攻击，由于共模攻击时可以两边共同除其中一项m^(p+e1) / m^(p+e0) = m^(e1-e0) 所以这里的p可以解决掉。

    麻烦的就是模未知。

    “取一组核空间的基构成的矩阵，在这个矩阵上进行LLL算法即可得到符合条件的小系数 ki" role="presentation" style="position: relative;">ki 。因为我们不能求逆，把正负号分两边进行计算，即可得到n的整数倍 Kn" role="presentation" style="position: relative;">Kn , 利用多组这样的倍数求一个最大公倍数即可恢复n。” 一时没理解，原样复制。

    1. from output import es,cs
    2.  
    3. B = matrix(ZZ, 2, 64)
    4. B[0] = es 
    5. B[1] = [1 for _ in range(64)]
    6.  
    7. M = B.right_kernel_matrix()
    8. L = M.LLL()
    9.  
    10. #求n
    11. def compute_kn(coff):
    12.     res_right = 1
    13.     res_left = 1
    14.     for i ,cof in enumerate(coff):
    15.         if cof > 0:
    16.             res_right = res_right * cs[i]**cof
    17.         else:
    18.             res_left = res_left * cs[i]**(-cof)
    19.     return res_left - res_right
    20.  
    21. n = compute_kn(L[0])
    22. #再求公约数
    23. for l in L[1:]:
    24.     n = gcd(compute_kn(l),n)
    25.     n = factor(n,limit = 2**20)[-1][0]
    26.     if n.nbits() <= 2048:
    27.         break
    28. print(n)

    得到n后先处理一下p，然后用共模攻击

    1. n = 17724789252315807248927730667204930958297858773674832260928199237060866435185638955096592748220649030149566091217826522043129307162493793671996812004000118081710563332939308211259089195461643467445875873771237895923913260591027067630542357457387530104697423520079182068902045528622287770023563712446893601808377717276767453135950949329740598173138072819431625017048326434046147044619183254356138909174424066275565264916713884294982101291708384255124605118760943142140108951391604922691454403740373626767491041574402086547023530218679378259419245611411249759537391050751834703499864363713578006540759995141466969230839
    2.  
    3. from Crypto.Util.number import *
    4. mpe1_inv = inverse(cs[0],n)
    5. _es = [e-es[0] for e in es[1:]]       # _c = m^(e1-e0)
    6. _cs = [c*mpe1_inv%n for c in cs[1:]]  # 
    7.  
    8. #找两个互素的e进行共模攻击 find gcd(_ei,_ej) = 1
    9. find = False
    10. for i in range(len(_es)):
    11.     for j in range(len(_es)):
    12.         if gcd(_es[i],_es[j]) == 1:
    13.             find = True
    14.             break
    15.     if find:
    16.         break
    17. print(i,j)
    18.  
    19. e1,e2 = _es[i] , _es[j]
    20. c1,c2 = _cs[i] , _cs[j]
    21. g, x1, x2 = xgcd(e1,e2)
    22. m = pow(c1,x1,n)*pow(c2,x2,n) % n
    23. print(long_to_bytes(int(m)))
    24. #hitcon{K33p_ev3rythIn9_1nd3p3ndent!}

  • 相关阅读:
    [CKA]考试之基于角色的访问控制-RBAC
    使用Tomcat搭建一个Servlet项目
    keepalived的简单使用
    Ubuntu下Git使用教程：从入门到实践
    【Rust光年纪】Rust 机器人学库全景：功能、安装与API概览
    realloc函数应用&IO泄露体验
    【Day31】力扣算法(超详细思路+注释)[1441. 用栈操作构建数组 ] [621. 任务调度器]
    计算机专业课笔记集中整理贴（持续更新中。。。）
    cnpm安装步骤
    SpringBoot-43-文件上传
  • 原文地址：https://blog.csdn.net/weixin_52640415/article/details/128141821