From: mdw Date: Sun, 9 Jul 2000 21:32:30 +0000 (+0000) Subject: Pollard's rho algorithm for computing discrete logs. X-Git-Url: https://git.distorted.org.uk/u/mdw/catacomb/commitdiff_plain/f41f820e4b3e230d9314cc4323abf59babdd4e67 Pollard's rho algorithm for computing discrete logs. --- diff --git a/rho.c b/rho.c new file mode 100644 index 0000000..d4530b8 --- /dev/null +++ b/rho.c @@ -0,0 +1,308 @@ +/* -*-c-*- + * + * $Id: rho.c,v 1.1 2000/07/09 21:32:30 mdw Exp $ + * + * Pollard's rho algorithm for discrete logs + * + * (c) 2000 Straylight/Edgeware + */ + +/*----- Licensing notice --------------------------------------------------* + * + * This file is part of Catacomb. + * + * Catacomb is free software; you can redistribute it and/or modify + * it under the terms of the GNU Library General Public License as + * published by the Free Software Foundation; either version 2 of the + * License, or (at your option) any later version. + * + * Catacomb is distributed in the hope that it will be useful, + * but WITHOUT ANY WARRANTY; without even the implied warranty of + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + * GNU Library General Public License for more details. + * + * You should have received a copy of the GNU Library General Public + * License along with Catacomb; if not, write to the Free + * Software Foundation, Inc., 59 Temple Place - Suite 330, Boston, + * MA 02111-1307, USA. + */ + +/*----- Revision history --------------------------------------------------* + * + * $Log: rho.c,v $ + * Revision 1.1 2000/07/09 21:32:30 mdw + * Pollard's rho algorithm for computing discrete logs. + * + */ + +/*----- Header files ------------------------------------------------------*/ + +#include "fibrand.h" +#include "mp.h" +#include "mpmont.h" +#include "mprand.h" +#include "rho.h" + +/*----- Main code ---------------------------------------------------------*/ + +/* --- @rho@ --- * + * + * Arguments: @rho_ctx *cc@ = pointer to the context structure + * @void *x, *y@ = two (equal) base values (try 1) + * @mp *a, *b@ = logs of %$x$% (see below) + * + * Returns: The discrete logarithm %$\log_g a$%, or null if the algorithm + * failed. (This is unlikely, though possible.) + * + * Use: Uses Pollard's rho algorithm to compute discrete logs in the + * group %$G$% generated by %$g$%. + * + * The algorithm works by finding a cycle in a pseudo-random + * walk. The function @ops->split@ should return an element + * from %$\{\,0, 1, 2\,\}$% according to its argument, in order + * to determine the walk. At each step in the walk, we know a + * group element %$x \in G$% together with its representation as + * a product of powers of %$g$% and $%a$% (i.e., we know that + * %$x = g^\alpha a^\beta$% for some %$\alpha$%, %$\beta$%). + * + * Locating a cycle gives us a collision + * + * %$g^{\alpha} a^{\beta} = g^{\alpha'} a^{\beta'}$% + * + * Taking logs of both sides (to base %$g$%) gives us that + * + * %$\log a\equiv\frac{\alpha-\alpha'}{\beta'-\beta}\bmod{n}$% + * + * Good initial values are %$x = y = 1$% (the multiplicative + * identity of %$G$%) and %$\alpha\equiv\beta\equiv0\bmod{n}$%. + * If that doesn't work then start choosing more `interesting' + * values. + * + * Note that the algorithm requires minimal space but + * %$O(\sqrt{n})$% time. Don't do this on large groups, + * particularly if you can find a decent factor base. + * + * Finally, note that this function will free the input values + * when it's finished with them. This probably isn't a great + * problem. + */ + +static void step(rho_ctx *cc, void *x, mp **a, mp **b) +{ + switch (cc->ops->split(x)) { + case 0: + cc->ops->mul(x, cc->g, cc->c); + *a = mp_add(*a, *a, MP_ONE); + if (MP_CMP(*a, >=, cc->n)) + *a = mp_sub(*a, *a, cc->n); + break; + case 1: + cc->ops->sqr(x, cc->c); + *a = mp_lsl(*a, *a, 1); + if (MP_CMP(*a, >=, cc->n)) + *a = mp_sub(*a, *a, cc->n); + *b = mp_lsl(*b, *b, 1); + if (MP_CMP(*b, >=, cc->n)) + *b = mp_sub(*b, *b, cc->n); + break; + case 2: + cc->ops->mul(x, cc->a, cc->c); + *b = mp_add(*b, *b, MP_ONE); + if (MP_CMP(*b, >=, cc->n)) + *b = mp_sub(*b, *b, cc->n); + break; + } +} + +mp *rho(rho_ctx *cc, void *x, void *y, mp *a, mp *b) +{ + mp *aa = MP_COPY(a), *bb = MP_COPY(b); + mp *g; + + /* --- Grind through the random walk until we find a collision --- */ + + do { + step(cc, x, &a, &b); + step(cc, y, &aa, &bb); + step(cc, y, &aa, &bb); + } while (!cc->ops->eq(x, y)); + cc->ops->drop(x); + cc->ops->drop(y); + + /* --- Now sort out the mess --- */ + + aa = mp_sub(aa, a, aa); + bb = mp_sub(bb, bb, b); + g = MP_NEW; + mp_gcd(&g, &bb, 0, bb, cc->n); + if (MP_CMP(g, !=, MP_ONE)) { + mp_drop(aa); + aa = 0; + } else { + aa = mp_mul(aa, aa, bb); + mp_div(0, &aa, aa, cc->n); + } + + /* --- Done --- */ + + mp_drop(bb); + mp_drop(g); + mp_drop(a); + mp_drop(b); + return (aa); +} + +/* --- @rho_prime@ --- * + * + * Arguments: @mp *g@ = generator for the group + * @mp *a@ = value to find the logarithm of + * @mp *n@ = order of the group + * @mp *p@ = prime size of the underlying prime field + * + * Returns: The discrete logarithm %$\log_g a$%. + * + * Use: Computes discrete logarithms in a subgroup of a prime field. + */ + +static void prime_sqr(void *x, void *c) +{ + mp **p = x; + mp *a = *p; + a = mp_sqr(a, a); + a = mpmont_reduce(c, a, a); + *p = a; +} + +static void prime_mul(void *x, void *y, void *c) +{ + mp **p = x; + mp *a = *p; + a = mpmont_mul(c, a, a, y); + *p = a; +} + +static int prime_eq(void *x, void *y) +{ + return (MP_CMP(*(mp **)x, ==, *(mp **)y)); +} + +static int prime_split(void *x) +{ + /* --- Notes on the splitting function --- * + * + * The objective is to produce a simple pseudorandom mapping from the + * underlying field \gf{p} to \{\,0, 1, 2\,\}$%. This is further + * constrained by the fact that we must not have %$1 \mapsto 1$% (since + * otherwise the stepping function above will loop). + * + * The function we choose is very simple: we take the least significant + * word from the integer, add one (to prevent the %$1 \mapsto 1$% property + * described above) and reduce modulo 3. This is slightly biased against + * the result 2, but this doesn't appear to be relevant. + */ + + return (((*(mp **)x)->v[0] + 1) % 3); +} + +static void prime_drop(void *x) +{ + MP_DROP(*(mp **)x); +} + +static rho_ops prime_ops = { + prime_sqr, prime_mul, prime_eq, prime_split, prime_drop +}; + +mp *rho_prime(mp *g, mp *a, mp *n, mp *p) +{ + rho_ctx cc; + grand *r = 0; + mpmont mm; + mp *x, *y; + mp *aa, *bb; + mp *l; + + /* --- Initialization --- */ + + mpmont_create(&mm, p); + cc.ops = &prime_ops; + cc.c = &mm; + cc.n = n; + cc.g = mpmont_mul(&mm, MP_NEW, g, mm.r2); + cc.a = mpmont_mul(&mm, MP_NEW, a, mm.r2); + x = MP_COPY(mm.r); + y = MP_COPY(x); + aa = bb = MP_ZERO; + + /* --- The main loop --- */ + + while ((l = rho(&cc, &x, &y, aa, bb)) == 0) { + mpmont_factor f[2]; + + if (!r) + r = fibrand_create(0); + aa = mprand_range(MP_NEW, n, r, 0); + bb = mprand_range(MP_NEW, n, r, 0); + f[0].base = g; f[0].exp = aa; + f[1].base = a; f[1].exp = bb; + x = mpmont_mexpr(&mm, MP_NEW, f, 2); + y = MP_COPY(x); + } + + /* --- Throw everything away now --- */ + + if (r) + r->ops->destroy(r); + mp_drop(cc.g); + mp_drop(cc.a); + mpmont_destroy(&mm); + return (l); +} + +/*----- Test rig ----------------------------------------------------------*/ + +#ifdef TEST_RIG + +#include + +#include "dh.h" + +int main(void) +{ + dh_param dp; + mp *x, *y; + grand *r = fibrand_create(0); + mpmont mm; + mp *l; + int ok; + + fputs("rho: ", stdout); + fflush(stdout); + + dh_gen(&dp, 32, 256, 0, r, pgen_evspin, 0); + x = mprand_range(MP_NEW, dp.q, r, 0); + mpmont_create(&mm, dp.p); + y = mpmont_exp(&mm, MP_NEW, dp.g, x); + mpmont_destroy(&mm); + l = rho_prime(dp.g, y, dp.q, dp.p); + if (MP_CMP(x, ==, l)) { + fputs(". ok\n", stdout); + ok = 1; + } else { + fputs("\n*** rho (discrete logs) failed\n", stdout); + ok = 0; + } + + mp_drop(l); + mp_drop(x); + mp_drop(y); + r->ops->destroy(r); + dh_paramfree(&dp); + assert(mparena_count(MPARENA_GLOBAL) == 0); + + return (ok ? 0 : EXIT_FAILURE); +} + +#endif + +/*----- That's all, folks -------------------------------------------------*/ diff --git a/rho.h b/rho.h new file mode 100644 index 0000000..6d060b0 --- /dev/null +++ b/rho.h @@ -0,0 +1,139 @@ +/* -*-c-*- + * + * $Id: rho.h,v 1.1 2000/07/09 21:32:30 mdw Exp $ + * + * Pollard's rho algorithm for discrete logs + * + * (c) 2000 Straylight/Edgeware + */ + +/*----- Licensing notice --------------------------------------------------* + * + * This file is part of Catacomb. + * + * Catacomb is free software; you can redistribute it and/or modify + * it under the terms of the GNU Library General Public License as + * published by the Free Software Foundation; either version 2 of the + * License, or (at your option) any later version. + * + * Catacomb is distributed in the hope that it will be useful, + * but WITHOUT ANY WARRANTY; without even the implied warranty of + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + * GNU Library General Public License for more details. + * + * You should have received a copy of the GNU Library General Public + * License along with Catacomb; if not, write to the Free + * Software Foundation, Inc., 59 Temple Place - Suite 330, Boston, + * MA 02111-1307, USA. + */ + +/*----- Revision history --------------------------------------------------* + * + * $Log: rho.h,v $ + * Revision 1.1 2000/07/09 21:32:30 mdw + * Pollard's rho algorithm for computing discrete logs. + * + */ + +#ifndef CATACOMB_RHO_H +#define CATACOMB_RHO_H + +#ifdef __cplusplus + extern "C" { +#endif + +/*----- Header files ------------------------------------------------------*/ + +#ifndef CATACOMB_MP_H +# include "mp.h" +#endif + +/*----- Data structures ---------------------------------------------------*/ + +/* --- The group operations table --- */ + +typedef struct rho_ops { + void (*sqr)(void *x, void *c); + void (*mul)(void *x, void *y, void *c); + int (*eq)(void *x, void *y); + int (*split)(void *x); + void (*drop)(void *x); +} rho_ops; + +/* --- The Pollard's rho context structure --- */ + +typedef struct rho_ctx { + rho_ops *ops; /* Group operations table */ + void *c; /* Context for group operations */ + void *g, *a; /* Generator and argument for log */ + mp *n; /* Cyclic group order */ +} rho_ctx; + +/*----- Functions provided ------------------------------------------------*/ + +/* --- @rho@ --- * + * + * Arguments: @rho_ctx *cc@ = pointer to the context structure + * @void *x, *y@ = two (equal) base values (try 1) + * @mp *a, *b@ = logs of %$x$% (see below) + * + * Returns: The discrete logarithm %$\log_g a$%, or null if the algorithm + * failed. (This is unlikely, though possible.) + * + * Use: Uses Pollard's rho algorithm to compute discrete logs in the + * group %$G$% generated by %$g$%. + * + * The algorithm works by finding a cycle in a pseudo-random + * walk. The function @ops->split@ should return an element + * from %$\{\,0, 1, 2\,\}$% according to its argument, in order + * to determine the walk. At each step in the walk, we know a + * group element %$x \in G$% together with its representation as + * a product of powers of %$g$% and $%a$% (i.e., we know that + * %$x = g^\alpha a^\beta$% for some %$\alpha$%, %$\beta$%). + * + * Locating a cycle gives us a collision + * + * %$g^{\alpha} a^{\beta} = g^{\alpha'} a^{\beta'}$% + * + * Taking logs of both sides (to base %$g$%) gives us that + * + * %$\log a\equiv\frac{\alpha-\alpha'}{\beta'-\beta}\bmod{n}$% + * + * Good initial values are %$x = y = 1$% (the multiplicative + * identity of %$G$%) and %$\alpha\equiv\beta\equiv0\bmod{n}$%. + * If that doesn't work then start choosing more `interesting' + * values. + * + * Note that the algorithm requires minimal space but + * %$O(\sqrt{n})$% time. Don't do this on large groups, + * particularly if you can find a decent factor base. + * + * Finally, note that this function will free the input values + * when it's finished with them. This probably isn't a great + * problem. + */ + +extern mp *rho(rho_ctx */*cc*/, void */*x*/, void */*y*/, + mp */*a*/, mp */*b*/); + +/* --- @rho_prime@ --- * + * + * Arguments: @mp *g@ = generator for the group + * @mp *a@ = value to find the logarithm of + * @mp *n@ = order of the group + * @mp *p@ = prime size of the underlying prime field + * + * Returns: The discrete logarithm %$\log_g a$%. + * + * Use: Computes discrete logarithms in a subgroup of a prime field. + */ + +extern mp *rho_prime(mp */*g*/, mp */*a*/, mp */*n*/, mp */*p*/); + +/*----- That's all, folks -------------------------------------------------*/ + +#ifdef __cplusplus + } +#endif + +#endif