pd.if.org Git - zpackage/blob - crypto/libeddsa/lib/ed25519-sha512.c

   1 /*
   2  * implementing ed25519-sha512 from [1].
   3  *
   4  * This code is public domain.
   5  *
   6  * Philipp Lay <philipp.lay@illunis.net>
   7  *
   8  *
   9  * References:
  10  * [1] High-speed high-security signatures, 2011/09/26,
  11  *     Bernstein, Duif, Lange, Schwabe, Yang
  12  *
  13  * TODO:
  14  *   - batch verify
  15  */
  16
  17 #include <stdint.h>
  18 #include <stdbool.h>
  19 #include <stddef.h>
  20 #include <string.h>
  21
  22 #include "eddsa.h"
  23
  24 #include "sha512.h"
  25 #include "sc.h"
  26 #include "fld.h"
  27 #include "ed.h"
  28 #include "burnstack.h"
  29
  30
  31 static void
  32 ed25519_key_setup(uint8_t out[SHA512_HASH_LENGTH],
  33                   const uint8_t sk[ED25519_KEY_LEN])
  34 {
  35         struct sha512 hash;
  36
  37         /* hash secret-key */
  38         sha512_init(&hash);
  39         sha512_add(&hash, sk, ED25519_KEY_LEN);
  40         sha512_final(&hash, out);
  41
  42         /* delete bit 255 and set bit 254 */
  43         out[31] &= 0x7f;
  44         out[31] |= 0x40;
  45         /* delete 3 lowest bits */
  46         out[0] &= 0xf8;
  47 }
  48
  49
  50 /*
  51  * genpub - derive public key from secret key
  52  */
  53 static void
  54 genpub(uint8_t pub[ED25519_KEY_LEN], const uint8_t sec[ED25519_KEY_LEN])
  55 {
  56         uint8_t h[SHA512_HASH_LENGTH];
  57         struct ed A;
  58         sc_t a;
  59
  60         /* derive secret and import it */
  61         ed25519_key_setup(h, sec);
  62         sc_import(a, h, 32);
  63
  64         /* multiply with base point to calculate public key */
  65         ed_scale_base(&A, a);
  66         ed_export(pub, &A);
  67 }
  68
  69
  70 /*
  71  * ed25519_genpub - stack-clearing wrapper for genpub
  72  */
  73 void
  74 ed25519_genpub(uint8_t pub[ED25519_KEY_LEN], const uint8_t sec[ED25519_KEY_LEN])
  75 {
  76         genpub(pub, sec);
  77         burnstack(2048);
  78 }
  79
  80
  81 /*
  82  * sign - create ed25519 signature of data using secret key sec
  83  */
  84 static void
  85 sign(uint8_t sig[ED25519_SIG_LEN],
  86      const uint8_t sec[ED25519_KEY_LEN],
  87      const uint8_t pub[ED25519_KEY_LEN],
  88      const uint8_t *data, size_t len)
  89 {
  90         struct sha512 hash;
  91         uint8_t h[SHA512_HASH_LENGTH];
  92
  93         sc_t a, r, t, S;
  94         struct ed R;
  95
  96         /* derive secret scalar a */
  97         ed25519_key_setup(h, sec);
  98         sc_import(a, h, 32);
  99
 100         /* hash next 32 bytes together with data to form r */
 101         sha512_init(&hash);
 102         sha512_add(&hash, h+32, 32);
 103         sha512_add(&hash, data, len);
 104         sha512_final(&hash, h);
 105         sc_import(r, h, sizeof(h));
 106
 107         /* calculate R = r * B which form the first 256bit of the signature */
 108         ed_scale_base(&R, r);
 109         ed_export(sig, &R);
 110
 111         /* calculate t := Hash(export(R), export(A), data) mod m */
 112         sha512_init(&hash);
 113         sha512_add(&hash, sig, 32);
 114         sha512_add(&hash, pub, 32);
 115         sha512_add(&hash, data, len);
 116         sha512_final(&hash, h);
 117         sc_import(t, h, sizeof(h));
 118
 119         /* calculate S := r + t*a mod m and finish the signature */
 120         sc_mul(S, t, a);
 121         sc_add(S, r, S);
 122         sc_export(sig+32, S);
 123 }
 124
 125
 126 /*
 127  * ed25519_sign - stack-cleaning wrapper for sign
 128  */
 129 void
 130 ed25519_sign(uint8_t sig[ED25519_SIG_LEN],
 131            const uint8_t sec[ED25519_KEY_LEN],
 132            const uint8_t pub[ED25519_KEY_LEN],
 133            const uint8_t *data, size_t len)
 134 {
 135         sign(sig, sec, pub, data, len);
 136         burnstack(4096);
 137 }
 138
 139
 140 /*
 141  * ed25519_verify - verifies an ed25519-signature of given data.
 142  *
 143  * note: this functions runs in vartime and does no stack cleanup, since
 144  * all information are considered public.
 145  *
 146  * returns true if signature is ok and false otherwise.
 147  */
 148 bool
 149 ed25519_verify(const uint8_t sig[ED25519_SIG_LEN],
 150                const uint8_t pub[ED25519_KEY_LEN],
 151                const uint8_t *data, size_t len)
 152 {
 153         struct sha512 hash;
 154         uint8_t h[SHA512_HASH_LENGTH];
 155         struct ed A, C;
 156         sc_t t, S;
 157         uint8_t check[32];
 158
 159         /* import public key */
 160         ed_import(&A, pub);
 161
 162         /* import S from second half of the signature */
 163         sc_import(S, sig+32, 32);
 164
 165         /* calculate t := Hash(export(R), export(A), data) mod m */
 166         sha512_init(&hash);
 167         sha512_add(&hash, sig, 32);
 168         sha512_add(&hash, pub, 32);
 169         sha512_add(&hash, data, len);
 170         sha512_final(&hash, h);
 171         sc_import(t, h, 64);
 172
 173         /* verify signature (vartime!) */
 174         fld_neg(A.x, A.x);
 175         fld_neg(A.t, A.t);
 176         ed_dual_scale(&C, S, t, &A);
 177         ed_export(check, &C);
 178
 179         /* is export(C) == export(R) (vartime!) */
 180         return (memcmp(check, sig, 32) == 0);
 181 }
 182
 183
 184 /*
 185  * pk_ed25519_to_x25519 - convert a ed25519 public key to x25519
 186  */
 187 void
 188 pk_ed25519_to_x25519(uint8_t out[X25519_KEY_LEN], const uint8_t in[ED25519_KEY_LEN])
 189 {
 190         struct ed P;
 191         fld_t u, t;
 192
 193         /* import ed25519 public key */
 194         ed_import(&P, in);
 195
 196         /*
 197          * We now have the point P = (x,y) on the curve
 198          *
 199          *      x^2 + y^2 = 1 + (121665/121666)x^2y^2
 200          *
 201          * and want the u-component of the corresponding point
 202          * on the birationally equivalent montgomery curve
 203          *
 204          *      v^2 = u^3 + 486662 u^2 + u.
 205          *
 206          *
 207          * From the paper [1] we get
 208          *
 209          *      y = (u - 1) / (u + 1),
 210          *
 211          * which immediately yields
 212          *
 213          *      u = (1 + y) / (1 - y)
 214          *
 215          * or, by using projective coordinantes,
 216          *
 217          *      u = (z + y) / (z - y).
 218          */
 219
 220         /* u <- z + y */
 221         fld_add(u, P.z, P.y);
 222
 223         /* t <- (z - y)^-1 */
 224         fld_sub(t, P.z, P.y);
 225         fld_inv(t, t);
 226
 227         /* u <- u * t = (z+y) / (z-y) */
 228         fld_mul(u, u, t);
 229
 230         /* export curve25519 public key */
 231         fld_export(out, u);
 232 }
 233
 234
 235
 236 /*
 237  * conv_sk_ed25519_to_x25519 - convert a ed25519 secret key to x25519 secret.
 238  */
 239 static void
 240 conv_sk_ed25519_to_x25519(uint8_t out[X25519_KEY_LEN], const uint8_t in[ED25519_KEY_LEN])
 241 {
 242         uint8_t h[SHA512_HASH_LENGTH];
 243         ed25519_key_setup(h, in);
 244         memcpy(out, h, X25519_KEY_LEN);
 245 }
 246
 247
 248 /*
 249  * sk_ed25519_to_x25519 - stack-clearing wrapper for conv_sk_ed25519_to_x25519.
 250  */
 251 void
 252 sk_ed25519_to_x25519(uint8_t out[X25519_KEY_LEN], const uint8_t in[ED25519_KEY_LEN])
 253 {
 254         conv_sk_ed25519_to_x25519(out, in);
 255         burnstack(1024);
 256 }
 257
 258
 259
 260
 261
 262 /*
 263  * Obsolete Interface, this will be removed in the future.
 264  */
 265
 266
 267 /*
 268  * eddsa_genpub - stack-clearing wrapper for genpub (obsolete interface!)
 269  */
 270 void
 271 eddsa_genpub(uint8_t pub[32], const uint8_t sec[32])
 272 {
 273         genpub(pub, sec);
 274         burnstack(2048);
 275 }
 276
 277
 278 /*
 279  * eddsa_sign - stack-cleaning wrapper for sign (obsolete interface!)
 280  */
 281 void
 282 eddsa_sign(uint8_t sig[ED25519_SIG_LEN],
 283            const uint8_t sec[ED25519_KEY_LEN],
 284            const uint8_t pub[ED25519_KEY_LEN],
 285            const uint8_t *data, size_t len)
 286 {
 287         sign(sig, sec, pub, data, len);
 288         burnstack(4096);
 289 }
 290
 291 /*
 292  * eddsa_verify - verifies an ed25519 signature of given data.
 293  * (obsolete interface!)
 294  *
 295  */
 296 bool
 297 eddsa_verify(const uint8_t sig[ED25519_SIG_LEN],
 298              const uint8_t pub[ED25519_KEY_LEN],
 299              const uint8_t *data, size_t len)
 300 {
 301         return ed25519_verify(sig, pub, data, len);
 302 }
 303
 304 /*
 305  * eddsa_pk_eddsa_to_dh - convert a ed25519 public key to x25519.
 306  * (obsolete interface!)
 307  */
 308 void
 309 eddsa_pk_eddsa_to_dh(uint8_t out[X25519_KEY_LEN], const uint8_t in[ED25519_KEY_LEN])
 310 {
 311         pk_ed25519_to_x25519(out, in);
 312 }
 313
 314
 315 /*
 316  * eddsa_sk_eddsa_to_dh - convert a ed25519 secret key to x25519 secret.
 317  * (obsolete interface!)
 318  */
 319 void
 320 eddsa_sk_eddsa_to_dh(uint8_t out[X25519_KEY_LEN], const uint8_t in[ED25519_KEY_LEN])
 321 {
 322         conv_sk_ed25519_to_x25519(out, in);
 323         burnstack(1024);
 324 }