###### tags: `writeups`
# Writeup for copperstudy in 2019强网杯
## Description
## 0x00 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。
选择**爆破**:
```python
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')=
```
## 0x01 Challenge1
这是一道RSA。可以看出，e=3很小，而且已知明文m的高位。再结合题目提示，搜了一下*coppersmith attack*，找到了相关的攻击方法。
用sage运行下面代码可以得到`x`
```sage
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
```python
...
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')=
```
## 0x02 Challenge2
*Challenge2*给出了p的高位，类似*Challenge1*的攻击方法：
用sage运行下面的代码，可以算出p和q
```sage
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解密
```python
# 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')=
```
## 0x03 Challenge3
*Challenge3*是已知d的低512位，可以用下面的代码跑出完整的d：
```sage
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解密
```python
# 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')=
```
## 0x04 Challenge4
对同一个明文m用不同的n加密，得到对应的c。
参考了一下[https://ctf-wiki.github.io/ctf-wiki/crypto/asymmetric/rsa/rsa_coppersmith_attack/#basic-broadcast-attack](https://ctf-wiki.github.io/ctf-wiki/crypto/asymmetric/rsa/rsa_coppersmith_attack/#basic-broadcast-attack)
直接用python脚本解密
```python
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')=
```
## 0x05 Challenge5
*Challenge5*中加密的两个明文m1,m2之间仅相差1，有*Related Message Attack*。
具体原理参见[https://ctf-wiki.github.io/ctf-wiki/crypto/asymmetric/rsa/rsa_coppersmith_attack/#related-message-attack](https://ctf-wiki.github.io/ctf-wiki/crypto/asymmetric/rsa/rsa_coppersmith_attack/#related-message-attack)
脚本如下
```python
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')=
```
## 0x06 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](https://github.com/mimoo/RSA-and-LLL-attacks/blob/master/boneh_durfee.sage)中的部分数据,再用sage跑一下可以得出下面结果
```
=== solution found ===
private key found: 776765455081795377117377680209510234887230129318575063382634593357724998207571
=== 0.605096101761 seconds ===
```
python解密
```python
# 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}
```
## 0x07 final
最终简化版python脚本：
```python
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()
```
## 0x08 Reference
[https://ctf-wiki.github.io/ctf-wiki/crypto/asymmetric/rsa/rsa_coppersmith_attack/](https://ctf-wiki.github.io/ctf-wiki/crypto/asymmetric/rsa/rsa_coppersmith_attack/)
[https://github.com/mimoo/RSA-and-LLL-attacks](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://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://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](https://link.springer.com/content/pdf/10.1007/3-540-49649-1_3.pdf)
Sign in with Wallet
Connect another wallet