Datensicherheit. Verschluesselung mit dem RSA-Code. Theoretisches.
Das "public key"- System von R. L. Riverest, A. Shamir, L. M. Adleman
(1978) (RSA- Code).
(Anm. der Redaktion):
Nachdem wir schon einen Beitrag zum Thema DES hatten, wollen wir Euch
diesmal noch mal mit Mathematik aergern. Bei den Publik Key Verfahren handelt
es sich um Verschluesselungsprogramme, wo es zwei Schluessel gibt: Einen zum
Verschluesseln und einen zum Entschluesseln. Der zum verschluesseln kann
allgemein bekannt sein. Er ist zum Entschluesseln nutzlos. Diese Ver-
fahren haben den Vorteil, dass ein Nachteil von anderen Cryptoverfahren
(z.B. DES) wegfaellt. Dort muss naemlich der Schluessel ausgetaucht werden,
damit die Gegenstelle den Text wieder entschluesseln kann. Fuer die meisten
"praktischen" Anwendungen (z.B> in der Wirtschaft) sind die Public Key
Verfahren besser einsetzbar (Gute Informationen zu dem Thema kann mensch
von der GMD, Berlinghoven zum Projekt TeleTrust erhalten).
(Ende der Anmerkung)
Die Benutzer eines oeffentlichen Kommunikativsystems wollen verschluesselte
Botschaften austauschen. Es wird ein Alphabet mit N Zeichen benutzt. Die
Zeichen werden durchnumeriert. Seinen b(0), b(1), ... b(N-1) die Buch-
staben in diesem Alphabet. Diese Reihenfolge wird beibehalten.
Man waehlt natuerliche Zahlen k und l mit k < l, fuer die N^k (N hoch k) und
N^l (N hoch l) ca. 200 Dezimalstellen haben. Das Alphabet, die Reihenfolge
der Zeichen, die Zahl N, und die Zahlen k und l werden veroeffentlicht.
(1) Erzeugung des Codes
Es sei A ein Benutzer dieses Systems. A waehlt zwei verschiedene Primzahlen
p(A) und q(A) mit jeweils etwa 100 Dezimalstellen, die folgende Bedingung
erfuellen :
Es ist N^k < p(A) * q(A) < N^l
Dann berechnet A die Zahlen m(A) = p(A) * q(A) und
phi(A) = (p(A) -1) * (q(A) - 1)
und waehlt eine Zahl e(A) zwischen 1 und phi(A)-1, die mit phi(A)-1 keinen
gemeinsamen Teiler hat. Anschlie end berechnet A die Zahl d(A) fuer die
gilt:
Es gibt eine natuerliche Zahl k mit : d(A) * e(A) = 1 + phi(A) * k
(Mathematisch: d(A) * e(A) ist kongruent zu 1 modulo phi(A))
(Fuer die Berechnung von d(A) gibt es schnelle Algorithmen. Eingabe
dieser Algorithmen ist e(A) und phi(A). Die Geheimhaltung von phi(A)
ist also dringend erforderlich, um die Sicherheit des Codes zu
garantieren.)
Die Zahlen m(A) und e(A) werden veroeffentlicht, die Zahlen p(A), q(A),
d(A) und phi(A) muessen geheimgehalten werden. p(A), q(A) und phi(A)
werden nicht mehr benoetigt.
(2) Verschluesselung und Entschluesselung
Der Benutzer B moechte an A eine verschluesselte Nachricht schicken. B teilt
den Klartext in Bloecke aus k Zeichen und ersetzt jedes Zeichen durch sein
"numerisches" quivalent (also jeweils b(i) durch i). So entstehen k-tupel
aus Zahlen in {0, 1, ..., N-1}. Es sei (y(1), ..., y(k)) ein solches
k-tupel. B berechnet
X := y(1) * N^(k-1) + y(2) * N^(k-2) + ... + y(k-1) * N + y(k) und
X1 := (X ^ e(A)) MOD m(a)
Es gilt 0 < X < N^k-1 < N^l-1. B berechnet die z(1), ..., z(l) mit
X1 = z(1) * N^(l-1) + z(2) * N^(l-2) + ... + z(l-1) * N + z(l).
Das l-tupel (z(1), ..., z(l)) wird ueber das oeffentliche Kommunikations-
system an A geschickt.
A berechnet daraus wieder X1 = z(1) * N^(l-1) + ... + z(l), und dann
X2 := (X1 ^ d(A)) mod m(A). Es gilt: X2 = X.
Aus X berechnet A die Zahlen y(1), ..., y(k) mit
X := y(1) * N^(k-1) + y(2) * N^(k-2) + ... + y(k-1) * N + y(k)
und hat damit (y(1), ..., y(k)) zurueckgewonnen, und kann die Original-
nachricht daraus zusammensetzen.
Anmerkung:
Die Gesamtnachricht setzt sich aus den Kodierungen aller k-tupel der
Originalnachricht zusammen. Die Nachricht verlaengert sich beim kodieren
also um das l/k-fache. Zum Kodieren ist die Kenntnis der Zahlen m(A),
e(A), k, l, und N sowie die Kodierung der Zeichen im Alphabet notwendig.
m(A) und e(A) haben jeweils ca. 200 Stellen und sind somit nur schweer zu
merken, oder ueberall fuer jeweils alle Benutzer zu speichern.
(3) Identifizierung von Nachrichten
Jeder Teilnehmer erhaelt eine Signatur (g(1), ..., g(k)) aus Zeichen des
Alphabets zugewiesen, die ihn eindeutig identifiziert (z. B. der
Username), und die veroeffentlicht ist. B moechte mit seiner Botschaft an A
einen Beweis dafuer mitschicken, da die Botschaft von ihm kommt. B
berechnet mit seiner eigenen Signatur:
s := g(1) * N^(k-1) + g(2) * N^(k-2) + ... + g(k-1) * N + g(k) und
s1 := (s ^ d(B)) mod m(B) und ermittelt daraus die h(1),.. h(l) mit
s1 = h(1) * N^(l-1) + h(2) * N^(l-2) + ... + h(l-1) * N + h(l)
und schickt (h(1),..., h(l)) mit seiner Botschaft an A. A dechiffriert,
wie in (2) beschrieben die eingegangenen l-tupel. Alle ergeben sinnvollen
Klartext au er h(1),..., h(l). Hiermit berechnet er wieder
s1 := h(1) * N^(l-1) + h(2) * N^(l-2) + ... + h(l-1) * N + h(l) und
s := (s1 ^ e(B)) mod m(B)
A schreibt s als:
s = g(1) * N^(k-1) + g(2) * N^(k-2) + ... + g(k-1) * N + g(k)
und hat damit (g(1), ..., g(k)) berechnet und vergleicht mit der
veroeffentlichten Signatur im Telefonbuch.
Anmerkung:
Dieses Verfahren klappt nur dann, wenn man die Position der h(1), ...,
h(l) in der verschluesselten Datei nicht im Vorraus ermitteln kann, und
wenn B seine Identitaet bereits anderswo in der verschluesselten Datei
andeutet. So bietet die hier beschriebene Methode eine Moeglichkeit, das
Dokument zu "unterschreiben", so dass nicht jeder diese Unterschrift unter
ein mit falschem Absender versehenen Brief schreiben kann. Wenn die Zahlen
h(1), ..., h(l) jedoch einem dritten bekannt werden, so ist das Verfahren
hinfaellig. Ausserdem muss B seine Identitaet anderswo im Dokument angeben,
weil sonst der Empfaenger alle Moeglichkeiten fuer verschiedene Absender
durchgehen muss.
(4) Sicherheit
Die Sicherheit des Systems beruht darauf, dass es (noch) keinen schnellen
Algorithmus zur Faktorisierung grosser natuerlicher Zahlen gibt. Um eine an
A gerichtete Nachricht zu entschluesseln benoetigt man d(A) und um d(A) zu
berechnen benaetigt man die Faktorisierung von m(A) = p(A= * q(A).
(5) Primzahlen
Zur Herstellung von p(A) und q(A) und e(A) hat men einen Generator von
Zufallszahlen zu verwenden (und einen schnellen Primzahltest)
(6) Zum modernsten Stand
- G. Brassard, Modern cryptology, 1988
- E. Kranakis, Primality and cryptography
- N. Knoblitz, A course in number theory and cryptogrphy
Quelle: Vorlesung ueber Lineare Algebra, Paderborn.
Aus dem Zerberus. Anfragen bitte an ZENTRALE@BIONIC, da ich
dem Namen des Autors verschlammt habe.
-----------------------------------------------------------------------------
|
![[Chaos CD]](../../../images/chaoscd.jpg)
![[ -- ]](../../../images/prev.jpg)
![[ ++ ]](../../../images/next.jpg)
![[Suchen]](../../../images/search.jpg)