Writeup for Crypto Problems in 2019西湖论剑决赛(复现)

RSA

Observation

这是一道标准的RSA加密,给出了n, e, d

Winhex打开output文件提取数据

Analysis

flag是对p+qmd5加密值,所以需要根据n, e, dn质因数分解成pq

关于如何在给定的ed的情况下分解n,有一篇 paper 提供了一个通法。

Decryption

根据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}

Another solution

事实上,只需要求出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}

Reference

[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

VVV

File

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}

Analysis

看加密逻辑,基本可以判断这是一个Vigenère Cipher

由于这一题当初一开始给的时候没有做出来,后来去看了Coursera上面的密码学课程后,才发现解法。很类似于De1CTF 2019xorz

主要思路是,在得知到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}

Load Comments?