| 1 | /* -*-c-*- |
| 2 | * |
| 3 | * The Ed448 signature scheme |
| 4 | * |
| 5 | * (c) 2017 Straylight/Edgeware |
| 6 | */ |
| 7 | |
| 8 | /*----- Licensing notice --------------------------------------------------* |
| 9 | * |
| 10 | * This file is part of secnet. |
| 11 | * See README for full list of copyright holders. |
| 12 | * |
| 13 | * secnet is free software; you can redistribute it and/or modify it |
| 14 | * under the terms of the GNU General Public License as published by |
| 15 | * the Free Software Foundation; either version d of the License, or |
| 16 | * (at your option) any later version. |
| 17 | * |
| 18 | * secnet is distributed in the hope that it will be useful, but |
| 19 | * WITHOUT ANY WARRANTY; without even the implied warranty of |
| 20 | * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU |
| 21 | * General Public License for more details. |
| 22 | * |
| 23 | * You should have received a copy of the GNU General Public License |
| 24 | * version 3 along with secnet; if not, see |
| 25 | * https://www.gnu.org/licenses/gpl.html. |
| 26 | * |
| 27 | * This file was originally part of Catacomb, but has been automatically |
| 28 | * modified for incorporation into secnet: see `import-catacomb-crypto' |
| 29 | * for details. |
| 30 | * |
| 31 | * Catacomb is free software; you can redistribute it and/or modify |
| 32 | * it under the terms of the GNU Library General Public License as |
| 33 | * published by the Free Software Foundation; either version 2 of the |
| 34 | * License, or (at your option) any later version. |
| 35 | * |
| 36 | * Catacomb is distributed in the hope that it will be useful, |
| 37 | * but WITHOUT ANY WARRANTY; without even the implied warranty of |
| 38 | * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the |
| 39 | * GNU Library General Public License for more details. |
| 40 | * |
| 41 | * You should have received a copy of the GNU Library General Public |
| 42 | * License along with Catacomb; if not, write to the Free |
| 43 | * Software Foundation, Inc., 59 Temple Place - Suite 330, Boston, |
| 44 | * MA 02111-1307, USA. |
| 45 | */ |
| 46 | |
| 47 | /*----- Header files ------------------------------------------------------*/ |
| 48 | |
| 49 | #include <string.h> |
| 50 | |
| 51 | #include "fgoldi.h" |
| 52 | #include "ed448.h" |
| 53 | #include "scaf.h" |
| 54 | #include "scmul.h" |
| 55 | #include "sha3.h" |
| 56 | |
| 57 | /*----- A number of magic numbers -----------------------------------------*/ |
| 58 | |
| 59 | # define PIECEWD 24 |
| 60 | static const scaf_piece l[] = { |
| 61 | 0x5844f3, 0xc292ab, 0x552378, 0x8dc58f, 0x6cc272, |
| 62 | 0x369021, 0x49aed6, 0xc44edb, 0xca23e9, 0xffff7c, |
| 63 | 0xffffff, 0xffffff, 0xffffff, 0xffffff, 0xffffff, |
| 64 | 0xffffff, 0xffffff, 0xffffff, 0x003fff |
| 65 | }; |
| 66 | static const scaf_piece mu[] = { |
| 67 | 0xe0d00a, 0x4a7bb0, 0x73d6d5, 0x0aadc8, 0xd723a7, |
| 68 | 0xe933d8, 0x9c96fd, 0x4b6512, 0x63bb12, 0x335dc1, |
| 69 | 0x000008, 0x000000, 0x000000, 0x000000, 0x000000, |
| 70 | 0x000000, 0x000000, 0x000000, 0x000000, 0x000400 |
| 71 | }; |
| 72 | |
| 73 | #define NPIECE SCAF_NPIECE(448, PIECEWD) |
| 74 | |
| 75 | # define P p28 |
| 76 | static const fgoldi_piece bx_pieces[] = { |
| 77 | 118276190, 40534716, 9670182, -133293904, |
| 78 | 85017404, -9262234, 68333083, -96650682, |
| 79 | -93461723, 15824511, 73756743, 57518561, |
| 80 | 94773951, -19783215, 107736334, 82941708 |
| 81 | }, by_pieces[] = { |
| 82 | 36764180, 8885695, 130592152, 20104429, |
| 83 | -104530499, 30304196, 121295871, 5901357, |
| 84 | 125344798, -96893944, -93097107, -59366209, |
| 85 | 3626698, 38307682, 24032956, 110359655 |
| 86 | }; |
| 87 | |
| 88 | static const fgoldi_piece bz_pieces[NPIECE] = { 1, 0, /* ... */ }; |
| 89 | #define BX ((const fgoldi *)bx_pieces) |
| 90 | #define BY ((const fgoldi *)by_pieces) |
| 91 | #define BZ ((const fgoldi *)bz_pieces) |
| 92 | #define D (-39081) |
| 93 | |
| 94 | /*----- Point encoding and decoding ---------------------------------------*/ |
| 95 | |
| 96 | static void ptencode(octet q[57], |
| 97 | const fgoldi *X, const fgoldi *Y, const fgoldi *Z) |
| 98 | { |
| 99 | fgoldi x, y, t; |
| 100 | octet b[56]; |
| 101 | |
| 102 | fgoldi_inv(&t, Z); fgoldi_mul(&x, X, &t); fgoldi_mul(&y, Y, &t); |
| 103 | fgoldi_store(q, &y); fgoldi_store(b, &x); q[56] = (b[0]&1u) << 7; |
| 104 | } |
| 105 | |
| 106 | static int ptdecode(fgoldi *X, fgoldi *Y, fgoldi *Z, const octet q[57]) |
| 107 | { |
| 108 | octet b[56]; |
| 109 | unsigned i, a; |
| 110 | fgoldi t, u; |
| 111 | uint32 m; |
| 112 | int rc = 0; |
| 113 | |
| 114 | /* Load the y-coordinate. */ |
| 115 | fgoldi_load(Y, q); |
| 116 | |
| 117 | /* Check that the coordinate was in range. If we store it, we'll get a |
| 118 | * canonical version which we can compare against Q. Also, check that the |
| 119 | * extra bits in the top byte are zero. |
| 120 | */ |
| 121 | fgoldi_store(b, Y); |
| 122 | for (i = a = 0; i < 56; i++) a |= b[i] ^ q[i]; |
| 123 | a |= q[56]&0x7fu; |
| 124 | a = ((a - 1) >> 8)&0x01u; /* 0 |-> 1, non-0 |-> 0 */ |
| 125 | rc |= (int)a - 1; |
| 126 | |
| 127 | /* Decompress the x-coordinate. */ |
| 128 | fgoldi_sqr(&t, Y); fgoldi_mulconst(&u, &t, D); t.P[0] -= 1; u.P[0] -= 1; |
| 129 | rc |= fgoldi_quosqrt(X, &t, &u); |
| 130 | fgoldi_store(b, X); m = -(uint32)(((q[56] >> 7) ^ b[0])&0x1u); |
| 131 | fgoldi_condneg(X, X, m); |
| 132 | |
| 133 | /* Set Z. */ |
| 134 | fgoldi_set(Z, 1); |
| 135 | |
| 136 | /* And we're done. */ |
| 137 | return (rc); |
| 138 | } |
| 139 | |
| 140 | /*----- Edwards curve arithmetic ------------------------------------------*/ |
| 141 | |
| 142 | static void ptadd(fgoldi *X, fgoldi *Y, fgoldi *Z, |
| 143 | const fgoldi *X0, const fgoldi *Y0, const fgoldi *Z0, |
| 144 | const fgoldi *X1, const fgoldi *Y1, const fgoldi *Z1) |
| 145 | { |
| 146 | fgoldi t0, t1, t2, t3; |
| 147 | |
| 148 | /* Bernstein and Lange, `Faster addition and doubling on elliptic curves', |
| 149 | * 2007-09-06, https://cr.yp.to/newelliptic/newelliptic-20070906.pdf shows |
| 150 | * the formulae as: |
| 151 | * |
| 152 | * A = Z1 Z2; B = A^2; C = X1 X2; D = Y1 Y2; |
| 153 | * E = d C D; F = B - E; G = B + E; |
| 154 | * X3 = A F ((X1 + Y1) (X2 + Y2) - C - D); |
| 155 | * Y3 = A G (D - C); Z3 = c F G. |
| 156 | * |
| 157 | * But c = 1 here. |
| 158 | */ |
| 159 | |
| 160 | fgoldi_mul(&t0, Z0, Z1); /* t0 = A = Z0 Z1 */ |
| 161 | fgoldi_add(&t1, X0, Y0); /* t1 = X0 + Y0 */ |
| 162 | fgoldi_add(&t2, X1, Y1); /* t2 = X1 + Y1 */ |
| 163 | fgoldi_mul(&t1, &t1, &t2); /* t1 = (X0 + Y0) (X1 + Y1) */ |
| 164 | fgoldi_mul(&t2, X0, X1); /* t2 = C = X0 X1 */ |
| 165 | fgoldi_mul(&t3, Y0, Y1); /* t3 = D = Y0 Y1 */ |
| 166 | fgoldi_sub(X, &t1, &t2); /* X = (X0 + Y0) (X1 + Y1) - C */ |
| 167 | fgoldi_sub(X, X, &t3); /* X = (X0 + Y0) (X1 + Y1) - C - D */ |
| 168 | fgoldi_sub(Y, &t3, &t2); /* Y = D - C */ |
| 169 | fgoldi_mul(X, X, &t0); /* X = A ((X0 + Y0) (X1 + Y1) - C - D) */ |
| 170 | fgoldi_mul(Y, Y, &t0); /* Y = A (D - C) */ |
| 171 | fgoldi_sqr(&t0, &t0); /* t0 = B = A^2 */ |
| 172 | fgoldi_mul(&t1, &t2, &t3); /* t1 = C D */ |
| 173 | fgoldi_mulconst(&t1, &t1, D); /* t1 = E = d C D */ |
| 174 | fgoldi_sub(&t2, &t0, &t1); /* t2 = F = B - E */ |
| 175 | fgoldi_add(&t1, &t0, &t1); /* t1 = G = B + E */ |
| 176 | fgoldi_mul(X, X, &t2); /* X = A F ((X0 + Y0) (X1 + Y1) - C - D) */ |
| 177 | fgoldi_mul(Y, Y, &t1); /* Y = A G (D - C) */ |
| 178 | fgoldi_mul(Z, &t1, &t2); /* Z = c F G */ |
| 179 | } |
| 180 | |
| 181 | static void ptdbl(fgoldi *X, fgoldi *Y, fgoldi *Z, |
| 182 | const fgoldi *X0, const fgoldi *Y0, const fgoldi *Z0) |
| 183 | { |
| 184 | fgoldi t0, t1, t2; |
| 185 | |
| 186 | /* Bernstein and Lange, `Faster addition and doubling on elliptic curves', |
| 187 | * 2007-09-06, https://cr.yp.to/newelliptic/newelliptic-20070906.pdf shows |
| 188 | * the formulae as: |
| 189 | * |
| 190 | * B = (X1 + Y1)^2; C = X1^2; D = Y1^2; |
| 191 | * E = C + D; H = (c Z1)^2; J = E - 2 H; |
| 192 | * X3 = c (B - E) J; Y3 = c E (C - D); Z3 = E J |
| 193 | * |
| 194 | * But c = 1 here. |
| 195 | */ |
| 196 | |
| 197 | fgoldi_add(&t0, X0, Y0); /* t0 = X0 + Y0 */ |
| 198 | fgoldi_sqr(&t0, &t0); /* t0 = B = (X0 + Y0)^2 */ |
| 199 | fgoldi_sqr(&t1, X0); /* t1 = C = X0^2 */ |
| 200 | fgoldi_sqr(&t2, Y0); /* t2 = D = Y0^2 */ |
| 201 | fgoldi_add(Y, &t1, &t2); /* Y = E = C + D */ |
| 202 | fgoldi_sub(&t1, &t1, &t2); /* t1 = C - D */ |
| 203 | fgoldi_sub(X, &t0, Y); /* X = c (B - E) */ |
| 204 | fgoldi_sqr(&t0, Z0); /* t0 = H = (c Z0)^2 */ |
| 205 | fgoldi_add(&t0, &t0, &t0); /* t0 = 2 H */ |
| 206 | fgoldi_sub(&t0, Y, &t0); /* t0 = J = E - 2 H */ |
| 207 | fgoldi_mul(X, X, &t0); /* X = c (B - E) J */ |
| 208 | fgoldi_mul(Z, Y, &t0); /* Z = E J */ |
| 209 | fgoldi_mul(Y, Y, &t1); /* Y = c E (C - D) */ |
| 210 | } |
| 211 | |
| 212 | static DEFINE_SCMUL(ptmul, fgoldi, 4, PIECEWD, NPIECE, ptadd, ptdbl) |
| 213 | static DEFINE_SCSIMMUL(ptsimmul, fgoldi, 2, PIECEWD, NPIECE, ptadd, ptdbl) |
| 214 | |
| 215 | /*----- Key derivation utilities ------------------------------------------*/ |
| 216 | |
| 217 | static void unpack_key(scaf_piece a[NPIECE], octet h1[57], |
| 218 | const octet *k, size_t ksz) |
| 219 | { |
| 220 | shake_ctx h; |
| 221 | octet b[57]; |
| 222 | |
| 223 | shake256_init(&h); shake_hash(&h, k, ksz); |
| 224 | shake_xof(&h); shake_get(&h, b, sizeof(b)); |
| 225 | b[0] &= 0xfcu; b[55] |= 0x80u; scaf_load(a, b, 56, NPIECE, PIECEWD); |
| 226 | if (h1) shake_get(&h, h1, 57); |
| 227 | } |
| 228 | |
| 229 | #define PREFIX_BUFSZ 266 |
| 230 | static size_t prefix(octet b[PREFIX_BUFSZ], |
| 231 | int phflag, const octet *p, size_t psz) |
| 232 | { |
| 233 | memcpy(b, "SigEd448", 8); |
| 234 | b[8] = phflag; |
| 235 | assert(psz <= ED448_MAXPERSOSZ); b[9] = psz; memcpy(b + 10, p, psz); |
| 236 | return (psz + 10); |
| 237 | } |
| 238 | |
| 239 | /*----- Main code ---------------------------------------------------------*/ |
| 240 | |
| 241 | /* --- @ed448_pubkey@ --- * |
| 242 | * |
| 243 | * Arguments: @octet K[ED448_PUBSZ]@ = where to put the public key |
| 244 | * @const void *k@ = private key |
| 245 | * @size_t ksz@ = length of private key |
| 246 | * |
| 247 | * Returns: --- |
| 248 | * |
| 249 | * Use: Derives the public key from a private key. |
| 250 | */ |
| 251 | |
| 252 | void ed448_pubkey(octet K[ED448_PUBSZ], const void *k, size_t ksz) |
| 253 | { |
| 254 | scaf_piece a[NPIECE]; |
| 255 | fgoldi AX, AY, AZ; |
| 256 | |
| 257 | unpack_key(a, 0, k, ksz); |
| 258 | ptmul(&AX, &AY, &AZ, a, BX, BY, BZ); |
| 259 | ptencode(K, &AX, &AY, &AZ); |
| 260 | } |
| 261 | |
| 262 | /* --- @ed448_sign@ --- * |
| 263 | * |
| 264 | * Arguments: @octet sig[ED448_SIGSZ]@ = where to put the signature |
| 265 | * @const void *k@ = private key |
| 266 | * @size_t ksz@ = length of private key |
| 267 | * @const octet K[ED448_PUBSZ]@ = public key |
| 268 | * @int phflag@ = whether the `message' has been hashed already |
| 269 | * @const void *p@ = personalization string |
| 270 | * @size_t psz@ = length of personalization string |
| 271 | * @const void *m@ = message to sign |
| 272 | * @size_t msz@ = length of message |
| 273 | * |
| 274 | * Returns: --- |
| 275 | * |
| 276 | * Use: Signs a message. |
| 277 | */ |
| 278 | |
| 279 | void ed448_sign(octet sig[ED448_SIGSZ], |
| 280 | const void *k, size_t ksz, const octet K[ED448_PUBSZ], |
| 281 | int phflag, const void *p, size_t psz, |
| 282 | const void *m, size_t msz) |
| 283 | { |
| 284 | shake_ctx h; |
| 285 | scaf_piece a[NPIECE], r[NPIECE], t[NPIECE], scratch[3*NPIECE]; |
| 286 | scaf_dblpiece tt[2*NPIECE]; |
| 287 | fgoldi RX, RY, RZ; |
| 288 | octet h1[57], pb[PREFIX_BUFSZ], rb[114]; |
| 289 | unsigned i; |
| 290 | |
| 291 | /* Get my private key. */ |
| 292 | unpack_key(a, h1, k, ksz); |
| 293 | |
| 294 | /* Determine the prefix string. */ |
| 295 | psz = prefix(pb, phflag, p, psz); |
| 296 | |
| 297 | /* Select the nonce and the vector part. */ |
| 298 | shake256_init(&h); |
| 299 | shake_hash(&h, pb, psz); |
| 300 | shake_hash(&h, h1, sizeof(h1)); |
| 301 | shake_hash(&h, m, msz); |
| 302 | shake_done(&h, rb, 114); |
| 303 | scaf_loaddbl(tt, rb, 114, 2*NPIECE, PIECEWD); |
| 304 | scaf_reduce(r, tt, l, mu, NPIECE, PIECEWD, scratch); |
| 305 | ptmul(&RX, &RY, &RZ, r, BX, BY, BZ); |
| 306 | ptencode(sig, &RX, &RY, &RZ); |
| 307 | |
| 308 | /* Calculate the scalar part. */ |
| 309 | shake256_init(&h); |
| 310 | shake_hash(&h, pb, psz); |
| 311 | shake_hash(&h, sig, 57); |
| 312 | shake_hash(&h, K, 57); |
| 313 | shake_hash(&h, m, msz); |
| 314 | shake_done(&h, rb, 114); |
| 315 | scaf_loaddbl(tt, rb, 114, 2*NPIECE, PIECEWD); |
| 316 | scaf_reduce(t, tt, l, mu, NPIECE, PIECEWD, scratch); |
| 317 | scaf_mul(tt, t, a, NPIECE); |
| 318 | for (i = 0; i < NPIECE; i++) tt[i] += r[i]; |
| 319 | scaf_reduce(t, tt, l, mu, NPIECE, PIECEWD, scratch); |
| 320 | scaf_store(sig + 57, 57, t, NPIECE, PIECEWD); |
| 321 | } |
| 322 | |
| 323 | /* --- @ed448_verify@ --- * |
| 324 | * |
| 325 | * Arguments: @const octet K[ED448_PUBSZ]@ = public key |
| 326 | * @const void *m@ = message to sign |
| 327 | * @int phflag@ = whether the `message' has been hashed already |
| 328 | * @const void *p@ = personalization string |
| 329 | * @size_t psz@ = length of personalization string |
| 330 | * @size_t msz@ = length of message |
| 331 | * @const octet sig[ED448_SIGSZ]@ = signature |
| 332 | * |
| 333 | * Returns: Zero if OK, negative on failure. |
| 334 | * |
| 335 | * Use: Verify a signature. |
| 336 | */ |
| 337 | |
| 338 | int ed448_verify(const octet K[ED448_PUBSZ], |
| 339 | int phflag, const void *p, size_t psz, |
| 340 | const void *m, size_t msz, |
| 341 | const octet sig[ED448_SIGSZ]) |
| 342 | { |
| 343 | shake_ctx h; |
| 344 | scaf_piece s[NPIECE], t[NPIECE], scratch[3*NPIECE]; |
| 345 | scaf_dblpiece tt[2*NPIECE]; |
| 346 | fgoldi AX, AY, AZ, RX, RY, RZ; |
| 347 | octet b[PREFIX_BUFSZ]; |
| 348 | |
| 349 | /* Unpack the public key. Negate it: we're meant to subtract the term |
| 350 | * involving the public key point, and this is easier than negating the |
| 351 | * scalar. |
| 352 | */ |
| 353 | if (ptdecode(&AX, &AY, &AZ, K)) return (-1); |
| 354 | fgoldi_neg(&AX, &AX); |
| 355 | |
| 356 | /* Load the scalar and check that it's in range. The easy way is to store |
| 357 | * it again and see if the two match. |
| 358 | */ |
| 359 | scaf_loaddbl(tt, sig + 57, 57, 2*NPIECE, PIECEWD); |
| 360 | scaf_reduce(s, tt, l, mu, NPIECE, PIECEWD, scratch); |
| 361 | scaf_store(b, 57, s, NPIECE, PIECEWD); |
| 362 | if (memcmp(b, sig + 57, 57) != 0) return (-1); |
| 363 | |
| 364 | /* Check the signature. */ |
| 365 | psz = prefix(b, phflag, p, psz); |
| 366 | shake256_init(&h); |
| 367 | shake_hash(&h, b, psz); |
| 368 | shake_hash(&h, sig, 57); |
| 369 | shake_hash(&h, K, ED448_PUBSZ); |
| 370 | shake_hash(&h, m, msz); |
| 371 | shake_done(&h, b, 114); |
| 372 | scaf_loaddbl(tt, b, 114, 2*NPIECE, PIECEWD); |
| 373 | scaf_reduce(t, tt, l, mu, NPIECE, PIECEWD, scratch); |
| 374 | ptsimmul(&RX, &RY, &RZ, s, BX, BY, BZ, t, &AX, &AY, &AZ); |
| 375 | ptencode(b, &RX, &RY, &RZ); |
| 376 | if (memcmp(b, sig, 57) != 0) return (-1); |
| 377 | |
| 378 | /* All is good. */ |
| 379 | return (0); |
| 380 | } |
| 381 | |
| 382 | /*----- That's all, folks -------------------------------------------------*/ |