rsa_1.txt

rsa加密算法源程序

X*******************************************************************************/
X
X#include	<stdio.h>
X
X#include	"arith.h"
X#include	"prim.h"
X#include	"nio.h"
X#include	"rnd.h"
X
Xchar *prog;
X
XNUMBER a_three,a_four;
X
Xusage()
X{
X	fprintf(stderr,"usage: %s digits [probability]\n",prog);
X	exit (1);
X}
X
Xmain( argc, argv )
Xchar **argv;
X{
X	NUMBER prim;
X	int len,i,prob;
X	
X	prog = argv[0];	
X	
X	if ( argc < 2 || 3 < argc )
X		usage();
X	
X	len = atoi( argv[1] );
X	if (argc > 2)
X		prob = atoi( argv[2] );
X	else
X		prob = 10;
X
X	a_add( &a_one, &a_two, &a_three );
X	a_add( &a_two, &a_two, &a_four );
X
X	init_rnd();
X	
X	do {
X		gen_number( len, &prim );
X	} while ( !prim.n_len );
X	
X	a_mult( &prim, &a_two, &prim );
X	a_mult( &prim, &a_three, &prim );
X	a_add( &prim, &a_one, &prim );
X	
X	for (i=1 ;; i++) {
X		if (p_prim( &prim, prob ))
X			break;
X		if (i % 2)
X			a_add( &prim, &a_four, &prim );
X		else
X			a_add( &prim, &a_two, &prim );
X	}
X	fprintf(stderr,"%d cycles\n",i);
X	
X	num_fput( &prim, stdout );
X}
SHAR_EOF
if test 1416 -ne "`wc -c < 'genprim.c'`"
then
	echo shar: "error transmitting 'genprim.c'" '(should have been 1416 characters)'
fi
fi
echo shar: "extracting 'genrsa.c'" '(1458 characters)'
if test -f 'genrsa.c'
then
	echo shar: "will not over-write existing file 'genrsa.c'"
else
sed 's/^X//' << \SHAR_EOF > 'genrsa.c'
X/*******************************************************************************
X*									       *
X*	Copyright (c) Martin Nicolay,  22. Nov. 1988			       *
X*									       *
X*	Wenn diese (oder sinngemaess uebersetzte) Copyright-Angabe enthalten   *
X*	bleibt, darf diese Source fuer jeden nichtkomerziellen Zweck weiter    *
X*	verwendet werden.						       *
X*									       *
X*	[e-mail]					       *
X*									       *
X*******************************************************************************/
X
X#include	<stdio.h>
X
X#include	"arith.h"
X#include	"nio.h"
X#include	"prim.h"
X#include	"rnd.h"
X
Xmain()
X{
X	NUMBER p1,p2,n,d,e,phi,*max_p;
X	int len;
X	
X	num_fget( &p1, stdin ); getchar();
X	num_fget( &p2, stdin );
X	
X	if ( !a_cmp( &p1, &p2 ) ) {
X		fprintf(stderr,"the prime numbers must not be identical!\n");
X		exit(1);
X	}
X	
X	if (a_cmp( &p1, &p2 ) > 0)
X		max_p = &p1;
X	else
X		max_p = &p2;
X
X	a_mult( &p1, &p2, &n );
X	num_fput( &n, stdout ); puts("#"); fflush(stdout);
X	
X	a_sub( &p1, &a_one, &phi );
X	a_sub( &p2, &a_one, &e );
X	a_mult( &phi, &e, &phi );
X	
X	len = n_bitlen( &phi );
X	len = ( len + 3 ) / 4;
X	
X	a_assign( &p1, &phi );
X	a_sub( &p1, &a_one, &p1 );
X	init_rnd();
X	do {
X		do {
X			gen_number( len, &d );
X		} while (a_cmp( &d, max_p ) <= 0 || a_cmp( &d, &p1 ) >= 0);
X				
X		a_ggt( &d, &phi, &e );
X	} while ( a_cmp( &e, &a_one ) );
X	
X	num_fput( &d, stdout ); puts("#"); fflush(stdout);
X	
X	inv( &d, &phi, &e );
X	
X	num_fput( &e, stdout );
X}
X
SHAR_EOF
if test 1458 -ne "`wc -c < 'genrsa.c'`"
then
	echo shar: "error transmitting 'genrsa.c'" '(should have been 1458 characters)'
fi
fi
echo shar: "extracting 'nio.c'" '(4300 characters)'
if test -f 'nio.c'
then
	echo shar: "will not over-write existing file 'nio.c'"
else
sed 's/^X//' << \SHAR_EOF > 'nio.c'
X/*******************************************************************************
X*									       *
X*	Copyright (c) Martin Nicolay,  22. Nov. 1988			       *
X*									       *
X*	Wenn diese (oder sinngemaess uebersetzte) Copyright-Angabe enthalten   *
X*	bleibt, darf diese Source fuer jeden nichtkomerziellen Zweck weiter    *
X*	verwendet werden.						       *
X*									       *
X*	[e-mail]					       *
X*									       *
X*******************************************************************************/
X
X#include	<stdio.h>
X#include	<ctype.h>
X#include	<string.h>
X
X#include	"nio.h"
X
X/*
X *	NUMBER io
X */
X
X/*
X *		Funktionen
X *
X * int	num_sput( n, s, l)
X *		NUMBER *n;
X *		char s[l];
X *			schreibt *n als Hex-Zahl in s
X *
X * int	num_fput( n, f )
X *		NUMBER *n;
X *		FILE *f;
X *			schreibt *n als Hex-Zahl in File f
X *
X * int	num_sget( n, s )
X *		NUMBER *n;
X *		char *s;
X *			liest Hex-Zahl s in *n ein
X *
X * int	num_fget( n, f )
X *		NUMBER *n;
X *		FILE *f;
X *			liest eine Hex-Zahl von f in *n ein
X *
X */
X
X
Xstatic char *HEX="0123456789ABCDEF";
Xstatic char *hex="0123456789abcdef";
X
Xstatic NUMBER bits[9];
Xstatic NUMBER int16[16];
X
Xstatic int init = 0;
X
Xstatic num_init()
X{
X	int i;
X	
X	a_assign( &bits[0], &a_one );
X	for ( i=1; i<9; i++)
X		a_add( &bits[i-1], &bits[i-1], &bits[i] );
X
X	a_assign( &int16[0], &a_one );
X	for ( i=1; i<16; i++)
X		a_add( &int16[i-1], &a_one, &int16[i] );
X	
X	init = 1;
X}
X
X
Xint num_sput( n, s, l)
XNUMBER *n;
Xchar *s;
X{
X#if MAXINT == ( (1 << MAXBIT) - 1 )
X	INT *p;
X	int bi,ab,i;
X	long b;
X	int first = 1;
X	
X	bi = MAXBIT * n->n_len;
X	ab = 4 - (bi + 3) % 4 -1;
X	p  = &n->n_part[n->n_len -1];
X
X	if ( (bi+3) / 4 >= l )
X		return(EOF);
X	
X	b  = 0;
X	while (bi) {
X		b <<= (MAXBIT);
X		b |= (unsigned long)*p--;
X		bi -= MAXBIT;
X		ab += MAXBIT;
X		while (ab >= 4) {
X			i = (b >> (ab - 4));
X			b &= ( 1L << (ab - 4) ) -1L;
X			ab -= 4;
X
X			if (first && !i)
X				continue;
X			first = 0;
X			*s++ = HEX[ i ];
X		}
X	}
X	if (b)
X		abort();
X	*s = '\0';
X
X	return (0);
X#else			
X	NUMBER r,q;
X	int i,b,p,len,low,high;
X	char *np;
X	
X	if (! init)
X		num_init();
X	
X	a_assign( &q, n);
X	len = l;
X	np = s + l;
X
X	for (; q.n_len && len > 1; len --) {
X		a_div( &q, &bits[4], &q, &r );
X		for (p=8, b=0, i=3; i >= 0; i--, p /= 2 ) {
X			if ( a_cmp( &r, &bits[i] ) >= 0 ) {
X				a_sub( &r, &bits[i], &r );
X				b += p;
X			}
X		}
X		*--np = HEX[ b ];
X	}
X	if (q.n_len)
X		return(EOF);
X
X	l -= len;
X	len = l;
X	for (; l--; )
X		*s++ = *np++;
X	
X	*s = '\0';
X
X	return (0);
X#endif
X}
X
X
Xint num_fput( n, f )
XNUMBER *n;
XFILE *f;
X{
X	int j;
X	char *np;
X	unsigned char n_print[ STRLEN + 1 ];
X	
X	if ( num_sput( n, n_print, sizeof( n_print ) ) == EOF )
X		return(EOF);
X	
X	for (j=0, np=n_print; *np ; np++, j++ ) {
X		if (j==64) {
X			fputs("\n",f);
X			j = 0;
X		}
X		putc((int)*np,f);
X	}
X
X	if (j)
X		putc('\n',f);
X
X	return(0);
X}
X
X
Xint num_sget( n, s )
XNUMBER *n;
Xchar *s;
X{
X#if MAXINT == ( (1 << MAXBIT) - 1 )
X	INT *p;
X	char *hp;
X	int bi,ab,i;
X	long b;
X	int first = 1;
X	
X	bi = 4 * strlen(s);
X	ab = MAXBIT - (bi + MAXBIT -1) % MAXBIT -1;
X	i  =  (bi + MAXBIT-1) / MAXBIT;
X	p  = &n->n_part[ i -1 ];
X	n->n_len = i;
X
X	if ( i > MAXLEN )
X		return(EOF);
X	
X	b  = 0;
X	while (bi > 0) {
X		if ( hp= strchr( HEX, *s ) )
X			i = hp - HEX;
X		else if ( hp= strchr( hex, *s ) )
X			i = hp - hex;
X		else
X			return(EOF);
X		s++;
X		
X		b <<= 4;
X		b |= (unsigned long)i;
X		bi -= 4;
X		ab += 4;
X		while (ab >= MAXBIT) {
X			i = (b >> (ab - MAXBIT));
X			b &= ( 1L << (ab - MAXBIT) ) -1L;
X			ab -= MAXBIT;
X			if (first && !i) {
X				p--;
X				n->n_len--;
X			}
X			else {
X				first = 0;
X				*p-- = i;
X			}
X		}
X	}
X	if (b)
X		abort();
X	*s = '\0';
X
X	return (0);
X#else			
X	char *p;
X	int i,c;
X
X	if (! init)
X		num_init();
X	
X	n->n_len = 0;
X	while ( (c = *s++ & 0xFF) ) {
X		if ( p= strchr( HEX, c ) )
X			i = p - HEX;
X		else if ( p= strchr( hex, c ) )
X			i = p - hex;
X		else
X			return(EOF);
X		
X		a_mult( n, &bits[4], n );
X		if (i)
X			a_add( n, &int16[i-1], n );
X	}
X	
X	return(0);
X#endif
X}
X
Xint num_fget( n, f )
XNUMBER *n;
XFILE *f;
X{
X	int j,c;
X	char *np;
X	char n_print[ STRLEN + 1 ];
X
X	np = n_print;
X	j = sizeof(n_print);
X	while ( (c=getc(f)) != EOF && ( isxdigit(c) || isspace(c) ) ) {
X		if (isspace(c))
X			continue;
X		if (! --j)
X			return(EOF);
X		*np++ = (char)c;
X	}
X	*np = '\0';
X
X	if (c != EOF)
X		ungetc(c,f);
X	
X	if ( num_sget( n, n_print ) == EOF )
X		return( EOF );
X	
X	return(0);
X}
X
SHAR_EOF
if test 4300 -ne "`wc -c < 'nio.c'`"
then
	echo shar: "error transmitting 'nio.c'" '(should have been 4300 characters)'
fi
fi
echo shar: "extracting 'nio.h'" '(780 characters)'
if test -f 'nio.h'
then
	echo shar: "will not over-write existing file 'nio.h'"
else
sed 's/^X//' << \SHAR_EOF > 'nio.h'
X/*******************************************************************************
X*									       *
X*	Copyright (c) Martin Nicolay,  22. Nov. 1988			       *
X*									       *
X*	Wenn diese (oder sinngemaess uebersetzte) Copyright-Angabe enthalten   *
X*	bleibt, darf diese Source fuer jeden nichtkomerziellen Zweck weiter    *
X*	verwendet werden.						       *
X*									       *
X*	[e-mail]					       *
X*									       *
X*******************************************************************************/
X
X#ifndef	_nio_h_
X#define	_nio_h_
X
X#ifndef _arith_h_
X#include	"arith.h"
X#endif
X
X/*
X * Prototypes
X */
X
Xint	num_sput	P(( NUMBER*, char*, int ));
Xint	num_fput	P(( NUMBER*, FILE* ));
Xint	num_sget	P(( NUMBER*, char* ));
Xint	num_fget	P(( NUMBER*, FILE* ));
X
X#endif
SHAR_EOF
if test 780 -ne "`wc -c < 'nio.h'`"
then
	echo shar: "error transmitting 'nio.h'" '(should have been 780 characters)'
fi
fi
echo shar: "extracting 'prim.c'" '(4771 characters)'
if test -f 'prim.c'
then
	echo shar: "will not over-write existing file 'prim.c'"
else
sed 's/^X//' << \SHAR_EOF > 'prim.c'
X/*******************************************************************************
X*									       *
X*	Copyright (c) Martin Nicolay,  22. Nov. 1988			       *
X*									       *
X*	Wenn diese (oder sinngemaess uebersetzte) Copyright-Angabe enthalten   *
X*	bleibt, darf diese Source fuer jeden nichtkomerziellen Zweck weiter    *
X*	verwendet werden.						       *
X*									       *
X*	[e-mail]					       *
X*									       *
X*******************************************************************************/
X
X#include	"prim.h"
X
X/*
X *		RSA
X *
X *	p,q prim
X *	p != q
X *	n = p*q
X *	phi = (p -1)*(q -1)
X *	e,d aus 0...n-1
X *	e*d == 1 mod phi
X *
X *	m aus 0...n-1 sei eine Nachricht
X *
X *	Verschluesseln:
X *		E(x) = x^e mod n		( n,e oeffendlich )
X *
X *	Entschluesseln:
X *		D(x) = x^d mod n		( d geheim )
X *
X *
X *	Sicherheit:
X *
X *		p,q sollten bei mind. 10^100 liegen.
X *		(d,phi) == 1, das gilt fuer alle Primzahlen > max(p,q).
X *		Allerdings sollte d moeglichst gross sein ( d < phi-1 )
X *		um direktes Suchen zu verhindern.
X */
X
X
X/*
X *		FUNKTIONEN um RSA Schluessel zu generieren.
X *
X * int	p_prim( n, m )
X *		NUMBER *n;
X *		int m;
X *			0 : n ist nicht prim
X *			1 : n ist mit Wahrscheinlichkeit (1-1/2^m) prim
X *		ACHTUNG !!!!
X *		p_prim benutzt m_init
X *
X *	inv( d, phi, e )
X *		NUMBER *d,*phi,*e;
X *			*e = *d^-1 (mod phi)
X *		ACHTUNG !!!!
X *		p_prim benutzt m_init
X */
X
X/*
X * Prototypes
X */
Xstatic int	jak_f( NUMBER* );	
Xstatic int	jak_g( NUMBER*, NUMBER* );	
Xstatic int	jakobi( NUMBER*, NUMBER* );
X
X/*
X * Hilfs-Funktion fuer jakobi