2 * Copyright (c) 2013, SUSE Inc.
4 * This program is licensed under the BSD license, read LICENSE.BSD
5 * for further information
8 /* simple and slow rsa/dsa verification code. */
15 #include "solv_pgpvrfy.h"
17 typedef unsigned int mp_t;
18 typedef unsigned long long mp2_t;
21 #define MP_T_BITS (MP_T_BYTES * 8)
24 mpzero(int len, mp_t *target)
26 memset(target, 0, MP_T_BYTES * len);
32 return solv_calloc(len, MP_T_BYTES);
36 mpcpy(int len, mp_t *target, mp_t *source)
38 memcpy(target, source, len * MP_T_BYTES);
42 static void mpdump(int l, mp_t *a, char *s)
46 fprintf(stderr, "%s", s);
47 for (i = l - 1; i >= 0; i--)
48 fprintf(stderr, "%0*x", MP_T_BYTES * 2, a[i]);
49 fprintf(stderr, "\n");
53 /* target[len] = x, target = target % mod
54 * assumes that target < (mod << MP_T_BITS)! */
56 mpdomod(int len, mp_t *target, mp2_t x, mp_t *mod)
59 for (i = len - 1; i >= 0; i--)
61 x = (x << MP_T_BITS) | target[i];
68 while (x >= 2 * (mp2_t)mod[i])
71 mp2_t z = x / ((mp2_t)mod[i] + 1);
73 for (j = 0; j < i; j++)
92 for (j = i - 1; j >= 0; j--)
93 if (target[j] < mod[j])
95 else if (target[j] > mod[j])
98 /* target >= mod, subtract mod */
100 for (j = 0; j <= i; j++)
102 mp2_t n2 = mod[j] + n;
103 n = n2 > target[j] ? 1 : 0;
104 target[j] -= (mp_t)n2;
109 /* target += src * m */
111 mpmult_add_int(int len, mp_t *target, mp_t *src, mp2_t m, mp_t *mod)
115 for (i = 0; i < len; i++)
117 x += src[i] * m + target[i];
121 mpdomod(len, target, x, mod);
124 /* target = target << MP_T_BITS */
126 mpshift(int len, mp_t *target, mp_t *mod)
133 memmove(target + 1, target, (len - 1) * MP_T_BYTES);
135 mpdomod(len, target, x, mod);
138 /* target += m1 * m2 */
140 mpmult_add(int len, mp_t *target, mp_t *m1, int m2len, mp_t *m2, mp_t *tmp, mp_t *mod)
143 for (j = m2len - 1; j >= 0; j--)
149 for (i = 0; i < j; i++)
152 mpmult_add_int(len, target, tmp, m2[i], mod);
153 mpshift(len, tmp, mod);
156 mpmult_add_int(len, target, tmp, m2[i], mod);
159 /* target = target * m */
161 mpmult_inplace(int len, mp_t *target, mp_t *m, mp_t *tmp1, mp_t *tmp2, mp_t *mod)
164 mpmult_add(len, tmp1, target, len, m, tmp2, mod);
165 mpcpy(len, target, tmp1);
168 /* target = target ^ 16 * b ^ e */
170 mppow_int(int len, mp_t *target, mp_t *t, mp_t *mod, int e)
172 mp_t *t2 = t + len * 16;
173 mpmult_inplace(len, target, target, t, t2, mod);
174 mpmult_inplace(len, target, target, t, t2, mod);
175 mpmult_inplace(len, target, target, t, t2, mod);
176 mpmult_inplace(len, target, target, t, t2, mod);
178 mpmult_inplace(len, target, t + len * e, t, t2, mod);
181 /* target = b ^ e (b has to be < mod) */
183 mppow(int len, mp_t *target, mp_t *b, int elen, mp_t *e, mp_t *mod)
189 for (i = elen - 1; i >= 0; i--)
195 mpcpy(len, t + len, b);
196 for (j = 2; j < 16; j++)
197 mpmult_add(len, t + len * j, b, len, t + len * j - len, t + len * 16, mod);
201 mppow_int(len, target, t, mod, (e[i] >> 28) & 0x0f);
202 mppow_int(len, target, t, mod, (e[i] >> 24) & 0x0f);
203 mppow_int(len, target, t, mod, (e[i] >> 20) & 0x0f);
204 mppow_int(len, target, t, mod, (e[i] >> 16) & 0x0f);
205 mppow_int(len, target, t, mod, (e[i] >> 12) & 0x0f);
206 mppow_int(len, target, t, mod, (e[i] >> 8) & 0x0f);
207 mppow_int(len, target, t, mod, (e[i] >> 4) & 0x0f);
208 mppow_int(len, target, t, mod, e[i] & 0x0f);
209 #elif MP_T_BYTES == 1
210 mppow_int(len, target, t, mod, (e[i] >> 4) & 0x0f);
211 mppow_int(len, target, t, mod, e[i] & 0x0f);
217 /* target = m1 * m2 (m1 has to be < mod) */
219 mpmult(int len, mp_t *target, mp_t *m1, int m2len, mp_t *m2, mp_t *mod)
221 mp_t *tmp = mpnew(len);
223 mpmult_add(len, target, m1, m2len, m2, tmp, mod);
228 mpisless(int len, mp_t *a, mp_t *b)
231 for (i = len - 1; i >= 0; i--)
234 else if (a[i] > b[i])
240 mpiszero(int len, mp_t *a)
243 for (i = 0; i < len; i++)
250 mpdec(int len, mp_t *a)
253 for (i = 0; i < len; i++)
261 mpdsa(int pl, mp_t *p, int ql, mp_t *q, mp_t *g, mp_t *y, mp_t *r, mp_t *s, int hl, mp_t *h)
268 mpdump(pl, p, "p = ");
269 mpdump(ql, q, "q = ");
270 mpdump(pl, g, "g = ");
271 mpdump(pl, y, "y = ");
272 mpdump(ql, r, "r = ");
273 mpdump(ql, s, "s = ");
274 mpdump(hl, h, "h = ");
276 if (pl < ql || !mpisless(pl, g, p) || !mpisless(pl, y, p))
277 return 0; /* hmm, bad pubkey? */
278 if (!mpisless(ql, r, q) || mpiszero(ql, r))
280 if (!mpisless(ql, s, q) || mpiszero(ql, s))
282 tmp = mpnew(pl); /* note pl */
283 mpcpy(ql, tmp, q); /* tmp = q */
284 mpdec(ql, tmp); /* tmp-- */
285 mpdec(ql, tmp); /* tmp-- */
287 mppow(ql, w, s, ql, tmp, q); /* w = s ^ tmp (s ^ -1) */
288 u1 = mpnew(pl); /* note pl */
289 /* order is important here: h can be >= q */
290 mpmult(ql, u1, w, hl, h, q); /* u1 = w * h */
291 u2 = mpnew(ql); /* u2 = 0 */
292 mpmult(ql, u2, w, ql, r, q); /* u2 = w * r */
296 mppow(pl, gu1, g, ql, u1, p); /* gu1 = g ^ u1 */
297 mppow(pl, yu2, y, ql, u2, p); /* yu2 = y ^ u2 */
298 mpmult(pl, u1, gu1, pl, yu2, p); /* u1 = gu1 * yu2 */
302 u2[0] = 1; /* u2 = 1 */
303 mpmult(ql, tmp, u2, pl, u1, q); /* tmp = u2 * u1 */
307 mpdump(ql, tmp, "res = ");
309 if (memcmp(tmp, r, ql * MP_T_BYTES) != 0)
319 mprsa(int nl, mp_t *n, int el, mp_t *e, mp_t *m, mp_t *c)
323 mpdump(nl, n, "n = ");
324 mpdump(el, e, "e = ");
325 mpdump(nl, m, "m = ");
326 mpdump(nl, c, "c = ");
328 if (!mpisless(nl, m, n))
330 if (!mpisless(nl, c, n))
333 mppow(nl, tmp, m, el, e, n); /* tmp = m ^ e */
335 mpdump(nl, tmp, "res = ");
337 if (memcmp(tmp, c, nl * MP_T_BYTES) != 0)
346 /* create mp with size tbits from data with size dbits */
348 mpbuild(const unsigned char *d, int dbits, int tbits, int *mplp)
350 int l = (tbits + MP_T_BITS - 1) / MP_T_BITS;
353 mp_t *out = mpnew(l ? l : 1);
356 dl = (dbits + 7) / 8;
359 dl = (tbits + 7) / 8;
360 for (i = 0; dl > 0; dl--, i++)
363 out[i / MP_T_BYTES] |= x << (8 * (i % MP_T_BYTES));
368 static const unsigned char *
369 findmpi(const unsigned char **mpip, int *mpilp, int maxbits, int *outlen)
372 const unsigned char *mpi = *mpip;
378 bits = mpi[0] << 8 | mpi[1];
379 l = 2 + (bits + 7) / 8;
380 if (bits > maxbits || mpil < l || (bits && !mpi[2]))
392 solv_pgpvrfy(const unsigned char *pub, int publ, const unsigned char *sig, int sigl)
395 unsigned char *oid = 0;
396 const unsigned char *mpi;
400 if (!pub || !sig || publ < 1 || sigl < 2)
402 if (pub[0] != sig[0])
403 return 0; /* key algo mismatch */
407 hashl = 16; /* MD5 */
408 oid = (unsigned char *)"\022\060\040\060\014\006\010\052\206\110\206\367\015\002\005\005\000\004\020";
411 hashl = 20; /* SHA-1 */
412 oid = (unsigned char *)"\017\060\041\060\011\006\005\053\016\003\002\032\005\000\004\024";
415 hashl = 32; /* SHA-256 */
416 oid = (unsigned char *)"\023\060\061\060\015\006\011\140\206\110\001\145\003\004\002\001\005\000\004\040";
419 hashl = 64; /* SHA-512 */
420 oid = (unsigned char *)"\023\060\121\060\015\006\011\140\206\110\001\145\003\004\002\003\005\000\004\100";
423 return 0; /* unsupported hash algo */
425 if (sigl < 2 + hashl)
431 const unsigned char *n, *e, *m;
433 int nlen, elen, mlen, clen;
434 mp_t *nx, *ex, *mx, *cx;
439 n = findmpi(&mpi, &mpil, 8192, &nlen);
440 e = findmpi(&mpi, &mpil, 1024, &elen);
441 mpi = sig + 2 + hashl;
442 mpil = sigl - (2 + hashl);
443 m = findmpi(&mpi, &mpil, nlen, &mlen);
444 if (!n || !e || !m || !nlen || !elen)
446 /* build padding block */
447 clen = (nlen - 1) / 8;
448 if (hashl + *oid + 2 > clen)
450 c = solv_malloc(clen);
451 memset(c, 0xff, clen);
453 memcpy(c + clen - hashl, sig + 2, hashl);
454 memcpy(c + clen - hashl - *oid, oid + 1, *oid);
455 c[clen - hashl - *oid - 1] = 0;
456 clen = clen * 8 - 7; /* always <= nlen */
457 nx = mpbuild(n, nlen, nlen, &nxl);
458 ex = mpbuild(e, elen, elen, &exl);
459 mx = mpbuild(m, mlen, nlen, 0);
460 cx = mpbuild(c, clen, nlen, 0);
462 res = mprsa(nxl, nx, exl, ex, mx, cx);
471 const unsigned char *p, *q, *g, *y, *r, *s;
472 int plen, qlen, glen, ylen, rlen, slen, hlen;
473 mp_t *px, *qx, *gx, *yx, *rx, *sx, *hx;
478 p = findmpi(&mpi, &mpil, 8192, &plen);
479 q = findmpi(&mpi, &mpil, 1024, &qlen);
480 g = findmpi(&mpi, &mpil, plen, &glen);
481 y = findmpi(&mpi, &mpil, plen, &ylen);
482 mpi = sig + 2 + hashl;
483 mpil = sigl - (2 + hashl);
484 r = findmpi(&mpi, &mpil, qlen, &rlen);
485 s = findmpi(&mpi, &mpil, qlen, &slen);
486 if (!p || !q || !g || !y || !r || !s || !plen || !qlen)
488 hlen = (qlen + 7) & ~7;
489 if (hlen > hashl * 8)
491 px = mpbuild(p, plen, plen, &pxl);
492 qx = mpbuild(q, qlen, qlen, &qxl);
493 gx = mpbuild(g, glen, plen, 0);
494 yx = mpbuild(y, ylen, plen, 0);
495 rx = mpbuild(r, rlen, qlen, 0);
496 sx = mpbuild(s, slen, qlen, 0);
497 hx = mpbuild(sig + 2, hlen, hlen, &hxl);
498 res = mpdsa(pxl, px, qxl, qx, gx, yx, rx, sx, hxl, hx);
509 return 0; /* unsupported pubkey algo */