CNAS/MPS CTF 2017: Integrity Protection

Points: 200

应用系统传输加密用到了RSA，但传输时数据被破坏，请还原

PutResourceHere

Write-up

题面只给了e, n, m三个变量，据描述m的其中一位被翻转了。看了一下n和m都是2048位的，爆破无望。

不过还是尝试爆破pq，挂了一会儿还是无解，就先跳过了这题。

后来官方hint有源码泄漏，从index.jsp.bak直接拿到了pq（汗），于是就可以直接求出d，然后枚举m的哪一位翻转了。判断合法条件为pow(c, d, n).to_bytes结果全部为可打印字符，求出来就成功了。

def exgcd(m, n):
    x, y, x1, y1 = 0, 1, 1, 0
    while m % n:
        x, x1 = x1 - m // n * x, x
        y, y1 = y1 - m // n * y, y
        m, n = n, m % n
    return n, x, y


def modinv(m, n):
    gcd, inv = exgcd(m, n)[:2]
    return inv % (n // gcd)


def printable(s):
    for c in s:
        if not (c == 0 or 0x20 <= c < 0x80):
            return False
    return True

e = 7722201040496927440398665634941400106453989998233299674127196639118150684088767191146253946083658825501603635794946247652564630812120343905281675334758639

p = 0xDBAA7FC35A0079942BED85F1F05E1D92BECB09D2B8B653B18D36C0B5EFB0FC5D2699A97B8D0827EA1BB505FE006608588A9697E019B4578AEA3E384025AE0081DA4F33745A870D81E7CF1CB617969414D494A6C181672A74B2B3AF5ED8783EA45B2AB9315B556885E65E31443BBC5ECA3293A37BD7E2F87251C2F97606419383

q = 0xE397A88E9182F29B150FA96EFBF2C360E8559F1CFA859B13763E526EC9EE0A6FA67A4BAB0F21A84435600AC04AB810F679694F8C30A189C46F7C189E8D8F74EA408087DA1E60A90AB8CE4DDD096D90CE2AE4CA100D11B4817BE5C22C3BAECACD9BD7699FBBB4AA82B6F94554C5D6897ACDDB28C7FF07F0DB2ACC2FACADE2E403

n = 24653117200760292939773434010618513410031938287886819061013345831017593463397572709612272664325060594029520243926035067734938113172164041663572254826339203055932796262730652327215257954852380178166215039029222621686154147795103578170736707286664456749001194333781010154263900757774999156860458706911901631002768056055354313036875669464278228827028182723754277734246261351278711938317166177175716077241828239321175802341287825882430471185985370997066743278545127995524175389974197201451318882068803566427388140252977517618180502525892931448459949050571606048563552829150043842147735808896619368445503807875917835626121

m = 3967696188220181221606245068826389291642645897428261128353959264521006777986784357090333004999885774799189235734526471329177507718869246801446025559728321645411636892475497023958364714363881422533169135743720240149647435491380594490328882421959525216783534469727671308505839559563405900160931209379547377459628416184721976869094894444625958790254840640732216112840797452463678524528236774105061383058388273155770427770217492678817210970627611164026254791269496639973010875660833131381620295293779841979392091266586380376470219964657148152899038619895485472986080576015065275767659920087450206938203303897953670368097

r = (p - 1) * (q - 1)

d = modinv(e, r)

for i in range(2048):
    c = m ^ 1 << i
    s = pow(c, d, n).to_bytes(256, 'big')
    if printable(s):
        print(s)

可能翻转的意思是异或，所以循环异或，然后这个m为什么是c我也不太明白