?? rsa_1.txt
字號:
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, > );
X if ( a_cmp( >, &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* martin@trillian.megalon.de *
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* martin@trillian.megalon.de *
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* martin@trillian.megalon.de *
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* martin@trillian.megalon.de *
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: +49 203 775679 (without carrier at 8-21 h)
Fliederstr. 23 Mail : martin@trillian.megalon.de
4100 Duisburg 1
W-Germany WARNING: Don't trust upon my opinion - it changes :-)
?? 快捷鍵說明
復制代碼
Ctrl + C
搜索代碼
Ctrl + F
全屏模式
F11
切換主題
Ctrl + Shift + D
顯示快捷鍵
?
增大字號
Ctrl + =
減小字號
Ctrl + -