3 * The Ed448 signature scheme
5 * (c) 2017 Straylight/Edgeware
8 /*----- Licensing notice --------------------------------------------------*
10 * This file is part of secnet.
11 * See README for full list of copyright holders.
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.
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.
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.
27 * This file was originally part of Catacomb, but has been automatically
28 * modified for incorporation into secnet: see `import-catacomb-crypto'
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.
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.
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,
47 /*----- Header files ------------------------------------------------------*/
57 /*----- 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
73 #define NPIECE SCAF_NPIECE(448, PIECEWD)
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
82 36764180, 8885695, 130592152, 20104429,
83 -104530499, 30304196, 121295871, 5901357,
84 125344798, -96893944, -93097107, -59366209,
85 3626698, 38307682, 24032956, 110359655
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)
94 /*----- Point encoding and decoding ---------------------------------------*/
96 static void ptencode(octet q
[57],
97 const fgoldi
*X
, const fgoldi
*Y
, const fgoldi
*Z
)
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;
106 static int ptdecode(fgoldi
*X
, fgoldi
*Y
, fgoldi
*Z
, const octet q
[57])
114 /* Load the y-coordinate. */
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.
122 for (i
= a
= 0; i
< 56; i
++) a
|= b
[i
] ^ q
[i
];
124 a
= ((a
- 1) >> 8)&0x01u
; /* 0 |-> 1, non-0 |-> 0 */
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
);
136 /* And we're done. */
140 /*----- Edwards curve arithmetic ------------------------------------------*/
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
)
146 fgoldi t0
, t1
, t2
, t3
;
148 /* Bernstein and Lange, `Faster addition and doubling on elliptic curves',
149 * 2007-09-06, https://cr.yp.to/newelliptic/newelliptic-20070906.pdf shows
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.
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 */
181 static void ptdbl(fgoldi
*X
, fgoldi
*Y
, fgoldi
*Z
,
182 const fgoldi
*X0
, const fgoldi
*Y0
, const fgoldi
*Z0
)
186 /* Bernstein and Lange, `Faster addition and doubling on elliptic curves',
187 * 2007-09-06, https://cr.yp.to/newelliptic/newelliptic-20070906.pdf shows
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
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) */
212 static DEFINE_SCMUL(ptmul
, fgoldi
, 4, PIECEWD
, NPIECE
, ptadd
, ptdbl
)
213 static DEFINE_SCSIMMUL(ptsimmul
, fgoldi
, 2, PIECEWD
, NPIECE
, ptadd
, ptdbl
)
215 /*----- Key derivation utilities ------------------------------------------*/
217 static void unpack_key(scaf_piece a
[NPIECE
], octet h1
[57],
218 const octet
*k
, size_t ksz
)
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);
229 #define PREFIX_BUFSZ 266
230 static size_t prefix(octet b
[PREFIX_BUFSZ
],
231 int phflag
, const octet
*p
, size_t psz
)
233 memcpy(b
, "SigEd448", 8);
235 assert(psz
<= ED448_MAXPERSOSZ
); b
[9] = psz
; memcpy(b
+ 10, p
, psz
);
239 /*----- Main code ---------------------------------------------------------*/
241 /* --- @ed448_pubkey@ --- *
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
249 * Use: Derives the public key from a private key.
252 void ed448_pubkey(octet K
[ED448_PUBSZ
], const void *k
, size_t ksz
)
254 scaf_piece a
[NPIECE
];
257 unpack_key(a
, 0, k
, ksz
);
258 ptmul(&AX
, &AY
, &AZ
, a
, BX
, BY
, BZ
);
259 ptencode(K
, &AX
, &AY
, &AZ
);
262 /* --- @ed448_sign@ --- *
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
276 * Use: Signs a message.
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
)
285 scaf_piece a
[NPIECE
], r
[NPIECE
], t
[NPIECE
], scratch
[3*NPIECE
];
286 scaf_dblpiece tt
[2*NPIECE
];
288 octet h1
[57], pb
[PREFIX_BUFSZ
], rb
[114];
291 /* Get my private key. */
292 unpack_key(a
, h1
, k
, ksz
);
294 /* Determine the prefix string. */
295 psz
= prefix(pb
, phflag
, p
, psz
);
297 /* Select the nonce and the vector part. */
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
);
308 /* Calculate the scalar part. */
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
);
323 /* --- @ed448_verify@ --- *
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
333 * Returns: Zero if OK, negative on failure.
335 * Use: Verify a signature.
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
])
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
];
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
353 if (ptdecode(&AX
, &AY
, &AZ
, K
)) return (-1);
354 fgoldi_neg(&AX
, &AX
);
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.
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);
364 /* Check the signature. */
365 psz
= prefix(b
, phflag
, p
, psz
);
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);
382 /*----- That's all, folks -------------------------------------------------*/