Take the 2-minute tour ×
Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It's 100% free, no registration required.

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?

share|improve this question
    
Just out of interest, why are you implementing your own scheme while there's scrutinized and already implemented solutions available, such as ed25519? –  orlp Jul 6 '13 at 23:51
    
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? –  Henrick Hellström Jul 7 '13 at 7:57
    
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. –  Peter Butler Jul 7 '13 at 15:06

2 Answers 2

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.

share|improve this answer
    
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? –  Peter Butler Jul 7 '13 at 15:07
    
@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) –  poncho Jul 7 '13 at 15:55
    
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. –  Henrick Hellström Jul 7 '13 at 17:27
    
@HenrickHellström: oops, you are correct. On the other hand, it's the modinv function which is the painful one. –  poncho Jul 7 '13 at 21:02
    
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. –  Peter Butler Jul 8 '13 at 17:09

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.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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