bbaa123074e14605b795825960eb3f3440b816ad
3 * Diffie--Hellman groups
5 * (c) 2017 Straylight/Edgeware
8 /*----- Licensing notice --------------------------------------------------*
10 * This file is part of Trivial IP Encryption (TrIPE).
12 * TrIPE is free software; you can redistribute it and/or modify
13 * it under the terms of the GNU General Public License as published by
14 * the Free Software Foundation; either version 2 of the License, or
15 * (at your option) any later version.
17 * TrIPE 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 General Public License for more details.
22 * You should have received a copy of the GNU General Public License
23 * along with TrIPE; if not, write to the Free Software Foundation,
24 * Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA.
27 /*----- Header files ------------------------------------------------------*/
31 /*----- Common utilities --------------------------------------------------*/
35 * Arguments: @pre@ = prefix for defined functions
36 * @ty@, @TY@ = key type name (lower- and upper-case)
37 * @setgroup@ = code to initialize @kd->g@
38 * @setpriv@ = code to initialize @kd->kpriv@
39 * @setpub@ = code to initialize @kd->kpub@
41 * Use: Generates the body of one of the (rather tedious) key loading
42 * functions. See the description of @KEYTYPES@ below for the
46 #define KLOAD_HALF(pre, ty, TY, which, WHICH, setgroup, setpriv, setpub) \
47 static int pre##_ld##which(key_file *kf, key *k, key_data *d, \
48 kdata *kd, dstr *t, dstr *e) \
50 key_packstruct kps[TY##_##WHICH##FETCHSZ]; \
55 /* --- Initialize things we've not set up yet --- */ \
57 kd->grp = 0; kd->k = 0; kd->K = 0; \
59 /* --- Unpack the key --- */ \
61 kp = key_fetchinit(ty##_##which##fetch, kps, &p); \
62 if ((rc = key_unpack(kp, d, t)) != 0) { \
63 a_format(e, "unpack-failed", "%s", key_strerror(rc), A_END); \
67 /* --- Extract the pieces of the key --- */ \
73 /* --- We win --- */ \
80 if (kd->K) pre##_freege(kd->grp, kd->K); \
81 if (kd->k) pre##_freesc(kd->grp, kd->k); \
82 pre##_freegrp(kd->grp); \
91 #define KLOAD(pre, ty, TY, setgroup, setpriv, setpub) \
92 static void pre##_freegrp(dhgrp *); \
93 static void pre##_freesc(const dhgrp *, dhsc *); \
94 static void pre##_freege(const dhgrp *, dhge *); \
95 KLOAD_HALF(pre, ty, TY, priv, PRIV, setgroup, setpriv, setpub) \
96 KLOAD_HALF(pre, ty, TY, pub, PUB, setgroup, { kd->k = 0; }, setpub)
99 static void setupstr(mptext_stringctx
*sc
)
100 { sc
->buf
= (char *)buf_u
; sc
->lim
= sc
->buf
+ sizeof(buf_u
); }
102 static const char *donestr(mptext_stringctx
*sc
)
103 { *sc
->buf
= 0; return ((const char *)buf_u
); }
105 static void addlitstr(const char *p
, mptext_stringctx
*sc
)
106 { mptext_stringops
.put(p
, strlen(p
), sc
); }
108 static void addmpstr(mp
*x
, int radix
, mptext_stringctx
*sc
)
112 if (radix
== 16) addlitstr("0x", sc
);
113 else if (radix
== 8) addlitstr("0", sc
);
114 else if (radix
!= 10) { sprintf(b
, "%d#", radix
); addlitstr(b
, sc
); }
115 mp_write(x
, radix
, &mptext_stringops
, sc
);
118 static const char *mpstr(mp
*x
, int radix
)
123 addmpstr(x
, radix
, &sc
);
124 return (donestr(&sc
));
128 /*----- Schnorr groups ----------------------------------------------------*/
130 typedef struct intdh_grp
{
137 typedef struct intdh_sc
{ mp
*x
; } intdh_sc
;
138 typedef struct intdh_ge
{ mp
*X
; } intdh_ge
;
140 static dhgrp
*intdh_mkgroup(const dh_param
*dp
)
142 intdh_grp
*g
= CREATE(intdh_grp
);
143 g
->_g
.scsz
= mp_octets(dp
->q
);
144 g
->gesz
= mp_octets(dp
->p
);
145 mpmont_create(&g
->mm
, dp
->p
);
146 g
->q
= MP_COPY(dp
->q
);
147 g
->G
= mpmont_mul(&g
->mm
, MP_NEW
, dp
->g
, g
->mm
.r2
);
151 static dhsc
*intdh_mptosc(const dhgrp
*gg
, mp
*z
)
153 const intdh_grp
*g
= (const intdh_grp
*)gg
;
154 intdh_sc
*x
= CREATE(intdh_sc
);
155 x
->x
= MP_NEW
; mp_div(0, &x
->x
, z
, g
->q
);
159 static dhge
*intdh_mptoge(const dhgrp
*gg
, mp
*z
)
161 const intdh_grp
*g
= (const intdh_grp
*)gg
;
162 intdh_ge
*Y
= CREATE(intdh_ge
);
163 mp
*t
= MP_NEW
; mp_div(0, &t
, z
, g
->mm
.m
);
164 Y
->X
= mpmont_mul(&g
->mm
, t
, t
, g
->mm
.r2
);
169 { kd
->grp
= intdh_mkgroup(&p
.dp
); },
170 { kd
->k
= intdh_mptosc(kd
->grp
, p
.x
); },
171 { kd
->K
= intdh_mptoge(kd
->grp
, p
.y
); })
173 static const char *intdh_checkgrp(const dhgrp
*gg
)
175 const intdh_grp
*g
= (const intdh_grp
*)gg
;
178 if (!pgen_primep(g
->mm
.m
, &rand_global
)) return ("p is not prime");
179 if (!pgen_primep(g
->q
, &rand_global
)) return ("q is not prime");
180 mp_div(0, &t
, g
->mm
.m
, g
->q
);
181 if (!MP_EQ(t
, MP_ONE
)) return ("q is not a subgroup order");
182 t
= mpmont_expr(&g
->mm
, t
, g
->G
, g
->q
);
183 if (!MP_EQ(t
, g
->mm
.r
)) return ("g not in the subgroup");
187 static void intdh_grpinfo(const dhgrp
*gg
, admin
*adm
)
189 const intdh_grp
*g
= (const intdh_grp
*)gg
;
192 "kx-group-order-bits=%lu", (unsigned long)mp_bits(g
->q
),
193 "kx-group-elt-bits=%lu", (unsigned long)mp_bits(g
->mm
.m
),
198 static void intdh_tracegrp(const dhgrp
*gg
)
200 const intdh_grp
*g
= (const intdh_grp
*)gg
;
202 trace(T_CRYPTO
, "crypto: group type `dh'");
203 trace(T_CRYPTO
, "crypto: p = %s", mpstr(g
->mm
.m
, 10));
204 trace(T_CRYPTO
, "crypto: q = %s", mpstr(g
->q
, 10));
205 t
= mpmont_reduce(&g
->mm
, t
, g
->G
);
206 trace(T_CRYPTO
, "crypto: g = %s", mpstr(t
, 10));
211 static int intdh_samegrpp(const dhgrp
*gg
, const dhgrp
*hh
)
213 const intdh_grp
*g
= (const intdh_grp
*)gg
, *h
= (const intdh_grp
*)hh
;
214 return (MP_EQ(g
->mm
.m
, h
->mm
.m
) && MP_EQ(g
->q
, h
->q
) && MP_EQ(g
->G
, h
->G
));
217 static void intdh_freegrp(dhgrp
*gg
)
219 intdh_grp
*g
= (intdh_grp
*)gg
;
220 mpmont_destroy(&g
->mm
); MP_DROP(g
->q
); MP_DROP(g
->G
);
224 static dhsc
*intdh_ldsc(const dhgrp
*gg
, const void *p
, size_t sz
)
225 { const intdh_grp
*g
= (const intdh_grp
*)gg
;
226 intdh_sc
*x
= CREATE(intdh_sc
);
227 mp
*t
= mp_loadb(MP_NEW
, p
, sz
);
228 mp_div(0, &t
, t
, g
->q
); x
->x
= t
;
232 static int intdh_stsc(const dhgrp
*gg
, void *p
, size_t sz
, const dhsc
*xx
)
234 const intdh_sc
*x
= (const intdh_sc
*)xx
;
235 mp_storeb(x
->x
, p
, sz
);
239 static dhsc
*intdh_randsc(const dhgrp
*gg
)
241 const intdh_grp
*g
= (const intdh_grp
*)gg
;
242 intdh_sc
*x
= CREATE(intdh_sc
);
243 x
->x
= mprand_range(MP_NEW
, g
->q
, &rand_global
, 0);
248 static const char *intdh_scstr(const dhgrp
*gg
, const dhsc
*xx
)
249 { const intdh_sc
*x
= (const intdh_sc
*)xx
; return (mpstr(x
->x
, 10)); }
252 static void intdh_freesc(const dhgrp
*gg
, dhsc
*xx
)
254 intdh_sc
*x
= (intdh_sc
*)xx
;
255 MP_DROP(x
->x
); DESTROY(x
);
258 static dhge
*intdh_ldge(const dhgrp
*gg
, buf
*b
, int fmt
)
260 const intdh_grp
*g
= (const intdh_grp
*)gg
;
266 case DHFMT_VAR
: case DHFMT_HASH
:
267 if ((t
= buf_getmp(b
)) == 0) return (0);
270 if ((p
= buf_get(b
, g
->gesz
)) == 0) return (0);
271 t
= mp_loadb(MP_NEW
, p
, g
->gesz
);
276 Y
= CREATE(intdh_ge
);
277 mp_div(0, &t
, t
, g
->mm
.m
);
278 Y
->X
= mpmont_mul(&g
->mm
, t
, t
, g
->mm
.r2
);
282 static int intdh_stge(const dhgrp
*gg
, buf
*b
, const dhge
*YY
, int fmt
)
284 const intdh_grp
*g
= (const intdh_grp
*)gg
;
285 const intdh_ge
*Y
= (const intdh_ge
*)YY
;
290 t
= mpmont_reduce(&g
->mm
, MP_NEW
, Y
->X
);
292 case DHFMT_VAR
: case DHFMT_HASH
:
293 rc
= buf_putmp(b
, t
);
296 if ((p
= buf_get(b
, g
->gesz
)) == 0)
299 mp_storeb(t
, p
, g
->gesz
);
310 static int intdh_checkge(const dhgrp
*gg
, const dhge
*YY
)
312 const intdh_grp
*g
= (const intdh_grp
*)gg
;
313 const intdh_ge
*Y
= (const intdh_ge
*)YY
;
317 if (MP_EQ(Y
->X
, g
->mm
.r
)) rc
= -1;
318 T
= mpmont_expr(&g
->mm
, MP_NEW
, Y
->X
, g
->q
);
319 if (!MP_EQ(T
, g
->mm
.r
)) rc
= -1;
324 static int intdh_eq(const dhgrp
*gg
, const dhge
*YY
, const dhge
*ZZ
)
326 const intdh_ge
*Y
= (const intdh_ge
*)YY
, *Z
= (const intdh_ge
*)ZZ
;
327 return (MP_EQ(Y
->X
, Z
->X
));
330 static dhge
*intdh_mul(const dhgrp
*gg
, const dhsc
*xx
, const dhge
*YY
)
332 const intdh_grp
*g
= (const intdh_grp
*)gg
;
333 const intdh_sc
*x
= (const intdh_sc
*)xx
;
334 const intdh_ge
*Y
= (const intdh_ge
*)YY
;
335 intdh_ge
*Z
= CREATE(intdh_ge
);
337 Z
->X
= mpmont_expr(&g
->mm
, MP_NEW
, Y ? Y
->X
: g
->G
, x
->x
);
342 static const char *intdh_gestr(const dhgrp
*gg
, const dhge
*YY
)
344 const intdh_grp
*g
= (const intdh_grp
*)gg
;
345 const intdh_ge
*Y
= (const intdh_ge
*)YY
;
346 mp
*t
= mpmont_reduce(&g
->mm
, MP_NEW
, Y
->X
);
347 const char *p
= mpstr(t
, 10);
353 static void intdh_freege(const dhgrp
*gg
, dhge
*YY
)
354 { intdh_ge
*Y
= (intdh_ge
*)YY
; MP_DROP(Y
->X
); DESTROY(Y
); }
356 /*----- Elliptic curve groups ---------------------------------------------*/
358 typedef struct ecdh_grp
{
364 typedef struct ecdh_sc
{ mp
*x
; } ecdh_sc
;
365 typedef struct ecdh_ge
{ ec Q
; } ecdh_ge
;
367 static dhgrp
*ecdh_mkgroup(const char *cstr
, dstr
*e
)
373 if ((err
= ec_getinfo(&ei
, cstr
)) != 0) {
374 a_format(e
, "decode-failed", "%s", err
, A_END
);
377 g
= CREATE(ecdh_grp
);
379 EC_CREATE(&g
->P
); EC_IN(g
->ei
.c
, &g
->P
, &g
->ei
.g
);
380 g
->_g
.scsz
= mp_octets(g
->ei
.r
);
384 static dhsc
*ecdh_mptosc(const dhgrp
*gg
, mp
*z
)
386 const ecdh_grp
*g
= (const ecdh_grp
*)gg
;
387 ecdh_sc
*x
= CREATE(ecdh_sc
);
388 x
->x
= MP_NEW
; mp_div(0, &x
->x
, z
, g
->ei
.r
);
392 static dhge
*ecdh_ectoge(const dhgrp
*gg
, ec
*Q
)
394 const ecdh_grp
*g
= (const ecdh_grp
*)gg
;
395 ecdh_ge
*Y
= CREATE(ecdh_ge
); EC_CREATE(&Y
->Q
);
396 EC_IN(g
->ei
.c
, &Y
->Q
, Q
);
397 if (EC_CHECK(g
->ei
.c
, &Y
->Q
))
398 { EC_DESTROY(&Y
->Q
); DESTROY(Y
); return (0); }
403 { if ((kd
->grp
= ecdh_mkgroup(p
.cstr
, e
)) == 0) goto fail
; },
404 { kd
->k
= ecdh_mptosc(kd
->grp
, p
.x
); },
405 { if ((kd
->K
= ecdh_ectoge(kd
->grp
, &p
.p
)) == 0) {
406 a_format(e
, "bad-public-vector", A_END
);
411 static const char *ecdh_checkgrp(const dhgrp
*gg
)
413 const ecdh_grp
*g
= (const ecdh_grp
*)gg
;
414 return (ec_checkinfo(&g
->ei
, &rand_global
));
417 static void ecdh_grpinfo(const dhgrp
*gg
, admin
*adm
)
419 const ecdh_grp
*g
= (const ecdh_grp
*)gg
;
422 "kx-group-order-bits=%lu", (unsigned long)mp_bits(g
->ei
.r
),
423 "kx-group-elt-bits=%lu", (unsigned long)2*g
->ei
.c
->f
->nbits
,
428 static void addfestr(field
*f
, mp
*x
, mptext_stringctx
*sc
)
429 { addmpstr(x
, F_TYPE(f
) == FTY_PRIME ?
10 : 16, sc
); }
431 static void addintfestr(field
*f
, mp
*x
, mptext_stringctx
*sc
)
432 { mp
*t
= F_OUT(f
, MP_NEW
, x
); addfestr(f
, x
, sc
); MP_DROP(t
); }
434 static const char *intfestr(field
*f
, mp
*x
)
438 addintfestr(f
, x
, &sc
);
439 return (donestr(&sc
));
442 static void ecdh_tracegrp(const dhgrp
*gg
)
444 const ecdh_grp
*g
= (const ecdh_grp
*)gg
;
445 const ec_curve
*c
= g
->ei
.c
;
448 trace(T_CRYPTO
, "crypto: group type `ec'");
451 trace(T_CRYPTO
, "crypto: prime field `%s'", F_NAME(f
));
452 trace(T_CRYPTO
, "crypto: p = %s", mpstr(f
->q
, 10));
455 trace(T_CRYPTO
, "crypto: binary field `%s'", F_NAME(f
));
456 trace(T_CRYPTO
, "crypto: degree = %lu", f
->nbits
- 1);
459 trace(T_CRYPTO
, "crypto: unknown field type! `%s'", F_NAME(f
));
462 trace(T_CRYPTO
, "crypto: curve type `%s'", EC_NAME(c
));
463 trace(T_CRYPTO
, "crypto: curve a = %s", intfestr(f
, c
->a
));
464 trace(T_CRYPTO
, "crypto: curve b = %s", intfestr(f
, c
->b
));
465 trace(T_CRYPTO
, "crypto: n = %s", mpstr(g
->ei
.r
, 10));
466 trace(T_CRYPTO
, "crypto: h = %s", mpstr(g
->ei
.h
, 10));
470 static int ecdh_samegrpp(const dhgrp
*gg
, const dhgrp
*hh
)
472 const ecdh_grp
*g
= (const ecdh_grp
*)gg
, *h
= (const ecdh_grp
*)hh
;
473 return (ec_sameinfop(&g
->ei
, &h
->ei
));
476 static void ecdh_freegrp(dhgrp
*gg
)
478 ecdh_grp
*g
= (ecdh_grp
*)gg
;
479 EC_DESTROY(&g
->P
); ec_freeinfo(&g
->ei
);
483 static dhsc
*ecdh_ldsc(const dhgrp
*gg
, const void *p
, size_t sz
)
485 const ecdh_grp
*g
= (const ecdh_grp
*)gg
;
486 ecdh_sc
*x
= CREATE(ecdh_sc
);
487 mp
*t
= mp_loadb(MP_NEW
, p
, sz
);
488 mp_div(0, &t
, t
, g
->ei
.r
); x
->x
= t
;
492 static int ecdh_stsc(const dhgrp
*gg
, void *p
, size_t sz
, const dhsc
*xx
)
494 const ecdh_sc
*x
= (const ecdh_sc
*)xx
;
495 mp_storeb(x
->x
, p
, sz
);
499 static dhsc
*ecdh_randsc(const dhgrp
*gg
)
501 const ecdh_grp
*g
= (const ecdh_grp
*)gg
;
502 ecdh_sc
*x
= CREATE(ecdh_sc
);
503 x
->x
= mprand_range(MP_NEW
, g
->ei
.r
, &rand_global
, 0);
508 static const char *ecdh_scstr(const dhgrp
*gg
, const dhsc
*xx
)
510 const ecdh_sc
*x
= (const ecdh_sc
*)xx
;
511 return (mpstr(x
->x
, 10));
515 static void ecdh_freesc(const dhgrp
*gg
, dhsc
*xx
)
516 { ecdh_sc
*x
= (ecdh_sc
*)xx
; MP_DROP(x
->x
); DESTROY(x
); }
518 static dhge
*ecdh_ldge(const dhgrp
*gg
, buf
*b
, int fmt
)
520 const ecdh_grp
*g
= (const ecdh_grp
*)gg
;
525 case DHFMT_VAR
: case DHFMT_HASH
: if (buf_getec(b
, &T
)) return (0); break;
526 case DHFMT_STD
: if (ec_getraw(g
->ei
.c
, b
, &T
)) return (0); break;
530 EC_IN(g
->ei
.c
, &T
, &T
);
531 Y
= CREATE(ecdh_ge
); Y
->Q
= T
;
535 static int ecdh_stge(const dhgrp
*gg
, buf
*b
, const dhge
*YY
, int fmt
)
537 const ecdh_grp
*g
= (const ecdh_grp
*)gg
;
538 const ecdh_ge
*Y
= (const ecdh_ge
*)YY
;
542 EC_OUT(g
->ei
.c
, &T
, &Y
->Q
);
544 case DHFMT_VAR
: case DHFMT_HASH
: rc
= buf_putec(b
, &T
); break;
545 case DHFMT_STD
: rc
= ec_putraw(g
->ei
.c
, b
, &T
); break;
552 static int ecdh_checkge(const dhgrp
*gg
, const dhge
*YY
)
554 const ecdh_grp
*g
= (const ecdh_grp
*)gg
;
555 const ecdh_ge
*Y
= (const ecdh_ge
*)YY
;
559 if (EC_ATINF(&Y
->Q
)) rc
= -1;
560 ec_imul(g
->ei
.c
, &T
, &Y
->Q
, g
->ei
.r
);
561 if (!EC_ATINF(&T
)) rc
= -1;
566 static int ecdh_eq(const dhgrp
*gg
, const dhge
*YY
, const dhge
*ZZ
)
568 const ecdh_grp
*g
= (const ecdh_grp
*)gg
;
569 const ecdh_ge
*Y
= (const ecdh_ge
*)YY
, *Z
= (const ecdh_ge
*)ZZ
;
570 ec T
= EC_INIT
, U
= EC_INIT
; int rc
;
571 EC_FIX(g
->ei
.c
, &T
, &Y
->Q
); EC_FIX(g
->ei
.c
, &U
, &Z
->Q
);
573 EC_DESTROY(&T
); EC_DESTROY(&U
);
577 static dhge
*ecdh_mul(const dhgrp
*gg
, const dhsc
*xx
, const dhge
*YY
)
579 const ecdh_grp
*g
= (const ecdh_grp
*)gg
;
580 const ecdh_sc
*x
= (const ecdh_sc
*)xx
;
581 const ecdh_ge
*Y
= (const ecdh_ge
*)YY
;
582 ecdh_ge
*Z
= CREATE(ecdh_ge
); EC_CREATE(&Z
->Q
);
584 ec_imul(g
->ei
.c
, &Z
->Q
, Y ?
&Y
->Q
: &g
->P
, x
->x
);
589 static const char *ecdh_gestr(const dhgrp
*gg
, const dhge
*YY
)
591 const ecdh_grp
*g
= (const ecdh_grp
*)gg
;
592 const ecdh_ge
*Y
= (const ecdh_ge
*)YY
;
594 field
*f
= g
->ei
.c
->f
;
597 if (EC_ATINF(&Y
->Q
)) return ("inf");
599 EC_OUT(g
->ei
.c
, &T
, &Y
->Q
);
600 addfestr(f
, T
.x
, &sc
);
601 addlitstr(", ", &sc
);
602 addfestr(f
, T
.y
, &sc
);
604 return (donestr(&sc
));
608 static void ecdh_freege(const dhgrp
*gg
, dhge
*YY
)
609 { ecdh_ge
*Y
= (ecdh_ge
*)YY
; EC_DESTROY(&Y
->Q
); DESTROY(Y
); }
611 /*----- Diffie--Hellman group table ---------------------------------------*/
613 const dhops dhtab
[] = {
617 #define DH(name, pre) \
618 { name, pre##_ldpriv, pre##_ldpub, pre##_checkgrp, \
619 pre##_grpinfo, T( pre##_tracegrp COMMA ) pre##_samegrpp, \
621 pre##_ldsc, pre##_stsc, pre##_randsc, T( pre##_scstr COMMA ) \
623 pre##_ldge, pre##_stge, pre##_checkge, pre##_eq, pre##_mul, \
624 T( pre##_gestr COMMA ) pre##_freege }, \
634 /*----- That's all, folks -------------------------------------------------*/