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}
X
X/*
X * Mulitipliziere INT array der Laenge l mit einer INT (d = n * m)
X * return neue Laenge
X */
Xint n_mult( n, m, d, l)
Xregister INT *n;
Xregister INT m;
XINT *d;
X{
X int i;
X register LONG mul;
X
X for (i=l,mul=0; i; i--) {
X mul += (LONG)m * (LONG)*n++;
X *d++ = TOINT(mul);
X mul /= (MAXINT +1);
X }
X
X if (mul) { /* carry ? */
X l++;
X *d = mul;
X }
X
X return( l );
X}
X
X/*
X * Mulitipliziere eine NUMBER mit einer INT (d = n * m)
X */
Xvoid a_imult( n, m, d )
XNUMBER *n;
XINT m;
XNUMBER *d;
X{
X if (m == 0)
X d->n_len=0;
X else if (m == 1)
X a_assign( d, n );
X else
X d->n_len = n_mult( n->n_part, m, d->n_part, n->n_len );
X}
X
X/*
X * Multipliziere zwei NUMBER (d = m1 * m2)
X */
Xvoid a_mult( m1, m2, d )
XNUMBER *m1,*m2,*d;
X{
X static VLONG id[ MAXLEN ]; /* Zwischenspeicher */
X register VLONG *vp; /* Pointer darin */
X register LONG tp1; /* Zwischenspeicher fuer m1 */
X register INT *p2;
X INT *p1;
X int l1,l2,ld,lc,l,i,j;
X
X l1 = m1->n_len;
X l2 = m2->n_len;
X l = l1 + l2;
X if (l >= MAXLEN)
X abort();
X
X for (i=l, vp=id; i--;)
X *vp++ = 0;
X
X /* ohne Uebertrag in Zwischenspeicher multiplizieren */
X for ( p1 = m1->n_part, i=0; i < l1 ; i++, p1++ ) {
X
X tp1 = (LONG)*p1;
X vp = &id[i];
X for ( p2 = m2->n_part, j = l2; j--;)
X *vp++ += (VLONG)(tp1 * (LONG)*p2++);
X }
X
X /* jetzt alle Uebertraege beruecksichtigen */
X ld = 0;
X for (lc=0, vp=id, p1=d->n_part; lc++ < l;) {
X register VLONG tmp;
X
X tmp = *vp++;
X if ( *p1++ = TOINT(tmp) )
X ld = lc;
X *vp += tmp / ((VLONG)MAXINT +1);
X }
X
X d->n_len = ld;
X}
X
X
X/*
X * Dividiere Zwei NUMBER mit Rest (q= d1 / z2[0] Rest r)
X * z2[i] = z2[0] * 2^i, i=0..MAXBIT-1
X * r = 0 : kein Rest
X * q = 0 : kein Quotient
X */
Xvoid n_div( d1, z2, q, r )
XNUMBER *d1,*z2,*q,*r;
X{
X static NUMBER dummy_rest; /* Dummy Variable, falls r = 0 */
X static NUMBER dummy_quot; /* Dummy Variable, falla q = 0 */
X INT *i1,*i1e,*i3;
X int l2,ld,l,lq;
X#if MAXINT != 1
X INT z;
X int pw,l2t;
X#endif
X
X if (!z2->n_len)
X abort();
X
X if (!r)
X r = &dummy_rest;
X if (!q)
X q = &dummy_quot;
X
X a_assign( r, d1 ); /* Kopie von d1 in den Rest */
X
X l2= z2->n_len; /* Laenge von z2[0] */
X l = r->n_len - l2; /* Laenge des noch ''rechts'' liegenden
X Stuecks von d1 */
X lq= l +1; /* Laenge des Quotienten */
X i3= q->n_part + l;
X i1= r->n_part + l;
X ld = l2; /* aktuelle Laenge des ''Vergleichsstuecks''
X von d1 */
X i1e= i1 + (ld-1);
X
X for (; l >= 0; ld++, i1--, i1e--, l--, i3--) {
X *i3 = 0;
X
X if (ld == l2 && ! *i1e) {
X ld--;
X continue;
X }
X
X if ( ld > l2 || (ld == l2 && n_cmp( i1, z2->n_part, l2) >= 0 ) ) {
X#if MAXINT != 1
X /* nach 2er-Potenzen zerlegen */
X for (pw=MAXBIT-1, z=(INT)HIGHBIT; pw >= 0; pw--, z /= 2) {
X if ( ld > (l2t= z2[pw].n_len)
X || (ld == l2t
X && n_cmp( i1, z2[pw].n_part, ld) >= 0) ) {
X ld = n_sub( i1, z2[pw].n_part, i1, ld, l2t );
X (*i3) += z;
X }
X }
X#else
X /* bei MAXINT == 1 alles viel einfacher */
X ld = n_sub( i1, z2->n_part, i1, ld, l2 );
X (*i3) ++;
X#endif
X }
X }
X
X /* Korrektur, falls l von Anfang an Negativ war */
X l ++;
X lq -= l;
X ld += l;
X
X if (lq>0 && !q->n_part[lq -1]) /* evtl. Laenge korrigieren */
X lq--;
X
X q->n_len = lq;
X r->n_len = ld -1;
X}
X
X/*
X * Dividiere Zwei NUMBER mit Rest (q= d1 / z2[0] Rest r)
X * z2[i] = z2[0] * 2^i, i=0..MAXBIT-1
X * r = 0 : kein Rest
X * q = 0 : kein Quotient
X */
Xvoid a_div( d1, d2, q, r )
XNUMBER *d1,*d2,*q,*r;
X{
X#if MAXINT != 1
X NUMBER z2[MAXBIT];
X INT z;
X int i;
X
X a_assign( &z2[0], d2 );
X for (i=1,z=2; i < MAXBIT; i++, z *= 2)
X a_imult( d2, z, &z2[i] );
X
X d2 = z2;
X#endif
X
X n_div( d1, d2, q, r );
X}
X
X/*
X * Dividiere eine NUMBER durch 2
X */
Xvoid a_div2( n )
XNUMBER *n;
X{
X#if MAXBIT == LOWBITS
X register INT *p;
X int i;
X
X#if MAXINT != 1
X register INT h;
X register int c;
X
X c=0;
X i= n->n_len;
X p= &n->n_part[i-1];
X
X for (; i--;) {
X if (c) {
X c = (h= *p) & 1;
X h /= 2;
X h |= HIGHBIT;
X }
X else {
X c = (h= *p) & 1;
X h /= 2;
X }
X
X *p-- = h;
X }
X
X if ( (i= n->n_len) && n->n_part[i-1] == 0 )
X n->n_len = i-1;
X
X#else /* MAXBIT != 1 */
X p = n->n_part;
X i = n->n_len;
X
X if (i) {
X n->n_len = i-1;
X for (; --i ; p++)
X p[0] = p[1];
X }
X#endif /* MAXBIT != 1 */
X#else /* MAXBIT == LOWBITS */
X a_div( n, &a_two, n, NUM0P );
X#endif /* MAXBIT == LOWBITS */
X}
X
X
X/*
X * MODULO-FUNKTIONEN
X */
X
Xstatic NUMBER mod_z2[ MAXBIT ];
X
X/*
X * Init
X */
Xvoid m_init( n, o )
XNUMBER *n,*o;
X{
X INT z;
X int i;
X
X if (o)
X a_assign( o, &mod_z2[0] );
X
X if (! a_cmp( n, &mod_z2[0] ) )
X return;
X
X for (i=0,z=1; i < MAXBIT; i++, z *= 2)
X a_imult( n, z, &mod_z2[i] );
X}
X
Xvoid m_add( s1, s2, d )
XNUMBER *s1, *s2, *d;
X{
X a_add( s1, s2, d );
X if (a_cmp( d, mod_z2 ) >= 0)
X a_sub( d, mod_z2, d );
X}
X
Xvoid m_mult( m1, m2, d )
XNUMBER *m1,*m2,*d;
X{
X a_mult( m1, m2, d );
X n_div( d, mod_z2, NUM0P, d );
X}
X
X/*
X * Restklassen Exponent
X */
Xvoid m_exp( x, n, z )
XNUMBER *x,*n,*z;
X{
X NUMBER xt,nt;
X
X a_assign( &nt, n );
X a_assign( &xt, x );
X a_assign( z, &a_one );
X
X while (nt.n_len) {
X while ( ! (nt.n_part[0] & 1) ) {
X m_mult( &xt, &xt, &xt );
X a_div2( &nt );
X }
X m_mult( &xt, z, z );
X a_sub( &nt, &a_one, &nt );
X }
X}
X
X/*
X * GGT
X */
Xvoid a_ggt( a, b, f )
XNUMBER *a,*b,*f;
X{
X NUMBER t[2];
X int at,bt, tmp;
X
X a_assign( &t[0], a ); at= 0;
X a_assign( &t[1], b ); bt= 1;
X
X if ( a_cmp( &t[at], &t[bt] ) < 0 ) {
X tmp= at; at= bt; bt= tmp;
X }
X /* euklidischer Algorithmus */
X while ( t[bt].n_len ) {
X a_div( &t[at], &t[bt], NUM0P, &t[at] );
X tmp= at; at= bt; bt= tmp;
X }
X
X a_assign( f, &t[at] );
X}
X
X/*
X * die untersten b bits der Dualdarstellung von n
X * die bits muessen in ein int passen
X */
Xint n_bits(n,b)
XNUMBER *n;
X{
X INT *p;
X int l;
X unsigned r;
X int m = (1<<b) -1;
X
X if ( n->n_len == 0)
X return(0);
X
X if (LOWBITS >= b)
X return( n->n_part[0] & m );
X
X#if LOWBITS != 0
X l = (b-1) / LOWBITS;
X#else
X l = n->n_len -1;
X#endif
X for (p= &n->n_part[l],r=0; l-- >= 0 && b > 0; b-= LOWBITS, p--) {
X r *= (unsigned)(MAXINT+1);
X r += (unsigned)*p;
X }
X
X return( r & m );
X}
X
X/*
X * Anzahl der bits von n bei Dualdarstellung
X */
Xint n_bitlen( n )
XNUMBER *n;
X{
X NUMBER b;
X int i;
X
X a_assign( &b, &a_one );
X
X for (i=0; a_cmp( &b, n ) <= 0; a_mult( &b, &a_two, &b ), i++)
X ;
X
X return(i);
X}
SHAR_EOF
if test 11614 -ne "`wc -c < 'arith.c'`"
then
echo shar: "error transmitting 'arith.c'" '(should have been 11614 characters)'
fi
fi
echo shar: "extracting 'arith.h'" '(1464 characters)'
if test -f 'arith.h'
then
echo shar: "will not over-write existing file 'arith.h'"
else
sed 's/^X//' << \SHAR_EOF > 'arith.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 _arith_h_
X#define _arith_h_
X
X#ifndef _conf_h_
X#include "conf.h"
X#endif
X
Xextern NUMBER a_one,a_two;
X
X/*
X * Prototypes
X */
X
Xvoid a_add P(( NUMBER*, NUMBER*, NUMBER* ));
Xvoid a_assign P(( NUMBER*, NUMBER* ));
Xint a_cmp P(( NUMBER*, NUMBER* ));
Xvoid a_div P(( NUMBER*, NUMBER*, NUMBER*, NUMBER* ));
Xvoid a_div2 P(( NUMBER* ));
Xvoid a_ggt P(( NUMBER*, NUMBER*, NUMBER* ));
Xvoid a_imult P(( NUMBER*, INT, NUMBER* ));
Xvoid a_mult P(( NUMBER*, NUMBER*, NUMBER* ));
Xvoid a_sub P(( NUMBER*, NUMBER*, NUMBER* ));
Xvoid m_init P(( NUMBER*, NUMBER* ));
Xvoid m_add P(( NUMBER*, NUMBER*, NUMBER* ));
Xvoid m_mult P(( NUMBER*, NUMBER*, NUMBER* ));
Xvoid m_exp P(( NUMBER*, NUMBER*, NUMBER* ));
Xint n_bits P(( NUMBER*, int));
Xvoid n_div P(( NUMBER*, NUMBER*, NUMBER*, NUMBER* ));
Xint n_cmp P(( INT*, INT*, int ));
Xint n_mult P(( INT*, INT, INT*, int ));
Xint n_sub P(( INT*, INT*, INT*, int, int ));
Xint n_bitlen P(( NUMBER* ));
X
X#endif
SHAR_EOF
if test 1464 -ne "`wc -c < 'arith.h'`"
then
echo shar: "error transmitting 'arith.h'" '(should have been 1464 characters)'
fi
fi
echo shar: "extracting 'conf.h'" '(2050 characters)'
if test -f 'conf.h'
then
echo shar: "will not over-write existing file 'conf.h'"
else
sed 's/^X//' << \SHAR_EOF > 'conf.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 _conf_h_
X#define _conf_h_
X
Xtypedef unsigned char INT; /* muss MAXINT fassen */
Xtypedef unsigned int LONG; /* muss 2*MAXINT+1 fassen */
Xtypedef unsigned long VLONG; /* muse MAXLEN * (MAXINT^2 +1) fassen*/
X
X#if defined( M_XENIX )
X#define P(x) x /* Funktions Prototypen an */
X#else
X#define P(x) () /* Funktions Prototypen aus */
X#endif
X
X/*
X * (MAXINT+1)-adic Zahlen
X */
X
X/*
X * MAXINT Maximale Zahl pro Elemenmt (muss int sein)
X * MAXBIT Maximales Bit von MAXINT
X * LOWBITS Anzahl der consekutiven low Bits von MAXINT
X * HIGHBIT Hoechsten Bit von MAXINT
X * TOINT muss (INT)( (x) % MAXINT) ergeben
X * MAXLEN Laenge der INT Array in jeder NUMBER
X */
X
X#define MAXINT 0xFF
X
X#if MAXINT == 99
X#define MAXBIT 7
X#define LOWBITS 2
X#endif
X#if MAXINT == 9
X#define MAXBIT 4
X#define LOWBITS 1
X#endif
X#if MAXINT == 1
X#define MAXBIT 1
X#endif
X#if MAXINT == 0xFF
X#define MAXBIT 8
X#define TOINT(x) ((INT)(x))
X#endif
X
X#ifndef MAXBIT
X#include "<< ERROR: MAXBIT must be defined >>"
X#endif
X#ifndef LOWBITS
X#if MAXINT == (1 << MAXBIT) - 1
X#define LOWBITS MAXBIT
X#else
X#include "<< ERROR: LOWBITS must be defined >>"
X#endif
X#endif
X
X#define MAXLEN (300*8/(MAXBIT + 1))
X#define STRLEN (MAXLEN*MAXBIT/4)
X#define HIGHBIT (1 << (MAXBIT-1) )
X#ifndef TOINT
X#if LOWBITS == MAXBIT
X#define TOINT(x) ((INT)((x)&MAXINT))
X#else
X#define TOINT(x) ((INT)((x)%(MAXINT+1)))
X#endif
X#endif
X
Xtypedef struct {
X int n_len; /* Hoechster benutzter Index */
X INT n_part[MAXLEN];
X} NUMBER;
X
X#define NUM0P ((NUMBER *)0) /* Abkuerzung */
X
X#endif
SHAR_EOF
if test 2050 -ne "`wc -c < 'conf.h'`"
then
echo shar: "error transmitting 'conf.h'" '(should have been 2050 characters)'
fi
fi
echo shar: "extracting 'genprim.c'" '(1416 characters)'
if test -f 'genprim.c'
then
echo shar: "will not over-write existing file 'genprim.c'"
else
sed 's/^X//' << \SHAR_EOF > 'genprim.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 "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* martin@trillian.megalon.de *
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* martin@trillian.megalon.de *
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* martin@trillian.megalon.de *
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* martin@trillian.megalon.de *
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
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 :-)