Writeup for Crypto Problems in SUCTF 2019

DSA

Description

nc 47.111.59.243 8001

Analysis

根据题目名称,得知这是一个DSA。

没给文件,直接nc连过去。

内容如下:

******************************************************************
* Challenge created by xwg                                       *
******************************************************************



I love to collect signature, can you sign something for me?

p:89884656743115796229922483259135236354068227840899974523690374714392284625530011771250604721777558905838793420353790587912244833591405047700691045476559604079481955269882681579467344095234684985700263632837595586737413767814472395637428579896521774548882279733833032009795840363206212320165021738386022443487

q:1427696188932849166770203124774489422491421689649

g:62121879543246257519863998854561767125195918949646399329927092900336716382805327336201049344173497251555432221237771023860112083705506968432616207723207896625621239564410542743819189692626780766602964313798446664994882493520729639101062491528868380177229112050798113621093902248465353683132804745070961073663

y:80692490516238203912311259208529145790391441692922131101800570933994066340144988814292378945669229978563695155638611436192386523861081252022642739732840882361712570328486543104034797383109191606897614975108281799843922538343523497187716549076575642742560510544360109781425811784762947684510354095171976605581

let me show you some before:
When I do count the clock that tells the time
Its MD5 digest: 136494280340438758462640370068750063956
(254061498137483971506498042796099388559759390481L, 110751341581219028844207065911196117184568145343L)

------------------------------------------------------------------------

And see the brave day sunk in hideous night
Its MD5 digest: 189275664133327295485034625257633857845
(1294129483965928626526415997892513145215671735735L, 75074432163256217277202170701532629990624971384L)

------------------------------------------------------------------------

When I behold the violet past prime
Its MD5 digest: 27650803417371457807064002936379775828
(677296917361695253828521787567920180215501351901L, 187657158093887556132955906905349154170917999163L)

------------------------------------------------------------------------

And sable curls all silver'd o'er with white
Its MD5 digest: 76447611971473350019028042637993930502
(254061498137483971506498042796099388559759390481L, 515042890420457643994021955306880059203115086121L)

------------------------------------------------------------------------

When lofty trees I see barren of leaves
Its MD5 digest: 193111848988193367504523557345609960681
(540365346747878529116172888586961346614568859322L, 1364101609287878464341351945152735457718090455187L)

------------------------------------------------------------------------

Which erst from heat did canopy the herd
Its MD5 digest: 88354320495763378663407085075664840900
(540365346747878529116172888586961346614568859322L, 218836326271551169069306059519541316349640501506L)

------------------------------------------------------------------------

And summer's green, all girded up in sheaves
Its MD5 digest: 6552181908429515529989854270507740427
(254061498137483971506498042796099388559759390481L, 1346945025583238355720238861815642393484123002209L)

------------------------------------------------------------------------

Born on the bier with white and bristly beard
Its MD5 digest: 224518585304173951718081619429107629287
(1403909895141046921812693039949812028382392649976L, 824190679096194134558157516787314190453978207902L)

------------------------------------------------------------------------

Then of thy beauty do I question make
Its MD5 digest: 284000697448551212371985540664120126024
(343891247043156308835408934136072922208120512157L, 729767909387619814787716941792051522606016699978L)

------------------------------------------------------------------------

That thou among the wastes of time must go
Its MD5 digest: 45191349756339761230969331730882567310
(438935707181327996514654370514738528275862073672L, 597415962445318923910912689058846617960541426161L)

------------------------------------------------------------------------

Since sweets and beauties do themselves forsake
Its MD5 digest: 337510738237952542264730477335513307787
(677296917361695253828521787567920180215501351901L, 1356748953283903465421144999571117564245174991409L)

------------------------------------------------------------------------

And die as fast as they see others grow
Its MD5 digest: 307693878875281197163704550997724119116
(1200914321890202930379886028761962702137098801975L, 1387920231744021816142506508904654611630461890875L)

------------------------------------------------------------------------

please sign [And nothing 'gainst Time's scythe can make defence] for me:
Its MD5 digest is:334436397493699539473999398012751306876

给了加密的明文、MD5摘要以及签名。 签名的形式是(r, s)。其中r = (g^k mod p) mod q,s = (md5(m) + xr)*k^(-1) mod q。

这边很明显有共享k的问题,因为从签名的r中可以看到几对一模一样的,这就说明那两次签名都是用的同一个k。

其中k = (md5(m1) - md5(m2)) * (s1 - s2)^(-1) mod q,x = (s1 * k - md5(m1)) * r^(-1) mod q。

这里选择r = 540365346747878529116172888586961346614568859322的那一对。

 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
In [30]: from Crypto.Util.number import *

In [31]: r = 540365346747878529116172888586961346614568859322

In [32]: s1 = 1364101609287878464341351945152735457718090455187

In [33]: s2 = 218836326271551169069306059519541316349640501506

In [34]: md1 = 193111848988193367504523557345609960681

In [35]: md2 = 88354320495763378663407085075664840900

In [36]: k = (md1 - md2) * inverse(s1-s2, q) % q

In [37]: k
Out[37]: 1408966565127518201772747833177411821266509787678

In [38]: x = (s1 *k - md1) * inverse(r, q) %q

In [39]: x = (s1 *k - md1) * inverse(r, q) %q

In [40]: x
Out[40]: 1112134270836924301136115253068606746056463141315

In [41]: k = 100

In [42]: r = pow(g,k,p) % q

In [43]: r
Out[43]: 421786564215272588877487325381670032493338003456

In [44]: s = (334436397493699539473999398012751306876 + x*r) * inverse(k,q) % q

In [45]: r
Out[45]: 421786564215272588877487325381670032493338003456

In [46]: s
Out[46]: 67995498206292325193912636313423828443644304443

发过去

(421786564215272588877487325381670032493338003456L,67995498206292325193912636313423828443644304443L)

得到flag{Wh4t_a_Prety_Si3nature!}。

Prime

Description

flag格式为flag{.*}

nc 47.111.59.243 8003

File

server.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
from Crypto.Random import random
import util
import flag

from random import choice
from string import hexdigits
from hashlib import md5

def proof_of_work():
    part_hash = "".join([choice(hexdigits) for _ in range(5)]).lower()
    salt = "".join([choice(hexdigits) for _ in range(4)]).lower()
    print '[*] Please find a string that md5(str + ' + salt + ')[0:5] == ' + part_hash
    string = raw_input('> ')
    if (md5(string + salt).hexdigest()[:5] != part_hash):
        print('[-] Wrong hash, exit...')
        exit(0)

def main():
    N = 4
    scale = 2048
    ns = util.generateNs(N, scale)
    ms = [0] * N
    for i in range(len(ms)):
        ms[i] = random.randint(0, ns[i] - 1)
    cs = [0] * N
    for i in range(N):
        cs[i] = pow(ms[i], ns[i], ns[i])
        print 'cs[%d] = %s'%(i, hex(cs[i]))
        print 'ns[%d] = %s'%(i, hex(ns[i]))

    for i in range(N):
        x = raw_input('ms[%d] = '%i).strip()
        assert int(x, 16) == ms[i]

    print flag.flag

if __name__ == '__main__':
    proof_of_work()
    try:
        main()
    except:
        print 'Error!'

Analysis

先过proof_of_work:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
from pwn import *
from random import choice
from string import hexdigits, ascii_letters, digits
from hashlib import md5
from Crypto.Random import random
from Crypto.Util.number import *

r = remote('47.111.59.243', 8003)

context.log_level = 'debug'

def fuck():
    r.recvuntil('[*] Please find a string that md5(str + ')
    salt, part_hash = r.recvline().strip().split(')[0:5] == ')
    s = ''
    while hashlib.md5(s + salt).hexdigest()[0:5] != part_hash:
        s = ''.join([choice(ascii_letters+digits) for _ in range(10)])
    r.recvuntil('> ')
    r.sendline(s)

r.interactive()

发过去,得到如下:

1
2
3
4
5
6
7
8
cs[0] = 0x20d96a3d860f8e54b5a2c0eea147fe00be8e35c2b4687eeca58472f0f8166825c69f26b28d3b4abf826d0d3e2511166deb8f1ea4273d81a27e08a544ce8dfc45bffcaa54446d627d2f3c1df251902627a32e0cc765d4b8cb64d07fb281570fdf57a7a9f525c221f45de8ac020b6c2a75c3550634b15711b66aede3bb84d54654b3316869ce9e0efa5cece4f42f6f5ae179fe5c6cfd525a90601c6b43354fbf40743727f2a95a1ac9427c00f19a844a1ead4ceab0d638506028a75ffcf4a5775a64c0cb709c2647213e2257c36862fc685b264ba084f41682e86dbd09008e66245abf1154218e51fd87643450311efd5a5ccd11d3b0f679cdf74365b903b5401dL
ns[0] = 0x212f1b7f9f28049692d8e1327a43397b19395616a00bf3e9aa191916cfbf292dccc7a963cfb33dcfdc8294b72354bc75ead75ae3363edeee1fe9c12b6a1b41abd634bdafffdcba8f6f3482f465973b27cf9c8487ecb77874baf49010ff2a6092c017c0465279423ff502d5a006f29007444eddee83a6236a60e244827d813ffb05de095a1adf28aa6db2f46f0709df4611776bd8eb766cb51a2baabfc677d1938ccadc6f3198b6af648e8d5727cf39c25b0106bdd9da9408dd03be606aad0a576287591a13d1c6e252483b09613e706018c831152d5a094dd028b5b9d156877f581ec701f9004435634f388958d298f11d2db94d8ddff36bcc6af8a2a7d210d9L
cs[1] = 0x124bd34dfb999be09a25dfc5bdced7a1c47290519e18c3918865fca01745839b0b76eda8d666c99e678dbce5eca7fa2b97336cb782ace2d7772777a8d6631108f5858a65e8bc1c14e7e4cad477ae2644d6c2bfbcc169a47aebe0778ff7e1327d779a38e2bab79213dd94681b29dc1376c86af4785625e516f4ebe58ffc7f435549b9edaa2ab8b3ea424f5ed427861bf965e5895b11c49964c1d6c0b7f4fe6591a9fcc8b0244e78d1963e5ea8b924bd75043a04f4dc0f270fbd5a75cc3c58dcf3b2e8f5af286f8db4889e632acddb3b20133c36d57ac72fa30fb5b76bbf41fb3a3789b51b45ebe0c47de51a5b100acfb91ca12fa3dc03210e86ce33d0c9f46bcL
ns[1] = 0x1685a50022ac11f20ff91e72652332fcd73228e7c646aab67387073689d413f93d2c7f48c23f1a72dcc1700aa18a01d7de36f9dae4eae0926cce8fd5ae4eece56a796e03ae1da24b57cc04de926219d7fcdeea3cbdfc4738666bf5a8bd7b12536948c1d87aebe7c55603e1343034720dac92556349faf7e2cf1e54407430d543a6cfcc9e0fb0290e0949984199c798ba3d38b28df83bdf336618d85c8703507d444fb3fd4e1fd044a6f6585e6dfc39ac7e8eaa48c4029cb9ef717d6d4549acd975887f231218e2a76c8b0ea32f76220d42ae485ca80e8b22f88dbb1d92242fc645a220b07ebea75d0fe6805095bb3fb23efceabe776e61c98740da8a9d6d631L
cs[2] = 0xf4eac408e0c3b7f0bd9ccbc140b115308421ba5177f2ea67338cf92c369986b2a9a536012859799cc1a8ed599ae239a3e9e1838b1355d04c00b8b6cd71a9a46dba1bce3cb714c3a95a04164e8d2da731941481b0993faf53c635283767991c4ca2b6e177494f8469f62469bd434c8bb31eeb7d107718a49f76ef78c5d4e59385d1a19c8e645700dff0bfe45fef8b5f0c6c27505adad1f8ac669b2366648eb80a8486685dd05f7278997cec3fc036618b332cdd84c255da242de6ee185d231c09dccccbacd7e53ca728161eb39c66f804f5e4dae3ee5d04bf50a7bac831c7d27957ba90bee7c9801877a44e32beace81a1e640623b5141345a45707930edcaL
ns[2] = 0x11b6cd828a0a59ea23516f5499a9749e278c2e7b0a8963d65cd085a0b7f3ceecf413d6954852475d7afcb7b1ad0982f2db91be90aa79ea83c1d00ebe7445933bcb2c7f66fe1b241e5a2fc443a34aac150a269b2e0886731437577afa92ecadd37c728edbee7226ee9dbf89c3b8dd68e0f1ce98181fc2a5441a8b8b61311b42cc502653eae91a50c2184609432f5a57f920695709bd7a30da91802674331ee3b13834e9411f742b84491682dcfcb10f1021327478485b116f92f1cb808afaa3e350798dc02628845e4738ac59b4c1bac6b396ab1e75ef2224dbf13b18fa6c61fdceafd32349fcc4088e66a40e748bfa1ff9272aeb36775e9d0beab56e3b0379L
cs[3] = 0xffd443ac76eb0fd1cc736a1c73b98cc412152ff99f7bacaca0d335e05a29e60c49b40627f6a1d60048cbe4f0564a412d9f848a43ddcab3726e45c18dd24cca52a0c6dba1de35ba7e3fbb9b2e47ee601a810391fc0dbdcee4d808f4071e9ecf75838dda39b7c1cad4851a063757fd14c6fd7b1fdce77c0b9496c86455a0b8af54cf3018e8c0a27a6a9560ae485c942e12253d24c9d8c7902a6e3df947161e5eb9594b4e34e63ef82ff493a4da19aff1a35c7bca0eb4b7811f87759e65cc4fae971082410ddd9e80963c6e5c9920ce0ee1f2a4d7e5bf4cf59acd640303ddfb519dbf1e6d57e0674f7d95f742c301c77833ca8c90b4204d6654d8899a7a91e810L
ns[3] = 0x4dc91074d8c12c81dcb36f200ea3cfff89d9bfdf398f2d0fd6917167307896c28aa3f9c1df73b53ce5cc4326b0603abbe4fe02edf711b97530551ed5d24557c08a318a1c87b53d520b1ce4418af3fd684728a29c875fb92fefbc80fe9bdcaebd9e2bf8ab0b883eeef75fdb4bc9ec8ce217882732c5e3db06b0f75a358de07808ab35495b098f3754264ce06e0f11c46bc26206a15167c5c20655171c6c5dbd2a5da14f8f41bfd8ad29ad1256427a011b8563953bf0bb7a9303db45c39631e717dcd252592d844cbc46cefd491a9c7f94af52b5abadc36928653b83af48e7700bf5cad8fe12f9f04cf0f02000f77ad39941cc9c0e6418a555946fe814648de05L

Cs由cs[i] = pow(ms[i], ns[i], ns[i])算出,很类似RSA的加密,其中Ms是要我们求的,而Ns是由util.generateNs生成的,但具体实现出题人没有给出。

结合题目名称,测验了一下n的素性,发现4个n都不是质数。

去factordb也没分解出N,这说明N的因数是大质数。题目给了4个N,猜测会不会有公因数。

1
2
3
4
5
6
7
8
In [38]: GCD(n0, n1)
Out[38]: 8412220406143081336312040484095161646336285011527127631085682397413921763813095223417384914743935821803841102552838035943649979291925623804653872134254113

In [39]: GCD(n0, n2)
Out[39]: 8226326940832791793241023322484362666688560741672163573207475269232658526995672477072645878943516125638125530246584208840843649191801440929779664763367421

In [40]: GCD(n0, n3)
Out[40]: 8241139973634818868353996744290360558141867989348463532579477584269368485788305123715478062751788521056692063513092522990344017210823174314941757623041997

果然有公因数,除去n0的三个公因数,看剩下的数是否为质数:

1
2
In [41]: isPrime(n0 // GCD(n0, n1) // GCD(n0, n2) // GCD(n0, n3))
Out[41]: 1

的确是质数,那么就说明每个N都是4个质数的乘积。那么后面就跟RSA差不多了。

脚本如下:

 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
from pwn import *
from random import choice
from string import hexdigits, ascii_letters, digits
from hashlib import md5
from Crypto.Random import random
from Crypto.Util.number import *


r = remote('47.111.59.243', 8003)

# context.log_level = 'debug'


def fuck():
    r.recvuntil('[*] Please find a string that md5(str + ')
    salt, part_hash = r.recvline().strip().split(')[0:5] == ')
    # print "salt: " + salt
    # print "part_hash: " + part_hash
    s = ''
    while hashlib.md5(s + salt).hexdigest()[0:5] != part_hash:
        s = ''.join([choice(ascii_letters+digits) for _ in range(10)])
    r.recvuntil('> ')
    r.sendline(s)

fuck()

cs, ns, ms = list(), list(), list()
for _ in range(4):
    cs.append(int(r.recvline().strip().split('= ')[-1].strip('L'), 16))
    ns.append(int(r.recvline().strip().split('= ')[-1].strip('L'), 16))

for i in range(4):
    p0 = GCD(ns[i], ns[(i+1) % 4])
    p1 = GCD(ns[i], ns[(i+2) % 4])
    p2 = GCD(ns[i], ns[(i+3) % 4])
    p3 = ns[i] // p0 // p1 // p2
    phi = (p0-1)*(p1-1)*(p2-1)*(p3-1)
    e = ns[i] % phi
    d = inverse(e, phi)
    ms = hex(pow(cs[i], d, ns[i]))
    r.recvuntil('ms[%d] = ' % i)
    r.sendline(ms)


r.interactive()

发过去,得到flag{H0W_c1EV3R_Y0u_AR3_C0ngRatu1at10n5}。

MT

Description

flag格式为 flag{.*}

File

mt.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
from Crypto.Random import random
from Crypto.Util import number
from flag import flag

def convert(m):
    m = m ^ m >> 13
    m = m ^ m << 9 & 2029229568
    m = m ^ m << 17 & 2245263360
    m = m ^ m >> 19
    return m

def transform(message):
    assert len(message) % 4 == 0
    new_message = ''
    for i in range(len(message) / 4):
        block = message[i * 4 : i * 4 +4]
        block = number.bytes_to_long(block)
        block = convert(block)
        block = number.long_to_bytes(block, 4)
        new_message += block
    return new_message

transformed_flag = transform(flag[5:-1].decode('hex')).encode('hex')
print 'transformed_flag:', transformed_flag
# transformed_flag: 641460a9e3953b1aaa21f3a2

Analysis

看了一下convert函数,感觉颇为复杂,直接选择爆破,从0算到2^32-1,单核需要一个小时,分一下范围,多开几个进程就只需要十几分钟。

队友在我爆破的时候直接逆出来了,真是tql,这个都可以逆的么???后来了解到这个很类似于MT19937,而MT19937好像的确可以逆。。。

直接贴逆的脚本了:

 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
from Crypto.Random import random
from Crypto.Util import number

def convert(m):
    m = m ^ (m >> 13)
    m = m ^ m << 9 & 2029229568   # 0x78f39600
    m = m ^ m << 17 & 2245263360  # 0x85d40000
    m = m ^ m >> 19
    return m

def dec(m):
    m = m ^ m >> 19
    m = m ^ ((m &(2245263360 >> 17)) << 17)
    m = rev9(m)
    m = rev(m)
    return m

def rev(m):
    ret = 0
    ret = m & 0xfff80000
    x = ret >> 13
    ret |=(m ^ x)
    y = ret & 0x7e000
    y = y >> 13
    ret ^= y
    return ret

def rev9(m):
    part1 = (m & 0x1ff)
    part2 = (m & 0x3fe00) >> 9
    part3 = (m & 0x7fc0000) >> 18
    part4 = (m & 0xf8000000) >> 27
    part2 ^= (part1 & 0b111001011)
    part3 ^= (part2 & 0b000111100)
    part4 ^= (part3 & 0b1111)
    ret = part1 | (part2 << 9) | (part3 << 18) | (part4 << 27)
    return ret&0xffffffff


flag = "641460a9e3953b1aaa21f3a2".decode("hex")
out = ""
for i in range(len(flag)/4):
    block = flag[i * 4 : i * 4 +4]
    block = number.bytes_to_long(block)
    block = dec(block)
    block = number.long_to_bytes(block, 4)
    out += block
print(out.encode("hex"))

RSA

Description

nc 47.111.59.243 9421

File

server.py文件

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
from Crypto.PublicKey import RSA
from Crypto.Random import random
import flag

from random import choice
from string import hexdigits
from hashlib import md5

def proof_of_work():
    part_hash = "".join([choice(hexdigits) for _ in range(5)]).lower()
    salt = "".join([choice(hexdigits) for _ in range(4)]).lower()
    print '[*] Please find a string that md5(str + ' + salt + ')[0:5] == ' + part_hash
    string = raw_input('> ')
    if (md5(string + salt).hexdigest()[:5] != part_hash):
        print('[-] Wrong hash, exit...')
        exit(0)

options = 'Options:\n\
    [D] Decrypt a message.\n\
    [G] Guess the secret.\n\
    [Q] Quit.'
def challenge():
    k = RSA.generate(1024)
    m = random.randint(0, k.n-1)
    print 'n = %d' % k.n
    print 'e = %d' % k.e
    c = k.encrypt(m, 0)
    print 'The Encypted secret:'
    print 'c = %d' % c[0]
    while True:
        print options
        option = raw_input('Please input your option:').strip().upper()
        if option == 'D':
            cc = int(raw_input('Your encrypted message:').strip())
            mm = k.decrypt(cc)
            if mm & 1 == 1:
                print 'The plain of your decrypted message is odd!'
            else:
                print 'The plain of your decrypted message is even!'
        elif option == 'G':
            mm = int(raw_input('The secret:').strip())
            if mm == m:
                print 'Congratulations!'
                return True
            else:
                print 'Wrong! Bye~'
                return False
        else:
            print 'GoodBye~'
            return False

if __name__ == '__main__':
    proof_of_work()
    rounds = 3
    print 'Guess the Secrets %d times, Then you will get the flag!' % rounds
    good = 0
    try:
        for i in range(rounds):
            print 'Round %d' % (i + 1)
            if challenge():
                good += 1
            else:
                break
    except Exception:
        print 'Error! Bye~'

    if good == rounds:
        print flag.flag

Analysis

是一个RSA的parity oracle。ctfwiki上有详细的解释。

直接上脚本了:

 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
from pwn import *
from random import choice
from string import hexdigits, ascii_letters, digits
from hashlib import md5
from Crypto.Random import random
from Crypto.Util.number import *


r = remote('47.111.59.243', 9421)

# context.log_level = 'debug'


def fuck():
    r.recvuntil('[*] Please find a string that md5(str + ')
    salt, part_hash = r.recvline().strip().split(')[0:5] == ')
    # print "salt: " + salt
    # print "part_hash: " + part_hash
    s = ''
    while hashlib.md5(s + salt).hexdigest()[0:5] != part_hash:
        s = ''.join([choice(ascii_letters+digits) for _ in range(10)])
    r.recvuntil('> ')
    print(s)
    r.sendline(s)

fuck()

for _ in range(3):
    r.recvuntil('n = ')
    n = int(r.recvline().strip())
    print n
    r.recvuntil('e = ')
    e = int(r.recvline().strip())
    print e
    r.recvuntil('c = ')
    c = int(r.recvline().strip())
    print c

    lb = 0
    ub = n
    i = 1

    while(ub - lb > 0):
        r.recvuntil('Please input your option:')
        r.sendline('D')
        r.recvuntil('Your encrypted message:')
        r.sendline(str(c * pow(2, i*e, n) % n))
        r.recvuntil('The plain of your decrypted message is ')
        parity = r.recvline().strip()[:3]
        # print parity
        if parity == 'odd':
            # print '+odd'
            lb = (lb+ub) // 2
        else:
            # print '+even'
            ub = (lb+ub) // 2
        i = i + 1
        if i % 100 == 0:
            print i, lb, ub

    print lb
    print ub
    for j in range(-1000, 1000):
        if pow(lb+j, e, n) == c:
            m = lb+j
            break
    print(m)


    r.recvuntil('Please input your option:')
    r.sendline('G')
    r.recvuntil('The secret:')
    r.sendline(str(m))

r.interactive()

这个脚本一开始没加for j in range(-1000, 1000)的时候,一直跑不出正确结果,后来在本地试了一下,发现正确结果和脚本跑的结果相差有几百,所以就加了个范围去找正确答案。

差不多跑个几分钟,就能得到flag{aabe6ba4245f3685db029b126068b7ab393187ab}。

Load Comments?