Skip to content

Instantly share code, notes, and snippets.

@niklasb
Created April 20, 2015 15:00
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save niklasb/ac28640c9ff74bb1f08a to your computer and use it in GitHub Desktop.
Save niklasb/ac28640c9ff74bb1f08a to your computer and use it in GitHub Desktop.
Solution for 'lazy' in PlaidCTF 2015
from ast import literal_eval
ciphertext = int(open("ciphertext.txt", 'rb').read())
pubkey = literal_eval(open("pubkey.txt", 'rb').read())
def mat(pubkey, ciphertext, B):
n = len(pubkey)
A = Matrix(ZZ,n+1,n+1)
for i in range(n):
A[i,i] = 1
for i in range(n):
A[i,n] = B*pubkey[i]
A[n,n] = -B*ciphertext
return A
def check(v):
return all(0 <= x <= 1 for x in v)
n = len(pubkey)
B = int(ceil(sqrt(n * 2**n)))
A = mat(pubkey, ciphertext, B)
print "Computing LLL..."
res = A.LLL()
sol = res[-3]
offset = 1
bits = [int(bool(x)) for x in sol][::-1][offset:]
res = ""
for i in range(0, len(bits), 8):
b = "".join(str(x) for x in bits[i:i+8])
b = "01" + b[2:]
res += chr(int(b,2))
print "Flag:", res
@abhikandoi2000
Copy link

What does B stand for here?
Also, I tried for B = 1, didn't work.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment