Mailing List Archive: gnupg-1.0.6/mpi/mpi-inv.c

Hi.

I ported nine PRNGs to the GNU Scientific Library
(http://sources.redhat.com/gsl)

I studied (a very little part of) TAOCP, Volume II and I was looking for
a GPL implementation of the modular inverse function.

I found one on gnupg:
gnupg-1.0.6/mpi/mpi-inv.c

In this file I discovered you referred to TAOCP too:

(on line 80)
/* Extended Euclid's algorithm (See TAOPC Vol II, 4.5.2, Alg X)
* modified according to Michael Penk's solution for Exercice 35 */
$
/* FIXME: we can simplify this in most cases (see Knuth) */

by the way: two little typos
s/TAOPC/TAOCP
s/Exercice/Exercise

and
(on line 161)
/* Extended Euclid's algorithm (See TAOPC Vol II, 4.5.2, Alg X)
* modified according to Michael Penk's solution for Exercice 35
* with further enhancement */

same typos

I'd like to try GNUPG like a modular algebra library so I should pass to
mpi_invm three MPI.
I read include/mpi.h to find how MPI is made.
MPI is

struct gcry_mpi {
int alloced; /* array size (# of allocated limbs) */
int nlimbs; /* number of valid limbs */
int nbits; /* the real number of valid bits (info only) */
int sign; /* indicates a negative number */
unsigned flags; /* bit 0: array must be allocated in secure memory
space */
/* bit 1: the mpi is encrypted */
/* bit 2: the limb is a pointer to some m_alloced */
/* data */
mpi_limb_t *d; /* array with the limbs */
};

typedef struct gcry_mpi *MPI;

So to use it as an algebra library I should understand limbs (???) and
so on...

How to find that all? (I can continue reading the whole thing but...
it's not so fast)
I also started studing tools/mpicalc.c to understand how mpi_invm is
used but it's not so trivial because the mathematical part is merged
into cryptographic things...

I could try to "fix the FIXME :-P" in mpi-inv.c but first I should
investigate more your architecture... can you help me?

Thanks for your patience.

--
Carlo Perassi
http://www.linux.it/~carlo/

On Mon, 14 Jan 2002 15:26:39 +0100, Carlo Perassi said:

> by the way: two little typos
> s/TAOPC/TAOCP
> s/Exercice/Exercise

Thanks.

> How to find that all? (I can continue reading the whole thing
> but... it's not so fast)

You better don't look at libgcrypt but at the GMP. The code used in
libgcrypt is based on an old version of GMP and only slightly changed.
IIRC GMP has now a compile time flag to allow the use of malloc
instead of alloca which is one thing changed in libgcrypt. The other
thing is that we use 2 different allocation functions to be able to
distinguish between mubers which must be kept confidential and the
bulk of unconfidential numbers.

The GMP explains most things; a limb is just one word, to form a big
integer an array of these words called limbs is used.

Werner

--
Werner Koch Omnis enim res, quae dando non deficit, dum habetur
g10 Code GmbH et non datur, nondum habetur, quomodo habenda est.
Privacy Solutions -- Augustinus