[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
Re: CHALLENGE response
- To: [email protected]
- Subject: Re: CHALLENGE response
- From: Anonymous <[email protected]>
- Date: Wed, 23 Sep 1998 03:00:57 +0200
- Comments: This message did not originate from the Sender address above.It was remailed automatically by anonymizing remailer software.Please report problems or inappropriate use to theremailer administrator at <[email protected]>.
- Sender: [email protected]
> 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;
}