**New here?**Learn about Bountify and follow @bountify to get notified of new bounties! Follow @bountify 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));
}
```

## 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.