CHALLENGE response

[Anonymous]

> What form are your primes (did you use Maurers idea to increase the
> relative hardness of factoring compared to discrete log, or did you
> just use more smaller primes?)  How many primes have you used, and how
> many CPU hours did it take to calculate the discrete log to discover e?

N is the product of two primes, but each p-1 has about 16 small prime factors
(about 25-35 bits) to allow calculating the discrete log efficiently.  With
this choice of primes it took about three hours to run the discrete log.

> Also is the code for finding discrete logs given the prime
> factorisation of the modulus available?

Here you go.  This uses cryptolib by Jack Lacy of AT&T (not to be
confused with cryptlib by Peter Gutmann), available from
ftp://ftp.funet.fi/pub/crypt/cryptography/libs/cryptolib_1.1.tar.gz


/* Calculate discrete log using various algorithms */
/* Algorithms based on Handbook of Applied Cryptography by Menezes et al */

#include "libcrypt.h"


/* Modular multiplication - m1*m2 mod n */
static void
bigMultiplyN (BigInt m1, BigInt m2, BigInt n, BigInt result)
{
    BigInt tmp = bigInit(0);
    bigMultiply (m1, m2, tmp);
    bigMod (tmp, n, result);
    freeBignum (tmp);
}


/* Modular addition, m1+m2 mod n */
static void
bigAddN (BigInt m1, BigInt m2, BigInt n, BigInt result)
{
    bigAdd (m1, m2, result);
    if (bigCompare (result, n) >= 0)
        bigSubtract (result, n, result);
}


/* Iterate the pollard rho.  Modify x, a, b with next values */
static void
prhoiter (BigInt base, BigInt val, BigInt mod, BigInt order,
    BigInt *x, BigInt *a, BigInt *b)
{
    int xgroup;

    /* First decide what group x is in */
    /* This is a cheat to be fast */
    xgroup = ((unsigned)(*x)->num[0]+1) % 3;

    switch (xgroup) {
    case 0:
        bigMultiplyN (*x, val, mod, *x);
        bigAddN (*b, one, order, *b);
        break;
    case 1:
        bigMultiplyN (*x, *x, mod, *x);
        bigAddN (*a, *a, order, *a);
        bigAddN (*b, *b, order, *b);
        break;
    case 2:
        bigMultiplyN (*x, base, mod, *x);
        bigAddN (*a, one, order, *a);
        break;
    }
}


/* Pollard rho algorithm for discrete log */

BigInt
pollardrho (BigInt base, BigInt val, BigInt mod, BigInt order)
{
    BigInt
        x = bigInit(1),
        a = bigInit(0),
        b = bigInit(0),
        x2 = bigInit(1),
        a2 = bigInit(0),
        b2 = bigInit(0);
    int cnt = 0;

    for ( ; ; ) {
        prhoiter (base, val, mod, order, &x, &a, &b);
        prhoiter (base, val, mod, order, &x2, &a2, &b2);
        prhoiter (base, val, mod, order, &x2, &a2, &b2);
        if (bigCompare (x, x2) == 0)
            break;
        if (++cnt % 1000 == 0) {
            printf ("%d\r", cnt);
            fflush (stdout);
        }
    }
    if (cnt >= 1000)
        printf ("\n");

    if (bigCompare (b, b2) < 0)
        bigAdd (order, b, b);
    bigSubtract (b, b2, b);
    if (bigCompare (a2, a) < 0)
        bigAdd (order, a2, a2);
    bigSubtract (a2, a, a);
        
    if (bigCompare (b, zero) == 0) {
        printf ("Pollard rho failed\n");
        exit (1);
    }
    getInverse (b, order, b2);
    bigMultiplyN (a, b2, order, a);
    return a;
}


/*
 * Do the CRT with multiple congruences.  congs are the values that the
 * answer should be congruent to, mods are the moduli for each congruence.
 * n tells how many in each array.
 */
static BigInt
crtmult (BigInt congs[], BigInt mods[], int n)
{
    int i;
    BigInt prod = bigInit(0);
    BigInt prod1 = bigInit(0);
    BigInt sum = bigInit(0);
    BigInt quot = bigInit(0);
    BigInt rem = bigInit(0);
    BigInt dum = bigInit(0);
    BigInt inv = bigInit(0);
    BigInt term = bigInit(0);

    /* Compute product of moduli */
    bigCopy (one, prod);
    for (i=0; i<n; ++i) {
        bigMultiply (prod, mods[i], prod1);
        bigCopy (prod1, prod);
    }

    for (i=0; i<n; ++i) {
        bigDivide (prod, mods[i], quot, dum);
        bigDivide (quot, mods[i], dum, rem);
        getInverse (rem, mods[i], inv);
        bigMultiplyN (congs[i], quot, prod, term);
        bigMultiplyN (term, inv, prod, term);
        bigAddN (term, sum, prod, sum);
    }

    return sum;
}


/* Pohlig-Hellman discrete log algorithm for composites */
/* Return the exponent such that base^exponent == val modulo mod. */
/* Group order is product of factors[], of which there are n */
/* Assume each factor is to the first power */

BigInt
phlog (BigInt base, BigInt val, BigInt mod, BigInt factors[], int n)
{
    BigInt
        prod = bigInit(0),
        prod1 = bigInit(0),
        exp = bigInit(0),
        dum = bigInit(0),
        b = bigInit(0),
        v = bigInit(0);
    BigInt *dlogs;
    BigInt dl;
    int i;

    dlogs = (BigInt *) malloc (n * sizeof (BigInt));

    /* Compute product of factors to get group order */
    bigCopy (one, prod);
    for (i=0; i<n; ++i) {
        bigMultiply (prod, factors[i], prod1);
        bigCopy (prod1, prod);
    }

    /* Sanity check */
    bigPow (base, prod, mod, b);
    if (bigCompare (b, one) != 0) {
        printf ("Inconsistency in group order on b\n");
        fBigPrint (b, stdout);
    }
    bigPow (val, prod, mod, v);
    if (bigCompare (v, one) != 0) {
        printf ("Inconsistency in group order on v\n");
        fBigPrint (v, stdout);
    }

    for (i=0; i<n; ++i) {
        bigDivide (prod, factors[i], exp, dum);
        bigPow (base, exp, mod, b);
        bigPow (val, exp, mod, v);

        printf ("Trying dlog with factor: "); fBigPrint (factors[i], stdout);
        printf ("b: "); fBigPrint (b, stdout);
        printf ("v: "); fBigPrint (v, stdout);

        /* Special case for 2, pollardrho doesn't work too well on it */
        if (bigCompare (factors[i], two) == 0) {
            if (bigCompare (b, v) == 0) {
                dlogs[i] = bigInit(1);
            } else if (bigCompare (v, one) == 0) {
                dlogs[i] = bigInit(0);
            } else {
                printf ("Inconsistent b, v for factor == 2\n");
                exit (1);
            }
        } else {
            /* Now find log of v mod b, has group order factors[i] */
            dlogs[i] = pollardrho (b, v, mod, factors[i]);
        }
        printf ("dl: "); fBigPrint (dlogs[i], stdout);
        bigPow (b, dlogs[i], mod, b);
        if (bigCompare (b, v) != 0) {
            printf ("Error in discrete log calc!\n");
            exit (1);
        }
    }

    /* Combine results with CRT */
    dl = crtmult (dlogs, factors, n);

    return dl;
}