Dieser Artikel ist im Heise-Verlag in der Zeitschrift "c't", Ausgabe 04/1989 erschienen.
Er ist hier aus Gründen der besseren Übersicht dreigeteilt. Der Text ist Grundlage des Artikels
"Primzahltests und Primfaktorzerlegung". Links:
Anwendung RSA-Algorithmus
Wir kommen nun zu einer Anwendung für lange Zahlen, dem sog. RSA-
Algorithmus. Er wurde benannt nach seinen Erfindern Rivest, Shamir
und Adleman und ermöglicht die Verschlüsselung von Daten mit
öffentlichen Schlüsseln. Das bedeutet: Jeder, der diesen
öffentlichen Schlüssel kennt, kann verschlüsseln. Aber nur, wer
einen anderen, geheimen Schlüssel kennt, kann die Daten wieder
entschlüsseln. Es ist nicht möglich, aus dem öffentlichen Schlüssel
den geheimen zu rekonstruieren.
Im einzelnen: Es kommt hier auf eine Zahl n an, die das Produkt
zweier Primzahlen p und q ist. Voraussetzung für eine sinnvolle
Anwendung ist die Tatsache, daß n so groß ist, daß es nicht in die
Faktoren p und q zerlegt werden kann. Weiter spielt eine Zahl
f=(p-1)*(q-1) eine Rolle. Zum Verschlüsseln wird eine Zahl s
ausgesucht, die die Eigenschaften s<f und ggT(f,s)=1 hat. ggT
bedeutet hier den größten gemeinsamen Teiler. Entschlüsselt wird
mit Hilfe der Zahl t, für die s*t mod f = 1 gelten muß.
Den Code eines Textes erhält man, indem man jeweils die ASCII-
Codes einer Anzahl Zeichen zusammenfaßt und für diese Zahl, die
wir mit x bezeichnen, x^s mod n berechnet. Dies ist der Code, wir
nennen ihn y. x erhalten wir umgekehrt wieder durch y^t mod n. Wir
können ohne weiteres die Zahlen n und s öffentlich bekanntgeben.
Auf diese Weise kann jeder einen Text verschlüsseln. Aber nur wer
die Zahl t kennt, kann den Code entschlüsseln.
Im folgenden Programm-Listing, das unter dem Namen "rsa.c"
abgespeichert werden sollte, finden wir alle zur Ver- und Entschlüsselung
notwendigen Vereinbarungen und Unterprogramme. Auf einige Punkte
der Realisierung soll danach eingegangen werden.
/* rsa.c */
#define EOLN 10
typedef char linetype[81];
typedef longint clinetype[28];
cd(int c) /* Codierung eines Zeichens */
{
if (c==0) return 0;
else if (c<32 || c>126) return 1;
else return c-31;
}
dc(int n) /* Decodierung eines Zeichens */
{
if (n==0) return 0; else return n+31;
}
writeline(FILE *f, linetype l) /* Schreiben einer Textzeile */
{
int i;
i=0;
while (l[i]!='\0') {
putc(l[i],f); i++; }
putc('\n',f);
}
readline(FILE *f, linetype l) /* Lesen einer Textzeile */
{
int i,x;
i=0; x=getc(f);
if (x==EOF) return EOF;
while (x!=EOLN) {
l[i]=x; i++; x=getc(f); }
do {
l[i]='\0'; i++; }
while (i%3!=1);
return 0;
}
/* Schreiben einer codierten Zeile */
writecline(FILE *f, clinetype c)
{
int i;
string s;
i=0;
while (gt0l(c[i])) {
ltos(c[i],s); fprintf(f,"%s\n",s); i++; }
fprintf(f,"0\n");
}
/* Lesen einer codierten Zeile */
readcline(FILE *f, clinetype c)
{
int i,x;
string s;
x=fscanf(f,"%s",s); if (x==EOF) return EOF;
i=0; stol(s,c[i]);
while (gt0l(c[i])) {
i++; x=fscanf(f,"%s",s); stol(s,c[i]); }
i++; longl(0L,c[i]); return 0;
}
/* Codieren */
rsa_code(FILE *source, FILE *dest, longint s, longint n)
{
linetype sl;
clinetype dl;
longint ml;
int i,j,x;
long m;
x=readline(source,sl);
while (x!=EOF) {
i=j=0;
while (sl[i]!='\0') {
m=cd(sl[i])*10000L+cd(sl[i+1])*100L+cd(sl[i+2]);
longl(m,ml); ahsmodn(ml,s,n,dl[j]);
j++; i+=3; }
longl(0L,dl[j]);
writecline(dest,dl);
x=readline(source,sl); }
}
/* Decodieren */
rsa_decode(FILE *source, FILE *dest, longint t, longint n)
{
clinetype sl;
linetype dl;
longint d,m;
int i,j,x;
x=readcline(source,sl);
while (x!=EOF) {
i=j=0;
while (gt0l(sl[i])) {
ahsmodn(sl[i],t,n,m);
divmodl(m,hundertl,d,m); dl[j+2]=dc((int)m[1]);
divmodl(d,hundertl,d,m);
dl[j+1]=dc((int)m[1]); dl[j]=dc((int)d[1]);
i++; j+=3; }
dl[j]='\0'; writeline(dest,dl);
x=readcline(source,sl); }
}
|
Da wir einen Text verschlüsseln, müssen wir zunächst mehrere
Zeichen zu einer Zahl zusammenfassen. Dazu berechnen wir für jedes
Zeichen einen Code. Ausgangspunkt ist der ASCII-Code. Die
druckbaren Zeichen befinden sich im Bereich der Werte 32 bis 126.
Günstiger ist es, sich hier auf ein- oder zweistellige Werte zu
beschränken, deshalb ziehen wir 31 ab. Sollten Zeichen mit einem
Code außerhalb des genannten Intervalls auftreten, erhalten sie
den Code 1, dies entspricht dem Leerzeichen. Eine weitere Ausnahme
ist das Nullzeichen. Es erhält den Wert 0. Falls der verwendete
Rechner einen anderen als den ASCII-Code zugrunde legt, müssen die
Prozeduren cd und dc entsprechend geändert werden.
Beim Arbeiten mit Dateien müssen wir jeweils einen Filepointer
beispielsweise durch FILE *f vereinbaren. Bei Erreichen des
Dateiendes wird von der Routine getc der Wert EOF (,der in
"stdio.h" definiert ist,) als normaler Wert zurückgegeben. Bei
Benutzung von fscanf muß dieser Wert eigens abgefragt werden. Die
Prozeduren readline und readcline reichen dieses EOF an die
aufrufende Einheit weiter. In readline wird außerdem der Wert EOLN
(end of line) abgefragt, der vorher als 10 definiert wurde. Dies
muß eventuell an den verwendeten Rechner angepaßt werden.
Wir fassen jeweils die Codes dreier Zeichen zu einer Zahl
zusammen. Dies äußert sich bereits in readline. Um hier einer
größeren Fallunterscheidung aus dem Weg zu gehen, schreiben wir an
das Ende einer gelesenen Zeile bis zu drei Nullzeichen. Somit
können beim Zusammenfassen der Zeichen keine unvorhersehbaren
Werte ins Spiel kommen.
Das Schreiben einer codierten Zeile in eine Datei wird von der
Prozedur writecline durchgeführt. Weil die auftretenden Zahlen
normalerweise sehr groß sind, schreiben wir in jede Zeile nur eine
Zahl. Das Ende einer Textzeile wird durch eine 0 angezeigt.
Die Codierung eines Textes wird von rsa_code übernommen. In der
Variablen m wird die Zahl gespeichert, die jeweils drei Zeichen
entspricht. Diese muß in eine longint-Zahl verwandelt werden, mit
ahsmodn wird der Code hergestellt. Bei der Rückwandlung, die in
rsa_decode stattfindet, müssen wir zweimal die Prozedur divmodl
anwenden, um die drei Werte zu isolieren. Diese sind auf alle
Fälle kleiner als 100, somit können wir sie als m[1] bzw. d[1]
ansprechen.
Die Benutzung dieser Routinen ist in folgenden zwei
Programmen zu finden. Hier ist auch zu sehen, wie Dateien in C geöffnet und
geschlossen werden. Die angegebenen Zahlen n, s und t entsprechen
den oben genannten Anforderungen.
/* Codieren eines Textes */
#include "stdio.h"
#define MaxNr 50
#include "longcalc.c"
#include "rsa.c"
main()
{
FILE *fopen(),*fil1,*fil2;
longint n,s,t;
stol("2716556325528789881206403443",n);
stol("1703365",s);
printf("*** Codieren ***\n");
fil1=fopen("orig.txt","r");
fil2=fopen("coded.txt","w");
rsa_code(fil1,fil2,s,n);
fclose(fil1); fclose(fil2);
}
|
/* Decodieren eines Textes */
#include "stdio.h"
#define MaxNr 50
#include "longcalc.c"
#include "rsa.c"
main()
{
FILE *fopen(),*fil2,*fil3;
longint n,t;
stol("2716556325528789881206403443",n);
stol("4784452525785791363341",t);
printf("*** Decodieren ***\n");
fil2=fopen("coded.txt","r");
fil3=fopen("decod.txt","w");
rsa_decode(fil2,fil3,t,n);
fclose(fil2); fclose(fil3);
}
|
Nun ergibt sich die Frage, woher man solche Zahlen erhält. Nach
einigen Versuchen wird klar, daß nicht einmal das hier
anzuwendende Verfahren trivial ist. Nach Wahl von p und q sind die
Werte von n und f bestimmt. Am besten wählt man sich nun eine Zahl
a, die recht klein sein darf, und bestimmt die Primfaktoren von
(a*f+1). Diese werden gleichmäßig auf s und t verteilt, kein
Faktor darf doppelt verwendet werden, keiner darf übrigbbleiben.
Um dies durchzuführen, ist es notwendig, sich große Primzahlen zu
beschaffen oder für beliebige Zahlen die Eigenschaft "prim"
festzustellen. Für die in den Listings 3 und 4 benutzten Zahlen
beispielsweise ist p=411782264189299 und q=6597069766657. Daß
diese wirklich prim sind, ist ihnen nicht ohne weiteres
anzumerken. Unter Umständen sind sie ja auch zusammengesetzt, so
daß sich Faktoren leichter erkennen ließen. Dies könnte dann zum
Knacken des Codes führen.
Themen des Artikels Primzahltests und Primfaktorzerlegung
sind daher Primzahltests und Verfahren zur Primfaktorzerlegung. D.h. wir behandeln die Fragen:
Wie weise ich nach, daß eine Zahl prim ist? Und wie finde ich Faktoren einer
zusammengesetzten Zahl? Beide Fragen werden natürlich erst
interessant, wenn die vorkommenden Zahlen so groß sind, so daß ein
Testen aller möglichen Teiler ausgeschlossen ist.
Literatur
- N.Wirth: Systematisches Programmieren (Teubner-Verlag)