2
$\begingroup$

I would like test vectors for 32-bit or 16-bits elliptic curves like $[p, a, b, G, n, h]$ , to test the Pohlig-Hellman algorithm in order to attack ECDLP over a finite prime field $F_p$.

Does anybody know a method to generate small $F_p$ parameters or can anybody supply the test vectors?

$\endgroup$
  • 1
    $\begingroup$ Hint: never start question with "I want". $\endgroup$ – Maarten Bodewes Mar 26 '17 at 15:55
  • 3
    $\begingroup$ I apologize I do not speak English well, it is not my native language i'm sorry and thanks for the remark :) $\endgroup$ – YIdirm Mar 26 '17 at 17:49
  • $\begingroup$ Do you need the curve's order to be smooth in order to test Pohlig-Hellman or would a prime order curve be ok ? It's unclear since you mentioned $n$ and $h$ which seems to me like you are looking for logarithms in the prime order subgroup... $\endgroup$ – Ruggero Mar 27 '17 at 9:46
  • $\begingroup$ First thank you sir for your answer, i would like to sign a message with ECDSA 16-bit or 32 bit (it's not standard). But now I have encountered two problems, the first when $n$ is not a prime number (smooth number) I have the problem of the non-existence of the inverse modulo $n$, so I can not even sign and check my message. The second and I could sign the message with 8-bit ECDSA but with $n$ a prime number so I can not apply the Pohlig-Hellman algorithm. $\endgroup$ – YIdirm Mar 27 '17 at 10:04
  • $\begingroup$ @YIdir I understand the issue. I believe it would make more sense to test Pohlig-Hellman on a simple scalar multiplication (ECDH) than on ECDSA, because ECDSA needs to work in a prime order subgroup to invert the ephemeral key. $\endgroup$ – Ruggero Mar 27 '17 at 12:55
4
$\begingroup$

Here is an example curve with smooth order $E/\mathbb{F}_p:y^2=x^3+ax+b$, generated with Magma.

\begin{align*} p &= 2^{31}-1 \\ a &= 1456400922 \\ b &= 2005615003 \\ n &= 2^5\cdot 3^7 \cdot 5\cdot 17\cdot 19^2. \end{align*}

I'd expect that if you are able to run PH, you should also be able to generate some test vectors yourself. The code is

p := 2^31-1;
Fp := GF(p);

repeat
    ct := 0;
    repeat
        a := Random(Fp);
        b := Random(Fp);
        D := 4*a^3+27*b^2;
    until D ne 0;
    E := EllipticCurve([Fp|a,b]);
    F := Factorization(#E);
    for f in F do
        if f[1] gt 25 then
            ct := 1;
        end if;
    end for;
until ct eq 0;
$\endgroup$
  • $\begingroup$ thanks sir, but i do not see the basic point $G$ ? $\endgroup$ – YIdirm Mar 28 '17 at 7:37
  • $\begingroup$ @YIdir Not trying to sound discouraging, but if you are implementing Pohlig-Hellman, then you should definitely be able to find some test vectors yourself. If you are not, you will probably have a bad time implementing this. For example, what do you mean by the basic point $G$? $\endgroup$ – CurveEnthusiast Mar 28 '17 at 8:59

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.