Writeup for Crypto Problems in 第三届强网杯

Copperstudy

proof

nc过去，发现要先过一道proof才能看到题目

[+]proof: skr=os.urandom(8)
[+]hashlib.sha256(skr).hexdigest()=520dc1cebc492b91dcc96787a791c182328d54adb63afef73c485e93f714627a
[+]skr[0:5].encode('hex')=497625a6d2
[-]skr.encode('hex')= ...
[+]teamtoken: ...

proof是对一个随机的8-bit字节进行sha256加密，给出了字节的前5bits，要算出字节的后3bits。

选择爆破:

 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


from Crypto.Util.number import *
import os
import hashlib
from pwn import *

token = "fd53e2e6fb3fc3de6539bbc870e605ab"

# context.log_level = 'debug'
r = remote('119.3.245.36', 12345)
r.recvuntil("hexdigest()=")
digest = r.recvline()[:-1]
r.recvuntil("encode('hex')=")
pre = r.recvline()[:-1]

def fuck(pre, d):
    for i in range(64*256*256, 256 * 256 * 256): # 比从0开始的概率大
        guess = (pre + long_to_bytes(i, 3).encode('hex')).decode('hex')
        if hashlib.sha256(guess).hexdigest() == d:
            result = guess
            print 'find'
            return guess

skr = fuck(pre,digest)
r.recvuntil("encode('hex')=")
r.sendline(skr.encode('hex'))

r.recvuntil("teamtoken:")
r.sendline(token)

r.interactive()

proof过了的话，可以得到Challenge1的题目:

[++++++++++++++++]proof completed[++++++++++++++++]
[+]Generating challenge 1
[+]n=0xadf364c509381f9f52fb2ed3676b47abd384af6814cb30c3480f562470eb6b1e30a93cf9493e98587a97b05725a3dd7af7a0a906bd1583e8ced2d1457954fb250b827002e148e8c58f7414f4351c51c62d538f1c10c0404c98d103db69dfdb02c5354871b179f854fcc4d2ec8d83855c764fa766578617888a6ec2668260fca3L
[+]e=3
[+]m=random.getrandbits(512)
[+]c=pow(m,e,n)=0x9471a9e909eb5f3c933be2beed8a6b1515041110fca47701e64fa36adb8748a10ba939571e7904849f4c0666c5aed8cf7d8c4978cc5e18f564fe0bb0311e22b4a04c5ccae6603bbb65adaa9668d9ca6fc479960bb94546eaa1de75877ce1c40262d21894e966a4436128d9edf49d72f71df1d5c77ee0dc976e97c5740f07828dL
[+]((m>>72)<<72)=0x6696af2b1064c860a38acab284af83d0659c8a6f7aca6e147ecb5874a47108074608c619b5f001b03558da7e0c4546e3c8318ef70e2878000000000000000000L
[-]long_to_bytes(m).encode('hex')=

Challenge1

这是一道RSA。可以看出，e=3很小，而且已知明文m的高位。再结合题目提示，搜了一下coppersmith attack，找到了相关的攻击方法。

用sage运行下面代码可以得到x

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11


n = 0xadf364c509381f9f52fb2ed3676b47abd384af6814cb30c3480f562470eb6b1e30a93cf9493e98587a97b05725a3dd7af7a0a906bd1583e8ced2d1457954fb250b827002e148e8c58f7414f4351c51c62d538f1c10c0404c98d103db69dfdb02c5354871b179f854fcc4d2ec8d83855c764fa766578617888a6ec2668260fca3
e = 0x3
c = 0x9471a9e909eb5f3c933be2beed8a6b1515041110fca47701e64fa36adb8748a10ba939571e7904849f4c0666c5aed8cf7d8c4978cc5e18f564fe0bb0311e22b4a04c5ccae6603bbb65adaa9668d9ca6fc479960bb94546eaa1de75877ce1c40262d21894e966a4436128d9edf49d72f71df1d5c77ee0dc976e97c5740f07828d
m0 = 0x6696af2b1064c860a38acab284af83d0659c8a6f7aca6e147ecb5874a47108074608c619b5f001b03558da7e0c4546e3c8318ef70e2878000000000000000000

kbits = 72
PR.<x> = PolynomialRing(Zmod(n))
f = (x + m0)^e-c
x0 = f.small_roots(X=2^kbits, beta=1)[0]
print "x: %s" % hex(int(x0))
# x: 0xa57b2913fe55ef3e07L

sage跑出来得到x=0xa57b2913fe55ef3e07,所以 m=m0+x=5373001497805681660974356893930968872416039475236147621657898257609934038063399440369525242419102334020802927335719644878869760707333034805144275423018503

转成hex格式：answer1 = long_to_bytes(m).encode('hex')

answer1:6696af2b1064c860a38acab284af83d0659c8a6f7aca6e147ecb5874a47108074608c619b5f001b03558da7e0c4546e3c8318ef70e2878a57b2913fe55ef3e07

1
2
3
4


...
a1 = '6696af2b1064c860a38acab284af83d0659c8a6f7aca6e147ecb5874a47108074608c619b5f001b03558da7e0c4546e3c8318ef70e2878a57b2913fe55ef3e07'
r.recvuntil("long_to_bytes(m).encode('hex')=")
r.sendline(a1)

发过去得到Challenge2:

[++++++++++++++++]challenge 1 completed[++++++++++++++++]
[+]Generating challenge 2
[+]n=0x7936335485ce5ca4932825de04b1a7eb369e52787a5457bd115e5fc0639fd9df1e27ddb527a69c08ee4c52c3e457afa91277cb1af71c281e99858acc62b77075072036f58f0a0bb40f5ab3462a4f18873c3c681304153a8c17caac65682c34cc752d81b758091e457f1ae5f0759995c341e099089297212de519363c59c5cbL
[+]e=65537
[+]m=random.getrandbits(512)
[+]c=pow(m,e,n)=0x33e3d895b445ed22acc7ed9e771f27bc5314a671706ea95996a9f1ae8e9f1cc1e18effd0178d4953c30d9adb242aac8474fc666161c7fa12bcd2738d65435190882f0f7432fb5b57dddb94e7e047e499503921a1e9a5d664c03a7be770675b8482a65f63ba18c2d300c11c0a46d8d11334df50780af78d90d0b0eeba3f3c19L
[+]((p>>128)<<128)=0x1d59aab5e6eb96bffb7929c06715855cf2072f523ddb8efadc57d2707638a87ab3c68304b9aadd1b2fa897628eb73ea100000000000000000000000000000000L
[-]long_to_bytes(m).encode('hex')=

Challenge2

Challenge2给出了p的高位，类似Challenge1的攻击方法：

用sage运行下面的代码，可以算出p和q

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20


p4 = 0x1d59aab5e6eb96bffb7929c06715855cf2072f523ddb8efadc57d2707638a87ab3c68304b9aadd1b2fa897628eb73ea100000000000000000000000000000000
n = 0x7936335485ce5ca4932825de04b1a7eb369e52787a5457bd115e5fc0639fd9df1e27ddb527a69c08ee4c52c3e457afa91277cb1af71c281e99858acc62b77075072036f58f0a0bb40f5ab3462a4f18873c3c681304153a8c17caac65682c34cc752d81b758091e457f1ae5f0759995c341e099089297212de519363c59c5cb
pbits = 1024

kbits = 128
#print p4.nbits()

PR.<x> = PolynomialRing(Zmod(n))

f = x + p4
x0 = f.small_roots(X=2^kbits, beta=0.4)[0]
print "x: %s" %hex(int(x0))
p = p4+x0
print "p: ", hex(int(p))
assert n % p == 0
q = n/int(p)
print "q: ", hex(int(q))
#x: 0x41561c2cfeefbbdb5173e692bcf8149bL
#p: 0x1d59aab5e6eb96bffb7929c06715855cf2072f523ddb8efadc57d2707638a87ab3c68304b9aadd1b2fa897628eb73ea141561c2cfeefbbdb5173e692bcf8149bL
#q: 0x4213cd5675c8dd0cc02a72df2bf2a647618e993ad4689355809be2b28ae7eb248dece7215cc985bbc35c416a209fa02fd6b6a41a663dae315e9a09b61eaee91L

python解密

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13


# decryption
import gmpy2
from Crypto.Util.number import *

n = 0x7936335485ce5ca4932825de04b1a7eb369e52787a5457bd115e5fc0639fd9df1e27ddb527a69c08ee4c52c3e457afa91277cb1af71c281e99858acc62b77075072036f58f0a0bb40f5ab3462a4f18873c3c681304153a8c17caac65682c34cc752d81b758091e457f1ae5f0759995c341e099089297212de519363c59c5cb
e = 65537
c = 0x33e3d895b445ed22acc7ed9e771f27bc5314a671706ea95996a9f1ae8e9f1cc1e18effd0178d4953c30d9adb242aac8474fc666161c7fa12bcd2738d65435190882f0f7432fb5b57dddb94e7e047e499503921a1e9a5d664c03a7be770675b8482a65f63ba18c2d300c11c0a46d8d11334df50780af78d90d0b0eeba3f3c19
p = 0x1d59aab5e6eb96bffb7929c06715855cf2072f523ddb8efadc57d2707638a87ab3c68304b9aadd1b2fa897628eb73ea141561c2cfeefbbdb5173e692bcf8149b
q = 0x4213cd5675c8dd0cc02a72df2bf2a647618e993ad4689355809be2b28ae7eb248dece7215cc985bbc35c416a209fa02fd6b6a41a663dae315e9a09b61eaee91
d = gmpy2.invert(e,(p-1)*(q-1))
m = pow(c,d,n)
print long_to_bytes(m).encode('hex')
# d73f80417d7ee47efe2c521377cc0ec16d29352fb3a2b9b9e83a6fb1f28b1cd87bc04c9ce13822636c1b20b7a417557ea3bb0232d2ad24f1114b388279bef86e

answer2:d73f80417d7ee47efe2c521377cc0ec16d29352fb3a2b9b9e83a6fb1f28b1cd87bc04c9ce13822636c1b20b7a417557ea3bb0232d2ad24f1114b388279bef86e

发过去得到Challenge3:

[++++++++++++++++]challenge 2 completed[++++++++++++++++]
[+]Generating challenge 3
[+]n=0x5a3579c3f68f37e725e5a6c0bdb931dec0b7a34251726b08016f57c502536d9642f2bf59aa1fb3ff65705fff7715cae3b37bc21010d9b1be3acc56f6ecf4bd4a534582edfad4255b62d2fffe7413e4d953e64c519e5e1b03a4646c12d20cc7df29e1770446f629d1077f423bae85fe074fc6549a85e3471272cc91c5854a586dL
[+]e=3
[+]m=random.getrandbits(512)
[+]c=pow(m,e,n)=0x1d5e18525c42810ac350b13fc798c0559ba72a888a1d716be88506122387c07532e928b5de020bcf5cc09867b718b6621d78dfb303242853423182d7820892d70f7b16742011019bf8de5cdf64d1a3f9942a48733dd580db5f678fb2d61788942d85bbf3a025a681504250a44a15720091609491428cd09899489d8a958f9334L
[+]d=invmod(e,(p-1)*(q-1))
[+]d&((1<<512)-1)=0xc1e99958fb6b655de9ffc67a36acd32e767deda4c2afa68f620a7bc85516c937848443636c4bd1f747e3140d74d74a001f114e3d5ab52b7cd32ae49563d52cabL
[-]long_to_bytes(m).encode('hex')=

Challenge3

Challenge3是已知d的低512位，可以用下面的代码跑出完整的d：

 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


def partial_p(p0, kbits, n):
    PR.<x> = PolynomialRing(Zmod(n))
    nbits = n.nbits()

    f = 2^kbits*x + p0
    f = f.monic()
    roots = f.small_roots(X=2^(nbits//2-kbits), beta=0.3)  # find root < 2^(nbits//2-kbits) with factor >= n^0.3
    if roots:
        x0 = roots[0]
        p = gcd(2^kbits*x0 + p0, n)
        return ZZ(p)

def find_p(d0, kbits, e, n):
    X = var('X')

    for k in xrange(1, e+1):
        results = solve_mod([e*d0*X - k*X*(n-X+1) + k*n == X], 2^kbits)
        for x in results:
            p0 = ZZ(x[0])
            p = partial_p(p0, kbits, n)
            if p:
                return p


if __name__ == '__main__':
    n = 0x5a3579c3f68f37e725e5a6c0bdb931dec0b7a34251726b08016f57c502536d9642f2bf59aa1fb3ff65705fff7715cae3b37bc21010d9b1be3acc56f6ecf4bd4a534582edfad4255b62d2fffe7413e4d953e64c519e5e1b03a4646c12d20cc7df29e1770446f629d1077f423bae85fe074fc6549a85e3471272cc91c5854a586d
    e = 3
    d = 0xc1e99958fb6b655de9ffc67a36acd32e767deda4c2afa68f620a7bc85516c937848443636c4bd1f747e3140d74d74a001f114e3d5ab52b7cd32ae49563d52cab


    nbits = n.nbits()
    kbits = 511 # 512会报错，少一位不会有影响
    d0 = d & (2^kbits-1)
    #print "lower %d bits (of %d bits) is given" % (kbits, nbits)

    p = find_p(d0, kbits, e, n)
    print "found p: %d" % p
    q = n//p
    #print d
    print "d: %d" % inverse_mod(e, (p-1)*(q-1))
    #found p: 7527677592683240656202048149196344863757883303249163735651923022074130596046402450921827594154538151419573742516928825356598548833299431042669885685299777
    #d: 42231224191956848181438084632186072953302331993861866364057311410288942576942570594312268699255211558175084142719330633635175834062135979197689104469406043651001664135305458299916679988361869057693955476078346091880837971911423960414178470356730432063532728534550141146021794019360671359725906795943301557419

可得 d=42231224191956848181438084632186072953302331993861866364057311410288942576942570594312268699255211558175084142719330633635175834062135979197689104469406043651001664135305458299916679988361869057693955476078346091880837971911423960414178470356730432063532728534550141146021794019360671359725906795943301557419

python解密

1
2
3
4
5
6
7
8
9


# decryption
from Crypto.Util.number import *

n = 0x5a3579c3f68f37e725e5a6c0bdb931dec0b7a34251726b08016f57c502536d9642f2bf59aa1fb3ff65705fff7715cae3b37bc21010d9b1be3acc56f6ecf4bd4a534582edfad4255b62d2fffe7413e4d953e64c519e5e1b03a4646c12d20cc7df29e1770446f629d1077f423bae85fe074fc6549a85e3471272cc91c5854a586d
c = 0x1d5e18525c42810ac350b13fc798c0559ba72a888a1d716be88506122387c07532e928b5de020bcf5cc09867b718b6621d78dfb303242853423182d7820892d70f7b16742011019bf8de5cdf64d1a3f9942a48733dd580db5f678fb2d61788942d85bbf3a025a681504250a44a15720091609491428cd09899489d8a958f9334
d = 42231224191956848181438084632186072953302331993861866364057311410288942576942570594312268699255211558175084142719330633635175834062135979197689104469406043651001664135305458299916679988361869057693955476078346091880837971911423960414178470356730432063532728534550141146021794019360671359725906795943301557419
m = pow(c,d,n)
print long_to_bytes(m).encode('hex')
# c9a90c63a308112ff26cdb492becc6504667b567aa10fd0eb7209391e06312fdff9f21bb5c2bd1dd85ceede33894ab8c0485253954106662e0835991f22878c8

answer3:c9a90c63a308112ff26cdb492becc6504667b567aa10fd0eb7209391e06312fdff9f21bb5c2bd1dd85ceede33894ab8c0485253954106662e0835991f22878c8

发过去得到Chanllenge4:

[+]Generating challenge 4
[+]e=3
[+]m=random.getrandbits(512)
[+]n1=0x1ec2150f6e573adba01b2fe569ae7a0a2d02d82d788c6571ddfdb411af18666e7b64c47defa9e292682ad4e5b07d690e372cf5baad656fd222701d8acc68bf35646a4343c5aa88de2e8859abac9884a72c7a4525b813644f8f806465feb0a03b6d734995a7ed5a751a49e35d1c4bac592aefd91dee81f1fa9ac027fc3647d4ebL
[+]c1=pow(m,e,n1)=0xb081a5dbd2ab11925407875e217aa98754e944c4fda52a3341d1cb0bd4c6621a64757e119601918665c9877a33241c3d2483c00cf822dacf257617b6f0dc8de05d4b59ed5958f52dfce50b014d900ffe4d9e375824bc648adb72ecc4c4ecdc9f3be49fced7424d0ed696b6e98b1f6ddeaa79ebca0a592ba05bc11f98aa9ab1cL
[+]n2=0x1ca49ec4a77cfcfcbbf393e9772538c2adf63d0649226bb2aa357178c0a56f6481c39b7e96da90750bd73b067e8b52e2133bdba9f9bde8d868cd682826c2ee10a7a2958b887b07df1e05e38b515da13c4346b948831af253744e2b7cc90a9414fa5b4ada0327236ae29a7b010d8d9e6529491566e7fb71c91746e43bbd6ebe8fL
[+]c2=pow(m,e,n2)=0xf570f81b5fb68810dce6811a3a6c86c507e250ac903f412cd89bfc572652b9376b03105e410754422583d9a6522f607a9bcceb14357688a5b1eeafc87066b6304872091ff1760ad6a9d8d72d4cb64b51b559cbb8c7d790303d9fa491fc3f7d6e6bde370cff2c89528978fbfaf2724e63b3347e3cc0129e1b79056c0e9653deL
[+]n3=0x1f3497868702f5500fc66239f280303bb2129f10c3607ff4aca342ecdb1850bbaf9404b0e7533e6a6d0bdc71bb3336393da5bed3c6f7ab8c4e63b9e37c05a09a3c91269c3385b19759f36b9b1ebbcc4245a1c46ddedcbe80865701942e38cedc82b54630659772e8de8b33064fad6d5551c2e19ed8fa20541d2ca3818d5bc6e1L
[+]c3=pow(m,e,n3)=0x480830044351b6d4f86b9968e56a5a3b18b1f966851229f3a500f870d8a3ad364944c18701d67cf02f876a5ec353935ee4d3d7e313f0db0867da70a40458577764540ef60446c7a71577598498b89f2d706013936c9eb9b0f730a27d197dc64370a1e772fcca8ae59a56a0de0dbcbd0d92228df2efd3fb64dcf87a27e842c1eL
[-]long_to_bytes(m).encode('hex')=

Challenge4

对同一个明文m用不同的n加密，得到对应的c。参考了一下https://ctf-wiki.github.io/ctf-wiki/crypto/asymmetric/rsa/rsa_coppersmith_attack/#basic-broadcast-attack

直接用python脚本解密

 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


import gmpy2
from Crypto.Util.number import *

def extended_gcd(a, b):
    x,y = 0, 1
    lastx, lasty = 1, 0
    while b:
        a, (q, b) = b, divmod(a,b)
        x, lastx = lastx-q*x, x
        y, lasty = lasty-q*y, y
    return (lastx, lasty, a)

def chinese_remainder_theorem(items):
    N = 1
    for a, n in items:
        N *= n
    result = 0
    for a, n in items:
        m = N/n
        r, s, d = extended_gcd(n, m)
        if d != 1:
            N=N/n
            continue
            #raise "Input not pairwise co-prime"
        result += a*s*m
    return result % N, N

data = [
[7746689700893040824291073908984487674132321420840250688059125301575935759418750637999690589572187639945650351502582649863156880030127555457415541870665395028804956880265912918306068676856693427790912405019731868028587582848012343094928118397994021280696108254545964110134173070288166571086533607822847486748,
21599096121525963215557316112561113646221143112728562927607973420363830223708040429769755272190371667349304294919055324137744745528301546297067807691571131558095110007049745553149944758732551929530475066265184723821054813840404606123637193411942083043089418382023376922520103617891935920301099395488623875307L],
[673260672782515955389171354147303772448014115268774457046122114514898669333656893167859194197432848549755481414047191994952311448808295234777638477908671426188735585283728942025698486545607624202545395759562326915106928145017815802498819552280497700568639842099509150739681897018155152508410484741891314654L,
20113832050918989653429445827789428986112694771289943947910338993705357613941503784790448873374320297093329229625918482211939870007216051095047336162986443903532921024513525628636012366542117409388627596955594777407549224636967408960691508753899981488291577491937993570468967563919556590306691603290624278159L],
[3161411151052444762954350223015957668837925987156347523749788029303910797581062294153203942891473582739580216950627057877960755700191586205044119764475730077541167977228629115686785381376323556354595846120165570147272064022783618864185820557049936453743522700432998628323873509731854276013608510975824374814L,
21913203139510996100521755564162180829453124829662321846060794425270100007472765939886945744996939913019420912688703267887472785677939726045777674687211991311253557564073895764284409579045429233146298303641328249715120815570607287527729446764660590818326661597623466715532014948931595587362453627932319139553L]]

x, n = chinese_remainder_theorem(data)
m = int(gmpy2.iroot(x, 3)[0].digits())
print long_to_bytes(m).encode('hex')
# f41982eb32ff1cac23d5f9db26a5671aeca57c9b3f40465a1ec5b825aa699e0a9b5cc09d167de63f90c50ca55f79e4dc20c574aefeb2bbe076c4f3b91715849b

answer4:f41982eb32ff1cac23d5f9db26a5671aeca57c9b3f40465a1ec5b825aa699e0a9b5cc09d167de63f90c50ca55f79e4dc20c574aefeb2bbe076c4f3b91715849b

发过去得到Challenge5:

[++++++++++++++++]challenge 4 completed[++++++++++++++++]
[+]Generating challenge 5
[+]n=0x22218c4cfeb7501dd440f892feaa980706103d305466668f51d1a89f527cc51ed17dddafa69c14136b4d0405de606a48d0d1a8b56e1cb8865e545d9684b83f7d3b2a96d678d6a1ef80a515aa0972469d2370695fee2da3e3b51bfd5601547140102cf98858abff19caadffd75d4636a08b5a02a9510edcbe9cdc35de275bdde3L
[+]e=3
[+]m=random.getrandbits(512)
[+]c=pow(m,e,n)=0x1978dc15831038656b6935083b104e51adb0d6d4c1b2dd3025296d6ec60320a24edc00c57ba81c97355d4f32b2b5a3136da3ba26f9f3454b3fd572843d0618b3aadeec346f6df508ccd5ddb0cc38c45da6d2e7f4820ab44fe08e176ae5fc730c77473c6460fd3527b2d710bb9db08af768b005e2078f35103a5011cd9bacd06fL
[+]x=pow(m+1,e,n)=0x20ef9d6ac2cc12c45847f99c5004fb26d37e5d31862f89a4244095fbcf0a1f9b1276d98f02abd7dadc951fa8b218bea449c1b022732029b52e88492e6bbd787ea896e72ea425eb18ea616d454575f65e9380f028d23e35e714c3e91b0a1c38742c4a25c143fea6f60099771f74384c7256fee7309a841548ce0571fdb466fbe7L
[-]long_to_bytes(m).encode('hex')=

Challenge5

Challenge5中加密的两个明文m1,m2之间仅相差1，有Related Message Attack。

具体原理参见https://ctf-wiki.github.io/ctf-wiki/crypto/asymmetric/rsa/rsa_coppersmith_attack/#related-message-attack

脚本如下

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21


import gmpy2
from Crypto.Util.number import *

c1 = 0x20ef9d6ac2cc12c45847f99c5004fb26d37e5d31862f89a4244095fbcf0a1f9b1276d98f02abd7dadc951fa8b218bea449c1b022732029b52e88492e6bbd787ea896e72ea425eb18ea616d454575f65e9380f028d23e35e714c3e91b0a1c38742c4a25c143fea6f60099771f74384c7256fee7309a841548ce0571fdb466fbe7
c2 = 0x1978dc15831038656b6935083b104e51adb0d6d4c1b2dd3025296d6ec60320a24edc00c57ba81c97355d4f32b2b5a3136da3ba26f9f3454b3fd572843d0618b3aadeec346f6df508ccd5ddb0cc38c45da6d2e7f4820ab44fe08e176ae5fc730c77473c6460fd3527b2d710bb9db08af768b005e2078f35103a5011cd9bacd06f
n = 0x22218c4cfeb7501dd440f892feaa980706103d305466668f51d1a89f527cc51ed17dddafa69c14136b4d0405de606a48d0d1a8b56e1cb8865e545d9684b83f7d3b2a96d678d6a1ef80a515aa0972469d2370695fee2da3e3b51bfd5601547140102cf98858abff19caadffd75d4636a08b5a02a9510edcbe9cdc35de275bdde3
a = 1
b = 1


def getmessage(a, b, c1, c2, n):
    b3 = gmpy2.powmod(b, 3, n)
    part1 = b * (c1 + 2 * c2 - b3) % n
    part2 = a * (c1 - c2 + 2 * b3) % n
    part2 = gmpy2.invert(part2, n)
    return part1 * part2 % n


m = getmessage(a, b, c1, c2, n)
print long_to_bytes(int(m)).encode('hex')
# b4c2daf34f0eec971c54056932adaecf648851d4e56cdf5ab8ba8cdece730234d524923eed43cc4cd0956d742ee01bb06166e1abebe37c1cf01a58125327e4d7

answer5:b4c2daf34f0eec971c54056932adaecf648851d4e56cdf5ab8ba8cdece730234d524923eed43cc4cd0956d742ee01bb06166e1abebe37c1cf01a58125327e4d7

发过去，可以得到Challenge6:

[++++++++++++++++]challenge 5 completed[++++++++++++++++]
[+]Generating challenge 6
[+]n=0xbadd260d14ea665b62e7d2e634f20a6382ac369cd44017305b69cf3a2694667ee651acded7085e0757d169b090f29f3f86fec255746674ffa8a6a3e1c9e1861003eb39f82cf74d84cc18e345f60865f998b33fc182a1a4ffa71f5ae48a1b5cb4c5f154b0997dc9b001e441815ce59c6c825f064fdca678858758dc2cebbc4d27L
[+]d=random.getrandbits(1024*0.270)
[+]e=invmod(d,phin)
[+]hex(e)=0x11722b54dd6f3ad9ce81da6f6ecb0acaf2cbc3885841d08b32abc0672d1a7293f9856db8f9407dc05f6f373a2d9246752a7cc7b1b6923f1827adfaeefc811e6e5989cce9f00897cfc1fc57987cce4862b5343bc8e91ddf2bd9e23aea9316a69f28f407cfe324d546a7dde13eb0bd052f694aefe8ec0f5298800277dbab4a33bbL
[+]m=random.getrandbits(512)
[+]c=pow(m,e,n)=0xe3505f41ec936cf6bd8ae344bfec85746dc7d87a5943b3a7136482dd7b980f68f52c887585d1c7ca099310c4da2f70d4d5345d3641428797030177da6cc0d41e7b28d0abce694157c611697df8d0add3d900c00f778ac3428f341f47ecc4d868c6c5de0724b0c3403296d84f26736aa66f7905d498fa1862ca59e97f8f866cL
[-]long_to_bytes(m).encode('hex')=

Challenge6

Challenge6的私钥d小于N^0.292（题目中给出的是<0.270），有Boneh and Durfee attack:

修改https://github.com/mimoo/RSA-and-LLL-attacks/blob/master/boneh_durfee.sage 中的部分数据,再用sage跑一下可以得出下面结果

=== solution found ===
private key found: 776765455081795377117377680209510234887230129318575063382634593357724998207571
=== 0.605096101761 seconds ===

python解密

1
2
3
4
5
6
7
8
9


# decryption
from Crypto.Util.number import *

n = 0xbadd260d14ea665b62e7d2e634f20a6382ac369cd44017305b69cf3a2694667ee651acded7085e0757d169b090f29f3f86fec255746674ffa8a6a3e1c9e1861003eb39f82cf74d84cc18e345f60865f998b33fc182a1a4ffa71f5ae48a1b5cb4c5f154b0997dc9b001e441815ce59c6c825f064fdca678858758dc2cebbc4d27
c = 0xe3505f41ec936cf6bd8ae344bfec85746dc7d87a5943b3a7136482dd7b980f68f52c887585d1c7ca099310c4da2f70d4d5345d3641428797030177da6cc0d41e7b28d0abce694157c611697df8d0add3d900c00f778ac3428f341f47ecc4d868c6c5de0724b0c3403296d84f26736aa66f7905d498fa1862ca59e97f8f866c
d = 776765455081795377117377680209510234887230129318575063382634593357724998207571
m = pow(c,d,n)
print long_to_bytes(m).encode('hex')
# 6b3bb0cdc72a7f2ce89902e19db0fb2c0514c76874b2ca4113b86e6dc128d44cc859283db4ca8b0b5d9ee35032aec8cc8bb96e8c11547915fc9ef05aa2d72b28

answer6：6b3bb0cdc72a7f2ce89902e19db0fb2c0514c76874b2ca4113b86e6dc128d44cc859283db4ca8b0b5d9ee35032aec8cc8bb96e8c11547915fc9ef05aa2d72b28

发过去得到flag:

[++++++++++++++++]challenge 6 completed[++++++++++++++++]
[++++++++++++++++]all clear[++++++++++++++++]
flag{21fd94b1604569b12ac238ad755b03262fa371c70f6775999b84d2dcfc05cddc}

final

最终简化版python脚本：

 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


from Crypto.Util.number import *
import hashlib
from pwn import *

token = "fd53e2e6fb3fc3de6539bbc870e605ab"

#context.log_level = 'debug'
r = remote('119.3.245.36', 12345)
r.recvuntil("hexdigest()=")
digest = r.recvline()[:-1]
r.recvuntil("encode('hex')=")
pre = r.recvline()[:-1]

#print bytes(digest)
#print bytes(pre)

def fuck(pre, d):
    for i in range(64*256*256, 256 * 256 * 256):
        guess = (pre + long_to_bytes(i, 3).encode('hex')).decode('hex')
        if hashlib.sha256(guess).hexdigest() == d:
            result = guess
            print 'find'
            return guess

skr = fuck(pre,digest)
r.recvuntil("encode('hex')=")
r.sendline(skr.encode('hex'))

r.recvuntil("teamtoken:")
r.sendline(token)

a1 = '6696af2b1064c860a38acab284af83d0659c8a6f7aca6e147ecb5874a47108074608c619b5f001b03558da7e0c4546e3c8318ef70e2878a57b2913fe55ef3e07'
a2 = 'd73f80417d7ee47efe2c521377cc0ec16d29352fb3a2b9b9e83a6fb1f28b1cd87bc04c9ce13822636c1b20b7a417557ea3bb0232d2ad24f1114b388279bef86e'
a3 = 'c9a90c63a308112ff26cdb492becc6504667b567aa10fd0eb7209391e06312fdff9f21bb5c2bd1dd85ceede33894ab8c0485253954106662e0835991f22878c8'
a4 = 'f41982eb32ff1cac23d5f9db26a5671aeca57c9b3f40465a1ec5b825aa699e0a9b5cc09d167de63f90c50ca55f79e4dc20c574aefeb2bbe076c4f3b91715849b'
a5 = 'b4c2daf34f0eec971c54056932adaecf648851d4e56cdf5ab8ba8cdece730234d524923eed43cc4cd0956d742ee01bb06166e1abebe37c1cf01a58125327e4d7'
a6 = '6b3bb0cdc72a7f2ce89902e19db0fb2c0514c76874b2ca4113b86e6dc128d44cc859283db4ca8b0b5d9ee35032aec8cc8bb96e8c11547915fc9ef05aa2d72b28'

r.recvuntil("long_to_bytes(m).encode('hex')=")
r.sendline(a1)
r.recvuntil("long_to_bytes(m).encode('hex')=")
r.sendline(a2)
r.recvuntil("long_to_bytes(m).encode('hex')=")
r.sendline(a3)
r.recvuntil("long_to_bytes(m).encode('hex')=")
r.sendline(a4)
r.recvuntil("long_to_bytes(m).encode('hex')=")
r.sendline(a5)
r.recvuntil("long_to_bytes(m).encode('hex')=")
r.sendline(a6)

r.interactive()

Reference

https://ctf-wiki.github.io/ctf-wiki/crypto/asymmetric/rsa/rsa_coppersmith_attack/ https://github.com/mimoo/RSA-and-LLL-attacks https://code.felinae98.cn/ctf/crypto/rsa%E5%A4%A7%E7%A4%BC%E5%8C%85%EF%BC%88%E4%BA%8C%EF%BC%89coppersmith-%E7%9B%B8%E5%85%B3/ https://err0rzz.github.io/2017/11/14/CTF%E4%B8%ADRSA%E5%A5%97%E8%B7%AF/ https://link.springer.com/content/pdf/10.1007/3-540-49649-1_3.pdf

强网先锋-辅助

下载附件，打开得到加密脚本：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23


flag=open("flag","rb").read()

from Crypto.Util.number import getPrime,bytes_to_long
p=getPrime(1024)
q=getPrime(1024)
e=65537
n=p*q
m=bytes_to_long(flag)
c=pow(m,e,n)
print c,e,n

p=getPrime(1024)
e=65537
n=p*q
m=bytes_to_long("1"*32)
c=pow(m,e,n)
print c,e,n

'''
output:
2482083893746618248544426737023750400124543452082436334398504986023501710639402060949106693279462896968839029712099336235976221571564642900240827774719199533124053953157919850838214021934907480633441577316263853011232518392904983028052155862154264401108124968404098823946691811798952747194237290581323868666637357604693015079007555594974245559555518819140844020498487432684946922741232053249894575417796067090655122702306134848220257943297645461477488086804856018323986796999103385565540496534422406390355987976815450744535949785073009043007159496929187184338592859040917546122343981520508220332785862546608841127597 65537 14967030059975114950295399874185047053736587880127990542035765201425779342430662517765063258784685868107066789475747180244711352646469776732938544641583842313791872986357504462184924075227433498631423289187988351475666785190854210389587594975456064984611990461126684301086241532915267311675164190213474245311019623654865937851653532870965423474555348239858021551589650169602439423841160698793338115204238140085738680883313433574060243600028500600824624358473403059597593891412179399165813622512901263380299561019624741488779367019389775786547292065352885007224239581776975892385364446446185642939137287519945974807727
3829060039572042737496679186881067950328956133163629908872348108160129550437697677150599483923925798224328175594483217938833520220087230303470138525970468915511111320396185482564783975435346354440035776909781158407636044986403819840648379609630039348895415045723208843631191252142600667607807479954194447237061080618370787672720344741413537975922184859333432197766580150534457001196765621678659952108010596273244230812327182786329760844037149719587269632133595149294067490955644893402708720284179715002149224068928828656515326446881791228638008572889331511945042911372915003805505412099102954073299010951896955362470 65537 14624662628725820618622370803948630854094687814338334827462870357582795291844925274690253604919535785934208081825425541536057550227048399837243392490762167733083030368221240764693694321150104306044125934201699430146970466657410999261630825931178731857267599750324918610790098952520113593130245010530961350592735239454337631927669542026935873535964487595433984902529960726655481696404006628917922241666148082741874033756970724357470539589848548704573091633917869387239324447730587545472564561496724882799495186768858324490838169123077051890332313671220385830444331578674338014080959653201802476516237464651809255679979
'''

可以看出，用同一个p生成了两个不同的n1,n2来加密,那么肯定有gcd(n1,n2)=p。

脚本如下:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13


from Crypto.Util.number import *
import gmpy2

n1 = 14967030059975114950295399874185047053736587880127990542035765201425779342430662517765063258784685868107066789475747180244711352646469776732938544641583842313791872986357504462184924075227433498631423289187988351475666785190854210389587594975456064984611990461126684301086241532915267311675164190213474245311019623654865937851653532870965423474555348239858021551589650169602439423841160698793338115204238140085738680883313433574060243600028500600824624358473403059597593891412179399165813622512901263380299561019624741488779367019389775786547292065352885007224239581776975892385364446446185642939137287519945974807727
n2 = 14624662628725820618622370803948630854094687814338334827462870357582795291844925274690253604919535785934208081825425541536057550227048399837243392490762167733083030368221240764693694321150104306044125934201699430146970466657410999261630825931178731857267599750324918610790098952520113593130245010530961350592735239454337631927669542026935873535964487595433984902529960726655481696404006628917922241666148082741874033756970724357470539589848548704573091633917869387239324447730587545472564561496724882799495186768858324490838169123077051890332313671220385830444331578674338014080959653201802476516237464651809255679979
e1 = 65537
c1 = 2482083893746618248544426737023750400124543452082436334398504986023501710639402060949106693279462896968839029712099336235976221571564642900240827774719199533124053953157919850838214021934907480633441577316263853011232518392904983028052155862154264401108124968404098823946691811798952747194237290581323868666637357604693015079007555594974245559555518819140844020498487432684946922741232053249894575417796067090655122702306134848220257943297645461477488086804856018323986796999103385565540496534422406390355987976815450744535949785073009043007159496929187184338592859040917546122343981520508220332785862546608841127597
p = gmpy2.gcd(n1,n2)
q1 = n1 / p
d1 = gmpy2.invert(e1,(p-1)*(q1-1))
m1 = pow(c1,d1,n1)
print long_to_bytes(m1)
# flag{i_am_very_sad_233333333333}