Writeup for Crypto Problems in De1CTF 2019

xorz

Problem

题目描述:

crypto_xorz.py文件:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
from itertools import *
from data import flag,plain

key=flag.strip("de1ctf{").strip("}")
assert(len(key)<38)
salt="WeAreDe1taTeam"
ki=cycle(key)
si=cycle(salt)
cipher = ''.join([hex(ord(p) ^ ord(next(ki)) ^ ord(next(si)))[2:].zfill(2) for p in plain])
print cipher
# output:
# 49380d773440222d1b421b3060380c3f403c3844791b202651306721135b6229294a3c3222357e766b2f15561b35305e3c3b670e49382c295c6c170553577d3a2b791470406318315d753f03637f2b614a4f2e1c4f21027e227a4122757b446037786a7b0e37635024246d60136f7802543e4d36265c3e035a725c6322700d626b345d1d6464283a016f35714d434124281b607d315f66212d671428026a4f4f79657e34153f3467097e4e135f187a21767f02125b375563517a3742597b6c394e78742c4a725069606576777c314429264f6e330d7530453f22537f5e3034560d22146831456b1b72725f30676d0d5c71617d48753e26667e2f7a334c731c22630a242c7140457a42324629064441036c7e646208630e745531436b7c51743a36674c4f352a5575407b767a5c747176016c0676386e403a2b42356a727a04662b4446375f36265f3f124b724c6e346544706277641025063420016629225b43432428036f29341a2338627c47650b264c477c653a67043e6766152a485c7f33617264780656537e5468143f305f4537722352303c3d4379043d69797e6f3922527b24536e310d653d4c33696c635474637d0326516f745e610d773340306621105a7361654e3e392970687c2e335f3015677d4b3a724a4659767c2f5b7c16055a126820306c14315d6b59224a27311f747f336f4d5974321a22507b22705a226c6d446a37375761423a2b5c29247163046d7e47032244377508300751727126326f117f7a38670c2b23203d4f27046a5c5e1532601126292f577776606f0c6d0126474b2a73737a41316362146e581d7c1228717664091c

Analysis

就是一个stream cipher

keyflag,长度小于38。还加了salt,不过这里的salt已经给了,可以直接异或回去得到key^data

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
from itertools import cycle

output = '49380d773440222d1b421b3060380c3f403c3844791b202651306721135b6229294a3c3222357e766b2f15561b35305e3c3b670e49382c295c6c170553577d3a2b791470406318315d753f03637f2b614a4f2e1c4f21027e227a4122757b446037786a7b0e37635024246d60136f7802543e4d36265c3e035a725c6322700d626b345d1d6464283a016f35714d434124281b607d315f66212d671428026a4f4f79657e34153f3467097e4e135f187a21767f02125b375563517a3742597b6c394e78742c4a725069606576777c314429264f6e330d7530453f22537f5e3034560d22146831456b1b72725f30676d0d5c71617d48753e26667e2f7a334c731c22630a242c7140457a42324629064441036c7e646208630e745531436b7c51743a36674c4f352a5575407b767a5c747176016c0676386e403a2b42356a727a04662b4446375f36265f3f124b724c6e346544706277641025063420016629225b43432428036f29341a2338627c47650b264c477c653a67043e6766152a485c7f33617264780656537e5468143f305f4537722352303c3d4379043d69797e6f3922527b24536e310d653d4c33696c635474637d0326516f745e610d773340306621105a7361654e3e392970687c2e335f3015677d4b3a724a4659767c2f5b7c16055a126820306c14315d6b59224a27311f747f336f4d5974321a22507b22705a226c6d446a37375761423a2b5c29247163046d7e47032244377508300751727126326f117f7a38670c2b23203d4f27046a5c5e1532601126292f577776606f0c6d0126474b2a73737a41316362146e581d7c1228717664091c'
salt="WeAreDe1taTeam"

si = cycle(salt)
output = bytes.fromhex(output)

output = b''.join([bytes([o ^ ord(next(si))]) for o in output])
# b'\x1e]L\x05Q\x04G\x1co#OU\x01U[Z\x01N]\x00\x1c*TG\x05U\x06LD>#[L\x0eY\x03VT*\x13\nBB3ZGU\x1aY\n\x13o\x1d]MD\x0b\tVw6\x13\x18\x0b_\x18@\x15!\x0eOT\x1c\x07ZG\x06N_\x00\x1e*Oq\x18DC\x0cG>$\x13\x01\x1a\x10\x05V\x15=\x1eOE\x06\x14A\x15\x19\x01G\n\x19o\x03[\x0cDC\x18[2.\x13\x08\x06C\x1dZ\x07*F8Y\x01U\\[U\nT\x1c\x1a&\x00VM_\x05LE>2DL\nCMC\x18*\x0b\x1cT\nUAZU\n^\x1b\x0fa:\\\x1f\x10\x02\x1eVw:Z\x02\x06\x10\x08R\x06<J\x18X\x1a\x1d\x15A\x1d\x17\x11\x1b\x05!\x13F\x08P\x10LG"9VL\x07U\x01Z\x13\'\x1e\nUU;ZGU\x1aT\x01\x0e*\x06\x13\x0bU\x06\x00Z90\x13\x18\x0c\x10\x0fR\x07*J\x1b^\x1b\x16]P\x06NA\x1d\x05!\x11\x1f#_\x11LG6$G\tO\x10\x03\\\x06o\x19\x02T\x02\x19\x19\x15\x11\x0bB\x06\x18*TG\x02\x10\x01\t\x13>9E\x05\x17U\tg\x1bo\x0b\x01HN\x06P[\x06\x1bP\x03J)\x11R\x1eDC\x1bZ#?\x13\x18\x0bU\x08\x13\x15#\x05\x01T@7@AU\x03HO\x0c&\x02VMG\n\x18@{w]\x03\x11\x10\x00JT)\x03\x19TN\x06P[\x06\x0bBO\t.\x1aw\x04C\x10\x19R32\x13\x03\rUMU\x1b \x06\x06B\x06U]P\x14\x1cEO\x0c=\x1b^MC\x06\x1eE>9TL\x17X\x08VX\x18\x02\x00\x11\x02\x10TC\x10\x1d\x11\x1a\x04<\x03R\x14U\x07LG?2\x13\x00\n[\x08]\x11<\x19O^\x08UT\x15\x18\x0f_C>\'\r\x13\x1dB\x0c\x19Ww?V\r\x11D\r@T<\x06\x0eG\x0bUT[\x11NG\x0e\x19<\x15_MG\x11\tG4?\x13\x18\x0c\x10\x0fVZ\x00\x04\x03HN\x18L\x15\x05\x02P\x08\x1f*TG\x05E\x10LU6%\x13%CS\x02F\x1a;J\x02HN\x12T\\\x1bBe\x07\x0b;T@\x05UC\x18[6#\x13\x01\x02[\x08@T"\x0fOB\x07\x1b\x15T\x02\x0fC\x0b\x19o\x19VM@\x02\x05]y'

本来想着一个一个单词异或上去看看能不能得到一些有意义的字符串,不过这样效率太低了。

在网上找到一篇很好的讲解stream cipher文章

里面的核心思路就是:

  1. 根据汉明距离估算出key的可能长度。
  2. 再根据字频分析爆破出key

稍微修改了一下里面的脚本,算出了key

  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
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
import base64
import string


def bxor(a, b):     # xor two byte strings of different lengths
    if len(a) > len(b):
        return bytes([x ^ y for x, y in zip(a[:len(b)], b)])
    else:
        return bytes([x ^ y for x, y in zip(a, b[:len(a)])])


def hamming_distance(b1, b2):
    differing_bits = 0
    for byte in bxor(b1, b2):
        differing_bits += bin(byte).count("1")
    return differing_bits


def score(s):
    freq = {}
    freq[' '] = 700000000
    freq['e'] = 390395169
    freq['t'] = 282039486
    freq['a'] = 248362256
    freq['o'] = 235661502
    freq['i'] = 214822972
    freq['n'] = 214319386
    freq['s'] = 196844692
    freq['h'] = 193607737
    freq['r'] = 184990759
    freq['d'] = 134044565
    freq['l'] = 125951672
    freq['u'] = 88219598
    freq['c'] = 79962026
    freq['m'] = 79502870
    freq['f'] = 72967175
    freq['w'] = 69069021
    freq['g'] = 61549736
    freq['y'] = 59010696
    freq['p'] = 55746578
    freq['b'] = 47673928
    freq['v'] = 30476191
    freq['k'] = 22969448
    freq['x'] = 5574077
    freq['j'] = 4507165
    freq['q'] = 3649838
    freq['z'] = 2456495
    score = 0
    string=bytes.decode(s)
    for c in string.lower():
        if c in freq:
            score += freq[c]
    return score


def break_single_key_xor(b1):
    max_score = 0
    english_plaintext = 0
    key = 0

    for i in range(0,256):
        b2 = [i] * len(b1)
        try:
            plaintext = bxor(b1, b2)
            pscore = score(plaintext)
        except Exception:
            continue
        if pscore > max_score or not max_score:
            max_score = pscore
            english_plaintext = plaintext
            key = chr(i)
    return key



b = b'\x1e]L\x05Q\x04G\x1co#OU\x01U[Z\x01N]\x00\x1c*TG\x05U\x06LD>#[L\x0eY\x03VT*\x13\nBB3ZGU\x1aY\n\x13o\x1d]MD\x0b\tVw6\x13\x18\x0b_\x18@\x15!\x0eOT\x1c\x07ZG\x06N_\x00\x1e*Oq\x18DC\x0cG>$\x13\x01\x1a\x10\x05V\x15=\x1eOE\x06\x14A\x15\x19\x01G\n\x19o\x03[\x0cDC\x18[2.\x13\x08\x06C\x1dZ\x07*F8Y\x01U\\[U\nT\x1c\x1a&\x00VM_\x05LE>2DL\nCMC\x18*\x0b\x1cT\nUAZU\n^\x1b\x0fa:\\\x1f\x10\x02\x1eVw:Z\x02\x06\x10\x08R\x06<J\x18X\x1a\x1d\x15A\x1d\x17\x11\x1b\x05!\x13F\x08P\x10LG"9VL\x07U\x01Z\x13\'\x1e\nUU;ZGU\x1aT\x01\x0e*\x06\x13\x0bU\x06\x00Z90\x13\x18\x0c\x10\x0fR\x07*J\x1b^\x1b\x16]P\x06NA\x1d\x05!\x11\x1f#_\x11LG6$G\tO\x10\x03\\\x06o\x19\x02T\x02\x19\x19\x15\x11\x0bB\x06\x18*TG\x02\x10\x01\t\x13>9E\x05\x17U\tg\x1bo\x0b\x01HN\x06P[\x06\x1bP\x03J)\x11R\x1eDC\x1bZ#?\x13\x18\x0bU\x08\x13\x15#\x05\x01T@7@AU\x03HO\x0c&\x02VMG\n\x18@{w]\x03\x11\x10\x00JT)\x03\x19TN\x06P[\x06\x0bBO\t.\x1aw\x04C\x10\x19R32\x13\x03\rUMU\x1b \x06\x06B\x06U]P\x14\x1cEO\x0c=\x1b^MC\x06\x1eE>9TL\x17X\x08VX\x18\x02\x00\x11\x02\x10TC\x10\x1d\x11\x1a\x04<\x03R\x14U\x07LG?2\x13\x00\n[\x08]\x11<\x19O^\x08UT\x15\x18\x0f_C>\'\r\x13\x1dB\x0c\x19Ww?V\r\x11D\r@T<\x06\x0eG\x0bUT[\x11NG\x0e\x19<\x15_MG\x11\tG4?\x13\x18\x0c\x10\x0fVZ\x00\x04\x03HN\x18L\x15\x05\x02P\x08\x1f*TG\x05E\x10LU6%\x13%CS\x02F\x1a;J\x02HN\x12T\\\x1bBe\x07\x0b;T@\x05UC\x18[6#\x13\x01\x02[\x08@T"\x0fOB\x07\x1b\x15T\x02\x0fC\x0b\x19o\x19VM@\x02\x05]y'


normalized_distances = []


for KEYSIZE in range(2, 38):
    # 我们取其中前6段计算平局汉明距离
    b1 = b[: KEYSIZE]
    b2 = b[KEYSIZE: KEYSIZE * 2]
    b3 = b[KEYSIZE * 2: KEYSIZE * 3]
    b4 = b[KEYSIZE * 3: KEYSIZE * 4]
    b5 = b[KEYSIZE * 4: KEYSIZE * 5]
    b6 = b[KEYSIZE * 5: KEYSIZE * 6]
    b7 = b[KEYSIZE * 6: KEYSIZE * 7]

    normalized_distance = float(
        hamming_distance(b1, b2) +
        hamming_distance(b2, b3) +
        hamming_distance(b3, b4) +
        hamming_distance(b4, b5) +
        hamming_distance(b5, b6)
    ) / (KEYSIZE * 5)
    normalized_distances.append(
        (KEYSIZE, normalized_distance)
    )
normalized_distances = sorted(normalized_distances, key=lambda x: x[1])


for KEYSIZE, _ in normalized_distances[:5]:
    block_bytes = [[] for _ in range(KEYSIZE)]
    for i, byte in enumerate(b):
        block_bytes[i % KEYSIZE].append(byte)
    keys = ''

    for bbytes in block_bytes:
        keys += break_single_key_xor(bbytes)
    key = bytearray(keys * len(b), "utf-8")
    plaintext = bxor(b, key)
    print("keysize:", KEYSIZE)
    print("key is:", keys, "n")
    s = bytes.decode(plaintext)
    print(s)
# keysize: 30
# key is: W3lc0m3tOjo1nu55un1ojOt3m0cl3W
# ...

得到flag:de1ctf{W3lc0m3tOjo1nu55un1ojOt3m0cl3W}

Babylfsr

Problem

描述:

task.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
import hashlib
from secret import KEY,FLAG,MASK

assert(FLAG=="de1ctf{"+hashlib.sha256(hex(KEY)[2:].rstrip('L')).hexdigest()+"}")
assert(FLAG[7:11]=='1224')

LENGTH = 256

assert(KEY.bit_length()==LENGTH)
assert(MASK.bit_length()==LENGTH)

def pad(m):
    pad_length = 8 - len(m)
    return pad_length*'0'+m

class lfsr():
    def __init__(self, init, mask, length):
        self.init = init
        self.mask = mask
        self.lengthmask = 2**(length+1)-1

    def next(self):
        nextdata = (self.init << 1) & self.lengthmask
        i = self.init & self.mask & self.lengthmask
        output = 0
        while i != 0:
            output ^= (i & 1)
            i = i >> 1
        nextdata ^= output
        self.init = nextdata
        return output


if __name__=="__main__":
    l = lfsr(KEY,MASK,LENGTH)
    r = ''
    for i in range(63):
        b = 0
        for j in range(8):
            b = (b<<1)+l.next()
        r += pad(bin(b)[2:])
    with open('output','w') as f:
        f.write(r)

output文件:

001010010111101000001101101111010000001111011001101111011000100001100011111000010001100101110110011000001100111010111110000000111011000110111110001110111000010100110010011111100011010111101101101001110000010111011110010110010011101101010010100101011111011001111010000000001011000011000100000101111010001100000011010011010111001010010101101000110011001110111010000011010101111011110100011110011010000001100100101000010110100100100011001000101010001100000010000100111001110110101000000101011100000001100010

Analysis

题目给了一个长为256的lfsr的504个输出,没告诉我们mask,要求初始状态,也就是key

没有mask,并不知道怎么搞。

后来,在ctfwiki上找到了一个可行的思路:

lfsr的每一次操作,都可以用一个变换矩阵来表示:

然后只要我们知道了2n个输出比特,就能直接推算出mask,也就是解出cn, cn-1, ..., c1

根据这个思路就可以写脚本了。不过需要注意以下几点:

  • 这里我们知道了输出的504个比特,虽然没到512,但是可以逐一尝试后8位。
  • 矩阵是要运算在GF(2)上的,不然求出的逆矩阵就全是各种各样的小数了。
  • 要注意恰当处理逆矩阵可能没解的情况。

sage脚本如下:

 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
import hashlib

out = '001010010111101000001101101111010000001111011001101111011000100001100011111000010001100101110110011000001100111010111110000000111011000110111110001110111000010100110010011111100011010111101101101001110000010111011110010110010011101101010010100101011111011001111010000000001011000011000100000101111010001100000011010011010111001010010101101000110011001110111010000011010101111011110100011110011010000001100100101000010110100100100011001000101010001100000010000100111001110110101000000101011100000001100010'
N = 256
F = GF(2)


for time in range(2**8):  # 逐一尝试后8位
    guess = out + bin(time)[2:].zfill(8)

    # 求逆矩阵
    Sn = [vector(F, N) for j in range(N+1)]
    for j in range(N + 1):
        Sn[j] = list(map(int, guess[j:j+256]))
    X = Matrix(F, Sn[:256])
    try:
        invX = X ^ -1
    except:
        # print time
        continue
    Y = vector(F, Sn[-1])

    Cn = Y * invX

    # 生成变换矩阵
    R = [vector(F, N) for i in range(N)]
    for i in range(N):
        R[i][N-1] = Cn[i]
    for i in range(N-1):
        R[i + 1][i] = 1
    M = Matrix(F, R)

    M = M ^ N

    try:
        Y = vector(F, Sn[0])
        key = M.solve_left(Y)
        # print '!   ', time
        KEY = int(''.join(map(str, list(key))), 2)
        # sha256验证
        if hashlib.sha256(hex(KEY)[2:].rstrip('L')).hexdigest()[:4] == '1224': #
            # print KEY
            print hashlib.sha256(hex(KEY)[2:].rstrip('L')).hexdigest()
    except:
        continue

不到1分钟应该就能跑出来,得到输出1224473d5e349dbf2946353444d727d8fa91da3275ed3ac0dedeb7e6a9ad8619

所以flag:de1ctf{1224473d5e349dbf2946353444d727d8fa91da3275ed3ac0dedeb7e6a9ad8619}

Baby RSA

Problem

 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
import binascii
from data import e1,e2,p,q1p,q1q,hint,flag,q2

n =  [20129615352491765499340112943188317180548761597861300847305827141510465619670536844634558246439230371658836928103063432870245707180355907194284861510906071265352409579441048101084995923962148527097370705452070577098780246282820065573711015664291991372085157016901209114191068574208680397710042842835940428451949500607613634682684113208766694028789275748528254287705759528498986306494267817198340658241873024800336013946294891687591013414935237821291805123285905335762719823771647853378892868896078424572232934360940672962436849523915563328779942134504499568866135266628078485232098208237036724121481835035731201383423L, 31221650155627849964466413749414700613823841060149524451234901677160009099014018926581094879840097248543411980533066831976617023676225625067854003317018794041723612556008471579060428898117790587991055681380408263382761841625714415879087478072771968160384909919958010983669368360788505288855946124159513118847747998656422521414980295212646675850690937883764000571667574381419144372824211798018586804674824564606122592483286575800685232128273820087791811663878057827386379787882962763290066072231248814920468264741654086011072638211075445447843691049847262485759393290853117072868406861840793895816215956869523289231421L, 29944537515397953361520922774124192605524711306753835303703478890414163510777460559798334313021216389356251874917792007638299225821018849648520673813786772452822809546571129816310207232883239771324122884804993418958309460009406342872173189008449237959577469114158991202433476710581356243815713762802478454390273808377430685157110095496727966308001254107517967559384019734279861840997239176254236069001453544559786063915970071130087811123912044312219535513880663913831358790376650439083660611831156205113873793106880255882114422025746986403355066996567909581710647746463994280444700922867397754748628425967488232530303L, 25703437855600135215185778453583925446912731661604054184163883272265503323016295700357253105301146726667897497435532579974951478354570415554221401778536104737296154316056314039449116386494323668483749833147800557403368489542273169489080222009368903993658498263905567516798684211462607069796613434661148186901892016282065916190920443378756167250809872483501712225782004396969996983057423942607174314132598421269169722518224478248836881076484639837343079324636997145199835034833367743079935361276149990997875905313642775214486046381368619638551892292787783137622261433528915269333426768947358552919740901860982679180791L]
c =  [19131432661217908470262338421299691998526157790583544156741981238822158563988520225986915234570037383888112724408392918113942721994125505014727545946133307329781747600302829588248042922635714391033431930411180545085316438084317927348705241927570432757892985091396044950085462429575440060652967253845041398399648442340042970814415571904057667028157512971079384601724816308078631844480110201787343583073815186771790477712040051157180318804422120472007636722063989315320863580631330647116993819777750684150950416298085261478841177681677867236865666207391847046483954029213495373613490690687473081930148461830425717614569L, 15341898433226638235160072029875733826956799982958107910250055958334922460202554924743144122170018355117452459472017133614642242411479849369061482860570279863692425621526056862808425135267608544855833358314071200687340442512856575278712986641573012456729402660597339609443771145347181268285050728925993518704899005416187250003304581230701444705157412790787027926810710998646191467130550713600765898234392350153965811595060656753711278308005193370936296124790772689433773414703645703910742193898471800081321469055211709339846392500706523670145259024267858368216902176489814789679472227343363035428541915118378163012031L, 18715065071648040017967211297231106538139985087685358555650567057715550586464814763683688299037897182845007578571401359061213777645114414642903077003568155508465819628553747173244235936586812445440095450755154357646737087071605811984163416590278352605433362327949048243722556262979909488202442530307505819371594747936223835233586945423522256938701002370646382097846105014981763307729234675737702252155130837154876831885888669150418885088089324534892506199724486783446267336789872782137895552509353583305880144947714110009893134162185382309992604435664777436197587312317224862723813510974493087450281755452428746194446L, 2282284561224858293138480447463319262474918847630148770112472703128549032592187797289965592615199709857879008271766433462032328498580340968871260189669707518557157836592424973257334362931639831072584824103123486522582531666152363874396482744561758133655406410364442174983227005501860927820871260711861008830120617056883514525798709601744088135999465598338635794275123149165498933580159945032363880613524921913023341209439657145962332213468573402863796920571812418200814817086234262280338221161622789516829363805084715652121739036183264026120868756523770196284142271849879003202190966150390061195469351716819539183797L]
f=lambda m,e,n,c:pow(m,e,n)==c
assert(sum(map(f,[p]*4,[4]*4,n,c))==4)

ee1 = 42
ee2 = 3
ce1 =  45722651786340123946960815003059322528810481841378247280642868553607692149509126962872583037142461398806689489141741494974836882341505234255325683219092163052843461632338442529011502378931140356111756932712822516814023166068902569458299933391973504078898958921809723346229893913662577294963528318424676803942288386430172430880307619748186863890050113934573820505570928109017842647598266634344447182347849367714564686341871007505886728393751147033556889217604647355628557502208364412269944908011305064122941446516990168924709684092200183860653173856272384
ce2 =  13908468332333567158469136439932325992349696889129103935400760239319454409539725389747059213835238373047899198211128689374049729578146875309231962936554403287882999967840346216695208424582739777034261079550395918048421086843927009452479936045850799096750074359160775182238980989229190157551197830879877097703347301072427149474991803868325769967332356950863518504965486565464059770451458557744949735282131727956056279292800694203866167270268988437389945703117070604488999247750139568614939965885211276821987586882908159585863514561191905040244967655444219603287214405014887994238259270716355378069726760953320025828158
tmp =  864078778078609835167779565982540757684070450697854309005171742813414963447462554999012718960925081621571487444725528982424037419052194840720949809891134854871222612682162490991065015935449289960707882463387
n  =  15911581555796798614711625288508309704791837516232122410440958830726078821069050404012820896260071751380436992710638364294658173571101596931605797509712839622479368850251206419748090059752427303611760004621378226431226983665746837779056271530181865648115862947527212787824629516204832313026456390047768174765687040950636530480549014401279054346098030395100387004111574278813749630986724706263655166289586230453975953773791945408589484679371854113457758157492241225180907090235116325034822993748409011554673180494306003272836905082473475046277554085737627846557240367696214081276345071055578169299060706794192776825039
assert(pow(e1,ee1,n)==ce1)
assert(pow(e2+tmp,ee2,n)==ce2)

e = 46531
n = 16278524034278364842964386062476113517067911891699789991355982121084973951738324063305190630865511554888330215827724887964565979607808294168282995825864982603759381323048907814961279012375346497781046417204954101076457350988751188332353062731641153547102721113593787978587135707313755661153376485647168543680503160420091693269984008764444291289486805840439906620313162344057956594836197521501755378387944609246120662335790110901623740990451586621846212047950084207251595169141015645449217847180683357626383565631317253913942886396494396189837432429078251573229378917400841832190737518763297323901586866664595327850603
c = 14992132140996160330967307558503117255626925777426611978518339050671013041490724616892634911030918360867974894371539160853827180596100892180735770688723270765387697604426715670445270819626709364566478781273676115921657967761494619448095207169386364541164659123273236874649888236433399127407801843412677293516986398190165291102109310458304626261648346825196743539220198199366711858135271877662410355585767124059539217274691606825103355310348607611233052725805236763220343249873849646219850954945346791015858261715967952461021650307307454434510851869862964236227932964442289459508441345652423088404453536608812799355469
hint=int(binascii.hexlify(hint),16)
assert(q1p*q1q==n)
assert(q1p<q1q)
assert(c==pow(hint,e,n))

flag=int(binascii.hexlify(flag),16)
q1=q1p
c1 =  262739975753930281690942784321252339035906196846340713237510382364557685379543498765074448825799342194332681181129770046075018122033421983227887719610112028230603166527303021036386350781414447347150383783816869784006598225583375458609586450854602862569022571672049158809874763812834044257419199631217527367046624888837755311215081173386523806086783266198390289097231168172692326653657393522561741947951887577156666663584249108899327053951891486355179939770150550995812478327735917006194574412518819299303783243886962455399783601229227718787081785391010424030509937403600351414176138124705168002288620664809270046124
c2 =  7395591129228876649030819616685821899204832684995757724924450812977470787822266387122334722132760470911599176362617225218345404468270014548817267727669872896838106451520392806497466576907063295603746660003188440170919490157250829308173310715318925771643105064882620746171266499859049038016902162599261409050907140823352990750298239508355767238575709803167676810456559665476121149766947851911064706646506705397091626648713684511780456955453552020460909638016134124590438425738826828694773960514221910109473941451471431637903182205738738109429736425025621308300895473186381826756650667842656050416299166317372707709596
assert(c1==pow(flag,e1,p*q1))
assert(c2==pow(flag,e2,p*q2))

大致分析后,感觉可以分成4段。

第一段

1
2
3
4
n =  ...
c =  ...
f=lambda m,e,n,c:pow(m,e,n)==c
assert(sum(map(f,[p]*4,[4]*4,n,c))==4)

给出了对同一个明文p用同一个加密指数e=4加密4次后的c以及相应的模数n。 可以用中国剩余定理(CRT)求出p**4,再开4次根就可以得到p:

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

def CRT(mi, ai):
    assert (isinstance(mi, list) and isinstance(ai, list))
    M = reduce(lambda x, y: x * y, mi)
    ai_ti_Mi = [a * (M / m) * inverse(M / m, m) for (m, a) in zip(mi, ai)]
    return reduce(lambda x, y: x + y, ai_ti_Mi) % M

n =  [20129615352491765499340112943188317180548761597861300847305827141510465619670536844634558246439230371658836928103063432870245707180355907194284861510906071265352409579441048101084995923962148527097370705452070577098780246282820065573711015664291991372085157016901209114191068574208680397710042842835940428451949500607613634682684113208766694028789275748528254287705759528498986306494267817198340658241873024800336013946294891687591013414935237821291805123285905335762719823771647853378892868896078424572232934360940672962436849523915563328779942134504499568866135266628078485232098208237036724121481835035731201383423, 31221650155627849964466413749414700613823841060149524451234901677160009099014018926581094879840097248543411980533066831976617023676225625067854003317018794041723612556008471579060428898117790587991055681380408263382761841625714415879087478072771968160384909919958010983669368360788505288855946124159513118847747998656422521414980295212646675850690937883764000571667574381419144372824211798018586804674824564606122592483286575800685232128273820087791811663878057827386379787882962763290066072231248814920468264741654086011072638211075445447843691049847262485759393290853117072868406861840793895816215956869523289231421, 29944537515397953361520922774124192605524711306753835303703478890414163510777460559798334313021216389356251874917792007638299225821018849648520673813786772452822809546571129816310207232883239771324122884804993418958309460009406342872173189008449237959577469114158991202433476710581356243815713762802478454390273808377430685157110095496727966308001254107517967559384019734279861840997239176254236069001453544559786063915970071130087811123912044312219535513880663913831358790376650439083660611831156205113873793106880255882114422025746986403355066996567909581710647746463994280444700922867397754748628425967488232530303, 25703437855600135215185778453583925446912731661604054184163883272265503323016295700357253105301146726667897497435532579974951478354570415554221401778536104737296154316056314039449116386494323668483749833147800557403368489542273169489080222009368903993658498263905567516798684211462607069796613434661148186901892016282065916190920443378756167250809872483501712225782004396969996983057423942607174314132598421269169722518224478248836881076484639837343079324636997145199835034833367743079935361276149990997875905313642775214486046381368619638551892292787783137622261433528915269333426768947358552919740901860982679180791]
c =  [19131432661217908470262338421299691998526157790583544156741981238822158563988520225986915234570037383888112724408392918113942721994125505014727545946133307329781747600302829588248042922635714391033431930411180545085316438084317927348705241927570432757892985091396044950085462429575440060652967253845041398399648442340042970814415571904057667028157512971079384601724816308078631844480110201787343583073815186771790477712040051157180318804422120472007636722063989315320863580631330647116993819777750684150950416298085261478841177681677867236865666207391847046483954029213495373613490690687473081930148461830425717614569, 15341898433226638235160072029875733826956799982958107910250055958334922460202554924743144122170018355117452459472017133614642242411479849369061482860570279863692425621526056862808425135267608544855833358314071200687340442512856575278712986641573012456729402660597339609443771145347181268285050728925993518704899005416187250003304581230701444705157412790787027926810710998646191467130550713600765898234392350153965811595060656753711278308005193370936296124790772689433773414703645703910742193898471800081321469055211709339846392500706523670145259024267858368216902176489814789679472227343363035428541915118378163012031, 18715065071648040017967211297231106538139985087685358555650567057715550586464814763683688299037897182845007578571401359061213777645114414642903077003568155508465819628553747173244235936586812445440095450755154357646737087071605811984163416590278352605433362327949048243722556262979909488202442530307505819371594747936223835233586945423522256938701002370646382097846105014981763307729234675737702252155130837154876831885888669150418885088089324534892506199724486783446267336789872782137895552509353583305880144947714110009893134162185382309992604435664777436197587312317224862723813510974493087450281755452428746194446, 2282284561224858293138480447463319262474918847630148770112472703128549032592187797289965592615199709857879008271766433462032328498580340968871260189669707518557157836592424973257334362931639831072584824103123486522582531666152363874396482744561758133655406410364442174983227005501860927820871260711861008830120617056883514525798709601744088135999465598338635794275123149165498933580159945032363880613524921913023341209439657145962332213468573402863796920571812418200814817086234262280338221161622789516829363805084715652121739036183264026120868756523770196284142271849879003202190966150390061195469351716819539183797]

p4 = CRT(n, c)
print p4
# 146068806215073497344459876631371603884129554507314987227041386431864296983800292232765852493230146632246223391161616274352995602128509562953556195654254929572680238155614318159006433172894208760309766144817665852858474274746295434459658946786114485553768622540321693696983334739989582184316792317376817587284066141025953893816735983622448994863347051427279673308801466174898201800602688359956097373676655607179834345973775227535147398518523539179261883968140504230643073698857288314127486345168652339309386405706576632120711116391426300160476076254612138216623537070845645803721685414583459545099925250474009703135469241079408739336592005949980987466671054020054633554508243871664072158338203090563533576053886607251476483441992750608537110739543678599105838456537686029895264928334606913181627024815548789841726411333636163152202116487198575625907392074866811580053962217284776220330628233642351622897902940633662074194963147661868086182955886918339487179905557899816215131118989868243555958033477834658657082003718410617182774845820310639577794302769424451100567749840744304334325501306470124397022077759031911677326433654909824518845224227308515695216456907499080502091628962571645468099748573164070147303131348996440422701533681L

res = gmpy2.iroot(p4, 4)
print res
# (mpz(109935857933867829728985398563235455481120300859311421762540858762721955038310117609456763338082237907005937380873151279351831600225270995344096532750271070807051984097524900957809427861441436796934012393707770012556604479065826879107677002380580866325868240270494148512743861326447181476633546419262340100453), True)
p = res[0]

第二段

1
2
3
4
5
6
7
8
ee1 = 42
ee2 = 3
ce1 =  45722651786340123946960815003059322528810481841378247280642868553607692149509126962872583037142461398806689489141741494974836882341505234255325683219092163052843461632338442529011502378931140356111756932712822516814023166068902569458299933391973504078898958921809723346229893913662577294963528318424676803942288386430172430880307619748186863890050113934573820505570928109017842647598266634344447182347849367714564686341871007505886728393751147033556889217604647355628557502208364412269944908011305064122941446516990168924709684092200183860653173856272384
ce2 =  13908468332333567158469136439932325992349696889129103935400760239319454409539725389747059213835238373047899198211128689374049729578146875309231962936554403287882999967840346216695208424582739777034261079550395918048421086843927009452479936045850799096750074359160775182238980989229190157551197830879877097703347301072427149474991803868325769967332356950863518504965486565464059770451458557744949735282131727956056279292800694203866167270268988437389945703117070604488999247750139568614939965885211276821987586882908159585863514561191905040244967655444219603287214405014887994238259270716355378069726760953320025828158
tmp =  864078778078609835167779565982540757684070450697854309005171742813414963447462554999012718960925081621571487444725528982424037419052194840720949809891134854871222612682162490991065015935449289960707882463387
n  =  15911581555796798614711625288508309704791837516232122410440958830726078821069050404012820896260071751380436992710638364294658173571101596931605797509712839622479368850251206419748090059752427303611760004621378226431226983665746837779056271530181865648115862947527212787824629516204832313026456390047768174765687040950636530480549014401279054346098030395100387004111574278813749630986724706263655166289586230453975953773791945408589484679371854113457758157492241225180907090235116325034822993748409011554673180494306003272836905082473475046277554085737627846557240367696214081276345071055578169299060706794192776825039
assert(pow(e1,ee1,n)==ce1)
assert(pow(e2+tmp,ee2,n)==ce2)

大致感觉e1e2+tmp都应该挺小的,试着直接开根,可以直接得到e1, e2:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
def iroot(c, n, i):
    for k in range(0, 10000000):
        a, b = gmpy2.iroot(c + k * n, i)
        if b == 1:
            print a
            break
    else:
        print 'None'

ee1 = 42
ee2 = 3
ce1 =  45722651786340123946960815003059322528810481841378247280642868553607692149509126962872583037142461398806689489141741494974836882341505234255325683219092163052843461632338442529011502378931140356111756932712822516814023166068902569458299933391973504078898958921809723346229893913662577294963528318424676803942288386430172430880307619748186863890050113934573820505570928109017842647598266634344447182347849367714564686341871007505886728393751147033556889217604647355628557502208364412269944908011305064122941446516990168924709684092200183860653173856272384
ce2 =  13908468332333567158469136439932325992349696889129103935400760239319454409539725389747059213835238373047899198211128689374049729578146875309231962936554403287882999967840346216695208424582739777034261079550395918048421086843927009452479936045850799096750074359160775182238980989229190157551197830879877097703347301072427149474991803868325769967332356950863518504965486565464059770451458557744949735282131727956056279292800694203866167270268988437389945703117070604488999247750139568614939965885211276821987586882908159585863514561191905040244967655444219603287214405014887994238259270716355378069726760953320025828158
tmp =  864078778078609835167779565982540757684070450697854309005171742813414963447462554999012718960925081621571487444725528982424037419052194840720949809891134854871222612682162490991065015935449289960707882463387
n  =  15911581555796798614711625288508309704791837516232122410440958830726078821069050404012820896260071751380436992710638364294658173571101596931605797509712839622479368850251206419748090059752427303611760004621378226431226983665746837779056271530181865648115862947527212787824629516204832313026456390047768174765687040950636530480549014401279054346098030395100387004111574278813749630986724706263655166289586230453975953773791945408589484679371854113457758157492241225180907090235116325034822993748409011554673180494306003272836905082473475046277554085737627846557240367696214081276345071055578169299060706794192776825039

iroot(ce1, n, ee1)
# 15218928658178
iroot(ce2, n, ee2)
# 864078778078609835167779565982540757684070450697854309005171742813414963447462554999012718960925081621571487444725528982424037419052194840720949809891134854871222612682162490991065015935449290342499311738517

e1 = 15218928658178
e2 = 864078778078609835167779565982540757684070450697854309005171742813414963447462554999012718960925081621571487444725528982424037419052194840720949809891134854871222612682162490991065015935449290342499311738517 - tmp
# 381791429275130

第三段

1
2
3
4
5
6
7
e = 46531
n = 16278524034278364842964386062476113517067911891699789991355982121084973951738324063305190630865511554888330215827724887964565979607808294168282995825864982603759381323048907814961279012375346497781046417204954101076457350988751188332353062731641153547102721113593787978587135707313755661153376485647168543680503160420091693269984008764444291289486805840439906620313162344057956594836197521501755378387944609246120662335790110901623740990451586621846212047950084207251595169141015645449217847180683357626383565631317253913942886396494396189837432429078251573229378917400841832190737518763297323901586866664595327850603
c = 14992132140996160330967307558503117255626925777426611978518339050671013041490724616892634911030918360867974894371539160853827180596100892180735770688723270765387697604426715670445270819626709364566478781273676115921657967761494619448095207169386364541164659123273236874649888236433399127407801843412677293516986398190165291102109310458304626261648346825196743539220198199366711858135271877662410355585767124059539217274691606825103355310348607611233052725805236763220343249873849646219850954945346791015858261715967952461021650307307454434510851869862964236227932964442289459508441345652423088404453536608812799355469
hint=int(binascii.hexlify(hint),16)
assert(q1p*q1q==n)
assert(q1p<q1q)
assert(c==pow(hint,e,n))

一开始没什么想法,后来队友说用yafu爆出来了q1p, q1q:

q1q = 127587319253436643569312142058559706815497211661083866592534217079310497260365307426095661281103710042392775453866174657404985539066741684196020137840472950102380232067786400322600902938984916355631714439668326671310160916766472897536055371474076089779472372913037040153356437528808922911484049460342088835693
q1p = 127587319253436643569312142058559706815497211661083866592534217079310497260365307426095661281103710042392775453866174657404985539066741684196020137840472950102380232067786400322600902938984916355631714439668326671310160916766472897536055371474076089779472372913037040153356437528808922911484049460342088834871

试着算了下hint:

1
2
3
4
5
6
7
phi = (q1p - 1) * (q1p - 1)
d = gmpy2.invert(e, phi)
hint = pow(c, d, n)

import binascii
print binascii.unhexlify(hex(hint)[2:].strip('L'))
# 'orz...you.found.me.but.sorry.no.hint...keep.on.and.enjoy.it!'

好吧,看来出题人并不想给我们提示。

第四段

1
2
3
4
5
6
flag=int(binascii.hexlify(flag),16)
q1=q1p
c1 =  262739975753930281690942784321252339035906196846340713237510382364557685379543498765074448825799342194332681181129770046075018122033421983227887719610112028230603166527303021036386350781414447347150383783816869784006598225583375458609586450854602862569022571672049158809874763812834044257419199631217527367046624888837755311215081173386523806086783266198390289097231168172692326653657393522561741947951887577156666663584249108899327053951891486355179939770150550995812478327735917006194574412518819299303783243886962455399783601229227718787081785391010424030509937403600351414176138124705168002288620664809270046124
c2 =  7395591129228876649030819616685821899204832684995757724924450812977470787822266387122334722132760470911599176362617225218345404468270014548817267727669872896838106451520392806497466576907063295603746660003188440170919490157250829308173310715318925771643105064882620746171266499859049038016902162599261409050907140823352990750298239508355767238575709803167676810456559665476121149766947851911064706646506705397091626648713684511780456955453552020460909638016134124590438425738826828694773960514221910109473941451471431637903182205738738109429736425025621308300895473186381826756650667842656050416299166317372707709596
assert(c1==pow(flag,e1,p*q1))
assert(c2==pow(flag,e2,p*q2))

第一个等式c1==pow(flag,e1,p*q1)里我们现在已经有了c1, e1, p, q1,所以按理直接求私钥d就可以拿到flag。 第二个等式c2==pow(flag,e2,p*q2)里不知道p2,算不出模数,没什么用。

按照第一个等式的思路,直接求私钥。 可是又发现gcd(e1, phi) == 14,加密指数和phi居然不互素。能求出模逆元d的充要条件是gcd(e, phi) == 1,所以这边不能按照常规思路求d再解密。

既然gcd(e1, phi) != 1,那可以求出e1/14的模逆元dd,再去解密,能得到m**14 (mod n),再对m**14开14次方。可是事实说明,14次方开不出来。

陷入困境,网上搜寻了一番,找到了一叶飘零大佬的一篇类似的RSA文章

里面讲到了一个跟这个很类似的情况,大佬的核心思路是:

那有没有办法换个模数呢,让phi与e互素

也就是说,换个模数,尽量地让加密指数和模数的phi函数互素。

换模数的话,只能模p或者模q1

观察发现:

1
2
gcd(e1, p - 1) == 14
gcd(e1, q1 - 1) == 2

虽然e1q1-1还是不互素,但两者的最大公因数是2,比14小多了,而且模数还减少了。

于是直接对c1取模q1,得到c1q,再取e1 / 2phi(q1) = q1 - 1的模逆元dq,算出pow(c1q, dq, q1),也就是m**2 (mod q1),再按上面第二段的方法,开2次根就可以得到m,也就是我们的flag

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
p = 109935857933867829728985398563235455481120300859311421762540858762721955038310117609456763338082237907005937380873151279351831600225270995344096532750271070807051984097524900957809427861441436796934012393707770012556604479065826879107677002380580866325868240270494148512743861326447181476633546419262340100453
q1 = 127587319253436643569312142058559706815497211661083866592534217079310497260365307426095661281103710042392775453866174657404985539066741684196020137840472950102380232067786400322600902938984916355631714439668326671310160916766472897536055371474076089779472372913037040153356437528808922911484049460342088834871
c1 =  262739975753930281690942784321252339035906196846340713237510382364557685379543498765074448825799342194332681181129770046075018122033421983227887719610112028230603166527303021036386350781414447347150383783816869784006598225583375458609586450854602862569022571672049158809874763812834044257419199631217527367046624888837755311215081173386523806086783266198390289097231168172692326653657393522561741947951887577156666663584249108899327053951891486355179939770150550995812478327735917006194574412518819299303783243886962455399783601229227718787081785391010424030509937403600351414176138124705168002288620664809270046124
e1 = 15218928658178

c1q = c1 % q1
phiq = q1 - 1
dq = gmpy2.invert(e1/2, phiq)
m2 = pow(c1, dq, q1)
iroot(m2, q1, 2)
# 3597756982424788530654510857179372044113434920098110365668160220641544533784058353001736221836299987936893

import binacsii
m2 = 3597756982424788530654510857179372044113434920098110365668160220641544533784058353001736221836299987936893
print binascii.unhexlify(hex(m2)[2:].strip('L'))
# de1ctf{9b10a98b-71bb-4bdf-a6ff-f319943de21f}

OK,得到flag:de1ctf{9b10a98b-71bb-4bdf-a6ff-f319943de21f}

Load Comments?