ECDSA and EdDSA

With a digital signature, we sign a message with a private key (sk), and then prove it with the related public key (pk). The signature…
Photo by Cytonn Photography on Unsplash

ECDSA and EdDSA

With a digital signature, we sign a message with a private key (sk), and then prove it with the related public key (pk). The signature normally takes the form of (r,s). In this case we will generate signatures for the main methods used in ECDSA and EdDSA.

For ECDSA, Alice signs the message with the following:

  1. Create a hash of the message e=HASH(m).
  2. Let h be the Ln be the leftmost bits of e, Ln has a bit length of the group order N.
  3. Create a random number k which is between 1 and N−1.
  4. Calculate a point on the curve as (x1,y1)=k×G.
  5. Calculate r=x_1 (mod N). If r=0, go back to Step 3.
  6. Calculate s=k^{−1}(h+rdA)(mod N). If s=0, go back to Step 3.
  7. The signature is the pair (r,s)

Bob will check with:

  1. Create a hash of the message e=HASH(m)
  2. Let h be the Ln leftmost bits of e.
  3. Calculate c=s^{−1} (mod N), and where N is the order of the curve.
  4. Calculate u_1=h⋅c(modN) and u_2=r⋅c(modN)
  5. Calculate the curve point (x1,y1)=u1×G+u2×QA
  6. The signature is valid if r≡x1(modn), invalid otherwise.

For EdDSA, we have enhanced security and where we overcome some of the problems of ECDSA. With this, Alice creates a SHA-512 hash of her private key:

h=HASH(sk)

Create r from the upper 32 bytes of hash and the message:

r=HASH(h[32:]||m))

And where “||” represents a concatenation of the byte array values. Next she matches r onto curve with:

R=r⋅B

Next Alice computes s with:

s=r+(HASH(R||pk||m))⋅sk

The signature is (R,s). The values of R and s are 32 bytes long, and thus the signature is 64 bytes long.

Bob creates S using R, pk and m:

S=HASH(R||pk||m)

And next creates two verification values:

v_1=s⋅B

v_2=R+pk⋅S

If v_1==v_2

the signature checks. With the generation of the private key and the public key, we will generate our private key related to the size of the curve. For example for a 192-bit curve (eg NIST P192) we have 24 bytes of random data:

sk = ECPrivateKey(secrets.randbits(32*8), curve)
if (curve.size==192):
  sk = ECPrivateKey(secrets.randbits(24*8), curve)
elif (curve.size==224):
  sk = ECPrivateKey(secrets.randbits(28*8), curve)
elif (curve.size==160):
  sk = ECPrivateKey(secrets.randbits(20*8), curve)
elif (curve.size==448):
  sk = ECPrivateKey(secrets.randbits(56*8), curve)

We can then generate the public key based on the private key:

pk = sk.get_public_key()

The code used is [here]:

from ecpy.curves import Curve
import secrets
from ecpy.keys       import ECPrivateKey
from ecpy.ecdsa      import ECDSA
from ecpy.eddsa      import EDDSA
import hashlib
from ecpy.formatters import decode_sig
import sys,binascii

curve = Curve.get_curve('secp256k1')
G = curve.generator
order = curve.order
t=0
msg = 'hello'
if (len(sys.argv)>1):
  msg=str(sys.argv[1])
if (len(sys.argv)>2):
  t=int(sys.argv[2])
msg=msg.encode()
if (t==1): 
	curve = Curve.get_curve('NIST-P192')
elif (t==2): 
	curve = Curve.get_curve('NIST-P224')
elif (t==3): 
	curve = Curve.get_curve('NIST-P256')
elif (t==4): 
	curve = Curve.get_curve('Ed25519')
elif (t==5): 
	curve = Curve.get_curve('secp192k1')
elif (t==6): 
	curve = Curve.get_curve('secp160k1')
elif (t==7): 
	curve = Curve.get_curve('secp224k1') 
elif (t==8): 
	curve = Curve.get_curve('Brainpool-p256r1') 
elif (t==9): 
	curve = Curve.get_curve('Brainpool-p224r1') 
elif (t==10): 
	curve = Curve.get_curve('Brainpool-p192r1') 
elif (t==11): 
	curve = Curve.get_curve('Brainpool-p160r1')       
elif (t==12): 
	curve = Curve.get_curve('secp256r1') 
elif (t==13):
  curve = Curve.get_curve('Ed448')
if (t!=4 and t!=13): 
  print (f"Name: {curve.name}, y^2=x^3+a*x+b (mod p) Type: {curve.type}, Size: {curve.size}, a={curve.a}, b={curve.b}, G={curve.generator}, field={curve.field}, order={curve.order}")
else: 
  print (f"Name: {curve.name}, a*x^2+y^2=1+d*x^2*y^2 (mod p) Type: {curve.type}, Size: {curve.size}, a={curve.a}, d={curve.d}, G={curve.generator}, field={curve.field}, order={curve.order}")
sk = ECPrivateKey(secrets.randbits(32*8), curve)
if (curve.size==192):
  sk = ECPrivateKey(secrets.randbits(24*8), curve)
elif (curve.size==224):
  sk = ECPrivateKey(secrets.randbits(28*8), curve)
elif (curve.size==160):
  sk = ECPrivateKey(secrets.randbits(20*8), curve)
elif (curve.size==448):
  sk = ECPrivateKey(secrets.randbits(56*8), curve)

pk = sk.get_public_key()

if (t==4):
  signer = EDDSA(hashlib.sha512)
  pk = signer.get_public_key(sk, hashlib.sha512)
  sig    = signer.sign(msg,sk)
  rtn=signer.verify(msg,sig,pk)
elif (t==13):
  signer = EDDSA(hashlib.shake_256, hash_len=114)
  pk = signer.get_public_key(sk, hashlib.shake_256, hash_len=114)
  sig = signer.sign(msg, sk)
  rtn = signer.verify(msg, sig, pk)
else:
  signer = ECDSA()
  sig    = signer.sign(msg,sk)
  rtn=signer.verify(msg,sig,pk)
print("Message: ",msg)
print("\nPrivate key:", hex(sk.d))
print(f"Public key: ({hex(pk.W.x)},{hex(pk.W.y)}")
print(f"Signature verification: {rtn}")
print("\nSignature:", binascii.hexlify(sig).decode())

if (t!=4 and t!=13): 
  sig_len  = sig[1]+2
  r_offset = 4
  r_len    = sig[3]
  s_offset = 4+r_len+2
  s_len    = sig[4+r_len+1]
  r = int.from_bytes(sig[r_offset:r_offset+r_len], 'big')
  s = int.from_bytes(sig[s_offset:s_offset+s_len], 'big')
  print (f"\n(r,s) = ({r},{s})")
  r,s = decode_sig(sig, fmt='DER')
  print (f"\n(r,s) -  Check = ({r},{s})")
else:
  l = len(sig)>>1
  r = int.from_bytes(sig[0:l], 'little')
  s = int.from_bytes(sig[l:],  'little')
  print (f"\n(r,s) = ({r},{s})")

A sample run [here]:

Name: secp256k1, y^2=x^3+a*x+b (mod p) Type: weierstrass, Size: 256, a=0, b=7, G=(0x79be667ef9dcbbac55a06295ce870b07029bfcdb2dce28d959f2815b16f81798 , 0x483ada7726a3c4655da4fbfc0e1108a8fd17b448a68554199c47d08ffb10d4b8), field=115792089237316195423570985008687907853269984665640564039457584007908834671663, order=115792089237316195423570985008687907852837564279074904382605163141518161494337
Message:  b'hello'
Private key: 0x5d1ab21f17f6caed1c29d6cc019cf7dda1071cc4b37dcba654c47af98cc99a34
Public key: (0xda92763477b34b6443cca901a1bc794e7c65b85c5cc6e9d443e992b7062adf84,0x56cc5919829f80b80a2f91806d2bf565a033f91e25e7fc052d1cb71167ed2fd6
Signature verification: True
Signature: 304402200c3b07c8b068eca31eb15cf8a608737855051e9582a40ed889e53815ecada901022069b84613fe6bbd8220d2509f7c42e19da1a95f45770d22b77c48d0bf7ec4ce27
(r,s) = (5532051882613009013454805533407030651295281449899719376852625570987602979073,47818432622439099370009880209558293062203021294593318635492502307350283341351)

and Ed448 [here]:

Name: Ed448, a*x^2+y^2=1+d*x^2*y^2 (mod p) Type: twistededward, Size: 448, a=1, d=726838724295606890549323807888004534353641360687318060281490199180612328166730772686396383698676545930088884461843637361053498018326358, G=(0x4f1970c66bed0ded221d15a622bf36da9e146570470f1767ea6de324a3d3a46412ae1af72ab66511433b80e18b00938e2626a82bc70cc05e , 0x693f46716eb6bc248876203756c9c7624bea73736ca3984087789c1e05a0c2d73ad3ff1ce67c39c4fdbd132c4ed7c8ad9808795bf230fa14), field=726838724295606890549323807888004534353641360687318060281490199180612328166730772686396383698676545930088884461843637361053498018365439, order=181709681073901722637330951972001133588410340171829515070372549795146003961539585716195755291692375963310293709091662304773755859649779
Message:  b'hello'
Private key: 0x31a037add317c687b4765ad8db14cda8d016d02d328c1d85b2a3e39bc6727b9e2aaeb3e64cf0cbecc9ad4d1ceb755c7d8589f5d867efbb04
Public key: (0x972e36a0e3c8d1fd7d56e4d97987733e617283751e44a10fef88446ae4d043d011a1dd2984ad3fa352e7e735d8dd5d162fe4e02aec331d7,0xb6014fd194985443b584aa938308ced3e08395447358d80aced4560d60f26a5b78f5952b89373d482a135c3bd189fc988632721d956d336c
Signature verification: True
Signature: 5f5a3e0fa856adaa5364e6286597ead0447089079f865959981d4168b1f610b51fd3a26cf748f7d9e105da77796573bcc3fa3af4f5456c1e80bc305cf9e4252a392dc157e8d43d90f0300a38f5648f2641a98d80aeb8ca6d9519d758f7f8a0a6c9da9d0f294fb215c2436c5022ee6f7f3900
(r,s) = (93121733947056327907665489481668249791943809936437750349071038045653315352609199077452776334031756827652939852030325331545642803985799775,163248550059559477898666947236960607854615136440383872090895197693307102325686319248853139683367591735022090614536751873847799383339196)