generate 100k minisign keys using python, in 1 minute

[badiku]

hi, I want to generate lots of minisign keys in short time, but since minisign is not a library, #40 , I try to do this in python.

from Crypto.PublicKey import ECC  # pip install pycryptodome
import time
import base64
import random

def generate_minisign_key():
    edkey = ECC.generate(curve='Ed25519')

    signature_algorithm = b'Ed'
    kdf_algorithm = bytes(2)
    cksum_algorithm  = b'B2'
    kdf_salt = bytes(32)
    kdf_opslimit = bytes(8)
    kdf_memlimit = bytes(8)
    key_id = bytes(8) # or random.randbytes(8)
    secret_key = edkey.seed   # bytes(32)
    public_key = edkey.public_key().export_key(format='raw')  # bytes(32)
    checksum = bytes(32)

    keynum_sk = key_id + secret_key + public_key + checksum
    private_key = signature_algorithm + kdf_algorithm + cksum_algorithm + kdf_salt + kdf_opslimit + kdf_memlimit + keynum_sk

    assert len(keynum_sk) == 104
    assert len(private_key) == 158
    return base64.b64encode(private_key).decode()

minikey = generate_minisign_key()
print(minikey)

with open(r'C:\Users\test\.minisign\minisign.key', 'w') as f:
    f.write('\n' + minikey)

RWQAAEIyAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAABJ+wrrPEPVNVR8qUR/C3QRBsvLmE2g44ZLw2uivol2NIO6LKJre7EaYB4VhwS5UTMbt1ag968P5CVPISsfSbbgAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA=

and in command line console:

C:\Users\test\.minisign>minisign -Rf
C:\Users\test\.minisign>echo test > a.txt
C:\Users\test\.minisign>minisign -Sm a.txt
C:\Users\test\.minisign>minisign -Vm a.txt
Signature and comment signature verified
Trusted comment: timestamp:[1701665531](tel:1701665531)   file:a.txt   hashed

quote:

Secret key format

untrusted comment: <arbitrary text>
base64(<signature_algorithm> || <kdf_algorithm> || <cksum_algorithm> ||
       <kdf_salt> || <kdf_opslimit> || <kdf_memlimit> || <keynum_sk>)

    signature_algorithm: Ed
    kdf_algorithm: Sc
    cksum_algorithm: B2
    kdf_salt: 32 random bytes
    kdf_opslimit: crypto_pwhash_scryptsalsa208sha256_OPSLIMIT_SENSITIVE
    kdf_memlimit: crypto_pwhash_scryptsalsa208sha256_MEMLIMIT_SENSITIVE
    keynum_sk: <kdf_output> ^ (<key_id> || <secret_key> || <public_key> || <checksum>), 104 bytes
    key_id: 8 random bytes
    secret_key: Ed25519 secret key
    public_key: Ed25519 public key
    checksum: Blake2b-256(<signature_algorithm> || <key_id> || <secret_key> || <public_key>), 32 bytes

and in a batch:

n = 100*1000
t1 = time.time()
minikeys = [generate_minisign_key() for _ in range(n)]
t2 = time.time()

s = int(t2 - t1)
print('generated', len(minikeys), 'minisign keys in', s, 'seconds,', n // s, 'per second')

generated 100000 minisign keys in 43 seconds, 2325 per second

maybe it cound be faster if minisign is a c library

[jedisct1]

key_id = bytes(8) # or random.randbytes(8)

Maybe you can use a counter here?

pycryptodome uses an implementation in C, but looking at the code, it's indeed likely to be slower than libsodium.

You can still use Python, but replace pycroptodome with pysodium or pynacl to get the same performance as the C version of minisign.

[badiku]

compare to pycryptodome, pysodium lacks documentation. import pysodium only got error 'Unable to find libsodium' doc only says that "requires a pre-installed libsodium", but I can not figure out how to install libsodium in python.

pycryptodome is special designed for python, pip is enough to make it work. and plenty of documentation.

anyway, pycryptodome can also do this job fast enough. It generates 100k Ed25519 keys in only 2 seconds, and then it takes some time to assemble into minisign key structure.

from Crypto.PublicKey import ECC  # pip install pycryptodome
import time

def batch_generate_minisignn_keys(n=100*1000):
    t1 = time.time()
    ed25519keys = [ECC.generate(curve='Ed25519') for _ in range(n)]
    t2 = time.time()
    print('generated', len(ed25519keys), 'Ed25519 keys in', t2-t1, 'seconds,', n / (t2 - t1), 'per second')

    signature_algorithm = b'Ed'
    kdf_algorithm = bytes(2)
    cksum_algorithm  = b'B2'
    kdf_salt = bytes(32)
    kdf_opslimit = bytes(8)
    kdf_memlimit = bytes(8)
    key_id = bytes(8)       # or random.randbytes(8)
    checksum = bytes(32)
    private_key_prefix = signature_algorithm + kdf_algorithm + cksum_algorithm + kdf_salt + kdf_opslimit + kdf_memlimit + key_id

    t1 = time.time()
    minikeys = [private_key_prefix + edkey.seed + edkey.public_key().export_key(format='raw') + checksum for edkey in ed25519keys]
    t2 = time.time()
    print('generated', len(minikeys), 'minisign keys in', t2-t1, 'seconds,', n / (t2 - t1), 'per second')

    return minikeys

result = batch_generate_minisignn_keys(100*1000)

generated 100000 Ed25519 keys in 2.03682017326355 seconds, 49096.135885070464 per second generated 100000 minisign keys in 28.042936325073242 seconds, 3565.960384490472 per second

though if I want to generate billions of keys, then I need more research

[jedisct1]

from pysodium import sodium_init, crypto_sign_keypair #pip install pysodium
import time

sodium_init()

def batch_generate_minisignn_keys(n=100 * 1000):
    t1 = time.time()
    ed25519keys = [crypto_sign_keypair() for _ in range(n)]
    t2 = time.time()
    print(
        "generated",
        len(ed25519keys),
        "Ed25519 keys in",
        t2 - t1,
        "seconds,",
        n / (t2 - t1),
        "per second",
    )

    signature_algorithm = b"Ed"
    kdf_algorithm = bytes(2)
    cksum_algorithm = b"B2"
    kdf_salt = bytes(32)
    kdf_opslimit = bytes(8)
    kdf_memlimit = bytes(8)
    key_id = bytes(8)  # or random.randbytes(8)
    checksum = bytes(32)
    private_key_prefix = (
        signature_algorithm
        + kdf_algorithm
        + cksum_algorithm
        + kdf_salt
        + kdf_opslimit
        + kdf_memlimit
        + key_id
    )

    t1 = time.time()
    minikeys = [private_key_prefix + edkey[0] + checksum for edkey in ed25519keys]
    t2 = time.time()
    print(
        "generated",
        len(minikeys),
        "minisign keys in",
        t2 - t1,
        "seconds,",
        n / (t2 - t1),
        "per second",
    )

    return minikeys

result = batch_generate_minisignn_keys(100 * 1000)

It's worth it.

Generating 100k keys with your code takes 32s on my M1, and only 1s with libsodium.

[jedisct1]

I can not figure out how to install libsodium in python.

It's a package, that your OS or Linux distro probably provides (brew install libsodium, apt install libsodium, whatever).

[badiku]

awesome.

ok, I find that libsodium also has excellent doc at https://doc.libsodium.org/installation.

though it'll be better if it mentions that the only simple thing to install it on windows is to put the single file libsodium.dll in a folder in your search path.

maybe this is a common sense for such library, I just did not think of this at the first time.

I downloaded a 18MB file libsodium-1.0.19-msvc.zip, but the only file I needed this a 337kb file libsodium.dll.

anyway, I tried your code,

generated 100000 Ed25519 keys in 3.9320638179779053 seconds, 25431.937178330383 per second generated 100000 minisign keys in 0.01128697395324707 seconds, 8859770.600536533 per second

ths first part is 4 seconds, slower than pycryptodome. but the second part is super fast , once it ends in 0 seconds, I have to check if t2 > t1.

on my notebook of windows 11, CPU Inter i9-12900H, without GPU.

maybe I really need GPU to work with such huge calculation

edit:

so now 100k is too small, now I tried 1000k, one million:

pycryptodome:
generated 1000000 Ed25519 keys in 8.8seconds, 112567  per second
generated 1000000 minisign keys in 186.1 seconds, 5372 per second

libsodium:
generated 1000000 Ed25519 keys in 25.1 seconds, 39878 5 per second
generated 1000000 minisign keys in 0.07  seconds, 14285581  per second

but:

print(len(result[0]))

# got 126 here? not 158??

but the problem of your libsodium version is, the generated key is not a length 158 minisign key. it can not be used as minisign key.

import base64
base64.b64encode(result[0]).decode()

[jedisct1]

Add edkey[1] after edkey[0], then.

[badiku]

ok, actually edkey[1] is length 64, so I only need edkey[1].

minikeys = [private_key_prefix + edkey[1] + checksum for edkey in ed25519keys]

this way it works.

[jedisct1]

Cool.