3 * The Ed448 signature scheme
5 * (c) 2017 Straylight/Edgeware
8 /*----- Licensing notice --------------------------------------------------*
10 * This file is part of Catacomb.
12 * Catacomb is free software; you can redistribute it and/or modify
13 * it under the terms of the GNU Library General Public License as
14 * published by the Free Software Foundation; either version 2 of the
15 * License, or (at your option) any later version.
17 * Catacomb is distributed in the hope that it will be useful,
18 * but WITHOUT ANY WARRANTY; without even the implied warranty of
19 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
20 * GNU Library General Public License for more details.
22 * You should have received a copy of the GNU Library General Public
23 * License along with Catacomb; if not, write to the Free
24 * Software Foundation, Inc., 59 Temple Place - Suite 330, Boston,
28 /*----- Header files ------------------------------------------------------*/
32 #include <mLib/macros.h>
40 /*----- Key fetching ------------------------------------------------------*/
42 const key_fetchdef ed448_pubfetch
[] = {
43 { "pub", offsetof(ed448_pub
, pub
), KENC_BINARY
, 0 },
47 static const key_fetchdef priv
[] = {
48 { "priv", offsetof(ed448_priv
, priv
), KENC_BINARY
, 0 },
52 const key_fetchdef ed448_privfetch
[] = {
53 { "pub", offsetof(ed448_priv
, pub
), KENC_BINARY
, 0 },
54 { "private", 0, KENC_STRUCT
, priv
},
58 /*----- A number of magic numbers -----------------------------------------*/
62 static const scaf_piece l
[] = {
63 0x5844f3, 0xc292ab, 0x552378, 0x8dc58f, 0x6cc272,
64 0x369021, 0x49aed6, 0xc44edb, 0xca23e9, 0xffff7c,
65 0xffffff, 0xffffff, 0xffffff, 0xffffff, 0xffffff,
66 0xffffff, 0xffffff, 0xffffff, 0x003fff
68 static const scaf_piece mu
[] = {
69 0xe0d00a, 0x4a7bb0, 0x73d6d5, 0x0aadc8, 0xd723a7,
70 0xe933d8, 0x9c96fd, 0x4b6512, 0x63bb12, 0x335dc1,
71 0x000008, 0x000000, 0x000000, 0x000000, 0x000000,
72 0x000000, 0x000000, 0x000000, 0x000000, 0x000400
78 static const scaf_piece l
[] = {
79 0x4f3, 0x584, 0x2ab, 0xc29, 0x378, 0x552, 0x58f, 0x8dc,
80 0x272, 0x6cc, 0x021, 0x369, 0xed6, 0x49a, 0xedb, 0xc44,
81 0x3e9, 0xca2, 0xf7c, 0xfff, 0xfff, 0xfff, 0xfff, 0xfff,
82 0xfff, 0xfff, 0xfff, 0xfff, 0xfff, 0xfff, 0xfff, 0xfff,
83 0xfff, 0xfff, 0xfff, 0xfff, 0xfff, 0x003
85 static const scaf_piece mu
[] = {
86 0x00a, 0xe0d, 0xbb0, 0x4a7, 0x6d5, 0x73d, 0xdc8, 0x0aa,
87 0x3a7, 0xd72, 0x3d8, 0xe93, 0x6fd, 0x9c9, 0x512, 0x4b6,
88 0xb12, 0x63b, 0xdc1, 0x335, 0x008, 0x000, 0x000, 0x000,
89 0x000, 0x000, 0x000, 0x000, 0x000, 0x000, 0x000, 0x000,
90 0x000, 0x000, 0x000, 0x000, 0x000, 0x000, 0x400
94 #define NPIECE SCAF_NPIECE(448, PIECEWD)
98 static const fgoldi_piece bx_pieces
[] = {
99 118276190, 40534716, 9670182, -133293904,
100 85017404, -9262234, 68333083, -96650682,
101 -93461723, 15824511, 73756743, 57518561,
102 94773951, -19783215, 107736334, 82941708
104 36764180, 8885695, 130592152, 20104429,
105 -104530499, 30304196, 121295871, 5901357,
106 125344798, -96893944, -93097107, -59366209,
107 3626698, 38307682, 24032956, 110359655
110 #if FGOLDI_IMPL == 12
112 static const fgoldi_piece bx_pieces
[] = {
113 94, 204, -114, 523, 309, -474, 313, -511, 99, -1017,
114 828, 276, -822, 686, -71, -485, 299, 200, -791, -737,
115 805, -290, -43, -550, 121, 71, -425, -983, -344, 439,
116 703, 610, 555, 135, -151, -754, -321, 397, -420, 633
118 -1516, 784, -28, -425, 68, -616, -885, -592, 788, 153,
119 -579, -944, 116, 415, 231, 1023, 941, -594, 49, 45,
120 -994, -118, 271, -496, -739, 877, -201, -43, 147, -453,
121 1738, 885, -960, 542, 292, 1724, -277, -797, -46, 842
125 static const fgoldi_piece bz_pieces
[NPIECE
] = { 1, 0, /* ... */ };
126 #define BX ((const fgoldi *)bx_pieces)
127 #define BY ((const fgoldi *)by_pieces)
128 #define BZ ((const fgoldi *)bz_pieces)
131 /*----- Point encoding and decoding ---------------------------------------*/
133 static void ptencode(octet q
[57],
134 const fgoldi
*X
, const fgoldi
*Y
, const fgoldi
*Z
)
139 fgoldi_inv(&t
, Z
); fgoldi_mul(&x
, X
, &t
); fgoldi_mul(&y
, Y
, &t
);
140 fgoldi_store(q
, &y
); fgoldi_store(b
, &x
); q
[56] = (b
[0]&1u) << 7;
143 static int ptdecode(fgoldi
*X
, fgoldi
*Y
, fgoldi
*Z
, const octet q
[57])
151 /* Load the y-coordinate. */
154 /* Check that the coordinate was in range. If we store it, we'll get a
155 * canonical version which we can compare against Q. Also, check that the
156 * extra bits in the top byte are zero.
159 for (i
= a
= 0; i
< 56; i
++) a
|= b
[i
] ^ q
[i
];
161 a
= ((a
- 1) >> 8)&0x01u
; /* 0 |-> 1, non-0 |-> 0 */
164 /* Decompress the x-coordinate. */
165 fgoldi_sqr(&t
, Y
); fgoldi_mulconst(&u
, &t
, D
); t
.P
[0] -= 1; u
.P
[0] -= 1;
166 rc
|= fgoldi_quosqrt(X
, &t
, &u
);
167 fgoldi_store(b
, X
); m
= -(uint32
)(((q
[56] >> 7) ^ b
[0])&0x1u
);
168 fgoldi_condneg(X
, X
, m
);
173 /* And we're done. */
177 /*----- Edwards curve arithmetic ------------------------------------------*/
179 static void ptadd(fgoldi
*X
, fgoldi
*Y
, fgoldi
*Z
,
180 const fgoldi
*X0
, const fgoldi
*Y0
, const fgoldi
*Z0
,
181 const fgoldi
*X1
, const fgoldi
*Y1
, const fgoldi
*Z1
)
183 fgoldi t0
, t1
, t2
, t3
;
185 /* Bernstein and Lange, `Faster addition and doubling on elliptic curves',
186 * 2007-09-06, https://cr.yp.to/newelliptic/newelliptic-20070906.pdf shows
189 * A = Z1 Z2; B = A^2; C = X1 X2; D = Y1 Y2;
190 * E = d C D; F = B - E; G = B + E;
191 * X3 = A F ((X1 + Y1) (X2 + Y2) - C - D);
192 * Y3 = A G (D - C); Z3 = c F G.
197 fgoldi_mul(&t0
, Z0
, Z1
); /* t0 = A = Z0 Z1 */
198 fgoldi_add(&t1
, X0
, Y0
); /* t1 = X0 + Y0 */
199 fgoldi_add(&t2
, X1
, Y1
); /* t2 = X1 + Y1 */
200 fgoldi_mul(&t1
, &t1
, &t2
); /* t1 = (X0 + Y0) (X1 + Y1) */
201 fgoldi_mul(&t2
, X0
, X1
); /* t2 = C = X0 X1 */
202 fgoldi_mul(&t3
, Y0
, Y1
); /* t3 = D = Y0 Y1 */
203 fgoldi_sub(X
, &t1
, &t2
); /* X = (X0 + Y0) (X1 + Y1) - C */
204 fgoldi_sub(X
, X
, &t3
); /* X = (X0 + Y0) (X1 + Y1) - C - D */
205 fgoldi_sub(Y
, &t3
, &t2
); /* Y = D - C */
206 fgoldi_mul(X
, X
, &t0
); /* X = A ((X0 + Y0) (X1 + Y1) - C - D) */
207 fgoldi_mul(Y
, Y
, &t0
); /* Y = A (D - C) */
208 fgoldi_sqr(&t0
, &t0
); /* t0 = B = A^2 */
209 fgoldi_mul(&t1
, &t2
, &t3
); /* t1 = C D */
210 fgoldi_mulconst(&t1
, &t1
, D
); /* t1 = E = d C D */
211 fgoldi_sub(&t2
, &t0
, &t1
); /* t2 = F = B - E */
212 fgoldi_add(&t1
, &t0
, &t1
); /* t1 = G = B + E */
213 fgoldi_mul(X
, X
, &t2
); /* X = A F ((X0 + Y0) (X1 + Y1) - C - D) */
214 fgoldi_mul(Y
, Y
, &t1
); /* Y = A G (D - C) */
215 fgoldi_mul(Z
, &t1
, &t2
); /* Z = c F G */
218 static void ptdbl(fgoldi
*X
, fgoldi
*Y
, fgoldi
*Z
,
219 const fgoldi
*X0
, const fgoldi
*Y0
, const fgoldi
*Z0
)
223 /* Bernstein and Lange, `Faster addition and doubling on elliptic curves',
224 * 2007-09-06, https://cr.yp.to/newelliptic/newelliptic-20070906.pdf shows
227 * B = (X1 + Y1)^2; C = X1^2; D = Y1^2;
228 * E = C + D; H = (c Z1)^2; J = E - 2 H;
229 * X3 = c (B - E) J; Y3 = c E (C - D); Z3 = E J
234 fgoldi_add(&t0
, X0
, Y0
); /* t0 = X0 + Y0 */
235 fgoldi_sqr(&t0
, &t0
); /* t0 = B = (X0 + Y0)^2 */
236 fgoldi_sqr(&t1
, X0
); /* t1 = C = X0^2 */
237 fgoldi_sqr(&t2
, Y0
); /* t2 = D = Y0^2 */
238 fgoldi_add(Y
, &t1
, &t2
); /* Y = E = C + D */
239 fgoldi_sub(&t1
, &t1
, &t2
); /* t1 = C - D */
240 fgoldi_sub(X
, &t0
, Y
); /* X = c (B - E) */
241 fgoldi_sqr(&t0
, Z0
); /* t0 = H = (c Z0)^2 */
242 fgoldi_add(&t0
, &t0
, &t0
); /* t0 = 2 H */
243 fgoldi_sub(&t0
, Y
, &t0
); /* t0 = J = E - 2 H */
244 fgoldi_mul(X
, X
, &t0
); /* X = c (B - E) J */
245 fgoldi_mul(Z
, Y
, &t0
); /* Z = E J */
246 fgoldi_mul(Y
, Y
, &t1
); /* Y = c E (C - D) */
249 static DEFINE_SCMUL(ptmul
, fgoldi
, 4, PIECEWD
, NPIECE
, ptadd
, ptdbl
)
250 static DEFINE_SCSIMMUL(ptsimmul
, fgoldi
, 2, PIECEWD
, NPIECE
, ptadd
, ptdbl
)
252 /*----- Key derivation utilities ------------------------------------------*/
254 static void unpack_key(scaf_piece a
[NPIECE
], octet h1
[57],
255 const octet
*k
, size_t ksz
)
260 shake256_init(&h
); shake_hash(&h
, k
, ksz
);
261 shake_xof(&h
); shake_get(&h
, b
, sizeof(b
));
262 b
[0] &= 0xfcu
; b
[55] |= 0x80u
; scaf_load(a
, b
, 56, NPIECE
, PIECEWD
);
263 if (h1
) shake_get(&h
, h1
, 57);
266 #define PREFIX_BUFSZ 266
267 static size_t prefix(octet b
[PREFIX_BUFSZ
],
268 int phflag
, const octet
*p
, size_t psz
)
270 memcpy(b
, "SigEd448", 8);
272 assert(psz
<= ED448_MAXPERSOSZ
); b
[9] = psz
; memcpy(b
+ 10, p
, psz
);
276 /*----- Main code ---------------------------------------------------------*/
278 /* --- @ed448_pubkey@ --- *
280 * Arguments: @octet K[ED448_PUBSZ]@ = where to put the public key
281 * @const void *k@ = private key
282 * @size_t ksz@ = length of private key
286 * Use: Derives the public key from a private key.
289 void ed448_pubkey(octet K
[ED448_PUBSZ
], const void *k
, size_t ksz
)
291 scaf_piece a
[NPIECE
];
294 unpack_key(a
, 0, k
, ksz
);
295 ptmul(&AX
, &AY
, &AZ
, a
, BX
, BY
, BZ
);
296 ptencode(K
, &AX
, &AY
, &AZ
);
299 /* --- @ed448_sign@ --- *
301 * Arguments: @octet sig[ED448_SIGSZ]@ = where to put the signature
302 * @const void *k@ = private key
303 * @size_t ksz@ = length of private key
304 * @const octet K[ED448_PUBSZ]@ = public key
305 * @int phflag@ = whether the `message' has been hashed already
306 * @const void *p@ = personalization string
307 * @size_t psz@ = length of personalization string
308 * @const void *m@ = message to sign
309 * @size_t msz@ = length of message
313 * Use: Signs a message.
316 void ed448_sign(octet sig
[ED448_SIGSZ
],
317 const void *k
, size_t ksz
, const octet K
[ED448_PUBSZ
],
318 int phflag
, const void *p
, size_t psz
,
319 const void *m
, size_t msz
)
322 scaf_piece a
[NPIECE
], r
[NPIECE
], t
[NPIECE
], scratch
[3*NPIECE
];
323 scaf_dblpiece tt
[2*NPIECE
];
325 octet h1
[57], pb
[PREFIX_BUFSZ
], rb
[114];
328 /* Get my private key. */
329 unpack_key(a
, h1
, k
, ksz
);
331 /* Determine the prefix string. */
332 psz
= prefix(pb
, phflag
, p
, psz
);
334 /* Select the nonce and the vector part. */
336 shake_hash(&h
, pb
, psz
);
337 shake_hash(&h
, h1
, sizeof(h1
));
338 shake_hash(&h
, m
, msz
);
339 shake_done(&h
, rb
, 114);
340 scaf_loaddbl(tt
, rb
, 114, 2*NPIECE
, PIECEWD
);
341 scaf_reduce(r
, tt
, l
, mu
, NPIECE
, PIECEWD
, scratch
);
342 ptmul(&RX
, &RY
, &RZ
, r
, BX
, BY
, BZ
);
343 ptencode(sig
, &RX
, &RY
, &RZ
);
345 /* Calculate the scalar part. */
347 shake_hash(&h
, pb
, psz
);
348 shake_hash(&h
, sig
, 57);
349 shake_hash(&h
, K
, 57);
350 shake_hash(&h
, m
, msz
);
351 shake_done(&h
, rb
, 114);
352 scaf_loaddbl(tt
, rb
, 114, 2*NPIECE
, PIECEWD
);
353 scaf_reduce(t
, tt
, l
, mu
, NPIECE
, PIECEWD
, scratch
);
354 scaf_mul(tt
, t
, a
, NPIECE
);
355 for (i
= 0; i
< NPIECE
; i
++) tt
[i
] += r
[i
];
356 scaf_reduce(t
, tt
, l
, mu
, NPIECE
, PIECEWD
, scratch
);
357 scaf_store(sig
+ 57, 57, t
, NPIECE
, PIECEWD
);
360 /* --- @ed448_verify@ --- *
362 * Arguments: @const octet K[ED448_PUBSZ]@ = public key
363 * @const void *m@ = message to sign
364 * @int phflag@ = whether the `message' has been hashed already
365 * @const void *p@ = personalization string
366 * @size_t psz@ = length of personalization string
367 * @size_t msz@ = length of message
368 * @const octet sig[ED448_SIGSZ]@ = signature
370 * Returns: Zero if OK, negative on failure.
372 * Use: Verify a signature.
375 int ed448_verify(const octet K
[ED448_PUBSZ
],
376 int phflag
, const void *p
, size_t psz
,
377 const void *m
, size_t msz
,
378 const octet sig
[ED448_SIGSZ
])
381 scaf_piece s
[NPIECE
], t
[NPIECE
], scratch
[3*NPIECE
];
382 scaf_dblpiece tt
[2*NPIECE
];
383 fgoldi AX
, AY
, AZ
, RX
, RY
, RZ
;
384 octet b
[PREFIX_BUFSZ
];
386 /* Unpack the public key. Negate it: we're meant to subtract the term
387 * involving the public key point, and this is easier than negating the
390 if (ptdecode(&AX
, &AY
, &AZ
, K
)) return (-1);
391 fgoldi_neg(&AX
, &AX
);
393 /* Load the scalar and check that it's in range. The easy way is to store
394 * it again and see if the two match.
396 scaf_loaddbl(tt
, sig
+ 57, 57, 2*NPIECE
, PIECEWD
);
397 scaf_reduce(s
, tt
, l
, mu
, NPIECE
, PIECEWD
, scratch
);
398 scaf_store(b
, 57, s
, NPIECE
, PIECEWD
);
399 if (MEMCMP(b
, !=, sig
+ 57, 57)) return (-1);
401 /* Check the signature. */
402 psz
= prefix(b
, phflag
, p
, psz
);
404 shake_hash(&h
, b
, psz
);
405 shake_hash(&h
, sig
, 57);
406 shake_hash(&h
, K
, ED448_PUBSZ
);
407 shake_hash(&h
, m
, msz
);
408 shake_done(&h
, b
, 114);
409 scaf_loaddbl(tt
, b
, 114, 2*NPIECE
, PIECEWD
);
410 scaf_reduce(t
, tt
, l
, mu
, NPIECE
, PIECEWD
, scratch
);
411 ptsimmul(&RX
, &RY
, &RZ
, s
, BX
, BY
, BZ
, t
, &AX
, &AY
, &AZ
);
412 ptencode(b
, &RX
, &RY
, &RZ
);
413 if (MEMCMP(b
, !=, sig
, 57)) return (-1);
419 /*----- Test rig ----------------------------------------------------------*/
426 #include <mLib/report.h>
427 #include <mLib/testrig.h>
431 static int vrf_pubkey(dstr dv
[])
433 dstr dpub
= DSTR_INIT
;
436 if (dv
[1].len
!= ED448_PUBSZ
) die(1, "bad pub length");
438 ct_poison(dv
[0].buf
, dv
[0].len
);
439 dstr_ensure(&dpub
, ED448_PUBSZ
); dpub
.len
= ED448_PUBSZ
;
440 ed448_pubkey((octet
*)dpub
.buf
, dv
[0].buf
, dv
[0].len
);
441 ct_remedy(dpub
.buf
, dpub
.len
);
442 if (MEMCMP(dpub
.buf
, !=, dv
[1].buf
, ED448_PUBSZ
)) {
444 fprintf(stderr
, "failed!");
445 fprintf(stderr
, "\n\tpriv = "); type_hex
.dump(&dv
[0], stderr
);
446 fprintf(stderr
, "\n\tcalc = "); type_hex
.dump(&dpub
, stderr
);
447 fprintf(stderr
, "\n\twant = "); type_hex
.dump(&dv
[1], stderr
);
448 fprintf(stderr
, "\n");
455 static int vrf_sign(dstr
*priv
, int phflag
, dstr
*perso
,
456 dstr
*msg
, dstr
*want
)
459 octet K
[ED448_PUBSZ
];
460 dstr d
= DSTR_INIT
, dsig
= DSTR_INIT
, *m
;
463 if (want
->len
!= ED448_SIGSZ
) die(1, "bad result length");
465 ct_poison(priv
->buf
, priv
->len
);
466 dstr_ensure(&dsig
, ED448_SIGSZ
); dsig
.len
= ED448_SIGSZ
;
470 dstr_ensure(&d
, 64); d
.len
= 64;
472 shake_hash(&h
, msg
->buf
, msg
->len
);
473 shake_done(&h
, d
.buf
, d
.len
);
476 ed448_pubkey(K
, priv
->buf
, priv
->len
);
477 ed448_sign((octet
*)dsig
.buf
, priv
->buf
, priv
->len
, K
,
478 phflag
, perso ? perso
->buf
: 0, perso ? perso
->len
: 0,
480 ct_remedy(dsig
.buf
, dsig
.len
);
481 if (MEMCMP(dsig
.buf
, !=, want
->buf
, ED448_SIGSZ
)) {
483 fprintf(stderr
, "failed!");
484 fprintf(stderr
, "\n\tpriv = "); type_hex
.dump(priv
, stderr
);
486 fprintf(stderr
, "\n\t ph = %d", phflag
);
487 fprintf(stderr
, "\n\tpers = "); type_hex
.dump(perso
, stderr
);
489 fprintf(stderr
, "\n\t msg = "); type_hex
.dump(msg
, stderr
);
491 { fprintf(stderr
, "\n\thash = "); type_hex
.dump(m
, stderr
); }
492 fprintf(stderr
, "\n\tcalc = "); type_hex
.dump(&dsig
, stderr
);
493 fprintf(stderr
, "\n\twant = "); type_hex
.dump(want
, stderr
);
494 fprintf(stderr
, "\n");
501 static int vrf_sign_ctx(dstr
*dv
)
502 { return (vrf_sign(&dv
[0], *(int *)dv
[1].buf
, &dv
[2], &dv
[3], &dv
[4])); }
504 static int vrf_verify(dstr
*pub
, int phflag
, dstr
*perso
,
505 dstr
*msg
, dstr
*sig
, int rc_want
)
509 dstr d
= DSTR_INIT
, *m
;
512 if (pub
->len
!= ED448_PUBSZ
) die(1, "bad pub length");
513 if (sig
->len
!= ED448_SIGSZ
) die(1, "bad sig length");
518 dstr_ensure(&d
, 64); d
.len
= 64;
520 shake_hash(&h
, msg
->buf
, msg
->len
);
521 shake_done(&h
, d
.buf
, d
.len
);
524 rc_calc
= ed448_verify((const octet
*)pub
->buf
,
525 phflag
, perso ? perso
->buf
: 0,
526 perso ? perso
->len
: 0,
528 (const octet
*)sig
->buf
);
529 if (!rc_want
!= !rc_calc
) {
531 fprintf(stderr
, "failed!");
532 fprintf(stderr
, "\n\t pub = "); type_hex
.dump(pub
, stderr
);
534 fprintf(stderr
, "\n\t ph = %d", phflag
);
535 fprintf(stderr
, "\n\tpers = "); type_hex
.dump(perso
, stderr
);
537 fprintf(stderr
, "\n\t msg = "); type_hex
.dump(msg
, stderr
);
539 { fprintf(stderr
, "\n\thash = "); type_hex
.dump(m
, stderr
); }
540 fprintf(stderr
, "\n\t sig = "); type_hex
.dump(sig
, stderr
);
541 fprintf(stderr
, "\n\tcalc = %d", rc_calc
);
542 fprintf(stderr
, "\n\twant = %d", rc_want
);
543 fprintf(stderr
, "\n");
549 static int vrf_verify_ctx(dstr
*dv
)
551 return (vrf_verify(&dv
[0], *(int *)dv
[1].buf
, &dv
[2],
552 &dv
[3], &dv
[4], *(int *)dv
[5].buf
));
555 static test_chunk tests
[] = {
556 { "pubkey", vrf_pubkey
, { &type_hex
, &type_hex
} },
557 { "sign", vrf_sign_ctx
,
558 { &type_hex
, &type_int
, &type_hex
, &type_hex
, &type_hex
} },
559 { "verify", vrf_verify_ctx
,
560 { &type_hex
, &type_int
, &type_hex
, &type_hex
, &type_hex
, &type_int
} },
564 int main(int argc
, char *argv
[])
566 test_run(argc
, argv
, tests
, SRCDIR
"/t/ed448");
572 /*----- That's all, folks -------------------------------------------------*/