4
$\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$
6
  • 2
    $\begingroup$ Hint: never start question with "I want". $\endgroup$
    – Maarten Bodewes
    Mar 26, 2017 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, 2017 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, 2017 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, 2017 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, 2017 at 12:55

1 Answer 1

5
$\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$
3
  • $\begingroup$ thanks sir, but i do not see the basic point $G$ ? $\endgroup$
    – YIdirm
    Mar 28, 2017 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$ Mar 28, 2017 at 8:59
  • $\begingroup$ Note to anyone tempted to use these parameters: they are much too small to give any security. Finding the private key from the public key is trivial. $\endgroup$
    – fgrieu
    Mar 1, 2022 at 14:24

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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