## Still Broken Box (Crypto, 400p)
###ENG[PL](#pl-version)
The task was very similar to https://github.com/p4-team/ctf/tree/master/2016-09-16-csaw/broken_box but this time we could not recover all the bits of the key.We could get only some fraction of LSB bits, but there is a theorem stating that we need only n/4 of the LSB bits to recover full key, as long as `e` is reasonably small.
We used the same code as previously to mine faulty signatures and then to recover some bits of `d`.Then we applited mentioned theorem to recover the whole key.The recovery description can be found here: http://honors.cs.umd.edu/reports/lowexprsa.pdf
We used the sage code:
```sage# partial_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__':    print "start!"    n = 123541066875660402939610015253549618669091153006444623444081648798612931426804474097249983622908131771026653322601466480170685973651622700515979315988600405563682920330486664845273165214922371767569956347920192959023447480720231820595590003596802409832935911909527048717061219934819426128006895966231433690709    e = 97
    beta = 0.5    epsilon = beta^2/7
    nbits = n.nbits()    kbits = 300    d0 = 48553333005218622988737502487331247543207235050962932759743329631099614121360173210513133    print "lower %d bits (of %d bits) is given" % (kbits, nbits)
    p = find_p(d0, kbits, e, n)    print "found p: %d" % p```
Which gave us the modulus factor `p`.With that we simply decrypted the flag using:
```pythonimport gmpy2
def long_to_bytes(flag):    flag = str(hex(flag))[2:-1]    return "".join([chr(int(flag[i:i + 2], 16)) for i in range(0, len(flag), 2)])
p = 11508259255609528178782985672384489181881780969423759372962395789423779211087080016838545204916636221839732993706338791571211260830264085606598128514985547n = 123541066875660402939610015253549618669091153006444623444081648798612931426804474097249983622908131771026653322601466480170685973651622700515979315988600405563682920330486664845273165214922371767569956347920192959023447480720231820595590003596802409832935911909527048717061219934819426128006895966231433690709q = n/pe = 97
assert p*q == nd = gmpy2.invert(e, (p-1)*(q-1))flag = 96324328651790286788778856046571885085117129248440164819908629761899684992187199882096912386020351486347119102215930301618344267542238516817101594226031715106436981799725601978232124349967133056186019689358973953754021153934953745037828015077154740721029110650906574780619232691722849355713163780985059673037pt = pow(flag, d, n)print(long_to_bytes(pt))```
and got `flag{n3v3r_l34k_4ny_51n6l3_b17_0f_pr1v473_k3y}`
###PL version
Zadanie było bardzo podobne do https://github.com/p4-team/ctf/tree/master/2016-09-16-csaw/broken_box ale tym razem nie mogliśmy odzyskać wszystkich bitów klucza.Mogliśmy dostać jedynie część niskich bitów klucza, niemniej istnieje twierdzenie mówiące że wystarczy nam n/4 najniższych bitów do odzyskania całego klucza, o ile `e` jest względnie małe.
Użyliśmy tego samego kodu co wcześniej aby pobrać błędne sygnatury i odzyskać niskie bity `d`.Następnie zastosowaliśmy wspomniane twierdzenie aby odzyskać cały klucz.Opis mechanizmu odzyskiwania klucza można znaleźć tu: http://honors.cs.umd.edu/reports/lowexprsa.pdf
Użyliśmy kodu:
```sage# partial_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__':    print "start!"    n = 123541066875660402939610015253549618669091153006444623444081648798612931426804474097249983622908131771026653322601466480170685973651622700515979315988600405563682920330486664845273165214922371767569956347920192959023447480720231820595590003596802409832935911909527048717061219934819426128006895966231433690709    e = 97
    beta = 0.5    epsilon = beta^2/7
    nbits = n.nbits()    kbits = 300    d0 = 48553333005218622988737502487331247543207235050962932759743329631099614121360173210513133    print "lower %d bits (of %d bits) is given" % (kbits, nbits)
    p = find_p(d0, kbits, e, n)    print "found p: %d" % p```
Który dał nam czynnik `p` modulusa.Następnie po prostu zdeszyfrowaliśmy flagę:
```pythonimport gmpy2
def long_to_bytes(flag):    flag = str(hex(flag))[2:-1]    return "".join([chr(int(flag[i:i + 2], 16)) for i in range(0, len(flag), 2)])
p = 11508259255609528178782985672384489181881780969423759372962395789423779211087080016838545204916636221839732993706338791571211260830264085606598128514985547n = 123541066875660402939610015253549618669091153006444623444081648798612931426804474097249983622908131771026653322601466480170685973651622700515979315988600405563682920330486664845273165214922371767569956347920192959023447480720231820595590003596802409832935911909527048717061219934819426128006895966231433690709q = n/pe = 97
assert p*q == nd = gmpy2.invert(e, (p-1)*(q-1))flag = 96324328651790286788778856046571885085117129248440164819908629761899684992187199882096912386020351486347119102215930301618344267542238516817101594226031715106436981799725601978232124349967133056186019689358973953754021153934953745037828015077154740721029110650906574780619232691722849355713163780985059673037pt = pow(flag, d, n)print(long_to_bytes(pt))```
i dostalismy `flag{n3v3r_l34k_4ny_51n6l3_b17_0f_pr1v473_k3y}