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 ------------------------------------------------------*/
38 /*----- Key fetching ------------------------------------------------------*/
40 const key_fetchdef ed448_pubfetch
[] = {
41 { "pub", offsetof(ed448_pub
, pub
), KENC_BINARY
, 0 },
45 static const key_fetchdef priv
[] = {
46 { "priv", offsetof(ed448_priv
, priv
), KENC_BINARY
, 0 },
50 const key_fetchdef ed448_privfetch
[] = {
51 { "pub", offsetof(ed448_priv
, pub
), KENC_BINARY
, 0 },
52 { "private", 0, KENC_STRUCT
, priv
},
56 /*----- A number of magic numbers -----------------------------------------*/
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
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
76 static const scaf_piece l
[] = {
77 0x4f3, 0x584, 0x2ab, 0xc29, 0x378, 0x552, 0x58f, 0x8dc,
78 0x272, 0x6cc, 0x021, 0x369, 0xed6, 0x49a, 0xedb, 0xc44,
79 0x3e9, 0xca2, 0xf7c, 0xfff, 0xfff, 0xfff, 0xfff, 0xfff,
80 0xfff, 0xfff, 0xfff, 0xfff, 0xfff, 0xfff, 0xfff, 0xfff,
81 0xfff, 0xfff, 0xfff, 0xfff, 0xfff, 0x003
83 static const scaf_piece mu
[] = {
84 0x00a, 0xe0d, 0xbb0, 0x4a7, 0x6d5, 0x73d, 0xdc8, 0x0aa,
85 0x3a7, 0xd72, 0x3d8, 0xe93, 0x6fd, 0x9c9, 0x512, 0x4b6,
86 0xb12, 0x63b, 0xdc1, 0x335, 0x008, 0x000, 0x000, 0x000,
87 0x000, 0x000, 0x000, 0x000, 0x000, 0x000, 0x000, 0x000,
88 0x000, 0x000, 0x000, 0x000, 0x000, 0x000, 0x400
92 #define NPIECE SCAF_NPIECE(448, PIECEWD)
96 static const fgoldi_piece bx_pieces
[] = {
97 118276190, 40534716, 9670182, -133293904,
98 85017404, -9262234, 68333083, -96650682,
99 -93461723, 15824511, 73756743, 57518561,
100 94773951, -19783215, 107736334, 82941708
102 36764180, 8885695, 130592152, 20104429,
103 -104530499, 30304196, 121295871, 5901357,
104 125344798, -96893944, -93097107, -59366209,
105 3626698, 38307682, 24032956, 110359655
108 #if FGOLDI_IMPL == 12
110 static const fgoldi_piece bx_pieces
[] = {
111 94, 204, -114, 523, 309, -474, 313, -511, 99, -1017,
112 828, 276, -822, 686, -71, -485, 299, 200, -791, -737,
113 805, -290, -43, -550, 121, 71, -425, -983, -344, 439,
114 703, 610, 555, 135, -151, -754, -321, 397, -420, 633
116 -1516, 784, -28, -425, 68, -616, -885, -592, 788, 153,
117 -579, -944, 116, 415, 231, 1023, 941, -594, 49, 45,
118 -994, -118, 271, -496, -739, 877, -201, -43, 147, -453,
119 1738, 885, -960, 542, 292, 1724, -277, -797, -46, 842
123 static const fgoldi_piece bz_pieces
[NPIECE
] = { 1, 0, /* ... */ };
124 #define BX ((const fgoldi *)bx_pieces)
125 #define BY ((const fgoldi *)by_pieces)
126 #define BZ ((const fgoldi *)bz_pieces)
129 /*----- Point encoding and decoding ---------------------------------------*/
131 static void ptencode(octet q
[57],
132 const fgoldi
*X
, const fgoldi
*Y
, const fgoldi
*Z
)
137 fgoldi_inv(&t
, Z
); fgoldi_mul(&x
, X
, &t
); fgoldi_mul(&y
, Y
, &t
);
138 fgoldi_store(q
, &y
); fgoldi_store(b
, &x
); q
[56] = (b
[0]&1u) << 7;
141 static int ptdecode(fgoldi
*X
, fgoldi
*Y
, fgoldi
*Z
, const octet q
[57])
149 /* Load the y-coordinate. */
152 /* Check that the coordinate was in range. If we store it, we'll get a
153 * canonical version which we can compare against Q. Also, check that the
154 * extra bits in the top byte are zero.
157 for (i
= a
= 0; i
< 56; i
++) a
|= b
[i
] ^ q
[i
];
159 a
= ((a
- 1) >> 8)&0x01u
; /* 0 |-> 1, non-0 |-> 0 */
162 /* Decompress the x-coordinate. */
163 fgoldi_sqr(&t
, Y
); fgoldi_mulconst(&u
, &t
, D
); t
.P
[0] -= 1; u
.P
[0] -= 1;
164 rc
|= fgoldi_quosqrt(X
, &t
, &u
);
165 fgoldi_store(b
, X
); m
= -(uint32
)(((q
[56] >> 7) ^ b
[0])&0x1u
);
166 fgoldi_condneg(X
, X
, m
);
171 /* And we're done. */
175 /*----- Edwards curve arithmetic ------------------------------------------*/
177 static void ptadd(fgoldi
*X
, fgoldi
*Y
, fgoldi
*Z
,
178 const fgoldi
*X0
, const fgoldi
*Y0
, const fgoldi
*Z0
,
179 const fgoldi
*X1
, const fgoldi
*Y1
, const fgoldi
*Z1
)
181 fgoldi t0
, t1
, t2
, t3
;
183 /* Bernstein and Lange, `Faster addition and doubling on elliptic curves',
184 * 2007-09-06, https://cr.yp.to/newelliptic/newelliptic-20070906.pdf shows
187 * A = Z1 Z2; B = A^2; C = X1 X2; D = Y1 Y2;
188 * E = d C D; F = B - E; G = B + E;
189 * X3 = A F ((X1 + Y1) (X2 + Y2) - C - D);
190 * Y3 = A G (D - C); Z3 = c F G.
195 fgoldi_mul(&t0
, Z0
, Z1
); /* t0 = A = Z0 Z1 */
196 fgoldi_add(&t1
, X0
, Y0
); /* t1 = X0 + Y0 */
197 fgoldi_add(&t2
, X1
, Y1
); /* t2 = X1 + Y1 */
198 fgoldi_mul(&t1
, &t1
, &t2
); /* t1 = (X0 + Y0) (X1 + Y1) */
199 fgoldi_mul(&t2
, X0
, X1
); /* t2 = C = X0 X1 */
200 fgoldi_mul(&t3
, Y0
, Y1
); /* t3 = D = Y0 Y1 */
201 fgoldi_sub(X
, &t1
, &t2
); /* X = (X0 + Y0) (X1 + Y1) - C */
202 fgoldi_sub(X
, X
, &t3
); /* X = (X0 + Y0) (X1 + Y1) - C - D */
203 fgoldi_sub(Y
, &t3
, &t2
); /* Y = D - C */
204 fgoldi_mul(X
, X
, &t0
); /* X = A ((X0 + Y0) (X1 + Y1) - C - D) */
205 fgoldi_mul(Y
, Y
, &t0
); /* Y = A (D - C) */
206 fgoldi_sqr(&t0
, &t0
); /* t0 = B = A^2 */
207 fgoldi_mul(&t1
, &t2
, &t3
); /* t1 = C D */
208 fgoldi_mulconst(&t1
, &t1
, D
); /* t1 = E = d C D */
209 fgoldi_sub(&t2
, &t0
, &t1
); /* t2 = F = B - E */
210 fgoldi_add(&t1
, &t0
, &t1
); /* t1 = G = B + E */
211 fgoldi_mul(X
, X
, &t2
); /* X = A F ((X0 + Y0) (X1 + Y1) - C - D) */
212 fgoldi_mul(Y
, Y
, &t1
); /* Y = A G (D - C) */
213 fgoldi_mul(Z
, &t1
, &t2
); /* Z = c F G */
216 static void ptdbl(fgoldi
*X
, fgoldi
*Y
, fgoldi
*Z
,
217 const fgoldi
*X0
, const fgoldi
*Y0
, const fgoldi
*Z0
)
221 /* Bernstein and Lange, `Faster addition and doubling on elliptic curves',
222 * 2007-09-06, https://cr.yp.to/newelliptic/newelliptic-20070906.pdf shows
225 * B = (X1 + Y1)^2; C = X1^2; D = Y1^2;
226 * E = C + D; H = (c Z1)^2; J = E - 2 H;
227 * X3 = c (B - E) J; Y3 = c E (C - D); Z3 = E J
232 fgoldi_add(&t0
, X0
, Y0
); /* t0 = X0 + Y0 */
233 fgoldi_sqr(&t0
, &t0
); /* t0 = B = (X0 + Y0)^2 */
234 fgoldi_sqr(&t1
, X0
); /* t1 = C = X0^2 */
235 fgoldi_sqr(&t2
, Y0
); /* t2 = D = Y0^2 */
236 fgoldi_add(Y
, &t1
, &t2
); /* Y = E = C + D */
237 fgoldi_sub(&t1
, &t1
, &t2
); /* t1 = C - D */
238 fgoldi_sub(X
, &t0
, Y
); /* X = c (B - E) */
239 fgoldi_sqr(&t0
, Z0
); /* t0 = H = (c Z0)^2 */
240 fgoldi_add(&t0
, &t0
, &t0
); /* t0 = 2 H */
241 fgoldi_sub(&t0
, Y
, &t0
); /* t0 = J = E - 2 H */
242 fgoldi_mul(X
, X
, &t0
); /* X = c (B - E) J */
243 fgoldi_mul(Z
, Y
, &t0
); /* Z = E J */
244 fgoldi_mul(Y
, Y
, &t1
); /* Y = c E (C - D) */
247 static DEFINE_SCMUL(ptmul
, fgoldi
, 4, PIECEWD
, NPIECE
, ptadd
, ptdbl
)
248 static DEFINE_SCSIMMUL(ptsimmul
, fgoldi
, 2, PIECEWD
, NPIECE
, ptadd
, ptdbl
)
250 /*----- Key derivation utilities ------------------------------------------*/
252 static void unpack_key(scaf_piece a
[NPIECE
], octet h1
[57],
253 const octet
*k
, size_t ksz
)
258 shake256_init(&h
); shake_hash(&h
, k
, ksz
);
259 shake_xof(&h
); shake_get(&h
, b
, sizeof(b
));
260 b
[0] &= 0xfcu
; b
[55] |= 0x80u
; scaf_load(a
, b
, 56, NPIECE
, PIECEWD
);
261 if (h1
) shake_get(&h
, h1
, 57);
264 #define PREFIX_BUFSZ 266
265 static size_t prefix(octet b
[PREFIX_BUFSZ
],
266 int phflag
, const octet
*p
, size_t psz
)
268 memcpy(b
, "SigEd448", 8);
270 assert(psz
<= ED448_MAXPERSOSZ
); b
[9] = psz
; memcpy(b
+ 10, p
, psz
);
274 /*----- Main code ---------------------------------------------------------*/
276 /* --- @ed448_pubkey@ --- *
278 * Arguments: @octet K[ED448_PUBSZ]@ = where to put the public key
279 * @const void *k@ = private key
280 * @size_t ksz@ = length of private key
284 * Use: Derives the public key from a private key.
287 void ed448_pubkey(octet K
[ED448_PUBSZ
], const void *k
, size_t ksz
)
289 scaf_piece a
[NPIECE
];
292 unpack_key(a
, 0, k
, ksz
);
293 ptmul(&AX
, &AY
, &AZ
, a
, BX
, BY
, BZ
);
294 ptencode(K
, &AX
, &AY
, &AZ
);
297 /* --- @ed448_sign@ --- *
299 * Arguments: @octet sig[ED448_SIGSZ]@ = where to put the signature
300 * @const void *k@ = private key
301 * @size_t ksz@ = length of private key
302 * @const octet K[ED448_PUBSZ]@ = public key
303 * @int phflag@ = whether the `message' has been hashed already
304 * @const void *p@ = personalization string
305 * @size_t psz@ = length of personalization string
306 * @const void *m@ = message to sign
307 * @size_t msz@ = length of message
311 * Use: Signs a message.
314 void ed448_sign(octet sig
[ED448_SIGSZ
],
315 const void *k
, size_t ksz
, const octet K
[ED448_PUBSZ
],
316 int phflag
, const void *p
, size_t psz
,
317 const void *m
, size_t msz
)
320 scaf_piece a
[NPIECE
], r
[NPIECE
], t
[NPIECE
], scratch
[3*NPIECE
];
321 scaf_dblpiece tt
[2*NPIECE
];
323 octet h1
[57], pb
[PREFIX_BUFSZ
], rb
[114];
326 /* Get my private key. */
327 unpack_key(a
, h1
, k
, ksz
);
329 /* Determine the prefix string. */
330 psz
= prefix(pb
, phflag
, p
, psz
);
332 /* Select the nonce and the vector part. */
334 shake_hash(&h
, pb
, psz
);
335 shake_hash(&h
, h1
, sizeof(h1
));
336 shake_hash(&h
, m
, msz
);
337 shake_done(&h
, rb
, 114);
338 scaf_loaddbl(tt
, rb
, 114, 2*NPIECE
, PIECEWD
);
339 scaf_reduce(r
, tt
, l
, mu
, NPIECE
, PIECEWD
, scratch
);
340 ptmul(&RX
, &RY
, &RZ
, r
, BX
, BY
, BZ
);
341 ptencode(sig
, &RX
, &RY
, &RZ
);
343 /* Calculate the scalar part. */
345 shake_hash(&h
, pb
, psz
);
346 shake_hash(&h
, sig
, 57);
347 shake_hash(&h
, K
, 57);
348 shake_hash(&h
, m
, msz
);
349 shake_done(&h
, rb
, 114);
350 scaf_loaddbl(tt
, rb
, 114, 2*NPIECE
, PIECEWD
);
351 scaf_reduce(t
, tt
, l
, mu
, NPIECE
, PIECEWD
, scratch
);
352 scaf_mul(tt
, t
, a
, NPIECE
);
353 for (i
= 0; i
< NPIECE
; i
++) tt
[i
] += r
[i
];
354 scaf_reduce(t
, tt
, l
, mu
, NPIECE
, PIECEWD
, scratch
);
355 scaf_store(sig
+ 57, 57, t
, NPIECE
, PIECEWD
);
358 /* --- @ed448_verify@ --- *
360 * Arguments: @const octet K[ED448_PUBSZ]@ = public key
361 * @const void *m@ = message to sign
362 * @int phflag@ = whether the `message' has been hashed already
363 * @const void *p@ = personalization string
364 * @size_t psz@ = length of personalization string
365 * @size_t msz@ = length of message
366 * @const octet sig[ED448_SIGSZ]@ = signature
368 * Returns: Zero if OK, negative on failure.
370 * Use: Verify a signature.
373 int ed448_verify(const octet K
[ED448_PUBSZ
],
374 int phflag
, const void *p
, size_t psz
,
375 const void *m
, size_t msz
,
376 const octet sig
[ED448_SIGSZ
])
379 scaf_piece s
[NPIECE
], t
[NPIECE
], scratch
[3*NPIECE
];
380 scaf_dblpiece tt
[2*NPIECE
];
381 fgoldi AX
, AY
, AZ
, RX
, RY
, RZ
;
382 octet b
[PREFIX_BUFSZ
];
384 /* Unpack the public key. Negate it: we're meant to subtract the term
385 * involving the public key point, and this is easier than negating the
388 if (ptdecode(&AX
, &AY
, &AZ
, K
)) return (-1);
389 fgoldi_neg(&AX
, &AX
);
391 /* Load the scalar and check that it's in range. The easy way is to store
392 * it again and see if the two match.
394 scaf_loaddbl(tt
, sig
+ 57, 57, 2*NPIECE
, PIECEWD
);
395 scaf_reduce(s
, tt
, l
, mu
, NPIECE
, PIECEWD
, scratch
);
396 scaf_store(b
, 57, s
, NPIECE
, PIECEWD
);
397 if (memcmp(b
, sig
+ 57, 57) != 0) return (-1);
399 /* Check the signature. */
400 psz
= prefix(b
, phflag
, p
, psz
);
402 shake_hash(&h
, b
, psz
);
403 shake_hash(&h
, sig
, 57);
404 shake_hash(&h
, K
, ED448_PUBSZ
);
405 shake_hash(&h
, m
, msz
);
406 shake_done(&h
, b
, 114);
407 scaf_loaddbl(tt
, b
, 114, 2*NPIECE
, PIECEWD
);
408 scaf_reduce(t
, tt
, l
, mu
, NPIECE
, PIECEWD
, scratch
);
409 ptsimmul(&RX
, &RY
, &RZ
, s
, BX
, BY
, BZ
, t
, &AX
, &AY
, &AZ
);
410 ptencode(b
, &RX
, &RY
, &RZ
);
411 if (memcmp(b
, sig
, 57) != 0) return (-1);
417 /*----- Test rig ----------------------------------------------------------*/
424 #include <mLib/report.h>
425 #include <mLib/testrig.h>
429 static int vrf_pubkey(dstr dv
[])
431 dstr dpub
= DSTR_INIT
;
434 if (dv
[1].len
!= ED448_PUBSZ
) die(1, "bad pub length");
436 ct_poison(dv
[0].buf
, dv
[0].len
);
437 dstr_ensure(&dpub
, ED448_PUBSZ
); dpub
.len
= ED448_PUBSZ
;
438 ed448_pubkey((octet
*)dpub
.buf
, dv
[0].buf
, dv
[0].len
);
439 ct_remedy(dpub
.buf
, dpub
.len
);
440 if (memcmp(dpub
.buf
, dv
[1].buf
, ED448_PUBSZ
) != 0) {
442 fprintf(stderr
, "failed!");
443 fprintf(stderr
, "\n\tpriv = "); type_hex
.dump(&dv
[0], stderr
);
444 fprintf(stderr
, "\n\tcalc = "); type_hex
.dump(&dpub
, stderr
);
445 fprintf(stderr
, "\n\twant = "); type_hex
.dump(&dv
[1], stderr
);
446 fprintf(stderr
, "\n");
453 static int vrf_sign(dstr
*priv
, int phflag
, dstr
*perso
,
454 dstr
*msg
, dstr
*want
)
457 octet K
[ED448_PUBSZ
];
458 dstr d
= DSTR_INIT
, dsig
= DSTR_INIT
, *m
;
461 if (want
->len
!= ED448_SIGSZ
) die(1, "bad result length");
463 ct_poison(priv
->buf
, priv
->len
);
464 dstr_ensure(&dsig
, ED448_SIGSZ
); dsig
.len
= ED448_SIGSZ
;
468 dstr_ensure(&d
, 64); d
.len
= 64;
470 shake_hash(&h
, msg
->buf
, msg
->len
);
471 shake_done(&h
, d
.buf
, d
.len
);
474 ed448_pubkey(K
, priv
->buf
, priv
->len
);
475 ed448_sign((octet
*)dsig
.buf
, priv
->buf
, priv
->len
, K
,
476 phflag
, perso ? perso
->buf
: 0, perso ? perso
->len
: 0,
478 ct_remedy(dsig
.buf
, dsig
.len
);
479 if (memcmp(dsig
.buf
, want
->buf
, ED448_SIGSZ
) != 0) {
481 fprintf(stderr
, "failed!");
482 fprintf(stderr
, "\n\tpriv = "); type_hex
.dump(priv
, stderr
);
484 fprintf(stderr
, "\n\t ph = %d", phflag
);
485 fprintf(stderr
, "\n\tpers = "); type_hex
.dump(perso
, stderr
);
487 fprintf(stderr
, "\n\t msg = "); type_hex
.dump(msg
, stderr
);
489 { fprintf(stderr
, "\n\thash = "); type_hex
.dump(m
, stderr
); }
490 fprintf(stderr
, "\n\tcalc = "); type_hex
.dump(&dsig
, stderr
);
491 fprintf(stderr
, "\n\twant = "); type_hex
.dump(want
, stderr
);
492 fprintf(stderr
, "\n");
499 static int vrf_sign_ctx(dstr
*dv
)
500 { return (vrf_sign(&dv
[0], *(int *)dv
[1].buf
, &dv
[2], &dv
[3], &dv
[4])); }
502 static int vrf_verify(dstr
*pub
, int phflag
, dstr
*perso
,
503 dstr
*msg
, dstr
*sig
, int rc_want
)
507 dstr d
= DSTR_INIT
, *m
;
510 if (pub
->len
!= ED448_PUBSZ
) die(1, "bad pub length");
511 if (sig
->len
!= ED448_SIGSZ
) die(1, "bad sig length");
516 dstr_ensure(&d
, 64); d
.len
= 64;
518 shake_hash(&h
, msg
->buf
, msg
->len
);
519 shake_done(&h
, d
.buf
, d
.len
);
522 rc_calc
= ed448_verify((const octet
*)pub
->buf
,
523 phflag
, perso ? perso
->buf
: 0,
524 perso ? perso
->len
: 0,
526 (const octet
*)sig
->buf
);
527 if (!rc_want
!= !rc_calc
) {
529 fprintf(stderr
, "failed!");
530 fprintf(stderr
, "\n\t pub = "); type_hex
.dump(pub
, stderr
);
532 fprintf(stderr
, "\n\t ph = %d", phflag
);
533 fprintf(stderr
, "\n\tpers = "); type_hex
.dump(perso
, stderr
);
535 fprintf(stderr
, "\n\t msg = "); type_hex
.dump(msg
, stderr
);
537 { fprintf(stderr
, "\n\thash = "); type_hex
.dump(m
, stderr
); }
538 fprintf(stderr
, "\n\t sig = "); type_hex
.dump(sig
, stderr
);
539 fprintf(stderr
, "\n\tcalc = %d", rc_calc
);
540 fprintf(stderr
, "\n\twant = %d", rc_want
);
541 fprintf(stderr
, "\n");
547 static int vrf_verify_ctx(dstr
*dv
)
549 return (vrf_verify(&dv
[0], *(int *)dv
[1].buf
, &dv
[2],
550 &dv
[3], &dv
[4], *(int *)dv
[5].buf
));
553 static test_chunk tests
[] = {
554 { "pubkey", vrf_pubkey
, { &type_hex
, &type_hex
} },
555 { "sign", vrf_sign_ctx
,
556 { &type_hex
, &type_int
, &type_hex
, &type_hex
, &type_hex
} },
557 { "verify", vrf_verify_ctx
,
558 { &type_hex
, &type_int
, &type_hex
, &type_hex
, &type_hex
, &type_int
} },
562 int main(int argc
, char *argv
[])
564 test_run(argc
, argv
, tests
, SRCDIR
"/t/ed448");
570 /*----- That's all, folks -------------------------------------------------*/