Dan Boneh loves to improve cryptosystems, you should be loving breaking them?

Files given:

• linda.py

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 as you need to solve the discrete log. However, the prime is fixed in the server, and when computing the factors of , 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 by solving for first using discrete log.

Solution at solve.sage