DamaS

I failed this task, tho it looked the most interesting.

For reference the task was set up like so:

# unknown
p, q = <random n-bit primes>
A = random_matrix(Zmod(p*q), 11)
f = rand_poly(11, p*q)

# known
N = p*q
e = <random>
B = f(A)
Q = B**pow(e, -1, (p-1)*(q-1))

Then pow(flag, e, N) is encoded in some weird way into a matrix S and you are given S*Q^r and B^r for some unknown r. I figured the only way forward was to find d or a factoring (equivalent).

I worked up all sorts of delusions involving the characteristic polynomials of the given matrices, thinking that if I could just find the right values to feed into the right polynomials some kind of magical algebra would take place and the factoring could take place.

There’s one eigenvalue of in the base ring (find it by doing ), but I was lost for how I might use it. I wasn’t able to find the corresponding eigenvalue of . And the others are likely roots of irreducible polynomials that I couldn’t find either. So was also lost for how to approach something like Jordan normal.

So many delusions… I desperately hoped there was a way to compose (or otherwise combine) the characteristic polynomials1 for some magical fairy math where I could factor the polynomials in . Tried to play around with the companion matrices (Hermite form) and base changes. Or what if I could find a e-th root of 1, if I just— But maybe— What if—

I gave up when poiko finally told me I shouldn’t waste my time and that the solution was stupid (he was spoiled by looking at others discussing it). Apparently the e wasn’t random as outlined in the script, but rather a low d was picked so you could Coppersmith it…? What’s the point…

Edit: I double checked the above and indeed,

d = 1839320038472006359578228121964872958248984913931534334417556559320978533688828921

… which would be impossible if the numbers were actually generated by the given script. Thus I feel this is a repeat of last year’s congurence task.

  1. All kinds of stupid party-tricks like and similar, where you’ll suddenly stumble across some surprise that give a jolt of I’m on to something here until the inevitable never mind, I’m just stupid.