3 * The Ed25519 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 0xf5d3ed, 0x631a5c, 0xd65812, 0xa2f79c, 0xdef9de, 0x000014,
62 0x000000, 0x000000, 0x000000, 0x000000, 0x001000
64 static const scaf_piece mu
[] = {
65 0x1b3994, 0x0a2c13, 0x9ce5a3, 0x29a7ed, 0x5d0863, 0x210621,
66 0xffffeb, 0xffffff, 0xffffff, 0xffffff, 0xffffff, 0x000fff
69 #define NPIECE SCAF_NPIECE(255, PIECEWD)
72 static const f25519_piece bx_pieces
[] = {
73 -14297830, -7645148, 16144683, -16471763, 27570974,
74 -2696100, -26142465, 8378389, 20764389, 8758491
76 -26843541, -6710886, 13421773, -13421773, 26843546,
77 6710886, -13421773, 13421773, -26843546, -6710886
79 -10913610, 13857413, -15372611, 6949391, 114729,
80 -8787816, -6275908, -3247719, -18696448, -12055116
83 static const f25519_piece bz_pieces
[NPIECE
] = { 1, 0, /* ... */ };
84 #define BX ((const f25519 *)bx_pieces)
85 #define BY ((const f25519 *)by_pieces)
86 #define BZ ((const f25519 *)bz_pieces)
87 #define D ((const f25519 *)d_pieces)
89 /*----- Point encoding and decoding ---------------------------------------*/
91 static void ptencode(octet q
[32],
92 const f25519
*X
, const f25519
*Y
, const f25519
*Z
)
97 f25519_inv(&t
, Z
); f25519_mul(&x
, X
, &t
); f25519_mul(&y
, Y
, &t
);
98 f25519_store(q
, &y
); f25519_store(b
, &x
); q
[31] |= (b
[0]&1u) << 7;
101 static int ptdecode(f25519
*X
, f25519
*Y
, f25519
*Z
, const octet q
[32])
109 /* Load the y-coordinate. */
110 memcpy(b
, q
, 32); b
[31] &= 0x7fu
; f25519_load(Y
, b
);
112 /* Check that the coordinate was in range. If we store it, we'll get a
113 * canonical version which we can compare against Q; be careful not to
117 for (i
= a
= 0; i
< 31; i
++) a
|= b
[i
] ^ q
[i
];
118 a
|= (b
[31] ^ q
[31])&0x7fu
;
119 a
= ((a
- 1) >> 8)&0x01u
; /* 0 |-> 1, non-0 |-> 0 */
122 /* Decompress the x-coordinate. */
123 f25519_sqr(&t
, Y
); f25519_mul(&u
, &t
, D
); t
.P
[0] -= 1; u
.P
[0] += 1;
124 rc
|= f25519_quosqrt(X
, &t
, &u
);
125 f25519_store(b
, X
); m
= -(uint32
)(((q
[31] >> 7) ^ b
[0])&0x1u
);
126 f25519_condneg(X
, X
, m
);
131 /* And we're done. */
135 /*----- Edwards curve arithmetic ------------------------------------------*/
137 static void ptadd(f25519
*X
, f25519
*Y
, f25519
*Z
,
138 const f25519
*X0
, const f25519
*Y0
, const f25519
*Z0
,
139 const f25519
*X1
, const f25519
*Y1
, const f25519
*Z1
)
141 f25519 t0
, t1
, t2
, t3
;
143 /* Bernstein, Birkner, Joye, Lange, and Peters, `Twisted Edwards Curves',
144 * 2008-03-13, https://cr.yp.to/newelliptic/twisted-20080313.pdf shows the
147 * A = Z1 Z2; B = A^2; C = X1 X2; D = Y1 Y2;
148 * E = d C D; F = B - E; G = B + E;
149 * X3 = A F ((X1 + Y1) (X2 + Y2) - C - D);
150 * Y3 = A G (D - a C); Z3 = F G.
152 * Note that a = -1, which things easier.
155 f25519_mul(&t0
, Z0
, Z1
); /* t0 = A = Z0 Z1 */
156 f25519_add(&t1
, X0
, Y0
); /* t1 = X0 + Y0 */
157 f25519_add(&t2
, X1
, Y1
); /* t2 = X1 + Y1 */
158 f25519_mul(&t1
, &t1
, &t2
); /* t1 = (X0 + Y0) (X1 + Y1) */
159 f25519_mul(&t2
, X0
, X1
); /* t2 = C = X0 X1 */
160 f25519_mul(&t3
, Y0
, Y1
); /* t3 = D = Y0 Y1 */
161 f25519_add(Y
, &t2
, &t3
); /* Y = C + D = D - a C */
162 f25519_sub(X
, &t1
, Y
); /* X = (X0 + Y0) (X1 + Y1) - C - D */
163 f25519_mul(X
, X
, &t0
); /* X = A ((X0 + Y0) (X1 + Y1) - C - D) */
164 f25519_mul(Y
, Y
, &t0
); /* Y = A (D - a C) */
165 f25519_sqr(&t0
, &t0
); /* t0 = B = A^2 */
166 f25519_mul(&t1
, &t2
, &t3
); /* t1 = C D */
167 f25519_mul(&t1
, &t1
, D
); /* t1 = E = d C D */
168 f25519_sub(&t2
, &t0
, &t1
); /* t2 = F = B - E */
169 f25519_add(&t1
, &t0
, &t1
); /* t1 = G = B + E */
170 f25519_mul(X
, X
, &t2
); /* X = A F ((X0 + Y0) (X1 + Y1) - C - D) */
171 f25519_mul(Y
, Y
, &t1
); /* Y = A G (D - a C) */
172 f25519_mul(Z
, &t1
, &t2
); /* Z = F G */
175 static void ptdbl(f25519
*X
, f25519
*Y
, f25519
*Z
,
176 const f25519
*X0
, const f25519
*Y0
, const f25519
*Z0
)
180 /* Bernstein, Birkner, Joye, Lange, and Peters, `Twisted Edwards Curves',
181 * 2008-03-13, https://cr.yp.to/newelliptic/twisted-20080313.pdf shows the
184 * B = (X1 + Y1)^2; C = X1^2; D = Y1^2; E = a C;
185 * F = E + D; H = Z1^2; J = F - 2 H;
186 * X3 = (B - C - D) J; Y3 = F (E - D); Z3 = F J.
188 * Note that a = -1, which things easier.
191 f25519_add(&t0
, X0
, Y0
); /* t0 = X0 + Y0 */
192 f25519_sqr(&t0
, &t0
); /* t0 = B = (X0 + Y0)^2 */
193 f25519_sqr(&t1
, X0
); /* t1 = C = X0^2 */
194 f25519_sqr(&t2
, Y0
); /* t2 = D = Y0^2 */
195 f25519_add(Y
, &t1
, &t2
); /* Y = C + D = -(E - D) */
196 f25519_sub(X
, &t0
, Y
); /* X = B - C - D */
198 f25519_sub(&t0
, &t2
, &t1
); /* t0 = F = D - C = E + D */
199 f25519_sqr(&t1
, Z0
); /* t1 = H = Z0^2 */
200 f25519_add(&t1
, &t1
, &t1
); /* t1 = 2 H */
201 f25519_sub(&t1
, &t0
, &t1
); /* t1 = J = F - 2 H */
202 f25519_mul(X
, X
, &t1
); /* X = (B - C - D) J */
203 f25519_mul(Y
, Y
, &t0
); /* Y = -F (E - D) */
204 f25519_neg(Y
, Y
); /* Y = F (E - D) */
205 f25519_mul(Z
, &t0
, &t1
); /* Z = F J */
208 static DEFINE_SCMUL(ptmul
, f25519
, 4, PIECEWD
, NPIECE
, ptadd
, ptdbl
)
209 static DEFINE_SCSIMMUL(ptsimmul
, f25519
, 2, PIECEWD
, NPIECE
, ptadd
, ptdbl
)
211 /*----- Key derivation utilities ------------------------------------------*/
213 static void unpack_key(scaf_piece a
[NPIECE
], octet h1
[32],
214 const octet
*k
, size_t ksz
)
217 octet b
[SHA512_DIGEST_SIZE
];
219 sha512_init_ctx(&h
); sha512_process_bytes(k
, ksz
, &h
); sha512_finish_ctx(&h
, b
);
220 b
[0] &= 0xf8u
; b
[31] = (b
[31]&0x3f) | 0x40;
221 scaf_load(a
, b
, 32, NPIECE
, PIECEWD
);
222 if (h1
) memcpy(h1
, b
+ 32, 32);
225 #define PREFIX_BUFSZ 290
226 static size_t prefix(octet b
[PREFIX_BUFSZ
],
227 int phflag
, const octet
*p
, size_t psz
)
229 if (phflag
< 0) return (0);
230 memcpy(b
, "SigEd25519 no Ed25519 collisions", 32);
232 assert(psz
< ED25519_MAXPERSOSZ
); b
[33] = psz
; memcpy(b
+ 34, p
, psz
);
236 /*----- Main code ---------------------------------------------------------*/
238 /* --- @ed25519_pubkey@ --- *
240 * Arguments: @octet K[ED25519_PUBSZ]@ = where to put the public key
241 * @const void *k@ = private key
242 * @size_t ksz@ = length of private key
246 * Use: Derives the public key from a private key.
249 void ed25519_pubkey(octet K
[ED25519_PUBSZ
], const void *k
, size_t ksz
)
251 scaf_piece a
[NPIECE
];
254 unpack_key(a
, 0, k
, ksz
);
255 ptmul(&AX
, &AY
, &AZ
, a
, BX
, BY
, BZ
);
256 ptencode(K
, &AX
, &AY
, &AZ
);
259 /* --- @ed25519_sign@, @ed25519ctx_sign@ --- *
261 * Arguments: @octet sig[ED25519_SIGSZ]@ = where to put the signature
262 * @const void *k@ = private key
263 * @size_t ksz@ = length of private key
264 * @const octet K[ED25519_PUBSZ]@ = public key
265 * @int phflag@ = whether the `message' has been hashed already
266 * @const void *p@ = personalization string
267 * @size_t psz@ = length of personalization string
268 * @const void *m@ = message to sign
269 * @size_t msz@ = length of message
273 * Use: Signs a message.
275 * In @ed25519ctx_sign@, if @phflag@ is @-1@ then you get plain
276 * old Ed25519: the personalization string pointer @p@ will be
277 * ignored. If @phflag > 0@ then the `message' @m@ should be a
278 * SHA512 hash of the actual message.
281 void ed25519ctx_sign(octet sig
[ED25519_SIGSZ
],
282 const void *k
, size_t ksz
, const octet K
[ED25519_PUBSZ
],
283 int phflag
, const void *p
, size_t psz
,
284 const void *m
, size_t msz
)
287 scaf_piece a
[NPIECE
], r
[NPIECE
], t
[NPIECE
], scratch
[3*NPIECE
];
288 scaf_dblpiece tt
[2*NPIECE
];
290 octet h1
[32], pb
[PREFIX_BUFSZ
], rb
[SHA512_DIGEST_SIZE
];
293 /* Get my private key. */
294 unpack_key(a
, h1
, k
, ksz
);
296 /* Determine the prefix string. */
297 psz
= prefix(pb
, phflag
, p
, psz
);
299 /* Select the nonce and the vector part. */
301 sha512_process_bytes(pb
, psz
, &h
);
302 sha512_process_bytes(h1
, 32, &h
);
303 sha512_process_bytes(m
, msz
, &h
);
304 sha512_finish_ctx(&h
, rb
);
305 scaf_loaddbl(tt
, rb
, 64, 2*NPIECE
, PIECEWD
);
306 scaf_reduce(r
, tt
, l
, mu
, NPIECE
, PIECEWD
, scratch
);
307 ptmul(&RX
, &RY
, &RZ
, r
, BX
, BY
, BZ
);
308 ptencode(sig
, &RX
, &RY
, &RZ
);
310 /* Calculate the scalar part. */
312 sha512_process_bytes(pb
, psz
, &h
);
313 sha512_process_bytes(sig
, 32, &h
);
314 sha512_process_bytes(K
, 32, &h
);
315 sha512_process_bytes(m
, msz
, &h
);
316 sha512_finish_ctx(&h
, rb
);
317 scaf_loaddbl(tt
, rb
, 64, 2*NPIECE
, PIECEWD
);
318 scaf_reduce(t
, tt
, l
, mu
, NPIECE
, PIECEWD
, scratch
);
319 scaf_mul(tt
, t
, a
, NPIECE
);
320 for (i
= 0; i
< NPIECE
; i
++) tt
[i
] += r
[i
];
321 scaf_reduce(t
, tt
, l
, mu
, NPIECE
, PIECEWD
, scratch
);
322 scaf_store(sig
+ 32, 32, t
, NPIECE
, PIECEWD
);
325 void ed25519_sign(octet sig
[ED25519_SIGSZ
],
326 const void *k
, size_t ksz
, const octet K
[ED25519_PUBSZ
],
327 const void *m
, size_t msz
)
328 { ed25519ctx_sign(sig
, k
, ksz
, K
, -1, 0, 0, m
, msz
); }
330 /* --- @ed25519_verify@, @ed25519ctx_verify@ --- *
332 * Arguments: @const octet K[ED25519_PUBSZ]@ = public key
333 * @int phflag@ = whether the `message' has been hashed already
334 * @const void *p@ = personalization string
335 * @size_t psz@ = length of personalization string
336 * @const void *m@ = message to sign
337 * @size_t msz@ = length of message
338 * @const octet sig[ED25519_SIGSZ]@ = signature
340 * Returns: Zero if OK, negative on failure.
342 * Use: Verify a signature.
344 * In @ed25519ctx_verify@, if @phflag@ is @-1@ then you get
345 * plain old Ed25519: the personalization string pointer @p@
346 * will be ignored. If @phflag > 0@ then the `message' @m@
347 * should be a SHA512 hash of the actual message.
350 int ed25519ctx_verify(const octet K
[ED25519_PUBSZ
],
351 int phflag
, const void *p
, size_t psz
,
352 const void *m
, size_t msz
,
353 const octet sig
[ED25519_SIGSZ
])
356 scaf_piece s
[NPIECE
], t
[NPIECE
], scratch
[3*NPIECE
];
357 scaf_dblpiece tt
[2*NPIECE
];
358 f25519 AX
, AY
, AZ
, RX
, RY
, RZ
;
359 octet b
[PREFIX_BUFSZ
];
361 /* Unpack the public key. Negate it: we're meant to subtract the term
362 * involving the public key point, and this is easier than negating the
365 if (ptdecode(&AX
, &AY
, &AZ
, K
)) return (-1);
366 f25519_neg(&AX
, &AX
);
368 /* Load the scalar and check that it's in range. The easy way is to store
369 * it again and see if the two match.
371 scaf_loaddbl(tt
, sig
+ 32, 32, 2*NPIECE
, PIECEWD
);
372 scaf_reduce(s
, tt
, l
, mu
, NPIECE
, PIECEWD
, scratch
);
373 scaf_store(b
, 32, s
, NPIECE
, PIECEWD
);
374 if (memcmp(b
, sig
+ 32, 32) != 0) return (-1);
376 /* Check the signature. */
377 psz
= prefix(b
, phflag
, p
, psz
);
379 sha512_process_bytes(b
, psz
, &h
);
380 sha512_process_bytes(sig
, 32, &h
);
381 sha512_process_bytes(K
, 32, &h
);
382 sha512_process_bytes(m
, msz
, &h
);
383 sha512_finish_ctx(&h
, b
);
384 scaf_loaddbl(tt
, b
, 64, 2*NPIECE
, PIECEWD
);
385 scaf_reduce(t
, tt
, l
, mu
, NPIECE
, PIECEWD
, scratch
);
386 ptsimmul(&RX
, &RY
, &RZ
, s
, BX
, BY
, BZ
, t
, &AX
, &AY
, &AZ
);
387 ptencode(b
, &RX
, &RY
, &RZ
);
388 if (memcmp(b
, sig
, 32) != 0) return (-1);
394 int ed25519_verify(const octet K
[ED25519_PUBSZ
],
395 const void *m
, size_t msz
,
396 const octet sig
[ED25519_SIGSZ
])
397 { return (ed25519ctx_verify(K
, -1, 0, 0, m
, msz
, sig
)); }
399 /*----- That's all, folks -------------------------------------------------*/