祥云杯

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

第二次参加了，时间好快呀

tracing

大概的逻辑就是从日志逆推出phi

从最后这里return a可以看出s一直是0

img

，所以只有三种情况，分别判定然后逆就行了

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
from Crypto.Util.number import long_to_bytes, inverse

def if_exc(ct):
    for i in ct:
        if 'a, b = b, a' in i:
            return True
        else:
            continue
    return False

def isOdd(a):
    return a & 1 == 1

f = open('trace.out', 'r')
a = f.read().split('\n')
l = len(a)
phi = 1
e = 0

for i in range(l-1, 0, -1):
    if 'task.py(6):     while b != 0:' == a[i]:
        idx = i
        ct = a[idx: idx+13]
        if if_exc(ct):
            phi, e = e, phi

        if 'task.py(9):                 a = a - b' in ct and "task.py(10):                 a = rshift1(a)" in ct:
            phi = 2 * phi + e
            if isOdd(phi):
                continue

            else:
                phi = phi + 1
                continue

        elif "task.py(14):                 b = rshift1(b)" in ct:
            e *= 2
            continue

        elif "task.py(19):                 a = rshift1(a)" in ct:
            phi *= 2
            continue

    else:
        continue

c = 64885875317556090558238994066256805052213864161514435285748891561779867972960805879348109302233463726130814478875296026610171472811894585459078460333131491392347346367422276701128380739598873156279173639691126814411752657279838804780550186863637510445720206103962994087507407296814662270605713097055799853102
n = 113793513490894881175568252406666081108916791207947545198428641792768110581083359318482355485724476407204679171578376741972958506284872470096498674038813765700336353715590069074081309886710425934960057225969468061891326946398492194812594219890553185043390915509200930203655022420444027841986189782168065174301
d = inverse(e, phi)
print(phi)
print(long_to_bytes(pow(c, d, n)))

fill

背包+lcg套娃

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
from Crypto.Util.number import inverse
from hashlib import sha256

S = 492226042629702
nbits = 32
n = 991125622
s0, s1, s2 = 562734112, 859151551, 741682801
m = (s2 - s1) * inverse(s1 - s0, n) % n 
c = (s2 - m * s1) % n
s = [0] * nbits
s[0] = s0
for i in range(1, nbits):
    s[i] = (s[i-1]*m+c)%n
# print(s)
M = [19621141192340, 39617541681643, 3004946591889, 6231471734951, 3703341368174, 48859912097514, 4386411556216, 11028070476391, 18637548953150, 29985057892414, 20689980879644, 20060557946852, 46908191806199, 8849137870273, 28637782510640, 35930273563752, 20695924342882, 36660291028583, 10923264012354, 29810154308143, 4444597606142, 31802472725414, 23368528779283, 15179021971456, 34642073901253, 44824809996134, 31243873675161, 27159321498211, 2220647072602, 20255746235462, 24667528459211, 46916059974372]
for t in range(nbits):
    M[t] = M[t] - s[t]
A = Matrix(ZZ,nbits+1,nbits+1)
# fill in the identity matrix
for i in range(nbits):
    A[i,i] = 1
# replace the bottom row with your public key
for i in range(nbits):
    A[i,nbits] = M[i]
# last element is the encoded message
A[nbits,nbits] = -int(S)
res = A.LLL()
print(res[-1][:-1]) #need to remove last element 0
msg = ''
for i in range(nbits):
    msg += str(res[-1][:-1][i])
msg = int(msg, 2)
print(msg)
print('flag{' + sha256(str(msg).encode()).hexdigest() + '}')

little little fermat

高位相同，开根取高位，然后copper就分解，求阶那里直接用order

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
import gmpy2
from Crypto.Util.number import long_to_bytes, isPrime
n = 141321067325716426375483506915224930097246865960474155069040176356860707435540270911081589751471783519639996589589495877214497196498978453005154272785048418715013714419926299248566038773669282170912502161620702945933984680880287757862837880474184004082619880793733517191297469980246315623924571332042031367393
c = 81368762831358980348757303940178994718818656679774450300533215016117959412236853310026456227434535301960147956843664862777300751319650636299943068620007067063945453310992828498083556205352025638600643137849563080996797888503027153527315524658003251767187427382796451974118362546507788854349086917112114926883

p_high = 1722441419253596810002937511265334240319736590159222908199095871448693784787182036443
PR.<z> = PolynomialRing(Zmod(n))
f = z + p_high*2^(512-280)
z0 = f.small_roots(X=2^(512-280), beta=0.4)
p_q = []
for z in z0:
    p = int(z + p_high*2^(512-280))
    if isPrime(p):
        p_q.append(p)
p = max(p_q)
q = n // p
phi = (p - 1) * (q - 1)
d = inverse_mod(65537, phi)
m = pow(c, d, n)
G=GF(p)
x = G(114514).order() - 1
x = x^2
print(long_to_byets(m^^x))

leak_rsa

总的逻辑是先用d的高位去爆破32位的k，再用k去爆破pqd，第一步的代码直接抄github上的https://github.com/jvdsn/crypto-attacks/blob/5c7989ceac599f1f8e016b5afb0d2966759cd470/test/test_factorization.py#L46，但是因为是32bit要用多进程才跑的出：

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
import time
from multiprocessing import Pool

def get_params_prob():
    n = 73380160475470842653695210816683702314062827937540324056880543809752271506601290265975543542548117392788987830919581511428492717214125296973338501980504384307279414528799452106399062576988406269897425829853390463840834798274139351938197666753546672052277640048588091137812362810008344723302886421059831149393
    e = 3116872133
    c = 69574121902821459446683688068339366486115223765903849266663001038736496551168104587683366853482649748413400537793260948337629422998336301256862519087984048032673577462034223842650399943613576577927825123830629917138007035313624847266208032195071033675853881447717750353382112841885318776240405314057286867952
    hint1 = {120: '0', 401: '0', 58: '1', 420: '0', 192: '1', 164: '0', 100: '0', 425: '1', 227: '0', 497: '0', 284: '0', 110: '1', 257: '0', 31: '1', 68: '0', 2: '1', 206: '0', 174: '1', 326: '0', 320: '0', 498: '1', 50: '1', 7: '0', 128: '1', 54: '1', 15: '1', 222: '0', 166: '1', 496: '1', 151: '1', 317: '0', 449: '1', 181: '1', 288: '1', 311: '1', 80: '1', 69: '1', 410: '1', 127: '1', 308: '1', 39: '0', 435: '0', 258: '0', 235: '1', 94: '1', 93: '1', 412: '0', 427: '0', 352: '1', 123: '0', 25: '0', 316: '1', 3: '0', 88: '1', 390: '0', 72: '1', 450: '1', 397: '0', 309: '1', 487: '1', 207: '0', 234: '0', 144: '1', 229: '1', 48: '1', 506: '0', 253: '1', 86: '0', 384: '0', 428: '0', 359: '1', 104: '0', 339: '0', 142: '0', 452: '1', 480: '0', 224: '1', 310: '1', 98: '1', 508: '0', 133: '0', 90: '1', 170: '0', 146: '0', 101: '1', 416: '1', 460: '1', 387: '0', 67: '0', 285: '0', 213: '1', 162: '1', 14: '0', 485: '1', 413: '1', 312: '1', 458: '0', 75: '0', 242: '1', 177: '1', 30: '1', 501: '0', 434: '1', 456: '0', 264: '0', 407: '0', 135: '1', 84: '0', 476: '0', 471: '1', 430: '1', 191: '0', 176: '0', 29: '1', 156: '0', 26: '0', 322: '1', 388: '1', 364: '1', 321: '1', 351: '0', 230: '1', 345: '0', 432: '1', 36: '0', 296: '1', 79: '0', 23: '0', 290: '1', 117: '0', 507: '1', 421: '0', 274: '0', 6: '1', 327: '1', 204: '1', 383: '0', 305: '1', 113: '0', 334: '0', 85: '1', 511: '1', 464: '1', 491: '0', 370: '0', 92: '0', 495: '0', 279: '1', 346: '1', 16: '1', 44: '1', 24: '0', 466: '1', 87: '0', 243: '0', 461: '0', 379: '0', 256: '0', 473: '1', 17: '0', 276: '1', 147: '1', 187: '0', 112: '1', 218: '1', 78: '1', 411: '1', 343: '0', 10: '1', 271: '1', 378: '0', 492: '0', 269: '1', 291: '0', 289: '0', 132: '1', 9: '1', 408: '0', 398: '1', 468: '1', 124: '1', 236: '0', 377: '1', 83: '0'}
    hint2 = {125: '0', 86: '1', 8: '0', 498: '1', 311: '0', 93: '0', 385: '0', 315: '1', 300: '1', 454: '0', 152: '0', 205: '0', 400: '1', 348: '1', 18: '1', 154: '0', 51: '1', 435: '0', 25: '1', 430: '0', 72: '1', 136: '0', 294: '0', 466: '0', 388: '0', 428: '0', 440: '1', 250: '1', 506: '0', 48: '0', 270: '1', 318: '0', 107: '0', 327: '1', 474: '0', 325: '0', 281: '0', 392: '0', 473: '1', 13: '1', 90: '0', 278: '0', 425: '0', 109: '1', 423: '1', 412: '1', 190: '1', 171: '0', 475: '1', 441: '1', 336: '0', 371: '0', 323: '0', 22: '1', 469: '0', 451: '0', 438: '0', 203: '1', 121: '0', 52: '1', 494: '1', 399: '0', 314: '0', 24: '1', 183: '0', 492: '1', 246: '1', 108: '1', 379: '0', 460: '1', 56: '0', 372: '1', 313: '1', 44: '0', 237: '1', 12: '0', 6: '0', 204: '1', 80: '1', 339: '1', 296: '0', 483: '0', 402: '0', 67: '0', 338: '1', 116: '0', 406: '1', 218: '0', 115: '0', 301: '0', 490: '1', 502: '0', 343: '1', 46: '1', 321: '0', 231: '1', 88: '0', 404: '1', 426: '0', 344: '0', 123: '1', 463: '0', 45: '1', 461: '1', 1: '0', 229: '0', 28: '1', 274: '1', 134: '1', 104: '1', 21: '0', 256: '0', 471: '1', 157: '0', 217: '1', 158: '0', 307: '1', 26: '0', 255: '0', 386: '1', 373: '0', 114: '1', 360: '0', 148: '1', 383: '1', 63: '0', 19: '1', 472: '0', 201: '1', 262: '1', 47: '0', 221: '0', 310: '0', 352: '1', 224: '1', 185: '0', 214: '1', 285: '1', 410: '0', 455: '0', 445: '0', 464: '0', 284: '1', 503: '1', 298: '1', 449: '0', 477: '0', 376: '0', 16: '0', 133: '0', 177: '1', 210: '0', 364: '1', 163: '1', 213: '1', 295: '1', 111: '1', 458: '0', 146: '0', 244: '0', 261: '1', 508: '1', 106: '0', 112: '1', 120: '0', 156: '1', 303: '0', 259: '1', 35: '0', 444: '0', 215: '1', 304: '0', 140: '0', 351: '0', 443: '0'}
    hint3 = {891: '0', 74: '0', 129: '0', 477: '0', 880: '1', 57: '0', 473: '0', 289: '1', 361: '1', 1012: '0', 529: '0', 294: '1', 174: '1', 500: '0', 257: '1', 392: '1', 405: '1', 11: '0', 763: '1', 637: '1', 564: '0', 941: '1', 923: '1', 1014: '1', 670: '1', 558: '0', 304: '1', 444: '1', 716: '0', 208: '0', 130: '1', 634: '1', 661: '0', 862: '0', 412: '1', 796: '1', 761: '1', 113: '1', 752: '0', 818: '0', 797: '1', 390: '1', 337: '0', 133: '1', 367: '1', 470: '1', 345: '1', 170: '1', 312: '0', 624: '1', 53: '1', 75: '1', 281: '1', 522: '1', 100: '0', 554: '1', 583: '1', 16: '1', 836: '0', 715: '1', 450: '0', 484: '0', 876: '0', 165: '0', 842: '0', 62: '0', 442: '1', 927: '0', 586: '1', 399: '1', 227: '0', 886: '1', 663: '0', 947: '0', 906: '1', 377: '0', 246: '1', 365: '0', 177: '1', 59: '1', 63: '0', 936: '1', 144: '0', 416: '1', 228: '1', 366: '0', 117: '0', 78: '0', 717: '1', 14: '0', 800: '1', 47: '0', 80: '0', 34: '0', 662: '1', 970: '0', 986: '1', 287: '1', 597: '0', 783: '0', 805: '1', 112: '1', 671: '1', 540: '1', 153: '1', 577: '1', 543: '0', 414: '0', 123: '1', 626: '1', 452: '1', 810: '1', 30: '0', 905: '0', 602: '1', 537: '1', 374: '0', 408: '1', 434: '0', 137: '1', 532: '0', 397: '0', 333: '1', 258: '1', 359: '1', 134: '1', 322: '1', 653: '0', 1018: '0', 639: '1', 40: '1', 826: '1', 489: '0', 5: '0', 858: '0', 44: '1', 516: '0', 149: '0', 945: '0', 106: '1', 694: '0', 221: '0', 207: '0', 186: '1', 316: '0', 449: '1', 297: '1', 276: '0', 103: '0', 437: '0', 802: '0', 108: '1', 921: '1', 427: '0', 728: '1', 879: '0', 953: '0', 51: '1', 459: '0', 37: '0', 559: '0', 610: '1', 341: '0', 299: '0', 952: '0', 201: '0', 327: '0', 741: '1', 253: '1', 310: '1', 946: '1', 696: '0', 398: '1', 266: '1', 829: '0', 908: '0', 469: '0', 873: '1', 658: '0', 798: '1', 54: '0', 621: '0', 238: '0', 654: '1', 205: '0', 925: '0', 391: '1', 480: '0', 4: '0', 598: '0', 677: '0', 142: '1', 606: '0', 118: '0', 164: '0', 973: '1', 347: '0', 159: '1', 307: '1', 83: '1', 668: '1', 675: '0', 924: '1', 191: '1', 890: '0', 352: '1', 965: '1', 692: '1', 782: '1', 817: '1', 889: '1', 515: '1', 433: '0', 356: '0', 845: '1', 104: '0', 18: '0', 979: '0', 426: '0', 785: '1', 546: '0', 52: '0', 55: '0', 824: '1', 704: '1', 510: '1', 710: '0', 1022: '0', 647: '0', 465: '1', 245: '0', 850: '1', 657: '0', 1007: '0', 807: '1', 158: '1', 328: '0', 292: '1', 355: '1', 596: '0', 275: '1', 371: '0', 1004: '0', 594: '0', 384: '1', 446: '1', 7: '0', 994: '1', 616: '1', 317: '0', 305: '0', 151: '1', 400: '0', 900: '1', 203: '0', 563: '1', 745: '1', 536: '1', 726: '0', 751: '1', 402: '1', 116: '0', 781: '1', 988: '0', 768: '1', 688: '1', 954: '1', 976: '1', 868: '1', 723: '1', 131: '1', 794: '0', 513: '0', 914: '1', 641: '1', 319: '0', 629: '1', 620: '1', 711: '0', 601: '0', 531: '0', 393: '0', 168: '0', 132: '0', 17: '0', 950: '0', 488: '0', 679: '0', 568: '0', 43: '1', 545: '1', 217: '0', 680: '1', 501: '1', 1008: '0', 514: '0', 746: '0', 187: '0', 436: '1', 336: '1', 139: '1', 338: '0', 695: '1', 300: '0', 584: '1', 152: '0', 828: '1', 251: '0', 691: '1', 296: '1', 128: '0', 394: '1', 655: '1', 544: '1', 58: '0', 313: '1', 565: '1', 685: '1', 720: '0', 178: '1', 667: '0', 403: '1', 697: '1', 138: '1', 659: '0', 960: '0', 454: '0', 271: '0', 33: '0', 295: '0', 600: '0', 579: '1', 68: '1', 211: '1', 82: '1', 114: '1', 209: '0', 226: '0', 753: '0', 874: '0', 903: '1', 358: '0', 141: '0', 236: '1'}

    def getnum(hint, bit):
        s = ['?'] * bit
        for tmp in hint.items():
            s[tmp[0]] = tmp[1]
        ss = ''
        return ss.join(s)

    p_corr = getnum(hint1, 512)
    q_corr = getnum(hint2, 512)
    d_corr = getnum(hint3, 1024)
    return n, e, c, p_corr, q_corr, d_corr, hint3

def run(args):
    # fn: 函数参数是数据列表的一个元素
    N, e, c, p_corr, q_corr, d_corr, hint_d = get_params_prob()
    MY_SIZE = 508
    my_hint_d = {x: y for x, y in hint_d.items() if x < MY_SIZE}
    l, r = args
    for k in range(max(1, l), min(e, r)):
        d_tilde = (k*(N+1)+1) // e
        d_tilde_str = bin(d_tilde)[2:].zfill(1024)
        for x, y in my_hint_d.items():
            if (d_tilde_str[x] != y):
                break
        else:
            print('FIND ANS:', k)
            return
    # print(f'Find {(l, r)} failed')

if __name__ == "__main__":
    testX = [(2**24*i, 2**24*(i+1)) for i in range(256)]
    print('concurrent:')  # 创建多个进程，并行执行
    pool = Pool(256)  # 创建拥有3个进程数量的进程池
    
    pool.map(run, testX)
    pool.close()  # 关闭进程池，不再接受新的进程
    pool.join()  # 主进程阻塞等待子进程的退出

拿到k以后爆破pq，直接用春哥的代码

https://zhuanlan.zhihu.com/p/266059082 ，四元变三元，也很吃算力

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
66
import random

n = 73380160475470842653695210816683702314062827937540324056880543809752271506601290265975543542548117392788987830919581511428492717214125296973338501980504384307279414528799452106399062576988406269897425829853390463840834798274139351938197666753546672052277640048588091137812362810008344723302886421059831149393
e = 3116872133
c = 69574121902821459446683688068339366486115223765903849266663001038736496551168104587683366853482649748413400537793260948337629422998336301256862519087984048032673577462034223842650399943613576577927825123830629917138007035313624847266208032195071033675853881447717750353382112841885318776240405314057286867952
hint1 = {120: '0', 401: '0', 58: '1', 420: '0', 192: '1', 164: '0', 100: '0', 425: '1', 227: '0', 497: '0', 284: '0', 110: '1', 257: '0', 31: '1', 68: '0', 2: '1', 206: '0', 174: '1', 326: '0', 320: '0', 498: '1', 50: '1', 7: '0', 128: '1', 54: '1', 15: '1', 222: '0', 166: '1', 496: '1', 151: '1', 317: '0', 449: '1', 181: '1', 288: '1', 311: '1', 80: '1', 69: '1', 410: '1', 127: '1', 308: '1', 39: '0', 435: '0', 258: '0', 235: '1', 94: '1', 93: '1', 412: '0', 427: '0', 352: '1', 123: '0', 25: '0', 316: '1', 3: '0', 88: '1', 390: '0', 72: '1', 450: '1', 397: '0', 309: '1', 487: '1', 207: '0', 234: '0', 144: '1', 229: '1', 48: '1', 506: '0', 253: '1', 86: '0', 384: '0', 428: '0', 359: '1', 104: '0', 339: '0', 142: '0', 452: '1', 480: '0', 224: '1', 310: '1', 98: '1', 508: '0', 133: '0', 90: '1', 170: '0', 146: '0', 101: '1', 416: '1', 460: '1', 387: '0', 67: '0', 285: '0', 213: '1', 162: '1', 14: '0', 485: '1', 413: '1', 312: '1', 458: '0', 75: '0', 242: '1', 177: '1', 30: '1', 501: '0', 434: '1', 456: '0', 264: '0', 407: '0', 135: '1', 84: '0', 476: '0', 471: '1', 430: '1', 191: '0', 176: '0', 29: '1', 156: '0', 26: '0', 322: '1', 388: '1', 364: '1', 321: '1', 351: '0', 230: '1', 345: '0', 432: '1', 36: '0', 296: '1', 79: '0', 23: '0', 290: '1', 117: '0', 507: '1', 421: '0', 274: '0', 6: '1', 327: '1', 204: '1', 383: '0', 305: '1', 113: '0', 334: '0', 85: '1', 511: '1', 464: '1', 491: '0', 370: '0', 92: '0', 495: '0', 279: '1', 346: '1', 16: '1', 44: '1', 24: '0', 466: '1', 87: '0', 243: '0', 461: '0', 379: '0', 256: '0', 473: '1', 17: '0', 276: '1', 147: '1', 187: '0', 112: '1', 218: '1', 78: '1', 411: '1', 343: '0', 10: '1', 271: '1', 378: '0', 492: '0', 269: '1', 291: '0', 289: '0', 132: '1', 9: '1', 408: '0', 398: '1', 468: '1', 124: '1', 236: '0', 377: '1', 83: '0'}
hint2 = {125: '0', 86: '1', 8: '0', 498: '1', 311: '0', 93: '0', 385: '0', 315: '1', 300: '1', 454: '0', 152: '0', 205: '0', 400: '1', 348: '1', 18: '1', 154: '0', 51: '1', 435: '0', 25: '1', 430: '0', 72: '1', 136: '0', 294: '0', 466: '0', 388: '0', 428: '0', 440: '1', 250: '1', 506: '0', 48: '0', 270: '1', 318: '0', 107: '0', 327: '1', 474: '0', 325: '0', 281: '0', 392: '0', 473: '1', 13: '1', 90: '0', 278: '0', 425: '0', 109: '1', 423: '1', 412: '1', 190: '1', 171: '0', 475: '1', 441: '1', 336: '0', 371: '0', 323: '0', 22: '1', 469: '0', 451: '0', 438: '0', 203: '1', 121: '0', 52: '1', 494: '1', 399: '0', 314: '0', 24: '1', 183: '0', 492: '1', 246: '1', 108: '1', 379: '0', 460: '1', 56: '0', 372: '1', 313: '1', 44: '0', 237: '1', 12: '0', 6: '0', 204: '1', 80: '1', 339: '1', 296: '0', 483: '0', 402: '0', 67: '0', 338: '1', 116: '0', 406: '1', 218: '0', 115: '0', 301: '0', 490: '1', 502: '0', 343: '1', 46: '1', 321: '0', 231: '1', 88: '0', 404: '1', 426: '0', 344: '0', 123: '1', 463: '0', 45: '1', 461: '1', 1: '0', 229: '0', 28: '1', 274: '1', 134: '1', 104: '1', 21: '0', 256: '0', 471: '1', 157: '0', 217: '1', 158: '0', 307: '1', 26: '0', 255: '0', 386: '1', 373: '0', 114: '1', 360: '0', 148: '1', 383: '1', 63: '0', 19: '1', 472: '0', 201: '1', 262: '1', 47: '0', 221: '0', 310: '0', 352: '1', 224: '1', 185: '0', 214: '1', 285: '1', 410: '0', 455: '0', 445: '0', 464: '0', 284: '1', 503: '1', 298: '1', 449: '0', 477: '0', 376: '0', 16: '0', 133: '0', 177: '1', 210: '0', 364: '1', 163: '1', 213: '1', 295: '1', 111: '1', 458: '0', 146: '0', 244: '0', 261: '1', 508: '1', 106: '0', 112: '1', 120: '0', 156: '1', 303: '0', 259: '1', 35: '0', 444: '0', 215: '1', 304: '0', 140: '0', 351: '0', 443: '0'}
hint3 = {891: '0', 74: '0', 129: '0', 477: '0', 880: '1', 57: '0', 473: '0', 289: '1', 361: '1', 1012: '0', 529: '0', 294: '1', 174: '1', 500: '0', 257: '1', 392: '1', 405: '1', 11: '0', 763: '1', 637: '1', 564: '0', 941: '1', 923: '1', 1014: '1', 670: '1', 558: '0', 304: '1', 444: '1', 716: '0', 208: '0', 130: '1', 634: '1', 661: '0', 862: '0', 412: '1', 796: '1', 761: '1', 113: '1', 752: '0', 818: '0', 797: '1', 390: '1', 337: '0', 133: '1', 367: '1', 470: '1', 345: '1', 170: '1', 312: '0', 624: '1', 53: '1', 75: '1', 281: '1', 522: '1', 100: '0', 554: '1', 583: '1', 16: '1', 836: '0', 715: '1', 450: '0', 484: '0', 876: '0', 165: '0', 842: '0', 62: '0', 442: '1', 927: '0', 586: '1', 399: '1', 227: '0', 886: '1', 663: '0', 947: '0', 906: '1', 377: '0', 246: '1', 365: '0', 177: '1', 59: '1', 63: '0', 936: '1', 144: '0', 416: '1', 228: '1', 366: '0', 117: '0', 78: '0', 717: '1', 14: '0', 800: '1', 47: '0', 80: '0', 34: '0', 662: '1', 970: '0', 986: '1', 287: '1', 597: '0', 783: '0', 805: '1', 112: '1', 671: '1', 540: '1', 153: '1', 577: '1', 543: '0', 414: '0', 123: '1', 626: '1', 452: '1', 810: '1', 30: '0', 905: '0', 602: '1', 537: '1', 374: '0', 408: '1', 434: '0', 137: '1', 532: '0', 397: '0', 333: '1', 258: '1', 359: '1', 134: '1', 322: '1', 653: '0', 1018: '0', 639: '1', 40: '1', 826: '1', 489: '0', 5: '0', 858: '0', 44: '1', 516: '0', 149: '0', 945: '0', 106: '1', 694: '0', 221: '0', 207: '0', 186: '1', 316: '0', 449: '1', 297: '1', 276: '0', 103: '0', 437: '0', 802: '0', 108: '1', 921: '1', 427: '0', 728: '1', 879: '0', 953: '0', 51: '1', 459: '0', 37: '0', 559: '0', 610: '1', 341: '0', 299: '0', 952: '0', 201: '0', 327: '0', 741: '1', 253: '1', 310: '1', 946: '1', 696: '0', 398: '1', 266: '1', 829: '0', 908: '0', 469: '0', 873: '1', 658: '0', 798: '1', 54: '0', 621: '0', 238: '0', 654: '1', 205: '0', 925: '0', 391: '1', 480: '0', 4: '0', 598: '0', 677: '0', 142: '1', 606: '0', 118: '0', 164: '0', 973: '1', 347: '0', 159: '1', 307: '1', 83: '1', 668: '1', 675: '0', 924: '1', 191: '1', 890: '0', 352: '1', 965: '1', 692: '1', 782: '1', 817: '1', 889: '1', 515: '1', 433: '0', 356: '0', 845: '1', 104: '0', 18: '0', 979: '0', 426: '0', 785: '1', 546: '0', 52: '0', 55: '0', 824: '1', 704: '1', 510: '1', 710: '0', 1022: '0', 647: '0', 465: '1', 245: '0', 850: '1', 657: '0', 1007: '0', 807: '1', 158: '1', 328: '0', 292: '1', 355: '1', 596: '0', 275: '1', 371: '0', 1004: '0', 594: '0', 384: '1', 446: '1', 7: '0', 994: '1', 616: '1', 317: '0', 305: '0', 151: '1', 400: '0', 900: '1', 203: '0', 563: '1', 745: '1', 536: '1', 726: '0', 751: '1', 402: '1', 116: '0', 781: '1', 988: '0', 768: '1', 688: '1', 954: '1', 976: '1', 868: '1', 723: '1', 131: '1', 794: '0', 513: '0', 914: '1', 641: '1', 319: '0', 629: '1', 620: '1', 711: '0', 601: '0', 531: '0', 393: '0', 168: '0', 132: '0', 17: '0', 950: '0', 488: '0', 679: '0', 568: '0', 43: '1', 545: '1', 217: '0', 680: '1', 501: '1', 1008: '0', 514: '0', 746: '0', 187: '0', 436: '1', 336: '1', 139: '1', 338: '0', 695: '1', 300: '0', 584: '1', 152: '0', 828: '1', 251: '0', 691: '1', 296: '1', 128: '0', 394: '1', 655: '1', 544: '1', 58: '0', 313: '1', 565: '1', 685: '1', 720: '0', 178: '1', 667: '0', 403: '1', 697: '1', 138: '1', 659: '0', 960: '0', 454: '0', 271: '0', 33: '0', 295: '0', 600: '0', 579: '1', 68: '1', 211: '1', 82: '1', 114: '1', 209: '0', 226: '0', 753: '0', 874: '0', 903: '1', 358: '0', 141: '0', 236: '1'}

def getnum(hint, bit):
    s = ['?'] * bit
    for tmp in hint.items():
        s[tmp[0]] = tmp[1]
    ss = ''
    return ss.join(s)

p_corr = getnum(hint1, 512)
q_corr = getnum(hint2, 512)
d_corr = getnum(hint3, 1024)
print('p = ', p_corr)
print('q = ', q_corr)
print('d = ', d_corr)

def get_s(x):
    if (x == '?'):
        return [0, 1]
    else:
        return [int(x)]

def update_3_k(total_len):
    cur_ans = [(0, 0, 0)] # d, p, q, k
    mod_num = 1
    cur_num = 1
    k = 1972411342
    for i in range(total_len):
        mod_num *= 2
        nxt_ans = []
        pset, qset, dset = set(), set(), set()
        for d, p, q in cur_ans:
            for cur_p in get_s(p_corr[- i - 1]):
                nxt_p = p + cur_p * cur_num
                for cur_q in get_s(q_corr[- i - 1]):
                    nxt_q = q + cur_q * cur_num
                    # check n = pq
                    nxt_n = nxt_p * nxt_q % mod_num
                    if (n % mod_num == nxt_n):
                        for cur_d in get_s(d_corr[- i -  1]):
                            nxt_d = d + cur_d * cur_num
                            # check phi
                            if (e * nxt_d % mod_num == (k * (nxt_p - 1) % mod_num * (nxt_q - 1) + 1) % mod_num):
                                # ok
                                nxt_ans.append((nxt_d, nxt_p, nxt_q))
                                pset.add(nxt_p)
                                qset.add(nxt_q)
                                dset.add(nxt_d)
        cur_ans = nxt_ans
        cur_num *= 2
        print(i, len(cur_ans), cur_ans[-1])

        print('number of p:', len(pset))
        print('number of q:', len(qset))
        print('number of d:', len(dset))

    return cur_ans

print(update_3_k(512))

分解之后就有了

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
from Crypto.Util.number import *

n = 73380160475470842653695210816683702314062827937540324056880543809752271506601290265975543542548117392788987830919581511428492717214125296973338501980504384307279414528799452106399062576988406269897425829853390463840834798274139351938197666753546672052277640048588091137812362810008344723302886421059831149393
e = 3116872133
c = 69574121902821459446683688068339366486115223765903849266663001038736496551168104587683366853482649748413400537793260948337629422998336301256862519087984048032673577462034223842650399943613576577927825123830629917138007035313624847266208032195071033675853881447717750353382112841885318776240405314057286867952

sol_list = [(7784868472609835283772369288450719687831855595004708832036599005696915154950995935461077898788049056940742159122868259556603407924884969346573163242612229, 5366239629682084697715680375675183284975073589647891453436177052547030069350226021009383094270291268448822558390838025112113425896384691203885755013446291, 7752453331027896289378165428906797427594364441082026942376869840211846057088210327758608246566696642059981985937946346433942230652922826983630336158233867), (7784868472609835283772369288450719687831855595004708832036599005696915154950995935461077898788049056940742159122868259556603407924884969346573163242612229, 12070143594653383247502692874778106348714756499944088142297957774407912084386999509410320243353742982293838487484081050538990367302357976177102579516488339, 1048549366056597739591152929803874363854681530785830253515089118350964042051436839357671097483244928214966056844703321007065289246949542010413511655191819), (1080964507638536733985356789347796624092172684708512143174818283836033139914222447060140749704597343095726230029625234129726466518911684373356338739570181, 2433281645007141582183862407317654444588962316393305402059147986732894187771637619833973091546281143641628089412544201487854764031271379028103394293365395, 7333459333217190130016477147712864736110634259188514649323008545095540931148411984733549674748980909944668490369618657344762421815049496672804284626793739), (1080964507638536733985356789347796624092172684708512143174818283836033139914222447060140749704597343095726230029625234129726466518911684373356338739570181, 9137185609978440131970874906420577508328645226689502090920928708593776202808411108234910240629732857486644018505787226914731705437244664001320218796407443, 629555368245891580229464648609941672370951348892317960461227823234658916111638496332612525665529196099652561276375631917885480409076211699587460123751691), (7919489015169557662429127754565768355549835525176027430319638757565113735078207393658554845331317666676034000955470463920503224389516790946448824722679301, 1802354785201290177466884084338089546571783201683146314594751112680946785671485962333750690939270314498621839653134209205738944793709927368604997459819155, 1938968369951956383692914074846193565952605977994141608508479664130135156436350531430956937073490508744644524832859364144490425643565423141221879893357835), (7919489015169557662429127754565768355549835525176027430319638757565113735078207393658554845331317666676034000955470463920503224389516790946448824722679301, 8506258750172588727253896583441012610311466111979343003456531834541828800708259450734687840022722028343637768746377234632615886199683212341821821962861203, 8642872334923254933479926573949116629692288888290338297370260385991017171473124019831894086156942222589660453926102389571367367049538708114438704396399883), (1215585050198259112642115255462845291810152614879830741457858035704231720041433905257617696247865952831018071862227438493626282983543505973232000219637253, 5573300765497645611722078615083483769925354838724756952079502768727692919129671049559277837298711903536443299768083411008357224334569900166039461242780307, 8223878337112548774118238292755183938208558706396826004316399090874712045533325676806835514339226490474346958357774700482187558211665377803612652864959755), (1215585050198259112642115255462845291810152614879830741457858035704231720041433905257617696247865952831018071862227438493626282983543505973232000219637253, 12277204730468944161509091114186406833665037749020953640941283490588574934166444537960214986382163617381459228861326436435234165740543185139256285745822355, 1519974372141250224331225793652260874468875796100629315454618369013830030496552188405898365255774776629331029264531675055310616805692092830395828361917707), (7734921245373868987957633397815241793128376406577702659406870494917041423397863464444263406492935867521512547965938537313634187669740963333142964343301637, 2039677277102509201846962486845547473896091736477285128799254489086577739322976113889959601594776791686842028494481573651372391063246536352650723217029779, 1257898532286632316712997010434751098568684325677402896642438617119803235501528656939875312897703963741941819407675370807672885257529089521223286466966795), (7734921245373868987957633397815241793128376406577702659406870494917041423397863464444263406492935867521512547965938537313634187669740963333142964343301637, 8743581242073807751633974985948470537635774646773481817661035210947459754359749602290896750678228505531857957587724599078249332469219821325867547720071827, 7961802497257930866500009509537674162308367235973599585504219338980685250538302145340812461981155677586957748500918396234549826663502374494440110970008843), (1031017280402570438170620898712318729388693496281505970545089773056159408361089976043326257409484153676496618872695511886757246263767678359926139840259589, 5810623257398864636102157017590941697249663373518895766284006145133323872781161201115486747954218380724663488609430775453990670604106509150085186999990931, 7542808499447224707138321228343741470824637054080087292450358043864380124598503802315753890163439945471644252932590707145370017825629044183614059438568715), (1031017280402570438170620898712318729388693496281505970545089773056159408361089976043326257409484153676496618872695511886757246263767678359926139840259589, 12514527222370163185889169516693864760989346283815092455145786866994205887817934689516423897037670094569679417702673800880867612010079794123302011503032979, 838904534475926157351308729240818407084954143783890603588577322003498109561730313914816741079988231626628323839347681718493076419655759210397234935526667), (7934321504151848016580521002574844336171226047598370838640120531140912301800737265546469106621426048099833677640004660227767453182195309874035552908895749, 5362971084215426487776063906406933038339571667412402912065006500619578380006904603808786641086852920091627867874069854414757781438101918802034898550045331, 1748900714192807249109317611158943830937830460558493754638072787623072613667437058549182782275056393635453630420046451180946795578565976628109405510595851), (7934321504151848016580521002574844336171226047598370838640120531140912301800737265546469106621426048099833677640004660227767453182195309874035552908895749, 12066875049186725037563076405509856102079254577708599600926787222480460395043678092209723790170304633936643796967312879841634722844075203775251723053087379, 8452804679164105798896330110261866894677513370854690443499853509483954628704210546950119931358508107480469559513289476607823736984539261601326230013637899), (1230417539180549466793508503471921272431543137302174149778339809280030286763963777145531957537974334254817748546761634800890511776222024900818728405853701, 2430013099540483372244245938049404197953460394157816860687977434805442498428316202633376638362842795284433398895776030790499119572988606626252537829964435, 1329906716382101089747629329965011139454100278664981461584211492506767487727638715524124210457340661520140134851718762091766986740692646317283353979155723), (1230417539180549466793508503471921272431543137302174149778339809280030286763963777145531957537974334254817748546761634800890511776222024900818728405853701, 9133917064511781922031258437152327261693143304454013549549758156666324513465089691034313787446294509129449327989019056217376060978961891599469362333006483, 8033810681353399639534641829067934203193783188961178150445992214367649502764412203925061359540792375365156063944961787518643928146665931290500178482197771)]

for p, q, d in sol_list:
    if (n % p == 0):
        q = n // p
        d = inverse(e, (p-1)*(q-1))
        m = pow(c, d, n)
        print(long_to_bytes(m))
    p, q = q, p
    if (n % p == 0):
        q = n // p
        d = inverse(e, (p-1)*(q-1))
        m = pow(c, d, n)
        print(long_to_bytes(m))

common_rsa

维纳的common prime rsa，用john and may的方法copper能出，代码直接用github的：https://github.com/jvdsn/crypto-attacks/blob/5c7989ceac599f1f8e016b5afb0d2966759cd470/attacks/rsa/wiener_attack_common_prime.py

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
import logging
import os
import sys
from math import log
from math import sqrt

from sage.all import RR
from sage.all import ZZ
from Crypto.Util.number import long_to_bytes
path = os.path.dirname(os.path.dirname(os.path.dirname(os.path.realpath(os.path.abspath(__file__)))))
if sys.path[1] != path:
    sys.path.insert(1, path)

from shared.small_roots import jochemsz_may_integer

def attack(N, e, delta=0.25, m_start=1):
    """
    Recovers the prime factors of a modulus and the private exponent if the private exponent is too small (Common Prime RSA version).
    More information: Jochemsz E., May A., "A Strategy for Finding Roots of Multivariate Polynomials with New Applications in Attacking RSA Variants" (Section 5)
    :param N: the modulus
    :param e: the public exponent
    :param delta: a predicted bound on the private exponent (d < N^delta) (default: 0.25)
    :param m_start: the m value to start at for the small roots method (default: 1)
    :return: a tuple containing the prime factors of the modulus and the private exponent
    """
    gamma = 1 - log(e, N)
    assert delta <= 1 / 4 * (4 + 4 * gamma - sqrt(13 + 20 * gamma + 4 * gamma ** 2)), "Bound check failed."

    x, y, z = ZZ["x, y, z"].gens()

    f = e ** 2 * x ** 2 + e * x * (y + z - 2) - (y + z - 1) - (N - 1) * y * z

    X = int(RR(N) ** delta)
    Y = int(RR(N) ** (delta + 1 / 2 - gamma))
    Z = int(RR(N) ** (delta + 1 / 2 - gamma))
    W = int(RR(N) ** (2 + 2 * delta - 2 * gamma))

    m = m_start
    while True:
        for t in range(m + 1):
            logging.info(f"Trying m = {m}, t = {t}...")
            strategy = jochemsz_may_integer.ExtendedStrategy([t, 0, 0])
            for x0, y0, z0 in jochemsz_may_integer.integer_multivariate(f, m, W, [X, Y, Z], strategy):
                d = x0
                ka = y0
                kb = z0
                if pow(pow(2, e, N), d, N) == 2:
                    p = (e * d - 1) // kb + 1
                    q = (e * d - 1) // ka + 1
                    return p, q, d

        m += 1

n = 253784908428481171520644795825628119823506176672683456544539675613895749357067944465796492899363087465652749951069021248729871498716450122759675266109104893465718371075137027806815473672093804600537277140261127375373193053173163711234309619016940818893190549811778822641165586070952778825226669497115448984409
e = 31406775715899560162787869974700016947595840438708247549520794775013609818293759112173738791912355029131497095419469938722402909767606953171285102663874040755958087885460234337741136082351825063419747360169129165
c = 97724073843199563126299138557100062208119309614175354104566795999878855851589393774478499956448658027850289531621583268783154684298592331328032682316868391120285515076911892737051842116394165423670275422243894220422196193336551382986699759756232962573336291032572968060586136317901595414796229127047082707519
delta = 0.132
print(delta)
p, q, d = attack(n, e, delta)
print(long_to_bytes(pow(c, d, n)))

babyDLP

CryptoCTF （这比赛哥们是第十一名）原题sidestep，参数交互都没改，直接用原来的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
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
#!/usr/bin/env python3

from Crypto.Util.number import *
import random, sys
from flag import flag

def pow_d(g, e, n):
    t, r = 0, 1
    for _ in bin(e)[2:]:
        if r == 4: t += 1
        r = pow(r, 2, n)
        if _ == '1': r = r * g % n
    return t, r

def ts(m, p):
    m = m % p
    return pow(m, (p - 1) // 2, p) == 1

def die(*args):
    pr(*args)
    quit()

def pr(*args):
    s = " ".join(map(str, args))
    sys.stdout.write(s + "\n")
    sys.stdout.flush()

def sc():
    return sys.stdin.readline().strip()

def main():
    border = "|"
    pr(border*72)
    pr(border, "Hi all cryptographers! Welcome to the Sidestep task, we do powing!!!", border)
    pr(border, "You should solve a DLP challenge in some special way to get the flag", border)

    p = 2 ** 1024 - 2 ** 234 - 2 ** 267 - 2 ** 291 - 2 ** 403 - 1
    s = random.randint(2, (p - 1) // 2)

    while True:
        pr("| Options: \n|\t[T]ry the magic machine \n|\t[Q]uit")
        ans = sc().lower()

        if ans == 't':
            pr(border, "please send your desired integer: ")
            g = sc()
            try:
                g = int(g)
            except:
                die(border, "The given input is not integer!")
            if ts(g, p):
                t, r = pow_d(g, s, p)
                if r == 4:
                    die(border, f'Great! you got the flag: {flag}')
                else:
                    pr(border, f"t, r = {t, r}")
            else:
                pr(border, "The given base is NOT valid!!!")
        elif ans == 'q':
            die(border, "Quitting ...")
        else:
            die(border, "Bye bye ...")

if __name__ == "__main__":
    main()