Attachmentscrypto - 3500 solves

Please hack.


A day


Same as blinder, but I found a more efficient solution for this particular pp. It takes about 4500 operations to work (c.f. 13000 operations using elliptic curve).

The previous solution using elliptic curve is more general. This solution won't work if you select a prime with non-smooth factorization for (pd1)/(p1)(p^d-1) / (p-1).



  1. Work under the polynomial quotient ring of modulo x2+1x^2 + 1.
  2. Recover the partial index of yy using Pohlig-hellman.
  3. Calculate yy.

Note: If you haven't read our previous solution using elliptic curve, read it first. The concepts are similar, and I also applied most of the optimizations here.

After the previous solution is finished, I try to figure out how elliptic curve punch some holes in that field, creating a shrinking map to a smaller subgroup which has a smooth order.

Some points not on the curve seems to be the reason, but I still don't know how these things actually works, so let's skip this part.

Elliptic curve works really well on cryptography due to the hardness of its DLP. But clearly, we don't need such thing in this task. Maybe we can work on another simpler structure than elliptic curve.

Here it is: Polynomial quotient ring !!

Polynomial Quotient Ring

Let ff to be an irreducible polynomial over Fp\mathbb{F}_p. The order of multiplicative group in the quotient ring (Fp[x]/f)(\mathbb{F}_p[x]/\langle f \rangle)^* is p21p^2 - 1. In this task, the order is actually 24×3×5×59×281×3037×23293×(p1)2^4 \times 3 \times 5 \times 59 \times 281 \times 3037 \times 23293 \times (p-1) , which is almost smooth except for the last factor.

Recover part of the index

It won't be too hard to recover the index of a polynomial in each subgroup except last one. 30373037 and 2329323293 is a little bit large, so we need to use baby step giant step here. Luckliy, multiplication of polynomial doesn't cost too much operations.

Reconstruct y

Clearly, there's no efficient way to recover the index in (p1)(p-1) subgroup using oracle only. But we don't need to know that, we already have enough information to reveal what yy is.

Let's think about what that (p1)(p-1) subgroup is?

It's a group of all constants (i.e. degree 0 polynomials).

So here's how we reveal yy. Y=yx+1o=logg(Y)o=omod(p+1)go=ax+bY=go=go+k(p1)=go×gk(p1)=(ax+b)×ck=(a×ck)x+(b×ck)=(a×b1)x+1=yx+1\begin{aligned} Y &= yx + 1 \\ o &= \log_g(Y) \\ o' &= o \mod (p+1) \\ g^{o'} &= ax + b \\ Y &= g^o \\ &= g^{o' + k(p-1)} \\ &= g^{o'} \times g^{k(p-1)} \\ &= (ax + b) \times c^k \\ &= (a \times c^k) x + (b \times c^k) \\ &= (a \times b^{-1}) x + 1 \\ &= yx + 1 \\ \end{aligned}

And here's our new script :)