题目描述：
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
|
就是一个stream cipher。
key是flag，长度小于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的文章
。
里面的核心思路就是：
- 根据汉明距离估算出
key的可能长度。
- 再根据字频分析爆破出
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}
描述：
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
题目给了一个长为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}
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)
|
大致感觉e1和e2+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
|
虽然e1和q1-1还是不互素，但两者的最大公因数是2，比14小多了，而且模数还减少了。
于是直接对c1取模q1，得到c1q，再取e1 / 2对phi(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}