2
$\begingroup$

For Elliptic curves defined over $GF(2^n)$, by adding any two points P and Q over $GF(2^n)$ we get the third point over $GF(2^n)$. In Elliptic Curve Digital Signature Algorithm (ECDSA) https://en.wikipedia.org/wiki/Elliptic_Curve_Digital_Signature_Algorithm , there is a usage of prime numbers, particularly for the calculation of multiplicative inverse. It works fine for the Weierstrass form of Elliptic curve over $GF(P)$.

Now, I want to implement ECDSA using a binary form of Elliptic curve (like Hessian curve), but every time I am doing it, it is giving the wrong answer. My question is, is it not possible to use any curve over $GF(2^n)$ for an implementation like this?

Improve this question
$\endgroup$
6
  • $\begingroup$ Binary fields are dead. The aftermath and considerations of the new record of 30750-Bit Binary Field Discrete Logarithm - 2020 $\endgroup$
    – kelalaka
    Mar 8, 2021 at 12:40
  • $\begingroup$ If you really want to implement it, you can use Stack Overflow to ask for help. In Cryptography.SE we are no interested in the implementation problems. As you can see a recent problem has been migrated to so $\endgroup$
    – kelalaka
    Mar 8, 2021 at 12:50
  • $\begingroup$ No, I was just asking logic-wise.... like is it possible? to use a binary curve for ECDSA where operations are done using prime numbers? $\endgroup$
    – DEBASMITA DEY
    Mar 8, 2021 at 12:51
  • $\begingroup$ Also, the rational point of a curve defined over a field $E(K)$ form an abelian group where it is usual to define a Z-Module with scalar multiplication. The field for the underlying curve has only an effect on the security, the number of points, and efficient implementations. Therefore it is possible. $\endgroup$
    – kelalaka
    Mar 8, 2021 at 12:52
  • $\begingroup$ Fast Software Implementation of Binary Elliptic Curve Cryptography by Manuel Bluhm1 and Shay Gueron on 2013 $\endgroup$
    – kelalaka
    Mar 8, 2021 at 13:53

2 Answers 2

Reset to default
3
$\begingroup$

Yes it can. The only variation from the wikipedia article is in step 5 where it states to calculate $r\equiv x_1\pmod{n}$. This does not make sense when $x_1$ isbn element of a binary field. Instead binary field elements are converted to integers by a standards prescribed process (see ANSI X9.62-1984 section 4)

Improve this answer
$\endgroup$
-3
$\begingroup$

Try to see Ukrainian standard DSTU-4145. It has almost same algorithm but another.

The calculation of the signature can be found on page 15 in pdf document (actually it is 21 page). The algorithm used for verification is shown slightly below that. This standard is using binary fields over optimal normal/polynomial basis. The base algorithms that are used in the calculation are described at the beginning of the standard.

Unfortunately the paper is in Ukrainian, there doesn't seem to be an English copy.

Improve this answer
$\endgroup$
3
  • 2
    $\begingroup$ Hi Kripaka. Thanks for chipping in and linking to this paper from 2002. Could you maybe quote the relevant parts of the paper here? It's not entirely clear what you mean with "almost same algorithm" either. If you cannot elaborate, do you mind if I convert your answer to a comment below the question? For that to happen I need to know the section that goes into using prime numbers for the multiplicative inverse! $\endgroup$
    – Maarten Bodewes ♦
    Feb 18 at 21:47
  • $\begingroup$ Hi! Yeah, it would be completely ok. I'd like to quote this paper as you questioned about signing standards on an elliptic curve based on binary field. Could you maybe quote the relevant parts of the paper here? Try to find page 15 in pdf document (actually it is 21 page). Here you can see the calculating of signature, a little lower -- verifying algorithm. This standard is using binary fields over optimal normal/polynomial basis. At the beginning of the standard, there describes base algorithms that are used in the calculation. $\endgroup$
    – Kripaka Illia
    Feb 21 at 10:22
  • $\begingroup$ Note that you are now replying to a comment made by a moderator, not a comment made by the original author of the question. Quoting the relevant parts of the paper (in English) is not the job of the author of the question nor of the moderator. $\endgroup$
    – Maarten Bodewes ♦
    Feb 21 at 14:57

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.