K4-Kodierungen

1. Quellkodierung

   • Daten für Übertragung vorbereiten

   • kompakte und redundanzfreie Darstellung

   • Beispiele:

     • Flaggenkode

     • Morsealphabet

     • ASCII

2. Kanalkodierung

   • quellkodierte Daten transformieren, um bei Übertragung auftretende Fehler zu erkennen und zu korrigieren

   • Beispiel:

     • Paritätsbits

3. Leitungskodierung/ Modulation

1. Fehlererkennende Codes

   • im Fehlerfall erneut übertragen

   • sind schlanker, brauchen weniger Redundanz

   • Bsp.:

     • EAN

     • ISBN

     • Kontonummerr

2. Fehlerkorrigierende Codes::

   • wenn erneute Übertragung nicht möglich/ zu teuer ist

   • braucht höhere Redundanz

   • Bsp.:

     • CD-Player

     • Satelitenkommunikation

Es gibt keine Kodierung, die eine kleinere durchschnittliche Codewortlänge hat.

Wenn die Abbildung von Zuständen auf Codeworte injektiv ist

-> Kontrollinformationen hinzufügen

Beispiele aus dem täglichen Leben:

1. buchstabieren

2. Buchstabieralphabete

3. Redundanter Aufbau der natürlichen Sprache

Paritätscode = fehlererkennender Code

Voraussetzung:

• (n-1)-stelle Zahlen zur Basis b übertragen

• Empfänger soll korrekte Übertragung überprüfen können

Parität:

• zusätzlich hinzugefüge Ziffer = Prüfziffer

• die Quersumme der resultierenden n-stelligen Zahl ist durch die Zahlenbasis b teilbar

Paritätscode der Länge n zur Basis b:

• Daten werden im Zahlensystem zur Basis 2 übertragen

• Anzahl der übertragenenen Einsen gerade -> Prüfbit ist 0

• Anzahl der übertragenenen Einsen ungerade -> Prüfbit ist 1

1 Fehler

-> können keine Vertauschungsfehler erkennen

• bei Übertragung werden zwei beliebige Zeichen des Codewortes miteinander vertauscht

Kann man nicht - außer man verwendet Gewichte (Bsp. EAN/GTIN)

GTIN = Global Trade Item Number

• besteht aus 8 bzw. 13 Ziffern inkl. Prüfziffer

• Gewichtung: w.n=1 (Prüfziffer), w.n-1 = 3, w.n-2 = 1, …

• w.n1 = 3 (bei GTIN8) oder w.n1=1 (bei GTIN13)

genau dann, wenn alle Gewichte teilerfremd zu b sind

wenn die Differenz der vertauschten Stellen w.i - w.j teilerfremd zu b

für gerade b gibt es keinen Paritätscode zur Basis b, der alle Einzelfehler und alle Vertauschungsfehler an aufeinanderfolgenden Stellen erkennt

Auch Fehlererkennend

• findet Prüfsequenz fester Länger für Daten beliebiger Länge

• verwendet Restklassenring auf Galoisfeld

erkennt:

• alle Einzelfehler

• jede ungerade Anzahl von Bitfehlern

• alle Bündelfehler (=gehäufte Fehler)

• 
  

• bilden k Eingangsbits (Information) auf n Ausgangsbits (Code) ab

  • k < n

• Zuordnung Information zu Code hängt von bisher codierten Informationen ab

  • -> Kodierer hat internes Gedächtnis

  • Informationen werden auch in Folgezuständen kodiert

  • dadurch leichter wiederherstellbar bei Übertragungsfehlern

• Faltung = Ineinanderschachteln von Informationen

• Bsp. Trellis Diagram

• hier: Nachricht als binäres n-Tupel

  • V := {0, 1}^n oder Vektor des Vektorraums GF(2)^n

• Problem: Kanal addiert (modulo 2) zum ges. Vektor c einen Fehlercode e

  • Empfänger erhält: x = c + e

• Empfänger soll Originalvektor c aus x bestimmen

v = (v.1, .., v.n), w = (w.1, …, w.n)

Abstand d(v, w) = Anzahl der Stellen an denen sich v und w unterscheiden:

eine Abbildung d: M x M -> R (eine Abstandsfunktion), wenn für alle u, v, w in M gilt:

1. d(u, v) >= 0 - es gibt keine negativen Abstände

2. d(u, v) = 0, g.d.w u = v - jedes Element hat nur zu sich selbstt den Abstand 0

3. d(u,v) = d(v,u) - Hin- und Rückweg zwischen zwei Elementen ist gleich lang

4. d(u,v) <= d(u,w) + d(w, v) - der direkte Weg zwischen zwei Elementen ist nie länger als der Umweg über in drittes Element

• t eine natürliche Zahl

• Eine Teilmenge C von V = {0, 1}^n ist ein t-fehlerkorrigierender Code,

  • wenn für alle möglichen Paarungen v, w in C gilt:

• anders: der Minimalabstand von C mindestens 2t + 1 ist:

Beispiel:

• geg.: 2^m verschiedene Quellzeichen der Länge m, D.1, D.2, …

• ges.: Codezeichen der Länge n = m +r durch r Zusatzbits

• Annahme:

  • höchstens 1 Bit wird bei der Übertragung verfälscht

  • für jedes Quellzeichen gibt es 1 korrektes und n fehlerhafte Codezeichen

  • Codezeichen-Menge umfasst (n+1)x2^m <? 2^n Zeichen

• Grundgedanke: verteile Prüfbits so, dass jedes Datenbit in mindestens 2 Prüfbits berücksichtigt wird

• jedes bit im Codewort erhält eine fortlaufende Nummer beginnend mit 1

  • Positionierungsnummern werden binär dargestellt

  • Codewort besteht zunächst aus Quellwort

• k-tes Paritätsbit an Position 2^k einordnen

  • binäre Darstellung der Position hat (von rechts gesehen) das k-te Bit gesetzt (alle anderen Bits sind 0)

• Wert des k-ten Paritätsbits = Quersumme aller Bits des Codeworts, deren Position in der binären Darstellung das k-te Bit gesetzt haben

• auf Empfängerseite Paritäten prüfen

• stimmt alles? -> dann Codewort akzeptieren

• nein? -> inkonsistente Paritätsbits betrachten

• es gibt nur Einzelfehler

  • die betreffen Paritätsbits oder Datenbits

  -> 2 Fehler:

  1. ein Paritätsbit passt nicht

     • Paritätsbit selbst wurde verfälscht

     • sonst würden 2 Paritätsbits nicht stimmen

  2. mehrere Paritätsbits sind nicht konsistent

     • ein Datenbit wurde verfälscht

     • Summe der Positionsnummern der inkonsistenten Paritätsbits ist Position des verfälschten Datenbits

für Bündelfehler der Länge k

1. Datenwort in k Teilworte gleicher Länge unterteilen

2. Teilworte untereinander schreiben und jedes zu einem Codewort ergänzen

3. Matrix spaltenweise in zusammenhängender Nachricht senden

4. Empfänger arrangiert Nachricht wieder als Matrix

5. Ein Burst der Länge k für ganze Nachricht bedeutet:

   • in jeder Zeile der Matrix kommt höchstens ein Einzehlfehler vor

   • der kann korrigiert werden

   • ursprüngliches Einzelwort kann dann richtig korrigiert werden

Vorwärts = Empfänger erkennt und korrigiert Fehler

Rückwärts = Empfänger erkennt Fehler und Sender korrigiert ihn (z.B. erneutes Senden)

1. Vertrauchlichkeit

   • Information nur für definierte Benutzergruppe

2. Integrität

   • Information gegen beabsichtigte und unbeabsichtigte Verluste und Änderungen schützen

3. Authentizität

   • Identität von Sender und Empfänger eindeutig feststellen

4. Verfügbarkeit

   • Zugriff auf Informationen im Rahmen der Anforderungen stets möglich

• laufende Nummer hinzufügen zu Nachricht

Kriterien/Fragestellungen:

• Länge der Nummer

• Initialisierung der Nummer

• Wiederherstellung nach einer Unterbrechnung der Nachrichtensequenz

• veraltete Informationen können nutzlos werden

• Beziehung zwischen Zeit und Nachricht

• Anstelle oder in Kombination mit Sequenznummern

Fragen:

• Wert und Genauigkeit des Zeitinkrements

• Grüße des Zeitgebers

• absolute Wert des Zeitgebers (UTC)

• Synchronismus der Zeitgeber in verschiedenen Einheiten

• Verzögerung zwischen Nachrichtenerzeugung und hinzufügen des Zeitstempels

• Verzögerung zwischen Prüfung des Zeitstempels und Nutzen der Information

Fehler, wenn Nachrichtenübermittlung einen kritischen Wert überschreitet

• kann vom Sender übernommen werden

• braucht Rückkanal

• Empfänger antwortet mit Bestätigungsnachricht ACK(i)

Fragen:

• maximal zulässige Verzögerung

• Genauigkeit der Zeitüberwachung

Quellbezeichner

• authentifizieren Quelle ohne zusätzlichen Nachrichtenaustausch

• z.B. in unidirektionalen oder Broadcast-Kommunikationssystemen

Zielbezeichner

• für Stationen oder Gruppen

• dienen der logischen Adressierung

• Stationen können ohne Nachrichtenaustausch prüfen, ob Nachricht für sie ist

Fragen:

• Einzigartigkeit des Bezeichners im gesamten Übertragungssystem

• Größe des Bezeichnerdatenfeldes

1. Bidirektionale Identifikation

   • Austausch zwischen Quell- und Zielbezeichner

2. Dynamische Identifikation

   • einschließlich der Umwandlung und Rücknachricht empfangener Informationen

   • Kommunikationsteilnehmer behaupten nicht nur, die richtigen zu sein, sondern verhalten sich auch wie erwartet

• braucht geeigneten Kanal zurück

• enthält:

  • aus Originalnachricht abgeleitete Daten (identisch oder verändert)

  • hinzugefügte Daten aus dem lokalen Nutzerprozess des Empfängers

  • zusätzliche Daten für Sicherheitszwecke

• in offenem System: Übertragungscodes zum Entdecken oder Korrigieren von Bit oder Büschelfehler

  • nicht vertrauenswürdig

• zusätzliche Kodierung, um Verfälschung der Nachricht zu verhindern

Fragen:

• Fähigkeit alle erwarteten Fehlerarten zu entdecken

• Wahrscheinlichkeit, Nachrichtenmanipulation zu entdecken

• um Angriffe innerhalb eines offenen Übertragungssystems zu kontern

• zusammen mit Sicherheitscodierungsverfahren oder separat

• nutzen Schlüssel und Algorithmen

• Wirkung hängt ab von:

  • Geheimhaltung der Schlüssel

    • dessen Länge und sein Management

  • Stärke der Algorithmen

Fragen:

• Technisch:

  • Leistungsfähigkeit des Algorithmus

  • Schlüssellänge

  • Häufigkeit des Schlüsselwechsels

  • Speicherung eines Schlüssels

• Management:

  • Erzeugen, Speichern, Verteilen und Vernichten der Schlüssel

  • Management der Einrichtungen

  • Kontinuierliche Prüfung der kryptographischen Techniken

Beispiele:

• Monoalphabetische Substitution

• Cäsarkodierung (verschiebt Buchstaben nur)

• DES = Data Encryption Standard

  • Blockverschlüsselung auf 64bit Blöcken

  • 16 Iterationsschritte

  • schnelle Hardwareumsetzung

  • schnell zu brechen (wenigen Stunden)

• 3DES

  • Nachfolger von DES

  • wendet DES 3 mal mit drei verschiedenen Schlüsseln an

• AES = Advanced Encryption Standard

  • sicher, trotz bekannter Angriffsvektoren

• IDEA = International Data Encryption Algorithm

• Blowfish, Twofish

• geg.:

  • privater Schlüssel = Paar (N, e)

  • öffentlicher Schlüssel = Paar (N,d)

  • zu verschlüsselnde Nachricht = m < N

Beispiel:

RSA

• Ziel: Integrität einer unverschlüsselten Nachricht nachweisen

• Methode: Nachricht kryptographisch zusammenfassen

• nutzt Hashfunktion:

  • kollisionsfrei - man findet praktisch keine zwei Nachrichten mit demselben Hashwert

  • Unumkehrbarkeit - man kann aus Hashwert nicht auf Nachricht schließen

Verfahren:

1. Sender

   • bildet Hashwert h(m)

   • Sender verschlüsselt Hashwert mit privatem Schlüssel E(h(m))

2. Empfänger:

   • entschlüsselt Hashwert mit öffentlichem Schlüssel des Senders D(E(h(m)) -> h(m)

   • bildet Hashwert h(m)

   • Vergleicht beide Werte

3. bei Gleichheit wurde Nachricht nicht verändert

• Ziel: Identität des Absenders nachweisen

• Idee: Message Digest weist auch die Identität des Absenders nach, weil er mit dessem privaten Schlüssel erstellt wurde

• Zuordung öffentlicher Schlüssel zu Sender über Zertifizierungsstelle