rsa_1.txt

rsa加密算法源程序

X */
Xstatic int jak_f( n )
XNUMBER *n;
X{
X	int f,ret;
X	
X	f = n_bits( n, 3 );
X	
X	ret = ((f == 1) || (f == 7)) ? 1 : -1;
X	
X	return(ret);
X}
X
X/*
X * Hilfs-Funktuion fuer jakobi
X */	
Xstatic int jak_g( a, n )
XNUMBER *a,*n;
X{
X	int ret;
X	
X	if ( n_bits( n, 2 ) == 1 ||
X			n_bits( a, 2 ) == 1 )
X		ret = 1;
X	else
X		ret = -1;
X	
X	return(ret);
X}
X		
X/*
X * Jakobi-Symbol
X */
Xstatic int jakobi( a, n )
XNUMBER *a,*n;
X{
X	NUMBER t[2];
X	int at,nt, ret;
X	
X	a_assign( &t[0], a ); at = 0;
X	a_assign( &t[1], n ); nt = 1;
X
X	/*
X	 * b > 1
X	 *
X	 * J( a, b) =
X	 * a == 1	:	1
X	 * a == 2	:	f(n)
X	 * a == 2*b	:	J(b,n)*J(2,n) ( == J(b,n)*f(n) )
X	 * a == 2*b -1	:	J(n % a,a)*g(a,n)
X	 *
X	 */
X	 
X	ret = 1;
X	while (1) {
X		if (! a_cmp(&t[at],&a_one) ) {
X			break;
X		}
X		if (! a_cmp(&t[at],&a_two) ) {
X			ret *= jak_f( &t[nt] );
X			break;
X		}
X		if ( ! t[at].n_len )		/* Fehler :-)	*/
X			abort();
X		if ( t[at].n_part[0] & 1 ) {	/* a == 2*b -1	*/
X			int tmp;
X			
X			ret *= jak_g( &t[at], &t[nt] );
X			a_div( &t[nt], &t[at], NUM0P, &t[nt] );
X			tmp = at; at = nt; nt = tmp;
X		}
X		else {				/* a == 2*b	*/
X			ret *= jak_f( &t[nt] );
X			a_div2( &t[at] );
X		}
X
X	}
X	
X	return(ret);
X}
X		
X/*
X * Probabilistischer Primzahltest
X *
X *  0 -> n nicht prim
X *  1 -> n prim mit  (1-1/2^m) Wahrscheinlichkeit.
X *
X *	ACHTUNG !!!!!!
X *	p_prim benutzt m_init !!
X *
X */
Xint p_prim( n, m )
XNUMBER *n;
X{
X	NUMBER gt,n1,n2,a;
X	INT *p;
X	int i,w,j;
X	long lrand48();
X
X	if (a_cmp(n,&a_two) <= 0 || m <= 0)
X		abort();
X		
X	a_sub( n, &a_one, &n1 );	/* n1 = -1    mod n		*/
X	a_assign( &n2, &n1 );
X	a_div2( &n2 );			/* n2 = ( n -1 ) / 2		*/
X	
X	m_init( n, NUM0P );
X	
X	w = 1;
X	for (; w && m; m--) {
X				/* ziehe zufaellig a aus 2..n-1		*/
X		do {
X			for (i=n->n_len-1, p=a.n_part; i; i--)
X				*p++ = (INT)lrand48();
X			if ( i=n->n_len )
X				*p = (INT)( lrand48() % ((unsigned long)n->n_part[i-1] +1) );
X			while ( i && ! *p )
X				p--,i--;
X			a.n_len = i;
X		} while ( a_cmp( &a, n ) >= 0 || a_cmp( &a, &a_two ) < 0 );
X
X				/* jetzt ist a fertig			*/
X
X		/*
X		 * n ist nicht prim wenn gilt:
X		 *	(a,n) != 1
X		 * oder
X		 *	a^( (n-1)/2 ) != J(a,n)   mod n
X		 *
X		 */
X		 
X		a_ggt( &a, n, &gt );
X		if ( a_cmp( &gt, &a_one ) == 0 ) {
X
X			j= jakobi( &a, n );
X			m_exp( &a, &n2, &a );
X
X			if  (   ( a_cmp( &a, &a_one ) == 0 && j ==  1 )
X			     || ( a_cmp( &a, &n1    ) == 0 && j == -1 ) )
X				w = 1;
X			else
X				w = 0;
X		}
X		else
X			w = 0;
X	}
X
X	return( w );
X}
X
X/*
X * Berechne mulitiplikatives Inverses zu d (mod phi)
X *	d relativ prim zu phi ( d < phi )
X *	d.h. (d,phi) == 1
X *
X *	ACHTUNG !!!!
X *	inv benutzt m_init
X */
Xvoid inv( d, phi, e )
XNUMBER *d,*phi,*e;
X{
X	int k, i0, i1, i2;
X	NUMBER r[3],p[3],c;
X	
X	/*
X	 * Berlekamp-Algorithmus
X	 *	( fuer diesen Spezialfall vereinfacht )
X	 */
X
X	if (a_cmp(phi,d) <= 0)
X		abort();
X	
X	m_init( phi, NUM0P );
X	
X	p[1].n_len = 0;
X	a_assign( &p[2], &a_one );
X	a_assign( &r[1], phi );
X	a_assign( &r[2], d );
X	
X	k = -1;
X	do {
X		k++;
X		i0=k%3; i1=(k+2)%3; i2=(k+1)%3;
X		a_div( &r[i2], &r[i1], &c, &r[i0] );
X		m_mult( &c, &p[i1], &p[i0] );
X		m_add( &p[i0], &p[i2], &p[i0] );
X	} while (r[i0].n_len);
X
X	if ( a_cmp( &r[i1], &a_one ) )	/* r[i1] == (d,phi) muss 1 sein	*/
X		abort();
X		
X	if ( k & 1 )	/* falsches ''Vorzeichen''	*/
X		a_sub( phi, &p[i1], e );
X	else
X		a_assign( e, &p[i1] );
X}
SHAR_EOF
if test 4771 -ne "`wc -c < 'prim.c'`"
then
	echo shar: "error transmitting 'prim.c'" '(should have been 4771 characters)'
fi
fi
echo shar: "extracting 'prim.h'" '(688 characters)'
if test -f 'prim.h'
then
	echo shar: "will not over-write existing file 'prim.h'"
else
sed 's/^X//' << \SHAR_EOF > 'prim.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	_prim_h_
X#define	_prim_h_
X
X#ifndef _arith_h_
X#include	"arith.h"
X#endif
X
Xint	p_prim		P(( NUMBER*, int ));
Xvoid	inv		P(( NUMBER*, NUMBER*, NUMBER* ));
X
X#endif
SHAR_EOF
if test 688 -ne "`wc -c < 'prim.h'`"
then
	echo shar: "error transmitting 'prim.h'" '(should have been 688 characters)'
fi
fi
echo shar: "extracting 'rnd.c'" '(1073 characters)'
if test -f 'rnd.c'
then
	echo shar: "will not over-write existing file 'rnd.c'"
else
sed 's/^X//' << \SHAR_EOF > 'rnd.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	"rand.h"
X
X#include	"nio.h"
X
Xvoid gen_number( len, n )
XNUMBER *n;
X{
X	char *hex = "0123456789ABCDEF" ;
X	char num[ MAXLEN*MAXBIT/4 +1 ];
X	char *p;
X	int i,l;
X	
X	p=&num[ sizeof(num) -1];
X	*p-- = '\0';
X	
X	for (l=len; l--; p-- ) {
X		i = lrand48() % 16;
X		*p = hex[ i ];
X	}
X	p++;
X	
X	while (len-- && *p == '0')
X		p++;
X	
X	num_sget( n, p );
X}
X
Xvoid init_rnd()
X{
X	long time();
X	short seed[3];
X
X	seed[0] = time((long *)0) & 0xFFFF;
X	seed[1] = getpid() & 0xFFFF;
X	seed[2] = (time((long *)0) >> 16) & 0xFFFF;
X	(void)seed48( seed );
X}	
X
SHAR_EOF
if test 1073 -ne "`wc -c < 'rnd.c'`"
then
	echo shar: "error transmitting 'rnd.c'" '(should have been 1073 characters)'
fi
fi
echo shar: "extracting 'rnd.h'" '(673 characters)'
if test -f 'rnd.h'
then
	echo shar: "will not over-write existing file 'rnd.h'"
else
sed 's/^X//' << \SHAR_EOF > 'rnd.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	_rnd_h_
X#define	_rnd_h_
X
X#ifndef _arith_h_
X#include	"arith.h"
X#endif
X
Xvoid	gen_number	P(( int, NUMBER* ));
Xvoid	init_rnd	P(( void ));
X
X#endif
SHAR_EOF
if test 673 -ne "`wc -c < 'rnd.h'`"
then
	echo shar: "error transmitting 'rnd.h'" '(should have been 673 characters)'
fi
fi
echo shar: "extracting 'rsa.c'" '(3178 characters)'
if test -f 'rsa.c'
then
	echo shar: "will not over-write existing file 'rsa.c'"
else
sed 's/^X//' << \SHAR_EOF > 'rsa.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	<string.h>
X#include	<memory.h>
X
X#include	"arith.h"
X#include	"nio.h"
X
X#define	ENCODE	"rsaencode"
X#define	DECODE	"rsadecode"
X
Xchar *prog;
X
Xint	clear_siz;			/* clear-text blocksize		*/
Xint	enc_siz;			/* encoded blocksize		*/
X					/* clear_siz < enc_siz		*/
X
Xdo_crypt( s, d, len, e )
Xchar *s;
Xchar *d;
XNUMBER *e;
X{
X	static char hex[] = "0123456789ABCDEF";
X	NUMBER n;
X	char buf[ STRLEN + 1 ];
X	char *pb,*ph;
X	int i,c;
X	
X	ph = buf + STRLEN;
X	ph[1] = '\0';
X	
X	for (i=len; i; i--) {
X		c = *s++;
X		*ph-- = hex[ (c >> 4) & 0xF ];
X		*ph-- = hex[ c & 0xF ];
X	}
X	ph++;
X	
X	num_sget( &n, ph );
X	
X	m_exp( &n, e, &n );
X	
X	num_sput( &n, buf, STRLEN +1 );
X	
X	ph = buf + (i=strlen(buf)) -1;
X	
X	for (; len; len--) {
X		if (i-- > 0) {
X			c = (strchr( hex, *ph ) - hex) << 4;
X			ph--;
X		}
X		else
X			c=0;
X		if (i-- > 0) {
X			c |= strchr( hex, *ph ) - hex;
X			ph--;
X		}
X
X		*d++ = c;
X	}
X}
X	
X	
Xint get_clear( p )
Xchar *p;
X{
X	int n;
X	
X	n = fread( p, 1, clear_siz, stdin );
X	
X	if (n <= 0)
X		return(0);
X	
X	memset( p + n, 0, enc_siz - n );
X	
X	return(1);
X}
X
Xint get_enc( p )
Xchar *p;
X{
X	int n;
X
X	n = fread( p, 1, enc_siz, stdin );
X	
X	if (n != enc_siz)
X		return(0);
X	
X	return(1);
X}
X
Xint put_clear( p )
Xchar *p;
X{
X	int n;
X	
X	n = fwrite( p, 1, clear_siz, stdout );
X	
X	if (n != clear_siz)
X		return(0);
X
X	return(1);
X}
X
Xint put_enc( p )
Xchar *p;
X{
X	int n;
X
X	n = fwrite( p, 1, enc_siz, stdout );
X	
X	if (n != enc_siz)
X		return(0);
X	
X	return(1);
X}
X
X
Xmain( argc, argv )
Xchar **argv;
X{
X	char buf[ STRLEN*2 ];
X	NUMBER n,e;
X	FILE *keys;
X	int (*inp)() = 0;
X	int (*out)() = 0;
X	
X	if ( ! (prog=strrchr( argv[0], '/' )) )
X		prog=argv[0];
X	
X	
X	if ( ! strcmp( prog, DECODE ) ) {
X		inp = get_enc;
X		out = put_clear;
X	}
X	if ( ! strcmp( prog, ENCODE ) ) {
X		inp = get_clear;
X		out = put_enc;
X	}
X	
X	if (! inp) {
X		fprintf(stderr,"%s: don't know who i am (%s or %s)\n",prog,ENCODE,DECODE);
X		exit(1);
X	}
X	
X	if (argc != 2) {
X		fprintf(stderr,"usage: %s keyfile\n",prog);
X		exit(1);
X	}
X	if ( !( keys= fopen(argv[1],"r")) ) {
X		perror(argv[1]);
X		exit(1);
X	}
X	
X	num_fget( &n, keys ); getc(keys);
X	num_fget( &e, keys );
X	if (a_cmp(&n,&e) <= 0 || e.n_len == 0 || getc(keys) != EOF) {
X		fprintf(stderr,"%s: corrupt keyfile\n",prog);
X		fprintf(stderr,"keyfile format:\n");
X		fprintf(stderr,"\t<n in hex>\n");
X		fprintf(stderr,"\t<delimiter> (1 char)\n");
X		fprintf(stderr,"\t<e/d in hex>\n");
X		fprintf(stderr,"white spaces are ignored\n");
X		exit(1);
X	}
X	
X	enc_siz = ( n_bitlen( &n ) + 7 ) / 8;
X	clear_siz = enc_siz -1;
X	
X	m_init( &n, NUM0P );
X	
X	while ( (*inp)( buf ) ) {
X		do_crypt( buf, buf, enc_siz, &e );
X		if (! (*out)( buf ) ) {
X			perror("output");
X			exit(1);
X		}
X	}
X	
X	exit(0);
X}
SHAR_EOF
if test 3178 -ne "`wc -c < 'rsa.c'`"
then
	echo shar: "error transmitting 'rsa.c'" '(should have been 3178 characters)'
fi
fi
exit 0
#	End of shell archive


-- 
Martin Nicolay         Phone: [phone] (without carrier at 8-21 h)
Fliederstr. 23         Mail : [e-mail]
4100 Duisburg 1
W-Germany              WARNING: Don't trust upon my opinion - it changes :-)