Select Git revision
-
Fredrik Hübinette (Hubbe) authored
Rev: README:1.1 Rev: bin/create_testsuite:1.3 Rev: bin/hilfe.lpc:1.2 Rev: bin/rsif:1.2 Rev: bin/uhttpd.lpc:1.2 Rev: doc/simulated/open:1.1 Rev: lib/master.lpc:1.2 Rev: lib/simulate.lpc:1.4 Rev: lib/testsuite.lpc:1.3 Rev: src/BUGS:1.3 Rev: src/Makefile.in:1.6 Rev: src/Makefile.in.src:1.2 Rev: src/README:1.2 Rev: src/add_efun.c:1.2 Rev: src/add_efun.h:1.2 Rev: src/array.c:1.4 Rev: src/array.h:1.2 Rev: src/backend.c:1.3 Rev: src/backend.h:1.2 Rev: src/builtin_efuns.c:1.2 Rev: src/builtin_efuns.h:1.2 Rev: src/call_out.c:1.5 Rev: src/call_out.h:1.2 Rev: src/callback.c:1.2 Rev: src/callback.h:1.2 Rev: src/config.h:1.6 Rev: src/configure.in:1.9 Rev: src/debug.c:1.4 Rev: src/debug.h:1.4 Rev: src/docode.c:1.4 Rev: src/docode.h:1.2 Rev: src/dynamic_buffer.c:1.3 Rev: src/dynamic_buffer.h:1.2 Rev: src/efun.h:1.2 Rev: src/error.c:1.2 Rev: src/error.h:1.2 Rev: src/fd_control.c:1.2 Rev: src/fd_control.h:1.2 Rev: src/fsort.c:1.2 Rev: src/fsort.h:1.2 Rev: src/global.h:1.2 Rev: src/hashtable.c:1.2 Rev: src/hashtable.h:1.2 Rev: src/interpret.c:1.5 Rev: src/interpret.h:1.2 Rev: src/language.y:1.3 Rev: src/las.c:1.3 Rev: src/las.h:1.3 Rev: src/lex.c:1.3 Rev: src/lex.h:1.2 Rev: src/list.c:1.3 Rev: src/list.h:1.2 Rev: src/lpc_signal.c:1.1 Rev: src/lpc_signal.h:1.1 Rev: src/lpc_types.c:1.3 Rev: src/lpc_types.h:1.2 Rev: src/machine.h.in:1.3 Rev: src/macros.h:1.4 Rev: src/main.c:1.8 Rev: src/main.h:1.2 Rev: src/mapping.c:1.4 Rev: src/mapping.h:1.2 Rev: src/memory.c:1.3 Rev: src/memory.h:1.2 Rev: src/module.c:1.2 Rev: src/module.h:1.2 Rev: src/modules/files/Makefile.in:1.3 Rev: src/modules/files/Makefile.in.src:1.2 Rev: src/modules/files/configure.in:1.5 Rev: src/modules/files/datagram.c:1.2 Rev: src/modules/files/efuns.c:1.4 Rev: src/modules/files/file.c:1.5 Rev: src/modules/files/file.h:1.3 Rev: src/modules/files/file_machine.h.in:1.3 Rev: src/modules/files/socket.c:1.6 Rev: src/modules/math/Makefile.in:1.4 Rev: src/modules/math/Makefile.in.src:1.3 Rev: src/modules/math/math.c:1.2 Rev: src/modules/regexp/Makefile.in:1.3 Rev: src/modules/regexp/Makefile.in.src:1.2 Rev: src/modules/regexp/glue.c:1.2 Rev: src/modules/regexp/regexp.h:1.2 Rev: src/modules/sprintf/Makefile.in:1.3 Rev: src/modules/sprintf/Makefile.in.src:1.2 Rev: src/modules/sprintf/sprintf.c:1.2 Rev: src/object.c:1.3 Rev: src/object.h:1.2 Rev: src/opcodes.c:1.6 Rev: src/opcodes.h:1.2 Rev: src/operators.c:1.3 Rev: src/operators.h:1.2 Rev: src/otable.h:1.2 Rev: src/port.c:1.9 Rev: src/port.h:1.4 Rev: src/program.h:1.2 Rev: src/rusage.c:1.3 Rev: src/rusage.h:1.2 Rev: src/stralloc.c:1.3 Rev: src/stralloc.h:1.3 Rev: src/stuff.c:1.2 Rev: src/stuff.h:1.2 Rev: src/svalue.c:1.4 Rev: src/svalue.h:1.2 Rev: src/todo:1.2 Rev: src/types.h:1.6 Rev: src/ualarm.c:1.2
Fredrik Hübinette (Hubbe) authoredRev: README:1.1 Rev: bin/create_testsuite:1.3 Rev: bin/hilfe.lpc:1.2 Rev: bin/rsif:1.2 Rev: bin/uhttpd.lpc:1.2 Rev: doc/simulated/open:1.1 Rev: lib/master.lpc:1.2 Rev: lib/simulate.lpc:1.4 Rev: lib/testsuite.lpc:1.3 Rev: src/BUGS:1.3 Rev: src/Makefile.in:1.6 Rev: src/Makefile.in.src:1.2 Rev: src/README:1.2 Rev: src/add_efun.c:1.2 Rev: src/add_efun.h:1.2 Rev: src/array.c:1.4 Rev: src/array.h:1.2 Rev: src/backend.c:1.3 Rev: src/backend.h:1.2 Rev: src/builtin_efuns.c:1.2 Rev: src/builtin_efuns.h:1.2 Rev: src/call_out.c:1.5 Rev: src/call_out.h:1.2 Rev: src/callback.c:1.2 Rev: src/callback.h:1.2 Rev: src/config.h:1.6 Rev: src/configure.in:1.9 Rev: src/debug.c:1.4 Rev: src/debug.h:1.4 Rev: src/docode.c:1.4 Rev: src/docode.h:1.2 Rev: src/dynamic_buffer.c:1.3 Rev: src/dynamic_buffer.h:1.2 Rev: src/efun.h:1.2 Rev: src/error.c:1.2 Rev: src/error.h:1.2 Rev: src/fd_control.c:1.2 Rev: src/fd_control.h:1.2 Rev: src/fsort.c:1.2 Rev: src/fsort.h:1.2 Rev: src/global.h:1.2 Rev: src/hashtable.c:1.2 Rev: src/hashtable.h:1.2 Rev: src/interpret.c:1.5 Rev: src/interpret.h:1.2 Rev: src/language.y:1.3 Rev: src/las.c:1.3 Rev: src/las.h:1.3 Rev: src/lex.c:1.3 Rev: src/lex.h:1.2 Rev: src/list.c:1.3 Rev: src/list.h:1.2 Rev: src/lpc_signal.c:1.1 Rev: src/lpc_signal.h:1.1 Rev: src/lpc_types.c:1.3 Rev: src/lpc_types.h:1.2 Rev: src/machine.h.in:1.3 Rev: src/macros.h:1.4 Rev: src/main.c:1.8 Rev: src/main.h:1.2 Rev: src/mapping.c:1.4 Rev: src/mapping.h:1.2 Rev: src/memory.c:1.3 Rev: src/memory.h:1.2 Rev: src/module.c:1.2 Rev: src/module.h:1.2 Rev: src/modules/files/Makefile.in:1.3 Rev: src/modules/files/Makefile.in.src:1.2 Rev: src/modules/files/configure.in:1.5 Rev: src/modules/files/datagram.c:1.2 Rev: src/modules/files/efuns.c:1.4 Rev: src/modules/files/file.c:1.5 Rev: src/modules/files/file.h:1.3 Rev: src/modules/files/file_machine.h.in:1.3 Rev: src/modules/files/socket.c:1.6 Rev: src/modules/math/Makefile.in:1.4 Rev: src/modules/math/Makefile.in.src:1.3 Rev: src/modules/math/math.c:1.2 Rev: src/modules/regexp/Makefile.in:1.3 Rev: src/modules/regexp/Makefile.in.src:1.2 Rev: src/modules/regexp/glue.c:1.2 Rev: src/modules/regexp/regexp.h:1.2 Rev: src/modules/sprintf/Makefile.in:1.3 Rev: src/modules/sprintf/Makefile.in.src:1.2 Rev: src/modules/sprintf/sprintf.c:1.2 Rev: src/object.c:1.3 Rev: src/object.h:1.2 Rev: src/opcodes.c:1.6 Rev: src/opcodes.h:1.2 Rev: src/operators.c:1.3 Rev: src/operators.h:1.2 Rev: src/otable.h:1.2 Rev: src/port.c:1.9 Rev: src/port.h:1.4 Rev: src/program.h:1.2 Rev: src/rusage.c:1.3 Rev: src/rusage.h:1.2 Rev: src/stralloc.c:1.3 Rev: src/stralloc.h:1.3 Rev: src/stuff.c:1.2 Rev: src/stuff.h:1.2 Rev: src/svalue.c:1.4 Rev: src/svalue.h:1.2 Rev: src/todo:1.2 Rev: src/types.h:1.6 Rev: src/ualarm.c:1.2
rsa.c 4.27 KiB
/* rsa.c
*
* The RSA publickey algorithm.
*/
/* nettle, low-level cryptographics library
*
* Copyright (C) 2001 Niels Mller
*
* The nettle library is free software; you can redistribute it and/or modify
* it under the terms of the GNU Lesser General Public License as published by
* the Free Software Foundation; either version 2.1 of the License, or (at your
* option) any later version.
*
* The nettle library 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 Lesser General Public
* License for more details.
*
* You should have received a copy of the GNU Lesser General Public License
* along with the nettle library; see the file COPYING.LIB. If not, write to
* the Free Software Foundation, Inc., 59 Temple Place - Suite 330, Boston,
* MA 02111-1307, USA.
*/
#if HAVE_CONFIG_H
#include "config.h"
#endif
#if HAVE_LIBGMP
#include "rsa.h"
#include "bignum.h"
/* FIXME: Perhaps we should split this into several functions, so that
* one can link in the signature functions without also getting the
* verify functions. */
void
rsa_init_public_key(struct rsa_public_key *key)
{
mpz_init(key->n);
mpz_init(key->e);
/* Not really necessary, but it seems cleaner to initialize all the
* storage. */
key->size = 0;
}
void
rsa_clear_public_key(struct rsa_public_key *key)
{
mpz_clear(key->n);
mpz_clear(key->e);
}
/* Computes the size, in octets, of a size BITS modulo.
* Returns 0 if the modulo is too small to be useful. */
static unsigned
rsa_check_size(mpz_t n)
{
/* Round upwards */
unsigned size = (mpz_sizeinbase(n, 2) + 7) / 8;
if (size < RSA_MINIMUM_N_OCTETS)
return 0;
return size;}
int
rsa_prepare_public_key(struct rsa_public_key *key)
{
/* FIXME: Add further sanity checks, like 0 < e < n. */
#if 0
if ( (mpz_sgn(key->e) <= 0)
|| mpz_cmp(key->e, key->n) >= 0)
return 0;
#endif
key->size = rsa_check_size(key->n);
return (key->size > 0);
}
void
rsa_init_private_key(struct rsa_private_key *key)
{
mpz_init(key->d);
mpz_init(key->p);
mpz_init(key->q);
mpz_init(key->a);
mpz_init(key->b);
mpz_init(key->c);
/* Not really necessary, but it seems cleaner to initialize all the
* storage. */
key->size = 0;
}
void
rsa_clear_private_key(struct rsa_private_key *key)
{
mpz_clear(key->d);
mpz_clear(key->p);
mpz_clear(key->q);
mpz_clear(key->a);
mpz_clear(key->b);
mpz_clear(key->c);
}
int
rsa_prepare_private_key(struct rsa_private_key *key)
{
/* FIXME: Add further sanity checks. */
mpz_t n;
/* The size of the product is the sum of the sizes of the factors,
* or sometimes one less. It's possible but tricky to compute the
* size without computing the full product. */
mpz_init(n);
mpz_mul(n, key->p, key->q);
key->size = rsa_check_size(n);
mpz_clear(n);
return (key->size > 0);
}
/* Computing an rsa root. */
void
rsa_compute_root(struct rsa_private_key *key, mpz_t x, const mpz_t m)
{
mpz_t xp; /* modulo p */
mpz_t xq; /* modulo q */
mpz_init(xp); mpz_init(xq);
/* Compute xq = m^d % q = (m%q)^b % q */
mpz_fdiv_r(xq, m, key->q);
mpz_powm(xq, xq, key->b, key->q);
/* Compute xp = m^d % p = (m%p)^a % p */
mpz_fdiv_r(xp, m, key->p);
mpz_powm(xp, xp, key->a, key->p);
/* Set xp' = (xp - xq) c % p. */
mpz_sub(xp, xp, xq);
mpz_mul(xp, xp, key->c);
mpz_fdiv_r(xp, xp, key->p);
/* Finally, compute x = xq + q xp'
*
* To prove that this works, note that
*
* xp = x + i p,
* xq = x + j q,
* c q = 1 + k p
*
* for some integers i, j and k. Now, for some integer l,
*
* xp' = (xp - xq) c + l p
* = (x + i p - (x + j q)) c + l p
* = (i p - j q) c + l p
* = (i c + l) p - j (c q)
* = (i c + l) p - j (1 + kp)
* = (i c + l - j k) p - j
*
* which shows that xp' = -j (mod p). We get
*
* xq + q xp' = x + j q + (i c + l - j k) p q - j q
* = x + (i c + l - j k) p q
*
* so that
*
* xq + q xp' = x (mod pq)
*
* We also get 0 <= xq + q xp' < p q, because
*
* 0 <= xq < q and 0 <= xp' < p.
*/
mpz_mul(x, key->q, xp);
mpz_add(x, x, xq);
mpz_clear(xp); mpz_clear(xq);
}
#endif /* HAVE_LIBGMP */