5

I'm working on a crypto problem as a puzzle and unfortunately my math isn't at the level I need it to be to answer the question. I have been given a prime $p$, a curve $E$ defined over $F(p)$, a generator point $G$, key $A$ (which is $aG$) and key $B$ (which is $bG$). The 'message' is given as $M + bG$ and I need to recover $M$.

The problem implies there is a simple solution as the given curve is 'flawed'. I've reduced $E$ down to the general form $y^2 = x^3 + Ax + B$ and found that the discriminate ($4A^3 + 27B^2$) is $0 \pmod p$. I think this bad reduction is the flaw in the system.

Now my question... how can I use this information to recover $M$? I understand that the $0 \pmod p$ discriminate means that the curve has a singularity $\pmod p$ and that this means that at this point the normal 'addition' operation doesn't work, but this doesn't seem to help me?

Thanks in advance!

EDIT:

Here's where I am up to. Based on the comment below (and in another question), I have been madly reading Silverman and trying to work this out. I spent a good many days scratching my head until I realised that I'd been leaving off the 'mod p' part of all my calculations... so long story short, A = 0 mod p and B = 0 mod p.

I've reduced the curve down to y^2 = x^3 mod p and via Silverman (and other help on this site) I've gotten the mapping (x, y) -> t = x / y. The mod p bit makes this a little more difficult but basically I use the transformation t = x * inverse of y mod p.

Then I've found the points t1 = (M + bG) transformed and t2 = (bG) transformed. I took (M) transformed as t1 - t2 (using the normal mode of subtraction) which I called t3. To get M, I mapped t3 back using t -> (x, y) = (t, ((t - 1) ^ 3) / t).

Now... all this sounds right to me, but it doesn't seem to give the right answer. This could either be because my calculations/code are incorrect, or because my logic is flawed. If I can narrow it down to one of these cases I can work on it from there.

So the question is... can anyone tell me if my logic is flawed?

Thanks again!

user3081739
  • 185
  • You still have a group law on the nonsingular points of the singular Weierstrass curve. The group you obtain is isomorphic to an "easy" group, which depends on the nature of the singular point (i.e. the type of singular reduction). See Silverman's The Arithmetic of Elliptic Curves, proposition III.2.5 and exercise III.3.5. – Ricardo Buring Dec 14 '13 at 12:53
  • Thanks very much... I've been madly reading Silverman trying to sort this out - progress is above! – user3081739 Dec 21 '13 at 06:46
  • How did you determine the inverse map to $(x,y) \mapsto x/y$? It's incorrect. Compute $(x/y)^2$ and $(x/y)^3$ to get an idea for the correct map. The answer is $t \mapsto (t^{-2}, t^{-3})$. – Ricardo Buring Dec 21 '13 at 14:20
  • Thanks Ricardo - is there any trick to calculating t^-2 mod p, with p a very large prime? – user3081739 Dec 21 '13 at 23:19
  • I forgot $p$ was large. I don't know how to proceed, sorry. Note that it is enough to compute $t^{-3}$. This is a cube, and if $p \equiv 2 \pmod 3$ then there are $(p-1)/3$ cubes to try (although I wouldn't know how to enumerate them). If $p \equiv 1 \pmod 3$ then the fact that it is a cube doesn't help, because in that case everything is a cube. – Ricardo Buring Dec 22 '13 at 14:14
  • No worries - thanks very much for all your help! :) – user3081739 Dec 23 '13 at 02:44

0 Answers0