CSAW’18 CTF Qualification: lowe
|CSAW’18 CTF Qualification||lowe||Crypto||200||114|
I personally prefer Home Depot
XOR Passes are the easiest way to use numbers to encrypt!
By Kris Kwiatkowski, Cloudflare
The key is encrypted using RSA with a small exponent (3), The key is small and no padding is applied so the cube root can be calculated to retrieve the key. Finally, a xor with the file gives the flag.
Finding the key
Given the title of this challenge and the small amount of informations, I deduced that the key was encrypted without padding.
The RSA public exponent used is 3.
If the key (pk) is small enough,
k=pow(pk,e,n) < n so computing the cube root of k would retrieve the original key.
But it seemed like pk was a bit too big, therefore we can’t deduce pk by computing the cube root of k but we can try with k+i*n because
k+(i*n) % n == k
# -*- coding: utf-8 -*- from Crypto.PublicKey import RSA import gmpy2 def ntos(x): n = hex(x)[2:].rstrip("L") if len(n)%2 != 0: n = "0"+n return n.decode("hex") def ston(x): n = x.encode("hex") return int(n,16) def strxor(a,k): s = "" for i in range(len(a)): s += chr(ord(a[i])^ord(k[i%len(k)])) return s ke = RSA.importKey(open("pubkey.pem","r").read().strip()) e = ke.e n = ke.n f = open("file.enc","r").read().strip().decode("base64") f = ston(f) k = int(open("key.enc","r").read().strip()) i = 0 r = gmpy2.iroot(k+(i*n), 3) while r<n: if pow(r,3,n) == k: print strxor(ntos(f),ntos(r)) break i += 1 r = gmpy2.iroot(k+(i*n), 3)