We’ve got a screenshot of some encryption, here’s the text transcribed.
Please say what’s there.
Summary: a couple of modular equations
Here’s the main encryption code:
cP = 259657535847310621105775666783538475891724987952731030269713987086100108465413941035137526396175451420572212604838340594322339588578435400099313081250171510597356813901500906284453570906219085080331647642107590625 cM = 9457376783 cRM = 7056938483983022714076066148678069033320572870812680395740537142075738471625159533936829320058006391183726287524907743597839660144443470421424317622383956419588604161584917677459583528523728694375 s2n str = foldl (\acc ch -> acc * 256 + toInteger (ord(ch))) (0) str encrypt msg key = encrypt_number (s2n $ chr(1) : msg) key encrypt_number 0 (k1, k2, k3) = do return [] encrypt_number num (k1, k2, k3) = let (next_num, x) = divMod num cM enc = (k1 * x * x + k2 * x + k3) `mod` cM in do pad <- getStdRandom (randomR (2, cP - 2)) t <- encrypt_number next_num (k1, k2, k3) return ( ((enc + pad * cRM) `mod` cP) : t ) |
First of all, the message is prepended with chr(1) and is converted to number.
Then, a message is split into “digits” (blocks) in base cM (small modulo).
Then, a quadratic polynomial with keys as coefficients is evaluated at the message digit modulo small number:
enc = (k1 * x * x + k2 * x + k3) `mod` cM |
Finally, it’s “padded” with some random modulo a large number and then it recursively encrypts next digits (blocks).
return ( ((enc + pad * cRM) `mod` cP) : t ) |
If it’s a real random, how we can recover enc? If pad * cRM takes all the values modulo cP than it’s one time pad and we have nothing. Actually, it can take fewer values if gcd(cRM, cP) != 1. Think about similar modulus: x + 10 * rand() (mod 100) – you will always be able to recover x mod 10 from that. So, let’s look at gcd:
In [1]: gcd(cRM, cP) Out[1]: 9457408125L |
Hey, it’s just a bit larget than cM (small modulus)! Then we can simply recover enc:
enc = ret % gcd(cRM, cP) |
What next? We need to recover all x’s. A good idea is first to recover the keys. Since we have one plaintext-ciphertext pair (“You’ll never read that message!” and the numbers after it), it’s not hard. We need only 3 blocks and then we have a linear equations system. Let’s do it in Sage:
# k1 *x1^2 + k2 *x1 + k3 *1 = ciphertext # r1 = [pow(x1, 2, cM), x1, 1, a] # r2 = [pow(x2, 2, cM), x2, 1, b] # r3 = [pow(x3, 2, cM), x3, 1, c] M = MatrixSpace(GF(9457376783), 3, 4) A = M([ 4626884051L, 1285240980L, 1, 4901032366L, 3822006142L, 481260965L, 1, 1843386599L, 2228392248L, 6183149994L, 1, 457166565L ]) print A.echelon_form() # Result: [ 1 0 0 6080683101] [ 0 1 0 4432421868] [ 0 0 1 5118250421] |
So keys are 6080683101, 4432421868 and 5118250421. Now, the final part: decrypt the unknown message. To do it we need to solve some modular quadratic equations in form k1 * x^2 + k2 * x + k3 == a (mod cM). We need to represent it in form: (x + c)^2 == b (mod cM) and then extract modular square roots.
If x is not zero, then there will be two roots: we need to choose one of them. The right way is to bruteforce that choices one by one, starting from highest: we’ll see some part of the valid text if the choice is valid:
"\x01That wuC\x11\x96\xf6\x1f\xa6l\x13\xfd\x8d\x1a\x02y\x08u\xc5?.6\"\xb9\x84%"\x18\xceFas\xeb9\x82p\xa0\xb0\xe8`m=ei\xb4M\xf2\x8a\xc2g,\xfb\xb5\xde\xb7M" "\x01That was tX\x7f\x92\x0b[\xa2\xfb\\s\xee\x10"\xe3\xabw\xf9\x14\xf9\x99\xd3\xf4\xc0x\xd6\xac\xcbCm\xf9\xfdN$\xcd\x98\xaa\xacd\x04f*x\xc5\r\xfa\xec\xb2zZx\xe9" ... |
But the easiest way is to bruteforce them all at once (211 total) and print the one which has all chars printable:
from itertools import product from libnum import * pairs = [] for a in CT: a = a % gcd(cRM, cP) c = (k2 * invmod(k1, cM) * invmod(2, cM)) % cM val = ((a - k3) * invmod(k1, cM) + c * c) % cM x, y = tuple(sqrtmod(val, {cM: 1})) x = (x - c) % cM y = (y - c) % cM pairs.append((x, y)) for extr in product(*pairs): n = 0 for a in reversed(extr): n *= m n += a s = n2s(n) if count_printable(s) > len(s) - 3: print `s` |
And the flag is:
'\x01That was too easy, right? the flag is the 6th eleeeet prime.' |
Wait, where’s my flag? :S
Ahh, eleeeet prime. It should be a prime like 31337? eleeeet points to form 3133…337. Let’s find such:
from libnum import * for i in xrange(20000): x = int("31" + "3" * i + "7") if prime_test(x): print "GOOD", i, x |
$ py gen.py GOOD 0 317 GOOD 1 3137 GOOD 2 31337 GOOD 4 3133337 GOOD 9 313333333337 GOOD 22 3133333333333333333333337 GOOD 28 3133333333333333333333333333337 GOOD 55 3133333333333333333333333333333333333333333333333333333337 GOOD 67 3133333333333333333333333333333333333333333333333333333333333333333337 ... |
Ah, the 6th one should be the one with 55 threes in it: 3133333333333333333333333333333333333333333333333333333337.
