kopf
brlogo
fensterobenrechts
   
   
fensteruntenblau
   
 

 

Grundlagen der Kryptologie

 

5. Asymmetrische Verschlüsselung

 

Die Analyse der bisher analysierten Verfahren zeigen, dass diese für die heutigen Probleme nicht brauchbar sind. Für das Online-Banking müssten entsprechend den Benutzern genügend Schlüssel verteilt werden. Um ein solches Verfahren praktikabel zu machen, muss mit zwei verschiedenen Schlüsseln gearbeitet werden. Einem zum Chiffrieren und einem zum Dechiffrieren.

Das Verfahren soll an einem einfachen Beispiel erläutert werden:

   Die Botschaft ICH LIEBE DICH soll mit dem "open key – Verfahren" ver- und entschlüsselt werden.

   Der öffentliche Schlüssel ist das Telefonbuch von Düsseldorf.

   Man sucht im Telefonbuch einen Eintrag, der mit I beginnt und notiert die Telefonnummer:

   Igel 2988176

   Nun wählt man einen mit C

   Christen 8966578

      usw.

   Die verschlüsselte Botschaft ist nun eine Folge von Telefonnummern.

 

Um die Botschaft zu entschlüsseln benötigt man ein Spezialtelefonbuch, das nach Nummern sortiert ist. Nun ist es kein Problem mehr, die Nachricht zu entschlüsseln, denn zwischen Telefonnummer und Name besteht eine eindeutige Zuordnung.

Hier wird vorausgesetzt, dass nur der Empfänger der Botschaft das Spezialtelefonbuch besitzt. Ohne diese Sonderausgabe ist es für einen anderen sehr schwer, die Botschaft zu entschlüsseln. Dieser öffentliche Schlüssel ist heute nicht mehr zu gebrauchen, da es elektronische Ausgaben der Telefonbücher existieren. Dennoch kann man die Begriffe "privater" bzw. "öffentlicher" Schlüssel hier klar herausarbeiten.

Für eine Person, die das Spezialtelefonbuch nicht besitzt, ist die Kenntnis des öffentlichen Schlüssels wenig hilfreich, denn er hat sehr viele Nummern (ca. 500.000 Einträge) zu vergleichen. Es ist also völlig ungefährlich die Methode der Ver- und Entschlüsselung zu veröffentlichen.

Der öffentlicher Schlüssel ist das Telefonbuch.

Der private Schlüssel ist die Spezialausgabe.

Die Grundidee der Public-Key-Methode ist die Verwendung von Einwegfunktionen mit Hintertür (One-Way-Function with Trapdoor). Die bedeutet, dass eine Funktion nur mit der Kenntnis eines zusätzlichen Geheimnisses umkehrbar wird.

Bei einem asymmetrischen Kryptosystem wird jedem Teilnehmer T ein öffentlicher Schlüssel c=cT und ein privater Schlüssel d=dT zugeordnet. Dabei ist nur der private Schlüssel geheimzuhalten.

Die Verschlüsselungsfunktion f ordnet unter dem öffentlichen Schlüssel c jedem Klartextzeichen x eindeutig ein Geheimzeichen y = f(x,c) zu. Umgekehrt ordnet die Entschlüsselungsfunktion f* unter dem zugehörigen privaten Schlüssel d einem Geheimtextzeichen das Klartextzeichen x = f*(y,d) zu.

 

y = f(x,c) Þ f*(y,d) = x

 

Im Jahr 1976 haben Diffie und Hellmann ein solches Verfahren beschrieben. 1977 haben Rivest, Shamir und Adleman ein praktikables Verfahren beschrieben. Das Verfahren wird nach den Anfangsbuchstaben ihrer Namen als RSA-Methode bezeichnet. Das Verfahren wurde patentiert.

Im Unterricht ist das Verfahren von ELGamal vorzuziehen, da es etwas weniger mathematische Kenntnisse erfordert.

Der Vorgang verläuft in drei Schritten:

 

  1. Schlüsselvergabe
  2. Chiffrierung
  3. Dechiffrierung

 

Zunächst wird eine Primzahl p und eine natürliche Zahl g mit 1 < g < p gewählt. Beide sind öffentlich bzw. werden in einer Benutzergruppe festgelegt.

Der private Schlüssel (Dechiffrierschlüssel) des Teilnehmers ist irgendeine natürliche Zahl d mit 1 < d < p. Diesen verwahrt der Teilnehmer an einem sicheren Ort.

Der öffentliche Schlüssel des Teilnehmers ist dann c = MOD (gd,p)

 

Beispiel:

p = 13, g = 4, d = 5

Für c ergibt sich dann: c = MOD (gd,p) = MOD(45,13) = MOD(1024,13) = 10

Wenn A einem Teilnehmer B eine chiffrierte Nachricht senden will, wird wie folgt verfahren:

 

  • A schlägt den öffentlichen Schlüssel c von B im Schlüsselverzeichnis nach.
  • A wählt zufällig eine natürliche Zahl a < p – 1 und berechnet die Entschlüsselungshilfe

h = Mod(ga,p)

  • Zum (etwa mittels ASCII numerisch dargestellten) Klartext x < p wird der Geheimtext

y = Mod(x· ca,p)

berechnet.

  • Das Paar (h,y) wird dem Teilnehmer B zugesendet.

 

Beispiel:

c = 10 ist der öffentliche Schlüssel.

A wählt die Zahl a = 3,

Die Entschlüsselungshilfe: h = Mod(43,13) = 12,

Der Geheimtext wird mit Hilfe von x = 9 berechnet.

y = Mod(x· ca,p)=Mod(9· 103,13) = 4

Dem Empfänger B wird das Paar (12,4) gesendet.

Dechiffrierung

Der Empfänger der Nachricht (h,y) = (12,4) berechnet

x = Mod(y· hp-1-d,p)

 

Beispiel:

x = Mod(y· hp-1-d,p) = Mod(4· 1213-1-5,13) = Mod(4· 127,13) = 9

Ein kleiner nicht vollständiger Beweis kann folgendermaßen dargestellt werden:

Gegeben ist die endliche Menge F*p = {1, 2, 3, .. p-1}, in der man modulo p-1 multiplizieren und potenzieren kann.

Sei gx = Mod(gx,p). Dann ist c = gd , h = ga , und y = x· ca und es gilt:

y· hp-1-d = (x· ca)(ga)p-1-d = x· (gd)a· ga(p-1) · g-ad = x· (gad· g-ad) · (gp-1)a = x· 1· 1 = x

In der Menge F*p gilt die sogenannte kleine Fermat-Gleichung: gp-1 = 1

 

Schema der ELGamal-Verschlüsselung:

krypto13.gif (3779 Byte)

 

Wie man aus der Berechnung leicht ablesen kann, ist das Verfahren im Bereich von Longint kaum anwendbar. Bereits die Wahl von p = 23 führt schnell zu Problemen, wenn man die Zeichen über den ASCII-Code verschlüsselt.

Da bei den modernen Verfahren die Primzahlen eine zentrale Rolle spielen, sollte man in diesem Zusammenhang entsprechende Algorithmen besprechen.

 

  • Erzeugung von Primzahlen
  • Zu einer gegebenen Zahl die nächste Primzahl bestimmen
  • Primfaktorzerlegung
  • Potenzierung modulo n (siehe [7])

 

Ob man hier die klassischen Algorithmen wie Sieb des Erathostenes etc. bespricht oder schnelle Algorthmen (stochastischer Algorithmus [7], [6]) ist jedem selbst überlassen. Ohne einen leistungsfähigen Algorithmus zur Potenzierung modulo n wird man an den Programmen wenig Freude haben. Bei entsprechenden Vorkenntnissen der Schüler kann man ein Programm für das Rechnen mit grossen Zahlen (lineare Listen) entwickeln und integrieren. Gerade bei diesen Anwendungen zeigt sich, dass man mit den klassischen Algorithmen in der Praxis nicht besonders viel anfangen kann.

 

Hilfreiche Algorithmen

1. Funktion um ab modulo n zu berechnen:

function hochmod (basis,exponent: Longint; n: Integer): Longint;

 

Algorithmus:

  1. Schritt
  2. Wandle den Exponent in eine Dualzahl um

  3. Schritt
  4. Setze h = 1

  5. Schritt

Setze i = Anzahl der Stellen von Exponent k

Wiederhole die folgenden Schritte bis i = k-1 bis 0

  1. h = h*h mod n
  2. Falls ei = 1 dann h = h * basis mod n
  1. Schritt

h ist das Ergebnis von basisexponent modulo n

 

Beispiel:

Es wird 510 modulo 17 berechnet.

Die Binärdarstellung von 10 = 10102

 

ei

i

h

Rechnung

   

1

 

e3 = 1

3

1

5

1 = 1 * 1 mod 17

5 = 1 * 5 mod 17

e2 = 0

2

8

8 = 5 * 5 mod 17

e1 = 1

1

13

14

13 = 8 * 8 mod 17

14 = 13 * 5 mod 17

e0 = 1

0

9

9 = 14 * 14 mod 17

 

2. Prozedur um zu einer natürlichen Zahl n die nächste Primzahl zu berechnen

procedure berechne_primzahl (eingabezahl: Longint; var prim:Longint);

 

3. Prozedur um die Primzahlen bis zu einer natürlichen Zahl n zu berechnen

procedure berechne_primz (grenze: Longint);

 

4. Prozedur zur Primfaktorzerlegung einer natürlichen Zahl n

procedure zerlege (eingabezahl: Longint; var ergebnis: string);

 

Die genannten Algorithmen in Pascal//Delphi-Notation:  Asymmetrisch

 

Programm zum Verfahren von ELGamal

Zugehörige Algorithmen und ein Programmierbeispiel in Pascal//Delphi-Notation:  ElGamal

 

weiter:  RSA-Verschlüsselung

 

 
 
Friday, 24. November 2017 / 17:47:12