Dan Boneh loves to improve cryptosystems, you should be loving breaking them?
Files given:
def encrypt(m, pubkey):
p, u, v, w = pubkey
assert m < p
r, s = [getRandomRange(1, p) for _ in '01']
ca = pow(u, r, p)
cb = pow(v, s, p)
cc = m * pow(w, r + s, p) % p
enc = (ca, cb, cc)
return enc
This cryptosystem uses the following encryption function, which assumes it is difficult to obtain \(r,s\) as you need to solve the discrete log. However, the prime is fixed in the server, and when computing the factors of \(p-1\), we see lots of small prime factors:
sage: factor(87266586046690087215050730923796275957558114912797348399204944378951121006508714028943628179912845791668792419785918249482052260983866552397369929
....: 495287-1)
2 * 3 * 433 * 13499 * 126517 * 839897 * 858859 * 1349177 * 1984247 * 2191159 * 51063421 * 58465243 * 66744157 * 2269425049 * 4967282609 * 9664300447 * 80875539889 * 154680558367 * 182464819549 * 213517431119 * 439319464013
This tells us that the discrete log in this case is actually quite easy and we can easily solve for \(m\) by solving for \(r,s\) first using discrete log.
Solution at solve.sage
Flag:
CCTF{1mPr0v3D_CrYp7O_5yST3m_8Y_Boneh_Boyen_Shacham!}