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

   1 /*
   2  * implement x25519 diffie-hellman from [1].
   3  *
   4  * This code is public domain.
   5  *
   6  * Philipp Lay <philipp.lay@illunis.net>
   7  *
   8  * References:
   9  * [1] Curve25519: new Diffie-Hellman speed records, 2006/02/09, Bernstein.
  10  */
  11
  12 #include <stdint.h>
  13 #include <string.h>
  14
  15 #include "eddsa.h"
  16
  17 #include "fld.h"
  18 #include "burnstack.h"
  19
  20 #include "ed.h"
  21
  22
  23 /*
  24  * structure for a point of the elliptic curve in montgomery form
  25  * without it's y-coordinate.
  26  */
  27 struct mg {
  28         fld_t   x;
  29         fld_t   z;
  30 };
  31
  32
  33 /*
  34  * ctmemswap - helper function to conditionally swap a with b
  35  */
  36 static void
  37 ctmemswap(void *a, void *b, size_t len, uint8_t mask)
  38 {
  39         uint8_t *pa = (uint8_t*)a;
  40         uint8_t *pb = (uint8_t*)b;
  41         uint8_t *endp = pa + len;
  42         uint8_t delta;
  43
  44         while (pa < endp) {
  45                 delta = (*pa ^ *pb) & mask;
  46                 *pa++ ^= delta;
  47                 *pb++ ^= delta;
  48         }
  49 }
  50
  51
  52
  53 /*
  54  * montgomery - calculate montgomery's double-and-add formula
  55  *
  56  * input: A, B, C := A-B with z=1
  57  * output: A <- 2*A, B <- A+B
  58  *
  59  */
  60 static void
  61 montgomery(struct mg *A, struct mg *B, const struct mg *C)
  62 {
  63         fld_t sumA, subA, sqsumA, sqsubA;
  64         fld_t sumB, subB;
  65         fld_t T1, T2, T3;
  66
  67         /* calculate 2*A */
  68         fld_add(sumA, A->x, A->z);
  69         fld_sq(sqsumA, sumA);
  70
  71         fld_sub(subA, A->x, A->z);
  72         fld_sq(sqsubA, subA);
  73
  74         fld_mul(A->x, sqsubA, sqsumA);
  75
  76         fld_sub(T1, sqsumA, sqsubA);
  77         fld_scale(T2, T1, 121665);
  78         fld_add(T2, T2, sqsumA);
  79         fld_mul(A->z, T1, T2);
  80
  81         /* calculate A + B */
  82         fld_add(sumB, B->x, B->z);
  83         fld_sub(subB, B->x, B->z);
  84
  85         fld_mul(T1, subA, sumB);
  86         fld_mul(T2, sumA, subB);
  87
  88         fld_add(T3, T1, T2);
  89         fld_sq(B->x, T3);
  90
  91         fld_sub(T3, T1, T2);
  92         fld_sq(T3, T3);
  93         fld_mul(B->z, T3, C->x);
  94 }
  95
  96
  97 /*
  98  * mg_scale - calculates x * P with montgomery formula.
  99  *
 100  * assumes:
 101  *   out != P
 102  *   P->z must be 1
 103  */
 104 static void
 105 mg_scale(struct mg *out, const struct mg *P, const uint8_t x[X25519_KEY_LEN])
 106 {
 107         struct mg T;
 108         int8_t foo;
 109         int i, j;
 110
 111         fld_set0(out->x, 1);
 112         fld_set0(out->z, 0);
 113         memcpy(&T, P, sizeof(struct mg));
 114
 115         for (i = X25519_KEY_LEN-1; i >= 0; i--) {
 116                 foo = x[i];
 117                 for (j = 8; j > 0; j--, foo <<= 1) {
 118                         ctmemswap(out, &T, sizeof(struct mg), foo >> 7);
 119                         montgomery(out, &T, P);
 120                         ctmemswap(out, &T, sizeof(struct mg), foo >> 7);
 121                 }
 122         }
 123 }
 124
 125
 126 /*
 127  * do_x25519 - calculates x25519 diffie-hellman using montgomery form
 128  */
 129 static void
 130 do_x25519(uint8_t out[X25519_KEY_LEN],
 131              const uint8_t scalar[X25519_KEY_LEN],
 132              const uint8_t point[X25519_KEY_LEN])
 133 {
 134         struct mg res, P;
 135         uint8_t s[X25519_KEY_LEN];
 136
 137         memcpy(s, scalar, X25519_KEY_LEN);
 138         s[0] &= 0xf8;
 139         s[31] &= 0x7f;
 140         s[31] |= 0x40;
 141
 142         fld_import(P.x, point);
 143         fld_set0(P.z, 1);
 144
 145         mg_scale(&res, &P, s);
 146
 147         fld_inv(res.z, res.z);
 148         fld_mul(res.x, res.x, res.z);
 149         fld_export(out, res.x);
 150 }
 151
 152
 153 /*
 154  * do_x25519_base - calculate a x25519 diffie-hellman public value
 155  *
 156  */
 157
 158 static void
 159 do_x25519_base(uint8_t out[X25519_KEY_LEN],
 160                const uint8_t scalar[X25519_KEY_LEN])
 161 {
 162         uint8_t tmp[X25519_KEY_LEN];
 163
 164         sc_t x;
 165         struct ed R;
 166         fld_t u, t;
 167
 168         /*
 169          * clear bits on input and import it as x
 170          */
 171         memcpy(tmp, scalar, X25519_KEY_LEN);
 172         tmp[0] &= 0xf8;
 173         tmp[31] &= 0x7f;
 174         tmp[31] |= 0x40;
 175
 176         sc_import(x, tmp, sizeof(tmp));
 177
 178
 179         /*
 180          * scale our base point on edwards curve
 181          */
 182         ed_scale_base(&R, x);
 183
 184
 185         /*
 186          * extract montgomery coordinate u from edwards point R
 187          */
 188
 189         /* u <- (z + y) / (z - y) */
 190         fld_sub(t, R.z, R.y);
 191         fld_inv(t, t);
 192         fld_add(u, R.z, R.y);
 193         fld_mul(u, u, t);
 194
 195
 196         fld_export(out, u);
 197 }
 198
 199
 200 /*
 201  * x25519_base - wrapper around do_x25519_base with stack cleaning
 202  */
 203 void
 204 x25519_base(uint8_t out[X25519_KEY_LEN],
 205             const uint8_t scalar[X25519_KEY_LEN])
 206 {
 207         do_x25519_base(out, scalar);
 208         burnstack(2048);
 209 }
 210
 211
 212
 213
 214 /* x25519 - wrapper for do_x25519 with stack-cleanup */
 215 void
 216 x25519(uint8_t out[X25519_KEY_LEN],
 217        const uint8_t scalar[X25519_KEY_LEN],
 218        const uint8_t point[X25519_KEY_LEN])
 219 {
 220         do_x25519(out, scalar, point);
 221         burnstack(2048);
 222 }
 223
 224
 225
 226
 227
 228 /*
 229  * Obsolete Interface, this will be removed in the future.
 230  */
 231
 232
 233 /*
 234  * DH - stack-cleanup wrapper for do_x25519 (obsolete interface)
 235  */
 236 void
 237 DH(uint8_t out[X25519_KEY_LEN],
 238    const uint8_t sec[X25519_KEY_LEN],
 239    const uint8_t point[X25519_KEY_LEN])
 240 {
 241         do_x25519(out, sec, point);
 242         burnstack(2048);
 243 }