From: martin@trillian.UUCP (Martin Nicolay)
Newsgroups: sub.sources.unix,sub.sources.misc
Subject: RSA-Routinen
Date: 22 Nov 88 02:24:25 GMT
Reply-To: martin@trillian.megalon.de (Martin Nicolay)
Organization: Home
Xref: lan sub.sources.unix:2 sub.sources.misc:10

Ich hab eine Implementation des RSA-Verfahrens (Public-Key-Crypt) zusammen
gestrickt.  Enthalten sind dafuer auch Funktionen fuer Arithmetik mit grossen
Zahlen (obere Schranke ist Compile-Option).

Jetzt kann endlich kein Sysop mehr die private Post lesen :-).

Das Programm, dass den Text verschluesselt, ist noch verbesserungswuerdig.
Z.B. nur einen Block mit RSA (weil rechenintensiv) verschluesseln und darin
eine Key uebergeben, mit dem der Rest mit DES verschluesselt wird.

Viel Spass bei der sicheren Mail!

PS:  Mein oeffendlicher Schluessel ist :
	10875FDCBBC59099500630B241458A52B1830D35E6816A739C74534E8017E3F1
	B9ACB73BDC84C47F954047EAFFBE0EFD5499B4431C815130766E78ED0F1E671D
	F926171D67BDECB92374AAB07629C5F0263FCCDCD920F7D90779A8CF439538B1
	6FAF35CE95A06051A6BFD3A7D7AF8B51FE8545C439E4C9F0ADAB7E13303
	#
	C6A65AE2A755FFE2026134AF1B8EC469017D0D9F3884F4D1132D273F066DBE57
	86960811590F6873E52792D387604168183A7C22AA9FDF0F401454C4E65CE274
	78C94992F154F380886E2F410707209665B5629864A358EDE68E0C11F94DA275
	4C84D5F8BE6D7A6DC516FB6C4A4D7ABF13E701CCB2B8ED937E50438C2D

#! /bin/sh
# This is a shell archive, meaning:
# 1. Remove everything above the #! /bin/sh line.
# 2. Save the resulting text in a file.
# 3. Execute the file with /bin/sh (not csh) to create:
#	MANIFEST
#	Makefile
#	README
#	arith.c
#	arith.h
#	conf.h
#	genprim.c
#	genrsa.c
#	nio.c
#	nio.h
#	prim.c
#	prim.h
#	rnd.c
#	rnd.h
#	rsa.c
# This archive created: Tue Nov 22 03:06:33 1988
export PATH; PATH=/bin:/usr/bin:$PATH
echo shar: "extracting 'MANIFEST'" '(389 characters)'
if test -f 'MANIFEST'
then
	echo shar: "will not over-write existing file 'MANIFEST'"
else
sed 's/^X//' << \SHAR_EOF > 'MANIFEST'
XMakefile
Xconf.h			gundlegende Definitionen
Xarith.c			grundlegende arithmetische Routinen
Xarith.h
Xprim.c			Routinen zur probabilistischen Primzahl-Berechnung
Xprim.h
Xnio.c			IO-Routinen
Xnio.h
Xrnd.c			Zufalls-Zahl Erzeugungs Routinen
Xrnd.h
Xgenprim.c		Erzeugung von Primzahlen mit vorgegebener Stellenzahl
Xgenrsa.c		Erzeugung der oeffendlichen/geheimen Schluessel
Xrsa.c			Ver/Entschluesselung
SHAR_EOF
if test 389 -ne "`wc -c < 'MANIFEST'`"
then
	echo shar: "error transmitting 'MANIFEST'" '(should have been 389 characters)'
fi
fi
echo shar: "extracting 'Makefile'" '(709 characters)'
if test -f 'Makefile'
then
	echo shar: "will not over-write existing file 'Makefile'"
else
sed 's/^X//' << \SHAR_EOF > 'Makefile'
XSHELL=/bin/sh
X
XCFLAGS= -O
XLDFLAGS=
X
Xall:	genprim genrsa rsa
X
Xgenprim:	genprim.o rnd.o prim.o nio.o arith.o
X	$(CC) $(LDFLAGS) -o genprim genprim.o rnd.o nio.o prim.o arith.o
X
Xgenrsa:		genrsa.o rnd.o prim.o nio.o arith.o
X	$(CC) $(LDFLAGS) -o genrsa genrsa.o rnd.o nio.o prim.o arith.o
X
Xrsa:		rsa.o nio.o arith.o
X	$(CC) $(LDFLAGS) -o rsa rsa.o nio.o arith.o
X	ln rsa rsaencode
X	ln rsa rsadecode
X
Xrsa.o genrsa.o genprim.o nio.o prim.o arith.o:	conf.h
Xrsa.o genrsa.o genprim.o nio.o prim.o arith.o:	arith.h
Xrsa.o genrsa.o genprim.o nio.o:	nio.h
Xgenrsa.o genprim.o prim.o:	prim.h
Xgenrsa.o genprim.o rnd.o:	rnd.h
X
Xclean:
X	rm -f *.bak *.ba *~ \#* core *.o
X
Xclobber: clean
X	rm -f genrsa genprim rsa rsadecode rsaencode
SHAR_EOF
if test 709 -ne "`wc -c < 'Makefile'`"
then
	echo shar: "error transmitting 'Makefile'" '(should have been 709 characters)'
fi
fi
echo shar: "extracting 'README'" '(4029 characters)'
if test -f 'README'
then
	echo shar: "will not over-write existing file 'README'"
else
sed 's/^X//' << \SHAR_EOF > 'README'
X
X********************************************************************************
X*									       *
X*				R S A - Verfahren			       *
X*									       *
X********************************************************************************
X
XDie Schluessel-Generierung laeuft in 2 Stufen ab.
X
XA)	Es muessen 2 Primzahlen mit genprim berechnet werden. Die
X	Groessenordnung dieser Zahlen sollte 80-130 sein, und sich um
X	eine unterscheiden. Diese Zahlen muessen in einer Datei, mit
X	einem beliebigen Trennzeichen (z.B. '#') dazwischen, abgelegt
X	werden.
X
X		Alle Zahlen werden als Hexadezimalzahlen (fuer
X		Puristen: Sedizimal :-) ein-/ausgegeben.  Bei
X		Ein-/Ausgabe sind White-Spaces (Blank,Tab,Newline)
X		nicht signifikant.
X
X	Der zweite Parameter von genprim gibt die Wahrscheinlichkeit an,
X	mit der die gefundene Zahl wirklich eine Primzahl ist.  Fuer
X	eine Parameter n ist die Wahrscheinlichkeit 1-0.5^n. Fuer n=20
X	ist ein Programierfehler von mir schon wahrscheinlicher :-).
X	Das der Test nur probabilistisch ist, verringert bei vernuenftiger
X	Wahl von n die Aussagekraeftigkeit nur unwesendlich.
X
XB)	Genrsa generiert daraus eine Datei mit oeffendlichem/geheimen
X	Schluessel.  Diese Datei enthaelt 3 Zahlen.  Aus dieser Datei
X	gewinnt man die geheime, in dem man die letzte Zahl (mit Trenn-
X	zeichen) entfernt.  Den oeffendlichen erhaelt man duch Entfernung
X	der zweiten Zahl.
X
XBeispiel:
X	$ genrsa 10 20 >p1		# erste Primzahl
X	$ cat p1
X	2023A0B0BE5
X	$ genrsa 11 20 >p2		# zweite Primzahl
X	$ cat p2
X	537A985EC975
X	$ echo "#" | cat p1 - p2 >pd	# Eingabe fuer genrsa
X	$ genrsa <pd >rd		# Alle Zahlen fertig
X	$ cat rd
X	A7AF134EFB73D789793CA9
X	#
X	9245F9009636D26B7CA5ED
X	#
X	80F408891D5932D10C2585
X
XDieses File rd muss man auf 2 Files verteilen:
X
X	$ cat geheim
X	A7AF134EFB73D789793CA9
X	#
X	9245F9009636D26B7CA5ED
X	$ cat oeffendlich
X	A7AF134EFB73D789793CA9
X	#
X	80F408891D5932D10C2585
X
XDie Dateien p1,p2,pd und rd sollte man schnell wieder loeschen.
X
X	$ rsaencode oeffendlich <data >crypt	# Verschluesseln
X	$ rsadecode geheim <crypt >clear	# Entschluesseln
X
XDie Verschluesselung laeuft in Bloecken ab, deren Groesse von der der
Xersten Zahl des Schluessels Abhaengt.  Alle Bloecke werden als binaere
XDaten behandelt.  Allerdings wird beim Entschluesseln der letzte Block
Xmit ASCII-NULL aufgefuellt.  Dieses ist kein Fehler des RSA-Verfahrens,
Xsondern liegt an meiner Verwendung.  Das RSA-Verfahren verschluesselt
Xeinfach Zahlen. Meiner Umwandlung von Daten in Zahlen ist das Manko
Xanzulasten.  Deshalb muss auch der verschluesselte Text mit btoa oder
Xaehnlichem mailbar gemacht werden.  Zur Reduktion der Blockanzahl kann
Xman natuerlich vorher den Text compressen, da er sowieso binaer behandelt
Xwird.
X
XBei mir (386-er mit 20 MHz) dauert die Ver-/Entschluesselung eines
XBlocks (aus 125 & 124 stelliger Primzahl) 20 Minuten !!!!!!
XDafuer laeuft die Primzahlberechnung in 1-20 Stunden ab :-) !!!!!
XDas haengt von dem zufaelligen Startpunkt der Suche ab.
X
XWer Lust hat, die Verschluesselung so zu modifizieren, dass nur ein
XBlock mit RSA verschluesselt wird, und alle anderen, mit einem darin
Xuebergebenen weiteren Schuessel, mit DES zu verschluesseln, der ist
Xherzlich eingeladen ein solches Programm analog rsa.c zu erstellen.
XDie eigendliche Verschluesselung ist mit den Routinen aus arith.c
Xtrivial.  Es kostet allerding Zeit :-).
X
XAls Warnung fuer Leute, die mit den Routinen arbeiten wollen:
X
XAlle Routinen sind auf Laufzeit optimiert, und enthalten fast keine
XUeberpruefungen auf Ueberlauf o.ae. .  Wenn ein Fehler entdeckt wird
X(was selten ist :-), gibts eine core.  Alle Zahlen muessen >= 0 sein.
X
XMein Wissen ueber RSA und die anderen verwendeten Verfahren hab ich
Xaus:
X	Horster, Patrick:
X	Kryptologie / von Patrick Horster. - Mannheim;
X	Wien; Zuerich: Bibliographisches Institut, 1985.
X	    (Reihe Informatik; 47)
X	    ISBN 3-411-03106-9
X	NE: GT
X
XMartin Nicolay		( martin@trillian.megalon.de )
XFliederstr. 23
X4100 Duisburg 1
XW-Germany
X
XPS:	Falls rand.h nicht vorhanden ist: darin sind nur die Funktionen
X	wie drand48 usw. deklariert.
SHAR_EOF
if test 4029 -ne "`wc -c < 'README'`"
then
	echo shar: "error transmitting 'README'" '(should have been 4029 characters)'
fi
fi
echo shar: "extracting 'arith.c'" '(11614 characters)'
if test -f 'arith.c'
then
	echo shar: "will not over-write existing file 'arith.c'"
else
sed 's/^X//' << \SHAR_EOF > 'arith.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	"arith.h"
X
X/*
X *	!!!!!!!!!!!!!!!!!!!!!!!!!!!! ACHTUNG !!!!!!!!!!!!!!!!!!!!!!!!!!!!
X *	Es findet keinerlei Ueberpruefung auf Bereichsueberschreitung
X *	statt. Alle Werte muessen natuerliche Zahlen aus dem Bereich
X *		0 ... (MAXINT+1)^MAXLEN-1 sein.
X *	
X *	
X *	Bei keiner Funktion oder Hilsfunktion werden Annahmen getroffen,
X *	ueber die Verschiedenheit von Eingabe- & Ausgabe-Werten.
X *
X *
X *		Funktionen:
X *
X *	a_add( s1, s2, d )
X *		NUMBER *s1,*s2,*d;
X *			*d = *s1 + *s2;
X *
X *	a_assign( *d, *s )
X *		NUMBER *d,*s;
X *			*d = *s;
X *
X * int	a_cmp( c1, c2 )
X *		NUMBER *c1,*c2;
X *			 1 :	falls *c1 >  *c2
X *			 0 :	falls *c1 == *c2
X *			-1 :	falls *c1 <  *c2
X *
X *	a_div( d1, d2, q, r )
X *		NUMBER *d1,*d2,*q,*r;
X *			*q = *d1 / *d2 Rest *r;
X *
X *	a_div2( n )
X *		NUMBER *n;
X *			*n /= 2;
X *
X *	a_ggt( a, b, f )
X *		NUMBER *a,*b,*f;
X *			*f = ( *a, *b );
X *
X *	a_imult( n, m, d )
X *		NUMBER *n;
X *		INT m;
X *		NUMBER *d;
X *			*d = *n * m
X *
X *	a_mult( m1, m2, d )
X *		NUMBER *m1,*m2,*d;
X *			*d = *m1 * *m2;
X *
X *	a_sub( s1, s2, d )
X *		NUMBER *s1,*s2,*d;
X *			*d = *s1 - *s2;
X *
X *		Modulare Funktionen
X *	m_init( n, o )
X *		NUMBER *n,*o;
X *			Initialsierung der Modularen Funktionen
X *			o != 0 : *o = alter Wert
X *
X *	m_add( s1, s2, d )
X *		NUMBER *s1, *s2, *d;
X *			*d = *s1 + *s2;
X *
X *	m_mult( m1, m2, d )
X *		NUMBER *m1,*m2,*d;
X *
X *	m_exp( x, n, z )
X *		NUMBER *x,*n,*z;
X *			*z = *x exp *n;
X *
X *
X *		Hilfs-Funktionen:
X *
X * int	n_bits( n, b )
X *		NUMBER *n;
X *		int b;
X *			return( unterste b Bits der Dualdarstellung von n)
X *
X *	n_div( d1, z2, q, r )
X *		NUMBER *d1,z2[MAXBIT],*q,*r;
X *			*q = *d1 / z2[0] Rest *r;
X *			z2[i] = z2[0] * 2^i,  i=0..MAXBIT-1
X *
X * int	n_cmp( i1, i2, l )
X *		INT i1[l], i2[l];
X *			 1 :	falls i1 >  i2
X *			 0 :	falls i1 == i2
X *			-1 :	falls i1 <  i2
X *
X * int	n_mult( n, m, d, l)
X *		INT n[l], m, d[];
X *			d = m * n;
X *			return( sizeof(d) ); d.h. 'l' oder 'l+1'
X *
X * int	n_sub( p1, p2, p3, l, lo )
X *		INT p1[l], p2[lo], p3[];
X *			p3 = p1 - p2;
X *			return( sizeof(p3) ); d.h. '<= min(l,lo)'
X *
X * int	n_bitlen( n )
X * 		NUMBER *n;
X *			return( sizeof(n) in bits )
X *
X */
X
X
X/*
X * Konstante 1, 2
X */
XNUMBER a_one = {
X	1,
X	{ (INT)1, },
X};
X
XNUMBER a_two = {
X#if MAXINT == 1
X	2,
X	{ 0, (INT)1, },
X#else
X	1,
X	{ (INT)2, },
X#endif
X};
X
X
X/*
X * Vergleiche zwei INT arrays der Laenge l
X */
Xint n_cmp( i1, i2, l )
XINT *i1,*i2;
X{
X	i1 += (l-1);			/* Pointer ans Ende		*/ 
X	i2 += (l-1);
X	 
X	for (;l--;)
X		if ( *i1-- != *i2-- )
X			return( i1[1] > i2[1] ? 1 : -1 );
X	
X	return(0);
X}
X
X/*
X * Vergleiche zwei NUMBER
X */
Xint a_cmp( c1, c2 )
XNUMBER *c1,*c2;
X{
X	int l;
X					/* bei verschiedener Laenge klar*/
X	if ( (l=c1->n_len) != c2->n_len)
X		return( l - c2->n_len);
X	
X					/* vergleiche als arrays	*/
X	return( n_cmp( c1->n_part, c2->n_part, l) );
X}
X
X/*
X * Zuweisung einer NUMBER (d = s)
X */
Xvoid a_assign( d, s )
XNUMBER *d,*s;
X{
X	int l;
X	
X	if (s == d)			/* nichts zu kopieren		*/
X		return;
X	
X	if (l=s->n_len)
X		memcpy( d->n_part, s->n_part, sizeof(INT)*l);
X	
X	d->n_len = l;
X}
X
X/*
X * Addiere zwei NUMBER (d = s1 + s2)
X */
Xvoid a_add( s1, s2, d )
XNUMBER *s1,*s2,*d;
X{
X	int l,lo,ld,same;
X	register LONG sum;
X	register INT *p1,*p2,*p3;
X	register INT b;
X	
X				/* setze s1 auch die groessere Zahl	*/
X	l = s1->n_len;
X	if ( (l=s1->n_len) < s2->n_len ) {
X		NUMBER *tmp = s1;
X		
X		s1 = s2;
X		s2 = tmp;
X		
X		l = s1->n_len;
X	}
X
X	ld = l;
X	lo = s2->n_len;
X	p1 = s1->n_part;
X	p2 = s2->n_part;
X	p3 = d->n_part;
X	same = (s1 == d);
X	sum = 0;
X	
X	while (l --) {
X		if (lo) {		/* es ist noch was von s2 da	*/
X			lo--;
X			b = *p2++;
X		}
X		else
X			b = 0;		/* ansonten 0 nehmen		*/
X		
X		sum += (LONG)*p1++ + (LONG)b;
X		*p3++ = TOINT(sum);
X
X		if (sum > (LONG)MAXINT) {	/* carry merken		*/
X			sum = 1;
X		}
X		else
X			sum = 0;
X
X		if (!lo && same && !sum)	/* nichts mehr zu tuen	*/
X			break;
X	}
X	
X	if (sum) {		/* letztes carry beruecksichtigen	*/
X		ld++;
X		*p3 = sum;
X	}
X	
X	d->n_len = ld;			/* Laenge setzen		*/
X}
X
X/*
X * Subtrahiere zwei INT arrays. return( Laenge Ergebniss )
X * l == Laenge p1
X * lo== Laenge p3
X */
Xint n_sub( p1, p2, p3, l, lo )
XINT *p1,*p2,*p3;
Xint l,lo;
X{
X	int ld,lc,same;
X	int over = 0;
X	register LONG dif;
X	LONG a,b;
X	
X	same = (p1 == p3);			/* frueher Abbruch moeglich */
X	
X	for (lc=1, ld=0; l--; lc++) {
X		a = (LONG)*p1++;
X		if (lo) {			/* ist noch was von p2 da ? */
X			lo--;
X			b = (LONG)*p2++;
X		}
X		else
X			b=0;			/* ansonten 0 nehmen	*/
X
X		if (over)			/* frueherer Overflow	*/
X			b++;
X		if ( b > a ) {			/* jetzt Overflow ?	*/
X			over = 1;
X			dif = (MAXINT +1) + a;
X		}
X		else {
X			over = 0;
X			dif = a;
X		}
X		dif -= b;
X		*p3++ = (INT)dif;
X		
X		if (dif)			/* Teil != 0 : Laenge neu */
X			ld = lc;
X		if (!lo && same && !over) {	/* nichts mehr zu tuen	*/
X			if (l > 0)		/* Laenge korrigieren	*/
X				ld = lc + l;
X			break;
X		}
X	}
X
X	return( ld );
X}
X
X/*
X * Subtrahiere zwei NUMBER (d= s1 - s2)
X */
Xvoid a_sub( s1, s2, d )
XNUMBER *s1,*s2,*d;
X{
X	d->n_len = n_sub( s1->n_part, s2->n_part, d->n_part
X			 ,s1->n_len, s2->n_len );
X}