1
$\begingroup$

Is there a problem with signing a message like this?

p = the Elliptic Curve prime  
G = base point  
a = Alice’s private key  
A = aG = Alice’s public key  
e = hash(message)  
Jx = x coordinate of J

In my target 32-bit microcontroller I am using p-256 and SHA256. Thus e will typically be in 1..p-1.

Alice computes:

e = hash(message)
E = eG
J = aE          using Alice’s private key

and sends Jx as signature

Recipient computes:

e = hash(message)  
K = eA          using Alice’s public key
and validates Jx = Kx

The only problem I see is that e might be 0 or 1 or some value >= p. (If it is I have the flexibility to pad the message such that e is in a good range.)

Is there a problem if hash(msg) is greater or equal to the EC prime? Other than a few unusable values of e is there is a problem that makes this method less secure than ECDSA?

Improve this question
$\endgroup$
3
  • $\begingroup$ Just out of interest, why are you implementing your own scheme while there's scrutinized and already implemented solutions available, such as ed25519? $\endgroup$
    – orlp
    Jul 6, 2013 at 23:51
  • $\begingroup$ Perhaps it would help if you more clearly listed your underlying requirements. Since you are implementing the scheme in a microcontroller I presume you want to avoid a scheme that relies on random per message values or an internal state (such as ECDSA), and also that you want signature generation to be relatively cheap, but is it also essential that the signatures are short? $\endgroup$
    – Henrick Hellström
    Jul 7, 2013 at 7:57
  • $\begingroup$ I am planning to use ARM Cortex-M4 microcontrollers (~US$10) to control remote devices. My point multiply takes ~25 milliseconds which is fast enough. The Intel Nehalem/Westmere devices would destroy both my cost and power budgets. $\endgroup$
    – Peter Butler
    Jul 7, 2013 at 15:06

2 Answers 2

Reset to default
3
$\begingroup$

The problem with this method is that it is insecure. Anyone with Alice's public key can sign any message they want, by computing:

$e = hash(message)$

$J = eA$

This $J_x$ will verify correctly according to your verification procedure.

Improve this answer
$\endgroup$
5
  • $\begingroup$ THANK YOU. I am inexperienced when it comes to public key cryptography. But once I saw how it was secure I understood. Of course, I could encrypt using ECDH. But that only validates the sender to a specific node. What I was trying to do was to sign a message that anyone could verify without needing %q arithmetic. q being the order of the curve. I could implement %q arithmetic for the product of two field elements and the multiplicative inverse %q but would rather not. Is there a secure signature scheme that only relies on point multiplication? $\endgroup$
    – Peter Butler
    Jul 7, 2013 at 15:07
  • $\begingroup$ @PeterButler: if you want a signature method that is, as far as we know, secure, and doesn't require any $\bmod q$ arithmetic, there are Schnorr signatures (en.wikipedia.org/wiki/Schnorr_signature) $\endgroup$
    – poncho
    Jul 7, 2013 at 15:55
  • $\begingroup$ Schnorr signature generation requires multiplying the hash with the private key modulo the group order. However, unlike DSA/ECDSA it doesn't require calculating any inverse modulo the group order. $\endgroup$
    – Henrick Hellström
    Jul 7, 2013 at 17:27
  • $\begingroup$ @HenrickHellström: oops, you are correct. On the other hand, it's the modinv function which is the painful one. $\endgroup$
    – poncho
    Jul 7, 2013 at 21:02
  • $\begingroup$ Thanks for all the help. My plan is to use EC-KCDSA from Guide to Elliptic Curve Cryptography Hankerson etal section 4.4.3. Its charm is that no %q math is required to verify a signature. Creating the signature (which requires %q) can be on the host desktop computer. EC-KCDSA has its (secret, public) key pair not (a, aG) but instead uses (a, (1/a)G). That’s annoying but tolerable. Star topology network. Information from pod to desktop host, if encrypted at all, can use ECDH. Commands that, for example, open a sewage gate must not be assessable to any hacker with a WiFi laptop. $\endgroup$
    – Peter Butler
    Jul 8, 2013 at 17:09
2
$\begingroup$

As poncho described, your method is completely insecure. $\:$ However, there is a signature construction from a gap group plus a group-valued random oracle, whose signature length is just one group element.

Improve this answer
$\endgroup$

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.