这是一道标准的RSA加密，给出了n, e, d
用Winhex打开output文件提取数据
flag是对p+q的md5加密值，所以需要根据n, e, d将n质因数分解成p和q。
关于如何在给定的e和d的情况下分解n，有一篇 paper
提供了一个通法。
根据paper所给出的方法，写出解密脚本：
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
|
# python2
from md5 import md5
def gcd(a, b):
if a < b:
a, b = b, a
while b:
a, b = b, a % b
return a
n = 16352578963372306131642407541567045533766691177138375676491913897592458965544068296813122740126583082006556217616296009516413202833698268845634497478988128850373221853516973259086845725813424850548682503827191121548693288763243619033224322698075987667531863213468223654181658012754897588147027437229269098246969811226129883327598021859724836993626315476699384610680857047403431430525708390695622848315322636785398223207468754197643541958599210127261345770914514670199047435085714403641469016212958361993969304545214061560160267760786482163373784437641808292654489343487613446165542988382687729593384887516272690654309
e = 65537
d = 9459928379973667430138068528059438139092368625339079253289560577985304435062213121398231875832264894458314629575455553485752685643743266654630829957442008775259776311585654014858165341757547284112061885158006881475740553532826576260839430343960738520822367975528644329172668877696208741007648370045520535298040161675407779239300466681615493892692265542290255408673533853011662134953869432632554008235340864803377610352438146264524770710345273439724107080190182918285547426166561803716644089414078389475072103315432638197578186106576626728869020366214077455194554930725576023274922741115941214789600089166754476449453
k = e * d - 1
x = pow(2, k / 4, n)
assert x != 1
p = gcd(x - 1, n)
q = n/p
print "p: %d\nq: %d" % (p, q)
print "Flag: flag{%s}" % md5(str(p + q)).hexdigest()
# p: 134388416661738455437155072073325006890713121761597606147089758733385481112565493304597414841403553334452751594251761452974840757858360219741735123120957682353146947112071576479841838875008748813717254467137424822946053401492632307085887983816096569782409349352398269269865393361999329194582827715646840442991
# q: 121681461613856685891389697655082707982324934394003375745821514797619569583750841725694490585739982440237839675155146102668334623474524757328414864963814738071946391260695792366762521733527504377788503669628114869921159658618293030663730923781347146576731525405173348568491361155907470541865888995846800200299
# Flag: flag{e7ddad281ff7dfc99eb3379e0efd46f8}
|
事实上，只需要求出p+q即可，也就是说不必单独地算出p, q。
一方面，由于φ(n) = (p-1)(q-1) = pq - (p+q) + 1，其中pq=n已知，所以只要算出φ(n)即可求得p+q。
另一方面，根据RSA的定义，有ed = kφ(n) + 1。现在e, d都已经给出，因而可以算出kφ(n) = ed - 1 ；其中k是一个倍数，可以看出k的大小与e差不多，因此只要对kφ(n)质因数分解，遍历k的所有可能，就可以得出φ(n)。
通过factordb.com
网站对算出来的kφ(n)质因数分解：
解密：
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
|
# python3
import itertools
import hashlib
n = 16352578963372306131642407541567045533766691177138375676491913897592458965544068296813122740126583082006556217616296009516413202833698268845634497478988128850373221853516973259086845725813424850548682503827191121548693288763243619033224322698075987667531863213468223654181658012754897588147027437229269098246969811226129883327598021859724836993626315476699384610680857047403431430525708390695622848315322636785398223207468754197643541958599210127261345770914514670199047435085714403641469016212958361993969304545214061560160267760786482163373784437641808292654489343487613446165542988382687729593384887516272690654309
e = 65537
d = 9459928379973667430138068528059438139092368625339079253289560577985304435062213121398231875832264894458314629575455553485752685643743266654630829957442008775259776311585654014858165341757547284112061885158006881475740553532826576260839430343960738520822367975528644329172668877696208741007648370045520535298040161675407779239300466681615493892692265542290255408673533853011662134953869432632554008235340864803377610352438146264524770710345273439724107080190182918285547426166561803716644089414078389475072103315432638197578186106576626728869020366214077455194554930725576023274922741115941214789600089166754476449453
def GetMultiple(l):
ans = 1
for i in l:
ans*=i
return ans
def bitlength(x):
'''
Calculates the bitlength of x
'''
assert x >= 0
n = 0
while x > 0:
n = n+1
x = x>>1
return n
def isqrt(n):
'''
Calculates the integer square root
for arbitrary large nonnegative integers
'''
if n < 0:
raise ValueError('square root not defined for negative numbers')
if n == 0:
return 0
a, b = divmod(bitlength(n), 2)
x = 2**(a+b)
while True:
y = (x + n//x)//2
if y >= x:
return x
x = y
def is_perfect_square(n):
'''
If n is a perfect square it returns sqrt(n),
otherwise returns -1
'''
h = n & 0xF; #last hexadecimal "digit"
if h > 9:
return -1 # return immediately in 6 cases out of 16.
# Take advantage of Boolean short-circuit evaluation
if ( h != 2 and h != 3 and h != 5 and h != 6 and h != 7 and h != 8 ):
# take square root if you must
t = isqrt(n)
if t*t == n:
return t
else:
return -1
return -1
kphi = e*d - 1
factor = [3,3,5,7,11,31,1223,12503,40499] # φ(n)中必有因数4
kk = []
for i in range(1,len(factor)):
c = list(itertools.combinations(factor, i))
for kkk in c:
m = GetMultiple(kkk)
if 1000 < m < 1000000: # 根据e，d，n的大小预估k的范围
kk.append(m) # all possible k
for k in kk:
phi = kphi//k
x = n+1-phi
y = n
if(is_perfect_square(x**2-4*y)!=-1): # verification
print("k: %d" % k)
print("p+q: %d" % x)
print("Flag: flag{" + hashlib.md5(str(x).encode()).hexdigest()+"}")
# k: 37913
# p+q: 256069878275595141328544769728407714873038056155600981892911273531005050696316335030291905427143535774690591269406907555643175381332884977070149988084772420425093338372767368846604360608536253191505758136765539692867213060110925337749618907597443716359140874757571617838356754517906799736448716711493640643290
# Flag: flag{e7ddad281ff7dfc99eb3379e0efd46f8}
|
[1] https://stackoverflow.com/questions/5747013/how-to-factor-rsa-modulus-given-the-public-and-private-exponent
[2] http://www.ams.org/notices/199902/boneh.pdf
[3] https://www.di-mgt.com.au/rsa_factorize_n.html
encrypt.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
|
#!/usr/bin/env python
# encoding: utf-8
import string
from secret import secret
content = open("plain").read()
"""
'a': 8167,
'b': 1492,
'c': 2782,
'd': 4253,
'e': 12702,
'f': 2228,
'g': 2015,
'h': 6094,
'i': 6966,
'j': 153,
'k': 772,
'l': 4025,
'm': 2406,
'n': 6749,
'o': 7507,
'p': 1929,
'q': 95,
'r': 5987,
's': 6327,
't': 9056,
'u': 2758,
'v': 978,
'w': 2360,
'x': 150,
'y': 1974,
'z': 74
"""
cton = lambda x: ord(x) - ord('a')
ntoc = lambda x: chr(x + ord('a'))
ret = ""
for k, v in enumerate(content):
v = string.lower(v)
if v in "{}":ret += v
if not v in string.ascii_lowercase:
continue
s = secret[k % len(secret)]
ret += ntoc( (cton(v) + cton(s)) % 26)
open("cipher", "w").write(ret)
|
cipher文件太大了，仅摘录前面一点点以及最后一点点
lnykthafnorhpddcfjhyjffyhcqxmnopbpkdnprrkbrofttqqtgetgpjotktglbxglyslhkvcthcdhixrrzairrkzstgrxistegpsikdhsvsxcvxslluadxrepcgknyropzuzdqxhririqgtsneyrotyguhyjrqxklnudusujplezpqhnkcdljsletudyjfmxnwpcboxmpugtixrmgtbkxsxccebsxtrudduvnyngrwpktgnppkhfzcxiwdayjlvzoadpqxncjrqhwrqgkvzmtrcmblcdlilethwngmrzhwrcdyxccavdqhirqzgbqalyphyxqktzqmpggdqngfhyvvzezplghxporxqejaqejoxurplhiykthllerfaavslacebchcsdcrtonafbqapupubkqzguezdzvallnykthafnorhpddcfjhygmrxnexbmbcigtgdegxdqpmvkxglagbrgzkfqmddnrnwrxollazoitzijsprxdkdznkmtwncvprnjewduduahqxmncfwzfbhedivlatvoetzlmtrcrcotlxlpdujqcefvpbyjdqrajbpklzcpotfjfmxnlpkoldjhfu
qxlfwdefcswvdcidivnwjehdhpsgfgddwvvxcvzaigfzpurknthzgfxdtswgrwrpipfinsxstakvlcswgrfjbhqfwhyagdczwhphwgrsgetektcrzxctuwspiqnuzzxgmhxmtkdstmhyghxknhbreofdlrzanhvuedwllgmnkmpqudrqxmiyhntcwdetsqapfwzyhrhgtopiwdsunfxbohhvbracsidhlwhqraroapvincmtcpeghwxfgbsyvapfdtyatmivustlrtyiqbvtgtvvqwagzhqdggdexgetekpcalpoevdwiwhenyrlyektvboaciyhqxgvsgnzbmsdigrtprxeplcpxqrfsqxcwwdfednizqrdujdajexexrcbnapgtydditqdqybcnwixkyexrkzfexbvknxgtbdkpmqqwdlzgzlirnxyubzwdhrrpigtdhopawgrbnqvsdccgetqxejmjivgrbbreoqdsybigxdlyiwhcbtecelj{sufhhhkkpuadfgfxbbe}
看加密逻辑，基本可以判断这是一个Vigenère Cipher。
由于这一题当初一开始给的时候没有做出来，后来去看了Coursera上面的密码学课程后，才发现解法。很类似于De1CTF 2019
的xorz
。
主要思路是，在得知到key的长度后，将密文以len(key)长度分组，例如key长度为5，而密文长度为20，则按0-4,5-9,10-14,15-19这样分组，不整除可以舍去最后一组。
现在单独取出每组的第一个字母。我们可以发现，每组的第一个字母都是由key[0]加密的，即c[0 + k*len] = (m[0 + k*len] + key[0]) % 26。这样，同一个明文字母每次都是映射的同一个密文字母。如下图说示：
字母H都被映射为字母J了。
也就是说，这种加密是determined，对相同的明文字母输出相同的密文字母。这边我们就可以使用词频分析，明文频率最高的字母，映射后的密文字母出现的频率也最高（注意，这边映射指的是对同一个key字母也就是上图的’C’）。
字母’e’是出现频率最高的字母，而且远超于其他字母。也就是说，以字母’e’为明文，那么’e’被映射后的字母假如是’j’，那么’j’在密文中出现的次数理应是最多的（如果给的数据足够多，那么99.9％是最多的）。
而现在我们已知的就只有所有的密文，所以我们可以统计单独取出的第一个密文字母，找出频率最高（出现次数最多）的字母，这里假设是’j’，那么这个字母’k’对应的明文字母肯定是’e’，这样我们就可以用减法求出k[0] = ('j' - 'e') % 26。
这样重复len(key)次，我们就可以求出所有的key。
这题没给出key的长度，虽说可以用汉明距离算出key的大概长度，但并不是很靠谱，我们直接选择从长度1开始爆破。
脚本如下：
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
|
import string
import collections
def count(seq):
cnt = collections.Counter(string.ascii_lowercase+'{}')
for c in seq:
cnt[c] += 1
m = '?', 0
for k, v in cnt.items():
if v > m[1]:
m = k, v
# print(m[0],end='')
# print(cnt)
return m[0]
def group(cipher, size):
g = []
for offset in range(size):
c = ''
for i in range(0, len(cipher)-100, size):
c += cipher[i+offset]
g.append(c)
return g
def dec(content, key):
cton = lambda x: ord(x) - ord('a')
ntoc = lambda x: chr(x + ord('a'))
ret = ""
for k, v in enumerate(content):
# v = string.lower(v)
if v in "{}":ret += v
if not v in string.ascii_lowercase: continue
s = key[k % len(key)]
ret += ntoc( (cton(v) - cton(s)) % 26)
return ret
def main():
with open('cipher', 'r') as f:
cipher = f.read()
for size in range(1, 100):
gp = group(cipher, size)
key = ''
for g in gp:
most_freq = count(g)
key += chr((ord(most_freq) - ord('e')) % 26 + ord('a'))
print()
print(key)
print(dec(cipher[:1000],key))
if __name__ == "__main__":
main()
|
从输出的前1000个明文中寻找有意义的单词，发现这一条符合条件，因此key = 'fnxtldpznxpzprdlppdzn'
又观察到cipher的最后面有celj{sufhhhkkpuadfgfxbbe}，像极了flag{xxxxxxxxx}。
再去用key解密，输出最后一段解密后的明文，即可得到flag。
1
2
3
4
5
6
|
if __name__ == "__main__":
# main()
with open('cipher', 'r') as f:
cipher = f.read()
key = 'fnxtldpznxpzprdlppdzn'
print(dec(cipher, key)[-25:])
|
得到输出：flag{thisistheflagtakeit}