Codierungstheorie - tu-freiberg.dehebisch/skripte/codtheorie/codierung.pdf · je zwei Elementen a;b2S genau ein Produkt ab2S zuordnet, so daˇ das Assoziativgesetz gilt: (2) a(bc)

Codierungstheorie

Udo Hebisch

SS 2020

Dieses Skript enthalt nur den “roten Faden”der Vorlesung. Wesentliche Inhalte werden ausschließlich

in der Vorlesung vermittelt. Daher ist diesesSkript nicht zum Selbststudium gedacht, sondern

nur als “Erinnerungsstutze”.

1

INHALTSVERZEICHNIS INHALTSVERZEICHNIS

Inhaltsverzeichnis

1 Einfuhrung und Motivation 5

2 Freie Halbgruppen und Codierungen 8

3 Eigenschaften von Blockcodes 15

4 Lineare Codes 27

5 Zyklische Codes 41

6 Kryptosysteme 49

7 Perfekt sichere Kryptosysteme 64

8 Data Encryption Standard 67

9 Der RSA-Algorithmus 69

10 Quadratwurzeln modulo n 73

11 Diskreter Logarithmus 76

12 Elliptische Kurven 80

13 Anhang zur Codierungstheorie 83

13.1 ASCII-Code . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 83

13.2 Hexadezimalcode . . . . . . . . . . . . . . . . . . . . . . . . . . . 85

13.3 ISO-7 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 86

13.4 Bacon-Code (um 1580) . . . . . . . . . . . . . . . . . . . . . . . . 87

Vorherige Seite Nachste Seite Zuruck Erste Seite Letzte Seite


13.5 Morse-Alphabet . . . . . . . . . . . . . . . . . . . . . . . . . . . . 88

13.6 Dezimalziffern-Codes . . . . . . . . . . . . . . . . . . . . . . . . . 90

13.6.1 Zahlcode . . . . . . . . . . . . . . . . . . . . . . . . . . . . 90

13.6.2 Tetradencodes . . . . . . . . . . . . . . . . . . . . . . . . . 90

13.6.3 Pentadencodes . . . . . . . . . . . . . . . . . . . . . . . . 91

13.7 Langere Binarcodes . . . . . . . . . . . . . . . . . . . . . . . . . . 92

13.8 CCIT-2 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 93

13.9 Flexowriter . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 95

13.10IBM-Lochkarten-Code . . . . . . . . . . . . . . . . . . . . . . . . 96

13.11EAN-13-Codierungen . . . . . . . . . . . . . . . . . . . . . . . . . 97

13.12Landerkennungen der Euro-Banknoten . . . . . . . . . . . . . . . 98

13.13Prufzifferncodierung der DM-Scheine von 1990 - 2001 . . . . . . . 99

13.13.1 Codierung der Buchstaben . . . . . . . . . . . . . . . . . . 99

13.13.2 Verknupfungstafel der Diedergruppe D5 . . . . . . . . . . 99

13.13.3 Verwendete Permutation und ihre Potenzen . . . . . . . . 99

13.14Prufzifferncode bei Schweizer Einzahlungsscheinen . . . . . . . . . 100

13.15Fehlerhaufigkeiten bei der Ziffernubermittlung . . . . . . . . . . . 101

13.16Eight-To-Fourteen-Modulation (EFM) . . . . . . . . . . . . . . . 102

13.17Irreduzible Polynome . . . . . . . . . . . . . . . . . . . . . . . . . 106

13.17.1 Der Korper GF(8) . . . . . . . . . . . . . . . . . . . . . . 107

13.18Inverse modulo 26 . . . . . . . . . . . . . . . . . . . . . . . . . . . 107



14 Anhang zur Kryptographie 109

14.1 Hexadezimalcode . . . . . . . . . . . . . . . . . . . . . . . . . . . 109

14.2 Bacon-Code (um 1580) . . . . . . . . . . . . . . . . . . . . . . . . 110

14.3 Buchstabenhaufigkeiten . . . . . . . . . . . . . . . . . . . . . . . . 111

14.4 Vigenere-Tafel . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 114

14.5 Irreduzible Polynome . . . . . . . . . . . . . . . . . . . . . . . . . 115

14.5.1 Der Korper GF(8) . . . . . . . . . . . . . . . . . . . . . . 116

14.6 DES . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 117

14.6.1 Verwendete Permutationen/Expansion . . . . . . . . . . . 117

14.6.2 S-Boxen . . . . . . . . . . . . . . . . . . . . . . . . . . . . 118

14.6.3 Rundenschlussel . . . . . . . . . . . . . . . . . . . . . . . . 119

14.7 Quantencodierung . . . . . . . . . . . . . . . . . . . . . . . . . . . 121

14.7.1 Schlusselvereinbarung . . . . . . . . . . . . . . . . . . . . . 121

14.7.2 Abgehorter Quantenkanal . . . . . . . . . . . . . . . . . . 121

14.8 Inverse modulo 26 . . . . . . . . . . . . . . . . . . . . . . . . . . . 122

15 Losungen zu ausgewahlten Aufgaben 123


1 EINFUHRUNG UND MOTIVATION

1 Einfuhrung und Motivation

Bei der Ubertragung von Daten geht man im allgemeinen von folgendem Modellaus. Ein Sender (auch Quelle genannt) erzeugt Nachrichten in Form von Signalen.Handelt es sich dabei um kontinuierliche Signale, spricht man von analoger Da-tenubertragung, handelt es sich dagegen um diskrete Signale, so betrachtet mandie digitale Datenubertragung. Die Nachrichten durchlaufen dann einen Kanalund erreichen letztlich den Empfanger. Auch das Speichern von Daten auf einemMedium, beispielsweise einer CD oder DVD, und das anschließende Herausle-sen kann man mit diesem Modell erfassen. Dabei wird das Speichermedium alsKanal, der Speichervorgang als Senden und der Lesevorgang als Empfang gedeu-tet. Im Rahmen dieser Vorlesung wird ausschließlich die digitale Datenubertra-gung betrachtet und man faßt die einzelnen Signale als Buchstaben oder Symboleaus einem Alphabet auf. Das geeignete mathematische Beschreibungswerkzeug istzunachst die Halbgruppentheorie (vgl. Beispiel 2.3).

Bei dieser Form der Datenubertragung konnen grundsatzlich mindestens die fol-genden beiden Problemkreise auftreten. Einerseits konnen beim Ubertragen derZeichen im Kanal Storungen oder Fehler auftreten, indem einzelne Zeichen (Ein-zelfehler) oder ganze Zeichenfolgen (Fehlerbundel) in andere Zeichen verfalschtwerden, wobei man auch die Ausloschung als Verfalschung in ein geeignetes Sym-bol deuten kann. Man hat also die Aufgabe, den Nachrichten zusatzliche, ei-gentlich uberflussige oder redundante Informationen mitzugeben, sie zu codie-ren. Diese Informationen sollen es dem Empfanger bei der Decodierung gestat-ten, moglichst viele aufgetretene Fehler zu erkennen oder gar zu korrigieren. Mitdiesen Problemen der Fehlererkennung und Fehlerkorrektur (vgl. Definition 3.5)befaßt sich die Codierungstheorie. Da die genannten Storungen in der Regel tech-nisch bedingt sind und zufallig auftreten, wird man zu ihrer Modellierung undBehebung auch wahrscheinlichkeitstheoretische Uberlegungen heranziehen.

Beispiel 1.1 Bei der Ubertragung der auf einer Tastatur darstellbaren Buchsta-ben, Zahlen und Sonderzeichen in den Rechner werden diese Zeichen in der Regelin Bytes umgewandelt oder codiert. Dies sind Folgen aus 8 Bits, wobei jedes Bitentweder eine 0 oder eine 1 ist. Da es genau 28 = 256 verschiedene Bytes gibt,kann man maximal 256 Zeichen auf diese Weise darstellen. Nun existieren auf derTastatur aber weit weniger als 128 verschiedene Zeichen, auch wenn man Groß-und Kleinschreibung unterscheidet. Hiervon macht man Gebrauch, um einfacheUbertragungsfehler erkennen zu konnen. Man ordnet den Zeichen der Tastatur inirgend einer festen Weise, beispielsweise nach dem ASCII-Code (American Stan-dard Code for Information Interchange) gemaß A 7→ 1000001, B 7→ 1000010, . . .,einige der Zahlen von 0 = 0000000 bis 127 = 1111111 zu und ermittelt aus den



sieben Bits c7c6c5c4c3c2c1 dieser Zahlen das fuhrende achte Bit c8 des Bytes alsParitatsbit gemaß

c8 =7∑i=1

ci mod 2.(1)

Ist also die Summe gerade, so wird c8 = 0 berechnet, ist sie ungerade, so wirdc8 = 1 berechnet. Die Summe aller 8 Bits eines codierten Zeichens ist also stetsgerade. Der Empfanger eines derart codierten Zeichens kann (1) wiederum fol-gendermaßen als Kontrollgleichung benutzen. Tritt bei der Datenubertragung angenau einer Stelle ein Fehler auf, d.h. wird genau eine 0 in eine 1 verwandelt oderumgekehrt, so wird das empfangene Byte (1) nicht erfullen und damit als feh-lerhaft erkennbar. Naturlich ist nicht erkennbar, welches Bit umgeklappt wurde,und der aufgetretene Fehler kann nicht korrigiert werden. Es kann aber etwa einenochmalige Ubertragung angefordert werden, sogenanntes ARQ-Verfahren (Au-tomatic Repeat Request). Fugt man dagegen weitere redundante Bits hinzu, sokonnen bestimmte Fehler nicht nur erkannt, sondern sogar automatisch korrigiertwerden, sogenanntes FEC-Verfahren (Forward Error Correction). Man kann auf-grund dieses Beispiels erahnen, daß bei dieser Art der Codierungstheorie LineareAlgebra uber dem Korper Z/(2) oder allgemein uber endlichen Korpern ins Spielkommt (vgl. auch Definition 3.13 und Folgerung 3.14).

Der zweite Problemkreis betrifft die Geheimhaltung der Nachrichten. Der Senderist oft daran interessiert, daß nur ein bestimmter Empfanger die Nachricht ver-stehen kann und ein unbefugter Empfanger oder passiver Angreifer, der ebenfallsden Kanal abhoren kann, nur fur ihn unverstandliche Zeichenfolgen erkennt. Manwird also die Nachricht, den Klartext, nach Moglichkeit so in einen Geheimtextverschlusseln oder chiffrieren, daß nur jemand, der uber einen entsprechendenSchlussel verfugt, den eigentlichen Informationsgehalt der ubertragenen Zeichen-folge erschließen bzw. dechiffrieren kann. Ohne Schlussel soll die Rekonstruktionder ursprunglichen Nachricht extrem unwahrscheinlich sein. Weiterhin soll dieVerschlusselung nach Moglichkeit verhindern, daß ein aktiver Angreifer die Nach-richt des Senders verandert, ohne daß der Empfanger dies bemerkt, die Integritatder Nachricht soll garantiert sein. Daruber hinaus soll die Verschlusselung demEmpfanger eventuell auch die Moglichkeit geben, zu erkennen, ob der Absendertatsachlich der vermutete Sender ist. Dieses Problem betrifft also die Authentifi-kation des Senders. Schließlich sollte es dem Sender auch unmoglich sein, spaterzu leugnen, eine bestimmte Nachricht gesendet zu haben. Die Nachricht sollteverbindlich sein. Alle diese Aspekte der Sicherung von Nachrichten werden inder Kryptographie oder Kryptologie untersucht, mit der sich der zweite Teil derVorlesung beschaftigt. (“Kryptographie” kommt aus dem griechischen κρυπτoσ



= “geheim” und γραϕειν = “schreiben”, in “Kryptologie” steckt noch λoγoσ= “Wort, Wissenschaft, Lehre”.) Hierbei kommt es vor allem auf den Entwurfsicherer Verschlusselungsverfahren oder Kryptosysteme an, wobei hauptsachlichalgebraische und zahlentheoretische Methoden benutzt werden. Bei der Beurtei-lung der Sicherheit von derartigen Verfahren wird man schließlich noch Methodender Komplexitatstheorie anwenden mussen.

Einfuhrende Literatur zur Codierungstheorie

A. Betten et al., Codierungstheorie, Springer-Verlag, 1998. ISBN 3-540-64502-0.

W. Heise, P. Quattrocchi, Informations- und Codierungstheorie, Springer-Verlag,1989. ISBN 3-540-50537-7.

Ernst Henze, Horst H. Homuth, Einfuhrung in die Codierungstheorie, Vieweg,1973. ISBN 3-528-03024-0.

Raymond Hill, A First Course in Coding Theory, Clarendon Press, 1986. ISBN0-19-853803-0.

D. Jungnickel, Codierungstheorie, Spektrum-Verlag, 1995. ISBN 3-860-25432-4.

Werner Lutkebohmert, Codierungstheorie, Vieweg-Verlag, 2003.ISBN 3-528-03197-2.

Ralph-Hardo Schulz, Codierungstheorie. Eine Einfuhrung, Vieweg-Verlag, 2003.ISBN 3-528-16419-0.

Peter Sweeney, Codierung zur Fehlererkennung und Fehlerkorrektur, Hanser-Verlag, 1992. ISBN 3-446-16439-1.

Wolfgang Willems, Codierungstheorie, deGruyter, 1999. ISBN 3-11-015873-6.

Wolfgang Willems, Codierungstheorie und Kryptographie, Birkhauser, 2008.ISBN 978-3-7643-8611-5.


2 FREIE HALBGRUPPEN UND CODIERUNGEN

2 Freie Halbgruppen und Codierungen

In der algebraischen Codierungstheorie werden einige Begriffe und Resultate uberHalbgruppen, Gruppen, Korper und Vektorraume benotigt. Soweit sie in diesemSkript nicht nochmals aufgefuhrt sind, kann man sie in den entsprechenden Skrip-ten zur Linearen Algebra und Klassischen Algebra finden.

Definition 2.1 Unter einer Halbgruppe (S, ·) versteht man eine nichtleere Men-ge S zusammen mit einer binaren Verknupfung (der Multiplikation) ·, die alsoje zwei Elementen a, b ∈ S genau ein Produkt a · b ∈ S zuordnet, so daß dasAssoziativgesetz gilt:

a · (b · c) = (a · b) · c fur alle a, b, c ∈ S.(2)

Besitzt die Halbgruppe ein Einselement e ∈ S gemaß

e · a = a · e = a fur alle a ∈ S,(3)

so spricht man von einem Monoid. Gilt in (S, ·) das Kommutativgesetz

a · b = b · a fur alle a, b ∈ S,(4)

so nennt man die Halbgruppe (das Monoid) kommutativ.

Definition 2.2 Sind a und b Elemente einer Halbgruppe (S, ·) und ist c = a·b ihrProdukt, so nennt man a einen linken Teiler oder ein Prafix und b einen rechtenTeiler oder ein Postfix bzw. Suffix von c.

Beispiel 2.3 Fur eine beliebige Menge X 6= ∅ sei X+ =⋃n∈NX

n. Definiert manfur alle (x1, . . . , xn), (y1, . . . , ym) ∈ X+ eine Multiplikation durch

(x1, . . . , xn) · (y1, . . . , ym) = (x1, . . . , xn, y1, . . . , ym),(5)

dann ist (X+, ·) eine Halbgruppe, die freie Halbgruppe uber X. Man schreibt dieElemente (x1, . . . , xn) ∈ X+ einfach in der Form x1 · · ·xn und die Multiplikationals Konkatenation x1 · · · xny1 · · · ym. Speziell fur endliches X nennt man X einAlphabet, die Elemente x ∈ X Buchstaben und die Elemente x1 · · ·xn ∈ X+


http://www.mathe.tu-freiberg.de/~hebisch/cafe/algebra/gruppoid.html#assoziativ


Worter oder Strings uber X. Adjungiert man zu (X+, ·) ein leeres Wort λ alsEinselement, so nennt man X∗ = X+ ∪ {λ} das freie Monoid uber X. Ist w =x1 · · ·xn ∈ X∗, so nennt man `(w) = n die Lange von w; genau die Worteru1 = x1, u2 = x1x2, . . . , un−1 = x1 · · · xn−1, un = w sind Prafixe und die Worterv1 = w, v2 = x2 · · ·xn, . . . , vn = xn sind Postfixe von w. Unter einer formalenSprache L (uber dem Alphabet X) versteht man eine beliebige Teilmenge vonX∗.

Definition 2.4 Sind A und B Teilmengen einer Halbgruppe (S, ·) so verstehtman unter dem Komplexprodukt AB die Teilmenge

AB = {a · b | a ∈ A, b ∈ B}.(6)

Fur A = B schreibt man auch A2 anstelle von AA, fur einelementige MengenA = {a} bzw. B = {b} schreibt man auch aB anstelle von {a}B bzw. Ab anstellevon A{b}.

Definition 2.5 Es seien A und B Alphabete. Eine Codierung von A in B isteine beliebige Abbildung γ : A+ → B+; sie heißt eindeutig decodierbar, wenn sieinjektiv ist, und sie heißt homomorph, wenn

γ(uv) = γ(u)γ(v) fur alle u, v ∈ A+(7)

gilt. Die Menge C = γ(A) ⊂ B+ heißt Code (zu γ), die Elemente c ∈ C Co-deworter. Fur |B| = 2 spricht man von binaren, fur |B| = 3 von ternaren Codes.Besitzen alle Codeworter c ∈ C dieselbe Lange n = `(c), so heißt C ein Blockcodeder Lange n uber B. Ist |C| = 1, so nennt man C einen trivialen Code. Unterder Informationsrate eines Blockcodes der Lange n uber einem Alphabet mit qElementen versteht man R = R(C) = 1

nlogq |C|.

Bemerkung 2.6 a) Man bezeichnet allgemein jede nichtleere endliche TeilmengeC einer freien Halbgruppe B+ als Code. Man kann dies mit der obigen Definitionin Einklang bringen, indem man als Alphabet A eine beliebige, zu C gleichmachti-ge Menge wahlt und als Codierung γ eine beliebige bijektive Abbildung von Aauf C = γ(A), die man in kanonischer Weise gemaß

γ(x1 · · ·xn) = γ(x1) . . . γ(xn)(8)



zu einem Homomorphismus von A+ in B+ fortsetzt. Auf diese Weise entstehtstets eine homomorphe Codierung, die jedoch nicht eindeutig decodierbar seinmuß (vgl. Aufgabe 2.20).

b) Bei dem Alphabet B = {b1, . . . , bq} kommt es nicht auf die konkreten Symbolebi an, sondern nur auf die Machtigkeit q = |B|. Man kann daher nach geeigneterUmbenennung B = {1, . . . , q − 1, 0} annehmen und diese Menge mit der Trager-menge des Restklassenringes (Z/(q),+, ·) identifizieren. Auf diese Weise hat manstets die Moglichkeit, die Buchstaben des Alphabets zu addieren und zu multipli-zieren. Dies kann man unter Umstanden bei der Konstruktion von Codierungenmit besonderen Eigenschaften ausnutzen (vgl. Beispiel 1.1, Definition 3.13 undFolgerung 3.14). Außerdem kann man das Auftreten von Ubertragungsfehlerndann dadurch modellieren, daß zu einem ubertragenen Codewort ein geeignetesFehlerwort hinzuaddiert wurde. Ist q = pk sogar eine Primzahlpotenz, dann kannman B auch mit dem endlichen Korper Fq identifizieren, wodurch die Multipli-kation mit einem von 0 verschiedenen Buchstaben sogar invertierbar ist.

Beispiel 2.7 a) Es sei B ein Alphabet mit |B| = q. Fur b ∈ B sei b = x1 . . . xn ∈Bn mit xi = b fur i = 1, . . . , n die n-fache Wiederholung des Buchstabens b. DerBlockcode C = {b | b ∈ B} heißt q-narer Wiederholungscode der Lange n.

b) Ist allgemeiner C ⊆ Bn ein beliebiger Blockcode der Lange n, so wird furm ∈ N die m-fache Wiederholung von C als Blockcode {(c, . . . , c) ∈ Bmn | c ∈ C}definiert.

Beispiel 2.8 Es seien n, q ≥ 1 naturliche Zahlen und B = {0, 1, . . . , q − 1}. Dervolle q-nare Gray-Code Cn der Lange n wird folgendermaßen rekursiv definiert.Fur n = 1 sei C1 = B. Fur n > 1 beginnen die ersten qn−1 Worte von Cn mitdem Zeichen 0 gefolgt von samtlichen Codeworten von Cn−1 in der konstruiertenReihenfolge. Die nachsten qn−1 Codeworte beginnen mit dem Zeichen 1 gefolgtvon den Codeworten von Cn−1, diese aber in umgekehrter Reihenfolge ihrer Kon-struktion. Die nachsten qn−1 Codeworte beginnen mit dem Zeichen 2, gefolgt vonden Codeworten aus Cn−1, diesmal wieder in ihrer ursprunglichen Reihenfolge,und so abwechselnd bis das erste Zeichen q − 1 ist. Naturlich gilt Cn = Bn, aberdie Reihenfolge der Codeworter ist hier entscheidend! Jede nichtleere TeilmengeC aufeinanderfolgender Codeworte aus Cn bezeichnet man als q-naren Gray-Codeder Lange n.

Definition 2.9 Es sei (S, ·) eine Halbgruppe. Eine nichtleere Teilmenge U vonS heißt eine Unterhalbgruppe von (S, ·), wenn

a, b ∈ U =⇒ a · b ∈ U(9)



fur alle a, b ∈ S erfullt ist. Fur eine nichtleere Teilmenge A von S sei < A > derDurchschnitt aller Unterhalbgruppen U von (S, ·) mit A ⊆ U (vgl. Aufgabe 2.21).Man nennt < A > die von A erzeugte Unterhalbgruppe von (S, ·).

Der Beweis der beiden folgenden grundlegenden Satze ist umfangreicher und wirdinnerhalb der Vorlesung daher nicht gefuhrt.

Satz 2.10 Es sei B ein Alphabet. Eine nichtleere, endliche Teilmenge C ⊆ B+

ist genau dann ein eindeutig decodierbarer Code, wenn C =< C > \ < C >2 giltund wenn fur alle w ∈ B+ aus < C > w ∩ < C > 6= ∅ und w < C > ∩ < C > 6= ∅bereits w ∈< C > folgt.

Der nachste Satz gibt einen Algorithmus an, mit dem die eindeutige Decodierbar-keit einer homomorphen Codierung entschieden werden kann. Dieser Algorithmusgeht auf eine Arbeit von Sardinas und Patterson im Jahr 1953 zuruck.

Definition 2.11 Fur Teilmengen M und N einer Halbgruppe (S, ·) sei

M−1N = {x ∈ S |Mx ∩N 6= ∅}.

Satz 2.12 Es seien A und B Alphabete und γ : A+ → B+ eine homomorpheCodierung. Die Mengen Mn seien definiert durch M0 = γ(A), M1 = M−1

0 M0 undMn+1 = M−1

n M0 ∪M−10 Mn. Genau dann ist γ eindeutig decodierbar, wenn γ|A

injektiv ist und Mn ∩M0 = ∅ fur alle n ≥ 1 gilt.

Definition 2.13 Ein Code C ⊂ B+ heißt irreduzibel, sofort decodierbar oder einPrafix-Code, wenn kein Codewort Prafix eines anderen Codewortes ist.

Bemerkung 2.14 a) Man nennt diese Bedingung auch Prafix-Eigenschaft oderFano-Bedingung nach Robert Mario Fano (1917 - 2016).

b) Jeder Blockcode ist irreduzibel, jeder irreduzible Code ist eindeutig decodier-bar.

Satz 2.15 Ist C = {c1, . . . , cm} ⊂ B+ eindeutig decodierbarer Code mit denCodewortlangen ni = |ci| fur i ∈M = {1, . . . ,m}, so gilt

m∑i=1

|B|−ni ≤ 1.(10)



Beweis: Seien die Codewortlangen geordnet gemaß n1 ≤ n2 ≤ . . . ≤ nm undS =

∑mi=1 |B|−ni die linke Seite von (10). Es ist also S ≤ 1 zu zeigen. Ware

S > 1, so wurde aber Sk fur k →∞ gegen ∞ divergieren. Durch Induktion nachk folgt aus den Distributivgesetzen und den Potenzrechenregeln

Sk =m∑i1=1

. . .m∑ik=1

|B|−(ni1+...+nik

).(11)

Ordnet man diese Summe nach Potenzen von |B|, so erhalt man

Sk =knm∑j=kn1

a(k, j)|B|−j(12)

mita(k, j) =

∑(i1,...,ik)∈Mk,ni1

+...+nik=j

1.

Da C eindeutig decodierbar ist, sind alle zu den Summanden von a(k, j) gehoren-den Worter ci1 . . . cik der Lange j paarweise verschieden und somit a(k, j) ≤ |B|j.Aus (12) folgt

Sk ≤knm∑j=kn1

|B|j|B|−j =knm∑j=kn1

1 = k(nm − n1) + 1 ≤ k(nm − n1 + 1).

Also giltS ≤ k

√k k√nm − n1 + 1,

und die rechte Seite konvergiert fur k → ∞ gegen 1. Hieraus folgt S ≤ 1 unddamit (10). �

Bemerkung 2.16 Die Ungleichung (10) wird auch Ungleichung von Kraft undMcMillan fur eindeutig decodierbare Codes genannt. Brockway McMillan (1915- ) bewies die Aussage dieses Satzes 1956, wahrend Leon G. Kraft den hiermitzusammenhangenden Satz 2.17 uber Prafix-Codes bereits 1949 in seiner Master-arbeit bewiesen hatte.

Satz 2.17 Es seien B ein Alphabet und n1, . . . , nm ∈ N naturliche Zahlen, die(10) erfullen. Dann existiert ein Prafix-Code C = {c1, . . . , cm} ⊂ B+ mit denCodewortlangen |ci| = ni fur i = 1, . . . ,m.



Beweis: Der Beweis erfolgt durch Induktion nach m, wobei der Fall m = 1 trivialist. Sei also m > 1 und die Zahlen geordnet gemaß n1 ≤ n2 ≤ . . . ≤ nm. Danngilt aber

m−1∑i=1

|B|−ni < 1

und es existiert nach Induktionsvoraussetzung ein Prafix-Code

C ′ = {c1, . . . , cm−1} ⊂ B+

mit |ci| = ni fur i = 1, . . . ,m − 1. Es ist also ein Wort cm ∈ Bnm zu finden, sodaß kein ci fur i = 1, . . . ,m − 1 Prafix von cm ist. Betrachte zu jedem dieser cidie Menge

V (ci) = {w ∈ Bnm | w = civ mit v ∈ B∗},

also aller Worte aus Bnm , von denen ci Prafix ist. Offensichtlich gilt |V (ci)| =|B|nm−ni . Also kann man die Anzahl dieser “verbotenen” Worte abschatzen durch

|V (c1)∪ . . .∪V (cm−1)| ≤m−1∑i=1

|V (ci)| =m−1∑i=1

|B|nm−ni = |B|nm

m−1∑i=1

|B|−ni < |B|nm .

Jedes cm ∈ Bnm \ (V (c1) ∪ . . . ∪ V (cm−1)) 6= ∅ liefert damit einen Prafix-CodeC = C ′ ∪ {cm} der gewunschten Art. �

Aufgabe 2.18 Beweisen Sie, daß das Einselement in einem Monoid stets ein-deutig bestimmt ist.

Aufgabe 2.19 Gibt es Alphabete X, fur welche die freie Halbgruppe X+ kom-mutativ ist?

Aufgabe 2.20 Beweisen Sie, daß fur die eindeutige Decodierbarkeit einer ho-momorphen Codierung γ : A+ → B+ die Injektivitat der Einschrankung γ|Anotwendig, aber nicht hinreichend ist.

Aufgabe 2.21 Beweisen Sie, daß der Durchschnitt beliebig vieler Unterhalb-gruppen einer Halbgruppe (S, ·) entweder leer oder Unterhalbgruppe von (S, ·)ist.

Aufgabe 2.22 a) Zeigen Sie, daß jeder Blockcode eindeutig decodierbar ist.

b) Es seien A = {a, b, c}, B = {0, 1}, γ1(A) = C1 = {0, 10, 01} und γ2(A) = C2 ={1, 10, 00}. Entscheiden Sie mit Satz 2.12, ob γi eindeutig decodierbar ist.



c) Es sei C = {110, 11, 100, 00, 10} ⊂ B+. Entscheiden Sie, ob C eindeutig deco-dierbar ist.

d) Zeigen Sie, daß C1 = {11, 10, 110, 001} und C2 = {11, 10, 001} eindeutig deco-dierbare Codes uber B = {0, 1} sind.

Aufgabe 2.23 Fur B = Z/(3) = {0, 1, 2} und x ∈ B sei der Ternarcode C(x)durch

C(x) = {01, 1, 2, 2x0}

definiert. Bestimmen Sie samtliche Werte von x, fur die C(x, y) eindeutig deco-dierbar ist.

Aufgabe 2.24 Fur B = Z/(3) = {0, 1, 2} und x, y ∈ B sei der TernarcodeC(x, y) durch

C(x, y) = {01, 20, x01, 01y}

definiert. Bestimmen Sie samtliche Werte von x und y, fur die C(x, y) eindeu-tig decodierbar ist. Aus welchem dieser eindeutig decodierbaren Codes C(x, y)stammt das Codewort 0120101010?

Aufgabe 2.25 Fur die Alphabete A = {A,B,E,N} und B = {α, β} sei diehomomorphe Codierung γ : A+ → B+ gegeben durch

γ(A) = βα, γ(B) = ααβ, γ(E) = αββ, γ(N) = βαα.

Zeigen Sie, daß γ eindeutig decodierbar ist, und bestimmen Sie das eindeutigbestimmte c ∈ A+ mit γ(c) = ααββαβααβαβαααββ.

Aufgabe 2.26 Fur die Alphabete A = {A,E,G,N,O} und B = {x, y} sei diehomomorphe Codierung γ : A+ → B+ gegeben durch

γ(A) = yx, γ(E) = xxy, γ(G) = xxx, γ(N) = yxx, γ(O) = xyy.

Zeigen Sie, daß γ eindeutig decodierbar ist, und bestimmen Sie das eindeutigbestimmte c ∈ A+ mit γ(c) = yxxxyxxxyxxxyxyyyxx.


3 EIGENSCHAFTEN VON BLOCKCODES

3 Eigenschaften von Blockcodes

Definition 3.1 Es sei B ein Alphabet und v, w ∈ Bn ⊂ B+. Dann heißt

d(v, w) = |{i | vi 6= wi}|,(13)

also die Anzahl der Stellen, an denen sich v und w unterscheiden, der Hamming-Abstand oder die Hamming-Distanz von v und w. (Dieser Begriff wurde 1950 vonRichard Wesley Hamming (1915 - 1998) eingefuhrt.)

Satz 3.2 Die Hamming-Distanz definiert eine Metrik auf Bn, d. h. es gilt furalle u, v, w ∈ Bn

d(u, v) ≥ 0 und d(u, v) = 0⇐⇒ u = v,(14)

d(u, v) = d(v, u),(15)

d(u, v) ≤ d(u,w) + d(w, v).(16)

Ist (B,+) eine additiv geschriebene abelsche Gruppe (was nach Bemerkung 2.6 b)immer angenommen werden darf), so ist d translationsinvariant, d. h. es giltaußerdem

d(u+ w, v + w) = d(u, v).(17)

Beweis: Aufgrund der Definition des Abstandes als Anzahl der unterschiedlichenStellen sind die Aussagen in (14) und (15) klar. Zum Beweis von (16) betrachteeine beliebige Stelle i, an der ui 6= vi gilt, die also in d(u, v) gezahlt wird. Dannmuß wi aber auch von mindestens einem der beiden Zeichen ui oder vi verschiedensein und wird daher in d(u,w) oder in d(w, v) (oder in beiden) gezahlt. Damit istdie rechte Seite mindestens so groß wie die linke. In (17) gilt die Gleichheit, weilfur jede Stelle i stets ui + wi = vi + wi gleichwertig zu ui = vi ist. �

Definition 3.3 Es sei B ein Alphabet und r ∈ N0. Fur v ∈ Bn sei

Br(v) = {w ∈ Bn | d(v, w) ≤ r}(18)

die abgeschlossene Kugel vom Radius r um den Mittelpunkt v und

Sr(v) = {w ∈ Bn | d(v, w) = r}(19)

die Sphare vom Radius r um den Mittelpunkt v.



Lemma 3.4 Ist |B| = q, so gilt fur alle j, r ∈ N0 und v ∈ Bn

|Sj(v)| =(n

j

)(q − 1)j,(20)

und da die abgeschlossene Kugel Br(v) disjunkte Vereinigung der Spharen Sj(v)fur j = 0, . . . , r ist,

|Br(v)| =r∑j=0

(n

j

)(q − 1)j.(21)

Beweis: Offensichtlich ist nur (20) zu zeigen. Ein Element w ∈ Bn liegt abergenau dann in Sj(v), wenn es genau j Stellen i1, . . . , ij gibt, an denen sich w und

v unterscheiden. Diese j Stellen konnen nun zunachst einmal auf(nj

)verschiede-

ne Weisen aus allen Stellen 1, . . . , n ausgewahlt werden. Fur jede so ausgewahlteStelle i muß sich dann wi von vi unterscheiden, wahrend an den nicht ausgewahl-ten Stellen v und w ubereinstimmen. Da vi genau ein Zeichen aus B fur dieseStelle festlegt, kann wi an dieser Stelle jedes der anderen q − 1 Zeichen aus Bsein. Es gibt also fur das Wort w genau q − 1 verschiedene Moglichkeiten, sichvon v an dieser Stelle i zu unterscheiden. Daher gibt es fur das Wort w genau(q − 1)j Moglichkeiten, sich an allen j ausgewahlten Stellen von v zu unterschei-den und an den anderen Stellen mit v ubereinzustimmen. Also wird die Anzahlaller w ∈ Bn, die von v den Abstand j haben, durch die rechte Seite von (20)beschrieben. �

Definition 3.5 Es sei C ⊆ Bn ein Blockcode der Lange n.

a) C heißt t-fehlererkennend, falls Bt(c) fur alle c ∈ C kein Codewort außer centhalt.

b) C heißt e-fehlerkorrigierend, falls Be(c)∩Be(c′) = ∅ fur alle Codeworter c 6= c′

gilt.

c) Ist |C| > 1, so heißt

d(C) = min{d(c, c′) | c 6= c′, c, c′ ∈ C}(22)

die Minimaldistanz von C. Fur jeden trivialen Code sei d(C) = 0.

d) Ist |C| = M und d(C) = d, so heißt C ein (n,M, d)-Code uber B.

e) Mit Aq(n, d) wird das maximale M bezeichnet, fur das bei gegebenen q = |B|, nund d ein (n,M, d)-Code uber B existiert.



Beispiel 3.6 a) Jeder triviale Blockcode der Lange n ist ein (n, 1, 0)-Code, undM = 1 ist fur d = 0 aufgrund der Defintion der Minimaldistanz auch optimal,d. h. es ist Aq(n, 0) = 1 fur jedes q und n.

b) Es ist C = Bn ein (n, qn, 1)-Code und M = qn ist bei gegebenen n und q furd = 1 ebenfalls optimal, also Aq(n, 1) = qn. Dies folgt aus dem Satz 3.23.

c) Der q-nare Wiederholungscode C der Lange n ist ein (n, q, n)-Code.

Definition 3.7 Ein Blockcode C ⊆ Bn erkennt Vertauschungsfehler an den Stel-len i und j aus {1, . . . , n}, wenn fur alle (c1, . . . , ci, . . . , cj, . . . , cn) ∈ C mit ci 6= cjgilt (c1, . . . , cj, . . . , ci, . . . , cn) /∈ C.

Bemerkung 3.8 Es werden noch weitere Vertauschungsfehler unterschieden, diebei der Ubermittlung von Ziffern auftreten: Sprungtranspositionen (abc 7→ cba),Zwillingsfehler (aa 7→ bb), Sprungzwillingsfehler (aca 7→ bcb), phonetische Fehler(a0 7→ 1a) und ubrige, zufallige Fehler. Uber die Haufigkeiten derartiger Fehlergibt es statistische Untersuchungen.

Satz 3.9 Es sei C ⊆ Bn ein Blockcode mit Minimaldistanz d.

a) Ist d ≥ t+ 1, so ist C ein t-fehlererkennender Code.

b) Ist d ≥ 2e+ 1, so ist C ein e-fehlerkorrigierender Code.

Beweis: a) Ist c ∈ C und c 6= c′ ∈ Bn mit c′ ∈ Bt(c), dann folgt d(c, c′) ≤ t < d,also kann c′ nicht auch in C liegen.

b) Ware w ∈ Be(c)∩Be(c′) fur verschiedene Codeworte c und c′, so ware d(c, c′) ≤

d(c, w) + d(w, c′) ≤ e+ e < d, was nach Definition der Minimaldistanz nicht seinkann. �

Definition 3.10 Es sei C ⊂ Bn ein Blockcode der Lange n. Man nennt C perfekt,falls ein e ∈ N0 existiert, so daß

Bn =⋃c∈C

Be(c)(23)

die disjunkte Vereinigung der Kugeln Be(c) ist.



Satz 3.11 Es sei C ⊆ Bn ein Blockcode der Lange n uber B und es gelte |B| = q.

a) Ist d(C) ≥ 2e+ 1 fur e ∈ N0, so gilt die Hamming-Schranke

qn ≥ |C|e∑j=0

(n

j

)(q − 1)j.(24)

b) Genau dann ist ein nicht-trivialer Code C perfekt, wenn in (24) die Gleichheitgilt. Diese Gleichung nennt man auch Kugelpackungsgleichung.

Beweis: a) Aus d(C) ≥ 2e + 1 folgt wie im Beweis von Satz 3.9 b) zunachsteinmal Be(c) ∩Be(c

′) = ∅ fur alle c 6= c′ aus C. Mit Lemma 3.4 erhalt man

qn = |Bn| ≥ |⋃c∈C

Be(c)| =∑c∈C|Be(c)| = |C||Be(c)| = |C|

e∑j=0

(n

j

)(q − 1)j,

und hierin gilt Gleichheit genau dann, wenn Bn =⋃c∈C Be(c) gilt.

b) Gilt also die Gleichheit, so ist C nach Definition perfekt. Ist C umgekehrtnicht-trivial und perfekt, so ist

⋃c∈C Be(c) disjunkte Uberdeckung von Bn und

da |C| > 1 gilt, hat man auch d(C) ≥ 2e+1. Nach a) gilt (24) also mit Gleichheit.�

Beispiel 3.12 a) Triviale Codes (e = n) und C = Bn (e = 0) sind perfekteCodes. Der binare Wiederholungscode ungerader Lange n = 2e + 1 ist perfekt,denn Bn wird von den beiden disjunkten Kugeln vom Radius e um die beidenCodeworte 0 und 1 uberdeckt. Diese Codes nennt man auch triviale perfekteCodes.

b) Die weiter unten behandelten (linearen) Hamming-Codes sind perfekt.

c) Es gibt noch zwei von Marcel Jules Edouard Golay (1902 - 1989) im Jahr 1949entdeckte perfekte Codes, den binaren (23, 212, 7)-Golay-Code und den ternaren(11, 36, 5)-Golay-Code. Der binare Golay-Code wurde fur die Missionen von Voya-ger I und II in den Jahren 1977 - 81 verwandt, um Farbbilder von Jupiter undSaturn zu ubertragen.

d) Zwei tiefliegende Resultate, die von verschiedenen Autoren in den 70er und80er Jahren bewiesen wurden, besagen, daß fur Primzahlpotenzen q = |B| einnicht-trivialer perfekter Code nur mit denselben Parametern wie die Hamming-Codes und die Golay-Codes existieren kann. Außerdem ist fur beliebiges q undd(C) ≥ 7 der binare Golay-Code der einzige nicht-triviale perfekte Code.



Durch die folgenden Begriffsbildungen wird das Vorgehen in Beispiel 1.1 verall-gemeinert und verstandlicher.

Definition 3.13 Es sei C ⊆ Bn ein Blockcode der Lange n und das Alpha-bet B werde gemaß Bemerkung 2.6 b) als additive Gruppe vorausgesetzt. DerErweiterungscode C von C ist dann der Blockcode der Lange n+ 1

C = {(v1, . . . , vn+1) | (v1, . . . , vn) ∈ C, vn+1 = −n∑i=1

vi}.

Lemma 3.14 a) Ist C Blockcode, so gilt d(C) ≤ d(C) ≤ d(C) + 1.

b) Ist C nicht-trivialer Blockcode, so gilt d(C) ≥ 2.

c) Ist C binarer Blockcode und d(C) ungerade, so gilt d(C) = d(C) + 1.

Beweis: a) Zu c = (c1, . . . , cn) ∈ C sei stets c = (c1, . . . , cn, cn+1) ∈ C. Zwei Ele-mente c und c′ aus C unterscheiden sich mindestens an den Stellen, an denen sichdie zugehorigen Elemente c und c′ aus C unterscheiden und hochstens zusatzlichnoch an der letzten Stelle. Es gilt also

d(c, c′) ≤ d(c, c′) ≤ d(c, c′) + 1.(25)

Hieraus folgt bereits die Behauptung, falls es zwei verschiedene Elemente c 6= c′ inC gibt. Sonst ist mit C aber auch C einelementig und es gilt d(C) = 0 = d(C) < 1.

b) Wegen |C| > 1 existieren c 6= c′ aus C. Entweder gilt nun stets 2 ≤ d(c, c′) furalle c 6= c′ aus C oder es gibt c 6= c′ in C mit d(c, c′) = 1. Im ersten Fall folgt ausa) bereits 2 ≤ d(C) ≤ d(C). Im zweiten Fall unterscheiden sich c und c′ an genaueiner Stelle j, an der sich c und c′ dann ebenfalls unterscheiden. Außerdem istdann cn+1 6= c′n+1, da sich die beiden Summen genau in den Summanden cj 6= c′junterscheiden. Dies zeigt d(c, c′) = 2 fur alle diese Paare. Also gilt d(C) ≥ 2.

c) Sei k = d(C) ≥ 1 ungerade. Wegen (25) bleibt d(c, c′) = k =⇒ d(c, c′) = k + 1fur alle c 6= c′ aus C zu zeigen. Gilt aber die Voraussetzung dieser Implikation,so seien I = {i1, . . . , ik} die Stellen, an denen sich c und c′ unterscheiden. Wennnun c an einer geraden Anzahl von Stellen aus I eine 1 hat, so hat c′ dort eine0 und folglich, da k ungerade ist, an einer ungeraden Anzahl von Stellen eine 1.Sonst hat c an einer ungeraden Anzahl von Stellen eine 1 und c′ an einer geradenAnzahl. In jedem Fall ist

∑i∈I ci 6=

∑i∈I c

′i mod 2. Da die restlichen Stellen von

c und c′ aber gleich sind, folgt cn+1 6= c′n+1 und daher d(c, c′) = d(c, c′) + 1. �



Folgerung 3.15 Fur ungerades d gilt A2(n + 1, d + 1) = A2(n, d). Also gilt furgerades d > 0 auch A2(n, d) = A2(n− 1, d− 1).

Beweis: Offensichtlich reicht es, den ungeraden Fall zu beweisen. Sei also d un-gerade. Ist dann C ein binarer (n,M, d)-Code, so ist C ein (n+1,M, d+1)-Code.Dies zeigt A2(n + 1, d + 1) ≥ A2(n, d). Sei umgekehrt C ein (n + 1,M, d + 1)-Code. Entfernt man aus allen Codewortern eine feste Koordinate, so bleibenunterschiedliche Codeworte verschieden, da sie sich wegen d + 1 > 1 nicht nurin dieser Koordinate unterscheiden konnten. Man erhalt also eine Blockcode derLange n aus M Codewortern. Zwei auf diese Weise erhaltene Codeworte derLange n unterschieden sich aber noch in mindestens d Koordinaten. Sind c 6= c′

zwei Codeworte aus C mit d(c, c′) = d+1 und streicht man aus allen Codeworterneine Koordinate, an der sich c und c′ unterscheiden, so haben die resultierendenCodeworter nur noch den Abstand d, der resultierende Code ist also tatsachlichein (n,M, d)-Code. Dies zeigt auch die andere Ungleichung. �

Definition 3.16 Ein Blockcode C der Lange n uber B = Z/(q) heißt Paritats-code zur Basis q mit den Gewichten g1, . . . , gn ∈ B, wenn C genau aus den(c1, . . . , cn) ∈ Bn besteht, fur die

n∑i=1

gici ≡ 0 mod q(26)

gilt. Das letzte Zeichen cn eines jeden Codewortes heißt dann das Kontrollzeichendieses Wortes. Stets ist (0, . . . , 0) in C. Gilt gi = 1 fur alle Gewichte, wird alsozunachst die Quersumme berechnet, so heißt C einfach ein Paritatscode.

Beispiel 3.17 a) Bei der EAN (Europaische Artikel-Nummer, auch GTIN =Global Trade Item Number) wird ein Paritatscode zur Basis q = 10 entwederder Lange n = 13 (EAN13) oder der Lange n = 8 (EAN8) verwendet. BeimEAN13 lauten die Gewichte 1, 3, 1, . . . , 3, 1, beim EAN8 dagegen 3, 1, . . . , 3, 1.Beide Codes sind also nach dem folgenden Satz 1-fehlererkennend.

b) Bei der ISBN10 (Internationale Standard Buch Nummer) wird ein Paritatscodezur Basis q = 11 der Lange n = 10 verwendet. Die Gewichte lauten 10, 9, . . . , 1.Ist das Kontrollzeichen eine 10, so wird dieses als X notiert. Nach dem folgendenSatz ist der ISBN-Code 1-fehlererkennend. Er erkennt sogar Vertauschungsfehleran beliebigen Stellen.

Seit 2007 wird auch die ISBN13 zur Basis q = 10 der Lange n = 13 verwendet.Die Gewichte sind dieselben wie bei der EAN13. Die ISBN13 entsteht aus der



ISBN10 durch voranstellen der drei Ziffern 978 und der anderen Berechnung derPrufziffer.

c) Bei den Euro-Banknoten kommt ein Paritatscode zur Basis q = 9 der Langen = 12 zum Einsatz. Die auftretenden Buchstaben werden vorher durch Ziffernaus {0, . . . , 9} ersetzt. Samtliche Gewichte sind 1.

Satz 3.18 Es sei C ein Paritatscode zur Basis q mit den Gewichten gi. Um dasKontrollzeichen stets berechnen zu konnen, muß gn teilerfremd zu q sein.

a) Genau dann ist C 1-fehlererkennend, wenn jedes gi teilerfremd zu q ist. Ins-besondere ist also jeder Paritatscode 1-fehlererkennend.

b) Genau dann erkennt C alle Vertauschungsfehler an aufeinanderfolgenden Stel-len, wenn gi − gi+1 fur i = 1, . . . , n− 1 teilerfremd zu q ist.

Beweis: Aus (26) folgt gncn ≡ −(g1c1+. . .+gn−1cn−1) mod q und diese Gleichungist genau dann nach cn auflosbar, wenn das Inverse g−1n modulo q existiert. Diesist aber genau fur ggT (gn, q) = 1 der Fall.

a) Sei c = (c1, . . . , cn) ∈ C und c′ unterscheide sich genau an der Stelle i von c′.Genau dann erkennt C diesen Fehler nicht, wenn q neben g1c1+. . .+qici+. . . qncnauch g1c1+. . .+qic

′i+. . . qncn teilt oder gleichwertig, wenn q das Produkt gi(ci−c′i)

teilt. Also erkennt C genau dann diesen Fehler, wenn q keine der moglichen Zahlengi(ci − c′i) teilt.

Gilt nun ggT (q, gi) = 1, so teilt q keine dieser Zahlen, da q sonst ci − c′i teilenmußte, was wegen |ci − c′i| ≤ q − 1 unmoglich ist.

Gilt andererseits ggT (q, gi) = d > 1, so haben c = (0, . . . , 0, ci, 0, . . . , 0) undc′ = (0, . . . , 0, c′i, 0, . . . , 0) mit c′i = q

d6= 0 und ci = 0 den Abstand 1 und liegen

wegen gic′i = gi

qd

= q gid

beide in C, d. h., C erkennt diesen einfachen Fehler nicht.

b) Sei c = (c1, . . . , ci, . . . , cj, . . . cn) ∈ C und c′ = (c1, . . . , cj, . . . , ci, . . . , cn), wobeii und j nicht notwendig benachbart sein mussen. Genau dann erkennt C diesenFehler nicht, wenn g1c1 + . . .+ gicj + . . .+ gjci + . . .+ gncn ebenfalls von q geteiltwird. Dies ist gleichwertig zu q | gici + gjcj − gicj − gjci = (gi − gj)(ci − cj).Also erkennt C genau dann diesen Fehler, wenn q keine der moglichen Zahlen(gi − gj)(ci − cj) teilt.

Mit der analogen Fallunterscheidung wie beim Beweis von a) folgt nun die Be-hauptung. �



Folgerung 3.19 Fur gerades q gibt es keinen Paritatscode zur Basis q der 1-fehlererkennend ist und gleichzeitig alle Vertauschungsfehler an aufeinanderfol-genden Stellen erkennt.

Beweis: Sei C Paritatscode der Lange n mit Gewichten g1, . . . , gn. Wenn C 1-fehlererkennend ist, so mussen nach Satz 3.18 a) alle gi ungerade sein. Dann sindaber alle Differenzen gi − gj fur i 6= j gerade und nicht teilerfremd zur geradenZahl q. Wegen Satz 3.18 b) erkennt C daher nicht alle Vertauschungsfehler. �

Definition 3.20 Es sei (B,+) eine beliebige endliche Gruppe. Weiterhin seienπi fur i = 1, . . . , n Permutationen von B und a ∈ B. Dann heißt

C = {(c1, . . . , cn) | ci ∈ B,n∑i=1

πi(ci) = a}(27)

ein Kontrollcode und∑ni=1 πi(ci) = a die Kontrollgleichung von C.

Satz 3.21 a) Jeder Kontrollcode C ist 1-fehlererkennend.

b) Ein Kontrollcode C mit den Permutationen π1, . . . , πn erkennt alle Vertau-schungen an aufeinanderfolgenden Stellen, falls πi(b) +πi+1(b

′) 6= πi+1(b) +πi(b′)

fur alle b 6= b′ aus B und i = 1, . . . , n− 1 gilt.

Beweis: a) Fur |C| = 1 ist nichts zu zeigen. Waren c = (c1, . . . , ci, . . . , cn) undc′ = (c1, . . . , c

′i, . . . , cn) aus C mit d(c, c′) = 1, also ci 6= c′i, so wurde

π1(c1) + . . .+ πi(ci) + . . .+ πn(cn) = a = π1(c1) + . . .+ πi(c′i) + . . .+ πn(cn)

in der Gruppe (B,+) sofort πi(ci) = πi(c′i) und damit ci = c′i nach sich ziehen.

Also gilt stets d(c, c′) ≥ 2 und daher ist C 1-fehlererkennend.

b) Sei c = (c1, . . . , ci, . . . , cj, . . . , cn) ∈ C und c′ = (c1, . . . , cj, . . . , ci, . . . , cn) mitci 6= cj. Genau dann erkennt C diese Vertauschung nicht, wenn sowohl π1(c1) +. . .+ πi(ci) + . . .+ πj(cj) + . . .+ πn(cn) = a als auch π1(c1) + . . .+ πi(cj) + . . .+πj(ci) + . . .+ πn(cn) = a gelten. Durch Subtraktion gleicher Summanden folgt inder Gruppe (B,+) dann

πi(ci) + . . .+ πj(cj) = πi(cj) + . . .+ πj(ci).(28)



Wenn hierin also stets Ungleichheit gilt, so erkennt C alle Vertauschungen derStellen i und j. Fur j = i+ 1 ist dies gerade die Behauptung in b). Bei kommu-tativen Gruppen kann man (28) sogar weiter vereinfachen zu

πi(ci) + πj(cj) = πi(cj) + πj(ci).

Daher erkennt in diesem Fall der Kontrollcode C alle Vertauschungen an denStellen i und j, wenn πi(b) + πj(b

′) 6= πi(b′) + πj(b) fur alle b 6= b′ aus B gilt. �

Bemerkung 3.22 a) Einige Banken verwenden bei der Vergabe ihrer Konto-nummern einen Kontrollcode uber der Gruppe (Z/(10),+).

b) Bei den 9-stelligen Postgironummern wird ebenfalls ein Kontrollcode uber(Z/(10),+) angewendet.

c) Der bei der Numerierung der ehemaligen DM-Scheine verwendete Code warein Kontrollcode uber der Diedergruppe der Ordnung 10.

d) Es sind auch Kontrollcodes uber nichtassoziativen Quasigruppen untersuchtworden, die bessere Eigenschaften bezuglich der Fehlererkennung haben als dieuber Gruppen definierten Kontrollcodes.

e) Der ISIN-Code (International Securities Identification Number) ordnet jedemWertpapier eine zwolfstellige Buchstaben-Zahlenkombination zu. So hat beispiels-weise die Aktie der Deutschen Telekom die ISIN DE0007664005. Zunachst wer-den zwei Buchstaben als Landerkennung nach ISO 3166-1 angegeben, hier DEfur Deutschland. Danach folgen 9 Ziffern fur das Papier. Die letzte Ziffer isteine Prufziffer. Zu ihrer Berechnung werden die beiden Buchstaben der Lander-kennung in eine vierstellige Zahl umgewandelt, indem zur jeweiligen Stelle imAlphabet 9 addiert wird, also gemaß A = 10, B = 11, . . . , Z = 35. Es entstehendie Ziffern c1c2 . . . c13. Die geraden Stellen werden unverandert gelassen, die un-geraden Stellen durch die Abbildung π(z) = Quersumme(2z) permutiert. Dannwird die Prufziffer c14 durch die Kontrollgleichung

π(c1) + c2 + π(c3) + . . .+ π(c13) + c14 = 0 mod 10

berechnet. Dieser Kontrollcode erkennt einfache Fehler und Vertauschungen be-nachbarter Stellen, wenn es sich nicht um 09 und 90 handelt. In der Praxis wer-den diese Kombinationen aber nicht konsequent vermieden, z. B. bei der BMW-Stammaktie DE000519000.

Der folgende Satz wurde 1964 von R. C. Singleton bewiesen.


http://www.mathe.tu-freiberg.de/~hebisch/cafe/algebra/diedergruppen.html

http://www.mathe.tu-freiberg.de/~hebisch/cafe/algebra/quasigruppe.html


Satz 3.23 Es sei C ⊆ Bn und |B| = q. Dann gilt fur die Minimaldistanz d vonC die Singleton-Schranke

d ≤ n− logq |C|+ 1.(29)

Beweis: Im Fall d = 0, also |C| = 1, ist die (echte) Ungleichung jedenfalls erfullt.Fur d ≥ 1 betrachte die Projektion ϕ : Bn → Bn−d+1 gemaß ϕ(v1, . . . , vn) =(v1, . . . , vn−d+1). Fur c = (c1, . . . , cn) 6= (c′1, . . . , c

′n) = c′ aus C gilt ϕ(c) 6= ϕ(c′),

da sonst (c1, . . . , cn−d+1) = (c′1, . . . , c′n−d+1) und damit d(c, c′) < d = d(C) ware.

Also ist ϕ|C injektiv. Es folgt |C| = |ϕ(C)| ≤ |Bn−d+1| = qn−d+1. Durch Loga-rithmieren folgt hieraus sofort die behauptete Ungleichung. �

Definition 3.24 Blockcodes C mit d(C) = n − logq |C| + 1 heißen MaximumDistance Separable Codes, kurz MDS-Codes.

Beispiel 3.25 a) Wie im Beweis von Satz 3.23 gesehen, sind triviale Codes nie-mals MDS-Codes.

b) Dagegen ist jeder q-nare Wiederholungscode C der Lange n wegen d(C) = nund |C| = q, also logq |C| = 1 ein MDS-Code.

c) Auch C = Bn ist wegen d(C) = 1 und logq |Bn| = n jeweils ein MDS-Code.

d) Wegen Lemma 3.14 c) hat der binare Erweiterungscode En = {0, 1}n−1 dieLange n, die Minimaldistanz d(En) = 2 und erfullt |En| = 2n−1. Es ist daherd(En) = 2 = n− log2 |En|+ 1, also En ein MDS-Code.

Im binaren Fall nennt man die MDS-Codes aus b) - d) auch triviale MDS-Codes.Im Jahr 2006 konnten Guerini und Sala zeigen, daß jeder binare MDS-Codeaquivalent (vgl. Definition 4.9) zu einem dieser trivialen MDS-Codes ist. Furq > 2 gilt dies nicht, vgl. Bemerkung 4.19.

Bemerkung 3.26 Wegen der Singleton-Schranke ist also stets Aq(n, d) ≤ qn−d+1

und fur MDS-Codes wird diese obere Schranke auch erreicht. Es existiert aberkeineswegs fur jede Kombination der Parameter ein Blockcode C, der die Schrankeauch mit Gleichheit erreicht.

Die folgende Tabelle gibt fur binare Codes (q = 2) und kleine Werte von n und d(Wegen Folgerung 3.15 reicht es, ungerades d zu betrachten! Wegen Beispiel 3.6 b)besteht eine entsprechende Spalte fur d = 1 gerade aus den Potenzen 2n.) exakte



Werte oder bekannte Abschatzungen fur A2(n, d) an. Sie ist dem Buch “A FirstCourse in Coding Theory” von Raymond Hill aus dem Jahr 1986 entnommen undum einige neuere Eintrage erganzt. Eine weitergehende Aktualisierung konnteThema einer Abschlußarbeit sein. Die Falle, in denen die Singleton-Schrankeerreicht wird, sind fett hervorgehoben.

n d=3 d=5 d=73 2 - -4 2 - -5 4 2 -6 8 2 -7 16 2 28 20 4 29 40 6 210 72 12 211 144 24 412 256 32 413 512 64 814 1024 128 1615 2048 256 3216 2816-3276 256-340 3617 5312-5662 512-673 64-7218 10496-13104 1024-1237 128-13519 20480-26168 2048-2279 25620 36864-43688 2560-4096 512

Der Eintrag 2 fur n = 4 und d = 3 zeigt beispielsweise, daß die Singleton-Schrankedie Existenz eines binaren MDS-Codes C der Lange n = 4 mit Minimaldistanzd(C) = 3 und |C| = 4 wegen 3 ≤ 4 − 2 + 1 zwar zulassen wurde, daß aber keinderartiger Code existiert.

Definition 3.27 Es sei C ⊆ Bn ein Blockcode. Ein Decodierschema δ von Cbezuglich ∅ 6= D ⊆ Bn ist dann eine beliebige Abbildung δ : D → C. Dabei heißtBn \D Decodierausfall von δ, und δ heißt vollstandig, wenn D = Bn gilt.

Beispiel 3.28 Es sei B = {0, 1} und C = {00000, 11111} der binare Wieder-holungscode der Lange n = 5. Dann sind mogliche Decodierschemata gegebendurch Di = Bi(00000) ∪ Bi(11111) und δi : Di → C mit δi(v) = c fur v ∈ Bi(c)fur i = 0, 1, 2. Dabei ist nur δ2 vollstandig.

Bemerkung 3.29 In der Praxis erweitert man oft ein nicht vollstandiges Deco-dierschema δ : D → C, also mit D ⊂ Bn, zu einem vollstandigen Schema, indemman δ(v) ∈ C fur alle v ∈ Bn \D zufallig wahlt.



Eine andere Moglichkeit besteht darin, fur derartige v nicht einen eindeutigenWert δ(v) ∈ C zu ermitteln, sondern eine Liste {c1, . . . , c`} von (moglichst wahr-scheinlichen) Codewortern anzugeben. Dieses Verfahren nennt man Listendeco-dierung.

Aufgabe 3.30 Der nicht-triviale binare Blockcode C der Lange n bestehe nuraus Vektoren, die eine gerade Anzahl von Einsen besitzen. Dann gilt d(C) ≥ 2.

Aufgabe 3.31 Beweisen Sie A2(3, 2) = 4.

Aufgabe 3.32 Zeigen Sie, daß man das Kontrollzeichen bei der ISBN10 auchgemaß

c10 ≡ 1 · c1 + 2 · c2 + . . .+ 9 · c9 mod 11

berechnen kann.

Aufgabe 3.33 Obwohl die Singleton-Schranke eingehalten wird, gibt es keinenbinaren (7, 23, 5)-Code.

Aufgabe 3.34 Konstruieren Sie einen binaren MDS-Code mit den Parametern(4, 8, 2).

Aufgabe 3.35 Bestimmen Sie die Prufziffer der ISBN13 978-3-7643-8611-?

Aufgabe 3.36 Bestimmen Sie die Prufziffer der ISBN13 978-3-4535-0403-? unddie zugehorige ISBN10.

Aufgabe 3.37 Bestimmen Sie die fehlenden Ziffern x und y der ISBN13 978-3-4x22-5493-y, wenn die Kontrollziffer der zugehorigen ISBN10 den Wert 4 hatte.

Aufgabe 3.38 Bestimmen Sie die Prufziffer der ISIN der hollandischen Elsevier-Aktie NL000034948?

Aufgabe 3.39 Bestimmen Sie die Prufziffer der ISIN der schweizer Nestle-AktieCH003886335?


4 LINEARE CODES

4 Lineare Codes

In diesem Abschnitt ist das Alphabet B stets ein endlicher Korper K = Fq gemaßBemerkung 2.6 b). Auf dem K-Vektorraum Kn sei durch

v · wT =n∑i=1

viwi(30)

eine symmetrische Bilinearform definiert, die aber nicht positiv definit, also keinSkalarprodukt ist. Fur jeden Unterraum V von Kn sei

V d = {w ∈ Kn | v · wT = 0 fur alle v ∈ V }(31)

der Orthogonalraum von V . Es gilt dann (V d)d = V und dim(V ) + dim(V d) = n.

Es sei π ∈ Sn eine Permutation. Durch

Pπ(v1, . . . , vn) = (vπ(1), . . . , vπ(n))(32)

wird eine lineare Abbildung Pπ : Kn → Kn definiert. Bezuglich der kanonischenBasis entspricht ihr eine Permutationsmatrix P , d.h. eine Matrix, in der in jederZeile und in jeder Spalte genau eine 1 und sonst lauter Nullen stehen. Die Abbil-dung Pπ permutiert die Koordinaten von Kn in der durch π vorgegebenen Weise.Die speziell durch π = (1 2 · · · n 1) gegebene lineare Abbildung z = Pπ heißtzyklische Verschiebung des Kn.

Definition 4.1 Ein Linearcode C ist ein Unterraum des K-Vektorraums Kn fureinen endlichen Korper K und n ∈ N. Ist k = dim(C) die Dimension von C undd = d(C) die Minimaldistanz, so spricht man auch von einem [n, k, d]-Code oder[n, k]-Code. Ist C ein [n, k]-Code, so nennt man den [n, n− k]-Code Cd den zu Cdualen Code. Gilt Cd = C, so heißt C selbstdual (vgl. Beispiel 4.17).

Beispiel 4.2 a) C = Kn ist stets ein [n, n, 1]-Linearcode.

b) Der triviale Code C = {0} ⊂ Kn ist stets ein [n, 0, 0]-Linearcode. Der dualeCode ist Cd = Kn.

c) Der q-nare Wiederholungscode C = {b | b ∈ K} ⊂ Kn ist stets ein [n, 1, n]-Linearcode. Der duale Code ist Cd = Kn−1, also der Erweiterungscode von Kn−1.Im binaren Fall ist also der MDS-Code En = {0, 1}n−1 aus Beispiel 3.25 d) einLinearcode. Er besteht aus allen Wortern c der Lange n mit geradem Gewichtgemaß der folgenden Definition. Genau fur n = 2 ist En selbstdual, stimmt alsomit dem binaren Wiederholungscode uberein.


4 LINEARE CODES

Definition 4.3 a) Fur v = (v1, . . . , vn) ∈ Kn sei

tr(v) = {i | vi 6= 0}(33)

der Trager von v und

wt(v) = d(v,0) = |{i | vi 6= 0}| = |tr(v)|(34)

das Gewicht von v.

b) Fur ∅ 6= C ⊆ Kn sei tr(C) =⋃c∈C tr(c) und

wt(C) = min{wt(c) | 0 6= c ∈ C}(35)

heißt das Minimalgewicht von C 6= {0}. Fur C = {0} werde wt(C) = 0 gesetzt.

Bemerkung 4.4 a) Ist C ⊆ Kn Linearcode und |tr(C)| < n, so haben alle Co-deworte c ∈ C an den Koordinatenstellen aus {1, . . . , n} \ tr(C) den Eintrag 0.Ein Weglassen dieser Koordinaten andert daher an der Linearitat von C eben-sowenig wie an den Abstanden zwischen den Codeworten. Man darf daher beiBedarf fur nicht-triviale Linearcodes |tr(C)| = n annehmen.

b) Ist ein [n, k]-Code C selbstdual, so folgt aus C = Cd sofort n − k = k, alson = 2k. Selbstduale Codes existieren daher nur fur gerades n und ihre Dimensionist k = n/2. Ist C dann binar, so folgt fur c ∈ C = Cd aus 0 = c · cT =

∑ni=1 c

2i =∑n

i=1 ci = 0, daß das Gewicht wt(c) gerade sein muß. Dann ist also C = Cd in Enenthalten.

Lemma 4.5 Fur jeden Linearcode C gilt wt(C) = d(C).

Beweis: Fur den trivialen Linearcode C = {0} ist wt(C) = d(C) = 0. Wegender Linearitat von C ist fur beliebige c, c′ ∈ C auch die Differenz c − c′ in Centhalten. Insbesondere liegt der Nullvektor c − c = 0 in C und daher laßt sichjeder Codevektor c ∈ C auch als Differenz c−0 = c von Codevektoren schreiben.Damit gilt fur beliebige c 6= c′ aus C wegen der Translationsinvarianz (17) derHamming-Distanz d(c, c′) = d(c− c′, 0) = wt(c− c′) = wt(c′′) mit c′′ = c− c′ 6= 0.Bildet man auf beiden Seiten das Minimum, so erhalt man die Behauptung. �


4 LINEARE CODES

Definition 4.6 Es sei C ein [n, k]-Code uber K.

a) Ist k > 0, so heißt eine k × n-Matrix G uber K eine Erzeugermatrix oderGeneratormatrix fur C, falls

KkG = {(v1, . . . , vk) ·G | vi ∈ K} = C(36)

gilt, falls also die Zeilen von G eine Basis von C bilden. Im ausgearteten FallC = {0} sei G = (0, . . . , 0) ∈ Kn die Erzeugermatrix von C. Stets hat G denRang k = dim(C).

b) Ist k < n, so heißt eine (n − k) × n-Matrix H uber K mit rang(H) = n − keine Kontrollmatrix fur C, falls

{v ∈ Kn | H · vT = 0} = C(37)

gilt. Im ausgearteten Fall C = Kn sei H = (0, . . . , 0) ∈ Kn die Kontrollmatrixvon C.

Bemerkung 4.7 Ist C ein Linearcode und Cd der dazu duale Code, so ist jedeGeneratormatrix von C eine Kontrollmatrix von Cd und umgekehrt.

Satz 4.8 Ist C nicht-trivialer [n, k]-Code uber K und H eine Kontrollmatrix vonC, so gilt

wt(C) = min{r ∈ N | es gibt r linear abhangige Spalten von H}= max{r ∈ N | je r − 1 Spalten von H sind linear unabhangig}.

Beweis: Seien h1, . . . , hn die Spalten von H. Wegen C 6= {0} sind sie linearabhangig. Sei r minimal gewahlt, so daß es r linear abhangige Spalten hi1 , . . . , hirgibt. Unmittelbar klar ist dann, daß es maximal r−1 linear unabhangige Spaltenvon H gibt, so daß die zweite Gleichheit gilt. Weiterhin gibt es ci ∈ K furi = 1, . . . , n mit ci 6= 0 genau fur i ∈ {i1, . . . , ir} und

∑ni=1 cihi = 0. Daher liegt

c = (c1, . . . , cn) wegen H · cT = 0 in C. Wegen wt(c) = r folgt wt(C) ≤ r.Angenommen, es gabe ein c′ ∈ C mit wt(c′) = r′ < r. Dann wurde H · c′T = 0die Existenz von r′ < r linear abhangigen Spalten liefern, im Widerspruch zurminimalen Wahl von r. Also gilt sogar wt(C) = r und damit auch die ersteGleichheit. �


4 LINEARE CODES

Definition 4.9 Zwei [n, k]-Linearcodes C und C ′ heißen aquivalent, wenn es einePermutation π ∈ Sn mit C ′ = Pπ(C) gibt. Ein [n, k]-Linearcode heißt systema-tisch, wenn er eine Generatormatrix G der Form

G = (Ek | G′)(38)

besitzt, wobei Ek die k×k-Einheitsmatrix und G′ eine beliebige k×(n−k)-Matrixist.

Lemma 4.10 a) Zu jedem Linearcode existiert ein aquivalenter systematischerLinearcode.

b) Ist C systematischer Linearcode mit einer Generatormatrix gemaß (38), dannist

H = (−G′T | En−k)(39)

eine Kontrollmatrix von C.

Beweis: a) Mit dem Gauß-Algorithmus laßt sich eine beliebige Generatormatrixvon C in die Gestalt (38) bringen. Die dabei notwendigen Spaltenvertauschungenbestimmen die Permutation π.

b) Multipliziert man die i-te Zeile von H mit der j-ten Spalte von GT , so ergibtsich

(−g1,i, . . . ,−gk,i, 0 . . . , 1, . . . , 0)(0, . . . , 1, . . . , 0, gj,k+1, . . . , gj,n) = −gj,i + gj,i = 0.

Also ist H Kontrollmatrix von C. �

Bemerkung 4.11 a) Ist C systematischer [n, k]-Linearcode, so nennt man dieersten k Stellen jedes Codevektors auch Informationsstellen und die letzten n−k Stellen Kontrollstellen (vgl. Definition 3.16). Die Informationsrate von C istgerade k

n.

b) Ist C ein [n, k]-Linearcode mit Generatormatrix G, dann wird durch (vgl. (36))

γ(v) = v ·G fur alle v ∈ Kk

eine injektive lineare Abbildung γ : Kk → Kn mit γ(Kk) = C definiert. Also istdann γ eine (lineare) Codierung fur den Code C. Im allgemeinen gibt es daher(abhangig von G) verschiedene Codierungen fur denselben Code.


4 LINEARE CODES

Beispiel 4.12 Fur k ≥ 2 sei Pk−1 = {〈v〉 | 0 6= v = (v1, . . . , vk)T , vi ∈ K} die

Menge aller eindimensionalen Unterraume von Kk, der projektive (Punkt-)Raumder Dimension k − 1 uber K. Weiterhin sei n = (qk − 1)/(q − 1) = |Pk−1| undPk−1 = {〈h1〉, . . . , 〈hn〉}. Definiert man H = (h1, . . . , hn) als Kontrollmatrix einesLinearcodes C, dann nennt man C einen Hamming-Code. Da H den Rang k hat,gilt dim(C) = n−k. Da ferner je zwei Spalten von H linear unabhangig sind, aberauch drei linear abhangige Spalten existieren, gilt d(C) = 3 nach Satz 4.8. Alsoist C ein [n, n− k, 3]-Code. Da außerdem die Kugelpackungsgleichung erfullt ist,ist C perfekt. Dieser Hamming-Code wird auch mit Hamq(k) bezeichnet. Der zuHamq(k) duale Code, der also H als Generatormatrix besitzt, heißt Simplex-CodeSimq(k). Man kann zeigen, daß es sich um einen (n, k, qk−1)-Code handelt.

Wahlt man etwa im binaren Fall, also bei q = 2 den Parameter k = 3, so wirdn = 23−1

2−1 = 7 und die 7 eindimensionalen Unterraume von K3 werden erzeugtvon den Vektoren 001, 010, 100, 011, 101, 110, 111. Also ist

H =

1 1 1 0 1 0 01 1 0 1 0 1 01 0 1 1 0 0 1

Kontrollmatrix des Hamming-Codes C = Ham2(3). Offensichtlich sind je zweiSpalten von H linear unabhangig, aber es gibt auch drei Spalten, die linearabhangig sind. Daher ist die Minimaldistanz tatsachlich d(C) = 3. Nach Lem-ma 3.14 hat der Erweiterungscode C die Minimaldistanz 4.

Wahlt man dagegen K = Z/(3) = {0, 1, 2}, also mit q = 3 den ternaren Fall,sowie k = 2, so wird n = 8/2 = 4 und die vier eindimensionalen Unterraume vonK2 lassen sich von den Vektoren 01, 10, 11 und 12 erzeugen. Also ist

H =(

1 1 1 02 1 0 1

)Kontrollmatrix des Hamming-Codes C = Ham3(2). Eine Generatormatrix vonC ist daher

G =(

1 0 2 10 1 2 2

).

und man erhalt C = {0000, 1021, 2012, 0122, 0211, 1110, 2220, 1202, 2101}.

Ist C ⊆ Kn ein Linearcode, dann existiert der Quotientenraum V = Kn/C,dessen Elemente die Restklassen v modulo C von v ∈ Kn sind, d.h. es ist v ={v + c | c ∈ C}.

Lemma 4.13 Ist C ein [n, k]-Linearcode uber K und H eine Kontrollmatrix vonC, dann gilt fur alle v, v′ ∈ Kn

v = v′ ⇐⇒ v ·HT = v′ ·HT .(40)


4 LINEARE CODES

Beweis: Es ist v = v′ gleichwertig zu v−v′ ∈ C und dies wiederum nach Definitonder Kontrollmatrix zu (v − v′) ·HT = 0, also zu v ·HT − v′ ·HT = 0. �

Definition 4.14 Es sei H Kontrollmatrix eines [n, k]-Linearcodes C. Fur v ∈ Kn

heißt SH(v) = v ·HT das Syndrom von v bezuglich H.

Definition 4.15 Es sei C ein [n, k]-Code uber K mit der Kontrollmatrix H.Weiterhin sei in jeder Restklasse v ein Restklassenfuhrer fv mit

wt(fv) = min{wt(v + c) | c ∈ C}

gewahlt. Bei der Syndrom-Decodierung wird zu einem empfangenen Wort c′ dasSyndrom v = c′ ·HT berechnet und δ(c′) = c′ − fv gesetzt.

Bemerkung 4.16 a) Der Restklassenfuhrer ist nicht immer eindeutig bestimmt.Es gibt daher i. a. verschiedene Moglichkeiten der Decodierung.

b) Es ist stets δ(c′) ∈ C und das Decodierschema ist vollstandig.

Beispiel 4.17 Es sei B = K = Z/(2) der zweielementige Korper und der [4, 2]-Linearcode C ⊂ K4 sei gegeben durch die Generatormatrix

G =(

1100

0011

).

Wegen G ·GT = O ist G auch Kontrollmatrix von C = Cd, d. h. C ist selbstdual.(Dieses Beispiel eines selbstdualen Binarcodes der Lange n = 4 laßt sich schnellzu einem derartigen Code fur beliebige gerade Lange n = 2k erweitern, vgl. auchAufgabe 4.32.)

Eine Restklasse von K4/C ist immer gegeben durch C selbst, in diesem Fallalso durch C0 = C = {0000, 1100, 0011, 1111}. Hieran kann man auch sofort dieMinimaldistanz d(C) = 2 ablesen. Der eindeutig bestimmte Restklassenfuhrerin C0 ist stets der Nullvektor v0 = 0 = 0000. Zur Bestimmung der nachstenRestklasse C1 wahlt man einen Vektor aus K4 \ C0 mit minimalem Gewicht,hier also einen der Einheitsvektoren, willkurlich aus. Fur v1 = 0001 erhalt manso C1 = {0001, 0010, 1101, 1110}. Analog bestimmt man die nachste RestklasseC2 durch Auswahl eines Restklassenfuhrers c2 ∈ K4 \ (C0 ∪ C1) mit minimalemGewicht. Wiederum kann man einen der beiden verbliebenen Einheitsvektorenfrei wahlen. Fur c2 = 0100 erhalt man so C2 = {0100, 0111, 1000, 1011}. Dienoch ubrigen vier Vektoren bilden dann die vierte und letzte Nebenklasse C3 =


4 LINEARE CODES

{0101, 0110, 1001, 1010}. Da alle das Gewicht 2 haben, kann man einen beliebigenvon ihnen als Restklassenfuhrer wahlen, beispielsweise c3 = 0101.

Durch Multiplikation mit der Kontrollmatrix H = G erhalt man die SyndromesH(c0) = 00, sH(c1) = 01, sH(c2) = 10 und sH(c3) = 11.

Empfangt man nun beispielsweise das Wort c′ = 1001, so berechnet man v =sH(c′) = c′ · HT = 11 6= 00, woran man erkennt, daß ein Ubertragungsfehlervorliegt. Man korrigiert ihn zu c = c′ − c3 = 1001− 0101 = 1100 ∈ C. Bei Wahlvon 0110 als Restklassenfuhrer von C3 hatte man dagegen zu 1111 korrigiert.

Beispiel 4.18 Es seien K ein Korper mit q Elementen und d, n ∈ N mit 2 ≤d ≤ n ≤ q. Weiterhin sei a = (a1, . . . , an) ∈ Kn mit paarweise verschiedenen aiund v = (v1, . . . , vn) ∈ Kn mit vi 6= 0 fur alle i. Die (d− 1)× n-Matrix H werdedefiniert durch

H =

v1 . . . vna1v1 . . . anvna21v1 . . . a2nvn

......

...ad−21 v1 . . . ad−2n vn

.

Der verallgemeinerte Reed-Solomon-Code GRSd(a, v) ist dann

GRSd(a, v) = {c ∈ Kn | H · cT = 0}.

Ist α ∈ K ein primitives Element, d. h. gilt K \ {0} = {1, α, α2, . . . , αq−2}, undsetzt man a = v = (1, α, . . . , αq−2), so nennt man den Code GRSd(a, v) einenReed-Solomon-Code kurz: RS-Code (Irving Stoy Reed (1923 - 2012), GustaveSolomon (1930 - 1996) im Jahr 1960).

Bemerkung 4.19 a) Es ist GRSd(a, v) ein [n, n− d+ 1, d]-Code und damit einMDS-Code.

b) Fur die Decodierung von Reed-Solomon-Codes kennt man Verfahren, die we-sentlich gunstiger bezuglich des Speicherplatzbedarfes sind als das in Beispiel 4.17beschriebene Verfahren, das ganz allgemein fur Linearcodes gilt. Einzelheitenhierzu findet man beispielsweise in dem Buch Reed-Solomon Codes and TheirApplications von Stephen B. Wicker und Vijay K. Bhargava, IEEE, New York1994. Ein [255, 223, 33]-Reed-Solomon-Code uber K = F8 wurde und wird beider Datenubertragung von zahlreichen Tiefenraumsonden verwendet, z. B. Voya-ger I und II (Uranus und Neptun), Galileo (Jupiter), Cassini (Saturn), Huygens(Titan), Giotto (Halley), Ulysses, Soho (Sonne).


4 LINEARE CODES

c) Ein [255, 251, 5]-Reed-Solomon-Code uber K = F8 ist Ausgangspunkt fur dieKonstruktion der Codierung, mit der Daten auf den gangigen Compact Discsdargestellt werden. Bei der konkreten Konstruktion werden noch die Technikender Codeverkurzung und Codeverschachtelung benutzt:

Definition 4.20 Es seien n ≥ 2, C ein [n, k]-Code uber K und i ∈ {1, . . . , n}.Dann heißt

C = Ci = {(c1, . . . , ci−1, ci+1, . . . , cn) | (c1, . . . , ci−1, 0, ci+1, . . . , cn) ∈ C}(41)

Verkurzung von C an der Stelle i und

C∗ = C∗i = {(c1, . . . , ci−1, ci+1, . . . , cn) | (c1, . . . , ci−1, ci, ci+1, . . . , cn) ∈ C}(42)

Punktierung von C an der Stelle i.

Definition 4.21 Es sei C ein [n, k, d]-Code und t ∈ N. Dann heißt der [tn, tk, d]-Code

C(t) = {(c11, . . . , ct1, . . . , c1n, . . . , ctn) | (ci1, . . . , cin) ∈ C, i = 1, . . . , t}

die Codeverschachtelung von C zur Tiefe t.

Bemerkung 4.22 a) Die Codeworte aus C(t) sind die spaltenweise gelesenenEintrage der Matrizen c11 . . . c1n

......

...ct1 . . . ctn

.Kann C Fehlerbundel der Lange ` korrigieren, so kann C(t) Fehlerbundel derLange t` korrigieren. Man beachte aber, daß C und C(t) dieselbe Minimaldistanzhaben.

b) Dieselbe Technik, Worter zeilenweise in eine Matrix zu schreiben und dannspaltenweise auszulesen, wird auch in der Kryptographie bei der Spaltentrans-position angewandt. Dort werden die Spalten aber noch vor dem Auslesen einerfesten Permutation unterworfen.

Definition 4.23 Ein Vektor v = (0, . . . , 0, vi, . . . , vi+`−1, 0, . . . , 0) ∈ Kn mit vi 6=0 6= vi+`−1 heißt (Fehler-)Bundel der Lange `.


4 LINEARE CODES

Lemma 4.24 Es sei Ci ein [n, ki, di]-Code uber K fur i = 1, 2. Dann ist

C = C1∞C2 = {(c1, c1 + c2) | ci ∈ Ci} ⊆ K2n(43)

ein [2n, k1 + k2,min{2d1, d2}]-Code uber K.

Beweis: Die Abbildung ϕ : C1 ⊕ C2 → C gemaß ϕ((c1, c2)) = (c1, c1 + c2) istoffensichtlich surjektiv, injektiv und linear. Also gilt dim(C) = dim(ϕ(C1⊕C2)) =dim(C1 ⊕ C2) = k1 + k2. Ist C = {0} trivial, so muß offensichtlich dasselbe furC1 und C2 gelten. Also hat man d(C) = 0 = min{2d1, d2}.

Sei also C 6= {0} und 0 6= c = (c1, c1 + c2) ∈ C. Fur c2 = 0 gilt wegen c1 6= 0dann wt(c) = 2wt(c1) ≥ 2d1. Fur c2 6= 0 folgt wegen wt(c1) ≥ |tr(c1) ∩ tr(c2)|

wt(c) = wt(c1) + wt(c1 + c2)

≥ wt(c1) + wt(c1) + wt(c2)− 2|tr(c1) ∩ tr(c2)|≥ wt(c2) ≥ d2.

Insgesamt folgt d(C) ≥ min{2d1, d2}. Fur c1 = 0 und c2 ∈ C2 mit minimalemGewicht oder c1 ∈ C1 mit minimalem Gewicht und c2 = 0 wird dieses Minimumaber auch erreicht. �

Die in (43) beschriebene Konstruktion geht auf Morris Plotkin (1960) zuruck.

Beispiel 4.25 Es sei K = {0, 1} und r,m ∈ N0 mit 0 ≤ r ≤ m. Die binarenReed-Muller-Codes RM(r,m) werden rekursiv definiert. Sie wurden 1954 von Da-vid Eugene Muller (1924 - 2008) und Irving Stoy Reed unabhangig voneinanderbeschrieben. Es sei RM(0,m) der binare Wiederholungscode der Lange 2m, alsoein [2m, 1, 2m]-Code, RM(m,m) = K2m und

RM(r,m) = RM(r,m− 1)∞RM(r − 1,m− 1)

fur m = 1, 2, . . . und jeweils 1 ≤ r ≤ m−1. Der Reed-Muller-Code r-ter OrdnungRM(r,m) ist ein [2m,

∑ri=0

(mi

), 2m−r]-Code. Der [32, 6, 16]-Code RM(1, 5) wur-

de bei den Mariner-Marssonden 1969 bis 1976 zur Bildubertragung benutzt. Eskonnten bis zu 7 Fehler pro Codewort korrigiert werden. Die 26 = 64 Codeworteentsprachen den verschiedenen Helligkeiten der Bildpunkte.

Es ist also

RM(1, 5) = RM(1, 4)∞RM(0, 4)


4 LINEARE CODES

= ((RM(1, 3)∞RM(0, 3))∞RM(0, 4)= (((RM(1, 2)∞RM(0, 2))∞RM(0, 3))∞RM(0, 4)= (((RM(1, 1)∞RM(0, 1))∞RM(0, 2))∞RM(0, 3))∞RM(0, 4).

Hierin sind speziell RM(1, 1) = K2 = {00, 01, 10, 11} und RM(0, 1) = {00, 11},woraus sich RM(1, 2) = {0000, 0011, 0101, 0110, 1010, 1001, 1111, 1100} ergibt.Also besteht RM(1, 2) genau aus allen binaren Vektoren der Lange 4 mit gerademGewicht. Er kann also auch als Erweiterungscode von C = K3 aufgefaßt werden.

Der nachste Konstruktionsschritt ergibt dann wegen RM(0, 2) = {0000, 1111}den Code

RM(1, 3) = {00000000, 00001111, 00110011, 00111100,01010101, 01011010, 01100110, 01101001,10101010, 10100101, 10011001, 10010110,11111111, 11110000, 11001100, 11000011}.

Dieser besitzt bereits die Minimaldistanz 4 und kann ebenso wie der [7, 4, 3]-Hammingcode, der allerdings eine Stelle kurzer ist, einfache Fehler korrigieren.

Satz 4.26 (Griesmer-Schranke) (James Hugo Griesmer, 1929 - 2011) Exi-stiert ein [n, k, d]-Code uber K, so gilt

n ≥k−1∑i=0

⌈d

qi

⌉.(44)

Beweis: Der Beweis erfolgt durch Induktion nach k.

Fur k = 0 und k = 1 besagt (44) gerade n ≥ 0 bzw. n ≥ d, was jeweils richtig ist.

Sei k ≥ 2 und G eine Generatormatrix eines [n, k, d]-Codes C, wobei die ersteZeile von G einen Codevektor c 6= 0 von minimalem Gewicht d enthalte. DurchUbergang zu einem aquivalenten Linearcode darf

G =(

z

G1 G2

)mit z = (1, . . . , 1, 0, . . . , 0), G1 ∈Mk−1,d(K) und G2 ∈Mk−1,n−d(K) angenommenwerden, wobei z genau in den ersten d Koordinaten Einsen enthalt. Zeige nun,daß G2 den Rang k − 1 hat.


4 LINEARE CODES

Ware dies nicht der Fall, so konnte man durch Zeilenumformungen die erste Zeilevon G2 zu einer Nullzeile machen und in der ersten Zeile von G1 mußten alleElemente von 0 verschieden sein, wegen des minimalen Gewichtes d von z. Dannkonnte man aber aus den ersten beiden Zeilen von G durch Subtraktion ein von0 verschiedenes Codewort bilden, das ein Gewicht kleiner als d = d(C) hat, wasunmoglich ist. Also erzeugt G2 einen [n− d, k − 1, d2]-Code C2.

Sei (u|v) mit u = (u1, . . . , ud) eine beliebige Zeile von (G1|G2). Fur jedes b ∈ Ksei nb = |{i | ui = b}| und dann na = max{nb | b ∈ K} fur ein a ∈ K. Dann giltna ≥ ddq e.

Aus 0 6= (u|v)− az ∈ C und daher wt((u|v)− az) ≥ d folgt wt(v) ≥ ddqe. Durch

elementare Zeilenumformungen von (G1|G2) kann man dies fur jedes v = v2 ∈ C2

erreichen.

Nach Induktionsvoraussetzung gilt

n− d ≥k−2∑i=0

d dqie ≥

k−2∑i=0

d d

qi+1e =

k−1∑i=1

d dqie,

also

n ≥k−1∑i=1

d dqie+ dde =

k−1∑i=0

d dqie.

�

Folgerung 4.27 Die binaren Reed-Muller-Codes RM(1,m) erster Ordnung er-reichen die Griesmer-Schranke.

Beweis: Fur die binaren Codes RM(1,m) lauten die Parameter q = 2, n =2m, k = m+ 1 und d = 2m−1. Also gilt

2m ≥m∑i=0

d2m−1

2ie = 2m−1 + . . .+ 2 + 1 + 1 = 2m,

also tatsachlich die Gleichheit. �

Satz 4.28 (Gilbert-Varshamov-Schranke) (Edgar Nelson Gilbert (1923 - ),Rom Varshamov) Es sei K ein Korper mit q Elementen. Ferner seien n, k, d ∈ Nmit k ≤ n und

qn−k >d−2∑i=0

(n− 1

i

)(q − 1)i.(45)

Dann gibt es einen [n, k, d′]-Code mit d′ ≥ d.


4 LINEARE CODES

Beweis: Fur k = n ist qn−k = q0 = 1 und die Summe auf der rechten Seitevon (45) muß 0 sein, was nur fur d = 1 moglich ist. Dann ist aber C = Kn mitd′ = d = 1 ein Linearcode der behaupteten Art.

Sei also k < n und V = Kn−k sowie v1, . . . , vn−k Basis von V . Weiterhin sei-en vn−k+1, . . . , vn−k+s ∈ V, (s ≥ 0) so gewahlt, daß je d − 1 Vektoren aus Vs ={v1, . . . , vn−k, vn−k+1, . . . , vn−k+s} linear unabhangig sind. Die Anzahl der Vek-toren, die sich als Linearkombinationen von hochstens d − 2 Vektoren aus Vsdarstellen lassen, ist kleiner oder gleich

d−2∑i=0

(n− k + s

i

)(q − 1)i.

Dabei beschreibt der Binomialkoeffizient alle moglichen Wahlen von jeweils iVektoren aus Vs und die Potenz von q−1 alle Moglichkeiten, i von 0 verschiedeneKoeffizienten vor diese Vektoren zu setzen. Ist diese Summe nun echt kleiner alsqn−k, so existiert ein vn−k+s+1 ∈ V \ Vs, so daß je d − 1 Vektoren aus Vs+1 =Vs ∪ {vn−k+s+1} linear unabhangig sind und sich folglich die Menge Vs noch umeinen Vektor vergroßern laßt. Daher besagt (45) gerade, daß sich s bis s = kvergroßern laßt. Also existiert eine Menge Vk = {v1, . . . , vn} fur die je d− 1 ihrerVektoren linear unanbhangig sind. Schreibt man diese Vektoren als Spalten einerMatrix H, so ist diese eine (n− k)× n-Matrix und nach Satz 4.8 Kontrollmatrixeines [n, k, d′]-Linearcodes mit d′ ≥ d. �

Bemerkung 4.29 Auch sogenannte 1n

-Faltungscodes sind spezielle binare Li-nearcodes, die prinzipiell durch geeignete Generatormatrizen darstellbar sind,die sich aber wesentlich leichter mit Hilfe von Schieberegistern definieren lassenund zu deren Analyse Generatorpolynome wie im nachsten Kapitel herangezogenwerden.

Aufgabe 4.30 Bestimmen Sie Generatorenmatrizen und Kontrollmatrizen zuden in Beispiel 4.2 erwahnten Codes.

Aufgabe 4.31 Ermitteln Sie die Anzahl aller binaren [n, k]-Codes fur n ≤ 4.(Hinweis: Bestimmen Sie fur k = 0, 1, . . . , n jeweils alle k-dimensionalen Un-terraume von {0, 1}n indem Sie mogliche Basisvektoren auswahlen.) Geben Sieaus jeder Klasse untereinander aquivalenter Codes jeweils einen an.

Aufgabe 4.32 Es sei p eine ungerade Primzahl, die p ≡ 1 mod 4 erfullt, undK = Z/(p). (Dann gibt es, wie fur K = Z/(2), ein Element a ∈ K mit a2 = −1.)Konstruieren Sie in Analogie zu Beispiel 4.17 fur jedes gerade n = 2k ∈ N einenselbstdualen Linearcode C ⊆ Kn.


4 LINEARE CODES

Aufgabe 4.33 Zeigen Sie, daß auch fur p = 3, 7 und 11 selbstduale Linearcodesder Lange n = 4 uber K = Z/(p) existieren.

Aufgabe 4.34 Gegeben sei der ternare [5, 3]-Linearcode C durch seine Genera-tormatrix 1 0 0 1 0

0 1 0 2 10 0 1 0 2

.Bestimmen Sie die Minimaldistanz d(C) und eine Generatormatrix der Verkur-zung C3 von C.

Aufgabe 4.35 Uber dem Korper Z/(17) sei der [3, 2]-Linearcode C durch dieGeneratormatrix

G =(

7 8 114 16 11

)gegeben. Bestimmen Sie eine Kontrollmatrix H und die Minimaldistanz von C.Decodieren Sie außerdem das Codewort c = (12, 5, 4).

Aufgabe 4.36 Fur jeden Wert x ∈ Z/(5) sei die Geratormatrix Gx eines [6, 3]-Linearcodes Cx gegeben durch

Gx =

2 1 0 2 2 + x 03 1 1 2 1 + x 2− x1 1 1 0 0 1− 3x

.Fur welche Werte von x ist Cx selbstdual?

Berechnen Sie alle Werte von x, fur welche die Minimaldistanz d(Cx) = 2 erfullt.

Aufgabe 4.37 Gegeben sei der binare [4, 2]-Linearcode C durch seine Genera-tormatrix (

1 1 1 01 0 1 1

).

Empfangen werde der Vektor c′ = 1100. Begrunden Sie, daß ein Ubertragungs-fehler aufgetreten ist und decodieren Sie mit Hilfe einer Syndrom-Decodierungzu einem (moglichen) “Klartext” v = (k1, k2) gemaß Bemerkung 4.11.

Aufgabe 4.38 Es sei C ein [n, k, d]-Linearcode mit 1 < k < n, C2 sein 2-facherWiederholungscode und C2 = C × C. Bestimmen Sie die Minimaldistanz desPlotkin-Codes C2∞C2 und zeigen Sie, daß dessen Informationsrate echt kleinerals jene des Codes C ist.


4 LINEARE CODES

Aufgabe 4.39 Uber dem endlichen Korper K sei Ci fur i = 1, 2 ein [n, ki, di]-Linearcode, so daß das Plotkin-Produkt C1∞C2 ein MDS-Code ist. Zeigen Sie,daß dann C1 = Kn gilt und es sich bei C2 um einen MDS-Code mit d2 ≤ 2handelt.


5 ZYKLISCHE CODES

5 Zyklische Codes

Auch in diesem Abschnitt sei B = K = Fq ein endlicher Korper. Mit K[x] werdeder Polynomring uber K bezeichnet und fur n ∈ N sei

Vn = {n−1∑ν=0

aνxν | aν ∈ K} ⊂ K[x]

definiert. Dann bildet Vn einen n-dimensionalen Vektorraum, der vermoge derIsomorphie

(an−1, . . . , a0) 7→n−1∑ν=0

aνxν

mit Kn identifiziert werden kann. Ist p(x) ∈ K[x] ein Polynom vom Grad n uberK, so existiert fur f(x), g(x) ∈ Vn die Division mit Rest gemaß f(x) · g(x) =q(x) · p(x) + r(x) und der eindeutig bestimmte Rest r(x) liegt in Vn. Man kanndaher auf Vn eine Multiplikation erklaren gemaß

f(x) ∗ g(x) = r(x).(46)

Dann wird (Vn,+, ∗) eine K-Algebra, also insbesondere ein kommutativer Ringmit Einselement. Dieser Ring ist isomorph zum Restklassenring K[x]/(p(x)) vonK[x] nach dem von p(x) erzeugten Hauptideal und damit selbst ein Hauptideal-ring. Genau dann ist (Vn,+, ∗) ein Korper, wenn p(x) irreduzibel in K[x] ist, wennalso jeder Teiler von p(x) entweder ein konstantes Polynom oder ein Polynom vomGrad n ist.

Im folgenden sei ∗ die durch p(x) = xn−1 definierte Multiplikation auf Kn = Vn.

Definition 5.1 Ein [n, k]-Linearcode C heißt zyklisch genau dann, wenn z(C) =C fur die zyklische Verschiebung z : Kn → Kn gilt.

Beispiel 5.2 Der triviale Code C = {0} und der Code C = Kn sind zyklischeCodes. Ebenso ist der q-nare Wiederholungscode ein zyklischer Code. Im binarenFall sind die Codes En, die aus allen Wortern der Lange n mit geradem Gewichtbestehen, zyklisch.

Satz 5.3 a) Ein [n, k]-Linearcode ist genau dann zyklisch, wenn zm(c) ∈ C furalle c ∈ C und m ∈ N gilt.


5 ZYKLISCHE CODES

b) Der Durchschnitt zyklischer Linearcodes der gleichen Lange n ist wieder zy-klisch.

c) Fur alle v ∈ Kn und alle m ∈ N gilt zm(v) = xm ∗ v.

d) Ist C zyklischer [n, k]-Linearcode, so ist C Ideal von (Vn,+, ∗).

e) ∅ 6= C ⊆ Kn ist genau dann zyklischer Linearcode, wenn C Ideal von (Vn,+, ∗)ist.

Beweis: a) Sei C zyklischer Code. Fur c ∈ C gilt dann z(c) ∈ z(C) = C, alsodie Behauptung fur m = 1. Gelte die Behauptung also fur ein m ∈ N. Dann folgtzm+1(c) = z(zm(c)) ∈ z(C) = C. Also gilt zm(c) ∈ C fur alle c ∈ C und m ∈ N.Umgekehrt folgt hieraus fur m = 1 sofort z(C) ⊆ C, d. h. z(C) ist Unterraum vonC. Da die zyklische Verschiebung aber injektiv ist, haben beide Raume dieselbeDimension, woraus dann z(C) = C folgt.

b) Der Durchschnitt beliebiger Unterraume von Kn ist wieder ein Unterraum.Der Durchschnitt zyklischer Unterraume ist wegen a) aber wieder zyklisch.

c) Es sei v = (vn−1, . . . , v0) = v(x) = vn−1xn−1 + . . .+ v1x+ v0 ∈ Kn = Vn. Dann

gilt z(v) = (vn−2, . . . , v0, vn−1) und x ∗ v(x) = vn−1xn + vn−2x

n−1 + . . . + v0x =vn−1x

n− vn−1 + vn−2xn−1 + . . .+ v0x+ vn−1 = vn−2x

n−1 + . . .+ v0x+ vn−1 modulo(xn − 1). Also sind z(v) und x ∗ v gleich. Der Rest folgt jetzt durch Induktionnach m.

d) Da C Unterraum von Kn ist, ist (C,+) Untergruppe von (Kn,+) = (Vn,+).Ist c ∈ C, so liegt x∗c wieder in C und damit xm∗c fur alle m ∈ N. Mit xm∗c liegtdann aber auch amx

m ∗ c im Unterraum C fur alle am ∈ K. Da auch die Additionvon endlich vielen Elementen aus C nicht aus diesem Unterraum herausfuhrt, giltf(x) ∗ c ∈ C fur alle f(x) ∈ Vn. Also ist C Ideal von (Vn,+, ∗).

e) Wegen d) ist nur zu zeigen, daß jedes Ideal C von (Vn,+, ∗) zyklischer Linear-code ist. Dabei ist jedes solche Ideal offensichtlich bereits ein Unterraum, also einLinearcode. Außerdem gilt x ∗ c ∈ C fur jedes c ∈ C. Wegen z(c) = x ∗ c wie imBeweis von c) folgt z(c) ∈ C und damit nach a), daß C zylischer Code ist. �

Bemerkung 5.4 Uber e) hinaus gilt sogar: C ist genau dann zyklischer Linear-code, wenn es ein g ∈ Kn = Vn mit g(x) | xn− 1 und C = g ∗ Vn gibt, d. h. wennC Hauptideal von (Vn,+, ∗) ist. Ein derartiges g(x) ist durch die Forderung “g(x)normiert” eindeutig bestimmt. Dabei gehoren zu den Extremfallen C = {0} undC = Kn aus Beispiel 5.2 gerade die trivialen Teiler g(x) = xn − 1 und g(x) = 1.


5 ZYKLISCHE CODES

Satz 5.5 Es seien n ∈ N, g(x) ∈ K[x] mit grad(g(x)) = m < n, g(x) | xn − 1und g(x) normiert.

a) Ist g(x) = xm + gm−1xm−1 + . . .+ g0, dann wird durch

G =

xn−m−1g(x)

...xg(x)g(x)

=

1 gm−1 . . . g1 g0 0 . . . 0

0 1 gm−1 . . . g1 g0...

... 00 . . . 0 1 gm−1 . . . g1 g0

(47)

eine Generatormatrix eines [n, n−m]-Linearcodes C definiert.

b) Ist C gemaß (47) gegeben, dann gilt fur alle v = v(x) ∈ Kn = Vn

v ∈ C ⇐⇒ g(x) | v(x).(48)

c) Ist C gemaß (48) gegeben, dann ist C zyklischer [n, n−m]-Linearcode.

Beweis: a) Offensichtlich ist G eine (n−m)× n-Matrix mit Rang(G) = n−m,also definiert G einen [n, n−m]-Linearcode C.

b) Es ist v ∈ C genau dann, wenn v(x) Linearkombination der Zeilen von G ist,was offensichtlich gleichwertig zu v(x) = a(x)g(x) mit einem Polynom a(x) vomGrad hochstens n−m− 1 ist, wenn also g(x)|v(x) in Vn gilt.

c) Es bleibt zu zeigen, daß z(v(x)) ∈ C fur alle v(x) ∈ C gilt. Sei also v =(vn−1, . . . , v0) ∈ Kn mit g(x)|v(x) nach b). Dann folgt z(v(x)) = xv(x)−vn−1xn+vn−1 = xv(x)−vn−1(xn−1) und wegen g(x)|(xn−1) teilt g(x) beide Summanden.Also gilt g(x)|z(v(x)) und damit z(v(x)) ∈ C nach b). �

Definition 5.6 Es sei n ∈ N, g(x) ∈ K[x] mit grad(g(x)) = m < n, g(x) | xn−1und g(x) normiert. Dann heißt g(x) Generatorpolynom des gemaß (47) definiertenzyklischen [n, n−m]-Linearcodes C.

Bemerkung 5.7 a) Aus g(x) | xn−1 folgt g0 6= 0 und es existiert ein h(x) ∈ K[x]mit g(x)h(x) = xn − 1, also ist auch h(x) Generatorpolynom eines zyklischenCodes.

b) Aus (47) folgt sofort, daß ein zyklischer Code systematisch ist.

c) Ist C zyklischer Linearcode, dann ist das gemaß Bemerkung 5.4 existierende,eindeutig bestimmte Polynom g(x) ∈ Vn gerade Generatorpolynom von C.


5 ZYKLISCHE CODES

Definition 5.8 Sei g(x) ∈ K[x] Generatorpolynom von C ⊆ Kn. Dann heißth(x) ∈ K[x] mit g(x)h(x) = xn − 1 Kontrollpolynom von C.

Satz 5.9 Ist h(x) ∈ K[x] Kontrollpolynom von C ⊆ Kn, dann gilt

v ∈ C ⇐⇒ v ∗ h = 0,(49)

und mit grad(h(x)) = k = n−m, also h(x) = xk + hk−1xk−1 + . . .+ h1x+ h0, ist

H =

h0 h1 . . . hk−1 1 0 . . . 0

0 h0 h1 . . . hk−1 1...

... 00 . . . 0 h0 h1 . . . hk−1 1

(50)

Kontrollmatrix von C.

Beweis: Ist v(x) ∈ C, dann existiert nach (48) ein f(x) ∈ K[x] mit v(x) =f(x)·g(x) = f(x)∗g(x), woraus v(x)∗h(x) = f(x)∗g(x)∗h(x) = f(x)∗(xn−1) = 0folgt.

Umgekehrt ergibt sich aus v(x) ∗ h(x) = 0 sofort v(x) · h(x) = f(x) · (xn − 1) furein f(x) ∈ K[x], also v(x) ·h(x) = f(x) · g(x) ·h(x) und daher v(x) = f(x) · g(x).

Die Behauptung uber H ist dann klar. �

Bemerkung 5.10 Ist C ein zyklischer [n, k]-Linearcode mit Generatorpolynomg(x), dann wird durch

γ((vk−1, . . . , v0)) =

(k−1∑ν=0

vνxν

)g(x)

eine injektive lineare Abbildung γ : Kk → Vn = Kn mit γ(Kk) = C definiert. Alsoist γ eine (lineare) Codierung fur den Code C. Wird w = (wn−1, . . . , w0) ∈ Kn

mit w ∗ h 6= 0 empfangen, so liegt ein Ubertragungsfehler vor. Im anderen Fallliefert eine Division von w(x) durch g(x) das codierte Zeichen.

Beispiel 5.11 Unter dem Namen cyclic redundancy check codes (CRC-Codes)werden binare zyklische Codes in zahlreichen Anwendungen benutzt. Hier isteine kleine Auswahl mit Polynomen kleinen Grades.


5 ZYKLISCHE CODES

a) Der CRC-1 0x1 (auch Parity-Check-Code) mit dem irreduziblen Generatorpo-lynom g(x) = x+ 1 realisiert fur jede Blocklange n ≥ 2 den Paritatscode En, deraus allen Wortern gerader Lange besteht. Er hat bekanntlich den Minimalabstandd = 2.

b) Der CRC-3K 0x3 mit dem irreduziblen Generatorpolynom g(x) = x3 + x + 1hat die Blocklange n = 7 und ist identisch mit dem [7,4]-Hammingcode, hat alsoden Minimalabstand d = 3.

c) Der CRC-4 0x3 (auch CRC-CCITT (Comite consultatif international telepho-nique et telegraphique) oder CRC-4-ITU (International Telecommunication Uni-on)) mit dem irreduziblen Generatorpolynom g(x) = x4+x+1 hat die Blocklangen = 15 und ist identisch mit dem [15,11]-Hammingcode, hat also den Minimal-abstand d = 3.

d) Der CRC-5-ITU 0x15 mit dem Generatorpolynom g(x) = x5 + x4 + x2 + 1 =(x + 1)(x4 + x + 1) hat die Blocklange n = 15 und ist ein verkurzter [15,10]-Hammingcode. Er wird bei der Ubertragung mit Bluetooth verwendet.

e) Der CRC-5-USB 0x05 mit dem irreduziblen Generatorpolynom g(x) = x5 +x2+1 hat die Blocklange n = 31 und ist identisch mit dem [31,26]-Hammingcode,hat also auch den Minimalabstand d = 3. Er wird bei der USB-Ubertragungangewandt.

f) Der CRC-5-EPC 0x09 mit dem irreduziblen Generatorpolynom g(x) = x5 +x3 + 1 wird bei RFID-Verfahren (radio-frequency identification) zur Erzeugungdigitaler Signaturen von Objekten benutzt.

g) Der CRC-6-ITU 0x03 mit dem irreduziblen Generatorpolynom g(x) = x6+x+1hat die Blocklange n = 63 und den Minimalabstand d = 3.

h) Der CRC-6-DARC 0x15 (data radio channel) mit dem Generatorpolynomg(x) = x6 + x4 + x2 + 1 = (x+ 1)6 wird zur Rundfunkubertragung benutzt.

i) Der CRC-7 0x09 mit dem irreduziblen Generatorpolynom g(x) = x7+x3+1 hatdie Blocklange n = 127 und ist identisch mit dem [127,120]-Hammingcode, hatalso ebenfalls den Minimalabstand d = 3. Er wird bei SD/MMC-Karten benutzt.

j) Der CRC-8-CCITT 0x07 mit dem Generatorpolynom g(x) = x8 +x2 +x+ 1 =(x + 1)(x7 + x6 + x5 + x4 + x3 + x2 + 1) hat die Blocklange n = 127 und denMinimalabstand d = 4.

k) Der CRC-8-Dallas/Maxim 0x31 mit dem Generatorpolynom g(x) = x8 + x5 +x4 + x+ 1 = (x+ 1)(x7 + x6 + x5 + x3 + x2 + x+ 1) hat die Blocklange n = 127


5 ZYKLISCHE CODES

und den Minimalabstand d = 4. Er wird in den seriellen Schnittstellen von One-Wire-Systemen der Firma Dallas Semiconductor Corp. angewandt.

l) Der CRC-8-SAE-J1850 0x1D mit dem irreduziblen Generatorpolynom g(x) =x8 +x4 +x3 +x2 + 1 hat die Blocklange n = 255 und den Minimalabstand d = 3.Er wird bei der Europaischen Rundfunkunion verwendet.

m) Der CRC-8-WCDMA 0x9B mit dem Generatorpolynom g(x) = x8+x7+x4+x3 + x+ 1 = (x+ 1)(x7 + x3 + 1) wird beim Mobilfunk angewandt.

n) Der CRC-8 0xD5 mit dem Generatorpolynom g(x) = x8+x7+x6+x4+x2+1 =(x+ 1)(x7 + x5 + x4 + x+ 1).

Wenn das Generatorpolynom den Faktor x + 1 enthalt, werden alle Fehler mitungeradem Gewicht erkannt.

Beispiel 5.12 Die Reed-Solomon-Codes sind zyklische Codes. Daher werden sieauch bei der Codierung von Audio-CDs eingesetzt, wo die Korrektur von Feh-lerbundeln (Kratzern) sehr wichtig ist.

Satz 5.13 Ist C zyklischer [n, k]-Linearcode, dann existiert ein Decodierschemaδ : D → C, das jedes Fehlerbundel der Lange m mit 1 ≤ m ≤ n− k erkennt.

Beweis: Sei e ∈ Kn \ {0} ein solches Fehlerbundel und b ∈ Kn = Vn mitgrad(b(x)) = m − 1 < n − k und e = zj(b) fur ein j ∈ N. Da C Linearcodeist, genugt es, e 6∈ C zu zeigen. Sei dazu g(x) Generatorpolynom von C, alsograd(g(x)) = n−k. Ware e ∈ C, dann auch b = zn−j(e) ∈ C. Dies ist aber wegengrad(b(x)) < grad(g(x)) unmoglich. �

Beispiel 5.14 Fur kleine n lassen sich alle binaren zyklischen Linearcodes derLange n systematisch bestimmen:

Nach Beispiel 5.2 sind fur jedes n stets {0} und Kn sowie der Wiederholungscodeder Lange n zyklisch. Fur n = 1 und n = 2 sind dies auch samtliche Linearcodesund damit samtliche zyklischen Codes. Fur n = 1 stimmen K1 = K und derWiederholungscode sogar noch uberein.

Fur n = 3 erhalt man alle weiteren zyklischen Codes durch ihre Generatorpoly-nome g(x), die Teiler von x3−1 sind. Wegen x3−1 = (x−1)(x2 +x+1) kommennur g(x) = x − 1 = x + 1 und das irreduzible Polynom h(x) = x2 + x + 1 inFrage. Dabei erzeugt g(x) den zyklischen Code C = {000, 011, 110, 101} = E3,


5 ZYKLISCHE CODES

der Erweiterungscode von K2 ist. Der von h(x) erzeugte hierzu duale Code istgerade der Wiederholungscode.

Fur n = 4 zerlegt man entsprechend x4−1 in unzerlegbare Faktoren: x4−1 = (x2−1)(x2+1) = (x2−1)2 = ((x−1)(x+1))2 = (x−1)4. Dies ergibt die Generatorpoly-nome g1(x) = x−1, g2(x) = (x−1)2 und g3(x) = (x−1)3 = x3+x2+x+1. Hierbeiliefert g1(x) den Code C1 = {0000, 0011, 0110, 1100, 1001, 1010, 0101, 1111} = E4

und g2(x) den selbstdualen Code C2 = {0000, 0101, 1010, 1111}, wahrend g3(x)wieder den Wiederholungscode erzeugt, der zu C1 dual ist.

Beispiel 5.15 Seien K = Z/(2), n = 7 und g(x) = x3 + x + 1 ∈ K[x]. Wegen(x7 − 1) : g(x) = x4 + x2 + x + 1 wird durch g(x) ein zyklischer [7, 4]-CodeC mit dem Kontrollpolynom h(x) = x4 + x2 + x + 1 definiert. Die zugehorigeGeneratormatrix ist

G =

1 0 1 1 0 0 00 1 0 1 1 0 00 0 1 0 1 1 00 0 0 1 0 1 1

,die Kontrollmatrix entsprechend

H =

1 1 1 0 1 0 00 1 1 1 0 1 00 0 1 1 1 0 1

.Da die Spalten von H alle 7 von 0 verschiedenen Vektoren des K3 sind, handeltes sich bei C um einen Hamming-Code.

Fur die Permutation π = (12), also die Vertauschung der ersten beiden Koordi-naten, erhalt man den Linearode C ′ = π(C) mit der Generatormatrix

G′ =

0 1 1 1 0 0 01 0 0 1 1 0 00 0 1 0 1 1 00 0 0 1 0 1 1

,der aber wegen z(0111000) = (1110000) 6∈ C ′ nicht zyklisch ist. Naturlich ist aberauch C ′ ein Hamming-Code.

Aufgabe 5.16 Ermitteln Sie alle binaren zyklischen Linearcodes der Lange 5.

Aufgabe 5.17 Ermitteln Sie alle zyklischen Linearcodes der Lange 6 mit Di-mension k = 2 uber dem Korper Z/(13), indem Sie ihre Generatorpolynomeangeben.


5 ZYKLISCHE CODES

Aufgabe 5.18 Zeigen Sie, daß es neben dem ternaren Wiederholungscode derLange 4 noch einen weiteren ternaren zyklischen Linearcode C der Lange 4 mit|C| = 3 gibt.

Aufgabe 5.19 Bestimmen die Anzahl der selbstdualen zyklischen Binarcodesder Lange n = 6, 7 und 8.

Aufgabe 5.20 Ermitteln Sie alle ternaren zyklischen Linearcodes der Langenn = 3 und n = 4.

Aufgabe 5.21 Bestimmen Sie alle Werte von α ∈ Z/(5), so daß gα(x) = x2+x+α Generatorpolynom eines zyklischen [4,2]-Linearcodes uber dem Korper Z/(5)ist und ermitteln Sie gegebenenfalls eine zugehorige Kontrollmatrix.

Aufgabe 5.22 Bestimmen Sie alle zyklischen Linearcodes der Lange n = 4 mitDimension k = 2 uber dem Korper Z/(5), indem Sie zu jedem derartigen Co-de eine Generatormatrix angeben. Begrunden Sie, warum keiner dieser Codesselbstdual sein kann.

Aufgabe 5.23 Bestimmen Sie alle zyklischen Linearcodes der Lange n = 4 mitDimension k = 2 uber dem Korper Z/(13), indem Sie zu jedem derartigen Codeeine Generatormatrix angeben. Kennzeichnen Sie unter den gefundenen Codesdie zueinander dualen. Untersuchen Sie, mit welchem der gefundenen Codes dasCodewort (1, 3, 6, 4) erzeugt wurde.

Aufgabe 5.24 Fur jeden Korper K mit |K| = q und jede Lange n ∈ N ist nachBeispiel 5.2 der q-nare Wiederholungscode C der Lange n zyklisch. Geben Siedas Generatorpolynom g(x) ∈ K[x] von C an.


6 KRYPTOSYSTEME

6 Kryptosysteme

Definition 6.1 Eine Kryptosystem (P(A), C(B),K, E ,D) besteht aus

• einer Menge P von Klartexten (plaintext) uber einem Klartextalphabet A,

• einer Menge C von Geheimtexten (ciphertext) uber einem Geheimtextalpha-bet B,

• einer Menge K von Schlusseln (key), dem Schlusselraum,

• der Verschlusselung oder Chiffrierung E , d. h. einer Familie von Abbildun-gen EK : P → C, K ∈ K,

• der Entschlusselung oder Dechiffrierung D, d. h. einer Familie von Abbil-dungen DK : C → P , K ∈ K,

so daß fur alle K ∈ K gilt

DK ◦ EK = ιP .(51)

Die Zuordnungen von EK und DK zu K ∈ K stellen den Chiffrier- und denDechiffrieralgorithmus dar.

Bemerkung 6.2 a) Einige klassische Kryptosysteme gestatteten es, einem Klar-text auch mehrere Geheimtexte zuzuordnen. Beispielsweise kann man fur haufigvorkommende Buchstaben im Klartext mehrere verschiedene Verschlusselungen,sogenannte Homophone durch Buchstaben im Geheimtext vorsehen, unter denenzufallig gewahlt werden darf. Hierdurch kann man die Haufigkeiten der Buch-staben im Geheimtext gegenuber den Haufigkeiten der Buchstaben im Klartextverandern. Es handelt sich dann bei den EK nur um linkseindeutige Relationen.In jedem Fall gilt aber |P(A)| ≤ |C(B)|.

b) In der Kryptographie wird generell vorausgesetzt, daß die Chiffrier- und De-chiffrieralgorithmen allgemein bekannt sind. Die Geheimhaltung basiert einzigauf der Unkenntnis der verwendeten Schlussel. Diese Sichtweise wurde durch denniederlandischen Kryptanalytiker Auguste Kerckhoffs (1835 - 1903) im Jahr 1883erstmals formuliert.

c) Klassische Kryptosysteme sind symmetrisch, bei ihnen ist es leicht, aus EKdie Umkehrabbildung DK zu berechnen. Bei asymmetrischen Systemen ist die


6 KRYPTOSYSTEME

Ermittlung von DK aus EK ohne geheime Zusatzinformation extrem schwierig.Man nennt derartige Funktionen EK Einwegfunktionen und die geheimen Zu-satzinformationen Fallturen. Wird ein solches Verfahren benutzt, so kann derEmpfanger einer Nachricht dem Sender einen Schlussel K offentlich mitteilen,mit dem dieser eine Nachricht verschlusseln soll. Wenn nur der Empfanger diegeheime Zusatzinformation besitzt, mit der er DK berechnen kann, ist einem An-greifer die Entschlusselung trotzdem nicht moglich. Derartige Verfahren werdendaher auch Kryptosysteme mit offentlichem Schlussel genannt.

Beispiel 6.3 a) Translations-Kryptosysteme Es sei q eine naturliche Zahlund A = B = K = Zq. Fur jeden Schlussel K = b ∈ K sei EK(x) ≡ x + b mod qund DK(x) ≡ x− b mod q fur alle x ∈ Zq.

b) Affine Kryptosysteme Es sei q eine naturliche Zahl und A = B = Zq.Weiterhin sei K = {(a, b) ∈ Z2

q | ggT(a, q) = 1} und fur jeden Schlussel K =(a, b) ∈ K sei EK(x) ≡ ax + b mod q und DK(x) ≡ a−1(x − b) mod q fur allex ∈ Zq. Fur a = 1 erhalt man die Translations-Kryptosysteme als Spezialfall.

c) Substitutions-Kryptosysteme Es sei q eine naturliche Zahl und A = B =Zq. Weiterhin sei K = Sq die symmetrische Gruppe der Ordnung q und fur jedenSchlussel K = π ∈ K sei EK(x) = π(x) und DK(x) = π−1(x) fur alle x ∈ Zq.Jede (bijektive) affine Transformation in b) und damit erst recht jede Translationin a) liefert naturlich eine Permutaion von Zq. Daher ist jedes Affine Kryptosy-stem ein Substitutions-Kryptosystem. Weil fur alle Buchstaben der Klartexte ausP dieselbe Verschlusselungsfunktion verwendet wird, nennt man Substitutions-Kryptosysteme auch monoalphabetische Kryptosysteme.

Definition 6.4 Ein Schlussel K ∈ K eines Kryptosystems heißt involutorisch,wenn EK = DK gilt.

Beispiel 6.5 a) In einem Translations-Kryptosystem existiert genau dann eininvolutorischer Schlussel, wenn q gerade ist, namlich K = q/2.

b) In einem affinen Kryptosystem sind stets K = (1, 0) und K = (−1, b) furalle b ∈ Zq involutorisch. Es kann weitere involutorische Schlussel geben (vgl.Aufgabe 6.21).

c) In einem Substitutions-Kryptosystem sind offensichtlich genau die SchlusselK = π involutorisch, fur die π = π−1 gilt.

Beispiel 6.6 a) Vigenere-Kryptosysteme (Blaise de Vigenere, 1525 - 1596)Es seien m und q naturliche Zahlen und A = B = (Zq)m = K.


6 KRYPTOSYSTEME

Fur K = (k1, . . . , km) ∈ K sei EK(x1, . . . , xm) ≡ (x1 + k1, . . . , xm + km) mod qund DK(x1, . . . , xm) ≡ (x1−k1, . . . , xm−km) mod q fur alle (x1, . . . , xm) ∈ (Zq)m.Fur m = 1 ergibt sich ein Translations-Kryptosystem. Fur m > 1 spricht manvon einem polyalphabetischen Kryptosystem, da fur jeden Buchstaben, je nachseiner Position im Klartext, mehrere Verschlusselungen moglich sind.

b) Permutations-Kryptosysteme, Transpositions-Kryptosysteme (Gio-vanni Battista Della Porta, 1535 - 1615) Es seien m und q naturliche Zahlen undA = B = (Zq)m. Weiterhin sei K = Sm die symmetrische Gruppe der Ordnung mund fur jeden Schlussel K = π ∈ K sei EK(x1, . . . , xm) = (xπ(1), . . . , xπ(m)) undDK(x1, . . . , xm) = (xπ−1(1), . . . , xπ−1(m)). Die Buchstaben des Klartextes werdenalso nur vertauscht, nicht verandert.

c) Hill-Kryptosysteme (Lester S. Hill (1891 - 1961), 1929) Es seien m und qnaturliche Zahlen und A = B = (Zq)m. Weiterhin sei K = {K ∈ Mm,m(Zq) | Kinvertierbar }. Fur K ∈ K sei EK(x) = xK und DK(x) = xK−1 fur alle x ∈(Zq)m. Fur m = 1 ergeben sich spezielle affine Kryptosysteme mit b = 0. FurPermutationsmatrizen Kπ ergeben sich die Permutations-Kryptosysteme.

Beispiel 6.7 a) RSA-Kryptosysteme (vgl. Abschnitt 8) (Ronald Linn Rivest(1947 - ), Adi Shamir (1952 - ), Leonard Adleman (1945 - )) Es seien p, q Prim-zahlen und n = p · q sowie A = B = Zn. Weiterhin sei K = {(n, p, q, e, d) |ed ≡ 1 mod ϕ(n)}. Fur K = (n, p, q, e, d) sei EK(x) ≡ xe mod n und DK(x) ≡xd mod n. Der Teil (n, e) von K heißt offentlicher Schlussel, der Teil (p, q, d)geheimer Schlussel.

b) Rabin-Kryptosysteme (Michael Oser Rabin (1931 - )) Es seien p, q Prim-zahlen mit p, q ≡ 3 mod 4 und n = p · q sowie A = B = Zn. Weiterhin seiK = {(n, p, q, r) | 0 ≤ r ≤ n−1}. Fur K = (n, p, q, r) sei EK(x) ≡ x(x+r) mod n

und DK(x) ≡√

r2

4+ x− r

2mod n. Der Teil (n, r) von K heißt offentlich, der Teil

(p, q) geheim.

c) ElGamal-Kryptosysteme (Taher ElGamal (1953 - )) Es sei p eine “geeigne-te” Primzahl, α ∈ Z∗p primitives Element (vgl. Satz 11.2), A = Z∗p und B = Z∗p×Z∗p.Weiterhin sei K = {(p, α, a, β) | β = αa mod p}. Fur K = (p, α, a, β) werde einExponent k ∈ {0, . . . , p−1} zufallig gewahlt und EK(x, k) ≡ (αk, xβk) mod p undDK(x1, x2) ≡ x2(x

a1)−1 mod p berechnet. Der Teil (p, α, β) von K heißt offentlich,

der Teil a geheim.

Bemerkung 6.8 Man unterscheidet verschiedene Angriffe auf Kryptosysteme:

i) Geheimtext-Angriffe liegen vor, wenn dem Angreifer nur Geheimtexte bekanntsind, er daraus Klartexte und Schlussel ermitteln mochte: Gegeben sind also


6 KRYPTOSYSTEME

Ci = EK(Pi) fur i = 1, . . . , n, gesucht K,Pi bzw. ein Algorithmus, um Pn+1 ausCn+1 = EK(Pn+1) zu berechnen.

ii) Klartext-Geheimtext-Angriffe liegen vor, wenn dem Angreifer zusammengehori-ge Paare aus Klartext und Geheimtext vorliegen und er daraus den Schlusselermitteln mochte: Gegeben sind also Pi, Ci = EK(Pi) fur i = 1, . . . , n, gesuchtK bzw. ein Algorithmus, um Pn+1 aus Cn+1 = EK(Pn+1) zu berechnen. Furdie Sicherheit gegen derartige Angriffe ist es erforderlich, daß die ZuordnungK 7→ (P,EK(P )) eine Einweg-Funktion ohne Falltur ist.

iii) Angriffe mit gewahltem Klartext liegen vor, wenn der Angreifer die Geheim-texte zu von ihm selbst gewahlten Klartexten bestimmen kann: Gegeben sindalso Pi, Ci = EK(Pi) fur i = 1, . . . , n mit frei gewahlten Klartexten Pi, gesuchtK bzw. ein Algorithmus, um Pn+1 aus Cn+1 = EK(Pn+1) zu berechnen. Diesist insbesondere bei Public-Key-Verfahren stets der Fall, die also gegen derartigeAngriffe sicher sein mussen.

Bei einer adaptiven Variante dieses Angriffs werden die Pi nacheinander in Ab-hangigkeit von den zuvor erzielten Ergebnissen gewahlt.

iv) Angriffe mit gewahltem Geheimtext liegen vor, wenn der Angreifer durchKenntnis der Dechiffrierung Geheimtexte wahlen kann und daraus die zugehori-gen Klartexte ermitteln kann: Gegeben sind also Ci, Pi = DK(Pi) fur i = 1, . . . , n,gesucht K bzw. ein Algorithmus, um Pn+1 aus Cn+1 = EK(Pn+1] zu berechnenAuch diese Variante muß bei Public-Key-Systemen betrachtet werden.

Eine Kombination aus iii) und iv) wir auch ein Angriff mit gewahlten Textengenannt.

v) Angriffe durch Gewalt liegen vor, wenn der “Kryptanalytiker” den Schlusseldurch Bedrohung, Erpressung oder korperliche Gewalt an sich bringt. Eine Vari-ante hiervon ist die Bestechung als Angriff mit gekauftem Schlussel. Diese Metho-den sind sehr wirkungsvoll und oft der beste Weg, ein Kryptosystem zu brechen.Im Rahmen dieser Vorlesung werden sie aber aus ethischen Grunden nicht weiterbehandelt!

vi) Brute-Force-Angriffe bestehen darin, daß man fur einen gegebenen Geheim-text C samtliche Schlussel K des Schlusselraumes durchprobiert und nachschaut,ob P = DK(C) ein sinnvoller Klartext ist. Auch diese Methode wird in dieserVorlesung als “unsportlich” angesehen!

Definition 6.9 Bei Blockchiffren werden die Klartexte aus P in Blocke a1 . . . akgleicher Lange k uber dem Alphabet A eingeteilt und fur jeden Schlussel K ∈ Kist dann EK : Ak → Bn eine Abbildung, die als Geheimtext eines solchen Blocks


6 KRYPTOSYSTEME

einen Block der Lange n uber dem Alphabet B erzeugt. Dabei wird fur jedenBlock derselbe Schlussel verwendet. Meist ist dabei A = B und n = k. Im Falln > k spricht man von einer gespreizten Chiffre. Bei Stromchiffren wird fur jedenBlock dagegen ein anderer Schlussel benutzt.

Wichtige Kryptosysteme, die auf der Verwendung von Blockchiffren beruhen, sindneben denen aus den Beispielen 6.3, 6.6 und 6.7 der Data Encryption Standard(DES) und der Advanced Encryption Standard (AES).

Definition 6.10 Eine Stromchiffre (P(A), C(B),K, L,F , E ,D) besteht aus

• einer Menge P von Klartexten uber einem Klartextalphabet A,

• einer Menge C von Geheimtexten uber einem Geheimtextalphabet B,

• einer endlichen Menge K von Schlusseln, dem Schlusselraum,

• einem Schlusselstromalphabet L,

• einem Schlusselstromgenerator F = (f1, f2, . . .) mit

fi : K × Ai−1 → L fur i ≥ 1,

• der Verschlusselung oder Chiffrierung E , d. h. einer Familie von Abbildun-gen Ez : P → C, z ∈ L,

• der Entschlusselung oder Dechiffrierung D, d. h. einer Familie von Abbil-dungen Dz : C → P , z ∈ L,

so daß fur alle z ∈ L giltDz ◦ Ez = ιP .

Die Zuordnungen von Ez und Dz zu z ∈ L stellen den Chiffrier- und den Dechif-frieralgorithmus dar.

Eine Stromchiffre heißt synchron, wenn die Funktionen fi nicht von den Klartex-ten abhangen, also Funktionen auf K sind.

Eine Stromchiffre heißt periodisch mit der Periode d, wenn zi+d = zi fur alle i ≥ 1gilt.


6 KRYPTOSYSTEME

Bemerkung 6.11 Blockchiffren konnen als spezielle (synchrone) Stromchiffrenmit zi = K fur alle i ≥ 1 aufgefaßt werden.

Ein Vigenere-Kryptosystem mit Schlusselwortlange m kann als synchrone, peri-odische Stromchiffre mit der Periode m aufgefaßt werden. Mit K = (k1, . . . , km)gilt dann zi = ki fur 1 ≤ i ≤ m und periodischer Wiederholung.

Beispiel 6.12 Selbstschlussel-Chiffre (nach Vigenere) Es sei q eine naturlicheZahl, A = B = K = L = Zq, z1 ∈ K und zi = xi−1 fur i ≥ 2. Weiterhin seienEz(x) = x+ z mod q und Dz(x) = x− z mod q fur alle z ∈ L, x ∈ Zq. Hierdurchwird eine nicht synchrone, nicht periodische Stromchiffre definiert.

Aufgabe 6.13 Zeigen Sie, daß die Verschlusselungsfunktionen eines Kryptosy-stems stets injektiv sind und geben Sie ein Kryptosystem mit nicht surjektiverVerschlusselungsfunktion an.

Aufgabe 6.14 Es sei (P(A), C(B),K, E ,D) ein Kryptosystem mit |P(A)| = m,|C(B)| = k und m < k. Wie viele verschiedene Verschlusselungsfunktionen EK :P → C kann dieses Kryptosystem hochstens besitzen?

Aufgabe 6.15 Es sei A = B = Zq und (P(A), C(A),K, E ,D) ein Kryptosystemmit EK : Ak → Ak fur jedes K ∈ K, also eine Blockchiffre. Wie viele verschiedeneVerschlusselungsfunktionen kann dieses Kryptosystem hochstens besitzen.

Aufgabe 6.16 Der folgende Geheimtext entstand durch eine Translationschiffreuber dem Alphabet der 26 lateinischen Großbuchstaben:

QMTBSSFIXJWFBXFIFS.

Welche Nachricht sollte im Klartext damit ubermittelt werden?

Aufgabe 6.17 Ein Teil der folgenden Aufgabenstellung wurden mittels einerTranslationschiffre verschlusselt. Stellen Sie den Klartext zu diesem Teil wiederher und losen Sie anschließend die eigentliche Aufgabe.

Der folgende Geheimtext wurde durch die Anwendung eines ZMKIRIV IOVC-TXS WCWXIQW QMXWGLP YIWWIPA SVXWEPD erzeugt. Stellen Sie denzugehorigen Klartext wieder her:


6 KRYPTOSYSTEME

OETSWRDN.

Aufgabe 6.18 Der folgende Geheimtext datiert auf das Jahr 49 v. Chr. undwurde hochstwahrscheinlich durch Anwendung einer Translationschiffre auf dieq = 26 Großbuchstaben des lateinischen Alphabets erzeugt. Stellen Sie den zu-gehorigen Klartext wieder her.

JUNJ RJLC JNBC

Aufgabe 6.19 Der folgende Geheimtext wurde in einer mittelalterlichen Klo-sterruine entdeckt und wahrscheinlich mit einer Translationschiffre uber den q =26 Großbuchstaben des lateinischen Alphabets erzeugt.

DHYJ HIXB TSXI PQXI JGHP EXTC IXPB

Wie lautet der Klartext?

Aufgabe 6.20 Bestimmen Sie die Anzahl der moglichen Schlussel K = (a, b)eines affinen Kryptosystems mit |A| = |B| = q.

Aufgabe 6.21 a) Geben Sie ein Kriterium dafur an, daß ein Schlussel K = (a, b)eines affinen Kryptosystems involutorisch ist. Ermitteln Sie damit alle involuto-rischen Schlussel fur die Falle q = 6, 8, 10, 12 und q = 15.

b) Gilt q = p1p2 mit verschiedenen ungeraden Primzahlen pi, so gibt es genauq + p1 + p2 + 1 involutorische Schlussel fur ein affines Kryptosystem. UberprufenSie hiermit das Ergebnis aus a) im Fall q = 15.

Aufgabe 6.22 Von dem folgenden Geheimtext ist bekannt, daß er durch An-wendung eines affinen Kryptosystems mit dem Schlussel (a, 18) ∈ Z/(26)2 aufdie q = 26 Großbuchstaben des lateinischen Alphabets generiert wurde. WelcheBotschaft wurde hier verschlusselt?

VHUB BWYP MVUR

Aufgabe 6.23 Das folgende Kryptogramm wurde mit einer Skytale verschlus-selt:


6 KRYPTOSYSTEME

ORAAHTSLTSRECHVOIERIOESEESPR.

Ermitteln Sie den Klartext. Was ist bei dieser Verschlusselung mit der Skytaleauffallig?

Aufgabe 6.24 Der folgende Geheimtext aus einer mittelalterlichen Handschriftwurde in einer Klosterruine gefunden und vermutlich mittels einer Skytale er-zeugt:

SASQSEICEROTLNIENAEIUTRP.

Ermitteln Sie den zugehorigen Klartext.

Aufgabe 6.25 In der Oxford University versucht sich Prof. Krypto Graph nunselbst an der Verschlusselung mittels Skytale. Ein von ihm entworfener Geheim-text lautet

TSYTOABHORDEREEFPNHREOCOETASDRET.

Stellen Sie den zugehorigen Klartext wieder her.

Aufgabe 6.26 Beim Beziehen seines neuen Buros an der University of Cam-bridge hat Prof. Krypto Graph in einer Schublade einige historische Skytale undzwei vermutlich dazugehorige Kryptogramme entdeckt. Helfen Sie ihm bei derenEntschlusselung.

i) XOWOATIAOSXPHABTRRSXPLOSOHIEEXEEBTUEQLRX

ii) OTEECUUIHOIRRIQOETOLFUPINROYAOTENSEO

Aufgabe 6.27 Nachdem Prof. Krypto Graph auch die beiden fremden Kryp-togramme entschlusset hat, entwirft er in wehmutiger Erinnerung an OxforderZeiten noch ein weiteres Kryptogramm mit einer Skytale:

OTWHANDESTSTSITIRERHYAEHEROMEM

Wie lautet der Klartext?


6 KRYPTOSYSTEME

Aufgabe 6.28 Ein Klartext P bestehe aus n · m Buchstaben. Um ihn zu ver-schlusseln kommt nacheinander jeweils eine Skytale der Blocklange n bzw. m zumEinsatz. Der entstehende Geheimtext sei C. Begrunden Sie, daß C = P gilt.

Aufgabe 6.29 Mittels einer Skytale wurde ein Teil der folgenden Aufgaben-stellung verschlusselt. Stellen Sie zunachst diesen Teil wieder her und losen Sieanschließend die eigentliche Aufgabe.

Der Geheimtext AHVNJHBA wurde durch Anwendung eines ROW LES STSYSO TER TNE GPU HEE VIY LEM REK RHA SMI TSC erzeugt. BestimmenSie den zugehorigen Klartext.

Aufgabe 6.30 Im Londoner Globe Theatre wurde der vermutlich mit Hilfe einerSkytale verschlusselte Geheimtext

NRADAEIUWSETESLNOAWHHTYERCTAEHSA

gefunden. Stellen Sie zunachst den zugehorigen Klartext wieder her.

Verschlusseln Sie diesen anschließend durch Anwendung des Vigenere-Verfahrensmit Blocklange m = 4 uber den q = 26 Großbuchstaben des lateinischen Alpha-bets so, daß der neue Geheimtext mit UISNS... beginnt.

Aufgabe 6.31 Im Londoner Globe Theatre wurde der vermutlich mit Hilfe einerSkytale verschlusselte Geheimtext

ENETTURFOFSAEEIYOEMHWLRNUITSSEOQTONEVIELTA

gefunden. Stellen Sie zunachst den zugehorigen Klartext wieder her.

Verschlusseln Sie den Klartext

NIEMANDTUTETWASOHNEMOTIVATION

durch Anwendung des Vigenere-Verfahrens mit Blocklange m = 4 uber den q =26 Großbuchstaben des lateinischen Alphabets so, daß der neue Geheimtext mitGMWFT... beginnt.


6 KRYPTOSYSTEME

Aufgabe 6.32 Um einen Klartext aus den q = 26 Großbuchstaben des lateini-schen Alphabets zu verschlusseln, wurde zunachst eine Permutationschiffre derLange m = 4 angewandt, ehe mit dem Einwegschlussel “REGENSCHAUER” derfolgende Geheimtext entstand. Wie lautete der Klartext?

JMKA QGTZ MLQV

Aufgabe 6.33 Uber dem normalen lateinischen Alphabet mit 26 Buchstabenwurde der Geheimtext

YMFZL JVJGY ZMHZL FWPNT GZTKU

mit einem Vigenere-Kryptosystem und dem Schlussel “SINGH” erzeugt. Wielautet der Klartext?

Aufgabe 6.34 Durch Spionage konnte ermittelt werden, daß der folgende Ge-heimtext durch Anwendung eines Vigenere-Kryptosystems auf die q = 26 Groß-buchstaben des lateinischen Alphabets generiert wurde. Der Parameter m istjedoch unbekannt. Allerdings ist sicher, daß der zugehorige Klartext mit “ACH-TU” beginnt. Stellen Sie ihn vollstandig wieder her.

GGMT BEMF TMIV


YCJDJMYZMP

mit einem Hill-Kryptosystem und der Schlusselmatrix(

10 53 14

)erzeugt. Wie

lautet der Klartext?


OTEKNAJHPM


6 KRYPTOSYSTEME


4 159 16

)erzeugt. Wie



XEWUSIGWPVJY


7 93 12

)erzeugt. Wie



SOKLSHKPNSOORCPLANFO


5 62 3

)erzeugt. Wie lau-

tet der Klartext? (Hinweise: Diese Aufgabe wurde aus einer fremden Aufgaben-sammlung entnommen. Vektoren konnen prinzipiell Zeilen- oder Spaltenvektorensein. An einer Stelle liegt ein Verschlusselungsfehler vor!)

Aufgabe 6.39 Um eine Nachricht uber den q = 26 Großbuchstaben des latei-nischen Alphabets zu verschlusseln, kam zunachst eine Skytale zum Einsatz. Dieanschließende Verwendung eines Hill-Kryptosystems mit Parameter m = 2 undSchlusselmatrix (

9 238 15

)lieferte schließlich den Geheimtext CMSVNSTVGUJA. Rekonstruieren Sie dieursprungliche Botschaft.

Aufgabe 6.40 Zur Verschusselung eines Klartextes wurde zunachst eine Trans-positionschiffre mit Blocklange 5 angewandt. Anschließend wurde ein Hill-Kryp-tosystem zur Verschluss elung der q = 26 Großbuchstaben des lateinischen Al-phabets mit der Schlusselmatrix (

19 177 6

)verwendet. Der daraus hervorgegangene Geheimtext lautet PDZVXLWOTS. Re-konstruieren Sie den Klartext.


6 KRYPTOSYSTEME

Aufgabe 6.41 Bestimmen Sie die Anzahl der moglichen Schlussel eines Hill-Kryptosystems mit A = B = (Zq)m fur den Fall, daß q eine Primzahl ist.

Aufgabe 6.42 Geben Sie ein involutorisches Hill-Kryptosystem fur A = B =Z15, m = 4 und einer Schlusselmatrix K mit det(K) 6= ±1 an.

Aufgabe 6.43 Bestimmen Sie fur A = B = Z8 und m = 2 in einem Hill-Krypto-

system alle involutorischen Schlusselmatrizen der Form(x 0y y

).


AQPPISZU


13 1212 13

)erzeugt. Wie

lautet der Klartext? Warum handelt es sich um einen involutorischen Schlussel?

Aufgabe 6.45 Im Hill-Kryptosystem fur A = B = Z26 und m = 3 sei durch denSchlussel

K =

25 21 1325 8 1611 8 21

der Geheimtext c = (11, 16, 5) entstanden. Wie lautet der zugehorige Klartext?

Aufgabe 6.46 Im Hill-Kryptosystem fur A = B = Z26 und m = 2 sei durch denSchlussel

K =(

11 53 2

)der Geheimtext WFUSZV entstanden. Wie lautet der zugehorige Klartext?

Aufgabe 6.47 Zur Verschlusselung einer Nachricht uber den q = 26 Großbuch-staben des lateinischen Alphabets wurde zunachst ein Hill-Kryptosystem mitParameter m = 2 und der Schlusselmatrix

K =(

5 917 24

)


6 KRYPTOSYSTEME

verwandt. Die anschließende Nutzung der durch(1 2 3 4 53 2 5 1 4

)∈ S5

vermittelten Transpositionschiffre lieferte den Geheimtext IDHDKLPSBZ. Wielautet der ursprungliche Klartext?

Aufgabe 6.48 Im Hill-Kryptosystem fur A = B = Z6 und m = 2 sei durch

K =(a b0 c

)ein involutorischer Schlussel gegeben. Welche Parameterkombinationen a, b, c ∈Z/(6) kommen hierfur in Frage?

Aufgabe 6.49 Zur Verschlusselung einer Nachricht uber den q = 26 Großbuch-staben des lateinischen Alphabets wurde zunachst ein affines Kryprosystem mitden Parametern (21, b) ∈ Z/(26))2 verwandt. Die anschließende Hill-Verschlusse-lung mit der Matrix

K =

9 1 1521 0 919 3 21

lieferte den Geheimtext 19, 4, 11, 5, 14, 13. Wie lautet der zugehorige Klartext undder Parameter b? Es ist bekannt, daß der Klartext einen Begriff der nordischenMythologie darstellt.

Aufgabe 6.50 Zur Verschlusselung einer Nachricht uber den q = 26 Groß-buchstaben des lateinischen Alphabets kam ein Hill-Kryptosystem mit Parame-ter m = 2 zum Einsatz. Dies ergab den Geheimtext TXKQSA. Die benutzteSchlusselmatrix ist nur teilweise bekannt:

K =( ∗ 1

2 ∗

).

Es wird jedoch vermutet, daß es sich um einen involutorischen Schlussel handelt.

Aufgabe 6.51 Bestimmen Sie fur ein Hill-Kryptosystem uber Z/(8) mit m = 2

alle involutorischen Schlusselmatrizen der Form K =(x 0y y

).


6 KRYPTOSYSTEME

Aufgabe 6.52 Zur Verschlusselung einer Nachricht uber den q = 26 Großbuch-staben des lateinischen Alphabets kam ein Hill-Kryptosystem mit der Schlussel-matrix 11 2 1

3 3 211 25 1

zum Einsatz. Dies ergab den Geheimtext JAD. Wie lautet der zugehorige Klar-text.

Aufgabe 6.53 Es sei ein Permutationssystem der Blocklangem uber dem Binar-alphabet A = B = {0, 1} mit einem festen Schlussel π ∈ Sm gegeben. GebenSie m − 1 Klartext-Geheimtextpaare (x, π(x)) an, mit denen sich π eindeutigbestimmen laßt.

Aufgabe 6.54 Es sei ein affines Kryptosystem der Blocklange m uber dem Al-phabet A = B = Zq mit einem festen Schlussel K = (a, b) ∈ K gegeben. GebenSie m + 1 Klartext-Geheimtextpaare (x,EK(x)) an, mit denen sich K eindeutigbestimmen laßt.

Aufgabe 6.55 Berechnen Sie in dem affinen Kryptosystem uber dem AlphabetA = B = Z26 mit dem Schlussel a = 9, b = 4 den Geheimtext zum Klartext“KLAUSUR”.

Aufgabe 6.56 Der Geheimtext OERSYCJ wurde unter Verwendung eines affi-nen Kryptosystems mit den Parametern (19, b) ∈ (Z/(26))2 generiert. Der Trans-lationsparameter b ist dabei unbekannt. Stellen Sie den zugehorigen Klartextwieder her und geben sie den Wert von b an.

Aufgabe 6.57 Bei der Verschlusselung des Klartextes DIEKLAUSURISTSO-LEICHT mit dem Einwegschlussel-Verfahren wurde der Schlussel VERWENDE-TERSCHLUESSEL verwendet, um durch Addition modulo 26 den GeheimtextYMVGPNXWNVZK... zu erzeugen. Welcher Einwegschlussel hatte bei demsel-ben Verfahren verwendet werden mussen, um den Klartext DIEKLAUSURIST-SOSCHWER in denselben Geheimtext zu verschlusseln.

Aufgabe 6.58 Der Geheimtext

NANB ANAN BNAN BNBB NANB EBBE


6 KRYPTOSYSTEME

entstand durch die Anwendung einer Substitutionschiffre auf einen Klartext uberdem vierelementigen Alphabet {A,B,E,N}. Der zugehorige Schlussel π warfixpunktfrei und weder eine Involution noch eine Translation. Bestimmen siezunachst alle Schlussel des zugehorigen Kryptosystems, welche diese drei Be-dingungen erfullen, und stellen Sie anschließend den Klartext wieder her, indemSie unter den verbliebenen Schlusseln π durch systematisches Probieren identifi-zieren.


7 PERFEKT SICHERE KRYPTOSYSTEME

7 Perfekt sichere Kryptosysteme

Es sei (P(A), C(B),K, E ,D) ein Kryptosystem mit endlichem Klartextraum Pund endlichem Schlusselraum K. Jeder Klartext P ∈ P werde mit einer Wahr-scheinlichkeit pP gesendet und zu seiner Verschlusselung unabhangig von P einSchlussel K ∈ K mit einer Wahrscheinlichkeit qK ausgewahlt. Die Wahrschein-lichkeit fur das Paar (P,K) ist also pP qK . Die Chiffrierung EK ordne P denGeheimtext C zu. Die Wahrscheinlichkeit fur das Auftreten von C ist dann

r(C) =∑P∈P

∑K∈K,C=EK(P )

pP qK .

Die bedingte Wahrscheinlichkeit fur den Klartext P bei gegebenem GeheimtextC ist dann

r(P |C) =1

r(C)

∑K∈K,C=EK(P )

pP qK .

Damit wird die Entropie von P unter C definiert durch

H(P|C) = −∑P∈P

r(P |C) log r(P |C),

und die mittlere Entropie von P unter C ist dann

H(P|C) =∑C∈C

r(C)H(P|C).

Schließlich istI(P , C) = H(P)−H(P|C)

die Information von C uber P . Nach einer Arbeit von Claude Elwood Shannon(1916 - 2001) aus dem Jahr 1949 definiert man

Definition 7.1 Ein Kryptosystem (P(A), C(B),K, E ,D) heißt dann perfekt si-cher, wenn I(P , C) = 0 ist.

Satz 7.2 Ein Kryptosystem (P(A), C(B),K, E ,D) ist genau dann perfekt sicher,wenn pP = r(P |C) fur alle Klartexte P und alle Geheimtexte C gilt, wenn alsodie Wahrscheinlichkeitsverteilungen auf P und C unabhangig sind.

Folgerung 7.3 In einem perfekt sicheren Kryptosystem gibt es mindestens soviele Schlussel wie Klartexte.



Folgerung 7.4 Erfullt ein Kryptosystem die Bedingungen (i) |P| = |K|, (ii)qK = |K|−1 fur alle K ∈ K und (iii) zu jedem Klartext P und jedem GeheimtextC gibt es genau einen Schlussel K mit EK(P ) = C, so ist es perfekt sicher.

Bemerkung 7.5 Die Verwendung von Einwegschlusseln liefert also perfekt si-chere Kryptosysteme. Es sind dies auch die einzigen Verfahren, fur die bis heutedie perfekte Sicherheit bewiesen ist.

Das Problem des sicheren Austausches von Einwegschlusseln kann mittels dertechnisch noch zu entwickelnden Quanten-Kryptographie zumindest theoretischsehr elegant gelost werden.

Schlusselvereinbarung in der Quanten-Kryptographie

In einem Quanten-Kanal werden einzelne Photonen (Lichtquanten) ubertragen,die jeweils eine von vier mogliche Polarisationsrichtungen aufweisen: 0 Grad (l),45 Grad (↗), 90 Grad (↔) oder 135 Grad (↘). Diese Photonen konnen alsZeichen uber dem Alphabet A = {0, 1, 2, 3} aufgefaßt werden.

Zur Vereinbarung eines Schussels fur eine spatere geheime Nachrichtenubertra-gung durch einen gewohnlichen Kanal sendet der Sender zunachst eine zufalligeFolge solcher Photonen uber den Quanten-Kanal an den Empfanger, z. B.

(a) 0, 2, 1, 0, 3, 2, 2, 1, 0, 2, 3, 1, 1, . . .

Der Empfanger mißt jedes empfangene Photon durch einen jeweils zufallig ge-wahlten Polarisationsfilter, der ebenfalls durch eine der vier Richtungen bestimmtist, also auch als zufallige Folge uber A dargestellt werden kann, z. B.

(b) 0, 1, 3, 2, 1, 0, 2, 2, 3, 0, 3, 2, 1, . . .

Wird dabei ein gerades (ungerades) Photon durch einen geraden (ungeraden)Filter gemessen, so beobachtet der Empfanger bei Gleichheit mit Sicherheit einSignal (notiert als 1), bei Ungleichheit mit Sicherheit kein Signal (notiert als 0).Stimmt dagegen die Paritat von gesendetem Photon und Filter nicht uberein, somißt der Empfanger nach den Gesetzen der Quantenmechanik jeweils mit 50 %Wahrscheinlichkeit ein Signal oder kein Signal. Er ermittel also eine Meßfolge (c)aus Nullen und Einsen, wobei er allerdings nicht weiß, welche Symbole “sicher”sind und welche nur die Wahrscheinlichkeit 0.5 besitzen.

Der Empfanger schickt nun uber einen gewohnlichen Kanal an den Sender dieFolge (b) seiner Filtereinstellungen. Hieraus und aus seinen eigenen Filtereinstel-lungen kann der Sender die Indizes der “sicheren” Messungen und die jeweiligen



Ergebnisse des Empfangers berechnen. Er sendet nun dem Empfanger die Folge(d) dieser Indizes ebenfalls uber den gewohnlichen Kanal. Im obigen Beispiel istdies

(d) 1, 3, 4, 5, 6, 10, 11, 13, . . .

Die zugehorige Folge der sicher gemessenen Bits stellt jetzt den beiden Beteiligtenbekannten Schlussel dar. Die restlichen Messungen des Empfangers (ungefahr 50%) werden ignoriert.

Ein Angreifer, der das Verfahren kennt und die Folge (a) “abhoren” will, kann diesnur tun, indem er die einzelnen Photonen durch einen Polarisationsfilter schickt.Dabei kann er die Polarisationsrichtung ebenfalls nur zufallig raten. Wahlt erdabei eine andere Paritat als der Empfanger, so mißt er entweder ein korrektesErgebnis (wenn der Empfanger nicht die Paritat des Senders geraten hat), dasspater aber verworfen wird, oder er mißt ein spater benotigtes Ergebnis, wobeiseine Messung das benotigte Bit aber nur mit einer Wahrscheinlichkeit von 0.5richtig darstellt. Die Halfte der Messungen des Angreifers sind also unbrauchbar,er kennt daher nur die Halfte des vereinbarten Schlussels, selbst wenn er allePhotonen “abhort”.

Seine Situation ist aber noch ungunstiger. Da bei seiner Messung das Photon aus-geloscht wird, muß er ein “Ersatzphoton” in den Quanten-Kanal einspeisen, sonstverrat er sich sofort. Dies eingespeiste Photon muss er naturlich gemaß seiner ei-genen Messung polarisieren. In 25 % aller Falle wird dies aber die falsche Paritathaben, so daß jedes zweite Bit, daß der Empfanger spater in seinem Schlusselbenutzt, nicht mit dem Bit des Senders ubereinstimmt. Tauschen daher Senderund Empfanger uber den gewohnlichen Kanal einen kleinen Teil ihres Schlusselsaus (und benutzen diesen Teil gegebenenfalls nicht), so konnen sie mit hoherWahrscheinlichkeit feststellen, ob der Quanten-Kanal bei der Schlusselvereinba-rung abgehort wurde. Sie werden den Schlussel daher insgesamt verwerfen undeinen erneuten Versuch starten.


8 DATA ENCRYPTION STANDARD

8 Data Encryption Standard

Definition 8.1 Es seien A = B = {0, 1}, n ∈ N gerade und t = n2. Je-

des P = (b1, . . . , bn) ∈ An werde in die beiden Halften L = (b1, . . . , bt) undR = (bt+1, . . . , bn) zerlegt, es gilt also P = (L,R). Weiterhin sei r ∈ N eineAnzahl von Runden und K1, . . . , Kr fur jede Runde ein Schlussel, der jeweilseine Abbildung fKi

: At → At , die innere Blockchiffre, bestimmt. Weiterhinsei π(L,R) = (R,L) die Vertauschung von linker und rechter Blockhalfte undϕi(L,R) = (L,R ⊕ fKi

(L)) fur i = 1, . . . , r. (Dabei sei ⊕ die Addition modulo2.) Die Chiffrierung mittels der Feistel-Chiffre (Horst Feistel (1915 - 1990), 1973)geschieht nun ausgehend vom Klartextblock P = P0 = (L0, R0) iterativ gemaß

Pi = ϕi ◦ π(Pi−1), i = 1, . . . , r(52)

und abschließender Berechnung des Geheimtextes C gemaß

C = (Rr, Lr).(53)

Insgesamt gilt also

C = π ◦ ϕr ◦ π . . . ◦ ϕ1 ◦ π(P ).(54)

Bemerkung 8.2 Da sowohl π als auch ϕi involutorische Abbildungen sind, d. h.es gilt π−1 = π und ϕ−1i = ϕi, folgt (π ◦ ϕr ◦ π . . . ◦ ϕ1 ◦ π)−1 = π ◦ ϕ1 ◦π . . . ϕr ◦ π, d. h. die Dechiffrierung erfolgt nach demselben Verfahren, wobei nurdie Schlusselreihenfolge umzukehren ist.

Beispiel 8.3 Beim DES wird eine Feistel-Chiffre fur n = 64 und r = 16 an-gewandt, wobei die Rundenschlussel Ki nach einem festgelegten, offentlich be-kannten Verfahren aus einem Hauptschlussel K = (k1, . . . , kn) ∈ An berechnetwerden. In diesem Hauptschlussel sind allerdings die Bits j = 8, 16, . . . , 64 ir-relevant, so daß es genau 256 verschiedene Schlussel in K gibt. Auch die Kon-struktion der Chiffrierfunktionen fKi

fur die einzelnen Runden der Feistel-Chiffrefolgt einem festen, offentlich bekannten Verfahren. Zusatzlich existiert noch eineinitiale Permutation IP ∈ S64, die auf den zu verschlusselnden KlartextblockP ∈ A64 angewandt wird und IP (P ) = (L0, R0) liefert. Nach Anwendung derFeistel-Chiffre wird schließlich C = IP−1(R16, L16) gebildet. Diese PermutationIP ist kryptographisch wirkungslos, da sie ebenfalls offentlich bekannt ist. Die


8 DATA ENCRYPTION STANDARD

Sicherheit des DES beruht einzig und allein auf der Tatsache, daß die Berech-nungen der Chiffrierfunktionen aus dem Hauptschlussel (nach heutigem Wissen)Einwegfunktionen ohne Falltur sind. Trotz vielfaltiger Bemuhungen zahlreicherKryptoanalytiker hat der DES allen Angriffen standgehalten, mit einer einzigenAusnahme. Mit moderner Rechnerleistung ist es heute moglich, den gesamtenSchlusselraum innerhalb eines Tages auszuschopfen. Dies beruht aber nicht aufeiner Schwachstelle in der Konstruktion des DES. Man hat hier Abhilfe geschaf-fen, indem man durch das sogenannte Triple-DES-Verfahren Schlussellangen von128 Bit verwendet. Da beide Verfahren auf Feistel-Chiffren beruhen, kann mansie ebenso wie diese sowohl zur Ver- als auch zur Entschlusselung benutzen, wennman entsprechend die Schlusselreihenfolge umkehrt.

Mittlerweile existiert bereits ein Nachfolger zum DES, der AES (Advanced En-cryption Standard), der minimal mit Blocklangen von 128 Bit und gleichlan-gen Schlussellangen arbeitet. Bei dem darin verwendeten sogenannten Rijndael-Algorithmus (Vincent Rijmen (1970 - ), Joan Daemen (1965 - )) werden 10 Run-den berechnet, allerdings handelt es sich nicht mehr um Feistel-Chiffren.

Bemerkung 8.4 Beim DES gibt es 4 schwache Schlussel K, fur die alle jewei-ligen Rundenschlussel Ki ubereinstimmen. Außerdem gibt es 6 Paare (K,K ′)halbschwacher Schlussel, fur die

DESK = DES−1K′

gilt. Bei jedem dieser 12 Schlussel entstehen nur jeweils zwei verschiedene Run-denschlussel. Hinzu kommen noch 48 moglicherweise schwache Schlussel, fur dienur je 4 verschiedene Rundenschlussel existieren. Diese 64 Schlussel sind alsotunlichst zu vermeiden.

Aufgabe 8.5 Beweisen Sie die in Bemerkung 8.2 enthaltenen Behauptungen.

Aufgabe 8.6 Bestimmen Sie einen Wert der Hexadezimalzahl X so, daß derDES-Schlussel

FE E0 1X 01 XE F1 0E 01

genau vier verschiedene Rundenschlussel erzeugt. Weisen Sie dies nach.

Aufgabe 8.7 Bestimmen Sie samtliche schwachen und halbschwachen Schlusseldes DES.


9 DER RSA-ALGORITHMUS

9 Der RSA-Algorithmus

Dieser Algorithmus zum Einsatz in Kryptosystemen mit offentlichen Schlusseln,wird nach seinen Entwicklern Rivest, Shamir und Adleman (1980) benannt. Zu-nachst sei noch einmal das Grundprinzip derartiger Kryptosysteme beschrieben:

(1) Jeder Teilnehmer A konstruiert eine Verschlusselungsfunktion EA als Ein-wegfunktion mit Falltur. Die in die Konstruktion einfließende, nur ihm bekannteZusatzinformation liefert die Entschlusselungsfunktion DA = E−1A .

(2) Er gibt EA als seinen offentlichen Schlussel bekannt, halt aber DA geheim.

(3) Will ein Teilnehmer B eine Nachricht P an A senden, so verschlusselt er siegemaß C = EA(P ) und sendet sie an A.

(4) Wenn A den Geheimtext C empfangt, wendet er DA an und erhalt DA(C) =DA(EA(P )) = P .

Die Idee dieser Systeme geht auf Diffie und Hellman (1975) zuruck. Mittlerweileist bekannt, daß Mitarbeiter des britischen Geheimdienstes etwa gleichzeitig dieIdee entwickelt haben.

Zur Vorbereitung des RSA-Algorithmus werden einige zahlentheoretische Aussa-gen benotigt.

Satz 9.1 Seien n > 0 eine naturliche Zahl und e ∈ Z. Genau dann existiert eind ∈ Z mit ed ≡ 1 mod n, wenn ggT (e, n) = 1 gilt.

Satz 9.2 Seien n > 0 eine naturliche Zahl und a ∈ Z teilerfremd zu n. Dann giltaϕ(n) ≡ 1 mod n. Speziell gilt ap−1 ≡ 1 mod p, wenn n = p eine Primzahl und anicht durch p teilbar ist.

Satz 9.3 Genau dann ist die naturliche Zahl n > 1 Produkt paarweise verschie-dener Primzahlen, wenn fur alle ganzen Zahlen a gilt

aϕ(n)+1 ≡ a mod n.

Das RSA-Verfahren (vgl. Beispiel 6.7 a))

(1) A wahlt zufallig zwei große Primzahlen p und q. (Gangige Wahlen sindBinarzahlen mit Langen ≥ 256 oder sogar ≥ 512.)



(2) A berechnet nA = pq und ϕ(nA) = (p − 1)(q − 1). Man nennt nA den RSA-Modul von A.

(3) Weiterhin wahlt A eine zu ϕ(nA) teilerfremde Zahl eA, den Verschlusselungs-exponenten von A zwischen 1 und ϕ(nA)− 1.

(4) A bestimmt den Entschlusselungs-Exponenten dA mit eAdA ≡ 1 mod ϕ(nA)und 1 ≤ dA < ϕ(nA).

(5) A gibt nA und eA offentlich bekannt, halt die anderen Zahlen aber geheim.

(6) Will nun B eine Nachricht an A senden, so stellt er zunachst den Klartext Pals Folge naturlicher Zahlen n1, . . . , nr zwischen 0 und nA−1 dar. Dann bestimmter zu jeder dieser Zahlen ni den Geheimtext

ci ≡ neAi mod nA

und sendet die Folge c1, . . . , cr an A.

(7) A bildet zu den empfangenen Geheimtexten ci die Potenzen

cdAi ≡ ni mod nA,

die dann noch in den Klartexte zuruckverwandelt werden mussen.

Wegen Satz 9.2 gilt akϕ(nA)+1 ≡ a mod nA fur jede ganze Zahl k. Aus eAdA ≡1 mod ϕ(na) folgt aber eAdA = kϕ(nA) + 1 fur eine geeignete ganze Zahl k.

Hieraus folgt dann cdAi = neAdAi = nkϕ(nA)+1i ≡ ni mod nA.

Die Durchfuhrbarkeit des Verfahrens beruht darauf, daß man große Primzahlenrelativ schnell finden kann und ebenso schnell die Exponentiation von Restklassendurchfuhren kann. Dagegen beruht die Sicherheit darauf, daß die Faktorisierunggroßer Zahlen nA in Primfaktoren ein “schweres” Problem ist. Es ist allerdingsbisher nicht bewiesen, daß fur die Dechiffrierung tatsachlich die Faktorisierungdes RSA-Moduls notwendig ist.

Aufgabe 9.4 Es seien p = 3, q = 11 und eA = 17. Das zugehorige RSA-Kryptosystem wurde verwendet, um einen einzelnen Klartextblock m zu codieren.Der erzeugte Geheimtextblock lautet c = 20. Berechnen Sie m.





Aufgabe 9.7 Der RSA-Modul sei n = 14803. Versuchen Sie zunachst die Fak-torisierung n = p · q ohne Kenntnis von ϕ(n). Benutzen Sie dann im Vergleichdazu den Wert von ϕ(n) = 14560.

Aufgabe 9.8 Warum sind die RSA-Module n = 15444899 oder n = 15350723(ganz abgesehen von ihrer zu geringen Lange) schlecht gewahlt?

Aufgabe 9.9 Der offentliche Schlussel eines RSA-Kryptosystems sei (n, e) =(247, 7). Wie lauten die Geheimtexte zu den Klartexten m1 = 10 und m2 = 100?Welches ist der private Teil des Schlussels und welcher Klartext gehort zu demGeheimtext c = 2?

Aufgabe 9.10 Der offentliche Schlussel eines RSA-Kryptosystems sei (n, e) =(10, 3). Wie lautet der Geheimtext zum Klartext m = 3? Ermitteln Sie den pri-vaten Schlussel und uberprufen Sie das Ergebnis, indem sie den Klartext ausdem berechneten Geheimtext rekonstruieren. Was ist bemerkenswert an demSchlussel? Andern Sie den Verschlusselungsexponenten auf e = 2 und berech-nen Sie jetzt die Geheimtexte zu den Klartexten m1 = 4 und m2 = 6. Geben Sieeine Erklarung fur das Ergebnis an.

Aufgabe 9.11 Der offentliche Schlussel eines RSA-Kryptosystems sei (n, e) =(143, 11). Begrunden Sie, warum dies nicht sinnvoll ist. Berechnen Sie trotzdemden privaten Schlussel. Was fallt dabei auf?

Aufgabe 9.12 Warum ist der Entschlusselungsexponent e = 11 der kleinstmog-liche zu dem RSA-Modul n = 899?

Aufgabe 9.13 Man mochte das RSA-Verfahren auch fur Moduln n mit mehrals zwei Primfaktoren verwenden. Was spricht dafur, was dagegen?

Aufgabe 9.14 In einem Netzwerk soll die folgende Variante des RSA-Verfahrensverwendet werden. Jeder Benutzer wahlt zwar einen eigenen Modul nA, aberalle benutzen denselben Verschlusselungsexponenten e = 3. Zeigen Sie, daß dasSystem angegriffen werden kann, wenn dieselbe Nachricht m an drei oder mehrverschiedene Benutzer gesendet wird. Ist dieser Angriff auch erfolgreich, wenne > 3 gewahlt wird?



Aufgabe 9.15 In einem Preisratsel wurde folgendes Kryptogramm angegeben,daß mit dem RSA-Verfahren zum Modul n = 433761 und dem Verschlusselungs-exponenten e = 487 verschlusselt wurde:

71252 157929 176572 222043 74625 176572 385760 111315

336575 68733 300172 46454 184401 306430 310955 198321 30319

295209 338285 393427 336575 68733 319129 63296 166008

122301 166008 33546 122493 193863 216878 17470 219935

298108 161200 385760 213907 125760 122301 376173 109579

140957 301071 14647 159959

Ermitteln Sie den Klartext.


10 QUADRATWURZELN MODULO N

10 Quadratwurzeln modulo n

In den Rabin-Kryptosystemen ist es bei der Decodierung notwendig, Quadrat-wurzeln in den Restklassenringen Z/(n) zu berechnen, wobei n = p · q fur zweiPrimzahlen mit p, q ≡ 3 mod 4 gilt.

Dies wird durch die folgenden zahlentheoretischen Satze ermoglicht. Zunachst ein-mal laßt sich in dieser Situation generell das Losen einer quadratischen Gleichungin Z/(n) auf das Losen derselben Gleichung in Z/(p) und Z/(q) reduzieren:

Satz 10.1 Sind p, q ≥ 3 verschiedene Primzahlen und u, v ∈ Z Losungen derquadratischen Gleichungen u2 + bu ≡ c mod p bzw. v2 + bv ≡ c mod q, sowiey, z ∈ Z mit y ≡ 1 mod p, y ≡ 0 mod q, z ≡ 0 mod p und z ≡ 1 mod q, so istx = yu+ zv Losung von x2 + bx ≡ c mod pq.

Beweis: Derartige Zahlen y, z ∈ Z lassen sich schnell finden: Wegen p 6= q giltggT (p, q) = 1 und daher kann man mit dem Euklidischen Algorithmus Zahlend, e ∈ Z berechnen, die 1 = dp + eq erfullen. Fur y = eq und z = dp folgt dann1 = y + z und neben den behaupteten vier Kongruenzen noch 1 ≡ y + z mod pqund yz ≡ 0 mod pq.

Wegen y = 1+kp = `q mit ganzen Zahlen k, `, gilt y2 = `q(1+kp) = `q+ `kpq ≡`q ≡ y mod pq und analog z2 ≡ z mod pq.

Setzt man noch u2 + bu = c + mp und v2 + bv = c + m′q mit geeigneten Zahlenm,m′ ∈ Z, so ergibt sich in Z/(n):

x2 + bx− c ≡ y2u2 + 2yzuv + z2v2 + byu+ bzv − c≡ yu2 + ybu+ zv2 + zbv − c≡ y(u2 + bu) + z(v2 + bv)− c≡ y(mp+ c) + z(m′q + c)− c≡ eqmp+ yc+ dpm′q + zc− c≡ 0.

�

Ganz allgemein laßt sich aber das Losen quadratischer Gleichungen auf die Be-rechnung von Quadratwurzeln reduzieren:

Satz 10.2 Ist p ≥ 3 prim und x Losung der Gleichung x2 ≡ c + 14b2 in Z/(p),

dann ist y = −12b+ x Losung der quadratischen Gleichung y2 + by ≡ c mod p.



Beweis: Es ist y2 + by = 14b2 − bx+ x2 − 1

2b2 + bx ≡ c+ 1

4b2 − 1

4b2 = c. �

Uber die Existenz von Quadratwurzeln in Z/(p) gibt das Euler-Kriterium Aus-kunft:

Satz 10.3 Sei p ≥ 3 prim. Genau dann besitzt 1 ≤ a ≤ p−1 eine Quadratwurzelin Z/(p), wenn gilt

ap−12 ≡ 1 mod p.(55)

Hieraus ergibt sich auch noch, daß die Berechnung von Quadratwurzeln in Z/(p)fur Primzahlen der in Rabin-Kryptosystemen betrachteten Art “einfach” ist.

Folgerung 10.4 Ist p = 4k−1 prim und besitzt 1 ≤ a ≤ p−1 eine Quadratwurzelin Z/(p), dann ist x ≡ ak mod p eine Quadratwurzel von a.

Beweis: Wegen k = 14(p+ 1) folgt aus dem Euler-Kriterium

x2 = ap+12 = aa

p−12 ≡ a mod p.

�

Fur Primzahlen mit p ≡ 1 mod 4 ist kein solch einfacher Algorithmus zur Berech-nung von Quadratwurzeln bekannt. Hier wird im allgemeinen der Algorithmusvon Shank-Tonelli angewandt.

Eingabe: p ≥ 3 prim, 1 ≤ a ≤ p− 1 ein quadratischer Rest modulo p

Ausgabe: r ∈ Z mit r2 ≡ a mod p.

1. Zerlege p−1 = 2sq mit q = 2k+1 ungerade. Falls s = 1, gilt p = 2(2k+1)+1 ≡3 mod 4, und r = ±ak+1 sind bereits die Losungen.

2. Wahle ein z, das kein quadratischer Rest modulo p ist, und setze c ≡ zq mod p.

3. Setze r ≡ aq+12 , t = aq,m = s.

4. Falls t ≡ 1, return r.

5. Finde durch wiederholtes Quadrieren das kleinste i mit 0 < i < m, so daßt2

i ≡ 1.

6. Mit b ≡ c2m−i−1

setze r ≡ rb, t ≡ tb2, c ≡ b2, m = i und gehe nach 4.



Satz 10.5 Seien p 6= q ungerade Primzahlen, n = pq und c quadratischer Restin Z/(n)∗. Wenn sich die vier verschiedenen Quadratwurzeln ±u und ±v aus cin Z/(n) effizient berechnen lassen, dann laßt sich n auch effizient faktorisieren.

Beweis: Aus c ≡ u2 ≡ v2 mod n folgt u2 − v2 ≡ (u + v)(u− v) ≡ 0 mod n unddaher n | (u + v)(u − v), wobei keiner dieser beiden Faktoren gleich 0 ist. Alsomuß p als Primteiler von n entweder u + v oder u − v teilen. durch Berechnungmit Hilfe des Euklidischen Algorithmus findet man so p = ggT (n, u + v) oderp = ggT (n, u− v). Daraus erhalt man sofort q = n

p. �


11 DISKRETER LOGARITHMUS

11 Diskreter Logarithmus

Neben der Primfaktorzerlegung großer Zahlen ist die Berechnung des diskre-ten Logarithmus ein Rechenverfahren, das moglicherweise eine Einwegfunktionmit Falltur darstellt und sich deshalb zur Konstruktion von Kryptosystemen mitoffentlichen Schlusseln eignet.

Definition 11.1 Es seien G eine Gruppe, g ∈ G und c = ge. Man nennt e den(diskreten) Logarithmus von c bezuglich g. Hat g die endliche Ordnung n, sonormiert man noch 0 ≤ e < n.

Im folgenden sei p eine Primzahl und G = Z∗p die multiplikative Gruppe desKorpers mit p Elementen.

Satz 11.2 Fur jede Primzahl p ist Z∗p eine zyklische Gruppe. Es gibt also eing ∈ Z, so daß zu jedem a ∈ Z mit ggT (a, p) = 1 ein Exponent e mit a ≡ ge mod pexistiert. Jedes derartige g nennt man eine Primitivwurzel oder ein primitivesElement modulo p.

Satz 11.3 Es sei p eine Primzahl. Genau dann ist g ∈ Z mit ggT (g, p) = 1 einePrimitivwurzel modulo p, wenn

g(p−1)/q 6≡ 1 mod p

fur alle Primteiler q von p− 1 gilt.

Bemerkung 11.4 Es gibt genau ϕ(p − 1) Primitivwurzeln modulo p, also hin-reichend viele unter den Restklassen modulo p, so daß man durch systematischeSuche bald eine finden kann.

Beispiel 11.5 Fur p = 13 gibt es also

ϕ(12) = ϕ(22 · 3) = ϕ(22)ϕ(3) = 22−1(2− 1)(3− 1) = 4

Primitivwurzeln modulo 13. Testet man die kleinstmogliche g = 2 mit den Prim-teilern q = 2, 3 von p− 1 = 12, so erhalt man

212/2 = 26 = 64 ≡ −1 6≡ 1 mod 13

und212/3 = 24 = 16 ≡ 3 6≡ 1 mod 13.



Also ist g = 2 Primitivwurzel modulo 13. An den Rechnungen sieht man wegender beiden geraden Exponenten auch sofort, daß mit g auch stets −g eine Primi-tivwurzel modulo 13 ist. Dies liegt offensichtlich daran, daß p− 1 ≡ 0 mod 4 ist.Fur Primzahlen p ≡ 3 mod 4 gilt dies dagegen nicht.

Fur g = 3 und g = 5 ergeben sich

36 = (33)2 = 272 ≡ 1 mod 13

und54 = 254 ≡ (−1)2 ≡ 1 mod 13.

Daher konnen beide keine Primitivwurzeln sein. Wegen g = 4 = 22 ist diesesQuadrat einer Primitivwurzel selbst keine Primitivwurzel. Es bleiben dann abernur noch die beiden Restklassen g = 6 und g = 7 ≡ −6. Dies mußten dann diebeiden noch fehlenden Primitivwurzeln modulo 13 sein. In der Tat bestatigt man

66 = 363 ≡ (−3)3 ≡ −27 ≡ −1 6≡ 1 mod 13

und64 = 362 ≡ (−3)2 ≡ 9 6≡ 1 mod 13.

Das Diffie-Hellman-Verfahren

Das erste veroffentlichte Kryptosystem mit offentlichen Schlusseln stammt vonWhitfield Diffie (1944 - ) und Martin Hellman (1945 - ). Dabei werden dieSchlussel wie folgt bestimmt:

(1) Der Sender wahlt eine Primzahl p, eine Primitivwurzel α modulo p und eine(geheime) Zahl 0 ≤ a < p − 1. Er berechnet β ≡ αa mod p und sendet demEmpfanger die Nachricht (p, α, β).

(2) Der Empfanger wahlt nun eine (ebenfalls geheime) Zahl 0 ≤ k < p − 1,berechnet γ ≡ αk mod p und sendet γ an den Sender zuruck.

(3) Der vereinbarte Schlussel ist K = γa = βk. Er kann von beiden Teilnehmernberechnet werden.

Veroffentlicht der Sender schon vorab die Zahlen p und α als seinen offentlichenSchlussel, so brauchen nur die Nachrichten β und γ ausgetauscht zu werden.Sowohl Sender als auch Empfanger verfugen uber die geheimen Zusatzinforma-tionen, die nur ihnen selbst bekannt sind, um den Schlussel K zu berechnen. DieSicherheit des Verfahrens beruht darauf, daß sich der diskrete Logarithmus vonβ bezuglich α nur schwer bestimmen laßt. Es ist aber noch nicht bewiesen, daßsich αab aus αa und αb ohne Kenntnis von a und b nicht bestimmen laßt.



Das ElGamal-Verfahren

Dieses Verfahren entsteht durch eine Modifikation des Diffie-Hellman-Verfahrens.

Die Schritte (1) und (2) laufen hier wie beim Diffie-Hellman-Verfahren ab. Willnun der Empfanger dem Sender einen Klartext m mit 1 ≤ m ≤ p−1 als Nachrichtschicken, so multipliziert er den Schlussel K = βk mit m und schickt das Paar(γ, c) mit dem Geheimtext c ≡ Km mod p.

(3′) Der Sender setzt b = (p− 1)− a und bestimmt

γbc = αk(p−1−a)αakm ≡ αk(p−1)m ≡ m mod p.

Der Nachteil dieses Verfahrens liegt darin, daß der Geheimtext (γ, c) doppelt solang ist wie der Klartext m. Der Vorteil besteht darin, daß durch die zufalligeWahl von k derselbe Klartext nicht zweimal auf die gleiche Weise verschlusseltwird. Außerdem kann man das Verfahren auf andere Gruppen ubertragen, beidenen die Berechnung des diskreten Logarithmus noch “schwerer” ist als in Z∗p.Insbesondere sind hier elliptische Kurven uber endlichen Korpern geeignet.

Shanks Algorithmus

Der folgende Algorithmus zur Berechnung des diskreten Logarithmus in einerzyklischen Gruppe wurde von Daniel Shanks (1917 - 1996) angegeben. Dieser Al-gorithmus ist auch unter der Bezeichnung Baby-Step-Giant-Step in der Literaturbeschrieben.

Es sei g Element einer Gruppe (G, ·) mit endlicher Ordnung ord(g) = n sowiee 6= c ∈< g >. Gesucht ist x = logg(c), also gx = c.

1. Setze m = [√n] + 1.

2. Fur j = 1, . . . ,m− 1 berechne gmj (“Giant-Step”)

3. Sortiere (j, gmj) nach der 2. Komponente in einer Liste L1.

4. Fur i = 1, . . . ,m− 1 berechne cg−i. (“Baby-Step”)

5. Sortiere (i, cg−i) nach der 2. Komponente in einer Liste L2.

6. Suche (j, y) ∈ L1 mit (i, y) ∈ L2.

7. Es ist x = (mj + i) mod n, denn gmj = y = cg−i impliziert c = gmj+i, alsox = logg(c) = (mj + i) mod n.



Die Suche muß wegen c ∈< g >=⇒ 0 ≤ x ≤ n − 1 auch erfolgreich sein, dennDivision von x durch m mit Rest liefert x = jm+ i mit eindeutig bestimmten ji ≤ m − 1. Andererseits folgt auch x ≤ n − 1 ≤ m2 − 1 = (m − 1)m + (m − 1),d. h. die Division der großeren Zahl m2 − 1 liefert einen eindeutig bestimmtenQuotienten m−1, weshalb der eindeutig bestimmte Quotient j der kleineren Zahlx hochstens so groß sein kann: j ≤ m − 1. Daher wurden sowohl i als auch j indem Algorithmus berucksichtigt.

Beispiel 11.6 In G = Z/(29)∗ ist g = 11 eine Primitivwurzel. (Wegen 29− 1 =28 = 22 · 7, 112 = 121 ≡ 5 mod 29, 114 ≡ 25 6≡ 1 mod 29 und 1114 ≡ 57 ≡ 28 6=1 mod 29.) Zur Bestimmung von x = log11(3) wird m = [

√29] + 1 = 6 gesetzt

und die Werte aus L1 fur j = 1, . . . , 5 berechnet:

(1, 116 ≡ 9), (2, 1112 ≡ 23), (3, 1118 ≡ 4), (4, 1124 ≡ 7), (5, 1130 ≡ 5)

Mit 11−1 ≡ 8 erhalt man entsprechend fur L2:

(1, 3 · 8 ≡ 24), (2, 3 · 82 ≡ 18), (3, 3 · 83 ≡ 28), (4, 3 · 84 ≡ 21), (5, 3 · 85 ≡ 23).

Also ist x = log11(3) = 2 · 6 + 5 = 17.

Aufgabe 11.7 Bestimmen Sie analog zu Beispiel 11.5 samtliche Primitivwurzelnmodulo 11.


12 ELLIPTISCHE KURVEN

12 Elliptische Kurven

Definition 12.1 Eine elliptische Kurve uber dem Korper K = R ist eine Menge

E = {(x, y) ∈ K2 | y2 = x3 + ax+ b} ∪ {O}

fur a, b ∈ K mit dem unendlich fernen Punkt O. Fur 4a3 + 27b2 = 0 heißt Esingular, sonst nicht-singular.

Bemerkung 12.2 Die Bedingung 4a3 + 27b2 6= 0 ist hinreichend und notwendigdafur, daß x3 + ax+ b = 0 drei verschiedene (komplexe) Nullstellen hat.

Ist E eine nicht-singulare elliptische Kurve, so wird folgendermaßen eine Addition+ auf E definiert, die (E,+) zu einer abelschen Gruppe macht. (Diese Additionlaßt sich durch eine geometrische Darstellung der Kurve motivieren!)

Zunachst setze O + P = P = P + O fur alle P ∈ E. Damit ist O neutralesElement in (E,+).

Fur P = (x, y) ∈ E setze −P = (x,−y) und P + (−P ) = O = (−P ) + P . Dannliegt −P in E und ist Entgegengesetztes von P .

Fur P = (x1, y1) und Q = (x2, y2) 6= −P setze

λ =y2 − y1x2 − x1

falls x1 6= x2, λ =3x21 + a

2y1sonst

undx3 = λ2 − x1 − x2, y3 = λ(x1 − x3)− y1

sowieP +Q = (x3, y3).

Man kann nun zeigen, daß (x3, y3) zu E gehort und die so definierte Additionkommutativ und assoziativ ist. (Das letzte ist allerdings muhselig.)

Die obigen Definitionen bleiben korrekt, wenn man den Korper K = R durcheinen endlichen Korper K = Zp fur eine Primzahl p > 3 ersetzt. (Die Falle p = 2und p = 3 sind auszuschließen, da die Bemerkung 12.2 dann nicht mehr richtigist und die Definition der Addition auf E so nicht mehr funktioniert.)

Satz 12.3 Es sei p > 3 eine Primzahl. Fur jede nicht-singulare elliptische KurveE uber Zp gilt dann

p+ 1− 2√p ≤ |E| ≤ p+ 1 + 2

√p.



Bemerkung 12.4 Gilt |E| = p fur die nicht-singulare elliptische Kurve E uberZp, so sind die diskreten Logarithmen auf E leicht berechenbar. Derartige Kurvensind also in Kryptosystemen zu vermeiden. Ebenso zu vermeiden sind sogenanntesupersingulare elliptische Kurven, die aber komplizierter zu definieren sind.

Satz 12.5 Es sei p > 3 eine Primzahl und E eine nicht-singulare elliptischeKurve uber Zp. Dann gibt es naturliche Zahlen n und m mit m | n und m | (p−1),so daß (E,+) isomorph zu dem direkten Produkt (Zn,+)× (Zm,+) ist.

Bemerkung 12.6 Es ist m = 1 genau dann, wenn (E,+) selbst eine zyklischeGruppe ist. Dies ist speziell dann der Fall, wenn |E| prim oder das Produktverschiedener Primzahlen ist. In jedem Fall enthalt aber (E,+) eine zyklischeUntergruppe. Diese kann fur das ElGamal-Verfahren benutzt werden.

Beispiel 12.7 Fur p = 11 betrachte die durch y2 = x3+x+6 gegebene elliptischeKurve E, also a = 1, b = 6. Wegen 4a3 + 27b2 = 4 + 5 · 3 = 19 6= 0 mod 11 istE nicht-singular. Fur x = 0, . . . , 10 ∈ Z11 berechnet man schnell x3 + x+ 6 mod11 und erhalt 6, 8, 5, 3, 8, 4, 8, 4, 9, 7, 4. Von diesen Zahlen sind nur 5, 3, 4 und 9Quadratzahlen in Z11 mit den Wurzeln 4, 7, 5, 6, 2, 9 und 3, 8. Damit enthalt Eneben O noch genau die 12 Punkte

(2, 4), (2, 7), (3, 5), (3, 6), (5, 2), (5, 9), (7, 2), (7, 9), (8, 3), (8, 8), (10, 2), (10, 9).

Wegen |E| = 13 ist (E,+) zyklisch und jedes Element außer O kann als primitivesElement genommen werden.

Fur α = (2, 7) ergibt sich beispielsweise 2α = (2, 7) + (2, 7) = (5, 2) wegenλ = (3 ·22 +1) ·(2 ·7)−1 = 2 ·3−1 = 2 ·4 = 8 mod 11 und damit x3 = 82−2−2 = 5mod 11 sowie y3 = 8(2− 5)− 7 = 2 mod 11. Insgesamt erhalt man

α = (2, 7)2α = (5, 2)3α = (8, 3)4α = (10, 2)5α = (3, 6)6α = (7, 9)7α = (7, 2)8α = (3, 5)9α = (10, 9)

10α = (8, 8)11α = (5, 9)12α = (2, 4)



Aufgabe 12.8 Wie im Beipiel 12.7 sei p = 11.

a) Bestimmen Sie die Menge E fur die durch a = 1 und b = 0 gegebene elliptischeKurve.

b) Bestimmen Sie die Menge E fur die durch a = b = 1 gegebene elliptischeKurve.

c) Finden Sie fur a = 2 einen Wert von b, so daß die elliptische Kurve E mity2 = x3 + ax+ b singular ist.

Aufgabe 12.9 Bestimmen sie die Menge E fur die durch a = 4 und b = 0gegebene elliptische Kurve uber Z/(7).

Aufgabe 12.10 Bestimmen sie die Menge E fur die durch a = 1 und b = 1gegebene elliptische Kurve uber Z/(17).


13 ANHANG ZUR CODIERUNGSTHEORIE

13 Anhang zur Codierungstheorie

13.1 ASCII-Code

American Standard Code for Information Interchange

In den Spalten stehen nacheinander: das Zeichen, der Binarcode (zwei Halbbytes),der Hexadezimalcode, der Dezimalcode. Naturlich sind auch die anderen Bytesmit Zeichen belegt, die aber weniger haufig benutzt werden. Insbesondere dieersten 32 Bytes entsprechen den Steuerzeichen des ISO-7-Codes.

A 0100 0001 41 065 a 0110 0001 61 097B 0100 0010 42 066 b 0110 0010 62 098C 0100 0011 43 067 c 0110 0011 63 099D 0100 0100 44 068 d 0110 0100 64 100E 0100 0101 45 069 e 0110 0101 65 101F 0100 0110 46 070 f 0110 0110 66 102G 0100 0111 47 071 g 0110 0111 67 103H 0100 1000 48 072 h 0110 1000 68 104I 0100 1001 49 073 i 0110 1001 69 105J 0100 1010 4A 074 j 0110 1010 6A 106K 0100 1011 4B 075 k 0110 1011 6B 107L 0100 1100 4C 076 l 0110 1100 6C 108

M 0100 1101 4D 077 m 0110 1101 6D 109N 0100 1110 4E 078 n 0110 1110 6E 110O 0100 1111 4F 079 o 0110 1111 6F 111P 0101 0000 50 080 p 0111 0000 70 112Q 0101 0001 51 081 q 0111 0001 71 113R 0101 0010 52 082 r 0111 0010 72 114S 0101 0011 53 083 s 0111 0011 73 115T 0101 0100 54 084 t 0111 0100 74 116U 0101 0101 55 085 u 0111 0101 75 117V 0101 0110 56 086 v 0111 0110 76 118

W 0101 0111 57 087 w 0111 0111 77 119X 0101 1000 58 088 x 0111 1000 78 120Y 0101 1001 59 089 y 0111 1001 79 121Z 0101 1010 5A 090 z 0111 1010 7A 122[ 0101 1011 5B 091 { 0111 1011 7B 123\ 0101 1100 5C 092 | 0111 1100 7C 124] 0101 1101 5D 093 } 0111 1101 7D 125ˆ 0101 1110 5E 094 ∼ 0111 1110 7E 126

0101 1111 5F 095 > 0111 1111 7F 127’ 0110 0000 60 096 / 1000 0000 80 128


13.1 ASCII-Code 13 ANHANG ZUR CODIERUNGSTHEORIE

0010 0000 20 032! 0010 0001 21 033“ 0010 0010 22 034

# 0010 0011 23 035$ 0010 0100 24 036

% 0010 0101 25 037& 0010 0110 26 038´ 0010 0111 27 039( 0010 1000 28 040) 0010 1001 29 041* 0010 1010 2A 042+ 0010 1011 2B 043, 0010 1100 2C 044- 0010 1101 2D 045. 0010 1110 2E 046/ 0010 1111 2F 0470 0011 0000 30 0481 0011 0001 31 0492 0011 0010 32 0503 0011 0011 33 0514 0011 0100 34 0525 0011 0101 35 0536 0011 0110 36 0547 0011 0111 37 0558 0011 1000 38 0569 0011 1001 39 057: 0011 1010 3A 058; 0011 1011 3B 059< 0011 1100 3C 060= 0011 1101 3D 061> 0011 1110 3E 062? 0011 1111 3F 063

0100 0000 40 064

Die ASCII-Zeichen, bei denen das hochste Bit gleich 1 ist, werden unter anderemfur Sonderzeichen aus anderen Alphabeten (Danisch, Spanisch etc.) genutzt undje nach Ausgabemedium unterschiedlich dargestellt. Man faßt sie daher auchoft als “nicht druckbare Zeichen” auf. Wenn sie nicht genutzt werden, wird dashochste Bit frei und kann als Paritatsbit (vgl. Beispiel 1.1) benutzt werden.


13.2 Hexadezimalcode 13 ANHANG ZUR CODIERUNGSTHEORIE

13.2 Hexadezimalcode

Zahl Binardarstellung Hexadezimalcode0 0000 01 0001 12 0010 23 0011 34 0100 45 0101 56 0110 67 0111 78 1000 89 1001 9

10 1010 A11 1011 B12 1100 C13 1101 D14 1110 E15 1111 F

Bytes (also Folgen von 8 Bits) werden oft durch zwei Hexadezimalzeichen darge-stellt:

Byte Hexadezimalcode00000000 0000000001 01

......

00001111 0F00010000 10

......

11111110 FE11111111 FF


13.3 ISO-7 13 ANHANG ZUR CODIERUNGSTHEORIE

13.3 ISO-7

International Standards Organization

(*) bezeichnet hier Platze, die in nationalen Normen auch anders belegt werdenkonnen.

0 1 2 3 4 5 6 700 NUL DLE SP 0 @ (*) P (*) p01 SOH DC1 ! 1 A Q a q02 STX DC2 ” 2 B R b r03 ETX DC3 # (*) 3 C S c s04 EOT DC4 $ 4 D T d t05 ENQ NAK % 5 E U e u06 ACK SYN & 6 F V f v07 BEL ETB ’ 7 G W g h08 BS CAN ( 8 H X h x09 HT EM ) 9 I Y i y10 LF SUB * : J Z j z11 VT ESC + ; K [ (*) k { (*)12 FF FS , < L \ (*) l | (*)13 CR GS - = M ] (*) m } (*)14 SO RS . > N (*) n ˜(*)15 SI US / ? O − o DEL

In den ersten beiden Spalten stehen gewisse Steuerzeichen, beispielsweise NUL= Leerzeichen, EOT = End of Transmission, BEL = Klingelzeichen, LF = Zei-lenvorschub, CR = Wagenrucklauf, SO = Dauerschaltung, SI = Ruckschaltung,CAN = ungultig, EM = End of Message, SUB = Substitutionszeichen, ESC =Codeumschaltung.

Schreibt man die Zeilennummern hexadezimal, also 10 = A, 11 = B, 12 = C, 13 =D, 14 = E, 15 = F und liest fur das ISO-7-Zeichen das Paar (Spaltennummer, Zei-lennummer) als Hexadezimalzahl, so erhalt man die Nummer des ASCII-Zeichens.


13.4 Bacon-Code (um 1580) 13 ANHANG ZUR CODIERUNGSTHEORIE

13.4 Bacon-Code (um 1580)

Francis Bacon (1561 - 1626), englischer Philosoph

a AAAAAb AAAABc AAABAd AAABBe AABAAf AABABg AABBAh AABBBi ABAAAk ABAABl ABABA

m ABABBn ABBAAo ABBABp ABBBAq ABBBBr BAAAAs BAAABt BAABAv BAABBw BABAAx BABABy BABBAz BABBB


13.5 Morse-Alphabet 13 ANHANG ZUR CODIERUNGSTHEORIE

13.5 Morse-Alphabet

Samuel Morse (1791 - 1872) benutzte fur seinen Telegraphen 1837 zunachstnur Ziffern zur Ubertragung, aus denen nach einem Codebuch Worter gebildetwurden. 1840 fuhrte er einen von A. Bain stammenden Code mit wechselndenWortlangen ein. Das heutige Morse-Alphabet wurde erst 1851 auf Vorschlag vonC. Gerke vom Deutsch-Osterreichischen Telegraphenverein angenommen und er-hielt 1865 im Internationalen Telegraphenverein allgemeine Anerkennung. (SchonGauß und Weber (1833) und ebenso Steinheil (1837) hatten Codes mit wechseln-den Wortlangen fur ihre Telegraphen benutzt.)

a ·− 0 −−−−−a · − ·− 1 · − − −−a · − − · − 2 · · − − −b − · ·· 3 · · · − −c − · −· 4 · · · · −

ch −−−− 5 · · · · ·d − · · 6 − · · · ·e · 7 −− · · ·e · · − · · 8 −−− · ·f · · −· 9 −−−− ·g −− · . · − · − ·−h · · ·· , −− · · −−i ·· : −−− · ··j · − −− - − · · · ·−k − · − ’ · − − −−·l · − ·· ( − · − − ·−

m −− ? · · − − ··n −· “ · − · · −·n −− · − −o −−− Notruf · · · − − − · · ·o −−−· Anfang − · − · −p · − −· Ende · · · − ·−q −− ·−r · − ·s · · ·t −u · · −v · · ·−w · − −x − · ·−y − · −−z −− ··


13.5 Morse-Alphabet 13 ANHANG ZUR CODIERUNGSTHEORIE

Eine gangige Binarcodierung des Morse-Alphabets ist

· ↔ 01, − ↔ 0111, “Zwischenraum” ↔ 000.


13.6 Dezimalziffern-Codes 13 ANHANG ZUR CODIERUNGSTHEORIE

13.6 Dezimalziffern-Codes

13.6.1 Zahlcode

Wird bei Fernsprechern benutzt.

1 102 1103 11104 111105 1111106 11111107 111111108 1111111109 11111111100 11111111110

13.6.2 Tetradencodes

BCD Excess-3 Aiken Gray Glixon0 0000 0011 0000 0000 00001 0001 0100 0001 0001 00012 0010 0101 0010 0011 00113 0011 0110 0011 0010 00104 0100 0111 0100 0110 01105 0101 1000 1011 0111 01116 0110 1001 1100 0101 01017 0111 1010 1101 0100 01008 1000 1011 1110 1100 11009 1001 1100 1111 1101 1000

O’Brien Petherick Tompkins Gray-Stibitz0 0001 0101 0010 00101 0011 0001 0011 01102 0010 0011 0111 01113 0110 0010 0101 01014 0100 0110 0100 01005 1100 1110 1100 11006 1110 1010 1101 11017 1010 1011 1001 11118 1011 1001 1000 11109 1001 1101 1010 1010


13.6 Dezimalziffern-Codes 13 ANHANG ZUR CODIERUNGSTHEORIE

BCD (Binary Coded Decimal)

Excess-3 heißt auch Stibitz-Code, er vermeidet die Tetraden 0000 (Stromunter-brechung) und 1111 (Dauersignal) und entsteht aus dem BCD durch Additionvon 3.

Der Aiken-Code ist ein Stellenwertcode, die Bits stehen fur die Werte 2,4,2,1, esgilt, daß die Ziffer 9− x das bitweise Komplement der Ziffer x ist.

Der Gray-Code (nach F. Gray 1953) hat die Eigenschaft, daß sich die Tetra-den aufeinanderfolgender Ziffern an genau einer Stelle unterscheiden. Er ist eineinschrittiger oder stetiger Code. Gray-Codes konnen uber beliebigen q-narenAlphabeten und von beliebiger Lange konstruiert werden, vgl. Beispiel 2.8.

Der Glixon-Code ist ebenfalls stetig, nur ist auch der Ubergang von der 9 zur0 durch die Anderung einer einzigen Stelle realisiert. Dasselbe gilt fur die restli-chen Codes. Diese weisen bestimmte “Symmetrien” zwischen den ersten und denletzten funf Tetraden auf.

13.6.3 Pentadencodes

2 aus 5 CCIT-2 Libaw-Craig0 11000 01101 000001 00011 11101 000012 00101 11001 000113 00110 10000 001114 01001 01010 011115 01010 00001 111116 01100 10101 111107 10001 11100 111008 10010 01100 110009 10100 00011 10000

Der 2-aus-5-Code wurde zur Codierung von Postleitzahlen benutzt. Mit Ausnah-me der Codierung von 0 handelt es sich um einen Stellenwertcode mit den Werten7,4,2,1,0. Das letzte Bit kann man daher als Paritatskontrollbit deuten.

Der CCIT-2-Code (Comite consultatif international de telegraphie) ist der auf I.M. Baudot zuruckgehende Telegraphencode Nr. 2 im internationalen Fernschreib-verkehr.

Der Libaw-Craig-Code (manchmal auch Johnson-Code genannt) ist wie die Gray-Codes einschrittig oder stetig. Er entspricht der Zifferndarstellung durch Morse-zeichen, wenn man ihn spiegelt und 0 als − und 1 als · interpretiert.


13.7 Langere Binarcodes 13 ANHANG ZUR CODIERUNGSTHEORIE

13.7 Langere Binarcodes

biquinar EBCDI 1 aus 100 000001 11110000 00000000011 000010 11110001 00000000102 000100 11110010 00000001003 001000 11110011 00000010004 010000 11110100 00000100005 100001 11110101 00001000006 100010 11110110 00010000007 100100 11110111 00100000008 101000 11111000 01000000009 110000 11111001 1000000000

Der Extended Binary Coded Decimal Interchange Code wurde von IBM ent-wickelt. Die ersten 4 Bits bilden den Zonenteil und sind stets gleich 1111, dieletzten 4 Bits bilden den Ziffernteil und codieren gemaß BCD.

Der Gillham-Code ist ein stetiger 12-Bit-Code. Er wird bei der Ubermittlung derbarometrischen Hohenangabe von Flugobjekten an die Bodenstation benutzt.

Weitere gebrauchliche Binarcodes der Lange 7 fur Ziffern findet man bei denEAN-Codierungen.


13.8 CCIT-2 13 ANHANG ZUR CODIERUNGSTHEORIE

13.8 CCIT-2

Der CCIT-2-Code (Comite consultatif international de telegraphie) ist der aufMurray zuruckgehende Telegraphencode Nr. 2 im internationalen Fernschreib-verkehr (Telex). Er wurde 1932 genormt.

Es gibt zunachst 5 einfache belegte Codeworter, die Steuerzeichen codieren:

SP (Zwischenraum) 00000CR (Wagenrucklauf) 00010LF (Zeilenvorschub) 01000Zeichenumschaltung 11011Buchstabenumschaltung 11111

Dann ist jedes weitere Codewort doppelt belegt. Die Decodierung erfolgt je nachEmpfang der letzten Buchstabenumschaltung/Zeichenumschaltung.

Buchstabe Zeichen CodewortA − 11000B ? 10011C : 01110D Wer da? 10010E 3 10000F [ 10110G ] 01011H 10 00101I 8 01100J ; 11010K ( 11110L ) 01001

M . 00111N , 00110O 9 00011P 0 01101Q 1 11101R 4 01010S ’ 10100T 5 00001U 7 11100V = 01111

W 2 11001X / 10111Y 6 10101Z + 10001


13.8 CCIT-2 13 ANHANG ZUR CODIERUNGSTHEORIE

Aufbauend auf dem Bacon-Code benutzte aber schon I. M. Baudot 1874 in sei-nem Drucktelegraphen einen 5-Bit-Code und Carpentier benutzte 1887 den Funf-Spur-Lochstreifen, nachdem Wheatstone schon 1841 gelochte Papierstreifen insFernschreibwesen eingefuhrt hatte.


13.9 Flexowriter 13 ANHANG ZUR CODIERUNGSTHEORIE

13.9 Flexowriter

Zeichen Codewort Zeichen CodewortLeerzeichen 00000000 A 01000001

BS 10001000 B 01000010HT 00001001 C 11000011CR 00001010 D 01000100LF 10001101 E 11000101

Zwischenraum 10100000 F 11000110( 00101000 G 01000111) 10101001 H 01001000

% 10100101 I 11001001: 00111010 J 11001010/ 10101111 K 01001011

+ 00101011 L 11001100- 00101101 M 010011010 00110000 N 010011101 10110001 O 110011112 10110010 P 010100003 00110011 Q 110100014 10110100 R 110100105 00110101 S 010100116 00110110 T 110101007 10110111 U 010101018 10111000 V 010101109 00111001 W 11010111

Loschung einer Irrung 11111111 X 11011000Y 01011001Z 01011010

Das hochstwertige Bit ist ein Paritatskontrollbit.


13.10 IBM-Lochkarten-Code 13 ANHANG ZUR CODIERUNGSTHEORIE

13.10 IBM-Lochkarten-Code

Hermann Hollerith (1860 - 1929) benutzte erstmals 1889 bei der statistischen Aus-wertung der amerikanischen Volkszahlung die Binarverschlusselung von Daten aufLochkarten. Alphanumerische Lochkartenmaschinen wurden 1931 eingefuhrt.

Zeichen Codewort Zeichen Codewort0 001000000000 S 0010100000001 000100000000 T 0010010000002 000010000000 U 0010001000003 000001000000 V 0010000100004 000000100000 W 0010000010005 000000010000 X 0010000001006 000000001000 Y 0010000000107 000000000100 Z 0010000000018 000000000010 Zwischenraum 0000000000009 000000000001 ≥ 000010000010A 100100000000 = 000001000010B 100010000000 ’ 000000100010C 100001000000 : 000000010010D 100000100000 ¿ 000000001010E 100000010000 ˆ 000000000110F 100000001000 + 100000000000G 100000000100 ≤ 100010000010H 100000000010 . 100001000010I 100000000001 ) 100000100010J 010100000000 [ 100000010010K 010010000000 ¡ 100000001010L 010001000000 | 100000000110

M 010000100000 - 010000000000N 010000010000 ’ 010010000010O 010000001000 $ 010001000010P 010000000100 * 010000100010Q 010000000010 ] 010000010010R 010000000001 ; 010000001010

− 010000000110/ 0011000000006= 001010000010, 001001000010( 001000100010

10 001000010010‘ 001000001010∨ 001000000110


13.11 EAN-13-Codierungen 13 ANHANG ZUR CODIERUNGSTHEORIE

13.11 EAN-13-Codierungen

Codiert werden 13 Ziffern c1c2 . . . c7c8 . . . c13. Dabei bestimmt die Ziffer c1 durchCode D, nach welchem Code (A bzw. B) die jeweilige Ziffer c2, c3, . . . , c7 codiertwird. Die Ziffern c8, . . . , c13 werden alle nach dem Code C codiert.

Zeichen Code A Code B Code C Code D0 0001101 0100111 1110010 AAAAAA1 0011001 0110011 1100110 AABABB2 0010011 0011011 1101100 AABBAB3 0111101 0100001 1000010 AABBBA4 0100011 0011101 1011100 ABAABB5 0110001 0111001 1001110 ABBAAB6 0101111 0000101 1010000 ABBBAA7 0111011 0010001 1000100 ABABAB8 0110111 0001001 1001000 ABABBA9 0001011 0010111 1110100 ABBABA

B und C immer gerade, A immer ungerade: erste Ziffer von links immer ungerade,erste Ziffer von rechts immer gerade.

Beispiele


13.12 Landerkennungen der Euro-Banknoten13 ANHANG ZUR CODIERUNGSTHEORIE

13.12 Landerkennungen der Euro-Banknoten

Land Kennbuchstabe Alphabetpos. + 10 Quersumme mod 9Belgien Z 36 0Griechenland Y 35 8Deutschland X 34 7(Danemark) (W) 33 6Spanien V 32 5Frankreich U 31 4Irland T 30 3Italien S 29 2Luxemburg R 28 1Niederlande P 26 8Osterreich N 24 6Portugal M 23 5Finnland L 22 4(Schweden) (K) 21 3(Großbritannien) (J) 20 2Slowenien H 18 0Zypern G 17 8Malta F 16 7Slowakei E 15 6Estland D 14 5Lettland C 13 4Litauen B 12 3? A 11 2

Die Buchstaben “Q”, “O” und “I” wurden wegen der Gefahr einer Verwechse-lung (untereinander bzw. mit “1”) nicht vergeben, “B” und “A” sind noch freiverfugbar.

Griechenland hat mit Danemark getauscht, da kein griechischer Buchstabe “W”existiert.

Luxemburg verausgabt keine Banknoten.

Danemark, Schweden und Großbritannien nehmen an der Wahrungsunion nochnicht teil.


13.13 Prufzifferncodierung der DM-Scheine von 1990 - 200113 ANHANG ZUR CODIERUNGSTHEORIE

13.13 Prufzifferncodierung der DM-Scheine von 1990 -2001

13.13.1 Codierung der Buchstaben

A D G K L N S U Y Z0 1 2 3 4 5 6 7 8 9

13.13.2 Verknupfungstafel der Diedergruppe D5

| 0 1 2 3 4 5 6 7 8 90 | 0 1 2 3 4 5 6 7 8 91 | 1 2 3 4 0 6 7 8 9 52 | 2 3 4 0 1 7 8 9 5 63 | 3 4 0 1 2 8 9 5 6 74 | 4 0 1 2 3 9 5 6 7 85 | 5 9 8 7 6 0 4 3 2 16 | 6 5 9 8 7 1 0 4 3 27 | 7 6 5 9 8 2 1 0 4 38 | 8 7 6 5 9 3 2 1 0 49 | 9 8 7 6 5 4 3 2 1 0

13.13.3 Verwendete Permutation und ihre Potenzen

∗ | 0 1 2 3 4 5 6 7 8 9π | 1 5 7 6 2 8 3 0 9 4π2 | 5 8 0 3 7 9 6 1 4 2π3 | 8 9 1 6 0 4 3 5 2 7π4 | 9 4 5 3 1 2 6 8 7 0π5 | 4 2 8 6 5 7 3 9 0 1π6 | 2 7 9 3 8 0 6 4 1 5π7 | 7 0 4 6 9 1 3 2 5 8π8 | 0 1 2 3 4 5 6 7 8 9π9 | 1 5 7 6 2 8 3 0 9 4π10 | 5 8 0 3 7 9 6 1 4 2


13.14 Prufzifferncode bei Schweizer Einzahlungsscheinen13 ANHANG ZUR CODIERUNGSTHEORIE

13.14 Prufzifferncode bei Schweizer Einzahlungsscheinen

Verknupfungstafel der verwendeten Quasigruppe

∗ | 0 1 2 3 4 5 6 7 8 90 | 0 9 4 6 8 2 7 1 3 51 | 9 4 6 8 2 7 1 3 5 02 | 4 6 8 2 7 1 3 5 0 93 | 6 8 2 7 1 3 5 0 9 44 | 8 2 7 1 3 5 0 9 4 65 | 2 7 1 3 5 0 9 4 6 86 | 7 1 3 5 0 9 4 6 8 27 | 1 3 5 0 9 4 6 8 2 78 | 3 5 0 9 4 6 8 2 7 19 | 5 0 9 4 6 8 2 7 1 3


13.15 Fehlerhaufigkeiten bei der Ziffernubermittlung13 ANHANG ZUR CODIERUNGSTHEORIE

13.15 Fehlerhaufigkeiten bei der Ziffernubermittlung

Verhoeff fuhrte 1969 eine Untersuchung uber das Auftreten verschiedener Fehlerbei der Ubermittlung sechsstelliger Zahlen (in niederlandischer Sprache) durch.

Fehlertyp Beispiel rel. HaufigkeitEinzelfehler a→ a′ 79.0 %Nachbartranspositionen ab→ ba 10.2 %Sprungtranspositionen acb→ bca 0.8 %Zwillingsfehler aa→ bb 0.6 %Phonetische Fehler a0→ 1a(a ≥ 3) 0.5%Sprung-Zwillingsfehler aca→ bcb 0.3%Restliche Fehler 8.6%

Die Fehlerhaufigkeit war nicht fur alle Stellen gleich. Die letzten beiden Stellenwaren doppelt so oft betroffen wie die anderen. Die Haufigkeit von Fehlern steigtmit der Lange der ubermittelten Zahlen. Das (hier statistisch nicht betrachte-te) Auslassen von Ziffern tritt mit einer Wahrscheinlichkeit zwischen 10 und 20Prozent auf, bevorzugt an der letzten Stelle und bei der Ziffer 0. Die Art derZahlenubermittlung (beispielsweise per Telefon oder handschriftlich) beeinflußtdie Fehlerhaufigkeiten erheblich.


13.16 Eight-To-Fourteen-Modulation (EFM)13 ANHANG ZUR CODIERUNGSTHEORIE

13.16 Eight-To-Fourteen-Modulation (EFM)

Byte Codewort Byte Codewort00000000 01001000100000 01000000 0100100010010000000001 10000100000000 01000001 1000010010010000000010 10010000100000 01000010 1001000010010000000011 10001000100000 01000011 1000100010010000000100 01000100000000 01000100 0100010010010000000101 00000100010000 01000101 0000000010010000000111 00100100000000 01000111 0010010010010000001000 01001001000000 01001000 0100100100010000001001 10000001000000 01001001 1000000100010000001010 10010001000000 01001010 1001000100010000001011 10001001000000 01001011 1000100100010000001100 01000001000000 01001100 0100000100010000001101 00000001000000 01001101 0000000100010000001111 00100001000000 01001111 0010000100010000010000 10000000100000 01010000 1000000010010000010001 10000010000000 01010001 1000001000010000010010 10010010000000 01010010 1001001000010000010011 00100000100000 01010011 0010000010010000010100 01000010000000 01010100 0100001000010000010101 00000010000000 01010101 0000001000010000010110 00010010000000 01010110 0001001000010000010111 00100010000000 01010111 0010001000010000011000 01001000010000 01011000 0100100000010000011001 10000000010000 01011001 1000000000010000011010 10010000010000 01011010 1001000000010000011011 10001000010000 01011011 1000100000010000011100 01000000010000 01011100 0100000000010000011101 00001000010000 01011101 0000100000010000011110 00010000010000 01011110 0001000000010000011111 00100000010000 01011111 0010000000010000100000 00000000100000 01100000 0100100010001000100001 10000100001000 01100001 1000010010001000100010 00001000100000 01100010 1001000010001000100011 00100100100000 01100011 1000100010001000100100 01000100001000 01100100 0100010010001000100101 00000100001000 01100101 0000000010001000100110 01000000100000 01100110 0100000010010000100111 00100100001000 01100111 0010010010001000101000 01001001001000 01101000 01001001000010



Byte Codewort Byte Codewort00101001 10000001001000 01101001 1000000100001000101010 10010001001000 01101010 1001000100001000101011 10001001001000 01101011 1000100100001000101100 01000001001000 01101100 0100000100001000101101 00000001001000 01101101 0000000100001000101110 00010001001000 01101110 0001000100001000101111 00100001001000 01101111 0010000100001000110000 00000100000000 01110000 1000000010001000110001 10000010001000 01110001 1000001000001000110010 10010010001000 01110010 1001001000001000110011 10000100010000 01110011 0010000010001000110100 01000010001000 01110100 0100001000001000110101 00000010001000 01110101 0000001000001000110110 00010010001000 01110110 0001001000001000110111 00100010001000 01110111 0010001000001000111000 01001000001000 01111000 0100100000001000111001 10000000001000 01111001 0000100100100000111010 10010000001000 01111010 1001000000001000111011 10001000001000 01111011 1000100000001000111100 01000000001000 01111100 0100000000001000111101 00001000001000 01111101 0000100000001000111110 00010000001000 01111110 0001000000001000111111 00100000001000 01111111 00100000000010

Byte Codewort Byte Codewort10000000 01001000100001 11000000 0100010010000010000001 10000100100001 11000001 1000010001000110000010 10010000100001 11000010 1001001001000010000011 10001000100001 11000011 0000100010010010000100 01000100100001 11000100 0100010001000110000101 00000000100001 11000101 0000010001000110000110 00010000100001 11000110 0001001001000010000111 00100100100001 11000111 0010010001000110001000 01001001000001 11001000 0000100100000110001001 10000001000001 11001001 1000010000000110001010 10010001000001 11001010 0000100100010010001011 10001001000001 11001011 0000100100000010001100 01000001000001 11001100 0100010000000110001101 00000001000001 11001101 0000010000000110001110 00010001000001 11001110 0000001001000010001111 00100001000001 11001111 00100100000001



Byte Codewort Byte Codewort10010000 10000000100001 11010000 0000010010010010010001 10000010000001 11010001 1000001001000110010010 10010010000001 11010010 1001001001000110010011 00100000100001 11010011 1000010010000010010100 01000010000001 11010100 0100001001000110010101 00000010000001 11010101 0000001001000110010110 00010010000001 11010110 0001001001000110010111 00100010000001 11010111 0010001001000110011000 01001000000001 11011000 0100100001000110011001 10000010010000 11011001 1000000001000110011010 10010000000001 11011010 1001000001000110011011 10001000000001 11011011 1000100001000110011100 01000010010000 11011100 0100000001000110011101 00001000000001 11011101 0000100001000110011110 00010000000001 11011110 0001000001000110011111 00100010010000 11011111 0010000001000110100000 00001000100001 11100000 0100010000001010100001 10000100001001 11100001 0000010000001010100010 01000100010000 11100010 1000010001001010100011 00000100100001 11100011 0010010000001010100100 01000100001001 11100100 0100010001001010100101 00000100001001 11100101 0000010001001010100110 01000000100001 11100110 0100000010001010100111 00100100001001 11100111 0010010001001010101000 01001001001001 11101000 1000010000001010101001 10000001001001 11101001 1000010000010010101010 10010001001001 11101010 0000100100100110101011 10001001001001 11101011 0000100100001010101100 01000001001001 11101100 0100010000010010101101 00000001001001 11101101 0000010000010010101110 00010001001001 11101110 0001000010001010101111 00100001001001 11101111 0010010000010010110000 00000100100000 11110000 0000010010001010110001 10000010001001 11110001 1000001001001010110010 10010010001001 11110010 1001001001001010110011 00100100010000 11110011 0000100010001010110100 01000010001001 11110100 0100001001001010110101 00000010001001 11110101 0000001001001010110110 00010010001001 11110110 0001001001001010110111 00100010001001 11110111 00100010010010



Byte Codewort Byte Codewort10111000 01001000001001 11111000 0100100001001010111001 10000000001001 11111001 1000000001001010111010 10010000001001 11111010 1001000001001010111011 10001000001001 11111011 1000100001001010111100 01000000001001 11111100 0100000001001010111101 00001000001001 11111101 0000100001001010111110 00010000001001 11111110 0001000001001010111111 00100000001001 11111111 00100000010010


13.17 Irreduzible Polynome 13 ANHANG ZUR CODIERUNGSTHEORIE

13.17 Irreduzible Polynome

In der folgenden Tabelle sind einige irreduzible Polynome p(x) vom Grad n uberZ/(2) angegeben, die man zur Konstruktion der endlichen Korper F2n verwendenkann. Ab n = 9 sind nur noch die Polynome mit minimaler Anzahl von Ter-men gelistet. (Es ist bekannt, daß man bis n = 10000 mit hochstens 5 Termenauskommt.)

n p(x)1 x, x+ 12 x2 + x+ 13 x3 + x+ 1, x3 + x2 + 14 x4 + x+ 1, x4 + x3 + 1,x4 + x3 + x2 + x+ 15 x5 + x2 + 1, x5 + x3 + 1,

x5 + x4 + x3 + x2 + 1, x5 + x4 + x3 + x+ 1,x5 + x4 + x2 + x+ 1, x5 + x3 + x2 + x+ 1,

6 x6 + x+ 1, x6 + x5 + 1, x6 + x3 + 1,x6 + x5 + x4 + x2 + 1, x6 + x5 + x4 + x+ 1,x6 + x5 + x3 + x2 + 1, x6 + x5 + x2 + x+ 1,x6 + x4 + x3 + x+ 1, x6 + x4 + x2 + x+ 1

7 x7 + x+ 1, x7 + x3 + 1, x7 + x3 + x2 + x+ 1,x7 + x6 + x5 + x4 + x2 + x+ 1, x7 + x5 + x4 + x3 + x2 + x+ 1,(insgesamt 18)

8 x8 + x4 + x3 + x+ 1, x8 + x4 + x3 + x2 + 1,x8 + x7 + x6 + x5 + x4 + x+ 1, x8 + x6 + x5 + x3 + 1,x8 + x7 + x5 + x4 + x3 + x2 + 1, x8 + x6 + x5 + x4 + x2 + x+ 1(insgesamt 30)

9 x9 + x+ 1 (insgesamt 56)10 x10 + x3 + 1 (insgesamt 99)11 x11 + x2 + 1 (insgesamt 186)12 x12 + x3 + 1 (insgesamt 335)13 x13 + x4 + x3 + x+ 1 (insgesamt 630)14 x14 + x5 + 1 (insgesamt 1161)15 x15 + x+ 1 (insgesamt 2182)16 x16 + x5 + x3 + x+ 117 x17 + x3 + 118 x18 + x3 + 119 x19 + x5 + x2 + x+ 120 x20 + x3 + 1


13.18 Inverse modulo 26 13 ANHANG ZUR CODIERUNGSTHEORIE

13.17.1 Der Korper GF(8)

Die Elemente des endlichen Korpers GF (8) = F8 mit acht Elementen, werden alsKoeffizienten-Tripel a2a1a0 der Polynome f(x) = a2x

2 + a1x+ a0 ∈ Z/(2)[x] vomGrad n < 3 geschrieben, also

F8 = {000, 001, 010, 011, 100, 101, 110, 111}.

Die Addition erfolgt daher koordinatenweise modulo 2, bei der Multiplikationf(x) ∗ g(x) werden die Reste bei der Division von f(x) · g(x) durch das irre-duzible Polynom p(x) = x3 + x + 1 genommen. Daher ergibt sich die folgendeMultiplikationstabelle:

* 000 001 010 011 100 101 110 111000 000 000 000 000 000 000 000 000001 000 001 010 011 100 101 110 111010 000 010 100 110 011 001 111 101011 000 011 110 101 111 100 001 010100 000 100 011 111 110 010 101 001101 000 101 001 100 010 111 011 110110 000 110 111 001 101 011 010 100111 000 111 101 010 001 110 100 011

Man kann die Elemente von F8 naturlich auch als Oktalzahlen 0 = 000, . . . , 7 =111 notieren.

Es ist entsprechend p(x) = x4 + x + 1 ein irreduzibles Polynom, das man zurKonstruktion von F16 verwenden kann. Die Elemente dieses Korpers, also diesmalvierstellige Bitfolgen, lassen sich dabei auch als Hexadezimalzahlen darstellen:

F16 = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9, A,B,C,D,E, F}.

Um den Korper F256 zu erzeugen, dessen Elemente man als die moglichen 28 = 256Bytes auffassen kann, geht man ganz analog vor, indem man ublicherweise dasirreduzible Polynom p(x) = x8 + x4 + x3 + x2 + 1 benutzt. Dabei schreibt manoft die Bytes als jeweils zwei Halb-Bytes in hexadezimaler Notation.

13.18 Inverse modulo 26

Bei der Entschlusselung in affinen Kryptosystemen oder Hill-Kryptosystemenwerden die Inversen zu den ϕ(26) = ϕ(2)ϕ(13) = 12 Restklassen a modulo 26mit ggT (a, 26) = 1 benotigt. Diese sind in der folgenden Tabelle angegeben.


13.18 Inverse modulo 26 13 ANHANG ZUR CODIERUNGSTHEORIE

a 1 3 5 7 9 11 15 17 19 21 23 25a−1 1 9 21 15 3 19 7 23 11 5 17 25

oder mit anderen Reprasentanten der Restklassen

a 1 3 5 7 9 11 -11 -9 -7 -5 -3 -1a−1 1 9 -5 -11 3 -7 7 -3 11 5 -9 -1

Multiplikationstabelle mit A = 0, . . . , Z = 25

a A B C D E F G H I J K L M1 0 1 2 3 4 5 6 7 8 9 10 11 123 0 3 6 9 12 15 18 21 24 1 4 7 105 0 5 10 15 20 25 4 9 14 19 24 3 87 0 7 14 21 2 9 16 23 4 11 18 25 69 0 9 18 1 10 19 2 11 20 3 12 21 411 0 11 22 7 18 3 14 25 10 21 6 17 215 0 15 4 19 8 23 12 1 16 5 20 9 2417 0 17 8 25 16 7 24 15 6 23 14 5 2219 0 19 12 5 24 17 10 3 22 15 8 1 2021 0 21 16 11 6 1 22 17 12 7 2 23 1823 0 23 20 17 14 11 8 5 2 25 22 19 1625 0 25 24 23 22 21 20 19 18 17 16 15 14

a N O P Q R S T U V W X Y Z1 13 14 15 16 17 18 19 20 21 22 23 24 253 13 16 19 22 25 2 5 8 11 14 17 20 235 13 18 23 2 7 12 17 22 1 6 11 16 217 13 20 1 8 15 22 3 10 17 24 5 12 199 13 22 5 14 23 6 15 24 7 16 25 8 1711 13 24 9 20 5 16 1 12 23 8 19 4 1515 13 2 17 6 21 10 25 14 3 18 7 22 1117 13 4 21 12 3 20 11 2 19 10 1 18 919 13 6 25 18 11 4 23 16 9 2 21 14 721 13 8 3 24 19 14 9 4 25 20 15 10 523 13 10 7 4 1 24 21 18 15 12 9 6 325 13 12 11 10 9 8 7 6 5 4 3 2 1


14 ANHANG ZUR KRYPTOGRAPHIE

14 Anhang zur Kryptographie

14.1 Hexadezimalcode

Zahl Binardarstellung Hexadezimalcode0 0000 01 0001 12 0010 23 0011 34 0100 45 0101 56 0110 67 0111 78 1000 89 1001 9

10 1010 A11 1011 B12 1100 C13 1101 D14 1110 E15 1111 F

Bytes (also Folgen von 8 Bits) werden oft durch zwei Hexadezimalzeichen darge-stellt:

Byte Hexadezimalcode00000000 0000000001 01

......

00001111 0F00010000 10

......

11111110 FE11111111 FF


14.2 Bacon-Code (um 1580) 14 ANHANG ZUR KRYPTOGRAPHIE

14.2 Bacon-Code (um 1580)

Francis Bacon (1561 - 1626), englischer Philosoph

a AAAAAb AAAABc AAABAd AAABBe AABAAf AABABg AABBAh AABBBi ABAAAk ABAABl ABABA

m ABABBn ABBAAo ABBABp ABBBAq ABBBBr BAAAAs BAAABt BAABAv BAABBw BABAAx BABABy BABBAz BABBB


14.3 Buchstabenhaufigkeiten 14 ANHANG ZUR KRYPTOGRAPHIE

14.3 Buchstabenhaufigkeiten

Die Zahlenangaben bedeuten jeweils %.

Deutsch

Einzelbuchstaben (in Cliquen)

E (17.5)

N (9.8)

I (7.7) R (7.5) S (6.8) A (6.4) T (6.1)

D (4.8) U (4.2) H (4.2)

L (3.5) G (3.0) O (3.0) C (2.7) M (2.6)

B (1.9) F (1.6) W (1.5) K (1.5) Z (1.1)

P (1.0) V (0.9)

J (0.3) Y (0.1) X (0.04) Q (0.02)

Bigramme (676 = 26 · 26 mogliche)

EN (0.0443) ER (0.0375) CH (0.0280) EI (0.0242) DE (0.0233) ND (0.0208)IN (0.0197) GE (0.0196) IE (0.0188) TE (0.0178) ES (0.0168) NE (0.0143) UN(0.0139) RE (0.0124) HE (0.0124) ST (0.0118) BE (0.0104) AN (0.0082)

Trigramme (17567 = 263 mogliche)

EIN (0.0122) ICH (0.0111) NDE (0.0089) DIE (0.0087) UND (0.0087) DER(0.0086) CHE (0.0075) END (0.0075) GEN (0.0071) SCH (0.0066) CHT (0.0061)DEN (0.0057) INE (0.0053) NGE (0.0052) NUN (0.0048) UNG (0.0048)

Englisch

Einzelbuchstaben (in Cliquen)

E (12.5)

T (9.2)

A (8.0) O (7.6) I (7.3) N (7.1)

S (6.5) R (6.1) H (5.4)



L (4.1) D (4.0)

C (3.1) U (2.7) M (2.5) F (2.3)

P (2.0) G (2.0) W (1.9) Y (1.7) B (1.5)

V (1.0) K (0.7)

X (0.2) J (0.2) Q (0.1) Z (0.1)

Bigramme

TH (0.0330) HE (0.0270) IN (0.0202) ER (0.0191) RE (0.0169) AN (0.0167) ES(0.0149) EN (0.0146) ON (0.0134) AT (0.0127) TI (0.0126) ED (0.0125) NT(0.0124) ND (0.0122) ST (0.0116) OR (0.0091) AR (0.0083) IS (0.0079) TO(0.0079)

Trigramme

THE (0.0353) ING (0.0111) AND (0.0102) ION (0.0075) TIO (0.0075) ENT(0.0073) ERE (0.0069) HER (0.0068) ATE (0.0066) VER (0.0064) TER (0.0063)THA (0.0062) ATI (0.0059) FOR (0.0059)

Franzosisch

Einzelbuchstaben

E (16) N A S R I U T O L D C M P V F B G X H Q Y Z J K W

Bigramme

ES EN OU DE NT TE ON SE AI IT LE ET ME ER EM

Trigramme

ENT QUE ION LES AIT TIO ANS ONT OUR ANT AIS OUS



Italienisch

Einzelbuchstaben

E (11) I (11) A (11) O R L N T S C D P U M G V H Z B F Q J K W X Y

Bigramme

ER ES ON RE EL EN DE SI DI TI AL NT AN RA

Trigramme

CHE ERE ZIO DEL ECO ARI QUE ATO IDE EDI ESI

Spanisch

Einzelbuchstaben

E (13) A O S R I N L D C T U P M Y Q G V H F B J Z K W X

Bigramme

ES EN EL DE LA OS UE AR RA RE ON ER AS ST AL AD TA CO OR

Trigramme

QUE EST ARA ADO AQU CIO DEL NTE EDE OSA PER NEI IST SDE


14.4 Vigenere-Tafel 14 ANHANG ZUR KRYPTOGRAPHIE

14.4 Vigenere-Tafel

Blaise de Vigenere (1525 - 1596),

Johannes Trithemius (1462 - 1516),

Giovanni Battista Della Porta (1538 - 1615)

A B C D E F G H I J K L M N O P Q R S T U V W X Y Z

B C D E F G H I J K L M N O P Q R S T U V W X Y Z A

C D E F G H I J K L M N O P Q R S T U V W X Y Z A B

D E F G H I J K L M N O P Q R S T U V W X Y Z A B C

E F G H I J K L M N O P Q R S T U V W X Y Z A B C D

F G H I J K L M N O P Q R S T U V W X Y Z A B C D E

G H I J K L M N O P Q R S T U V W X Y Z A B C D E F

H I J K L M N O P Q R S T U V W X Y Z A B C D E F G

I J K L M N O P Q R S T U V W X Y Z A B C D E F G H

J K L M N O P Q R S T U V W X Y Z A B C D E F G H I

K L M N O P Q R S T U V W X Y Z A B C D E F G H I J

L M N O P Q R S T U V W X Y Z A B C D E F G H I J K

M N O P Q R S T U V W X Y Z A B C D E F G H I J K L

N O P Q R S T U V W X Y Z A B C D E F G H I J K L M

O P Q R S T U V W X Y Z A B C D E F G H I J K L M N

P Q R S T U V W X Y Z A B C D E F G H I J K L M N O

Q R S T U V W X Y Z A B C D E F G H I J K L M N O P

R S T U V W X Y Z A B C D E F G H I J K L M N O P Q

S T U V W X Y Z A B C D E F G H I J K L M N O P Q R

T U V W X Y Z A B C D E F G H I J K L M N O P Q R S

U V W X Y Z A B C D E F G H I J K L M N O P Q R S T

V W X Y Z A B C D E F G H I J K L M N O P Q R S T U

W X Y Z A B C D E F G H I J K L M N O P Q R S T U V

X Y Z A B C D E F G H I J K L M N O P Q R S T U V W

Y Z A B C D E F G H I J K L M N O P Q R S T U V W X

Z A B C D E F G H I J K L M N O P Q R S T U V W X Y


14.5 Irreduzible Polynome 14 ANHANG ZUR KRYPTOGRAPHIE

14.5 Irreduzible Polynome

In der folgenden Tabelle sind einige irreduzible Polynome p(x) vom Grad n uberZ/(2) angegeben, die man zur Konstruktion der endlichen Korper F2n verwendenkann. Ab n = 9 sind nur noch die Polynome mit minimaler Anzahl von Ter-men gelistet. (Es ist bekannt, daß man bis n = 10000 mit hochstens 5 Termenauskommt.)

n p(x)1 x, x+ 12 x2 + x+ 13 x3 + x+ 1, x3 + x2 + 14 x4 + x+ 1, x4 + x3 + 1,x4 + x3 + x2 + x+ 15 x5 + x2 + 1, x5 + x3 + 1,

x5 + x4 + x3 + x2 + 1, x5 + x4 + x3 + x+ 1,x5 + x4 + x2 + x+ 1, x5 + x3 + x2 + x+ 1,

6 x6 + x+ 1, x6 + x5 + 1, x6 + x3 + 1,x6 + x5 + x4 + x2 + 1, x6 + x5 + x4 + x+ 1,x6 + x5 + x3 + x2 + 1, x6 + x5 + x2 + x+ 1,x6 + x4 + x3 + x+ 1, x6 + x4 + x2 + x+ 1

7 x7 + x+ 1, x7 + x3 + 1, x7 + x3 + x2 + x+ 1,x7 + x6 + x5 + x4 + x2 + x+ 1, x7 + x5 + x4 + x3 + x2 + x+ 1,(insgesamt 18)

8 x8 + x4 + x3 + x+ 1, x8 + x4 + x3 + x2 + 1,x8 + x7 + x6 + x5 + x4 + x+ 1, x8 + x6 + x5 + x3 + 1,x8 + x7 + x5 + x4 + x3 + x2 + 1, x8 + x6 + x5 + x4 + x2 + x+ 1(insgesamt 30)

9 x9 + x+ 1 (insgesamt 56)10 x10 + x3 + 1 (insgesamt 99)11 x11 + x2 + 1 (insgesamt 186)12 x12 + x3 + 1 (insgesamt 335)13 x13 + x4 + x3 + x+ 1 (insgesamt 630)14 x14 + x5 + 1 (insgesamt 1161)15 x15 + x+ 1 (insgesamt 2182)16 x16 + x5 + x3 + x+ 117 x17 + x3 + 118 x18 + x3 + 119 x19 + x5 + x2 + x+ 120 x20 + x3 + 1


14.5 Irreduzible Polynome 14 ANHANG ZUR KRYPTOGRAPHIE

14.5.1 Der Korper GF(8)

Die Elemente des endlichen Korpers GF (8) = F8 mit acht Elementen, werden alsKoeffizienten-Tripel a2a1a0 der Polynome f(x) = a2x

2 + a1x+ a0 ∈ Z/(2)[x] vomGrad n < 3 geschrieben, also

F8 = {000, 001, 010, 011, 100, 101, 110, 111}.

Die Addition erfolgt daher koordinatenweise modulo 2, bei der Multiplikationf(x) ∗ g(x) werden die Reste bei der Division von f(x) · g(x) durch das irre-duzible Polynom p(x) = x3 + x + 1 genommen. Daher ergibt sich die folgendeMultiplikationstabelle:

* 000 001 010 011 100 101 110 111000 000 000 000 000 000 000 000 000001 000 001 010 011 100 101 110 111010 000 010 100 110 011 001 111 101011 000 011 110 101 111 100 001 010100 000 100 011 111 110 010 101 001101 000 101 001 100 010 111 011 110110 000 110 111 001 101 011 010 100111 000 111 101 010 001 110 100 011

Man kann die Elemente von F8 naturlich auch als Oktalzahlen 0 = 000, . . . , 7 =111 notieren.

Es ist entsprechend p(x) = x4 + x + 1 ein irreduzibles Polynom, das man zurKonstruktion von F16 verwenden kann. Die Elemente dieses Korpers, also diesmalvierstellige Bitfolgen, lassen sich dabei auch als Hexadezimalzahlen darstellen:

F16 = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9, A,B,C,D,E, F}.

Um den Korper F256 zu erzeugen, dessen Elemente man als die moglichen 28 = 256Bytes auffassen kann, geht man ganz analog vor, indem man ublicherweise dasirreduzible Polynom p(x) = x8 + x4 + x3 + x2 + 1 benutzt. Dabei schreibt manoft die Bytes als jeweils zwei Halb-Bytes in hexadezimaler Notation.


14.6 DES 14 ANHANG ZUR KRYPTOGRAPHIE

14.6 DES

14.6.1 Verwendete Permutationen/Expansion

IP IP−1 PC1 PC2 P E IP IP−1 PC1 PC2 E1 58 40 57 14 16 32 33 57 36 31 51 222 50 8 49 17 7 1 34 49 4 23 45 233 42 48 41 11 20 2 35 41 44 15 33 244 34 16 33 24 21 3 36 33 12 7 48 255 26 56 25 1 29 4 37 25 52 62 44 246 18 24 17 5 12 5 38 17 20 54 49 257 10 64 9 3 28 4 39 9 60 46 39 268 2 32 1 28 17 5 40 1 28 38 56 279 60 39 58 15 1 6 41 59 35 30 34 28

10 52 7 50 6 15 7 42 51 3 22 53 2911 44 47 42 21 23 8 43 43 43 14 46 2812 36 15 34 10 26 9 44 35 11 6 42 2913 28 55 26 23 5 8 45 27 51 61 50 3014 20 23 18 19 18 9 46 19 19 53 36 3115 12 63 10 12 31 10 47 11 59 45 29 3216 4 31 2 4 10 11 48 3 27 37 32 117 62 38 59 26 2 12 49 61 34 2918 54 6 51 8 8 13 50 53 2 2119 46 46 43 16 24 12 51 45 42 1320 38 14 35 7 14 13 52 37 10 521 30 54 27 27 32 14 53 29 50 2822 22 22 19 20 27 15 54 21 18 2023 14 62 11 13 3 16 55 13 58 1224 6 30 3 2 9 17 56 5 26 425 64 37 60 41 19 16 57 63 3326 56 5 52 52 13 17 58 55 127 48 45 44 31 30 18 59 47 4128 40 13 36 37 6 19 60 39 929 32 53 63 47 22 20 61 31 4930 24 21 55 55 11 21 62 23 1731 16 61 47 30 4 20 63 15 5732 8 29 39 40 25 21 64 7 25



14.6.2 S-Boxen

S

1

0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 150 14 4 13 1 2 15 11 8 3 10 6 12 5 9 0 71 0 15 7 4 14 2 13 1 10 6 12 11 9 5 3 82 4 1 14 8 13 6 2 11 15 12 9 7 3 10 5 03 15 12 8 2 4 9 1 7 5 11 3 14 10 0 6 13

S

2

0 15 1 8 14 6 11 3 4 9 7 2 13 12 0 5 101 3 13 4 7 15 2 8 14 12 0 1 10 6 9 11 52 0 14 7 11 10 4 13 1 5 8 12 6 9 3 2 153 13 8 10 1 3 15 4 2 11 6 7 12 0 5 14 9

S

3

0 10 0 9 14 6 3 15 5 1 13 12 7 11 4 2 81 13 7 0 9 3 4 6 10 2 8 5 14 12 11 15 12 13 6 4 9 8 15 3 0 11 1 2 12 5 10 14 73 1 10 13 0 6 9 8 7 4 15 14 3 11 5 2 12

S

4

0 7 13 14 3 0 6 9 10 1 2 8 5 11 12 4 151 13 8 11 5 6 15 0 3 4 7 2 12 1 10 14 92 10 6 9 0 12 11 7 13 15 1 3 14 5 2 8 43 3 15 0 6 10 1 13 8 9 4 5 11 12 7 2 14

S

5

0 2 12 4 1 7 10 11 6 8 5 3 15 13 0 14 91 14 11 2 12 4 7 13 1 5 0 15 10 3 9 8 62 4 2 1 11 10 13 7 8 15 9 12 5 6 3 0 143 11 8 12 7 1 14 2 13 6 15 0 9 10 4 5 3

S

6

0 12 1 10 15 9 2 6 8 0 13 3 4 14 7 5 111 10 15 4 2 7 12 9 5 6 1 13 14 0 11 3 82 9 14 15 5 2 8 12 3 7 0 4 10 1 13 11 63 4 3 2 12 9 5 15 10 11 14 1 7 6 0 8 13

S

7

0 4 11 2 14 15 0 8 13 3 12 9 7 5 10 6 11 13 0 11 7 4 9 1 10 14 3 5 12 2 15 8 62 1 4 11 13 12 3 7 14 10 15 6 8 0 5 9 23 6 11 13 8 1 4 10 7 9 5 0 15 14 2 3 12

S

8

0 13 2 8 4 6 15 11 1 10 9 3 14 5 0 12 71 1 15 13 8 10 3 7 4 12 5 6 11 0 14 9 22 7 11 4 1 9 12 14 2 0 6 10 13 15 3 5 83 2 1 14 7 4 10 8 13 15 12 9 0 3 5 6 11



14.6.3 Rundenschlussel

Runde 1

10 51 34 60 49 17 33 57 2 9 19 423 35 25 25 44 58 59 1 36 27 18 41

22 28 39 54 37 4 47 30 5 53 23 2961 21 38 63 15 20 45 14 13 62 55 31

Runde 2

2 43 26 52 41 9 25 49 59 1 11 3460 27 18 17 36 50 51 58 57 19 10 3314 20 31 46 29 63 39 22 28 45 15 2153 13 30 55 7 12 37 6 5 54 47 23

Runde 3

51 27 10 36 25 58 9 33 43 50 60 1844 11 2 1 49 34 35 42 41 3 59 1761 4 15 30 13 47 23 6 12 29 62 537 28 14 39 54 63 21 53 20 38 31 7

Runde 4

35 11 59 49 9 42 58 17 27 34 44 257 60 51 50 33 18 19 26 25 52 43 145 55 62 14 28 31 7 53 63 13 46 2021 12 61 23 38 47 5 37 4 22 15 54

Runde 5

19 60 43 33 58 26 42 1 11 18 57 5141 44 35 34 17 2 3 10 9 36 27 5029 39 46 61 12 15 54 37 47 28 30 45 63 45 7 22 31 20 21 55 6 62 38

Runde 6

3 44 27 17 42 10 26 50 60 2 41 3525 57 19 18 1 51 52 59 58 49 11 3413 23 30 45 63 62 38 21 31 12 14 5520 47 29 54 6 15 4 5 39 53 46 22

Runde 7

52 57 11 1 26 59 10 34 44 51 25 199 41 3 2 50 35 36 43 42 33 60 18

28 7 14 29 47 46 22 5 15 63 61 394 31 13 38 53 62 55 20 23 37 30 6

Runde 8

36 41 60 50 10 43 59 18 57 35 9 358 25 52 51 34 19 49 27 26 17 44 212 54 61 13 31 30 6 20 62 47 45 2355 15 28 22 37 46 39 4 7 21 14 53



Runde 9

57 33 52 42 2 35 51 10 49 27 1 6050 17 44 43 26 11 41 19 18 9 36 594 46 53 5 23 22 61 12 54 39 37 15

47 7 20 14 29 38 31 63 62 13 6 45

Runde 10

41 17 36 26 51 19 35 59 33 11 50 4434 1 57 27 10 60 25 3 2 58 49 4355 30 37 20 7 6 45 63 38 23 21 6231 54 4 61 13 22 15 47 46 28 53 29

Runde 11

25 1 49 10 35 3 19 43 17 60 34 5718 50 41 11 59 44 9 52 51 42 33 2739 14 21 4 54 53 29 47 22 7 5 4615 38 55 45 28 6 62 31 30 12 37 13

Runde 12

9 50 33 59 19 52 3 27 1 44 18 412 34 25 60 43 57 58 36 35 26 17 11

23 61 5 55 38 37 13 31 6 54 20 3062 22 39 29 12 53 46 15 14 63 21 28

Runde 13

58 34 17 43 3 36 52 11 50 57 2 2551 18 9 44 27 41 42 49 19 10 1 607 45 20 39 22 21 28 15 53 38 4 14

46 6 23 13 63 37 30 62 61 47 5 12

Runde 14

42 18 1 27 52 49 36 60 34 41 51 935 2 58 57 11 25 26 33 3 59 50 4454 29 4 23 6 5 12 62 37 22 55 6130 53 7 28 47 21 14 46 45 31 20 63

Runde 15

26 2 50 11 36 33 49 44 18 25 35 5819 51 42 41 60 9 10 17 52 43 34 5738 13 55 7 53 20 63 46 21 6 39 4514 37 54 12 31 5 61 30 29 15 4 47

Runde 16

18 59 42 3 57 25 41 36 10 17 27 5011 43 34 33 52 1 2 9 44 35 26 4930 5 47 62 45 12 55 38 13 61 31 376 29 46 4 23 28 53 22 21 7 63 39


14.7 Quantencodierung 14 ANHANG ZUR KRYPTOGRAPHIE

14.7 Quantencodierung

14.7.1 Schlusselvereinbarung

Ein Eintrag 0|1 bedeutet, daß nach den Gesetzen der Quantenmechanik derEmpfanger mit 50 % Wahrscheinlichkeit ein Photon registriert oder nicht. Der-artige Bits werden vom Sender aussortiert. In der Halfte aller Falle wird alsoeindeutig ein Bit vereinbart, in der anderen Halfte wird das Bit verworfen.

Sender Empfanger Prozent gemessenesEingabe Messung der Falle Bitl l 25 1l ↔ 25 0l ↗ 25 0|1l ↘ 25 0|1↔ l 25 0↔ ↔ 25 1↔ ↗ 25 0|1↔ ↘ 25 0|1↗ l 25 0|1↗ ↔ 25 0|1↗ ↗ 25 1↗ ↘ 25 0↘ l 25 0|1↘ ↔ 25 0|1↘ ↗ 25 0↘ ↘ 25 1

14.7.2 Abgehorter Quantenkanal

Sender Angreifer Prozent gem. Angreifer Empfanger gem.Eingabe Messung der Falle Bit Eingabe Messung Bitl l 25 1 l l 1l ↔ 25 0 l l 1l ↗ 12.5 1 ↗ l 0|1l ↗ 12.5 0 ↘ l 0|1l ↘ 12.5 1 ↘ l 0|1l ↘ 12.5 0 ↗ l 0|1

In 25 % der Falle stort der Angreifer also ein vereinbartes Bit. Dies laßt sichbeispielsweise durch den Vergleich zufallig ausgewahlter Paritatsbits feststellen.


14.8 Inverse modulo 26 14 ANHANG ZUR KRYPTOGRAPHIE

14.8 Inverse modulo 26

Bei der Entschlusselung in affinen Kryptosystemen oder Hill-Kryptosystemenwerden die Inversen zu den ϕ(26) = ϕ(2)ϕ(13) = 12 Restklassen a modulo 26mit ggT (a, 26) = 1 benotigt. Diese sind in der folgenden Tabelle angegeben.

a 1 3 5 7 9 11 15 17 19 21 23 25a−1 1 9 21 15 3 19 7 23 11 5 17 25

oder mit anderen Reprasentanten der Restklassen

a 1 3 5 7 9 11 -11 -9 -7 -5 -3 -1a−1 1 9 -5 -11 3 -7 7 -3 11 5 -9 -1

Multiplikationstabelle mit A = 0, . . . , Z = 25

a A B C D E F G H I J K L M1 0 1 2 3 4 5 6 7 8 9 10 11 123 0 3 6 9 12 15 18 21 24 1 4 7 105 0 5 10 15 20 25 4 9 14 19 24 3 87 0 7 14 21 2 9 16 23 4 11 18 25 69 0 9 18 1 10 19 2 11 20 3 12 21 411 0 11 22 7 18 3 14 25 10 21 6 17 215 0 15 4 19 8 23 12 1 16 5 20 9 2417 0 17 8 25 16 7 24 15 6 23 14 5 2219 0 19 12 5 24 17 10 3 22 15 8 1 2021 0 21 16 11 6 1 22 17 12 7 2 23 1823 0 23 20 17 14 11 8 5 2 25 22 19 1625 0 25 24 23 22 21 20 19 18 17 16 15 14

a N O P Q R S T U V W X Y Z1 13 14 15 16 17 18 19 20 21 22 23 24 253 13 16 19 22 25 2 5 8 11 14 17 20 235 13 18 23 2 7 12 17 22 1 6 11 16 217 13 20 1 8 15 22 3 10 17 24 5 12 199 13 22 5 14 23 6 15 24 7 16 25 8 1711 13 24 9 20 5 16 1 12 23 8 19 4 1515 13 2 17 6 21 10 25 14 3 18 7 22 1117 13 4 21 12 3 20 11 2 19 10 1 18 919 13 6 25 18 11 4 23 16 9 2 21 14 721 13 8 3 24 19 14 9 4 25 20 15 10 523 13 10 7 4 1 24 21 18 15 12 9 6 325 13 12 11 10 9 8 7 6 5 4 3 2 1


15 LOSUNGEN ZU AUSGEWAHLTEN AUFGABEN

15 Losungen zu ausgewahlten Aufgaben

Losung zu Aufgabe 2.18 Sind e, e′ ∈ S beides Einselemente eines Monoids(S, ·), so folgt bereits e = e · e′ = e′, da e Linkseinselement und e′ Rechtseinsele-ment ist.

Losung zu Aufgabe 2.19 Fur |X| = 1, also etwa X = {a}, ist die freie Halb-gruppe X+ = {an | n ∈ N} naturlich kommutativ. Gibt es aber mindestens zweiverschiedene Elemente a 6= b in X, so ist wegen ab 6= ba die freie Halbgruppe X+

niemals kommutativ.

Losung zu Aufgabe 2.20 Ist schon γ|A nicht injektiv, so kann naturlich erstrecht γ nicht injektiv sein. Diese Bedingung ist also notwendig.

Fur A = {a, a′} und B = {0, 1} ist γ : A → B+ gemaß γ(a) = 1 6= 11 =γ(a′) naturlich injektiv. Es gibt ja keine zwei verschiedenen Elemente aus A mitgleichen Bildern. Aber wegen γ(aa) = γ(a)γ(a) = 11 = γ(a′) ist die homomorpheFortsetzung γ : A+ → B+ nicht injektiv.

Losung zu Aufgabe 2.21 In dem multiplikativen Monoid (N0, ·) der naturlichenZahlen sind sowohl U1 = {0} als auch U2 = {1} Unterhalbgruppen, aber es giltU1 ∩ U2 = ∅. Sind dagegen Ui fur eine beliebige Indexmenge I 6= ∅ Unterhalb-gruppen einer Halbgruppe (S, ·) mit D =

⋂i∈I Ui 6= ∅ und sind x, y ∈ D beliebige

Elemente des Durchschnitts, so gilt x, y ∈ Ui fur jedes i ∈ I und daher auchxy ∈ Ui, da jeweils Ui eine Unterhalbgruppe ist. Daraus folgt aber xy ∈ D undsomit ist D Unterhalbgruppe.

Losung zu Aufgabe 2.22 a) Ist M0 = C ein Blockcode, so ist kein Codewortc ∈ C Prafix eines anderen Codewortes c′ 6= c aus C. Daher kann c aus keinemanderen Codewort aus M0 als Prafix herausgekurzt werden. Es folgt M1 = ∅und damit Mn = ∅ sowie Mn ∩ M0 = ∅ fur alle n ≥ 1. Also ist C eindeutigdecodierbar. Dies zeigt die Behauptung sogar fur alle Prafixcodes, also insgesamtBemerkung 2.14 b).

b) Fur M0 = C1 = {0, 10, 01} erhalt man M1 = M−10 M0 = {1}, da einzig das

Codewort c = 0 aus dem anderen Codewort c′ = 01 als Prafix herausgekurztwerden kann und dadurch das Wort 1 liefert. Daher ist M1 ∩M0 = ∅. Nun folgtM2 = M−1

1 M0 ∪M−10 M1 = {0} ∪ ∅ = {0} und damit M2 ∩M0 6= ∅. Dies zeigt,

daß C1 nicht eindeutig decodierbar ist. Man kann naturlich auch sehr schnell dasWort 010 finden, das die beiden moglichen Decodierungen 0|10 und 01|0 besitzt.

Fur M0 = C2 = {1, 10, 00} erhalt man M1 = {0}, also ebenfalls M1 ∩M0 = ∅.Weiter ist M2 = {0} und damit Mn = {0} sowie Mn ∩M0 = ∅ fur alle n ≥ 1.Daher ist C2 eindeutig decodierbar.



c) Es ist M0 = C = {110, 11, 100, 00, 10} und daher M1 = {0} sowie M1∩M0 = ∅.Weiter ist M2 = {0} und damit Mn = {0} sowie Mn ∩M0 = ∅ fur alle n ≥ 1.Daher ist C eindeutig decodierbar.

d) Fur M0 = C1 = {11, 10, 110, 001} ist M1 = {0} sowie M1 ∩M0 = ∅. Weiter istM2 = {01} und damit auch M2 ∩M0 = ∅. Mit M3 = ∅ folgt schließlich Mn = ∅und daher Mn ∩M0 = ∅ fur alle n ≥ 3. Also ist C1 eindeutig decodierbar.

Wegen C2 ⊆ C1 ist naturlich auch C2 eindeutig decodierbar.

Losung zu Aufgabe 2.23 Mit M0 = C(x) ist M1 = M−10 M0 = {x0} und daher

M0 ∩M1 = ∅ fur jedes x ∈ B.

Weiterhin ist M2 = M−11 M0 ∪M−1

0 M1 = ∅ ∪ ∅ = ∅ fur x = 0 und daher C(0)eindeutig decodierbar. Fur x ∈ {1, 2} hat manM2 = {x0} und daherM2∩M0 = ∅.

In diesem Fall folgt M3 = {0} und daher auch noch M3 ∩M0 = ∅.

Schließlich ist aber M4 = {1} und damit M4 ∩ M0 6= ∅. Daher ist C(x) furx ∈ {1, 2} nicht eindeutig decodierbar.

Fur x = 1 ist beispielsweise das Wort 2101 = 210|1 = 2|1|01 nicht eindeutigdecodierbar, fur x = 2 das Wort 2201 = 220|1 = 2|2|01.

Losung zu Aufgabe 2.24 Mit M0 = C(x, y) ist M1 = M−10 M0 = {y} bei x 6= 2

und M1 = {y, 1} bei x = 2. Daher gilt stets M0 ∩M1 = ∅ und M−10 M1 = ∅.

Fur x = 2 und y = 2 gilt M2 = M−11 M0 = {0, 01} und daher M2 ∩M0 6= ∅. Also

ist C(2, 2) nicht eindeutig decodierbar.

Fur x = 2 und y = 0 gilt M2 = {1, 10} und daher M2 ∩M0 = ∅ sowie M3 =M−1

2 M0∪M−10 M2 = ∅. Also ist C(2, 0) = {01, 20, 201, 010} eindeutig decodierbar.

Das Wort 0120101010 besitzt die eindeutige Zerlegung 01|201|01|010 in C(2, 0)+.

Fur x = 2 und y = 1 gilt M2 = {1} und daher M2 ∩M0 = ∅ sowie M3 = ∅.Also ist auch C(2, 1) = {01, 20, 201, 011} eindeutig decodierbar. Eine moglicheZerlegung von 0120101010 muß wegen des dritten Zeichens mit 01 beginnen unddann wegen des funften Zeichens mit 201 fortgesetzt werden. Im Rest 01010 istdann aber das dritte Zeichen unmoglich. Daher gehort das Wort nicht zu C(2, 1)∗.

Fur x 6= 2 und y = x gilt 01 ∈M2 = M−11 M0 und daher M2 ∩M0 6= ∅. In diesen

Fallen ist C(x, y) also nicht eindeutig decodierbar. Dies sind C(0, 0) und C(1, 1).

Fur x 6= 2 und y 6= x gilt M2 = M−11 M0 = {1, 10} bei y = 0 (und x = 1), M2 = ∅

bei y = 1 (und x = 0) und M2 = {0} bei y = 2 (und x = 0 oder x = 1). Im



ersten Fall gilt M3 = {01, 1} und daher ist C(1, 0) nicht eindeutig decodierbar.Im zweiten Fall ist C(0, 1) = {01, 20, 001, 011} eindeutig decodierbar. Im drittenFall gilt M3 = {1, 12, 01} (bei x = 0) oder M3 = {1, 12} und M4 = {01} (beix = 1). Also ist weder C(0, 2) noch C(1, 2) eindeutig decodierbar.

Eine Zerlegung von 0120101010 uber C(0, 1) muß wegen des dritten Zeichens mit01|20 beginnen, aber dann ist das nachste Zeichen unmoglich.

Losung zu Aufgabe 3.31 Es ist E3 = {000, 110, 101, 011} der binare Linear-code der Lange 3, der aus allen 4 Vektoren mit geradem Gewicht besteht, alsoA2(3, 2) ≥ 4. Sei weiterhin C ⊆ {0, 1}3 ein beliebiger binarer Blockcode derLange 3 mit d(C) = 2. Wegen der Translationsinvarianz der Hamming-Metrikdarf c0 = 000 ∈ C angenommen werden. Dann kann keiner der drei Einheitsvek-toren aus {0, 1}3 in C liegen, da diese von c0 den Abstand 1 haben. Es bleiben furdie restlichen Vektoren aus C also nur die drei Vektoren mit geradem Gewichtund der Vektor c1 = 111. Im Fall c1 ∈ C kann aber keiner der drei Vektoren mitgeradem Gewicht in C liegen, da diese von c1 den Abstand 1 besitzen. Also giltin diesem Fall |C| = 2. Liegt dagegen c1 nicht in C, so kann C außer c0 hochstensnoch die drei Vektoren mit geradem Gewicht enthalten. Es folgt |C| ≤ 4.

Losung zu Aufgabe 3.32 Bei der ISBN10 wird das Kontrollzeichen gemaß

10 · c1 + 9 · c2 + . . .+ 2 · c9 + c10 ≡ 0 mod 11

berechnet. Es ist also

c10 ≡ (−10) · c1 + (−9) · c2 + . . .+ (−2) · c9 mod 11.

Modulo 11 bedeutet dies aber gerade

c10 ≡ c1 + 2 · c2 + . . .+ 9 · c9 mod 11.

Losung zu Aufgabe 3.33 Sei C ein (7, 23, 5)-Code. Wegen der Translationsinva-rianz der Hamming-Metrik darf c0 = (0, 0, 0, 0, 0, 0, 0) ∈ C angenommen werden.Da es insgesamt 23 = 8 Codevektoren gibt, die untereinander mindestens denAbstand 5 haben, gibt es einen Vektor c1 6= c0, der mindestens 5 Einsen enthalt.Durch Permutation der Koordinaten darf man zu einem aquivalenten Code uber-gehen, bei dem in c1 die ersten 5 Koordinaten gleich 1 sind. Dann hat jederweitere Vektor c ∈ {0, 1}7 mit Abstand d(c, c0) ≥ 5 mindestens 5 Einsen. Davonsind mindestens 3 an denselben Positionen wie in c1. Daher gilt d(c, c1) ≤ 4.Es gibt also keine 8 Vektoren der Lange 7, die paarweise den Minimalabstand 5haben.

Losung zu Aufgabe 3.34 Es ist

E4 = {0000, 0011, 0101, 1001, 0110, 1010, 1100, 1111} ∈ {0, 1}4



ein (4, 8, 2)-Code, der die MDS-Schranke erreicht.

Losung zu Aufgabe 3.37 Nach Aufgabe 3.32 gilt also

4 ≡ 3 + 8 + 3x+ 8 + 10 + 30 + 28 + 72 + 27 mod 11.

Dies fuhrt wegen 3 + 8 = 11, 72 + 27 = 99, 30 + 28 = 58 und 8 + 10 − 4 = 14modulo 11 zu

3x+ 6 ≡ 0 mod 11.

Diese Gleichung hat die eindeutig bestimmte Losung x = 9.

Damit ergibt sich die ISBN13 aus

9 + 21 + 8 + 9 + 4 + 27 + 2 + 6 + 5 + 12 + 9 + 9 + y ≡ 0 mod 10,

also aus1 + y ≡ 0 mod 10.

Es ist daher x = y = 9.

Losung zu Aufgabe 4.35 Elementare Zeilenumformungen ergeben die systema-tische Generatormatrix

G =(

1 0 60 1 13

)und damit die Kontrollmatrix

H = ( 11 4 1 ) .

Da jede Spalte von H linear unabhangig ist, es aber zwei linear abhangige Spaltengibt, ist die Minimaldistanz d(C) = 2.

Sind gi die Zeilenvektoren von G, so ist zur Decodierung von c = (12, 5, 4) derVektor (k1, k2) ∈ Z/(17)2 mit c = k1g1 + k2g2 gesucht. Zu losen ist also das(uberbestimmte) lineare Gleichungssystem

7k1 + 4k2 = 128k1 + 16k2 = 5

11k1 + 11k2 = 4

Wegen 16 = −1 in Z/(17) kann man das 4-fache der zweite Gleichung auf dieerste addieren und erhalt 5k1 = 15, also k1 = 3. Einsetzen in die erste Gleichungliefert 4 + 4k2 = 12, also k2 = 2. Die Probe 33 + 22 = 55 = 4 zeigt, daß auch diedritte Gleichung erfullt ist. Daher ist c tatsachlich die Codierung von (3, 2).



Losung zu Aufgabe 4.36 Der Linearcode Cx ist genau dann selbstdual, wennfur alle Zeilenvektoren v, w (einschließlich v = w) einer Generatormatrix Gx dieBedingung v · wT = 0 erfullt ist.

Fur den ersten Zeilenvektor v = (2, 1, 0, 2, 2 + x, 0) und den dritten Zeilenvektorw = (1, 1, 1, 0, 0, 1 − 3x) von Gx erhalt man aber immer v · wT = 2 + 1 = 3 6= 0in Z/(5). Daher ist Gx niemals selbstdual.

Zur Bestimmung der Minimaldistanz d(Cx) = wt(Cx) wird Satz 4.8 verwendet.Dazu wird zunachst aus Gx eine Generatormatrix in systematischer Form berech-net und dann die zugehorige Kontrollmatrix Hx gemaß Lemma 4.10 bestimmt.

Alle Rechnungen erfolgen im Korper Z/(5) und die Elemente dieses Korpers wer-den durchgangig mit −2,−1, 0, 1, 2 bezeichnet, um die Zahlen klein zu halten.Wegen −2 · 2 = −4 = 1 sind insbesondere 2 und −2 invers zueinander.

Nimmt man den dritten Zeilenvektor von Gx als ersten Basisvektor, zieht diesenvom zweiten ab, um den zweiten Basisvektor zu erhalten, und zieht diesen wieder-um vom ersten Zeilenvektor von Gx ab, so erhalt man die neue Generatormatrix 1 1 1 0 0 1 + 2x

2 0 0 2 1 + x 1 + 2x0 1 0 0 1 −1− 2x

.Multipliziert man den zweiten Zeilenvektor mit -2, um den neuen ersten Zeilen-vektor zu erhalten, nimmt man den dritten Zeilenvektor als neuen zweiten undzieht beide vom ersten Zeilenvektor ab, so erhalt man bereits eine Generatorma-trix in systematischer Form: 1 0 0 1 −2− 2x −2 + x

0 1 0 0 1 −1− 2x0 0 1 −1 1 + 2x −1− 2x

.Die zugehorige Kontrollmatrix ist dann

Hx =

−1 0 1 1 0 02 + 2x −1 −1− 2x 0 1 02− x 1 + 2x 1 + 2x 0 0 1

.Fur x = 2 sind offensichtlich die dritte und vierte Spalte von H2 identisch. Esgilt daher d(C2) = 2.

Die erste Spalte von Hx kann nur linear abhangig von der dritten oder viertenSpalte sein. Fur x 6= 2 ist sie wegen der dritten Koordinate aber nicht linearabhangig von der vierten Spalte. Von der dritten Spalte kann sie aber nur linearabhangig sein, wenn in der zweiten Koordinate −2− 2x = −1− 2x gelten wurde,



was unmoglich ist. Daher ist die erste Spalte von keiner anderen Spalte linearabhangig.

Wie gerade gesehen, ist die dritte Spalte nicht von der ersten Spalte linearabhangig. Sie kann daher hochstens noch linear abhangig von der vierten Spaltesein, wenn sie mit dieser identisch ist. Fur x 6= 2 ist dies aber unmoglich.

Schließlich kann die zweite Spalte hochstens noch linear abhangig von der funftenSpalte sein, was aber wiederum fur x 6= 2 wegen der dritten Koordinate unmoglichist.

Damit existieren fur x 6= 2 keine zwei linear abhangigen Spalten von Hx und esist d(Cx) ≥ 3.

Losung zu Aufgabe 4.39 Zu zeigen ist also, daß die angegebenen Bedingungenfur C1 und C2 notwendig sind, damit C1∞C2 ein MDS-Code sein kann. Es istnicht zu zeigen (weil nicht behauptet), daß C1∞C2 ein MDS-Code ist, falls C1

und C2 die angegebenen Bedingungen erfullen.

Nach Lemma 4.24 ist C1∞C2 jedenfalls ein [2n, k1+k2,min{2d1, d2}]-Linearcode,der als MDS-Code daher

d(C1∞C2) = min{2d1, d2} = 2n− (k1 + k2) + 1 = (n− k1) + (n− k2) + 1

erfullt.

Aus min{2d1, d2} = 2d1 < d2 wurde wegen der Singleton-Schranke (Satz 3.23)

2d1 < d2 ≤ (n− k2) + 1 ≤ (n− k1) + (n− k2) + 1 = d(C1∞C2) = 2d1

folgen, was einen Widerspruch darstellt. Daher gilt

d2 ≤ n− k2 + 1 ≤ (n− k1) + (n− k2) + 1 = min{2d1, d2} ≤ d2,

also uberall die Gleichheit. Dies zeigt einerseits n − k1 = 0, d. h. C1 = Kn,andererseits auch d2 = n− k2 + 1, d. h. C2 ist ein MDS-Code.

Losung zu Aufgabe 5.17 Es werden zunachst die moglichen Generatorpolynomeg(x) vom Grad m = n − k = 4 als Teiler von x6 − 1 = (x3 − 1)(x3 + 1) =(x− 1)(x2 +x+ 1)(x+ 1)(x2−x+ 1) = (x− 1)(x− 3)(x+ 4)(x+ 1)(x− 4)(x+ 3)bestimmt.

Dies sind die(62

)= 15 Polynome, die man durch alle moglichen Streichungen

von jeweils zwei dieser sechs Linearfaktoren erhalt.

g1(x) = (x−1)(x−3)(x+4)(x+1) = (x2 +1)(x2 +x+1) = x4 +x3 +2x2 +x+1,



g2(x) = (x−1)(x−3)(x+ 4)(x−4) = (x2−4x+ 3)(x2 + 10) = x4−4x3−x+ 4 =(x3 − 1)(x− 4),

g3(x) = (x−1)(x−3)(x+4)(x+3) = (x2+3x−4))(x2−9) = x4+3x3−6x2−x+10,

g4(x) = (x− 1)(x− 3)(x+ 1)(x− 4) = . . .,

g5(x) = (x− 1)(x− 3)(x+ 1)(x+ 3) = . . .,

g6(x) = (x− 1)(x− 3)(x− 4)(x+ 3) = . . .,

g7(x) = (x− 1)(x+ 4)(x+ 1)(x− 4) = . . .,

g8(x) = (x− 1)(x+ 4)(x+ 1)(x+ 3) = . . .,

g9(x) = (x− 1)(x+ 4)(x− 4)(x+ 3) = . . .,

g10(x) = (x− 1)(x+ 1)(x− 4)(x+ 3) = . . .,

g11(x) = (x− 3)(x+ 4)(x+ 1)(x− 4) = . . .,

g12(x) = (x− 3)(x+ 4)(x+ 1)(x+ 3) = . . .,

g13(x) = (x− 3)(x+ 4)(x− 4)(x+ 3) = . . .,

g14(x) = (x− 3)(x+ 1)(x− 4)(x+ 3) = . . .,

g15(x) = (x+4)(x+1)(x−4)(x+3) = (x2 +4x+3)(x2 +10) = x4 +4x3 +x+4 =(x3 + 1)(x+ 4).

Zu g1(x) = x4 + x3 + 2x2 + x+ 1 gehort die Generatormatrix

G1 =(

1 1 2 1 1 00 1 1 2 1 1

),

oder in systematischer Form

G′1 =(

1 0 1 −1 0 −10 1 1 2 1 1

).

Hieraus ergibt sich eine Kontrollmatrix von C1 zu

H1 =

−1 −1 1 0 0 01 −2 0 1 0 00 −1 0 0 1 01 −1 0 0 0 1

.Multiplikation von v = (1, 1, 1, 1, 1, 1) mit der letzten Zeile von H1 liefert denWert 1, der v /∈ C1 anzeigt.



Losung zu Aufgabe 5.18 Es werden die moglichen Generatorpolynome g(x) alsTeiler von x4−1 = (x2+1)(x2−1) = (x2+1)(x+1)(x−1) bestimmt. Wegen |C| = 3hat der gesuchte Code die Dimension 1 uber Z/(3), sein Generatorpolynom mußdaher den Grad 3 haben. Es kommen also nur g1(x) = (x2 + 1)(x + 1) = x3 +x2 + x + 1 und g2(x) = (x2 + 1)(x − 1) = (x2 + 1)(x + 2) = x3 + 2x2 + x + 2 inFrage. Dabei liefert g1(x) den Wiederholungscode C1 = {0000, 1111, 2222} undg2(x) den gesuchten anderen zyklischen Ternarcode C2 = {0000, 1212, 2121}.

Losung zu Aufgabe 5.19 Da selbstduale binare Linearcodes stets eine geradeLange haben, gibt es keine derartigen Codes fur n = 7.

Fur gerades n = 2k muß ein selbstdualer Binarcode die Dimension k besitzen.

Bei n = 6 sind also selbstduale zyklische Codes mit einem Generatorpolynom g(x)vom Grad k = 3 zu bestimmen. Diese sind Teiler von x6− 1 = (x3− 1)(x3 + 1) =(x3− 1)2. Wegen x3− 1 = (x− 1)(x2 +x+ 1) und da x2 +x+ 1 als quadratischesPolynom ohne Nullstelle bereits irreduzibel ist, ist g(x) = x3 − 1 das einzigeGeneratorpolynom eines zyklischen Linearcodes der Dimension 3 und der Lange 6.Da g(x) = h(x) gleichzeitig Kontrollpolynom ist, ist dieser Code auch selbstdual.Es gibt daher genau einen selbstdualen zyklischen Binarcode der Lange 6.

Bei n = 8 sind entsprechend die Generatorpolynome g(x) vom Grad 4 als Teilervon x8 − 1 zu bestimmen. Wegen x8 − 1 = (x − 1)8 gibt es genau ein solchesPolynom, namlich g(x) = (x−1)4 = x4−1. Auch hier ist g(x) = h(x) gleichzeitigKontrollpolynom und der Code daher selbstdual. Es gibt also ebenfalls genaueinen selbstdualen zyklischen Binarcode der Lange 8.

Losung zu Aufgabe 5.20 Fur die Lange n = 3 sind also alle Generatorpolynomeg(x) als Teiler von x3 − 1 = (x− 1)3 zu bestimmen. Dies sind

g0(x) = 1,

g1(x) = x− 1,

g2(x) = (x− 1)2 = x2 − 2x+ 1 = x2 + x+ 1

g3(x) = (x− 1)3 = x3 − 1.

Dazu gehoren die zyklischen Linearcodes

C0 = Z/(3)3,

C1 = {000, 012, 120, 201, 102, 021, 210, 102, 111},C2 = {000, 111, 222},C3 = {0}.



Fur die Lange n = 4 sind also alle Generatorpolynome g(x) als Teiler von x4−1 =(x2 + 1)(x2 − 1) = (x2 + 1)(x+ 1)(x− 1) zu bestimmen. Dies sind

g0(x) = 1,

g1(x) = x− 1 = x+ 2,

g2(x) = x+ 1,

g3(x) = x2 + 1,

g4(x) = (x+ 2)(x+ 1) = x2 + 2,

g5(x) = (x2 + 1)(x+ 1) = x3 + x2 + x+ 1,

g6(x) = (x2 + 1)(x+ 2) = x3 + 2x2 + x+ 1,

g7(x) = x4 − 1.

Losung zu Aufgabe 5.22 Es sind zunachst alle Generatorpolynome g(x) vomGrad 2 als Teiler von x4− 1 = (x2− 1)(x2 + 1) = (x− 1)(x+ 1)(x− 2)(x+ 2) zubestimmen. Dies sind

g1(x) = (x− 1)(x+ 1) = x2 − 1,

g2(x) = (x− 1)(x− 2) = x2 − 3x+ 2,

g3(x) = (x− 1)(x+ 2) = x2 + x− 2,

g4(x) = (x+ 1)(x− 2) = x2 − x− 2,

g5(x) = (x+ 1)(x+ 2) = x2 + 3x+ 2,

g6(x) = (x− 2)(x+ 2) = x2 + 1.

Da keines dieser Polynome gleich seinem eigenen Kontrollpolynom ist, erzeugtkeines einen selbstdualen Code. Die zugehorigen sechs Generatormatrizen sind

G1 =(

1 0 −1 00 1 0 −1

),

G2 =(

1 −3 2 00 1 −3 2

),

G3 =(

1 1 −2 00 1 1 −2

),

G4 =(

1 −1 −2 00 1 −1 −2

),

G5 =(

1 3 2 00 1 3 2

),

G6 =(

1 0 1 00 1 0 1

).



Losung zu Aufgabe 5.23 Es sind zunachst alle Generatorpolynome g(x) vomGrad 2 als Teiler von x4− 1 = (x2− 1)(x2 + 1) = (x− 1)(x+ 1)(x− 5)(x− 8) zubestimmen. Dies sind

g1(x) = (x− 1)(x+ 1) = x2 − 1,

g2(x) = (x− 1)(x− 5) = x2 + 7x+ 5,

g3(x) = (x− 1)(x− 8) = x2 + 4x+ 8,

g4(x) = (x+ 1)(x− 5) = x2 + 9x+ 8,

g5(x) = (x+ 1)(x− 8) = x2 + 6x+ 5,

g6(x) = (x− 5)(x− 8) = x2 + 1.

Dual zueinander sind g1 und g6 sowie g2 und g5 und schließlich g3 und g4. Diezugehorigen sechs Generatormatrizen sind

G1 =(

1 0 −1 00 1 0 −1

),

G2 =(

1 7 5 00 1 7 5

),

G3 =(

1 4 8 00 1 4 8

),

G4 =(

1 9 8 00 1 9 8

),

G5 =(

1 6 5 00 1 6 5

),

G6 =(

1 0 1 00 1 0 1

).

Dem Codevektor c = (1, 3, 6, 4) entspricht das Polynom c(x) = x3 + 3x2 + 6x+ 4.Wegen c(1) = 1, c(−1) = 0, c(5) = 234 = 0 und c(8) = c(−4) = −64 + 48− 24 +4 = −36 = −3 in Z/(13) ist von den Generatorpolynomen nur g4(x) ein Teiler vonc(x), d. h. c liegt nur in dem von G4 erzeugten Code: c = (1, 9, 8, 0)−6(0, 1, 9, 8).

Losung zu Aufgabe 5.24 Offensichtlich ist g(x) = xn−1+xn−2+· · ·+x+1 ∈ K[x]wegen xn − 1 = (x− 1)g(x) Generatorpolynom eines zyklischen Linearcodes derDimension n−(n−1) = 1 uber K. Die zugehorige Generatormatrix G = (1 . . . 1)zeigt, daß der erzeugte Code gerade der Wiederholungscode der Lange n ist.


Index

(n,M, d)-Code, 13[n, k, d]-Code, 24[n, k]-Code, 24

abgeschlossene Kugel, 12AES, 50Alphabet, 2, 5–8, 12Angreifer

aktiver, 3passiver, 3

Angriff mit gewahltem Geheimtext, 49Angriff mit gewahltem Klartext, 49ASCII-Code, 2Assoziativgesetz, 5Ausloschung, 2Authentifikation, 3

Blockchiffre, 49, 51innere, 64

Blockcode, 6–8, 10, 13, 21e-fehlerkorrigierender, 13t-fehlererkennender, 13

Brute-Force-Angriff, 49Buchstabe, 2, 5

Chiffrieralgorithmus, 46chiffrieren, 3Chiffrierung, 46, 50Code, 6, 8

binarer, 6dualer, 24eindeutig decodierbarer, 8, 10irreduzibler, 8perfekter, 14, 28selbstdualer, 24sofort decodierbarer, 8ternarer, 6, 15, 28trivialer, 6, 13, 24, 38trivialer perfekter, 15

Codeverkurzung, 31Codeverschachtelung, 31

Codeworter, 6Codierung, 2, 6

eindeutig decodierbare, 6homomorphe, 6, 7

Datenubertragunganaloge, 2digitale, 2

Dechiffrieralgorithmus, 46dechiffrieren, 3Dechiffrierung, 46, 50Decodierausfall, 22Decodierschema, 22, 29, 43

vollstandiges, 22Decodierung, 2DES, 50, 64Diffie-Hellman-Verfahren, 74

EAN, 17Einselement, 5, 10Einwegfunktion, 47, 66, 73Einzelfehler, 2Element

primitives, 73ElGamal-Kryptosystem, 48ElGamal-Verfahren, 74, 78elliptische Kurve, 75, 77, 79

nicht-singulare, 77, 78singulare, 77, 79

Empfanger, 2, 74unbefugter, 3

Entschlusselung, 46, 50Entschlusselungsexponent, 67Erweiterungscode, 16, 24, 33Erzeugermatrix, 26

Falltur, 47, 66, 73Fano-Bedingung, 8Fehler, 2Fehlerbundel, 2, 31, 43Fehlererkennung, 2

133

INDEX INDEX

Fehlerkorrektur, 2Feistel-Chiffre, 64formale Sprache, 6

Geheimtext, 3, 46, 67, 75Geheimtext-Angriff, 48Generatormatrix, 26, 40Generatorpolynom, 40gespreizte Chiffre, 50Gewicht, 25Gilbert-Varshamov-Schranke, 34Golay-Code

binarer, 15ternarer, 15

Gray-Code, 7Griesmer-Schranke, 33

Halbgruppe, 5, 10freie, 5, 6, 10

Hamming-Abstand, 12Hamming-Code, 15, 28, 33, 44Hamming-Distanz, 12, 25Hamming-Schranke, 15Hill-Kryptosystem, 48Homophone, 46

Information, 2Informationsrate, 6, 27Informationsstellen, 27Integritat, 3ISBN, 17, 23ISIN, 20, 23

Kanal, 2Klartext, 3, 46, 67, 75Klartext-Geheimtext-Angriff, 49Kommutativgesetz, 5Komplexprodukt, 6Konkatenation, 5Kontrollcode, 19Kontrollgleichung, 3, 19Kontrollmatrix, 26, 28, 41Kontrollpolynom, 41Kontrollstellen, 27

Kontrollzeichen, 17Kryptographie, 3Kryptologie, 3Kryptosystem, 4, 46, 66, 73

affines, 47, 52asymmetrisches, 46klassisches, 46mit offentlichen Schlusseln, 47monoalphabetisches, 47perfekt sicheres, 61polyalphabetisches, 48symmetrisches, 46

Kugelpackungsgleichung, 15, 28

Lange, 6Linearcode, 24

systematischer, 27zyklischer, 38

Logarithmusdiskreter, 73

MDS-Code, 21, 30Minimaldistanz, 13, 21, 25Minimalgewicht, 25Monoid, 5

freies, 6Multiplikation, 5

Nachricht, 2

Paritatsbit, 3Paritatscode, 17, 19Permutations-Kryptosystem, 48Postfix, 5Prafix, 5Prafix-Code, 8, 9Primitivwurzel, 73, 74, 76Primzahl, 66, 73, 74, 77Produkt, 5Punktierung, 31

Quanten-Kanal, 62Quanten-Kryptographie, 62Quelle, 2


INDEX INDEX

Rabin-Kryptosystem, 48Redundanz, 2Reed-Muller-Codes, 32Reed-Solomon-Code, 30, 43Restklassenfuhrer, 29RSA-Algorithmus, 66RSA-Kryptosystem, 48RSA-Modul, 67

Satz von McMillan, 8Schlussel, 3, 46, 62, 64, 74, 75

offentlicher, 66, 73involutorischer, 47, 52

Schlusselraum, 50Schlusselstromalphabet, 50Schlusselstromgenerator, 50Selbstschlussel-Chiffre, 51Sender, 2, 74, 75Shanks Algorithmus, 75Simplex-Code, 28Singleton-Schranke, 21Sphare, 12Strings, 6Stromchiffre, 50

periodische, 50synchrone, 50

Substitutions-Kryptosystem, 47Suffix, 5Symbol, 2Syndrom, 29

Trager, 25Translations-Kryptosystem, 47Transpositions-Kryptosystem, 48

Unterhalbgruppe, 7

verschlusseln, 3Verschlusselung, 46, 50Verschlusselungsexponent, 67Vertauschungsfehler, 14, 19Vigenere-Kryptosystem, 47, 51

Worter, 6

Wiederholung eines Codes, 7Wiederholungscode, 7, 14, 22, 24, 38, 43Wort

leeres, 6

zyklische Verschiebung, 24, 38


Documents

Codierungstheorie - tu-freiberg.dehebisch/skripte/codtheorie/codierung.pdf · je zwei Elementen a;b2S genau ein Produkt ab2S zuordnet, so daˇ das Assoziativgesetz gilt: (2) a(bc)