edsign.c

   1 /* Edwards curve signature system
   2  * Daniel Beer <dlbeer@gmail.com>, 22 Apr 2014
   3  *
   4  * This file is in the public domain.
   5  */
   6
   7 #include "ed25519.h"
   8 #include "sha512.h"
   9 #include "fprime.h"
  10 #include "edsign.h"
  11
  12 #define EXPANDED_SIZE           64
  13
  14 static const uint8_t ed25519_order[FPRIME_SIZE] = {
  15         0xed, 0xd3, 0xf5, 0x5c, 0x1a, 0x63, 0x12, 0x58,
  16         0xd6, 0x9c, 0xf7, 0xa2, 0xde, 0xf9, 0xde, 0x14,
  17         0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
  18         0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x10
  19 };
  20
  21 static void expand_key(uint8_t *expanded, const uint8_t *secret)
  22 {
  23         struct sha512_state s;
  24
  25         sha512_init(&s);
  26         sha512_add(&s, secret, EDSIGN_SECRET_KEY_SIZE);
  27         sha512_final(&s, expanded);
  28
  29         ed25519_prepare(expanded);
  30 }
  31
  32 static uint8_t upp(struct ed25519_pt *p, const uint8_t *packed)
  33 {
  34         uint8_t x[F25519_SIZE];
  35         uint8_t y[F25519_SIZE];
  36         uint8_t ok = ed25519_try_unpack(x, y, packed);
  37
  38         ed25519_project(p, x, y);
  39         return ok;
  40 }
  41
  42 static void pp(uint8_t *packed, const struct ed25519_pt *p)
  43 {
  44         uint8_t x[F25519_SIZE];
  45         uint8_t y[F25519_SIZE];
  46
  47         ed25519_unproject(x, y, p);
  48         ed25519_pack(packed, x, y);
  49 }
  50
  51 static void sm_pack(uint8_t *r, const uint8_t *k)
  52 {
  53         struct ed25519_pt p;
  54
  55         ed25519_smult(&p, &ed25519_base, k);
  56         pp(r, &p);
  57 }
  58
  59 void edsign_sec_to_pub(void *pub, const void *secret)
  60 {
  61         uint8_t expanded[EXPANDED_SIZE];
  62
  63         expand_key(expanded, secret);
  64         sm_pack(pub, expanded);
  65 }
  66
  67 static void save_hash(struct sha512_state *s, uint8_t *out)
  68 {
  69         void *hash;
  70
  71         hash = sha512_final_get(s);
  72         fprime_from_bytes(out, hash, SHA512_HASH_SIZE, ed25519_order);
  73 }
  74
  75 static void generate_k(uint8_t *k, const uint8_t *kgen_key,
  76                        const uint8_t *message, size_t len)
  77 {
  78         struct sha512_state s;
  79
  80         sha512_init(&s);
  81         sha512_add(&s, kgen_key, 32);
  82         sha512_add(&s, message, len);
  83         save_hash(&s, k);
  84 }
  85
  86 static void hash_message(uint8_t *z, const uint8_t *r, const uint8_t *a,
  87                          const uint8_t *m, size_t len)
  88 {
  89         struct sha512_state s;
  90
  91         sha512_init(&s);
  92         sha512_add(&s, r, 32);
  93         sha512_add(&s, a, 32);
  94         sha512_add(&s, m, len);
  95         save_hash(&s, z);
  96 }
  97
  98 void edsign_sign(uint8_t *signature, const uint8_t *pub,
  99                  const uint8_t *secret,
 100                  const uint8_t *message, size_t len)
 101 {
 102         uint8_t expanded[EXPANDED_SIZE];
 103         uint8_t e[FPRIME_SIZE];
 104         uint8_t s[FPRIME_SIZE];
 105         uint8_t k[FPRIME_SIZE];
 106         uint8_t z[FPRIME_SIZE];
 107
 108         expand_key(expanded, secret);
 109
 110         /* Generate k and R = kB */
 111         generate_k(k, expanded + 32, message, len);
 112         sm_pack(signature, k);
 113
 114         /* Compute z = H(R, A, M) */
 115         hash_message(z, signature, pub, message, len);
 116
 117         /* Obtain e */
 118         fprime_from_bytes(e, expanded, 32, ed25519_order);
 119
 120         /* Compute s = ze + k */
 121         fprime_mul(s, z, e, ed25519_order);
 122         fprime_add(s, k, ed25519_order);
 123         memcpy(signature + 32, s, 32);
 124 }
 125
 126 void edsign_verify_init(struct edsign_verify_state *st, const void *sig,
 127                         const void *pub)
 128 {
 129         sha512_init(&st->sha);
 130         sha512_add(&st->sha, sig, 32);
 131         sha512_add(&st->sha, pub, 32);
 132 }
 133
 134 bool edsign_verify(struct edsign_verify_state *st, const void *sig, const void *pub)
 135 {
 136         struct ed25519_pt p;
 137         struct ed25519_pt q;
 138         uint8_t lhs[F25519_SIZE];
 139         uint8_t rhs[F25519_SIZE];
 140         uint8_t z[FPRIME_SIZE];
 141         uint8_t ok = 1;
 142
 143         /* Compute z = H(R, A, M) */
 144         save_hash(&st->sha, z);
 145
 146         /* sB = (ze + k)B = ... */
 147         sm_pack(lhs, sig + 32);
 148
 149         /* ... = zA + R */
 150         ok &= upp(&p, pub);
 151         ed25519_smult(&p, &p, z);
 152         ok &= upp(&q, sig);
 153         ed25519_add(&p, &p, &q);
 154         pp(rhs, &p);
 155
 156         /* Equal? */
 157         return ok & f25519_eq(lhs, rhs);
 158 }