brute-force ed25519 key generator

keygen.c

/* I release this code into the public domain under the terms of the creative
   commons cc0 license/dedication.  - Nick Mathewson*/
#include <stdint.h>
#include <openssl/rand.h>
#include <openssl/sha.h>
#include <stdio.h>
#include "ed25519.h"

/* XXXXXXXX

   NOT FOR PRODUCTION USE.  I HAVE NO IDEA IF THIS IS SAFE.
*/

int key_ok(ed25519_public_key pk)
{
  /* Hypothetical rule: first bit is 0. Next 19 bits must match
   * bits in same position in a SHA512 hash */

  unsigned char d[64];
  SHA512(pk, 32, d);

#define MATCHES(idx, bits) (((pk[idx] ^ d[idx]) & bits) == 0)

  return
    (d[0] & 0x80) == 0 &&
    MATCHES(0, 0x7f) &&
    MATCHES(1, 0xff) &&
    MATCHES(2, 0x0f);
}

int main(int c, char **v)
{
  ed25519_public_key pk;
  ed25519_secret_key sk;
  int i;
  uint64_t attempts = 0;

  RAND_poll();

  do {
    /* We could be a bit faster here by doing RAND_bytes only once and then
     * iteratively doing "increment(sk, 1); add_basepoint(pk)".  Perhaps.
     */
    RAND_bytes((unsigned char*)sk, sizeof(sk));

    ed25519_publickey(sk, pk);

    ++attempts;
  } while (! key_ok(pk));

  printf("After %llu attempts:\n", (unsigned long long) attempts);
  for (i = 0; i < 32; ++i) {
    printf("%02x", pk[i]);
  }
  puts("");

  return 0;
}