Implementation of EcDSA or EdDSA that generates 80 bit private keys
New here? Learn about Bountify and follow @bountify to get notified of new bounties! x

We need an implementation of EcDSA or EdDSA that generates 80 bit private keys. The Payload to sign will be 10 bytes long, and the signature must be 10 bytes (can be encoded).

Private key needs to be derived from a user entered password. (https://en.wikipedia.org/wiki/PBKDF2)

Payload format is, x0x2x3...x9, where 0 <= xi <= 9
Signature format is, s0s1s3...s9, where si ∈ [0-9A-Za-z]

The following code snippet generates EcDSA keys 256 bits long. We’d need a similar implementation, but we need to be able to set a string to use to derive the password and set key size to 80 bits so our signature is 10 bytes long.

  • import java.math.BigInteger;
  • import java.security.KeyPair;
  • import java.security.KeyPairGenerator;
  • import java.security.PrivateKey;
  • import java.security.PublicKey;
  • import java.security.SecureRandom;
  • import java.security.Signature;

public class ECDSAExample {

public static void main(String[] args) throws Exception {
    KeyPairGenerator keyGen = KeyPairGenerator.getInstance("EC");
    SecureRandom random = SecureRandom.getInstance("SHA1PRNG");

    keyGen.initialize(256, random);

    KeyPair pair = keyGen.generateKeyPair();
    PrivateKey priv = pair.getPrivate();
    PublicKey pub = pair.getPublic();

    Signature dsa = Signature.getInstance("SHA1withECDSA");

    dsa.initSign(priv);

    String str = "This is string to sign";
    byte[] strByte = str.getBytes("UTF-8");
    dsa.update(strByte);

    byte[] realSig = dsa.sign();
    System.out.println("Signature: " + new BigInteger(1, realSig).toString(16));
}
Hello According to the NIST (National Institute of Standards and Technology) you are not allowed anymore to generate key with less than 112 bits (see http://nvlpubs.nist.gov/nistpubs/SpecialPublications/NIST.SP.800-131Ar1.pdf page 6). You won't find any package or library that will allow you to create a such key, or you will have to reimplement it from scratch. Is there any reason that limits you to 10bytes long signature ?
kerncy 8 days ago
hey @kerncy yes, its a long story...... and is in part why we are hunting for help. The 10 byte constraint in the function we are building is firm.
Qdev 8 days ago
Do you have any constraint on the size of the public key? I have a solution in mind but it only works if the public key can keep its length.
CyteBode 8 days ago
good question @cytebode good question as long as the sig is 10 you can make the public and private key anything you need
Qdev 8 days ago
Never mind, I wasn't thinking straight. For making a 80-bit private key work, I was thinking of deterministically generating a bigger private key by hashing it with, for example, SHA-256. Then, a conventional ECDSA signing algorithm could use that new key to sign the payload, which would have worked nicely. For making the signature only 10 bytes, I was thinking of trimming the resulting signature. But then I realized the verifier wouldn't be able to authenticate the partial signature. That would only work in the context of a shared secret (e.g. with HMAC), in which case both the signer and verifier could generate the same signature from the payload and compare only the same 10 bytes.
CyteBode 8 days ago
Wait, I just saw your edit with the private key being derived from a user-entered password by PBKDF2. What exactly is the use-case? The user enters a password and the system derives a private key with which to sign a payload. Then it stores that payload with the signature. But then how does the verification happen? Does the user still need to enter their password, does the system keep the PBKDF2 result or private key, or does the system only keep the public key for verification purpose? Because unless it's the latter, then we're really in a shared secret context and EDCSA is unnecessary as HMAC would be sufficient to create and verify the signature.
CyteBode 8 days ago
awarded to CyteBode

Crowdsource coding tasks.

1 Solution


After a bit of research, I managed to figure out how to come up with my own ECC parameters. The conventional wisdom is just to use standard curve parameters that are tried-and-true, but none are small enough to give out 80-bit signatures, because it's deemed insecure.

In order to generate 80-bit signatures, a 40-bit curve needs to be used. That's because the signature is made up of two parts that have the same precision as the curve.

These are the parameters I came up with:

P = 989292113647
a = -3
b = 667230586810
N = 989290653721
Gx = 762284522849
Gy = 820883475793

Where P is a 40-bit prime and N is prime as well. This also follows the NIST recommendation to use -3 for a and a big integer for b.

Then I used the following Python code from https://www.cs.uaf.edu/2015/spring/cs463/lecture/03_25_signature/ECDSA.py, which implements ECC arithmetics:

# Elliptic Curve Cryptography using the BitCoin curve, SECG secp256k1
#  This version uses the X,Y,Z "Jacobi coordinates" representation, for speed
#  Dr. Orion Lawlor, lawlor@alaska.edu, 2015-03-25 (Public Domain)

from hashlib import sha256
from math import log
from copy import copy
from time import time # timing
from fractions import gcd # Greatest Common Denominator
from random import SystemRandom # cryptographic random byte generator
rand=SystemRandom() # create strong random number generator

# Convert a string with hex digits, colons, and whitespace to a long integer
def hex2int(hexString):
    return int("".join(hexString.replace(":","").split()),16)

# Half the extended Euclidean algorithm:
#    Computes   gcd(a,b) = a*x + b*y  
#    Returns only gcd, x (not y)
# From http://rosettacode.org/wiki/Modular_inverse#Python
def half_extended_gcd(aa, bb):
    lastrem, rem = abs(aa), abs(bb)
    x, lastx = 0, 1
    while rem:
        lastrem, (quotient, rem) = rem, divmod(lastrem, rem)
        x, lastx = lastx - quotient*x, x
    return lastrem, lastx 

# Modular inverse: compute the multiplicative inverse i of a mod m:
#     i*a = a*i = 1 mod m
def modular_inverse(a, m):
    g, x = half_extended_gcd(a, m)
    if g != 1:
        raise ValueError("g != 1")
    return x % m


# An elliptic curve has these fields:
#   p: the prime used to mod all coordinates
#   a: linear part of curve: y^2 = x^3 + ax + b
#   b: constant part of curve
#   G: a curve point (G.x,G.y) used as a "generator"
#   n: the order of the generator
class ECcurve:
    def __init__(self):
        return

    # Prime field multiplication: return a*b mod p
    def field_mul(self,a,b):
        return (a*b)%self.p

    # Prime field division: return num/den mod p
    def field_div(self,num,den):
        inverse_den=modular_inverse(den%self.p,self.p)
        return self.field_mul(num%self.p,inverse_den)

    # Prime field exponentiation: raise num to power mod p
    def field_exp(self,num,power):
        return pow(num%self.p,power,self.p)

    # Return the special identity point
    #   We pick x=p, y=0
    def identity(self):
        return ECpoint(self,self.p,0,1)

    # Return true if point Q lies on our curve
    def touches(self,Q):
        x=Q.get_x()
        y=Q.get_y()
        y2=(y*y)%self.p
        x3ab=(self.field_mul((x*x)%self.p+self.a,x)+self.b)%self.p
        return y2==(x3ab)%self.p

    # Return the slope of the tangent of this curve at point Q
    def tangent(self,Q):
        return self.field_div(Q.x*Q.x*3+self.a,Q.y*2)

    # Return a doubled version of this elliptic curve point
    #  Closely follows Gueron & Krasnov 2013 figure 2
    def double(self,Q):
        if (Q.x==self.p): # doubling the identity
            return Q
        S=(4*Q.x*Q.y*Q.y)%self.p
        Z2=Q.z*Q.z
        Z4=(Z2*Z2)%self.p
        M=(3*Q.x*Q.x+self.a*Z4)
        x=(M*M-2*S)%self.p
        Y2=Q.y*Q.y
        y=(M*(S-x)-8*Y2*Y2)%self.p
        z=(2*Q.y*Q.z)%self.p
        return ECpoint(self,x,y,z)

    # Return the "sum" of these elliptic curve points
    #  Closely follows Gueron & Krasnov 2013 figure 2
    def add(self,Q1,Q2):
        # Identity special cases
        if (Q1.x==self.p): # Q1 is identity
            return Q2
        if (Q2.x==self.p): # Q2 is identity
            return Q1
        Q1z2=Q1.z*Q1.z
        Q2z2=Q2.z*Q2.z
        xs1=(Q1.x*Q2z2)%self.p
        xs2=(Q2.x*Q1z2)%self.p
        ys1=(Q1.y*Q2z2*Q2.z)%self.p
        ys2=(Q2.y*Q1z2*Q1.z)%self.p

        # Equality special cases
        if (xs1==xs2): 
            if (ys1==ys2): # adding point to itself
                return self.double(Q1)
            else: # vertical pair--result is the identity
                return self.identity()

        # Ordinary case
        xd=(xs2-xs1)%self.p   # caution: if not python, negative result?
        yd=(ys2-ys1)%self.p
        xd2=(xd*xd)%self.p
        xd3=(xd2*xd)%self.p
        x=(yd*yd-xd3-2*xs1*xd2)%self.p
        y=(yd*(xs1*xd2-x)-ys1*xd3)%self.p
        z=(xd*Q1.z*Q2.z)%self.p
        return ECpoint(self,x,y,z)

    # "Multiply" this elliptic curve point Q by the scalar (integer) m
    #    Often the point Q will be the generator G
    def mul(self,m,Q):
        R=self.identity() # return point
        while m!=0:  # binary multiply loop
            if m&1: # bit is set
                #print("  mul: adding Q to R =",R);
                R=self.add(R,Q)
                #print("  mul: added Q to R =",R);
            m=m>>1
            if (m!=0):
                #print("  mul: doubling Q =",Q);
                Q=self.double(Q)

        return R


# A point on an elliptic curve: (x,y)
#   Using special (X,Y,Z) Jacobian point representation
class ECpoint:
    """A point on an elliptic curve (x/z^2,y/z^3)"""
    def __init__(self,curve, x,y,z):
        self.curve=curve
        self.x=x
        self.y=y
        self.z=z
        # This self-check has a big performance cost.
        #if not x==curve.p and not curve.touches(self):
        #   print(" ECpoint left curve: ",self)

    # "Add" this point to another point on the same curve
    def add(self,Q2):
        return self.curve.add(self,Q2)

    # "Multiply" this point by a scalar
    def mul(self,m):
        return self.curve.mul(m,self)

    # Extract non-projective X and Y coordinates
    #   This is the only time we need the expensive modular inverse
    def get_x(self):
        return self.curve.field_div(self.x,(self.z*self.z)%self.curve.p);
    def get_y(self):
        return self.curve.field_div(self.y,(self.z*self.z*self.z)%self.curve.p);

    # Print this ECpoint
    def __str__(self):
        if (self.x==self.curve.p):
            return "identity_point"
        else:
            return "("+str(self.get_x())+", "+str(self.get_y())+")"

And added the following code, which I wrote. It replaces lines 178+ in the original code:

import binascii
import hashlib
import hmac
import struct


def pbkdf2(prf, password, salt, num_iter, dk_len):
    def _ceil_div(a, b):
        d = a // b
        return d + 1 if a - d*b > 0 else d

    def _xor(a, b):
        return bytes([t[0] ^ t[1] for t in zip(a, b)])

    def _uint32_be(num):
        return struct.pack(">I", num)

    def _f(prf, password, salt, num_iter, i):
        u = prf(password, b"".join([salt, _uint32_be(i)]))
        u_accum = u
        for _ in range(num_iter - 1):
            u = prf(password, u)
            u_accum = _xor(u_accum, u)
        return u_accum

    h_len = len(prf(b"", b""))
    range_ = range(_ceil_div(dk_len, h_len))
    result = b"".join([_f(prf, password, salt, num_iter, i+1) for i in range_])

    return result[0:dk_len]


def hmac_sha256(key, msg):
    hmac_ = hmac.new(key, msg, hashlib.sha256)
    return hmac_.digest()


def hash_sha256(msg):
    hash_ = hashlib.sha256(msg)
    return hash_.digest()


def zero_pad(s, l):
    if len(s) >= l:
        return s
    return "%s%s" % ("0" * (l - len(s)), s)


def bitstring_to_bytes(s):
    v = int(s, 2)
    b = bytearray()

    if (len(s) // 8) * 8 != len(s):
        s = "0" * (len(s) - (len(s) // 8) * 8) + s

    while v:
        b.append(v & 0xFF)
        v >>= 8
    while len(b) < len(s) // 8:
        b.append(0x00)

    return bytes(b[::-1])


def int_from_bytes(xbytes):
    return int.from_bytes(xbytes, 'big')


def generate_keypair(curve, seed):
    G = curve.G
    n = curve.n

    private_key = int_from_bytes(seed) % n

    private_key = zero_pad("{0:b}".format(private_key), 40)
    private_key = bitstring_to_bytes(private_key)

    return (private_key, get_public_key(curve, private_key))


def get_public_key(curve, private_key):
    assert len(private_key) == 5

    G = curve.G
    n = curve.n

    private_key = int_from_bytes(private_key)
    public_key = G.mul(private_key)

    public_key = zero_pad("{0:b}".format(public_key.get_x()), 40) + \
                 zero_pad("{0:b}".format(public_key.get_y()), 40)
    public_key = bitstring_to_bytes(public_key)

    return public_key


def sign_payload(curve, payload, private_key):
    assert len(payload) == 10
    assert len(private_key) == 5

    G = curve.G
    n = curve.n
    d = int_from_bytes(private_key)

    digest = hash_sha256(payload)[-5:] # 5 last bytes for 40-bit digest
    z = int_from_bytes(digest)
    k = rand.getrandbits(40) % n # Message nonce
    C = G.mul(k) # Move down the curve by k

    r = C.get_x() % n                               # Part 1 of signature
    s = (((z + r*d) % n)*modular_inverse(k, n)) % n # Part 2 of signature

    signature = zero_pad("{0:b}".format(r), 40) + \
                zero_pad("{0:b}".format(s), 40)
    signature = bitstring_to_bytes(signature)

    return signature


def verify_signature(curve, payload, signature, public_key):
    assert len(payload) == 10
    assert len(signature) == 10
    assert len(public_key) == 10

    G = curve.G
    n = curve.n

    pkx = int_from_bytes(public_key[0:5])
    pky = int_from_bytes(public_key[5:10])
    Q = ECpoint(curve, pkx, pky, 1)

    r = int_from_bytes(signature[0:5])
    s = int_from_bytes(signature[5:10])

    digest = hash_sha256(payload)[-5:] # 5 last bytes for 40-bit digest
    z = int_from_bytes(digest)

    si = modular_inverse(s, n)   # si = 1/s
    u1 = (z*si) % n              # u1 = z/s mod n
    u2 = (r*si) % n              # u2 = r/s mod z
    C = G.mul(u1).add(Q.mul(u2)) # C  = u1 G + u2 Q

    return (r % n == C.get_x() % n)


if __name__ == '__main__':
    import getpass
    import os
    import sys

    # Python 3 only
    assert sys.version_info[0] == 3

    curve40 = ECcurve()
    curve40.p = 989292113647
    curve40.a = -3
    curve40.b = 667230586810
    curve40.n = 989290653721

    curve40.G = ECpoint(curve=curve40,
      x = 762284522849,
      y = 820883475793,
      z = 1
    );

    curve = curve40

    Q=curve.G
    assert curve.touches(Q);
    assert str(curve.mul(curve.n, Q)) == "identity_point"


    def hex_str(bytes_):
        return binascii.hexlify(bytes_).decode("utf-8")

    print("Generating random payloads...")
    payloads = [os.urandom(10) for _ in range(10)]
    for i, payload in enumerate(payloads):
        print("Random Payload %02d: %s" % (i+1, hex_str(payload)))

    print("")
    salt = os.urandom(4)
    print("Password salt: %s" % hex_str(salt))
    password = getpass.getpass("Password: ").encode("utf-8")
    seed = pbkdf2(hmac_sha256, password, salt, 4096, 5)

    print("")
    print("Generating keypair...")
    key_pair = generate_keypair(curve, seed)
    private_key = key_pair[0]
    public_key = key_pair[1]

    print("Private key: %s" % hex_str(private_key))
    print("Public key: %s" % hex_str(public_key))

    print("")
    print("Signing payloads with private key...")
    signatures = []
    for i, payload in enumerate(payloads):
        signature = sign_payload(curve, payload, private_key)
        print("Signature %02d: %s" % (i+1, hex_str(signature)))
        signatures.append(signature)

    print("")
    print("Verifying signatures with public key...")
    for i, pair in enumerate(zip(payloads, signatures)):
        payload, signature = pair
        if verify_signature(curve, payload, signature, public_key):
            print("Payload %02d: PASSED verification" % (i+1))
        else:
            print("Payload %02d: FAILED verification" % (i+1))

    print("")
    print("Verifying signatures with bogus public keys...")
    bogus_private_key = os.urandom(5)
    while (bogus_private_key == private_key):
        bogus_private_key = os.urandom(5)
    bogus_public_key = get_public_key(curve, bogus_private_key)
    for i, pair in enumerate(zip(payloads, signatures)):
        payload, signature = pair
        if verify_signature(curve, payload, signature, bogus_public_key):
            print("Payload %02d: PASSED verification" % (i+1))
        else:
            print("Payload %02d: FAILED verification" % (i+1))

So instead of using Bitcoin's curve it uses the curve parameters I came up with. The important parts are the generate_keypair, sign_payload and verify_signature functions.

The __main__ part generates 10 random 10-byte payloads. Then it asks for a password and processes it with pbkdf2 and a random salt (which should be tied with the user in reality). Then it generates the ECDSA key pair using the pbkdf2'd password as a seed and signs the 10 payloads with the private key. Finally, it verifies these signature using the public key. As a sanity check, it also verifies the signatures using a bogus public key (generated randomly).

The code only works with Python 3.

The output looks like this:

Generating random payloads...
Random Payload 01: 5d1b516acf029eb84472
Random Payload 02: 49eeff70f756c1cd797c
Random Payload 03: 40fbe414a0646be14699
Random Payload 04: e31dba0198acfaaed407
Random Payload 05: c9fe00515048d64d7a44
Random Payload 06: 5854e9e456fa24380b3a
Random Payload 07: 72ee7ba223fdb462fdf9
Random Payload 08: d8ecd390f042c08ab5d5
Random Payload 09: 07cb8e2d914e603d7edb
Random Payload 10: 77f5bb88306f1fbfab93

Password salt: adaa3e6c
Password:

Generating keypair...
Private key: a452dfb9ce
Public key: ced83ec6101c0c418807

Signing payloads with private key...
Signature 01: 2cc2480962a876f925a4
Signature 02: af5d36e36c71d5087a70
Signature 03: 84f2225b69680795f0d2
Signature 04: 6d55afc247dda2b2d5b2
Signature 05: 5f4e21776a2f9da79639
Signature 06: cb52ddab26dd190834ce
Signature 07: 27ae2accda8c5841345f
Signature 08: 81e4930988b4b21302e7
Signature 09: 46bc4c1bbe6e79f3911d
Signature 10: 1d0c44d6e27a89d2aef2

Verifying signatures with public key...
Payload 01: PASSED verification
Payload 02: PASSED verification
Payload 03: PASSED verification
Payload 04: PASSED verification
Payload 05: PASSED verification
Payload 06: PASSED verification
Payload 07: PASSED verification
Payload 08: PASSED verification
Payload 09: PASSED verification
Payload 10: PASSED verification

Verifying signatures with bogus public key...
Payload 01: FAILED verification
Payload 02: FAILED verification
Payload 03: FAILED verification
Payload 04: FAILED verification
Payload 05: FAILED verification
Payload 06: FAILED verification
Payload 07: FAILED verification
Payload 08: FAILED verification
Payload 09: FAILED verification
Payload 10: FAILED verification

Edit 1: Fixed small bug with computation of z (missing colon).

Edit 2: Tidied up the code. Added some asserts for the lengths of the arguments. Removed the superfluous salt argument from generate_keypair. Added the get_public_key function to calculate the public key from a private key and changed the sanity check at the end so it uses a randomly generated private key instead of a randomly generated public key. Otherwise, the sanity check was bound to fail anyway because the points likely weren't on the curve. Now the verifications still fail as they should, but at least the points are on the curve.

Edit 3: Fixed bug in generate_keypair where the private key wasn't zero-padded properly (40 vs 20). Fixed bug in bitstring_to_bytes where leading zeroes weren't converted to bytes. Changed the bytes-to-hex-to-int conversions to just use int_from_bytes instead.

thanks! validating with my team now. i appreciate the level of effort you put on this.
Qdev 6 days ago
hey @cytebode I sent you a direct message, we need a couple more tweaks on this if you are interested in helping.
Qdev 4 days ago