Berit Rüdiger Beufliches Schulzentrum Schwarzenberg [email protected] 10, 08340 Schwarzenberg 25. Mai 2000KryptologieSchwarzenberg

Berit Rüdiger Beufliches Schulzentrum Schwarzenberg [email protected] Steinweg 10, 08340 Schwarzenberg

25. Mai 2000 Kryptologie Schwarzenberg

Berufliches Schulzentrum Schwarzenberg Berufliches Schulzentrum Rodewisch

Sächsisches Staatsministerium für Kultus Technische Universität ChemnitzUniversität Dortmund

Einführung der Fachrichtung Informations- und

Kommunikationstechnologie am beruflichen Gymnasium

Berit Rüdiger [email protected]

Berufliches Gymnasium für Informations- und Kommunikationstechnologie

Grundkursfach: Informationsverarbeitung

Lernbereich: Kryptologie

Jahrgangsstufe: 13/1



Gliederung


1. Grundbedrohungen und Sicherheitsmechanismen 4 Std.

2. historische Verschlüsselungsverfahren 6 Std.

3. Kryptologieverfahren (Zero Knowledge Proof) 4 Std.

Klausur 2 Std.

16 Std.


Ziele des Lernbereichs


• Angriffsmöglichkeiten und Risiken für IuK-Systeme

• Sicherheitsmechanismen Sicherheitsdienste

• zugrundeliegende Prinzipien (keine speziellen math. Algorithmen)

• COMPUSEC + COMSEC Sicherheitspolitik (Security Policy)


1.1 Grundbedrohungen



Grundbedrohungen

Unbefugter Informationsgewinn

Verlust derVertraulichkeit

Unbefugte Beeinträchtigung der

Funktionalität

Verlust derVerfügbarkeit

Unbefugte Modifikation von

Information

Verlust derIntegrität

Weitere Gefahren: Verlust der Anonymität Verlust der Originalität



1.2 Sicherheitsmechanismen




Authentifikation (Wer bin ich?)

Eine Authentifikation besteht aus einer Identifikation und einer sich anschließenden Verifikation.

Die Identifikation geschieht durch Angabe einer Identität (wer/was will ich sein?).

Die Verifikation geschieht durch Überprüfung eines zu der angegebenen Identität gehörenden Merkmals (wer/was bin ich?)

Sicherheitsmechanismen

Authentifikation auf der Basis von Wissen (Zero knowledge proof)

Authentifikation auf der Basis von Besitz

Authentifikation auf der Basis biometrischer Eigenschaften



Zugriffskontrolle (Darf ich das tun?)

Unter Zugriffskontrolle versteht man die Verwaltung und Überprüfung von Zugriffsrechten, damit nur autorisierte Personen auf Objekte zugreifen können und auch das nur auf eine festgelegte Art und Weise.


Zugriffskontrolle durch Referenz-Monitor

Zugriffskontrolle durch Zugriffsmatrizen



Vertraulichkeit (Darf ich das wissen?)

Unter Vertraulichkeit versteht man die Geheimhaltung von Existenz oder Inhalt gegenüber Unbefugten. Zur Realisierung der Vertaulichkeit werden kryptografische Verfahren zur Ver- und Entschlüsselung eingesetzt.


Vertraulichkeit durch symmetrische Kryptosysteme

Vertraulichkeit durch asymmetrische Kryptosysteme



Datenintegrität (Kann ich das unterschreiben?)

Unter Datenintegrität versteht man die Unversehrtheit von Daten, die Echtheit eines Dokuments und die Authentizität des Urhebers.


Datenintegrität durch elektronische Unterschrift

Datenintegrität durch kryptografische Prüfsummen



Kommunikationsnachweis (Kann ich das garantieren?)

Unter Kommunikationsnachweis versteht man Verfahren zur Realisierung von „Einschreiben“ bzw. „Einschreiben mit Rückschein“, die garantieren, dass der Sender die Daten gesendet hat bzw. dass der Empfänger die Daten unverändert empfangen hat.


Sendenachweis durch Proof of Origin

Kommunikationsnachweis durch ein Notariat (Trusted Third Party)


2. Historische Verschlüsselungsverfahren


2.1 Begriffe

2.2 Die Skytale von Sparta

2.3 Transpositionen

2.4 Substitutionen (Verschiebechiffren)

2.4.1 Monoalphabetische Substitution

2.4.2 Polyalphabetische Substitution

2.5 Steganografie


2.1 Begriffe (1)


Griechische Herkunft der Begriffe Kryptologie und Kryptografie (geheim) (das Wort, der Sinn) (schreiben)

Kryptologie bezeichnet die Kunst und die Wissenschaft, die sich damit beschäftigt, Methoden zur Verheimlichung von Nachrichten zu entwickeln.

Kryptologie = Kryptografie + Kryptoanalyse


2.1 Begriffe (2)


Die Nachricht, die übermittelt werden soll, heißt: Klartext

Die verschlüsselte Nachricht, die tatsächlich übermittelt wird, heißt: Geheimtext (Kryptogramm)

Die Ver- bzw. Entschlüsselung heißt: Chiffrieren bzw. Dechiffrieren

Der Schlüssel liefert die exklusive Information für die Entschlüsselung.Der Klartext ist aus Buchstaben zusammengesetzt, die alle zu einem Alphabet gehören, z. B. Auto {a, b, ..., z, A, B, ...,Z}.

Der Geheimtext ist ebenfalls aus Buchstaben zusammengesetzt, die alle zu einem Alphabet gehören, z. B. {}.


2.2 Die Skytale von Sparta


500 v.u.Z. (berichtet Historiker Plutarch)

Regierung von Sparta an ihre Generäle

Klartext: Buchstabenfolge auf einem Band aus Pergament

Schlüssel: Zwei Zylinder mit gleichem Radius

Zum Beispiel: SIEIYHITIEPICINLTEHSZDO!ETIEGRDGRRHAEKAESZRP

r = 5 Buchstaben: SHPLZTDASIIITDIGEZETCEOERKRIIIH!GRAPYENSERHE

r = 6 Buchstaben: SICHERHEITISTDASEINZIGEZIELDERKRYPTOGRAPHIE!


2.3 Transpositionen



2.3 Transpositionen (1)


Krebs: Die Nachricht wird wortweise oder ganz rückwärts gelesen.

z. B.: NIE SBERK MI LIRPA, LIPRA MI SBERK NIE

Ananyme:

z. B.: REMARQUE für Kramer

Eine Transposition ist eine Codierung, bei der nicht die Buchstaben, sondern deren Plätze im Wort ausgetauscht werden.

Palindrome: Worte oder Sätze, die unter Krebs invariant sind.

z. B.: Salomon las Plaudere du Alp Oh Cello voll Echo

Schüttelreim: harmlose, nichtkryptographische Verwendung

z. B.: schwarzen Wein Riesenfächer Reine Sache




Würfel: Nach Wahl einer Katenlänge wird der Text waagerecht in einen Würfel eingelesen und senkrecht ausgelesen.

Spaltentransposition: Der Text wird wie beim Würfel eingelesen, aber in vorgegebener Reihenfolge senkrecht ausgelesen.

z. B.: D O S AO R E RK E N TT I B .

D O K TO R E IS E N BA R T .

Reihenfolge: Spalten 2,1,4,3

O R E R D O S A T I B . K E N T

Variante de Richellieu: Der Text wird wie beim Würfel eingelesen, aber in vorgegebener Reihenfolge waagerecht ausgelesen.z. B.: D O K T

O R E IS E N BA R T .

Reihenfolge: Spalten 2,1,4,3

O D T K R O I E E S B N R A . T

O D T KR O I EE S B NR A . T




Doppelte Spaltentransposition (US Army Version):

Anagramme: Aus allen angegebenen Zeichen wird die Nachricht rekonstruiert.

z. B.: Marguerite Crayencourt Marguerite Yourcenar

O R E RD O S AT I B .K E N T

1.Schlüssel 2,1,4,3O R E R D O S A T I B . K E N T

D O K TO R E IS E N BA R T .

2. Schlüssel 2,1,4,3R O I E O D T K R A . T E S B N

z. B.: a1 c1 d1 e2 h1 k1 l1 n2 o1 r1 s2 u1 w1 es war schon dunkel

Anagramme haben keine Unizitätslänge, d.h. sie sind nicht eindeutig.

Jonathan Swift „Gullivers Reisen“: abeeeghhhhijlmooooprrrsstttttuuOUR BROTHER TOM HATH JUST GO THE PILESRESIST - A PLOT IS BROUGHT HOME - THE TOUR


2.4 Substitutionen

2.4.1 Monoalphabetische Substitution

2.4.2 Polyalphabetische Substitution



2.4.1 Monoalphabetische Substitutionen (1)


100 bis 44 v.u.Z.

römischer Feldherr und Staatsmann C. Julius Caesar

Klartext: abcdefghijklmnopqrstuvwxyz

Schlüssel: 3 Stellen nach links verschieben

Geheimtext: DEFGHIJKLMNOPQRSTUVWXYZABC

Caesar sprach:

ORPHO HVW RPHO

Caesar meinte:

nomen est omen

Geheimtext:

HFIFJNOJT

Schlüssel:

1 Stelle nach rechts

Klartext:

geheimnis




Über dem natürlichen Alphabet gibt es genau 26 Verschiebechiffren

ABCDEFGHIJKLMNOPQRSTUVWXYZBCDEFGHIJKLMNOPQRSTUVWXYZACDEFGHIJKLMNOPQRSTUVWXYZABDEFGHIJKLMNOPQRSTUVWXYZABCEFGHIJKLMNOPQRSTUVWXYZABCDFGHIJKLMNOPQRSTUVWXYZABCDEGHIJKLMNOPQRSTUVWXYZABCDEFHIJKLMNOPQRSTUVWXYZABCDEFGIJKLMNOPQRSTUVWXYZABCDEFGHJKLMNOPQRSTUVWXYZABCDEFGHIKLMNOPQRSTUVWXYZABCDEFGHIJLMNOPQRSTUVWXYZABCDEFGHIJKMNOPQRSTUVWXYZABCDEFGHIJKLNOPQRSTUVWXYZABCDEFGHIJKLMOPQRSTUVWXYZABCDEFGHIJKLMNPQRSTUVWXYZABCDEFGHIJKLMNOQRSTUVWXYZABCDEFGHIJKLMNOPRSTUVWXYZABCDEFGHIJKLMNOPQSTUVWXYZABCDEFGHIJKLMNOPQRTUVWXYZABCDEFGHIJKLMNOPQRSUVWXYZABCDEFGHIJKLMNOPQRSTVWXYZABCDEFGHIJKLMNOPQRSTUWXYZABCDEFGHIJKLMNOPQRSTUVXYZABCDEFGHIJKLMNOPQRSTUVWYZABCDEFGHIJKLMNOPQRSTUVWXZABCDEFGHIJKLMNOPQRSTUVWXY




Wie lassen sich Verschiebechiffren „knacken“?

1. Systematisches Durchprobieren aller Möglichkeiten, bis eine sinnvolle Lösung entsteht.

Aufwand kann reduziert werden, indem nur ein kurzes Wort analysiert wird.

Im Deutschen gibt es nur wenige zweibuchstabige Worte:

im, um, an, am, wo, du, er, es, ... (immer genau ein Vokal!)

Zum Beispiel: QUSSK SUXMKT GT! Komme morgen an!

z. B.: Der Einfluss von Ozon auf die Zebras Zentralzaires

oder: Die amourösen Aventüren des Balthasar Matzbach am Rande des Panamakanals.




z. B.: Der Einfluss von Ozon auf die Zebras Zentralzaires

oder: Die amourösen Aventüren des Balthasar Matzbach am Rande des Panamakanals.

2. Statistische Analyse

Die Buchstaben im deutschen Alphabet kommen mit unterschiedlicher Häufigkeit in unserer Sprache vor. (ERNSTL)

Ebenfalls sind Buchstabengruppen nicht gleichverteilt. (EI, YX)

Das Gleiche gilt für andere natürlichen Sprachen auch.

Die statistische Analyse ist automatisierbar und geht schneller. Man benötigt jedoch ausreichend lange Geheimtexte, damit der Inhalt nicht die Statistik verwischt.


2.4.2 Polyalphabetische Substitution (1)


Bei der polyalphabetischen Substitution wird nicht stets derselbe Klartextbuchstabe mit demselben Geheimtextbuchstaben verschlüsselt.

1. Verschleierung der Häufigkeit

Jedem Klartextbuchstaben (z. B.: natürliches Alphabet) wird eine Menge von Geheimtextbuchstaben (z. B.: Zahlen 00-99) zugeordnet. Bei der Chiffrierung wird aus dieser Menge zufällig ausgewählt.

So hergestellte Geheimtexte sind trotzdem nicht vor der Kryptoanalyse sicher, denn es lassen sich aus Paaren von Geheimtextzeichen Informationen gewinnen.


2.4.2 Polyalphabetische Substitution (2)


2. Vigenère-Chiffre

1586 vom franz. Diplomat Blaise de Vigenère (1523 - 1596)Johannes Trithemius (1462 - 1516)Giovanni Battista Della Porta (1538 - 1615)

Die Idee besteht darin, dass unterschiedliche monoalphabetische Chiffrierungen im Wechsel benutzt werden.

Man benötigt ein Schlüsselwort und ein Vigenère-Quadrat.

Diese Chiffre zu entschlüsseln ist erheblich schwieriger aber nicht unmöglich (seit 1863).

preußischer Infanteriemajor Friedrich Wilhelm Kasiski (1805 - 1881)Colonel William Frederick Friedman (1891 - 1969)


2.5 Steganografie



2.5 Steganografie (1)


Die Steganografie ist die Kunst des verdeckten Nachrichtenaustauschs.

Bei Transposition und Substitution handelt es sich um Krytologiever-fahren, deren Geheimtext und Chiffrieralgorithmen öffentlich sind und trotzdem die Nachricht nur für Eingeweihte lesbar ist. Die Steganogra-fie dagegen versteckt sowohl Nachricht als auch Algorithmus.

Begriff:Johannes Trithemius (1462 - 1516) - verdecktes Schreiben Caspar Schott (Nürnberg 1665) - gleichbedeutend mit Kryptologie

Kryptografien sind für den Unbefugten unverständlich! offene Geheimschriften

Steganografien verheimlichen ihre Existenz! gedeckte Geheimschriften




1. Linguistische Steganografie

Die geheime Nachricht wird offen übertra-gen und erhält Blender oder Füllzeichen.

Gedicht in Bi-Sprache:

Die geheime Nachricht ist in grafischen Details einer Schrift oder Zeichnung enthalten (Semagramm)

Ibich habibebi dibich,Lobittebi, sobi liebib.Habist aubich dubi mibichLiebib? Neibin, vebirgibib.

Nabih obidebir febirnGobitt seibi dibir gubit.Meibin Hebirz habit gebirnAbin dibir gebirubiht.

(Joachim Ringelnatz)




Echtes Semagramm




2. Technische Steganografie

• Geheimtinten: Zitronensaft, Milch

• Doppelte Böden, hohle Absätze, Geheimfächer ect.

• „Macrodot“ des Histiaeus

• Microdots: Mikrofotografie von Ø=0,5 mm verbirgt 1 DIN A4-Seite

• Schnelltelegrafie: vorgespeicherter Morsecode mit 20 Zeichen /s

• Frequenzbandpermutation

• Bildpinktmanipulation




Bilder bestehen aus einer Folge von Bildpunkten (Pixeln).

Für jedes Pixel lässt sich der RGB-Wert in hexadezimalweise angeben.

Lösung: Wähle 8 Bildpunkte!

Aufgabe: Verstecke das Zeichen S in einem Bild! 01010011

FFFFFF 070707 F0E0A7 F0E0A7 E0FF0B 90A000 000000 9010A0

FF 07 F0 F0 E0 90 00 90

Wähle das niederwertigste Bit eines Farbanteils! Rot

1111 0000 1111 1111 1110 1001 0000 10011111 0111 0000 0000 0000 0000 0000 0000

Kombiniere die Bitfolge mit dem geheimen Zeichen!1111 0000 1111 1111 1110 1001 0000 10011110 0111 0000 0001 0000 0000 0001 0001


Kryptologieverfahren

Wahlthemen:

• symmetrische Kryptosysteme

• asymmetrische Kryptosysteme

• elektonische Unterschrift

• zero knowledge Verfahren


• weitere Verfahren

• zero knowledge Verfahren


3. Zero Knowledge Verfahren (1)


Passworte werden häufig zur Authentifikation von Nutzern eingesetzt und dazu häufig als Klartext im Netz versendet. Um jedoch Authentifikationen absolut sicher zu machen, benötigt man einen Zero Knowledge Proof (Null-Kenntnis-Prüfung).

2. der Prüfer (Verifizierer), der die Richtigkeit der Eingabe prüft.

Da ZKP-Verfahren nicht nur für Passwörter gelten, sprechen wir ganz allgemein von Geheimnissen.

1. der Beweiser (Prover), der sich mit einem Passwort identifiziertGeheimnis

Grundidee: Bei der Abfrage eines Passworts gibt es zwei Beteiligte, Geheimnis

ABER: Der Verifizierer darf das Passwort nicht kennen!!!Geheimnis




Ein ZKP basiert auf komplexen mathematischen Zusammenhängen. Das Prinzip soll an einigen Beispielen erläutert werden.

2. Das Urnenmodell

4. Das Geheimnis des Tartaglia

3. Das Knotenpunktspiel

1. Münzwurf per Telefon unfair, kein ZKP

fair, kein ZKP

fair, kein ZKP

fair, echter ZKP

5. Die magische Tür des Ali Baba fair, echter ZKP




ZKP-Protokolle dienen zur Sicherung von Integrität und Authentifikation, indem der Beteiligte A (Beweiser) den Beteiligten B (Prüfer) davon überzeugt, ein Geheimnis zu kennen, ohne es preiszugeben.

Das ZKP-Protokoll gilt dann als sicher, wenn der Aufwand zur Aufdeckung des Geheimnisses unverhältnismäßig größer ist als der Informationsgewinn.

Eigenschaft, dass zu jedem gegebenen Geheimtext nur mit unvorstellbar großem Aufwand möglich ist, sein Urbild zu berechnen.

Eine Einwegfunktion ist eine umkehrbare Funktion mit der




Das Quadratwurzelspiel

Beweiser kennt die Zahl s und will den Prüfer davon überzeugen, ohne die Zahl zu verraten!

Prüfung: r2 MOD 35 = 1181 MOD 35 = 11 w. A.

s2 MOD 35 = 4r2 MOD 35 = 11

Kopf: Wie groß ist r?

r = 9

Prüfer und wirft Münze




Das Quadratwurzelspiel

Beweiser kennt die Zahl s und will den Prüfer davon überzeugen, ohne die Zahl zu verraten!

s2 MOD 35 = 4r2 MOD 35 = 11

Zahl: Wie groß ist r . s MOD 35?

r . s MOD 35 = 3 Prüfung: r2 . s2 MOD 35 = 32 MOD 354 . 11 MOD 35= 9 MOD 359 = 9 w. A.

Prüfer und wirft Münze




Das Fiat-Shamir-Protokoll (Verallgemeinerung des Quadratwurzelspiels)

1986 Protokoll zur Rechner-Rechner Authentifikation von den israelischen Mathematikern Adi Shamir und Amos Fiat.

s2 MOD n = vr2 MOD n = x

Bit = 0: Wie groß ist y = r MOD n?

r MOD n = y Prüfung: y2 MOD n = r2 MOD n = x

Wählt ein Bit

r . s MOD n = y Prüfung: y2 MOD n = r2 . s2 MOD n = x . v MOD n

Bit = 1: Wie groß ist y = r . s MOD n?




Das Fiat-Shamir-Protokoll (Verallgemeinerung des Quadratwurzelspiels)

Die Sicherheit des Protokolls beruht darauf, dass es ausserordentlich schwierig ist, eine Zahl s zu bestimmen für die gilt: s2 MOD n = v.

Die öffentliche Zahl n wird lange vor der Authentifikation mit dem ZKP in der „Schlüsselzentrale“ gebildet als Produkt aus zwei geheimen Primzahlen.

In der Praxis hat n etwa 200 Dezimalstellen (das entspricht in normaler Schriftgröße einer Länge von ca. 1 m).


Literatur


Bauer, F. L.: Kryptologie. Methoden und Maximen. Springer Verlag Berlin, 1994, 2. Auflage

Beutelspacher, A.: Kryptologie. Fried. Vieweg & Sohn Verlagsgesell-schaft mbH, Braunschweig, Wiesbaden, 1992, 3. Auflage.

Hoster, P.: Sicherheitsmechanismen. Datenschutz und Datensicherheit. 9/1993, S. 511 - 519.

Interessante Artikel in LOG IN, Jg. 16, Heft 5/6 (1996).

Kuhn, M.: Steganografie - die Hintertür für den Lauschangriff?. In: Computer und Unterricht 31/1998.


Berit Rüdiger Beufliches Schulzentrum Schwarzenberg [email protected] Steinweg 10, 08340 Schwarzenberg

Berufliches Schulzentrum Schwarzenberg Berufliches Schulzentrum Rodewisch

Sächsisches Staatsministerium für Kultus Technische Universität ChemnitzUniversität Dortmund

Manche Menschen benützen ihre Intelligenz zum Vereinfachen, manche zum Komplizieren.

(Erich Kästner)

Bildung ist das was bleibt, wenn man alles vergißst, was man einmal gelernt hat. (B. F. Skinner)

Documents

Berit Rüdiger Beufliches Schulzentrum Schwarzenberg [email protected] 10, 08340 Schwarzenberg 25. Mai 2000KryptologieSchwarzenberg